Стронгин Р.Г. Высокопроизводительные паралленльные вычисления на кластерных системах. 2003

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

Система CMDE (Channel Memory based Dynamic Environment) [1]

позволяет решать проблему восстановления выполнения параллельного приложения после сбоя его узла на основе использования Памяти Каналов (ПК), разделяющей процесс посылки и приёма сообщения между узлами и хранящей сообщения в промежутке между посылкой и приёмом, а также на основе сохранения всех сообщений, переданных через канал начиная с момента последней контрольной точки процесса-получателя сообщений. Основными достоинствами системы является возможность асинхронного создания контрольных точек параллельными процессами на каждом узле и независимое восстановление параллельных процессов после сбоя. Реализация этих возможностей потребовала введения в систему дополнительных компонент – Сервера Памяти Каналов (СПК) и Сервера Контрольных Точек (СКТ). Далее в работе представлены архитектура и принципы функционирования системы CMDE, а также некоторые результаты оценки её производительности.

Архитектура системы

Система CMDE является динамическим программным окружением, состоящим из множества взаимосвязанных компонент, каждый из которых запускается на отдельном узле кластерной системы или сети. Динамизм системы определяется обеспечением динамического включения компонентов в систему или исключения из неё.

Система CMDE состоит из двух подсистем: подсистемы низкоуровневых коммуникаций для библиотеки MPICH [2] и подсистемы запуска и сопровождения параллельных MPI-программ на кластерах и сетях. Первая подсистема состоит из одного компонента – коммуникационной библиотеки низкого уровня, реализующей всё множество высокоуровневых коммуникационных функций библиотеки MPICH. Вторая подсистема состоит из компонентов четырёх типов – Диспетчера, Сервера Памяти Каналов (СПК), Сервера

161

Диспетчер является центральным компонентом системы. Он обеспечивает добавление других компонентов в систему и отслеживает их отключение, формирует и поддерживает очередь приложений, назначает ресурсы приложению и перераспределяет ресурсы в случае сбоев.

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

Исполнитель является главным рабочим компонентом системы, обеспечивающим получение подзадачи параллельного приложения от Диспетчера, запуск подзадачи с начала или с последней контрольной

162

точки, инициирование генерации подзадачей контрольных точек на основе специального протокола [3] и отправка их на Сервер Контрольных Точек, а также контроль и анализ завершения подзадачи.

Сервер Контрольных Точек предназначен для получения, хранения и выдачи по запросу последних контрольных точек подпроцессов приложения. Контрольные точки различаются по уникальному идентификатору, определяемому в соответствии с номером приложения в системе и номером (ранком) подзадачи в приложении.

Коммуникационная библиотека низкого уровня обеспечивает подключение процесса подзадачи к Серверам Памяти Каналов для передачи сообщений на основе протокола TCP/IP, передачу служебных и пользовательских сообщений и генерацию контрольных точек на основе функций библиотеки Condor Stand-Alone Checkpointing Library (CSCL)[4] системы Condor[5]. Генерация контрольной точки осуществляется параллельно с помощью специально создаваемого процесса.

Функционирование системы

Функционирование системы CMDE можно условно разделить на две составляющие: формирование системы и обслуживание процесса запуска, выполнения, восстановления после сбоев и завершения параллельного приложения.

Формирование системы начинается с запуска Диспетчера на отдельном узле системы, при этом узел должен позволять входящие соединения с других узлов на специально выделенные порты. Диспетчер создаёт на диске базу приложений, регистрируемых в системе и ожидает соединений от других компонентов системы. Все остальные компоненты могут быть подключены в произвольном порядке, используя IP-адрес Диспетчера. Каждый новый компонент регистрируется Диспетчером и помещается во множество доступных ресурсов. Отключение компонентов от системы при отсутствии запущенных приложений приводит к исключению ресурсов из этого множества. Введение новых компонентов в систему возможно и во время выполнения параллельных приложений. Новые СКТ и Исполнители регистрируются как свободные ресурсы и могут быть использованы другим приложением, ожидающим достаточного количества ресурсов. Включение в систему нового СПК приводит либо к его включению в уже выполняющееся приложение, если

