BC/NW 2009; №2 (15):5

BC/NW 2009; №2 (15):5.1

ПРОТОТИП СИСТЕМЫ ПРОВЕДЕНИЯ МНОГОЭТАПНЫХ ВЫЧИСЛИТЕЛЬНЫХ ЭКСПЕРИМЕНТОВ НА КЛАСТЕРЕ МЭИ (ТУ)

Паринов А.А., Незнанов А.А.

(ГОУВПО «Московский энергетический институт (технический университет»), Россия)

Эффективное проведение многоэтапных вычислительных экспериментов (ВЭ) на больших объемах однотипных данных с использованием распределенных высокопроизводительных вычислительных систем (РВВС) представляет собой сложную организационную и технологическую проблему. В связи с тем, что проведение ВЭ предполагает многочисленные запуски вычислительных модулей на различных элементах данных, очевидным методом повышения эффективности является использование средств распараллеливания вычислений. Наиболее универсальным подходом к распараллеливанию является потоковый (нитевый).

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

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

Цель настоящего исследования состоит в разработке программной системы (далее – Системы), которая позволит упростить:

1) эффективное параллельное выполнение на вычислительных узлах РВВС (далее – Узлах);

2) эффективное параллельное выполнение частей алгоритма на Узлах;

3) настройку системы для использования различных форматов данных благодаря использованию расширяемой внутренней системы типов;

4) доступ к исходным, промежуточным и итоговым данным;

5) повторное использование созданных реализаций алгоритмов благодаря их сохранению в каталоге (хранилище) алгоритмов;

6) использование реализаций алгоритмов, написанных на различных языках программирования, благодаря реализации Системы на платформе Microsoft .NET;

7) масштабирование (изменение числа и характеристик Узлов);

8) расширение функциональности Системы, благодаря модульной структуре архитектуры.

В рамках НИРС был реализован и успешно протестирован на кластере МЭИ (ТУ) прототип данной системы.

При создании архитектуры Системы, были выделены следующие части (рис. 1):

1) клиентская часть (Клиент), развертываемая на клиентской машине;

2) серверная часть Системы (Сервер), развертываемая на управляющем Узле (Узлах, в случае её кластеризации).

$E:\_mpei_bachelor\bachelor documents\main2.emf$

Рис. 1. Общая архитектура Системы

В Клиентской части (рис. 2) выделены три основные подсистемы:

1) интерфейс пользователя;

2) взаимодействия с Сервером;

3) взаимодействия с Клиентской БД.

$E:\_mpei_bachelor\bachelor documents\client.emf$

Рис. 2. Архитектура Клиента Системы

Серверной частью производятся непосредственное проведение ВЭ на РВВС. В Серверной части (рис. 3) выделены четыре подсистемы:

1) подсистема доступа к БД;

2) подсистема запуска ВЭ;

3) подсистема доступа к алгоритмическим (вычислительным) ресурсам;

4) каталог реализаций алгоритмов.

В качестве платформы реализации Системы была выбрана платформа Microsoft .NET [4], что обеспечивает переносимость на различные программно-аппаратные среды, в том числе и на системы под управлением операционных систем семейства Linux, в которых используется проект MONO [5]. Необходимо отметить также, что программирование .NET-приложений упрощается за счет существования мощной интегрированной среды разработки Microsoft Visual Studio (используется версия 2005), в которую может быть интегрирован модуль графического создания объектно-ориентированных граф-схемных программ [6, 7]. В качестве базовой системы управления базами данных (СУБД) была выбрана Microsoft SQL Server 2005.

$E:\_mpei_bachelor\bachelor documents\server.emf$

Рис. 3. Архитектура Сервера Системы

Для параллельного выполнения на узлах РВВС была спроектирована модельная граф-схемная потоковая параллельная программа[2], которая позволяет параллельно запускать на каждом узле РВВС реализации последовательных алгоритмов. Граф-схемная программа состоит из модулей Generator, Calculator и Result.

Mult

Рис. 4. Реализация граф-схемной программы

Данная структура граф-схемы обусловлена необходимостью параллельного проведения однотипных вычислений на больших массивах исходных данных.

Для тестирования работоспособности прототипа Системы при выполнении реального ВЭ была написана программа поиска индекса структурной спектральной сложности обыкновенного графа в базисе цепей длины от 0 до 8 [3]. Индекс структурной спектральной сложности в базисе цепей вычисляется по следующей формуле:

где w_i – число цепей длины i в графе G, PISC(P_i) – индекс сложности цепи длины i. Для того чтобы можно было начать вычисления, необходимо задать не определяемую рекурсивно сложность базовых цепей, в качестве которых выбраны цепи P₀ и P₁ (PISC(P_i) = 1, PISC(P_i) = 3). Сложность цепей большей длины вычисляется рекурсивно по приведенной выше формуле, задача поиска индекса структурной спектральной сложности в базисе цепей длины разбивается на три подзадачи:

1) вычисление массива коэффициентов;

2) вычисление количества цепей длины от 0 до n , где n=8;

3) вычисление индекса структурной спектральной сложности графа.

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

Система была протестирована на персональном компьютере и на кластере МЭИ(ТУ) [8]. Вычисления проводились на базе графов, состоящей из 10 000 графов со средним числом 50 вершин.

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

$E:\_mpei_bachelor\bachelor documents\pc.JPG$

Рис. 5. График зависимости времени выполнения модельного ВЭ
на персональном компьютере

$E:\_mpei_bachelor\bachelor documents\cluster.JPG$

Рис. 6. График зависимости времени выполнения модельного ВЭ
на кластере МЭИ (ТУ)

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

Таким образом, на модельных примерах была показана работоспособность Системы и установлена корректность её работы, подтверждена масштабируемость. Сейчас идёт работа над созданием уровня абстракции баз данных для доступа к исходным данным и хранения результатов независимо от используемых СУБД. Также дорабатывается внутренняя система типов данных, оптимизируется планировщик и повышается общая эффективность.

Литература

1. Спецификация программного интерфейса MPI (http://www.mpi-forum.org/docs/)

2. Котляров Д. В., Кутепов В.П., Осипов М.А. Граф-схемное потоковое параллельное программирование и его реализация на кластерных системах. – М. : Издательство РАН, Теория и системы управления, №1, 2005.

3. Незнанов А.А., Кохов В.А. Алгоритмизация решения переборных задач анализа графов. – М. : Издательский дом МЭИ, 2007.

4. Официальный сайт платформы Microsoft .NET (http://www.microsoft.com/NET/)

5. Проект ”MONO” (http://www.mono-project.com/Main_Page)

6. Маланин В.Н., Панков Н.А. Реализация среды объекто-ориентированной граф-схемного потокового параллельного программирования на основе платформы Microsoft .NET. – М. : Издательский дом МЭИ, 2008.

7. Маланин В.Н. Разработка объектно-ориентированный среды проектирования граф-схемных потоковых параллельных программ, – М. : Издательский дом МЭИ, 2008.

8. Информация о кластере МЭИ (ТУ) (http://www.parallel.ru/russia/russian_clusters.html)