УДК 004.272.2: 519.63
БАЛАНСИРОВКА ЗАГРУЗКИ ПРОЦЕССОРОВ ПРИ МОДЕЛИРОВАНИИ РАСПРОСТРАНЕНИЯ ЗАГРЯЗНЕНИЙ С УЧЕТОМ ХИМИЧЕСКОЙ КИНЕТИКИ В УСЛОВИЯХ МЕДЛЕННОГО ДРЕЙФА “ГОРЯЧИХ” ОБЛАСТЕЙ
Пекунов В.В.

Наиболее совершенные математические модели распространения загрязнений обычно учитывают не только первичное загрязнение в результате диффузионного и конвективного переносов загрязняющих веществ, но и вторичное загрязнение в результате происходящих химических реакций. Как следствие, подобные модели помимо динамических уравнений механики сплошной среды (для скорости, давления, температуры, концентраций загрязняющих веществ) содержат систему уравнений химической кинетики следующего вида:
	,	(1)
где Сj — концентрация j-го вещества, Fj — функция, выражающая скорость образования j-го вещества, T — температура, NВ — число веществ. Данная система обычно интегрируется одним из численных методов (Гира, Арсеньева-Демидова, Рожкова).
При необходимости расчета картины загрязнений в достаточно большой расчетной области суммарный объем вычислений очень велик, что приводит к необходимости распараллеливания вычислений.
Наилучшие результаты дают методы распараллеливания по пространству, основанные на распределении узлов расчетной сетки по процессорам. Для динамических уравнений объемы вычислений в различных узлах обычно отличаются незначительно, что позволяет использовать простое разбиение расчетной области на прямоугольные блоки, каждый из которых обрабатывается “своим” процессором. Для систем уравнений химической кинетики вида (1) объемы вычислений в узлах существенно варьируются в зависимости от жесткости системы, которая, в свою очередь, зависит от многих факторов, прежде всего от температуры. Соответственно, для обеспечения равномерной загрузки процессоров необходимо так распределить между ними узлы расчетной сетки (в первую очередь самые “горячие”), чтобы исключить простои в работе. Поскольку в ходе вычислений распределение “горячих” узлов может изменяться, процедуру балансировки загрузки следует выполнять на каждой итерации.
Известен централизованный алгоритм балансировки, где управляющий процессор владеет всеми значениями концентраций веществ в каждом узле и информацией о времени их обработки. В начале каждой итерации данный процессор распределяет узлы по рабочим процессорам, а в конце — собирает. При этом велики количество и объем пересылок между управляющим и рабочими процессорами, что существенно снижает эффективность распараллеливания [1].
Более совершенен алгоритм [1], предложенный для моделирования задач горения с быстрым изменением местоположения “горячих” точек. Суть алгоритма заключается в распределенной балансировке загрузки, когда каждый процессор обрабатывает некоторое множество локальных узлов, а затем запрашивает по одному узлу для обработки у других процессоров.
Основным недостатком указанного алгоритма является наличие большого числа коротких транзакций, что малоэффективно для систем со сравнительно высокой латентностью каналов связи (например, сетей Fast Ethernet), когда серия коротких сообщений передается медленнее, чем одного длинное. Существует “нижний” порог эффективности данного алгоритма, когда время t1 на обработку одного узла сравнимо со временем tп на передачу короткого сообщения, содержащего блок необходимых данных об этом узле. При t1 < tп эффективность падает.
Предложим алгоритм, лишенный вышеуказанного недостатка. Для многих задач распространения загрязнений характерен относительно медленный дрейф “горячих” областей, когда выполняется соотношение , где hmin — минимальное расстояние между узлами расчетной сетки;  — шаг интегрирования по времени; Vдрейф — максимальная скорость дрейфа “горячих” участков; k — положительный коэффициент, превышающий единицу. Тогда время, затраченное на пересчет концентраций в каком-либо узле на итерации s, незначительно отличается от аналогичного времени на итерации s + 1. Для распределения вычислительной нагрузки на итерации s + 1 с достаточно высокой степенью достоверности можно использовать информацию о времени обработки узлов на предыдущей итерации s. Так как произвести точный замер времени обработки узла затруднительно (по причине малости), можно считать, что время прямо пропорционально числу проделанных итераций метода Гира. Пусть имеется NП процессоров, каждый из которых имеет номер в диапазоне от 1 до NП. Каждому из них изначально принадлежит некоторое множество узлов, выделенное, например, в результате разбиения расчетной области на блоки. Предлагаемый алгоритм балансировки включает следующую последовательность действий, выполняемую на каждом i-м процессоре:
1. Подсчет величины собственной предполагаемой несбалансированной загрузки , где Tij — количество итераций метода Гира, проделанное для обработки j-го узла на предыдущей итерации (на первой итерации можно считать, что i j Tij = 1); Pi — количество узлов, принадлежащих i-му процессору.
2. Передача значения Li всем остальным процессорам.
3. Подсчет предполагаемой средней загрузки , дисбаланса загрузки  и допустимого дисбаланса , где  — величина порядка 10-3 или меньше, подбираемая экспериментально.
4. Если  < E, то для данного процессора балансировка не требуется. Он обрабатывает все принадлежащие ему узлы и переходит к шагу 12. Иначе осуществляется переход к шагу 5.
5. Определение ролей процессоров на данной итерации. Формируются два списка (S и R), состоящие из двоек вида (j, Qj), где Qj первоначально присвоено значение . В список отправителей S попадают j-е процессоры, для которых Mj  E. В список получателей R попадают j-е процессоры, для которых Mj  – E. Списки сортируются по убыванию . Отметим, что каждый процессор присутствует только в одном из списков, что и определяет его роль.
6. Создание списка транзакций, состоящего из троек вида (j, k, Vjk), где j — номер процессора-отправителя; k — номер процессора-получателя; Vjk — величина загрузки, которую j-й процессор передает k-му процессору. Изначально список транзакций пуст. Пусть (s, Qs) — текущий элемент списка S, а (r, Qr) — текущий элемент списка R. Первоначально это первые элементы списков (с наибольшим ). Пока не исчерпан список S и не исчерпан список R выполнять цикл (6.1 - 6.3):
6.1. Если Qr > Qs, то уменьшить Qr на величину Qs, добавить в список транзакций тройку (s, r, Qs), обнулить Qs. Иначе уменьшить Qs на величину Qr, добавить в список транзакций тройку (s, r, Qr), обнулить Qr.
6.2. Если Qs = 0, то выбрать следующий элемент списка S.
6.3. Если Qr = 0, то выбрать следующий элемент списка R.
7. Для каждой из транзакций (i, k, Vik), где текущий i-й процессор выступает в роли отправителя, создается список узлов, которые будут передаваться на обработку k-му процессору (передаются температура и концентрации веществ). Список формируется в первую очередь из узлов, для которых ожидается наибольшее количество итераций метода Гира. При этом суммарное количество итераций для узлов, входящих в список не должно быть меньше Vik.
8. Запускаются (в асинхронном режиме) все транзакции, в которых принимает участие текущий i-й процессор. Одновременно с этим идет обработка тех узлов, принадлежащих текущему процессору, которые не передаются на обработку другим процессорам.
9. Обработка “локальных” узлов завершается.
10. Если i-й процессор является получателем, то он ожидает завершения инициированных транзакций приема, обрабатывает полученные узлы и отсылает обратно результат вместе с информацией о числе проделанных итераций.
11. Если i-й процессор является отправителем, то он инициирует получение результатов обработки с информацией о числе проделанных итераций.
12. Конец итерации.
Данный алгоритм балансировки используется в параллельной программе математического моделирования распространения загрязнений в воздушном бассейне большого города и в окрестности предприятия. Эксперименты показали, что эффективность алгоритма стабилизируется на уровне 973% (в расчет не принимаются самые первые несколько десятков итераций моделирования, когда в расчетной области могут идти быстрые переходные процессы, на которые данный алгоритм не рассчитан).
Дальнейшее совершенствование алгоритма возможно в двух направлениях:
а) введение средств предсказания времени вычислений в узлах, например, путем обучения нейронной сети или построения специальных экстраполяционных функций;
б) использование дополнительного алгоритма балансировки (например, того же алгоритма [1]) в конце итерации для сглаживания остаточного дисбаланса. Но следует заметить, что это имеет смысл лишь при величине дисбаланса, превышающей 34%, в противном случае дополнительная балансировка, вероятно, лишь снизит эффективность распараллеливания за счет дополнительных накладных расходов на передачи данных.

1. Корнилина М.А., Якобовский М.В. Динамическая балансировка загрузки процессоров при моделировании задач горения // Высокопроизводительные вычисления и их приложения: Тр. Всеросс. науч. конф. - М.: Изд-во МГУ, 2000. - С.34-39.

Автор: Пекунов Владимир Викторович.
Адрес: 153008, Иваново, а/я 1160.
Телефон: (0932) 38-37-36 (служ.)