163

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

Запуск приложения в систему требует подготовительного этапа, на котором исходный код(ы) приложения без модификации компилируется с использованием модифицированной библиотеки MPICH и библиотеки Condor. Конфигурация приложения, включающая в себя имя исполняемого файла, командную строку и имена всех входных файлов, описывается простым текстовым файлом, являющимся входным для специального Клиента, обеспечивающего необходимый интерфейс с Диспетчером для введения приложения в систему. На втором этапе с помощью Клиента все необходимые файлы и параметры пересылаются Диспетчеру, который ставит приложение в очередь или запускает его при наличии свободных ресурсов. В текущей реализации системы CMDE, СПК и СКТ являются ресурсами, разделяемыми между приложениями и наличие в системе двух СПК, одного СКТ и одного Исполнителя позволяет запустить приложение на выполнение. Исполнители являются выделенными ресурсами: исполнитель не может использоваться двумя подзадачами одновременно.

Обеспечение отказоустойчивости приложений

Использование системы CMDE на кластерах и сетях имеет целью обеспечение выполнения параллельных MPI-приложений на кластерах и сетях при наличии сбоев их компонентов. Сбой компонента (узла) кластера или сети считается фатальным, т.е. включение компонента в систему после сбоя осуществляется так же, как и его первое подключение. Реализация отказоустойчивости параллельного приложения в системе CMDE основывается на использовании Памяти Каналов, позволяющей хранить сообщения, переданные процессу параллельного приложения с момента последней контрольной точки до момента сбоя и восстанавливать эти сообщения при перезапуске процесса на другом узле. Контрольные точки процессов формируются с использованием библиотеки системы Condor. Использование в CMDE дополнительных компонентов требует обеспечения их отказоустойчивости или введения дополнительных требований на надёжность узлов кластеров или сетей. В настоящее время в системе существуют ограничения, связанные с надёжностью, только для двух её компонент: Диспетчера и Сервера Контрольных Точек. Серверы

164

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

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

165

Рис. 2. Пропускная способность Серверов Памяти Каналов (верхняя кривая) по сравнению со стандартным MPICH

Производительность коммуникаций через Память Канала

Использование Памяти Канала в целях обеспечения отказоустойчивости параллельного приложения вводит дополнительные накладные расходы на время передачи сообщения от одной подзадачи к другой. Коммуникации «Подзадача 1 – Подзадача 2» распадаются на две составляющих: «Подзадача 1 – СПК» и «СПК – Подзадача 2». При синхронно взаимодействующих подзадачах время пересылки сообщения может удвоиться. Для уменьшения этих накладных расходов в СПК реализован транзитный конвейер, позволяющий отправлять сообщение одновременно с его получением. Результаты RTT(round-trip time) тестов пропускной способности Серверов Памяти Каналов в сравнении со стандартной реализацией MPICH (ch_p4) представлены на Рис.2. В этих экспериментах использовались два СПК, по одному на каждую подзадачу приложения. Такая конфигурация (одна подзадача на один СПК) является оптимальной с точки зрения пропускной способности СПК. При большем количестве подзадач, обслуживаемом одним СПК, его пропускная способность уменьшается. Результаты тестов приведены

166

для системы, не включающей протоколы обеспечения отказоустойчивости СПК.

Заключение

В работе представлена система CMDE, позволяющая запускать параллельные MPI-программы на кластерах или сетях, узлы которых не являются надёжными и могут быть выключены во время выполнения программы. Система поддерживает очередь приложений с помощью централизованного диспетчера и имеет Серверы Памяти Каналов и Серверы Контрольных точек для обеспечения восстановления выполнения работы параллельной программы после сбоя одного или нескольких её узлов. Все коммуникации между подзадачами приложений в системе осуществляются через Серверы Памяти Каналов, что позволяет сохранять и восстанавливать сообщения, принятые подзадачей в промежутке между последней контрольной точкой и сбоем, а также буферизировать и не передавать сообщения, отправляемые второй раз. Контрольные точки процессов подзадач создаются с использованием библиотеки системы Condor и сохраняются на специальном Сервере Контрольных Точек. В отличие от системы MPICH-V[6], в CMDE реализована отказоустойчивость Серверов Памяти Каналов, которая обеспечивается специальным алгоритмом дублирования сообщений. Система CMDE может быть использована для объединения вычислительных ресурсов различных кластеров и узлов сети с целью выполнения время- и ресурсоёмких MPI-программ.

