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

Подождите немного. Документ загружается.

231

 осуществляет регистрацию подключившихся

Исполнителей;

 осуществляет планирование и запуск потоков на

свободных исполнителях;

 обнаруживает сбои в работе системы и извещает о

них центральное приложение;

 несколько Исполнителей, исполняющих потоки работающих в

Alchemi приложений:

 загрузка исходных данных и кода потока;

 исполнение кода потока;

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

Инструментарий Alchemi был модифицирован с целью реализации

механизма взаимодействия центрального приложения и

выполняющихся потоков на исполнителях. Данное взаимодействие

предусматривает посылку сообщений потоков путем вызова

обработчика события получения сообщения от потока у центрального

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

машине Исполнителя, исполняющего поток.

Реализация

механизма взаимодействия центрального приложения

с потоками позволила:

 избежать повторных пересылок входных данных и их

предварительную обработку при мелком разбиении задачи;

 сделать приложение независимым от реализованного в

Менеджере планировщика заданий;

 реализовать в приложении механизм динамического

планирования расчетов.

Реализация расчетной схемы

Расчет задачи методом суперэлементов можно рассмотреть в виде

следующих этапов:

Первым этапом метода суперэлементов является:

 решение матричных уравнений для нахождения

матриц

iii

−

, которые затем умножаются справа на

с целью получения компонент матрицы

жесткости узлов граничных подобластей

0 iiii

AAA

−

;

o решение уравнений для нахождения векторов

iii

1−

;

232

Второй этап состоит в подготовке исходных данных для

вычисления значений узлов граничных элементов:

 вычисление матрицы

∑

−

iiii

AAAA

000

 вычисление правой части системы линейных уравнений:

∑

−

iiii

