BC/NW 2006, №2, (9) :4.3

РЕШЕНИЕ ЗАДАЧ МОДЕЛИРОВАНИЯ ПО ИНТЕРВАЛАМ ВРЕМЕНИ НА КЛАСТЕРНОЙ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЕ

Ладыгин И.И., Яньков С.Г.

(Москва, Московский энергетический институт (технический университет), Россия)

Решение прикладных задач (ПЗ) на кластерных системах (КлС) достаточно сложный процесс и требует больших усилий для эффективного использования всей мощности такой ВС по сравнению с обычными ПК. Для этого требуется учет всех особенностей КлС еще на стадии разработки алгоритма ПЗ. Наиболее узким местом в КлС является коммуникационная сеть (КС), существенно влияющая на время выполнения ПЗ. Наиболее важными параметрами КС являются латентность и скорость передачи данных по сети [1]. Основные временные затраты при решении ПЗ происходят за счет межпроцессорных обменов (МпО). Так как параметры КС для конкретной КлС величины фиксированные (т.е. не зависящие от пользователя) сокращения времени передач можно добиться только путем сокращения количества МпО. Поэтому в предлагаемом методе сокращения времени решения ПЗ основной упор делается на сокращение времени передач между вычислителями, за счет разделения задачи на максимально несвязные части.

Существует ряд задач, в которых алгоритм расчета предопределен, и перераспараллелить его практически невозможно, так как последовательность действий жестко задана самим алгоритмом задачи. В качестве примера такой задачи рассматривается расчет надежности моделированием по интервалам времени [2]. Добиться эффективного использования КлС в таких задачах достаточно сложно, и все известные наработки и методы распараллеливания здесь не применимы.

Предлагаемый в данном случае метод сокращения количества МпО заключается в способе распределения узлов задачи по вычислителям КлС. Рассматриваемый метод основывается на том факте, что для расчета нескольких узлов, имеющих связь по данным и назначенных на одни и тот же вычислитель, нет необходимости в МпО, так как все необходимые для расчета данные и результаты располагаются в локальной памяти вычислителя. Можно показать, что при решении одной и той же ПЗ на одной и той же КлС количество МпО в процессе решения будет разным при разных способах распределения узлов ПЗ по вычислителям КлС. Так же можно показать, что существует такое распределение узлов ПЗ, при котором количество МпО будет минимальным и меньшим, чем при любом другом способе распределения. Это позволит сократить общее время выполнения ПЗ.

Для поиска такого распределения была составлена математическая модель задачи оптимизации (ММЗ (1)), описывающая МпО в процессе выполнения ПЗ, в которой функция оптимизации (минимизации) является функцией количества МпО в зависимости от способа распределения.

(1),

где N – общее количество узлов задачи,

M – общее количество доступных вычислительных узлов системы,

x_ij – двоичная переменная,

1 – если j-й узел назначен на i-й процессор,

0 – в противном случае,

a_j – количество связей (передач) j-го узла,

Q_i – количество связей i-го процессора, время передачи которых можно обнулить,

y_i – относительная производительность i-го процессора,

Решение данной задачи даст такое распределение, при котором можно достичь минимума МпО. В настоящее время ведется анализ различных способов решения поставленной задачи с целью определения наиболее подходящего по критерию сложности расчета. В качестве возможного метода решения был рассмотрен метод динамического программирования, который дает точный результат за приемлемое для пользователя число шагов (по сравнению с методом полного перебора). Разрабатываемый метод сокращения количества МпО может быть использован при разработке и других параллельных программ как самостоятельно, так и в совокупности с другими методами распараллеливания.

В результате планируется разработать методику создания эффективных параллельных программ для кластерных систем, в основе которой будет лежать предложенный метод распределения узлов ПЗ по вычислителям КлС, и которая будет описывать весь процесс создания эффективной параллельной программы начиная со стадии разработки алгоритма.

ЛИТЕРАТУРА

1. Воеводин В.В., Воеводин Вл.В., Параллельные вычисления: Учебное пособие для вузов по направлению 510200 – Прикладная математика и информатика/ – СПб.: БХВ-Петербург, 2004. – 608 с.

2. Ладыгин И.И., Яньков С.Г., Решение задачи анализа надежности на параллельной вычислительной системе, Труды международной конференции «Информационные средства и технологии», 2004.