ПАРАЛЛЕЛЬНЫЙ АЛГОРИТМ ОБУЧЕНИЯ СТРУКТУРЫ БАЙЕСОВСКОЙ СЕТИ
КРАТКИЕ СООБЩЕНИЯ
УДК 004.056.53 ПАРАЛЛЕЛЬНЫЙ АЛГОРИТМ ОБУЧЕНИЯ СТРУКТУРЫ БАЙЕСОВСКОЙ СЕТИ С.А. Арустамов, В.Ю. Дайнеко
Представлена реализация масштабируемого параллельного алгоритма обучения структуры байесовской сети. Произведен сравнительный анализ последовательного и параллельного алгоритмов. Ключевые слова: обучение структуры байесовской сети, вычисления на графических процессорах.
В основе алгоритмов обучения структуры байесовской сети (БС) лежат два подхода: ограничение условной независимости (в этом случае сеть может оказаться неориентированной, частично обученной) и оценка меры качества сети (оптимизация локального поиска с полным перебором всех комбинаций, сопровождающаяся экспоненциальным ростом вычислений с увеличением числа узлов сети). Известный гибридный алгоритм обучения Max-Min Hill-Climbing (MMHC) включает оба этих подхода и состоит в следующем [Л]. Вначале применяется алгоритм ограничения условной независимости Max-Min Parents and Children (MMPC), который на основе данных обучения восстанавливает «скелет» БС. Далее в MMHC используется алгоритм оптимизации меры качества сети Hill-Climbing (HC). Тем не менее, применение гибридного алгоритма MMHC в работе с крупными сетями не решает проблему минимизации времени обучения. Цель представляемой авторами работы – уменьшение времени обучения гибридного алгоритма MMHC.
Предлагается использование платформы параллельных вычислений на графических процессорах (ГП) Compute Unified Device Architecture (CUDA), которая позволяет добиться значительного вычислительного ускорения. Архитектура CUDA для ГП поколения Geforce 600 позволяет объединить 4 видеокарты с двуядерными ГП, что позволяет одновременно работать с 12 288 потоковыми процессорами. Основные подходы для распараллеливания алгоритма обучения MMHC заключаются в следующих оптимизациях для работы с архитектурой CUDA. 1. Разделение обрабатываемых данных на подмножества и вычисление промежуточных данных для ка-
ждого подмножества отдельными потоковыми процессорами, работающими одновременно. 2. Использование механизма синхронизации доступа к общей памяти для каждого из потоков. 3. Масштабирование размеров заданий пулом потоков для функции ядра в зависимости от выбранного
количества работающих потоков в блоках вычисления и используемой памяти для их работы. 4. Сведение к минимуму использования ветвлений внутри функций ядра.
Начало
Инициализация
1
Начало
Инициализация
For all x in V MMCPC Set CPC
For all CPCx in set CPC
For all x in CPCx
Фаза 1 MMCPC While
For all x in CPC cudaFreq
cudaFreq (X,T|CPC )
...
cudaFreq (X,T|CPC )
cudaIndep
Фаза 2 MMCPC For all x in CPC
cudaFreq
cudaFreq (X,T|CPC )
...
cudaFreq (X,T|CPC )
cudaIndep
Начало
Инициализация
G=empty L=empty While15 pass imp For allx in PCx
cudaScore
...cudaScore
(x, PCx)
cudaScore (x, PCx)
MMCPC PCx
Set PC Конец
...cudaIndep
(X,T|CPC )
cudaIndep (X,T|CPC )
Max Min Heuristic
Пока CPC присоединяется
...cudaIndep
(X,T|CPC )
cudaIndep (X,T|CPC )
CPC Конец
core x Best G Конец
1
аб
в
Рисунок. Блок-схема алгоритма MMPC (а); блок-схемы параллельных алгоритмов Max-Min Candidate Parents and Children (MMCPC) (б) и HC (в)
Разработаны следующие функции ядра архитектуры CUDA на языке С: cudaFreq – вычисление
частоты появления всех комбинаций принимаемых значений между тестируемыми переменными из обу-
чающего набора данных D с N экспериментами; cudaIndep – тест на независимость двух переменных X и
Y при данной переменной Z; cudaScore – вычисление меры качества сети для целевого узла T от его по-
томков. Блок-схемы применяемых алгоритмов представлены на рисунке.
Для сравнения производительности разработанного параллельного алгоритма MMHC с последова-
тельной реализацией использовался персональный компьютер Intel Core i5 2500 3,5 ГГц с оперативной па-
мятью 4 ГБ; видеокарта Nvidia Geforce 9600GT с 64 потоковыми процессорами; операционная система
170
Научно-технический вестник информационных технологий, механики и оптики, 2013, № 2 (84)
КРАТКИЕ СООБЩЕНИЯ
Ubuntu 12.04; набор разработчика CUDA Toolkit 4.0. Использовался тип данных float. Тестирование производилось пятью разными входными данными размером выборок от 1024 до 16384 записей. Размер БС – 14 узлов. В результате эксперимента для размера выборки данных 16384 время работы параллельного алгоритма сократилось до 36 раз и составило 1,46 с по сравнению с последовательным алгоритмом MMHC.
Разработанный параллельный алгоритм обучения структуры БС позволяет значительно сократить время обучения и масштабируется в зависимости от доступности потоковых процессоров. [Л]. Tsamardinos I., Brown L.E., Aliferis C.F. The max-min hill-climbing bayesian network structure learning algorithm // Springer Science, Machine learning. – 2006. – V. 65. – № 1. – P. 31–78.
Арустамов Сергей Аркадьевич – Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики, доктор технических наук, профессор, sergey.arustamov@gmail.com Дайнеко Вячеслав Юрьевич – Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики, аспирант, daynekovy@yandex.ru
Научно-технический вестник информационных технологий, механики и оптики, 2013, № 2 (84)
171
УДК 004.056.53 ПАРАЛЛЕЛЬНЫЙ АЛГОРИТМ ОБУЧЕНИЯ СТРУКТУРЫ БАЙЕСОВСКОЙ СЕТИ С.А. Арустамов, В.Ю. Дайнеко
Представлена реализация масштабируемого параллельного алгоритма обучения структуры байесовской сети. Произведен сравнительный анализ последовательного и параллельного алгоритмов. Ключевые слова: обучение структуры байесовской сети, вычисления на графических процессорах.
В основе алгоритмов обучения структуры байесовской сети (БС) лежат два подхода: ограничение условной независимости (в этом случае сеть может оказаться неориентированной, частично обученной) и оценка меры качества сети (оптимизация локального поиска с полным перебором всех комбинаций, сопровождающаяся экспоненциальным ростом вычислений с увеличением числа узлов сети). Известный гибридный алгоритм обучения Max-Min Hill-Climbing (MMHC) включает оба этих подхода и состоит в следующем [Л]. Вначале применяется алгоритм ограничения условной независимости Max-Min Parents and Children (MMPC), который на основе данных обучения восстанавливает «скелет» БС. Далее в MMHC используется алгоритм оптимизации меры качества сети Hill-Climbing (HC). Тем не менее, применение гибридного алгоритма MMHC в работе с крупными сетями не решает проблему минимизации времени обучения. Цель представляемой авторами работы – уменьшение времени обучения гибридного алгоритма MMHC.
Предлагается использование платформы параллельных вычислений на графических процессорах (ГП) Compute Unified Device Architecture (CUDA), которая позволяет добиться значительного вычислительного ускорения. Архитектура CUDA для ГП поколения Geforce 600 позволяет объединить 4 видеокарты с двуядерными ГП, что позволяет одновременно работать с 12 288 потоковыми процессорами. Основные подходы для распараллеливания алгоритма обучения MMHC заключаются в следующих оптимизациях для работы с архитектурой CUDA. 1. Разделение обрабатываемых данных на подмножества и вычисление промежуточных данных для ка-
ждого подмножества отдельными потоковыми процессорами, работающими одновременно. 2. Использование механизма синхронизации доступа к общей памяти для каждого из потоков. 3. Масштабирование размеров заданий пулом потоков для функции ядра в зависимости от выбранного
количества работающих потоков в блоках вычисления и используемой памяти для их работы. 4. Сведение к минимуму использования ветвлений внутри функций ядра.
Начало
Инициализация
1
Начало
Инициализация
For all x in V MMCPC Set CPC
For all CPCx in set CPC
For all x in CPCx
Фаза 1 MMCPC While
For all x in CPC cudaFreq
cudaFreq (X,T|CPC )
...
cudaFreq (X,T|CPC )
cudaIndep
Фаза 2 MMCPC For all x in CPC
cudaFreq
cudaFreq (X,T|CPC )
...
cudaFreq (X,T|CPC )
cudaIndep
Начало
Инициализация
G=empty L=empty While15 pass imp For allx in PCx
cudaScore
...cudaScore
(x, PCx)
cudaScore (x, PCx)
MMCPC PCx
Set PC Конец
...cudaIndep
(X,T|CPC )
cudaIndep (X,T|CPC )
Max Min Heuristic
Пока CPC присоединяется
...cudaIndep
(X,T|CPC )
cudaIndep (X,T|CPC )
CPC Конец
core x Best G Конец
1
аб
в
Рисунок. Блок-схема алгоритма MMPC (а); блок-схемы параллельных алгоритмов Max-Min Candidate Parents and Children (MMCPC) (б) и HC (в)
Разработаны следующие функции ядра архитектуры CUDA на языке С: cudaFreq – вычисление
частоты появления всех комбинаций принимаемых значений между тестируемыми переменными из обу-
чающего набора данных D с N экспериментами; cudaIndep – тест на независимость двух переменных X и
Y при данной переменной Z; cudaScore – вычисление меры качества сети для целевого узла T от его по-
томков. Блок-схемы применяемых алгоритмов представлены на рисунке.
Для сравнения производительности разработанного параллельного алгоритма MMHC с последова-
тельной реализацией использовался персональный компьютер Intel Core i5 2500 3,5 ГГц с оперативной па-
мятью 4 ГБ; видеокарта Nvidia Geforce 9600GT с 64 потоковыми процессорами; операционная система
170
Научно-технический вестник информационных технологий, механики и оптики, 2013, № 2 (84)
КРАТКИЕ СООБЩЕНИЯ
Ubuntu 12.04; набор разработчика CUDA Toolkit 4.0. Использовался тип данных float. Тестирование производилось пятью разными входными данными размером выборок от 1024 до 16384 записей. Размер БС – 14 узлов. В результате эксперимента для размера выборки данных 16384 время работы параллельного алгоритма сократилось до 36 раз и составило 1,46 с по сравнению с последовательным алгоритмом MMHC.
Разработанный параллельный алгоритм обучения структуры БС позволяет значительно сократить время обучения и масштабируется в зависимости от доступности потоковых процессоров. [Л]. Tsamardinos I., Brown L.E., Aliferis C.F. The max-min hill-climbing bayesian network structure learning algorithm // Springer Science, Machine learning. – 2006. – V. 65. – № 1. – P. 31–78.
Арустамов Сергей Аркадьевич – Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики, доктор технических наук, профессор, sergey.arustamov@gmail.com Дайнеко Вячеслав Юрьевич – Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики, аспирант, daynekovy@yandex.ru
Научно-технический вестник информационных технологий, механики и оптики, 2013, № 2 (84)
171