Оценка трудоемкости алгоритмом коллективных операций MPI для кластеров многоуровневой архитектуры - BioinforMatix.ru - портал по биоинформатике, имейджингу и биософту

Оценка трудоемкости алгоритмом коллективных операций MPI для кластеров многоуровневой архитектуры

Печать E-mail
Автор А.В. Гришагин, А.Л. Курылев   
27.04.2009 г.
Введение
 
Коллективные операции  являются важным и часто используемым компонентом MPI, и в настоящее время различные исследовательские коллективы  выполняют разработки,  связанные  с повышением их производительности. Однако  в  большинстве  случаев  при  оценке  стоимости  операций  предполагается,  что  расположение  процессов  на  узлах сети  не  имеет  значение,  а  число  одновременно  взаимодействующих пар  процессов  можно  учесть  в  виде  дополнительного  слагаемого  и  в дальнейшем не учитывать его изменение. Проведенные нами исследование показывают, что в кластерах из машин  с большим числом процессоров  данные  параметры  вносят  существенный  вклад  в  результат оценки  стоимости. Например,  при  изменении  нумерации  процессов  в коммуникаторе время выполнения одного и того же алгоритма операции bcast может отличаться на 30%.
 
Кластер многоуровневой архитектуры
 
В качестве примера кластера с многоуровневой архитектурой рассмотрим кластер, построенный на базе POWER5-систем. Он имеет иерархическую архитектуру и содержит следующие уровни:
 
•  сеть (network, cluster);
•  узел (node);
•  книга (book);
•  сборка (multi-chip module);
•  чип (chip);
•  ядро (core);
•  виртуальный процессор (virtual processor).

Каждому уровню  соответствует  свой  способ взаимодействия процессов,  выполняющихся  в  пределах  одного  объекта  данного  уровня (сетевое взаимодействие, общая память, общий кэш L3 или L2 и т.д.).
 
Соответственно,  время  передачи  сообщения  существенно  зависит  от того,  механизм  какого  уровня  используется  взаимодействующими процессами.
 
В настоящий момент мы ограничиваем рассмотрение двумя уровнями архитектуры:
•  передача данных внутри SMP-узла через общую память;
•  передача данных между SMP-узлами через сеть.

Можно принимать во внимание нижележащие уровни, но в современных операционных системах существует миграция процессов внутри SMP-узла, например, в Linux  с  ядрами  семейства 2.6, реализованы специализированные  алгоритмы,  контролирующие  перемещение  процессов  в  рамках  узла  с  учетом  неоднородной  архитектуры SMP-системы.
 
Измерение стоимости операций точка-точка
 
Для  оценки  стоимости  коллективных  операций  мы  предлагаем предварительно  измерить  стоимость  операций  точка-точка.  В  дальнейших рассуждениях мы рассматриваем однородный кластер (то есть кластер, состоящий из одинаковых узлов, единообразно подключенных   к  сети), и исходим из следующих гипотез:

•  одновременная  передача  и  прием  сообщений  через  одно  подключение  к  сети не изменяют время приема и передачи, так как современные  сетевые  компоненты  функционируют  в  полнодуплексном  режиме;
•  одновременная  передача  и  прием  сообщений  через  общую  память снижают скорость приема и передачи;
•  при  выполнении  операции  доставки  сообщения  время,  вклад операций передачи и приема в общее время выполнения считается равным.
 
При принятии перечисленных гипотез для оценки времени выполнения  элементарных  операций  на  конкретном  кластере  необходимо выполнить следующие эксперименты:

•  определение  зависимости  времени  передачи  сообщения  через сеть  от  размера  сообщения  и  числа  передающих  процессов  на SMP-узле. В ходе  эксперимента производится передача  сообщений различного размера между парами процессов, при этом процессы каждой пары расположены на различных узлах;
•  определение  зависимости  времени  передачи  сообщения  через общую  память  от  размера  сообщения  и  числа  взаимодействующих процессов  на SMP-узле. В  ходе  эксперимента  производится  передача сообщений  различного  размера между  несколькими  процессами,  расположенными на одном узле.

По  результатам  экспериментов  мы  можем  оценить  зависимость стоимости операций точка-точка от следующих параметров:
•  длина сообщения;
•  число  процессов  на SMP-узле,  одновременно  выполняющих прием/передачу через сетевое соединение;
•  число  процессов  на SMP-узле,  одновременно  выполняющих прием/передачу через общую память.
 
Оценка стоимости коллективных операций

 
Расчет  стоимости  алгоритма коллективной операции выполняется для  некоторого  конкретного  случая  размещения  процессов  на  узлах сети. Оценка выполняется следующим образом:

•  определяется число шагов,  требуемых  алгоритму  коллективной операции;
 
•  для каждого шага алгоритма определяется:

−  какие процессы передают и принимают сообщения и размер этих сообщений,
−  какие процессы  совместно используют подключение   к   сети для  приема  или  передачи,  и  какие  процессы  совместно  используют общую память,
−  рассчитывается  время  выполнения  шага  для  каждого  процесса;

•  трудоемкость алгоритма принимается как сумма максимальных
значений, полученных на каждом шаге.

Результаты исследований показывают, что применение предлагаемого  подхода  позволяет  получить  оценки  стоимости  алгоритмов  коллективных  операций,  качественно  повторяющие  экспериментальные данные  и  позволяющие  проводить  сравнение  производительности  алгоритмов.
 
Заключение

 
Проведенные  исследования  показывают  существенную  зависимость  стоимости  алгоритмов  коллективных  операций  от  размещения процессов на узлах сети и различия в стоимости операций точка-точка через разделяемую память и сетевое соединение. Очевидна необходимость разработки специализированных алгоритмов коллективных операций для таких кластеров. Предлагаемый подход  к  оценке стоимости алгоритмов коллективных операций учитывает многоуровневую архитектуру кластера и может быть использован как для реализации динамического  выбора  оптимального  алгоритма  при  вызове  коллективной операции, так и для оценки производительности новых алгоритмов.
Работа  выполнена при поддержке IBM Faculty Awards for Innovation Program
 
« Пред.   След. »