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

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

использование ВС со специфической архитектурой. Они позволяют

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

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

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

в диапазоне от 2-3% до 10%. Благодаря использованию GRID-систем

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

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

заведениях.

Ориентация на идеологию GRID-систем и применение

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

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

разработке программной реализации решения задачи дифракции. К

этим особенностям относятся:

1. Разнородность узлов вычислительной системы, которая

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

производительности.

2. Ограниченная пропускная способность вычислительной сети

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

3. Динамическое изменение количества узлов, задействованных

для выполнения вычислений.

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

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

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

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

организация программы, при которой

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

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

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

производительности каждого из них. Такой подход позволяет также

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

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

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

назначенной порции вычислений. Для

учета второй особенности

необходимо при распараллеливании алгоритма обеспечить

минимальную зависимость подзадач по данным. В противном случае

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

сети, простою рабочих станций (которые будут ожидать освобождения

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

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

использованию вычислительных мощностей и увеличению общего

времени выполнения программы. Третья особенность среды

предполагает, что программа решения задачи дифракции должна

обладать значительной гибкостью. Необходимо, чтобы она могла

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

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

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

таких

узлов. Кроме того, программа должна корректно обрабатывать

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

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

некоторой подзадачи на одной из рабочих станций весь процесс

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

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

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

Для разработки программы решения задачи дифракции,

удовлетворяющей вышеперечисленным требованиям, целесообразно

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

основные положения концепции GRID-систем. К числу таких наборов

программных средств относятся пакеты Globus, X-Com и MathNet.

Отличительной особенностью системы Globus является возможность

решения с ее помощью широкого круга сложных вычислительных

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

приложений. Однако возможности Globus представляются явно

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

система отличается сложностью и громоздкостью, что делает крайне

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

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

малых вычислительных мощностях. Возможность решения с помощью

системы Globus широкого круга задач достигается за счет

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

параллельной

программной реализации каждой из них. Это приводит к повышению

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

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

специфики задачи, для решения которой они предназначены.

В отличие от Globus X-Com обеспечивает решение ограниченного

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

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

применение для проектирования

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

использованием стандартной на сегодня компьютерной техники. Во-

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

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

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

каждой конкретной задачи. Во-вторых, наличие автоматической

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

инструментарий X-Com разработчика, который может

сосредоточиться на поиске и рациональной реализации наиболее

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

конфигурации

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

сама система. В-третьих, ориентация на иерархическую структуру

(вместо децентрализованной, используемой Globus) облегчает

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

системы и объема ресурсов, доступных на каждом из ее узлов. X-Com

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

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

использует только стандартные

протоколы передачи данных и в принципе не требует применения

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

характеристиками.

Система распределенных вычислений (СРВ) MathNet реализует

ключевые принципы, аналогичные X-Com. На текущем этапе своего

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

начального уровня для проведения экспериментов по решению

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

оборудовании.

Развертывание программного комплекса MathNet не требует каких-

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

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

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

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

программирования. Система работает под управлением ОС Windows,

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

Программы для системы MathNet

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

загружаемых библиотечных модулей (DLL), написанных на языке

C/C++ и в обязательном порядке содержащих функции Initialize и

Calculate. В рамках первой из указанных функций должно выполняться

разбиение исходной задачи на небольшие фрагменты, что

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

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

функция отвечает за непосредственную

реализацию вычислений,

которым предшествует этап извлечения данных из входного буфера и

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

промежуточных) в указанный выходной буфер. Семантика Initialize и

Calculate уточняется разработчиком конкретного приложения. Автор

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

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

исходных данных и результатов, поскольку индивидуальные буферы

подзадач абсолютно прозрачны для стандартных модулей СРВ.

Задача дифракции в

общем случае сводится к системе линейных

алгебраических уравнений, которую можно решить, используя

итерационные методы. Обработка СЛАУ предполагает выполнение

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

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

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

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

значений отдельных элементов

результирующего вектора. Учитывая

