Development and application of the computational model for skeleton solutions. Case study - using “bag-of-task” for hrbf neural network learning

Full Text

Введение. Эпоха увеличения тактовых частот вычислительных ядер процессоров закончена, её конец ознаменовал начало эпохи многоядерных процессоров и распределенных вычислительных систем [1]. На текущий момент огромное количество задач математического моделирования требует разработки параллельных (распределенных) программ. Это требование связано с необходимостью увеличения размерности и сокращения времени решения © 2014 Самарский государственный технический университет. Образец для цитирования: Л и т в и н о в В. Г. Разработка и применение вычислительной модели типовых решений. Пример использования «портфеля задач» для обучения нейронной сети HRBF // Вестн. Сам. гос. техн. ун-та. Сер. Физ.-мат. науки, 2014. № 3 (36). С. 183-195. doi: 10.14498/vsgtu1341. 183 Л и т в и н о в В. Г. задачи. Инженерная сложность такой разработки во много раз выше, чем стандартный последовательный подход и переход от численного метода к реализации программы для высокопроизводительных вычислений. На данный момент это остается самостоятельной научной и инженерной проблемой. Данная проблема выделена академиком Г. И. Марчуком как фундаментальное научное направление, называемое проблемой отображения [2]. Одним из методов её решения является повторное использование имеющихся паттернов (шаблонов или типовых решений), что отражено в работе Э. Гамма, Р. Хелма, Р. Джонсона и Дж. Влиссидеса [3]. В области типовых решений для параллельного программирования известны работы отечественных и зарубежных ученых: М. И. Коула [4], С. Макдональда [5], Д. Шмидта [6], П. К. Берзигиярова [7], В. Э. Малышкина [8] и других. Описано около двух десятков типовых решений в области параллельного программирования. Однако задача разработки моделей типовых решений, удобных для понимания специалистами прикладных областей и для конструирования программ на их основе, сохраняет актуальность. 1. Метод. В работе предлагается подход к реализации параллельных паттернов, близкий к языкам координации [9, 10]. Модели выполнения данных языков отражают только аспекты, относящиеся к синхронизации и обмену данными в параллельных алгоритмах. Таким образом, можно строить скелеты типовых решений, которые пользователь затем дополняет последовательным кодом, относящимся к конкретной прикладной задаче. Строится точная модель исполнения в виде графа и его динамической интерпретации. Далее на примере типового решения «портфель задач» [11] показано, каким образом при помощи графической нотации выполняется связь абстрактной модели исполнения с операциями типового решения. Наконец, в терминах этих операций определяется конкретный алгоритм обучения нейронной сети типа HRBF (Hyper-Radial Basis Function). Распараллеливание алгоритма благодаря введённой модели выполнения производится единообразно для различных типовых решений и зависит только от программно-аппаратной платформы целевой системы исполнения. Предлагаемый подход близок к реализованному в библиотеке tbb::gragh пакета Intel Threading Building Blocks [12], однако он не ограничен только языком C++. По сравнению с техниками инкрементного распараллеливания (Cilk [13], OpenMP [14], DVM [15]), в которых последовательный код пользователя дополняется распараллеливающими инструкциями, в данном подходе код каркаса (последовательный, но с известным методом распараллеливания) дополняется пользовательским кодом. Проводимые в дальнейшем вычислительные эксперименты призваны подтвердить, что это не снижает производительность результирующих программ и пригодно для применения в случаях, когда специалисту предметной области требуется построить параллельный алгоритм и выполнить вычислительный эксперимент на высокопроизводительной технике. 2. Построение имитационной модели. Для описания типовых решений использовалась темпоральная логика Лампорта [16, 17]. C её помощью структуру алгоритмов можно представить ориентированным графом вида GM (P, C) , P ⊂ N, C ⊂ N × N, в котором вершины P представляют собой процессы, а дуги C - каналы, по 184 Разработка и применение вычислительной модели типовых решений. . . которым передаются сообщения между процессами. Состояние вычислительного процесса - значения множества переменных, связанных с процессами и каналами: f (i ∈ P : ai ; (i, j) ∈ C : ei,j , di,j ) , где ai ∈ {1, 0}, bi,j ∈ {1, 0}, di,j ∈ {1, 0}. Логические переменные ai обозначают пассивное 0 или активное 1 состояние процесса i; ei,j - пассивное 0 или активное 1 состояние канала (i, j); di,j - направление передачи сообщений по двунаправленным каналам (1 - i → j; 0 - j → i). В начальном состоянии некоторые каналы находятся в активном состоянии с передачей сообщений в направлении i → j, все процессы находятся в пассивном состоянии: I ∀i ∈ P : ai ∧ ∀ (i, j) ∈ C : (ei,j ∧ di,j ) ∨ (ei,j ∧ di,j ) . Действия, выполняемые каналами, описываются формулой Ac (i, j) ei,j ∧ ei,j ∧ di,j ∧ di,j ∨ di,j ∧ di,j ∨ ei,j ∧ ei,j ∧ ∨ di,j ∧ di,j ∨ di,j ∧ di,j . (1) Действия описывают соседние в истории вычислительного процесса состояния, переменные следующего состояния обозначены апострофом. Согласно формуле (1), состояние канала периодически меняется с активного на пассивное, а направление передачи данных - с прямого на обратное. Действия, выполняемые процессами, описываются формулой Ap (i) ai ∧ ai ∧ ∃!j : ei,j ∧ ei,j ∧ di,j ∧ ∃j : ej,i ∧ ej,i ∧ dj,i ∨ ∨ ai ∧ ai ∧ ∃!j : ej,i ∧ ej,i ∧ dj,i ∧ ∃j : ei,j ∧ ei,j ∧ di,j ∨     ∨ ai ∧ ai ∧ ei,k ∧ ei,k ∧ di,k ∨   k : (i,k)∈C     ek,i ∧ ek,i ∧ dk,i ∨ ai ∧ ai . (2) ∨ ai ∧ ai ∧   k : (k,i)∈C Процесс становится активным, когда из смежного с ним канала поступает сообщение. При этом такой канал сам переходит в пассивное состояние. Среди нескольких каналов, готовых передать сообщение в процесс, выбирается произвольный канал. Когда процесс завершит работу и перейдет в пассивное состояние, по одному или нескольким каналам от него могут передаваться сообщения в другие процессы. С учетом выражений (1) и (2) действия, выполняемые моделируемым вычислительным процессом, можно представить в виде Ac (i, j) ∨ N (i,j)∈C Ap (i) . i∈P 185 Л и т в и н о в В. Г. Способ планирования вычислительного процесса характеризуется выражением F ∀i ∈ P : W Ff ai ∧ ai ∧ ∀ (i, j) ∈ C : W Ff ei,j ∧ ei,j , подразумевающим справедливую в слабом смысле стратегию планирования. Окончательно получаем модель вычислительных процессов для представления типовых решений: ΦM I ∧ [N ]f ∧ F. (3) По построению вычислительного процесса порядок смены состояний, удовлетворяющий формуле (3), легко воспроизвести дискретно-событийной имитационной моделью. Для этого организуется очередь каналов, находящихся в активном состоянии. На каждом шаге моделирования случайным образом выбирается активный канал. Далее он переводится в неактивное состояние, выполняется действие процесса и отправка сообщений из данного процесса. Для представления типового решения далее требуется определить сообщения, передаваемые в каналах, и методы процессов, запускаемые при их обработке. Это реализуется использованием графической нотации Templet [18-20]. Так как типовыми схемами решения многих переборных и оптимизационных задач являются схемы «управляющий-рабочие», далее рассматривается модель одной из общих схем управления вычислениями из данного класса: вычисление с «портфелем задач». Это схема с активными рабочими, реализующая управление pull-типа. Здесь иллюстрируется описание более сложного протокола взаимодействия процессов с несколькими типами сообщений (по сравнению с исходными (1) протоколами «запрос-ответ»). Подробное описание реализации шаблона приведено в работе [21], для дальнейшей ясности приведем фрагмент диаграммы управляющего процесса с именем Master (рис. 1), относящийся к порту pN , где N - номер порта. Методы процесса get, put, if_task и start реализуют специфические для решаемой задачи операции: get - извлечение очередной задачи; put - сохранение результата; if_task - проверку наличия задачи для обработки. Метод start может использоваться для инициализации. Методы if_active, waitN , stopN , waitingN являются универсальными для произвольного численного метода. Метод if_active возвращает истинное значение, если имеются активные рабочие процессы. То есть имеются каналы, не находящиеся в состоянии «доставлено сообщение start или result», что в программной реализации определяется простым подсчетом при поступлении и отправке сообщений. Метод waitN устанавливает признак, что канал находится в состоянии ожидания появления заданий, метод waitingN возвращает значение данного признака. Метод stopN используется при отправке сообщения stop рабочему для начала очистки. Роль рабочих процессов заключается в периодическом получении задания от управляющего процесса в сообщении task и отправке результата его обработки result. Обработка выполняется в методе do. Цикл обработки начинается по инициативе рабочего с отправки сообщения start и заканчивается при получении от управляющего процесса сообщения stop. Остановка вычислений и очистка начинаются, если нет задач и нет активных рабочих процессов. Когда сформирована и отправлена очередная задача, происходит поиск ожидающего рабочего процесса. Если такой процесс 186 Разработка и применение вычислительной модели типовых решений. . . Рис. 1. Фрагмент диаграммы управляющего процесса Master [Figure 1. Fragment of the Master control process diagram] найдется и есть еще одна задача для обработки, то выполняется ее формирование и отправка рабочему. В противном случае управляющий процесс либо заканчивает обработку сообщения и ждет ответа от рабочих, либо начинает остановку вычислений и очистку. Для типового решения «портфель задач» разработаны среды многопоточного исполнения на основе Windows API, POSIX и MPI, позволяющие проводить высокопроизводительные вычисления на системах с общей и распределённой памятью. 3. Реализация алгоритма обучения. Параллельный алгоритм обучения был реализован для HRBF нейронной сети [22, 23] на языке C++ с использованием библиотеки CLAPACK. Он основан на использовании метода грубой силы и выполняет обучение и подбор количества нейронов скрытого слоя [24]. Алгоритм заключается в итеративном добавлении различающихся случайным положением центра нейронов в идентичные копии нейронных сетей. На каждой итерации производится выбор лучшей сети (по критерию достижения минимального значения целевой функцией) и её клонирование. Применение типового решения «портфель задач», фрагмент которого показан на рис. 1, состоит в определении его методов get, put, if_task. В «портфеле задач» для управления вычислениями хранятся: 1) K - текущее количество нейронов в скрытом слое; 2) Kmax - максимальное число нейронов в скрытом слое; 3) W - число решенных задач; 4) Wmax - максимальное количество задач (попыток добавления нейрона); 5) Eend - значение, при достижении целевой функцией которого процесс обучения останавливается; 6) ΨK - коэффициенты обученной нейронной сети с K нейронами (включают вектора центров, матрицы диаметров и вектор весов выходного слоя); 7) ΨK+1 - коэффициенты обученной нейронной сети с K + 1 нейронами; 8) EK+1 - значение целевой функции сети Ψ. Задача определяется коэффициентами ΨK и положением центра добавляемого нейрона ψ . Результат её вычисления - коэффициенты ΨK+1 и значение 187 Л и т в и н о в В. Г. ошибки EK+1 . Как и в последовательном случае, при решении задачи производится уточнение коэффициентов сети Ψn+1 -гибридным алгоритмом. В начальном состоянии (start) определяются постоянные алгоритма Kmax , Wmax , Eend ; переменные W := 0, K := 2, ΨK := Ψ2 (параметры сети с двумя нейронами), ΨK+1 - не определены, EK+1 Eend . Проверка наличия задачи (if_task). Возможна выборка очередной задачи на обработку, если одновременно выполняются следующие условия: не достигнута заданная ошибка обучения EK+1 < Eend ; остались невыданные задачи W < Wmax . Алгоритм извлечения задачи (get). Присвоить ΨK := ΨK ; определить случайное положение центра нейрона ψ . Увеличить счетчик запущенных задач W := W + 1. Алгоритм помещения результата вычисления задачи (put). Если EK+1 < EK+1 , то определить EK+1 := EK+1 и ΨK+1 := ΨK+1 . Если W = Wmax , то закончено обучение слоя. В этом случае, если K < Kmax , переходим к следующему слою: K := K + 1; W := 0. Алгоритм завершается, когда будут обучены все сети с числом нейронов до Kmax включительно либо будет достигнуто заданное значение ошибки обучения EK+1 Eend . 4. Численный эксперимент. Эксперимент по обучению нейронной сети параллельным алгоритмом на основе типового решения «портфель задач» был проведен на кластере Сергей Королёв (http://hpc.ssau.ru). Запуск задач производился на узлах 3-х типов с 3-мя различными типами процессоров соответственно: 1) узлы с процессорами типа Intel®Xeon®X5560 (8M Cache, 2.80 GHz, 6.40 GT/s Intel®QPI), имеющими 8 вычислительных ядер; 2) узлы с процессорами типа Intel®Xeon®X5670 (12M Cache, 2.93 GHz, 6.40 GT/s Intel®QPI), имеющими 12 вычислительных ядер; 3) узлы с процессорами типа Intel®Xeon®E5-2665 (20M Cache, 2.40 GHz, 8.00 GT/s Intel®QPI), имеющими 16 вычислительных ядер. В рамках данного эксперимента на быстродействие влияло количество доступных вычислительных ядер на узле, остальные параметры ощутимого влияния не оказывали. Условия эксперимента состояли в следующем. 1. Варьировалось максимальное количество рабочих процессов P «портфеля задач» (объявлено в конкретном эксперименте). 2. Предельное количество нейронов Kmax во всех экспериментах равнялось 100. 3. Количество попыток добавления нейронов Wmax во всех экспериментах равнялось 100. Для осуществления сравнительного анализа были произведены замеры времени исполнения последовательного и параллельного алгоритмов. Для минимизации воздействия сторонней динамической нагрузки процессоров на измеряемое время производилось по 20 запусков. При этом полученное время исполнения параллельного алгоритма tpr i (P ) было усреднено: tpr (P ) = 188 1 20 20 i=1 tpr i (P ). (4) Разработка и применение вычислительной модели типовых решений. . . Рис. 2. Зависимость времени исполнения от количества рабочих процессов (8-ядер) [Figure 2. Dependence of the performance on the number of worker processes (8 cores)] Рис. 3. Зависимость СКО от количества рабочих процессов (8-ядер) [Figure 3. Dependence of the standard deviation (SD) on the number of worker processes (8 cores)] Рис. 4. Зависимость времени исполнения от количества рабочих процессов (12-ядер) [Figure 4. Dependence of the performance on the number of worker processes (12 cores)] Рис. 5. Зависимость СКО от количества рабочих процессов (12-ядер) [Figure 5. Dependence of the standard deviation (SD) on the number of worker processes (12 cores)] 189 Л и т в и н о в В. Г. Для времени исполнения последовательного алгоритма tsq i было найдено минимальное значение tsq min = min tsq 1 , tsq 2 , . . . , tsq 20 , и на его основе рассчитано эталонное время исполнения параллельного алгоритма tstd (P ) = tsq min /P. (5) Среднеквадратическое отклонение (СКО) рассчитывалось для tpr i (P ). На узлах с процессорами Intel®Xeon®X5560 максимальное количество рабочих процессов P изменялось в интервале [1, 2, . . . , 20]. Данные, полученные при проведении эксперимента, приведены на рис. 2, соответствующее среднеквадратическое отклонение изображено на рис. 3. На узлах с процессорами Intel®Xeon®X5570 максимальное количество рабочих процессов P изменялось в интервале [1, 2, . . . , 30]. Данные, полученные при проведении эксперимента, приведены на рис. 4, соответствующее среднеквадратическое отклонение изображено на рис. 5. На узлах с процессорами Intel®Xeon®E5-2665 максимальное количество рабочих процессов P изменялось в интервале [1, 2, . . . , 40]. Данные, полученные при проведении эксперимента, приведены на рис. 6, соответствующее среднеквадратическое отклонение изображено на рис. 7. Рис. 6. Зависимость времени исполнения от количества рабочих процессов (16-ядер) [Figure 6. Dependence of the performance on the number of worker processes (16 cores)] Рис. 7. Зависимость СКО от количества рабочих процессов (16-ядер) [Figure 7. Dependence of the standard deviation (SD) on the number of worker processes (16 cores)] Заключение. Анализируя графики, изображенные на рис. 2-7, можно сделать вывод, что усредненное время исполнения параллельного алгоритма (4), разработанного с использованием типового решения «портфель задач», лишь немного больше эталонного времени исполнения последовательного алгоритма (5). 190 Разработка и применение вычислительной модели типовых решений. . . Также можно заметить, что при достижении количеством рабочих процессов значения, приблизительно равного удвоенному количеству физических вычислительных ядер, уменьшение времени исполнения параллельного алгоритма практически прекращается. Это объясняется наличием технологии Hyper-threading в процессорах (удвоенное количество вычислительных потоков по отношению к количеству ядер). Если продолжать увеличивать количество рабочих процессов, то в связи с ростом накладных расходов время исполнения начнёт возрастать. Следовательно, число рабочих процессов, равное количеству вычислительных потоков, можно считать оптимальным и рекомендовать для использования в экспериментах с применением типового решения «портфель задач». Реализация параллельного алгоритма с использованием данного типового решения значительно снижает трудоёмкость построения параллельного численного метода и сокращает объем кода, введенного ручным способом [25]; избавляет программиста от необходимости проектирования параллельной программы и, следовательно, уменьшает вероятность ошибок. Еще одно достоинство применения данного метода заключается в платформонезависимости. Для переноса программы с одной операционной системы на другую или с платформы, имеющей общую память, на платформу с распределенной памятью достаточно лишь заменить библиотеку времени исполнения, при этом программа будет компилироваться без каких-либо доработок (при условии, что она написана по стандартам ANSI С/С++). Разработанное в настоящей работе типовое решение «портфель задач» включено в состав веб-сервиса автоматизации параллельных вычислений на суперкомпьютере Сергей Королёв Самарского государственного аэрокосмического университета, развернутого по адресу http://templet.ssau.ru [26].

About the authors

Vladimir G Litvinov

S. P. Korolyov Samara State Aerospace University (National Research University)

Email: litvinov_vg@ssau.ru
Assistant, Dept. of Information Systems & Technology 34, Moskovskoe sh., Samara, 443086, Russian Federation

References

Supplementary files