|
Введение
Коллективные операции являются важным и часто используемым компонентом 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 |