fAAf )(

 расчет значений узлов на границе путем решения полученной

системы уравнений;

Третий этап состоит в получении значений узлов подобластей по

формулам

)(A

uAfu

iiiii

−=

−

Принципы динамического планирования вычислений

При запуске расчетов создаются 2 грид-потока и посылаются

Менеджеру Alchemi, где ставятся в очередь на исполнение. Для того

чтобы задействовать все доступные ресурсы, подключенные к Alchemi

сети, центральное приложение создает новые потоки, которые

попадают в очередь Менеджеру Alchemi.

После запуска грид-поток уведомляет центральное приложение о

своем запуске, и ему центральным приложением назначаются расчеты

в соответствии с принципами, описанными ниже.

При отключении Исполнителя Менеджер Alchemi уведомляет

центральное приложение об этом, которое в свою очередь производит

перераспределение заданий с данного Исполнителя.

Первый этап метода

Задача решения матричного уравнения разбивается на задачи по

количеству подобластей, каждая из которых соответствует обработке

соответствующей области. Необходимо отметить, что обработка

подобластей может выполняться независимо от других подобластей.

Кроме того, каждая из полученных подзадач разбивается на части

в соответствии с разбиением множества граничных узлов подобласти.

Таким образом получается достаточно мелкое разбиение

исходной

задачи на вычисления по 2-4 секунды (Core 2 Duo). Однако для

обработки узлов границы подобласти необходима предварительная

факторизация матрицы подобласти (

), которая занимает некоторое

время. Однако после факторизации мы можем обрабатывать

граничные узлы более быстро.

233

Вначале между запущенными грид-потоками распределяются

подобласти и отсылается по 2 задания на обработку границ узлов

(одно задание всегда держится в запасе на удаленном узле, чтобы

избежать простоев вычислительных ресурсов, связанных в передачей

данных). Если грид-потоку нужно задание, а все подобласти уже

распределены, то выбирается подобласть наименее посчитанная

(«медленный»

узел или тяжелая подзадача) и передается потоку

вместе с незанятыми другими грид-потоками узлами границы

подобласти. Когда поток досчитает подобласть (или область будет

досчитана другим потоком), то ему назначается другая подобласть.

Таким образом, если уже все подобласти и узлы их границ

распределены по потокам, то производится их повторное

распределение. Это полезно

в том случае, если некоторые удаленные

машины очень сильно нагружены другими задачами и не могут с

номинальной скоростью обработать наши задания, но у нас имеются

свободные машины, которые также могут заняться этими

вычислениями.

Первый этап метода завершается, когда все подобласти обсчитаны

(обсчитаны все узлы границ подобластей).

Второй этап метода

Данный этап полностью выполняется на центральной машине.

Исполнители на данном этапе не выполняют никаких вычислений.

Однако на Исполнителях сохраняются полученные данные о

подобластях.

Третий этап метода

Выбор грид-потоков для расчета значений внутренних узлов

подобласти происходит с учетом данных о подобластях, посланных

грид-потоками на первом этапе. Таким образом, планирование

происходит таким образом, чтобы уменьшить объем передаваемых

данных. При этом также возможно дублирование расчетов одной и той

же подобласти сразу на нескольких грид-потоках.

Распределение подобластей между

потоками происходит до тех

пор, пока все подобласти не будут посчитаны.

Литература

1. Ильин В.П., Карпов В.В., Масленников А.М. Численные

методы решения задач строительной механики (справочное

пособие) Минск 1990.

234

http://www.alchemi.net – официальный сайт проекта Alchemi

.NET.

3. http://www.intel.com/software/products/mkl – официальный сайт

библиотеки MKL.

РАЗВИТИЕ СИСТЕМЫ ПАРАЛАБ ДЛЯ ИЗУЧЕНИЯ

И ИССЛЕДОВАНИЯ ПАРАЛЛЕЛЬНЫХ МЕТОДОВ РЕШЕНИЯ

СЛОЖНЫХ ВЫЧИСЛИТЕЛЬНЫХ ЗАДАЧ

Д.Ю. Лабутин, А.А. Лабутина, С.В. Ливерко

Нижегородский государственный университет

Характеристика системы

В работе представлен программный комплекс ПараЛаб для

изучения и исследования параллельных методов решения сложных

вычислительных задач, который отвечает следующим основным

требованиям: позволяет проводить как реальные параллельные

вычисления на многопроцессорной вычислительной системе, так и

имитировать такие эксперименты на одном последовательном

компьютере с визуализацией процесса решения сложной

вычислительной задачи.

При проведении имитационных экспериментов

предоставлена

возможность для пользователя:

определить топологию параллельной вычислительной системы

для проведения экспериментов, задать число процессоров в этой

топологии, установить производительность процессоров, выбрать

характеристики коммуникационной среды и способ коммуникации;

осуществить постановку вычислительной задачи, для которой в

составе системы ПараЛаб имеются реализованные параллельные

алгоритмы решения, выполнить задание параметров задачи;

выбрать параллельный метод

для решения выбранной задачи;

установить параметры визуализации для выбора желаемого темпа

демонстрации, способа отображения пересылаемых между

процессорами данных, степени детальности визуализации

выполняемых параллельных вычислений;

выполнить эксперимент для параллельного решения выбранной

задачи. При этом в системе ПараЛаб предусмотрена возможность

сформировать несколько различных заданий для проведения

экспериментов с отличающимися типами многопроцессорных систем,

235

задач или методов параллельных вычислений, для которых

выполнение эксперимента может происходить одновременно (и

режиме разделения времени). Одновременное выполнение

эксперимента для нескольких заданий позволяет сравнивать динамику

решения задачи различными методами, на разных топологиях, с

разными параметрами исходной задачи. Для организации анализа

полученных данных при проведении длительных вычислений система

обеспечивает возможность проведения

серии экспериментов в

автоматическом режиме с запоминанием результатов в журнале

экспериментов;

накапливать и анализировать результаты выполненных

экспериментов; по ним система позволяет построить графики

зависимостей, характеризующих параллельные вычисления (времени

решения, ускорения, эффективности), от параметров задачи и

вычислительной системы.

Одной из важнейших характеристик системы является

возможность выбора способов проведения экспериментов.

Эксперимент можно выполнить в режиме имитации, т.е. на одном

процессоре без использования каких-либо специальных программных

средств типа библиотек передачи сообщений.

Кроме того, в рамках системы ПараЛаб обеспечивается

возможность проведения вычислительного эксперимента в режиме

удаленного доступа к вычислительному кластеру.

Для реальных экспериментов на многопроцессорных

вычислительных системах зависимости времени и ускорения от

параметров

задачи и вычислительной системы строятся по набору

результатов проведенных экспериментов.

При построении зависимостей для экспериментов в режиме

имитации используются теоретические оценки в соответствии с

имеющимися моделями параллельных вычислений. Используемые

модели отображают реальные процессы, протекающие при решении

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

каждого из проведенных экспериментов имеется возможность

восстановить его

для повторного проведения. Кроме того, обеспечено

ведение журнала экспериментов с записью туда постановки задачи,

параметров вычислительной системы и полученных результатов.

Реализованные таким образом процессы позволяют освоить

теоретические положения и помогают формированию представлений о

236

методах построения параллельных алгоритмов, ориентированных на

решение конкретных прикладных задач.

Расширение множества реализованных задач

Первоначально в системе ПараЛаб были реализованы следующие

основные классы задач: сортировка данных, матричные операции

(задача умножения матрицы на вектор, умножения матриц и решения

систем линейных уравнений) и задачи обработки графов (поиск

минимального охватывающего дерева и кратчайшего пути в графе).

Сейчас этот набор расширен задачей глобальной оптимизации и

задачей решения дифференциальных

уравнений в частных

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

оптимизации реализован параллельный индексный метод. Для

решения дифференциальных уравнений в частных производных (на

примере решения задачи Дирихле для уравнения Пуассона)

предлагается параллельное обобщение метода Гаусса-Зейделя. Для

более наглядной визуализации процессов решения новых задач

потребовалась визуализация трехмерных объектов, которая была

реализована в

системе ПараЛаб с использованием технологии

Microsoft DirectX.

Поддержка дополнительных модулей (плагинов) в системе

ПараЛаб

Текущая версия системы ПараЛаб допускает расширение

функциональности путем добавления модулей для решения новых

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

предусмотрена возможность написания дополнительных библиотек

(плагинов) сторонними разработчиками.

Система ПараЛаб разработана на платформе Microsoft .NET с

использованием языка С# и объектно-ориентированного подхода.

Каждая задача (например, задача умножения матриц) в

системе

ПараЛаб представлена абстрактным классом-наследником класса Task

(MatrixMultTask: Task). Все поддерживаемые методы решения задачи

представляются как классы, наследуемые от задачи (например,

FoxMatrixMultTask: MatrixMultTask - алгоритм Фокса для умножения

матриц).

Чтобы добавить в систему новый тип задач, необходимо добавить

в рабочий каталог системы ПараЛаб файлы динамических библиотек

(.dll), представляющих собой библиотеки классов Microsoft .NET

Framework. В одном из этих

файлов должен содержаться класс,

237

производный от абстрактного класса Task, который описывает новую

задачу. В остальных добавленных файлах должны быть реализованы

классы-наследники этого промежуточного класса, которые будут

соответствовать конкретным методам решения задач этого типа.

Итак, создание описанных выше сборок и помещение их в рабочий

каталог системы - это все, что необходимо для добавления поддержки

в системе

ПараЛаб новой задачи. После запуска система ПараЛаб

произведет сканирование файлов с расширение DLL в своем рабочем

каталоге и, используя механизм рефлексии типов .NET, определит те

из них, которые содержат описания абстрактных классов, наследуемых

от ParaLab.Task — они будут соответствовать добавляемым типам

задач. Неабстрактные же классы, наследуемые от них, соответственно,

определяют конкретные методы решения.

Поддержка многопроцессорных и многоядерных архитектур в

системе ПараЛаб

Последняя версия системы ПараЛаб позволяет эмулировать

параллельные эксперименты не только на системе, состоящей из

«простых» однопроцессорных и одноядерных компьютеров. Каждый

компьютер может содержать несколько процессоров, а каждый

процессор - несколько ядер. Ядро системы не ограничивает

количество ядер и процессоров, но для удобства визуализации были

введены следующие ограничения: число процессоров в рамках

одного

вычислительного узла (сервера) может равняться 1 или 2, а число ядер

в процессоре – 1, 2 или 4.

При этом процесс обмена данными между ядрами разделяется на 3

этапа:

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

том числе между ядрами разных процессоров), а также