Литература

1.Selikhov, A., Germain, C.: CMDE: a Channel Memory based Dynamic Environment for Fault-Tolerant Message Passing based on MPICH-V architecture. Proc. of 7-th Int. Conf. PaCT-2003, Russia, (2003) (to appear).

2.Selikhov, A., Bosilca, G., Germain, C., Fedak, G., Cappello, F.: MPICH-CM: A communication library design for a P2P MPI implementation. Proc. 9th European PVM/MPI User's Group Meeting, Linz, Austria, September/October 2002, LNCS, Vol.~2474. Springer-Verlag, Berlin Heidelberg (2002) 323–330.

3.Herault T., Lemarinier P.: A rollback-recovery protocol on peer to peer systems. In Proc. of MOVEP'2002 Summer School (2002) 313–319.

167

4.Condor Manuals, Chapter 4.2.1. http://www.cs.wisc.edu/condor/manual/

5.Raman R., Livny M.: High throughput resource management. Chapter 13 in The Grid: Blueprint for aNew Computing Infrastructure, Morgan Kaufmann, San Francisco, California (1999).

6.Bosilca G., Bouteiller A., Cappello F., Djilali S., Fedak G., Germain C., Herault T., Lemarinier P., Lodygensky O., Magniette F., Neri V., Selikhov A.: MPICH-V: Toward a scalable fault tolerant MPI for volatile nodes. In Proc. IEEE/ACM SC2002 Conf., Baltimore, Maryland (2002).

МОДЕЛИРОВАНИЕ ДИНАМИКИ ПРОТОПЛАНЕТНОГО ДИСКА НА МНОГОПРОЦЕССОРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ

А.В.Снытников

ИВМиМГ СО РАН, г. Новосибирск

Аннотация

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

Введение

Эволюция самогравитирующих систем таких, как галактики или протопланетные диски имеет большой интерес для астрофизики Образование структуры диска представляет собой задачу многих тел в самосогласованном гравитационном поле. Хорошим приближением для моделирования самогравитирующего диска является кинетическое уравнение Власова-Лиувилля. Вместе с уравнением Пуассона для самосогласованного гравитационного поля они образуют систему уравнений звездной динамики [1]:

Здесь диск галактики считается плоским и бесстолкновительным, и используется приближение дальнодействующего поля. Оценка ресурсов ЭВМ [2], требуемых для моделирования эволюции

168

протопланетного диска, дает сетку 1000х1000х500 узлов и порядка 100 млн. частиц. Для этого требуется 8 Gb оперативной памяти, таким образом, данная задача должна решаться на суперкомпьютерах.

Описание численного алогоритма

Основную трудность в задаче моделирования эволюции протопланетного диска представляет расчет потенциала самосогласованного гравитационного поля, который определяется из уравнения Пуассона. Для того, чтобы получить быстрый алгоритм решения уравнения Пуассона, необходимо учесть особенности задачи

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

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

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

иусловие сходимости выполняется гораздо быстрее. Таким образом, время счета значительно сокращается за счет того, что, удаленные от диска узлы не участвуют в расчете.

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

169

Общая структура метода решения показана на рисунке. Первый шаг – быстрое преобразование Фурье по угловой кординате, в результате чего получается система линейных алгебраических уравнений на фурье-гармоники потенциала, каждое из которых независимо друг от друга. Далее двумерное уравнение для каждой гармоники решается методом верхней релаксации с прогонкой по радиальной координате. Общая структура метода показана на следующем рисунке. После окончания итерационного процесса выполняется обратное преобразование Фурье для значений потенциала в плоскости диска.

Распараллеливание

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

170