размерность матрицы коэффициентов (порядка 10

- 10

для реальных

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

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

которой каждому процессу будет передаваться строка (или группа

строк) исходной матрицы и копия вектора-множителя. При этом

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

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

каждого узла

системы окажется все необходимое для автономного

выполнения вычислений. Однако решение СЛАУ оказывается

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

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

интегралов. Это означает, что распараллеливание вычислений на этапе

определения коэффициентов СЛАУ (т.е. построения используемой в

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

снижения временных затрат

на решение задачи дифракции. Более

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

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

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

нецелесообразным. Таким образом, еще одним направлением

распараллеливания вычислений в рамках решения задачи дифракции

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

системы. Поскольку процедуры заполнения матрицы

и решения СЛАУ

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

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

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

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

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

Initialize, входящая в состав первой программы, будет отвечать за

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

Это распределение должно быть осуществлено таким образом, чтобы

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

порядок превосходило

число доступных вычислительных узлов. Такое разбиение позволит

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

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

ее конфигурация не претерпит значительных изменений на

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

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

Для этого можно использовать

файл настроек, содержимое которого

будет анализироваться функцией Initialize (такой же подход вполне

приемлем и для второй программы). Функция Calculate первой

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

интегралов. Сбор значений, полученных в результате вызовов

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

автоматически средствами СРВ MathNet. Вычисленные значения

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

которая

сформирует из них искомую матрицу и сохранит ее на

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

Основной задачей второй программы, как отмечалось выше, будет

решение СЛАУ (представленной в матричной форме) одним из

итерационных методов (например, методом сопряженных градиентов).

Функция Initialize этой программы выполнит разрезание полученной

на предыдущем этапе матрицы по строкам и

поместит образовавшиеся

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

вектора-множителя. Собственно итерационный процесс по методу

сопряженных градиентов будет реализован функцией Calculate.

Ключевой операцией, выполняемой этой функцией, будет умножение

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

нужной форме и их сохранение для последующего анализа и

дальнейшего использования, как

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

функция Initialize. Процесс решения задачи дифракции для тела

заданной формы можно будет считать законченным после успешного

завершения работы второй программы.

Таким образом, разрабатываемая программа позволит отлаживать

параллельный алгоритм решения задачи дифракции электромагнитных

волн с учетом особенностей GRID-систем, что позволит легко

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

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

РАЗРАБОТКА WEB-ОРИЕНТИРОВАННОГО

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

ТРЕХМЕРНЫХ ВЕКТОРНЫХ ЗАДАЧ ДИФРАКЦИИ

ЭЛЕКТРОМАГНИТНЫХ ВОЛН НА ОСНОВЕ

СУБИЕРАРХИЧЕСКИХ ПАРАЛЛЕЛЬНЫХ

АЛГОРИТМОВ

А.В. Антонов, М.Ю. Медведик, И.А. Родионова, Ю.Г. Смирнов

Пензенский государственный университет

Введение

Рассмотрим задачу дифракции электромагнитного поля на

идеально проводящем тонком, плоском ограниченном экране. В общей

постановке задача состоит в нахождении решений уравнений

Максвелла, удовлетворяющих определенным краевым условиям и

условиям излучения на бесконечности. Данная задача принадлежит

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

подход к решению этой задачи – сведение ее к векторному

интегродифференциальному уравнению на экране. В наших

обозначениях это уравнение имеет вид:

(

)

,,:

Ω∈=+= xfuAkuDivAGradLu

ττ

(1)

где

Div

- операция поверхностной дивергенции,

- интегральный

оператор

()

,dsyu

yxik

∫

−

(2)

u – касательное к поверхности экрана

векторное поле (плотность

поверхностного тока). Индекс

. показывает взятие касательных к

компонент соответствующего векторного поля. Центральной

проблемой при исследовании разрешимости представленных выше

уравнений является выбор пространств для решений и для правых

частей таким образом, чтобы обеспечить фредгольмовость (и, если

удастся, однозначную разрешимость) этого уравнения в выбранных

пространствах. Кроме того, пространство решений должно быть

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

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

(метод моментов, метод Галеркина), но без достаточного

математического обоснования. Тем не менее в численных решениях

задач дифракции был накоплен

значительный опыт. Имеется ряд

монографий по решению задач дифракции на экранах различной

формы. Наиболее распространенным стал метод, предложенный в 1982

году в статье [3]. Следует подчеркнуть, что проблема эффективного

численного решения задач дифракции на тонких экранах в настоящее

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

мощных современных ЭВМ.

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

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

«вырезается» другой экран произвольной формы, целиком помещается

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

СЛАУ определяется значение поверхностных токов на новом экране.

Таким образом можно решить серию задач дифракции на экранах

различной формы.

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

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

вычислительной сложностью формирования матрицы СЛАУ.

Наиболее удобно рассчитывать подобные задачи на кластере [4].

Постановка задачи

Пусть

{

}

0 RxR ⊂==⊂Ω

- ограниченная область с кусочно-

гладкой границей

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

класса

∞

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

дифракции стороннего монохроматического электромагнитного поля

, HE

на бесконечно тонком идеально проводящем экране

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

)0(0Im),(,

122

≠≥+=

−

kkikk

σωεμω

, сводится к решению уравнения

(1), где

kEf

Будем предполагать, что все источники падающего поля находятся

вне экрана

так, что

)(|

Ω∈

∞

Обычно падающее поле - это либо плоская волна, либо

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

Определим пространство

как замыкание

)(

∞

в норме

//w

Divuuu

−−

Можно показать, что [1]

{

}

)(

:)(

2/12/1

Ω∈Ω∈=

−−

HDivuHuW

где пространство Соболева

)(

определяем обычным образом.

Через

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

относительно полуторалинейной формы

xvfvf d),(

∫

⋅=

{

}

)(Rot),(:'

2/12/1

MHuMHuuW

−−

∈∈=

где

– замкнутая поверхность, такая, что

∈

Метод Галеркина

Рассмотрим n-мерное пространство

⊂

. Будем проводить

аппроксимации

u элементами

∈

. Методом Галеркина находим

u из системы уравнений [2]

VvvfvLu

∈

∀

= ),(),(

. (3)

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

nnn

VVL →

, где

есть антидуальное пространство к

Основная трудность для уравнений электрического поля (1)

состоит в том, что оператор

не является сильно эллиптическим и

традиционные теоремы о сходимости метода Галеркина неприменимы.

Результаты о сходимости метода Галеркина удается обобщить на

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

числе на уравнение электрического поля (1), так как оператор

является эллиптическим на подпространствах.

Каждый элемент матрицы (3) получается путем вычисления

четырехкратного интеграла

,)()(),()()(),(),(

dsyxyxGkdsydivxdivyxGLl

jijijiij

ϕϕϕϕϕϕ

∫∫

ΩΩ

⋅+⋅−==

имеющего слабую особенность в области интегрирования. Здесь

),(),,(

2121

yyyxxx ==

. В качестве базисных функций

)(x

и тестовых

)( yu

выберем функции RWG.

Аналогично рассматривается трехмерная векторная задача

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

областях: определение рассеянного электромагнитного поля

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

связанными отверстием произвольной формы. Слои образованы тремя

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

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

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

объектов через отверстие. Наиболее естественным и эффективным

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

интегральному уравнению на отверстии с помощью метода функций

Грина. Задача решается методом Галеркина. В связи с большим

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

Интерфейс пользователя

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

по принципу «тонкого клиента» с возможностью

доступа через сеть

Интернет [6]. Для использования его возможностей необходимо иметь

выход в сеть Интернет и Web-браузер с поддержкой JavaScript

(рекомендуется использовать MS Internet Explorer версии не ниже 6

или Mozilla Firefox версии не ниже 1.8). Тестовая версия

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

суперкомпьютерных вычислений (РЦСВ) при Пензенском

государственном университете по адресу http://alpha.pnzgu.ru в разделе

«Научная работа».

Исходными данными для вычислений являются следующие

параметры (см. рис. 1):

 p – выбор поляризации: "1" - E-поляризация, "-1" - H-

поляризация падающей волны;

 e – относительная диэлектрическая проницаемость (e>=1)

(для двумерной задачи параметр не используется);

 x – X-координата вектора падения плоской волны;

 y – Y-координата вектора падения плоской волны;

 z – Z-координата вектора падения плоской волны;

 n – параметр размерности матрицы из расчета 2

;

 матрица, задающая форму фигуры, на которой также задаются

вертикальная и горизонтальная срезки.

Рис. 1. Ввод исходных данных

Числовые характеристики вводятся в соответствующие поля

формы, а матрица рисуется при помощи указателя манипулятора

мышь.

После ввода параметров нужно нажать кнопку «Сохранить», при

этом все исходные данные сохранятся на сервере в файле

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

Рис. 2. Результаты работы

Далее пользователь должен перейти в раздел «Результаты работы»

(см. рис. 2). В нем отображается в виде рисунка заданная ранее фигура