отправка ядрами данных во внешнюю сеть (через сетевой

адаптер);

передача данных между отдельными серверами по локальной

сети;

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

сетевого адаптера).

В связи с тем, что архитектура вычислительной системы

существенно усложнилась (по сравнению с более ранними версиями

системы ПараЛаб), использование заранее определенных формул для

238

подсчета времени обмена данными невозможно. С этой целью

используются результаты имитации. Разработчик модуля

визуализации задачи должен указать следующее:

время выполнения базовой вычислительной операции

алгоритма (например, для алгоритмов сортировки - это

операция сравнения); время выполнения операции должно

быть выражено в числе стандартных операций с

вещественными числами;

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

ядром вычислительной системы на каждой итерации

алгоритма;

размер единицы обмена данными, выраженный в байтах;

при формировании списка пар ядер, которые будут

обмениваться данными на текущей итерации, необходимо

указать не только номера ядра-отправителя и ядра-получателя,

но и объем передаваемых в этой паре данных в условных

единицах.

По этой информации можно произвести автоматизированный

расчет времени, потраченного на вычисления и на передачу данных в

соответствии

с предлагаемой универсальной моделью параллельных

вычислений.

Как и ранее, для упрощения модели предполагается, что процессы

передачи данных и выполнения вычислений ядрами разделены во

