Е. И. ВИЗГАЛОВ, А. В. КРЯНЕВ, Г. В. ЛУКИН
Московский инженерно-физический институт (государственный университет)
АВТОМАТИЗАЦИЯ ПЛАНИРОВАНИЯ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ В РАСПРЕДЕЛЁННЫХ СИСТЕМАХ
В работе рассматриваются математические модели и алгоритмы минимизации общего времени вычисления сложной, допускающей распараллеливание задачи в рамках GRID-комплекса. Минимизация общего времени вычисления задачи достигается за счёт оптимального распределения отдельных её подзадач по вычислительным узлам GRID-комплекса.
GRID-комплекс - инфраструктура, объединяющая в единое целое множество территориально распределённых ресурсов разных типов, включающих рабочие станции, вычислительные кластеры, хранилища данных, средства визуализации, научные приборы и много другое [1]. Вычислительная мощность отдельных узлов GRID-комплекса, а также пропускная способность соединяющих их каналов связи, в общем случае различны. В связи с этим, до сих пор остаётся актуальной проблема минимизации общего времени решения сложной задачи путём выбора оптимальной стратегии распределения её отдельных подзадач по узлам GRID-комплекса во времени.
В настоящей работе представлены результаты проведённых исследований в области оптимизации вычислений для решения в рамках GRID-комплекса сложной комплексной задачи, допускающей распараллеливание. Исследования проводились в двух основных направлениях:
· поиск оптимального распределения подзадач по узлам GRID-комплекса при неизменном количестве вычислительных узлов (первая основная задача);
· определение минимально допустимого числа вычислительных узлов GRID-комплекса, необходимых для решения сложной задачи за минимальное время (вторая основная задача).
В работе было введено понятие процессорной конфигурации 
GRID-системы, позволяющее установить соответствие между вычислительными узлами комплекса и решаемыми на них подзадачами, а также определить порядок решения этих подзадач.
Таким образом, первая основная задача сводится к поиску оптимальной конфигурации 
, являющейся решением следующей минимаксной задачи [2]:
(1)
В выражении (1) минимум и максимум берутся относительно 
множества возможных процессорных конфигураций и k = 1, …, n соответственно, 
реализованное время расчета k-ой ветви при условии использования процессорной конфигурации . Следовательно, оптимальная процессорная конфигурация GRID-комплекса обеспечивает минимальное время расчета для самой напряженной ветви при решении комплексной задачи.
Минимаксная оптимизационная задача (1) решается при помощи итерационного процесса, на каждом шаге которого выбирается лучшая конфигурация для самой напряженной ветви в рамках рассматриваемого шага итераций.
Решение второй основной задачи сводится к поиску минимального числа вычислительных узлов GRID-комплекса, обеспечивающих выполнение равенства в следующем выражении [2]:
(2)
Алгоритм решения второй основной задачи сводится к последовательному решению ряда минимаксных задач вида (1), на каждом шаге которого увеличивается или уменьшается число m вычислительных узлов GRID-комплекса. Процесс останавливается, когда для m = m* имеем в выражении (2) равенство, а для m = m* - 1 – неравенство.
В докладе приведены численные результаты, позволяющие оценить эффективность предлагаемого подхода для планирования параллельных вычислений в распределённых системах
Список литературы
1. Foster, C. Kesselman, S. Tuecke. The Anotomy of the Grid: Enabling Scalable Virtual Organizations. International J. Supercomputer Applications, 15(3), 2001.
2. , , А., , Говоров и решение задач оптимизации конфигурации программного обеспечения для интеграции корпоративных приложение. М.: МИФИ, Препринт №., 2007.