времени: на время выполнения обменов данными вычисления на всех

ядрах приостанавливаются.

Интеграция модуля анализа трассы выполнения

параллельной программы

В настоящий момент система ПараЛаб предоставляет

пользователю развитые средства анализа параллельных алгоритмов в

режиме имитации. Среди таких средств - визуализация процесса

решения задачи при помощи параллельного метода, в ходе которой

отображаются вычисления, выполняемые процессорами кластера, а

также коммуникационные операции. По результатам проведенных

экспериментов система позволяет построить оценки эффективности

параллельного алгоритма.

Однако на

практике часто встречается ситуация, когда конкретная

реализация того или иного параллельного метода, будучи запущена на

239

реальной многопроцессорной вычислительной системе, не

демонстрирует того ускорения, которое было получено при анализе

модели данного параллельного метода. Возникает задача

профилирования параллельного приложения.

Библиотека передачи сообщений MPI имеет расширение –

библиотеку MPE (Multi-Processing Environment), содержащую

необходимые средства для анализа производительности MPI

программ. Если параллельное приложение скомпилировано и

запущено с библиотекой MPE, то по результатам запуска формируется

файл с

информацией о процессе выполнения приложения на

вычислительной системе. Мы планируем интегрировать в систему

ПараЛаб модуль анализа и визуализации MPE-данных. Это позволит

анализировать процесс выполнения реального вычислительного

эксперимента на реальной многопроцессорной вычислительной

системе с использованием развитых средств системы ПараЛаб.

Визуализация процесса выполнения эксперимента позволит

обнаружить источники недостаточного ускорения параллельных

вычислений, простаивающие процессоры

, блокирующие передачи

сообщений и т.п.

ФОРМИРОВАНИЕ ОБУЧАЮЩЕЙ СРЕДЫ В ОБЛАСТИ

ПРИКЛАДНОГО И ПАРАЛЛЕЛЬНОГО

ПРОГРАММИРОВАНИЯ

Е.С. Логунова, Н.В. Фролова, В.С. Холушкин

СарФТИ, Саров

Параллельные вычисления на сегодняшний день перешли из

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

перспективной и максимально востребованной областью IT.

Технология является динамично развивающейся и соответственно

требует инновационных подходов к образованию.

Подготовка специалистов в сфере параллельных вычислений

началась в СарФТИ ещё в 1990-х годах, благодаря уникальному

кадровому потенциалу математического отделения ВНИИЭФ

востребованности специалистов данного профиля.

Программы подготовки ориентированы на решение задач

математического моделирования сложных физических проблем. В

учебном процессе рассматриваются авторские методики решения

240

задач, классические схемы, гетерогенные вычислительные среды.

Имеющаяся материально-техническая база позволяет проводить

обучение не на эмуляторах, а на действующих неоднородных

вычислительных кластерных системах с использованием

специализированного программного обеспечения.

Обучение ведётся в рамках образовательных программ двух

специальностей: «Информационные системы и технологии»,

«Вычислительные машины, комплексы, системы и сети».

Сверх часов, отведённых на

освоение основной образовательной

программы, студенты имеют возможность дополнительно участвовать

в проектных работах в совместной с компанией «Интел» лаборатории,

а также работать в Центре информационных технологий и

программирования СарФТИ, получая педагогический опыт работы со

студентами младших курсов и мотивированными школьниками.

ПАРАЛЛЕЛЬНАЯ МОДИФИКАЦИЯ АЛГОРИТМА ДВОЙНОГО

ОПИСАНИЯ ДЛЯ МНОГОГРАННОГО КОНУСА

С.С. Лялин

Нижегородский государственный университет

Пусть дана матрица

∈

. Многогранным выпуклым конусом

в пространстве

называют множество решений системы

линейных неравенств

0≥Ax

{

}

0| ≥∈= AxxC

. (1)

Кроме представления (1) конус

может быть записан в

параметрическом виде, а именно для некоторой матрицы

∈

{

}

BxxC

∈=∈= RR

λλ

, (2)

где

– неотрицательные действительные числа. Алгоритм

двойного описания [6], известный также как алгоритм Моцкина-

Бургера, по одному из описаний, (1) или (2), строит другое. При этом

метод всегда находит неприводимую систему векторов в матрице

(неприводимую систему неравенств в матрице

A соответственно).

Везде далее мы будем считать, что рассматривается задача перехода от

(1) к (2).

Со времени публикации [6] появилось множество модификаций

алгоритма (см. например, [2, 5]). На основе модификации [2] и