стр. 1
(всего 4)

СОДЕРЖАНИЕ

>>

Государственное образовательное учреждение высшего профессионального образования «Самарский государственный аэрокосмический университет имени академика СП. Королева»
Государственное образовательное учреждение
высшего профессионального образования «Нижегородский государственный университет имени Н.И.Лобачевского»
Самарский научный центр Российской академии наук
Институт систем обработки изображений Российской академии наук







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

Материалы
четвертого Международного научно-практического семинара и Всероссийской молодежной школы

30 сентября - 2 октября 2004 года















Самара 2004
УДК 681.3.012:51

ББК 32.973.26-018.2:22





Высокопроизводительные параллельные вычисления на кла­стерных системах. Материалы четвертого Международного научно-практического семинара и Всероссийской молодежной школы. / Под редакцией член-корреспондента РАН В.А. Сойфера, Самара.

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

Отв. за выпуск к.т.н. М.А. Чичева




















© 2004г, СГАУ, ННГУ, СНЦРАН, ИСОИРАН



30 сентября - 2 октября 2004 года на базе Самарского государст­венного аэрокосмического университета имени академика СП. Короле­ва был проведен четвертый Международный научно-практический се­минар и Всероссийская молодежная школа «Высокопроизводительные параллельные вычисления на кластерных системах» (НРС-2004).
Главная направленность мероприятия - обмен опытом и активиза­ция научно-практической деятельности в области решения задач мате­матической физики, моделирования, обработки и анализа сигналов и других задач, требующих высокопроизводительных вычислительных ресурсов, в частности, обсуждение основных аспектов организации вы­числений на кластерных компьютерных системах.

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

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

ПРОГРАММНЫЙ КОМИТЕТ

Каляев А.В.


Бурцев B.C. Воеводин В.В.


Гергель В.П. Золотарев В.И.
Казанский Н.Л.
Крюков В.А.
КузьмичевВ.С.
Левин В.К.



Нестеренко Л.В.

Сойфер В.А. Стронгин Р.Г. Соловое А.В.
Фурсов В.А.
Четверушкин Б.Н
Шорин В.П.
председатель программного комитета, акаде­мик РАН, директор НИИ многопроцессорных вычислительных систем Таганрогского госу­дарственного радиотехнического университета академик РАН, Институт проблем информати-киРАН
член-корреспондент РАН, д.ф.-м.н, заведую­щий лабораторией, заместитель директора НИВЦ МГУ
д.т.н., профессор кафедры МО ЭВМ ННГУ к.ф.-м.н., директор Петродворцового телеком­муникационного центра СПбГУ д.ф.м.н., профессор, заместитель директора Ин­ститута систем обработки изображений РАН профессор, д.ф.-м.н., зав отделом Института Прикладной Математики РАН д.т.н., профессор, директор Самарского регио­нального информационного центра академик, научный руководитель, заместитель директора ФГУП «НИИ «КВАНТ», председа­тель научного совета «Вычислительные систе­мы массового параллелизма» к.ф.-м.н., директор по стратегии и технологиям Нижегородской лаборатории Intel (INNL) член-корреспондент РАН, ректор СГАУ д.т.н., профессор, ректор ННГУ к.т.н., директор Самарского регионального ре­сурсного центра
д.т.н., профессор, директор Института компью­терных исследований СГАУ член-корреспондент РАН, директор Института Математического Моделирования РАН академик, председатель Президиума Самарско­го научного центра РАН

ОРГАНИЗАЦИОННЫЙ КОМИТЕТ

Сойфер В.А. Фурсов В.А.
Гришагин В.А.
Бочкарев С.К. Казанский ПЛ.

Кравчук В.В.

Попов СБ. Санчугов В.П.

Чичева М.А.


- председатель оргкомитета, член-корреспондент РАН,
ректор СГАУ
заместитель председателя оргкомитета, д.т.н., про­фессор, директор Института компьютерных иссле­дований СГАУ
заместитель председателя оргкомитета, к.ф.-м.н., доцент кафедры МО ЭВМ ННГУ
к.т.н., зам. проректора по научной работе СГАУ
д.ф.м.н., профессор, заместитель директора Инсти­тута систем обработки изображений РАН
к.т.н., начальник отдела телекоммуникаций Самар­ского научного центра РАН
к.т.н., доцент кафедры ТК СГАУ
д.т.н., профессор, зам. председателя Президиума СНЦРАН
ученый секретарь семинара, к.т.н., с.н.с. Института систем обработки изображений РАН

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

О.Н. Абросимова
Нижегородский государственный университет им. Лобачевского,
г. Нижний Новгород
Наблюдаемые события редко могут быть описаны как прямые следствия строго детерминированных причин. На практике широко применяется вероятностное описание явлений. Обоснований тому не­сколько: и наличие неустранимых погрешностей в процессе экспери­ментирования и наблюдений, и невозможность полного описания структурных сложностей изучаемой системы, и неопределенности вследствие конечности объема наблюдений. Часть из указанных про­блем решается в вероятностных байесовых сетях [3].
Байесова сеть - графовая модель причинно-следственных отно­шений между случайными переменными. Байесова сеть [3] состоит из следующих понятий и компонент:
множество случайных переменных и направленных связей между переменными;
каждая переменная может принимать одно из конечного множества взаимоисключающих значений;
переменные вместе со связями образуют ориентированный граф без ориентированных циклов (Directed Acyclic Graph - DAG);
каждой переменной-потомку A с переменными-предками B1, Bn приписывается таблица условных вероятностей P(A|B1,..., Bn).
Для более полного знакомства с вероятностными сетями может быть использована, например, работа [4].
Байесовы сети широко используются в медицинских исследовани­ях (например, диагностика заболеваний лимфатических узлов), в косми­ческих и военных системах управления (система поддержки принятия решений Vista в Центре управления полетами NASA), при создании различного программного обеспечения (управление помощником в Office), при обработке изображений и видео (синтез изображений из ви­деосигнала) и в других областях [3].
Одной из задач для вероятностных сетей является задача вывода. Суть данной задачи состоит в том, чтобы вычислить вероятности инте­ресующих (ненаблюдаемых) значений переменных байесовой сети при условии, что имеется некая информация о значениях некоторых других
(наблюдаемых) переменных. Имея совместное распределение вероятно­стей, мы знаем все о нашей модели. Однако вычисление совместного распределения связано с определенными проблемами, а именно требу­ется большой объем памяти и вычислительных ресурсов в случае реше­ния задачи со многими переменными. Используя предположение о том, что состояния переменных в графических моделях зависят только от со­стояний их соседей и не зависят от других переменных модели (допу­щение, применимое к любым баейсовым сетям), совместное распреде­ление вероятности может быть разделено на более мелкие составляю­щие, связанные с подмножествами переменных графической модели.
Одним из алгоритмов, предназначенных для решения задачи вы­вода, позволяющим декомпозировать исходный граф для облегчения процесса вычислений, является метод, известный в литературе, как Junction Tree Inference Engine [4].
Junction Tree Inference Engine - точный алгоритм вывода на веро­ятностных сетях. Алгоритм осуществляет вывод на дереве клик (Junction Tree), которое строится из исходного графа. Для построения дерева клик требуется выполнить морализацию и триангуляцию исходного графа. Морализация представляет собой процедуру, которая выполняет­ся следующим образом: всех родители каждого узла связываются в пол­ный подграф, после чего ориентацию ребер убирают. На основании триангуляции графа известными алгоритмами (например, метод Maxi­mum Cardinality Search [4]) формируется набор клик, т.е. граф представ­ляется в виде связанного набора максимальных полных подграфов [4].
Время, требуемое при работе алгоритма вывода Junction Tree Inference Engine, складывается из времени обработки каждой клики де­рева. Время, требуемое на обработку каждой клики, зависит от числа узлов, входящих в нее. Таким образом, время выполнения алгоритма напрямую зависит от построенного набора клик, а, следовательно, от выполненной триангуляции.
Для реализации параллельного алгоритма Junction Tree Inference Engine данная зависимость еще более актуальна. В случае распараллели­вания по кликам дерева более желательна ситуация наличия множества мелких клик, чем несколько крупных. Если имеется одна или две боль­ших клики, то часто возникает ситуация ожидания процессоров друг дру­гом вследствие того, что процессор, получивший для обработки боль­шую клику, занимает большее время для ее обработки в то время, как ос­тальные процессоры простаивают в ожидании [1].
Доказано [6], что поиск триангуляции, порождающей клики ми­нимального размера - TVP-полная задача.
Алгоритм One Step Look Ahead Triangulation (триангуляция с про­смотром на шаг вперед) описан в [4]. Это итерационный оптимизирую­щий алгоритм. В кратком виде он может быть представлен следующем образом.
На каждой итерации оптимизируется некоторый критерий, задан­ный на подмножестве вершин графа.
Алгоритм One Step Look Ahead Triangulation.
Пусть все вершины незанумерованы. Установить счетчик i:=n,
Пока есть незанумерованные вершины, повторять:
выбрать любую незанумерованную вершину v, оптимизирующую критерий c(v);
пометить ее номером i;
сформировать Ci - множество, содержащее всех незанумерованных соседей помеченной вершины v;
добавить ребра в граф так, чтобы Ci было полным подграфом;
исключить помеченную вершину v и уменьшить i на 1.
Качество алгоритма с точки зрения вычислительной сложности в приложениях, связанных с вероятностными сетями, будет зависеть от критерия c(v), который используется при выборе вершин.
В качестве критерия c(v) могут быть использованы [4]:
- число ребер, которое нужно добавить, чтобы Ci был полным подграфом;
- число еще не занумерованных соседей вершины v.
Первый критерий подходит для моделей с любыми типами пере­менных. Второй критерий - только для моделей с дискретными случай­ными переменными. Используя различные критерии, можно получать различные триангуляции для одного графа.
Для оценки эффективности распараллеливания алгоритма Junction Tree Inference Engine был введен показатель, называемый коэффициен­том максимально возможного ускорения. Он рассчитывается, как от­ношение веса всего дерева к весу клики, содержащей наибольшее число узлов. Вес клики - величина, определяющая трудоемкость выполнения операция для узлов, входящих в клику. Вес всего дерева - сумма весов всех клик, его составляющих.
Коэффициент максимально возможного ускорения определяет теоретическое ускорение, которое может быть достигнуто при распа­раллеливании по кликам. Этот показатель можно применять и при оценке эффективности триангуляции. Чем выше коэффициент ускоре­ния, тем лучше сбалансировано дерево клик и лучше триангуляция.
Кроме коэффициента максимально возможного ускорения для оценки качества триангуляции будем использовать следующие показа­тели: количество ребер, добавляемых при триангуляции, и число узлов в клике максимального размера.
Ниже представлены алгоритмы, которые предлагаются для реше­ния обозначенной проблемы.
Алгоритм 1. Выделение дерева-остова
В описываемом подходе для морализованного графа строится дере­во-остов. Для каждого ребра, не вошедшего в дерево-остов, необходимо построить цикл, который образуется при добавлении его к остову. По­строенные циклы могут иметь сложную структуру, т.е. один цикл может являться частью другого или целиком входить в какой-то цикл. Исполь­зуя некоторые допущения, построенные циклы можно сократить и ис­ключить уже триангулированные участки.
После исключения общих участков все циклы можно поделить на классы. В зависимости от того, какому классу принадлежит цикл, вы­полняется или не выполняется его триангуляция.
В результате такой схемы будет триангулирована только часть циклов, и, следовательно, исходный граф полностью триангулирован не будет. Для получения триангулированного графа после обработки цик­лов необходимо запустить алгоритм One Step Look Ahead Triangulation, который добавит недостающие ребра.
Алгоритм 2. Формирование кластеров
Предыдущий алгоритм может быть немного модифицирован. По­сле того, как выделены и обработаны все циклы, необходимо их собрать в один подграф и триангулировать его алгоритмом One Step Look Ahead Triangulation.
Алгоритм 3. Просмотр на несколько шагов вперед
Из рис. 1 видно, что существует некоторый пик среди значений критерия и возникает вопрос, нельзя ли этот пик обойти. Для решения
В основе описываемого алгоритма лежит алгоритм One Step Look Ahead Triangulation. Алгоритм One Step Look Ahead Triangulation на каж­дом шаге выбирает узел с минимальным значением критерия и, таким об­разом, анализирует ситуацию только на один шаг вперед. Если просмот­реть значения критериев для выбираемых вершин на всех шагах, то можно заметить, что они ведут себя, как правило, как показано на рис. 1.
этой задачи предлагается алгоритм One Step Look Ahead Triangulation развить на несколько шагов вперед, т.е. на каждом шаге выбирать узлы так, чтобы избежать образования пика. Рассмотрим случай просмотра на 2 шага вперед.
Для всех узлов i = 1,n морализованного графа выполнять шаги:
посчитать для узла i значение критерия c(i);
посчитать для всех узлов j = 1,n, j& значения критерия c(j), с учетом того, что выбрана вершина i на шаге 1.
Узел i теперь выбирается как узел с минимальным суммарным критерием c(i) + c(j) после прохода по всем узлам i = 1,n.
Схема может быть расширена на произвольное число шагов.
Описанная выше схема представляет собой перебор всех возмож­ных вариантов и по этой причине требует больших временных затрат. Для графов с числом узлов уже более 50 просмотр на 4, 5 шагов вперед требует значительного времени.
Для сокращения времени работы предлагается следующая идея. Так как алгоритм выбирает узел, исходя из минимального значения кри­терия, то уже на первом шаге узлы с большим значением критерия рас­сматривать нет смысла. Таким образом, предлагается на первом шаге вычислить значение критерия для всех узлов, выбрать узлы с мини­мальным значением критерия и узлы, значение критерия для которых отличается от минимального на некоторую заданную величину А.
Идею, описанную выше, можно развить далее. Не только на пер­вом шаге, но и на всех последующих выбирать не все узлы, а узлы с ми­нимальным значением критерия c(j) и те, значение критерия для кото­рых отличается от минимального на заданную величину А.
Алгоритм 4. Разрушение максимальной клики
Данный подход связан с тем, чтобы, зная максимальную клику в триангулированном графе, попытаться ее уменьшить. Для получения максимальной клики можно использовать алгоритм One Step Look Ahead Triangulation. Под максимальной кликой понимается клика, со­держащая наибольшее число узлов.
После того, как максимальная клика найдена, нужно выполнить триангуляцию с узлов, которые входят в эту клику. Порядок обработки узлов, входящих в максимальную клику, играет существенную роль, т.к. неправильно выбранный порядок может привести к добавлению лиш­них ребер. Чтобы избегать подобных ситуаций, предлагается выбрать только один узел из максимальной клики, причем такой, который в мо-рализованом графе имеет наименьшее число соседей (или минимальную степень), а затем запускать алгоритм One Step Look Ahead Triangulation для всех узлов графа, начиная с этого узла.

Результаты экспериментов:


Коэффициент распараллеливания

4 |


1 —
0 j i 1 i 1 i 1 i 1 i 1 i 1
1 2 3 4 5 6

Рис. 2. Сравнениерезулътатовработы экспериментов
?
? ? ? ? ?
Алгоритм, связанный с формированием кластеров, дает худший результат. Использование этого алгоритма приводит к существенному добавлению лишних ребер, существенному снижению коэффициента распараллеливания и увеличению максимальной клики.
17
16,5
16
15,5
OSLA, критерий 1
OSLA, критерий 2
Выделение дерева-остова
Формирование кластеров
Просмотр на неск. шагов
Разрушение клики

Рис. 3. Сравнениерезулътатов работы экспериментов
Для алгоритма выделения остова можно заметить, что этот алго­ритм добавляет большее количество ребер по сравнению с алгоритмом One Step Look Ahead.
Для алгоритма One Step Look Ahead лучше использовать в качест­ве критерия число ребер, которое нужно добавить, чтобы подграф C был полным подграфом. В этом случае добавляется меньше ребер в граф, значение коэффициента распараллеливания больше и максималь­ная клика в среднем меньше.
Для алгоритма прохода на несколько шагов вперед наилучших ре­зультатов удалось добиться при использовании так называемой моди­фицированной схемы при проходе на 3 шага вперед. В этом алгоритме удалось добиться наилучших результатов по двум наиболее существен­ным показателям - число узлов в максимальной клике и значение коэф­фициента распараллеливания.
Алгоритм разрушения максимальной клики - наиболее эффектив­ный алгоритм из всех описанных выше. Он проигрывает алгоритму One Step Look Ahead по числу добавляемых ребер, но с большим отрывом лидирует по двум другим показателям.
Работа выполнялась в рамках проекта «Масштабируемые алгоритмы вывода и обучения графических моделей в рамках библиотеки PNL».
Литература
Абросимова О.Н., Белов С.А., Сысоев А.В. Балансировка вычислительной нагрузки для параллельных алгоритмов на вероятностных сетях. Высокопроиз­водительные параллельные вычисления на кластерных системах. Материалы третьего Международного научно-практического семинара // Под ред. проф. Р. Г. Стронгина. Н. Новгород: Изд-во Нижегородского госуниверситета, 2003.
Лекции по теории графов под ред. В.А. Емеличева. М: Наука, 1990.
Научная сессия МИФИ-2003. V Всероссийская научно-техническая конференция «Нейроинформатика-2003»: Лекции по нейроинформатике. Часть 1. М.: МИФИ, 2003. - 188 с.
Cowell R., Dawid A., Lauritzen L., Spiegelhalter D. Probabilistic networks and expert systems, Springer-Verlag, NewYork. 1999. - 321 c.
Huang C., Darwiche A. Inference in Belief Networks: A Procedural Guide.
Yannakakis M. Computing the minimum fill-in is NP-complete // SIAM Journal on Algebraic and Discrete Methods. 1981.

ОБОБЩЕННЫЙ КОНВЕЙЕРНЫЙ ПАРАЛЛЕЛИЗМ И РАСПРЕДЕЛЕНИЕ ОПЕРАЦИЙ И ДАННЫХ МЕЖДУ ПРОЦЕССОРАМИ
Е.В. Адуцкевич
Институт математики НАНБеларуси, г. Минск, Беларусь
Введение
Для отображения алгоритмов, заданных последовательными про­граммами, на параллельные компьютеры с распределенной памятью тре­буется распределить операции и данные алгоритма между процессорами, а также установить порядок выполнения операций и обмена данными.
Среди важнейших задач различают, в частности, следующие зада­чи: временное отображение [1], согласование распределения операций и данных по процессорам [1-3], пространственно-временное отображение [4]. Существенным этапом в решении перечисленных задач является поиск функций (таймирующие функции, функции размещения, разверт­ки графов), удовлетворяющих некоторым ограничениям.
Одной из эффективных схем распараллеливания является исполь­зование нескольких таймирующих функций для получения конвейерно­го параллелизма [1, 4]. Такая схема имеет ряд достоинств: возможность получения высокой степени параллелизма без явного указания парал­лельных циклов, регулярный код, упрощенная синхронизация. Приме­нение этой схемы с использованием части таймирующих функций в ка­честве функций размещения позволяет решить проблему пространст­венного и временного отображения. В то же время, при таком подходе требует еще отдельного рассмотрения проблема согласования распреде­ления операций и данных по процессорам.
В этой работе предлагается единая процедура для получения кон­вейерного параллелизма и решения перечисленных задач. Согласован­ное решение этих задач позволяет получать таймирующие функции и функции размещения операций и данных, наилучшим образом подхо­дящие друг другу.
1. Основные определения
Будем рассматривать аффинные гнезда циклов, т.е. будем предпо­лагать, что выражения индексов элементов массивов и границы измене­ния параметров циклов являются аффинными функциями от параметров циклов и внешних переменных.
Пусть в гнезде циклов имеется K операторов Sp и используется L массивов al Область изменения параметров гнезда циклов для оператора Sp будем называть индексной областью и обозначать Vp. Область изме­нения индексов 1-го массива будем обозначать Wl Обозначим np - число циклов, окружающих оператор Sp , vl - размерность l-ro массива, тогда Vp с Znp, W с ZVl.
Индексы элементов l -го массива, встречающегося в операторе Sp и относящегося к q -му входу элементов этого массива в оператор, бу­дем выражать аффинной функцией Fi,p,q(J) = FpqJ + G,pqN + f(l,p,q), где J g Vp, N g Ze - вектор внешних переменных алгоритма, матрицы F,pq g Zvl np, Gipq g ZVl e и векторы f(l,p,q) g ZVl не зависят от внешних пе­ременных.
Реализацию (выполнение) оператора Sp при конкретных значени­ях p и вектора параметров цикла J будем называть операцией и обо­значать S p (J).
Операция Sp (J) , J g Vp, зависитот операции Sa (I) , I g Va, если:
Sa (I) выполняетсяраныпе Sp (J);
Sa (I) и Sp (J) используют один и тот же элемент какого-либо
массива и, по крайней мере, одно из использований есть переопределе­ние (изменение) элемента;
3) между операциями Sa (I) и Sp (J) этот элемент не переопределя-
ется. Зависимость операции Sp (J) от операции Sa (I) будем обозначать
S„ (I) ® Sp (J).
Обозначим P = {(<x,p)| 31 gVa, Jg Vp, Sa(I) ®Sp(J)}. Множество P определяет пары зависимых операторов. Для каждой пары (a,p) gP обозначим Va,p = {J g Vp 13 Sa (I) ® Sp (J)}.
Функции Fa,p: Va,p® Va такие, что если Sa (I) ® Sp (J), IgVa, JgVap eVp, то I = фар(J), назовем функциями зависимостей. Бу­дем предполагать, что функции зависимостей являются аффинными: Fa,p(J) = Fa,pJ + Ya,pN-j(a,p), где J g V,,p, (a, p) g P, N g Ze, матрицы Fap g Znanp, Yap g ZnaXe и векторы j(a,p) g Zna не зависят от внешних пе­ременных.
Обозначим n = maxnp. Пусть функции t((p):Vp ®Z, 1 <p<K,
1<p<K P i P
1 < ( < n, ставят в соответствие каждой операции Sp (J) алгоритма целое число t(( p)(J). Пусть функции t(( p) являются таймирующими функциями (t-функциями), т.е.
)(J) > t(a )(Fa,p J + Ya,p N-j(a,p)), J GVa,p, (a , p ) G P. (1)
Условия (1) называются условиями сохранения зависимостей. Бу­дем предполагать, что функции t(( p )(J) являются аффинными:
t(( p) =t(p,( )J + b( p,( )N + ap^, где 1 <p< K, 1 <(< n, J g Vp, t(p,() g Znp, b(p'^),NgZe, ap( gZ. Предполагается, что t(p(), b(p(), ap( независятот N.
Пусть функции d(l): W{ ® Z, 1 < l < L, 1 < ( < n, ставят в соответствие каждому элементу a{ (F) массива a{ целое число d(((l)(F). Будем интер­претировать r -мерное пространство, в которое отображают функции d(l), как r -мерное пространство виртуальных процессоров. Мы будем
рассматривать аффинные функции d(l): d(l)(F) =h)F + z(l,()N+y,( , где 1 < l < L, 1 <(< r, F gW{ , л(l,() g ZVl, z), N g Ze, yt k g Z. Предполагается, что л), z), yl( независятот N.
2. Получение конвейерного параллелизма с помощью таймирующих функций
Пусть найдены n независимых наборов t-функций tK), 1 <( < n. Требование независимости наборов будем формализовать условием
rang T(p) = np, 1 <p< K, (2)
где T(p) - матрица размера n х np, строки которой составлены из векто­ров t(p,().
Будем использовать r наборов функций t((p), 1 <p<K, 1 <( <r<n, для пространственного отображения операций алгоритма в r -мерное пространство виртуальных процессоров, а оставшиеся n - r наборов -для упорядочения (выполнения в лексикографическом порядке) вычис­лений, выполняемых процессорами. Примем за единицу времени время, необходимое для выполнения самой длительной итерации алгоритма и обмена данными.
Утверждение 1. Пусть M - наименьшее целое число, параметри­чески зависящее от внешних переменных и пределов изменения пара­метров гнезда циклов и превосходящее любую из внешних переменных и любой из пределов изменения параметров циклов. В рамках описанной схемы распараллеливания O(Mr) виртуальных процессоров могут реа­лизовать алгоритм за время O(Mn-r).
Таким образом, описанная схема распараллеливания позволяет получить наилучшее по порядку время реализации алгоритма в r -мерном пространстве виртуальных процессоров. При этом обмен дан­ными между любыми двумя процессорами сводится к передаче данных от одного и того же процессора другому процессору. Получаемый спо­соб обработки данных можно рассматривать как обобщение классиче­ской конвейерной обработки.
3. Постановка задачи
Пусть t(K), 1 <( <n, - независимые наборы таймирующих
функций и d(L), 1 <Х <r, - наборы функций размещения массивов
данных между процессорами. Определим ограничения, которым долж­ны удовлетворять функции t(р) и d((').
Условия сохранения зависимостей (1) можно записать в виде:

J eVa,p, (a,p) eP, 1 <(< n. ( )
Условия для распределения данных между процессорами, не тре­бующего обменов данными, можно получить, рассмотрев величины
5(,м (J) = t(р)(J) - df)(F ,р,,( J)) =
= (t(р,() -л)F^q)J + (b(p,x) -h(1 ,x4M -z(1 ,x))N + ар,-л(1 ,x)f(',p,q) -ylk,
1 < <r,
характеризующие для фиксированных /,р, q, J расстояние между про­цессором, в котором выполняется операция, и процессором, в котором хранится необходимый для выполнения операции элемент массива. Эти условия можно записать в виде:
t(Р,() -Л(,,()F,P,q = 0, b(р,()-л(,,(Чм - z(',x) = 0, ар,(-Л )f(l,p,q) - ylA = 0.(4)


4. Lim A.W., Lam M.S. Maximizing parallelism and minimizing synchroniza­tion with affine partitions // Parallel Computing. 1998. Vol. 24. № 3-4. P. 445-475.


АДАПТАЦИЯ ПОСЛЕДОВАТЕЛЬНОЙ МЕТОДИКИ РЕШЕНИЯ НЕЛИНЕЙНЫХ ЗАДАЧ ДИНАМИКИ КОНСТРУКЦИЙ ДЛЯ МНОГОПРОЦЕССОРНЫХ ЭВМ

В.Г. Баженов, А.В. Гордиенко, А.И. Кибец, П.В. Лаптев
НИИмеханики ННГУ, г. Нижний Новгород Введение
Численное решение трехмерных нелинейных задач нестационар­ного деформирования конструкций, как правило, трудоемко и требует применения достаточно мощной вычислительной техники. Одним из наиболее перспективных путей достижения высокой производительно­сти является создание кластеров - многопроцессорных вычислительных систем (МВС), имеющих локальную память, и связанных между собой однородной коммутационной сетью, предназначенных для быстродей­ствующей параллельной обработки. Большое количество современных пакетов прикладных программ для решения задач математической фи­зики основано на алгоритмах последовательных вычислений (метод ко­нечных элементов, конечно-разностный метод, метод граничных эле­ментов и т.д.). Поэтому эффективное применение разработанных ранее программ с использованием таких МВС требует их модернизации с уче­том особенностей параллельных вычислений. Целью настоящей работы является адаптация алгоритмов программного комплекса «Динамика-3» для организации параллельных вычислений на многопроцессорных ЭВМ. Ожидаемый эффект заключается не только в ускорении вычисле­ний, ноив увеличении возможного количества используемых конечных элементов в дискретной модели расчетной области, а также моделиро­вании более сложных конструкций.
Численная методика решения, и ее программная реализация
Программный комплекс «Динамика-3» предназначен для решения трехмерных задач нестационарного деформирования конструкций, вклю­чающих массивные тела и оболочки. Конструкции могут подвергаться си­ловым и кинематическим воздействиям. Отдельные конструктивные эле­менты могут вступать в динамический контакт друг с другом или взаимо­действовать с внешними телами. В рамках пакета реализована следующая численная методика. Определяющая система уравнений сплошной среды формулируется в переменных Лагранжа. Уравнение движения выводятся из вариационного принципа Журдена. Кинематические соотношения формулируются в метрике текущего состояния. Упругопластическое де­формирование материала описывается соотношениями теории течения с кинематическим и изотропным упрочнением. На контактирующих по­верхностях задаются условия непроникания. Гипотезы, принятые в теории тонкостенных элементов конструкций, вводятся на этапе дискретизации определяющей системы уравнений. Благодаря этому можно упростить стыковку разных типов конструктивных элементов и учесть особенности их напряженно-деформированного состояния.
Решение определяющей системы уравнений, при заданных на­чальных и граничных условиях, основано на методе конечных элемен­тов и явной конечно-разностной схеме интегрирования по времени типа «крест». Расчетная область разбивается 8-узловыми элементами, в узлах которых определяются перемещения, скорости и ускорения. С помощью изопараметрического преобразования, искаженный в общем случае КЭ, отображается на куб. Компоненты скорости перемещений узлов ап­проксимируются внутри конечного элемента полилинейными функция­ми формы. Скорости деформаций аппроксимируются линейными функ­циями в виде суммы безмоментных и моментных составляющих. Ос­новные интегралы в элементе находятся с применением формул чис­ленного интегрирования. Для этого в выбранных квадратурных точках вычисляются скорости деформаций и напряжения.
Заменяя интегрирование по области суммированием по элементам, получим дискретный аналог уравнений движения, который интегрируется по явной конечно-разностной схеме типа «крест». В дискретном аналоге уравнений движения матрица масс является диагональной и не возникает необходимости в ее обращении. Благодаря этому возможно разбиение конструкции на отдельные блоки, внутри которых вычисления на каждом временном слое производятся независимо. Сшивка блоков осуществляется путем согласования сил и ускорений между блоками, после которого про­исходит переход на следующий временной шаг. На рис. 1. схематично представлен последовательный алгоритм расчета.
Алгоритм адаптации численной методики для организации параллельных вычислений
Наиболее предпочтительным алгоритмом для распараллеливания упомянутой выше методики решения трехмерных задач динамики упру-гопластических конструкций на имеющейся вычислительной системе кластерного типа, является метод пространственной декомпозиции рас­четной области (domain decomposition method). Согласно ему распарал­леливание производится путем распределения вычислений в разных точках расчетной области в разные процессоры.
Расчет напряженно деформируемого состояния: определение узловых сил от напряжений и внешних воздействий


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

Рис. 1
Поскольку при численном решении трехмерных задач динамики существует необходимость обработки больших объемов информации, один узел выделяется для организации сбора и распределения данных, производимых при сшивке подобластей и моделировании контактного взаимодействия на каждом шаге интегрирования по времени.
В основу алгоритма адаптации были заложены следующие прин­ципы:
длины параллельно выполняемых ветвей (процессов) программы равны между собой;
минимизация простоев из-за ожидания данных и передачи управления;
минимизация числа и объема временных массивов для оптимизации работы с кэш-памятью;
переход от исходной программы, работающей с полными массивами, к программе обрабатывающей только локальную порцию, распреде­ленную на процессор: изменение размеров массивов и соответст­вующее ему преобразование текста программы.
Для реализации такого подхода исследуемая конструкция разделяет­ся согласно числу процессоров на подконструкции, дискретные модели которых будут иметь, примерно, равное количество конечных элементов. В соответствии с этим база данных решения задачи разбивается на ряд фрагментов БД^, которые распределяются по процессорам (1<L<K). Мас­сивы узлов А и конечных элементов В разделяются на фрагменты AL, BL, соответствующие подконструкциям, которые хранятся и обрабатываются в локальных базах данных БД^ процессоров, отведенных под расчет на­пряженно-деформированного состояния. Процессор 0 используется для управления параллельными процессами (стыковки подконструкции). В массивах AL выделяются внутренние и внешние узлы, (внешние узлы мо­гут вступать в контакт с узлами других подконструкции, внутренние -нет). Такое разделение массива данных на области позволяет обеспечить равномерную загрузку всего расчетного кластера.
Решение начально-краевой задачи осуществляется в соответствии с блок-схемой представленной на рис. 2.

Рис. 2
Расшифровка обозначений, принятых в блок-схеме, приведена в таблице 1.
6

Ci
Определение давления в зонах контакта и уз­ловых сил от контактного давления
7


Корректировка скорости перемещений и пе­ремещений узлов с учетом контактного давле­ния и их распределение из буфера контакта (процессор 0) в память процессора L
8

FE Ml
Расчет деформаций, напряжений, узловых сил от напряжений и внешней нагрузки в процес­соре L
9

Gl
Предварительная обработка результатов счета в процессоре L
10

G
Занесение результатов счета в графическую базу данных
Последовательность действий при решении начально-краевой за­дачи имеет следующий вид:
В процессоре 0 формируется или считывается сформированная зара­нее начальная база данных решения задачи БД, которая разделяется пользователем на фрагменты и распределяется по другим процессо­рам;
Выполняется интегрирование уравнений движения узлов по време­ни:

просматриваются все базы данных БД\^ и в рабочий массив С (буфер сшивки), расположенный в процессоре 0, из массивов ^4L заносятся узловые силы внешних узлов подконструкции (процедуры N1L на рис. 2);
для идентичных узлов подконструкции в процессоре 0 вычисляются результирующие узловых сил (процедура N1 на рис. 2);
результирующие узловые силы распределяются по локальным базам данных БД\,, после чего осуществляется интегрирование уравнений движения и корректировка узловых скоростей перемещений и пере­мещений (процедуры N2L на рис. 2}
3. Проверяются условия контактного взаимодействия деформируемых
тел:
просматриваются все базы данных БД\^ и в рабочий массив С (буфер контакта) в процессоре 0, из массивов ^4L, BL заносятся информация о внешних узлах и гранях КЭ (координаты и скорости перемещений узлов), попавших в зоны вероятного контакта, определенные на те­кущем временном слое без учета сил от контактного давления (про­цедуры C1l на рис. 2);
в процессоре 0 проверяются условия непроникания, вычисляются уз­ловые силы от контактного давления (процедура С1 на рис. 2);
контактные узловые силы распределяются по массивам AL локаль­ных баз данных БДL, скорости перемещений и координаты узлов корректируются в AL с учетом сил от контактного давления (проце­дуры C2L) .
В конечных элементах подконструкции определяются компоненты тензоров деформаций и напряжений, вычисляются узловые силы от напряжений и внешнего давления (процедуры FEML);
Результаты счета обрабатываются (процедуры GL) и передаются на центральный процессор, где с помощью процедуры G1 заносятся в графические базы данных.
Осуществляется переход на следующий временной слой.
Таким образом, обработка информации в изложенном алгоритме на параллельных процессорах преимущественно ведется автономно. Необходимость в обмене информацией между процессорами возникает дважды: при сшивке подконструкции: на этапе интегрирования уравне­ний движения и при численном моделировании условий контакта на не­согласованных сетках. С целью достижения наибольшей эффективности использования вычислительной техники, объединенной в обычную ло­кальную сеть, для модернизации алгоритмов ППП «Динамика-3» была выбрана библиотека MPI.

РАЗРАБОТКА И РЕАЛИЗАЦИЯ СИСТЕМЫ ФУНКЦИОНАЛЬНОГО ПАРАЛЛЕЛЬНОГО ПРОГРАММИРОВАНИЯ НА ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ

СЕ. Бажанов, В.П. Кутепов, Д.А. Шестаков
Московский Энергетический Институт (ТУ), г. Москва
Введение
В докладе обсуждается реализуемый на кафедре прикладной ма­тематики проект создания системы функционального параллельного программирования для кластерных систем [1].
Главная особенность проекта состоит в том, что в нем комплексно на единой основе решаются взаимосвязанные задачи:
создание системы функционального композиционного парал­лельного программирования, включающей высокоуровневый язык и ин­струментальные средства программирования: подсистемы верификации программ, анализа их структурной и вычислительной сложности, экви­валентных преобразований и контроля типовой правильности [1];
разработка системы управления процессом параллельного вы­полнения функциональных программ на вычислительных системах, в частности на кластерах.

Работа выполнена при поддержке РФФИ, проект 03-01-00588
1. Язык функционального программирования
Большинство существующих языков функционального програм­мирования (Lisp, ML, Hope, Haskell и др.) создано на основе 1-исчисления, базовыми понятиями которого являются 1-связывание пе­ременных в выражении, конкатенация выражений и 1-аппликация. Хотя рекурсия выражается в 1-исчислении (через парадоксальный комбина­тор Карри), тем не менее, по практическим соображениям во всех 1-основанных языках в явном виде используется рекурсия. Простой меха­низм различения связанных и свободных переменных в задании функ­ций, единообразный способ задания функций высших типов - главные достоинства этой ветви функциональных языков.
В тоже время, 1-функции плохо поддаются структуризации и рас­параллеливанию, да и сам подход к заданию функций путем 1-связывания переменных в выражении плохо согласуется с общеприня­той трактовкой функций и обычно используемыми способами их зада­ния (использование последовательной композиции, условных конструк­ций, подстановки и рекурсивных определений).
Созданный в рамках проекта язык функционального параллельно­го программирования является композиционным, в нем используется четыре простых операции композиции функций: последовательная ком­позиция, конкатенация (через эти обе операции выражается оператор подстановки), условие и объединение (графиков) ортогональных функ­ций, а также определение функций через систему функциональных уравнений. Теоретической базой языка являются работы [3]. Было вы­полнено несколько реализаций ранних версий языков функционального программирования, основанных на указанном подходе. Одна из этих версий, реализованная для персональных компьютеров, до сих пор ис­пользуется, в том числе и для учебных целей [5].
В разработанном языке композиционного функционального про­граммирования, сокращенно FPTL (Functional Parallel Typified Program­ming Language), с одной стороны воплощены многие механизмы, кото­рые стали неотъемлемыми в современных языках программирования: модульность, инкапсуляция, типизация и др. С другой стороны, в языке FPTL введен целый ряд механизмов, которые либо обязаны исследова­ниям по теории программирования, в частности, схемотологии про­грамм, либо продиктованы чисто прагматическими соображениями. К наиболее важным из них следует отнести:
- схемный характер задания функций [4], упрощающий анализ функциональных программ и динамическое выявление параллелизма при их выполнении;
возможность использования (импортирования) в программе функций, описанных на традиционных языках программирования (C, C++, Pascal и др.), что делает реализованную систему функционального программирования полиязычной [6];
статический контроль типовой правильности, который обеспе­чен сознательным ограничением возможностей отношений между ти­пами с тем, чтобы типизация не была превращена в новую проблему при программировании и контроле правильности задания типов;
теоретически обоснованная асинхронная модель параллельного вычисления значений функций [3], снимающая вопрос о ее корректно­сти и существенно упрощающая ее реализацию.
2. Инструментальная среда программирования
Арсенал средств, представляемых современными ОС и средами программирования, помогающих программисту разрабатывать про­грамму, весьма широк. Однако многие принципиального характера ме­ханизмы, существенные с позиций разработки качественной программы и обоснования ее правильности, практически никак не представлены в реализации всех известных императивных, функциональных, объектно-ориентированных и логических языков. Это касается анализа структуры программы, оценивания сложности, ее эквивалентных целенаправлен­ных преобразований, верификации и др. [7].
В инструментальной среде программирования на FPTL сделана, пожалуй, первая попытка создания комплексной системы программных средств, выполняющих названные функции [8]. Отметим наиболее важ­ные моменты в реализации этих функций.
Разработанная модель и алгоритмы анализа структурной сложности функциональных программ [9] позволяют определять характеристики программы, касающиеся их «устройства» с позиций использования цик­лических и рекурсивных определений. Именно по этим характеристикам наиболее объективно можно судить о логической сложности организации программы, ими, в основном, определяются и сложность самого анализа программы и проверки ее правильности, эти характеристики также ис­пользуются при построении алгоритмов планирования выполнения функциональных программ на вычислительных системах.
Система верификации функциональных программ [8] интересна тем, что в ней, в отличие от традиционных подходов к доказательству правильности программы, (выполняемых путем введения специфици­рующих входо-выходных логических утверждений, обычно соотноси­мых с выделяемыми участками программы), программа сначала транс­лируется в логическую форму (формулу логики первого порядка или хорновскую формулу этой логики). Имея такое представление своей программы, программист может использовать весь арсенал стандартных логических средств для доказательства правильности программы, ее эк­вивалентности другой программе и т.п.
Подсистемы типового контроля, управления процессом разработ­ки функциональных программ, использования функций, представляе­мых на других языках программирования, и др., разработанных для ин­струментальной среды, более детально описаны в [1, 8].
3. Управление параллельным выполнением функциональных программ на вычислительных системах
Организационная структура и состав программных средств систе­мы управления параллельным выполнением функциональных программ подробно описаны в статье [1]. Реализация системы управления осуще­ствляется для кластерных ВС, которые структурно представляют собой множество узлов (локальных сетей) из однородных компьютеров, объе­диняемых посредством использования серверов, выполняющих роль локальных управлений узлами ВС. При объединении серверных узлов соответственно их управление образует иерархическую структуру, от­ражающую декомпозицию множества узлов на подмножества и правила делегирования функций межузлового управления вышестоящим серве­рам.
Основные функции управления серверов каждого уровня:
сбор данных о загруженности подчиненных им компьютеров (для серверов самого низшего уровня) или узлов (для серверов высших уровней), вычисление по ним усредненной загруженности и ее де­виации, а также прогнозирование загруженности;
реакция на отказы и восстановления системы и обеспечение высокой отказоустойчивости;
администрирование подчиненных компонентов;
динамическое управление конфигурацией (масштабированием, из­менением структуры коммуникаций идр.).
Каждый компьютер ВС сам выполняет функции о контроле своей загруженности путем измерения (стандартными, как правило, средствами ОС) таких параметров, как объем свободной памяти, интенсивность обме­на страницами между дисковой и оперативной памятью, интенсивность межкомпьютерного обмена, количество выполняемых процессов и др.
Общий поход к реализации данного управления параллельными процессами на ВС такой организации подробно рассмотрен в [7]. Его основная задача - обеспечение равномерной загрузки компьютеров ВС и минимизация времени выполнения функциональной программы. Для решения этой задачи в реализации управления используется ряд эври­стических правил, позволяющих компьютеры (и узлы) ВС дифференци­ровать по степени их загруженности, количественно отраженной в шка­ле: недогружен, нормально загружен и перегружен. Компьютер ВС пе­регружен по памяти, если у него нет свободной оперативной памяти и высока интенсивность обменов между оперативной памятью и дисками. Компьютер перегружен по интерфейсу, если у него большая интенсив­ность обменов с другими компьютерами (трафик по сети обмена срав­ним с ее пропускной способностью).
Стратегия равномерной загрузки предполагает перемещение части процессов перегруженных компьютеров на недогруженные. Естествен­но, что центральной проблемой при регулировании загрузки является выбор процессов-кандидатов для перемещения на другой компьютер. Эту роль выполняет планировщик, размещенный на каждом компьюте­ре, во взаимодействии с интерпретатором [1, 8], также устанавливаемом на каждом компьютере.
В качестве кандидатов на перемещение рассматриваются только процессы, связанные с вычислением значений рекурсивно определяемых функций, т.е. функциональных переменных, а также импортируемых функций из других языков, если программист отмечает их как достаточ­но сложные по вычислению [9].
Эвристические соображения, стоящие за этим, обоснованы в [7]. Запрет на перемещение между компьютерами базисных и нерекурсивно определяемых функциональных переменных (как правило, несложных с вычислительной точки зрения) позволяет исключить деградацию рабо­ты ВС из-за частых обменов между ее компьютерами.
Более детально стратегии выбора процесса-кандидата на переме­щение рассматриваются в докладе [9].
Заключение
В настоящее время завершена реализация языка, основной частью которого является интерпретатор, реализующий процесс параллельного выполнения функциональной программы. Выполненные эксперименты по сравнению его эффективности (времени, затрачиваемому на выполнение программы) вполне удовлетворительны [8]. Несмотря на то, что интерпре­татор значительно усложнен из-за того, что в нем реализованы сложные механизмы динамического выявления в программе параллельных процес­сов, по эффективности он не уступает, а часто и превосходит «последова­тельные» интерпретаторы известных языков Lisp, Haskell, ML и др. [8].
В стадии завершения (идут отладочные работы) находятся про­граммные средства для управления параллельным выполнением функ­циональных программ на кластерах. Получены первые позитивные ре­зультаты этой работы на практике [9]. Завершение проекта должно по­казать, что сложные рекурсивные функциональные программы можно успешно выполнять параллельно, без участия программиста в какой-либо предварительной работе по так настоятельно навязываемому ему распараллеливанию программы.
Литература
Бажанов С.Е., Кутепов В.П., Шестаков Д.А. Язык функционального па­раллельного программирования и его реализация на кластерных системах // Теория и системы управления (в печати).
Кутепов В.П., Фальк В.Н. Функциональные системы: теоретический и практический аспекты // Кибернетика, 1979. №1.
Кутепов В.П., Фальк В.Н. Модели асинхронных вычислений значений функций в языке функциональных схем // Программирование, 1978. №3.
Кутепов В.П. Исчисление функциональных схем и параллельные алго­ритмы // Программирование, 1976, №6.
Ерызунов В.Б. Разработка и реализация системы функционального про­граммирования // Автореф. дис. на соиск. учен. степени канд. техн. наук. М.: МЭИ, 1990.
Борздова Т.В. и др. Полиязычная система параллельного программирования, основанная на одном семействе функциональных языков // Программирова­ние, 1984. №2.
Кутепов В.П. Об интеллектуальных компьютерах и больших компьютер­ных системах нового поколения // Изв. РАН. Теория и системы управле­ния, 1996. №5.
Бажанов С.Е., Кутепов В.П. Функциональное параллельное программи­рование: язык, его реализация и инструментальная среда разработки про­грамм // Доклад на четвертом Международном научно-практическом се­минаре «Высокопроизводительные параллельные вычисления на кластер­ных системах».
Кутепов В.П., Шестаков Д.А. Анализ структурной сложности функцио­нальных программ и его применение для планирования их выполнения на вычислительных системах // Доклад на четвертом Международном научно-практическом семинаре «Высокопроизводительные параллельные вычис­ления на кластерных системах».


МОДЕЛИРОВАНИЕ СВЕРХИЗЛУЧЕНИЯ СИСТЕМЫ ЗАРЯЖЕННЫХ ОСЦИЛЛЯТОРОВ

В.В. Березовский
Поморский Еосударственный Университет им. М.В. Ломоносова,
г. Архангельск
Рассмотрен классический аналог сверхизлучения Дикке [2] в клас­сической системе нелинейных заряженных осцилляторов, взаимодейст­вующих через собственное поле излучения. В начальный момент ос-


ных классических осцилляторов с учетом их взаимодействия. Рассмот­рим систему (1). В общем случае мы можем представить ее в следую­щем виде:
Lf = Af,
где линейный дискретный оператор L соответствует разностному выра­жению:
г к г к-1
Lfk = f - f , At
а нелинейный оператор A

b^a rab 2 b
Для параллельной реализации ядра алгоритма оказывается доста­точным «расщепить» индексные массивы, используемые для генерации дискретных операторов, и применить процедуру межпроцессорных об­менов при реализации простейших блоков умножения операторов на элементы вектора. Пусть требуется вычислить произведение AxB, где A = a.. ,B = llbj . Умножение матрицы на вектор можно выполнить на n
J пхп II \\п
процессорах, организованных в ii-структуру. Каждый z-тый процессор (z=0,..N-1) в начале выполнения программы содержит z-тый элемент век­тора B и z-тый столбец матрицы операторов A. Умножение производится за п тактов, каждый такт включает в себя накопление и сдвиг. Накопле­ние включает в себя применение оператора из ячейки матрицы A, отме­ченной шаблоном, к имеющемуся на данный такт у процессора элементу вектора B и прибавление результата к значению, хранящемуся в накопи­теле. Сдвиг состоит из цикличного сдвига шаблона вверх и передаче те­кущего элемента вектора B соседнему процессору. В случае произволь­ного количества процессоров меньшего N, столбцы матрицы A и элемен­ты вектора B распределяются по процессорам, схема же вычислений ос­тается той же.
Схематично вычисления происходят, как показано на рис. 1: где
, ,2 1 3n.. (п b) - b
aubt =-/8 (b, - 1)bz xAt, avb, = (--b ob +ib J' J\' ' + b,) xAt.
2 rj.
Для упрощения, предполагается, что F направлена только вдоль
2 2
оси x, то скалярное произведение nab(nabFb)=Fbcos (Znabx) и cos (Znabx) не изменяется с течением времени. В начале работы высчитываются cos2(Znabx) и гъаЬ для каждой ячейки матрицы A, для чего каждому про­цессору передаются координаты всех точек.








л

После чего начинается основной ход программы. Шаг вычислений состоит из применения текущего оператора к текущему элементу векто­ра. Например, для 0-го процессора вначале применяется оператор а00 к элементу Ь0, результат сохраняется в накопителе, Ь0 передается процес­сору 1 и шаблон циклично смещается вверх к ячейке an0. На следую­щем такте к полученному от соседа слева элементу bn применяется оператор an0, результат прибавляется к значению в накопителе и сохра­няется, затем сдвиг шаблона вверх и передача bn соседу справа. И так N тактов. Когда цикл завершится, значение из накопителя умножается на At и складывается с полученным слева b0. В конце все bi пересылаются 0-му процессору, который сохраняет их на диске.
Структура обменов является однородной. В дополнение к этому корневой процесс выполняет незначительный объем вычислений, обу­словленный необходимостью сборки значений шагов по времени от ос­тальных процессов. Основные этапы вычислений на одном временном шаге представлены на рис. 2. В соответствие с ним мы имеем следую­щую схему на каждом шаге:
- вычисление значений шагов по времени для каждого процесса;
- сборка значений шагов по времени на корневом процессе;
- сохранение результатов.
Настоящая работа содержит результаты, полученные при числен­ном решении системы (1) для системы осцилляторов, находящихся в те­ле произвольной формы со случайным образом заданной начальной фа­зой фв.

Инициализация

?
?
?



у MPI_Bcast у
Передача ко­ординат точек



! MPI_Send! -*тМР1 Recvr1-
¦6
Накопление и сдвиг. N раз



^MPI_Gathery
Сбор резуль-
Шаг вычис­лений



6
Сохранение результатов

Рис. 2. Схема вычислений
Возбужденные в начальный момент времени полностью несфази-рованные ангармонические осцилляторы, взаимодействующие через собственное поле излучения, находятся в неустойчивом состоянии. По­ляризация системы инициирует развитие этой неустойчивости и приво­дит к росту интенсивности излучения [3]. В рамках этой работы удалось сделать расчет для числа осцилляторов до 104. Благодаря применению технологии параллельных вычислений, существует принципиальная возможность произвести численный расчет для числа осцилляторов по­рядка 106, что близко к количественным оценкам числа участвующих в сверхизлучении осцилляторов в последних экспериментах [4].
Литература
МенъшиковЛ.И. УФЫ 169 113 (1999).
Dicke R.H. Phys. Rev. 93 99 (1954).
ИлъшскшЮ. А., МасловаН. С. ЖЭТФ 94 171 (1988).
Зайцев СВ., Гордеев Н.Ю., Graham L.A., Копчатов В.И., Карачинский Л.Я., Новиков И.И., Huffaker D.L., Копъев П.С. Физика и техника полупровод­ников // 1999. 33. 1456.
СИСТЕМА АВТОМАТИЗИРОВАННОГО ТЕСТИРОВАНИЯ ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ ВЫВОДА И ОБУЧЕНИЯ В ВЕРОЯТНОСТНЫХ СЕТЯХ

Р.В. Виноградов
Нижегородский государственный университет им. Лобачевского,
г. Н. Новгород
Введение
В данной работе рассматривается возможность автоматизации процесса тестирования параллельных алгоритмов на классе задач выво­да и обучения в вероятностных графических моделях. Необходимость создания специализированных средств, упрощающих тестирование, вы­звана высокой трудоемкостью этого процесса.
Для демонстрации результатов работы дадим ряд основных поня­тий рассматриваемой темы [1, 3, 8]. Байесовская сеть (Bayesian belief network) - это направленный ациклический граф (directed acyclic graph -DAG), обладающий следующими свойствами:
каждая вершина представляет собой событие, описываемое слу­чайной величиной, которая может иметь несколько состояний;
все вершины, связанные с родительскими вершинами, опреде­ляются таблицами условных вероятностей или функцией условных ве­роятностей;
для вершин, не имеющих родителей, вероятности ее состояний являются безусловными (маргинальными).
В байесовских сетях могут сочетаться эмпирические частоты по­явления различных значений переменных, субъективные оценки «ожи­даний» и теоретические представления о математических вероятностях тех или иных следствий из априорной информации. Клика в графе - это полный подграф, не содержащийся ни в каком другом полном подграфе исходного графа. Под семьей вершины в орграфе понимается список, включающий родительские вершины и саму вершину.
Существующая реализация алгоритмов в вероятностных сетях
Существует большое количество программных продуктов, реали­зующих идею использования графических вероятностных моделей. Од­нако многие из них обладают рядом недостатков [6]:
Недоступность исходного кода. Подобные продукты исключают собственную интеграцию в другие приложения;




ректности выполненных тестов и документировать результаты экспери­ментов в табличные формы, содержащие числовые показатели эффек­тивности работы параллельных методов.
Генерация случайной байесовской сети
Одна из задач, возникающих на этапе тестирования параллельных алгоритмов, реализованных на базе библиотеки PNL, связана с подбо­ром тестовых случаев (вероятностных моделей), объективно отражаю­щих реальность. Подход очевиден - случайная генерация. Этот способ формирования моделей подразумевает наличие некоторого набора па­раметров, ограничивающих топологию модели и размеры таблиц веро­ятностей, заданных на вершинах сети. В данной работе рассматривалось случайное формирование как ориентированных, так и неориентирован­ных графических вероятностных моделей. Более подробно остановимся на генерации байесовских сетей.
Произвольная байесовская сеть (рис. 2) необходима для изучения поведения показателя эффективности и масштабируемости разрабаты­ваемых параллельных алгоритмов.

Рис. 2. Пример байесовской сети, имеющей случайную топологию
При формировании произвольного графа, лежащего в основе байе­совской сети, основным параметром, явно ограничивающим число связей у каждой вершины и косвенно ограничивающим размер таблиц распре­деления вероятности, служит максимальный размер семьи вершин в сети.
При создании графа учитывается еще один параметр, определяющий число вершин, не зависящих от других вершин (размер семьи таких вер­шин равен 1, а распределение вероятности является маргинальным). С це­лью ограничить размер таблиц условных вероятностей рассматривается параметр, определяющий максимально возможное число состояний дис­кретных случайных величин, соответствующих вершинам модели.
Важно отметить, что реализация определенных алгоритмов в рамках библиотеки PNL подразумевает ее дальнейшее применение для решения практических задач. Имеющиеся ограничения на случайность структуры графа и размеры вещественных матриц, присутствуют и в реальных моде­лях, отражающих проблематику конкретной практической задачи.
Топология графа, лежащая в основе сети toyQMR (рис. 3), совпада­ет с топологией двудольного графа. В сети такого рода каждая вершина нижнего уровня образует некоторое количество связей с вершинами верхнего уровня, однако вершины одного уровня не могут находиться в зависимости между собой.

Рис. 3. Пример байесовской сети с топологией toyQMR
Ориентированные модели с подобной топологией часто встреча­ются в медицинской диагностике. В этом случае вершины верхнего слоя отражают сущности медицинских тестов и симптомов, а вершины ниж­него слоя, подчиненные вершинам верхнего слоя, соответствуют диаг­нозам пациентов. Общее описание подобного рода байесовских сетей, а также уникальные свойства и поведение таких моделей применительно к алгоритмам вывода можно найти в статье [2].
Байесовская сеть с топологией пирамиды (рис. 4) имеет структуру, графическая интерпретация которой выглядит следующим образом:

Рис. 4. Пример байесовской сети с топологией PYRAMID
все вершины графа можно собрать в некоторое количество упорядо­ченных сверху вниз слоев так, чтобы выполнялись пункты 2 и 3;
можно «подвинуть» слои так, чтобы полученный граф представлял собой пирамиду, симметричную относительно некоторой вертикальной оси;
каждая вершина i-ro уровня может находиться в отношении «ребе­нок-родитель» только с соседними вершинами (i-1)-ro уровня.
Байесовские сети, имеющие такую топологию, частично исполь­зуются в диагностических целях (в том числе в медицине). Важно также отметить, что в силу симметричности модели и небольшого размера се­мьи вершин модели PYRAMID представляют определенный интерес:
подобная топология важна для изучения свойств масштабируемости параллельных алгоритмов вывода, основанных на распределении вершин сети по процессорам. Примером может служить итерацион­ный метод Loopy Belief Propagation [2];
алгоритм вывода Junction Tree Inference [1], реализующий идею выде­ления в сети дерева клик (при удачной триангуляции графа исходной сети размер клик будет ограничен) также представляет интерес для исследования вопросов трудоемкости и скорости работы метода на задачах небольшого размера. Алгоритм может работать на сетях не­большого размера, поскольку является точным и весьма трудоемким.
Информацию о подобной топологии байесовских сетей можно най­ти в статье [2].
При формировании сети с топологией полного графа, случайный механизм используется только для задания маргинальных распределе­ний вероятностей на независимых вершинах и условных распределений, при этом топология сети определяется однозначно.
Структура полного графа попадает в одну из вырожденных ситуа­ций, наличие которых необходимо в ходе тестирования на предмет от­казоустойчивости и универсальности разрабатываемых методов. На­пример, алгоритм вывода Junction Tree Inference [1] на сети, имеющей топологию полного графа, создаст вырожденное дерево клик с одним корнем, в результате чего, исчезнет необходимость в распространении вероятностей между кликами.
В данной работе для создания набора тестовых случаев (под тес­товым случаем понимается вероятностная модель с определенной топо­логией) использовалось два формата представления моделей:
DSL (Decision Systems Laboratory) - формат хранения моделей, пре­доставленный лабораторией систем принятия решений [7];
формат представления объектов библиотеки PNL, основанный на XML 1.0.
Автоматизированное тестирование
Автоматизация процесса тестирования заключается во внедрении средств (рис. 1), позволяющих упростить подготовку исходных наборов данных в отдельности для каждого из алгоритмов, ускорить создание необходимых конфигурационных файлов, содержащих параметры за­пуска параллельных MPI- или OpenMP-реализаций, обеспечить хране­ние результатов как атомарных, так и серийных экспериментов, уско­рить сбор и обработку результатов (автоматическое документирование и проверка правильности результатов). Документирование данных по­средством COM-сервера Word позволило сократить время обработки результатов для последующего анализа.
Работа выполнялась в рамках проекта «Масштабируемые алго­ритмы вывода и обучения графических моделей в рамках библиотеки PNL», действующего в Нижегородском университете, по заказу компа­нии Intel.
Литература
Cowell R., DawidA., Lauritzen L., Spiegelhalter D. Probabilistic networks and expert systems // Springer-Verlag, NewYork. 1999. - 321 c.
Kevin P. Murphy, Yair Weiss, Michael I. Jordan Loopy Belief Propagation for Approximate Inference // An Empirical Study. University of California, Berkeley. Seminar 37-551: Belief Propagation Algorithms.
Хабаров СП. Экспертныесистемы.
Терехов С.А. Введение в байесовы сети // Лекция для школы-семинара «Современные проблемы нейроинформатики», Москва, МИФИ, 29­31 января 2003 года.
Библиотека Open Source Probabilistic Networks Library.
Victor Eruhimov, Kevin P. Murphy, Gary Bradski Intel's open-source probabilistic networks library.
Проект GeNIe от Decision Systems Laboratory - University of Pittsburgh.
Dictionary of Algorithms and Data Structures.


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

СВ. Востокин
Самарский государственный аэрокосмический университет, г. Самара
Введение
В последнее время в компьютерной индустрии наметилась тен­денция к интеграции вычислительных ресурсов для решения некоторой общей задачи. Она обусловлена развитием и широким распространени­ем технических средств, таких как высокопроизводительные компьюте­ры и коммуникационные среды высокой пропускной способности. Тех­нологический аспект разработки программного обеспечения для такого рода систем связан с решением комплекса проблем, включающих про­блемы надежности, масштабируемости алгоритмов и программ, мо­бильности программ, разработки технологий повторного использова­ния. Широкое распространение средств связи также дает возможность реализовать программное управление внешними по отношению к вы­числительной системе пространственно распределенными процессами, которые протекают параллельно во времени. Разработка качественного программного обеспечения для распределенных систем не возможна без применения системного подхода, опирающегося на формальную модель пространственно распределенных параллельных процессов. В докладе представляется новый графический язык моделирования, предназначен­ный для использования в качестве основы программных сред и средств автоматизации параллельного программирования.
В первой части доклада излагается спецификация языка модели­рования пространственно распределенных дискретных систем, которая включает: определение семантики языка моделирования; формальное определение синтаксиса языка моделирования с использованием формы Бекуса-Наура; определение графической нотации описания моделей систем.
Во второй части описывается метод хранения сети объектов структурных элементов модели, метод преобразования текстового пред­ставления в сеть объектов, а также набор команд, однократное исполне­ние последовательности которых позволяет восстановить сеть из струк­турных элементов модели в памяти.
В третьей части рассматривается метод построения модели рас­пределенного вычислительного процесса по известному последователь­ному алгоритму. Рассматривается тестовая задача организации вычис­лительного процесса для решения системы линейных уравнений мето­дом Гаусса-Зейделя. Метод основан на параллелизме по данным. Суть его заключается в разделении области обрабатываемых данных на фрагменты, в которых организуется локальная обработка. Используе­мый метод распараллеливания сводит решение задачи к организации корректного взаимодействия нескольких последовательных процессов, работающих с локальными данными. Данный вычислительный процесс может быть наглядно описан на введенном языке моделирования. Рас­сматривается набор диаграмм на языке моделирования, описывающий масштабируемый вычислительный процесс решения тестовой задачи.
В заключении рассматриваются возможные сферы применения языка моделирования. Дополнительную информацию по проекту разра­ботки языка моделирования и инструментальных средств автоматиза­ции параллельного программирования на его основе можно найти по адресу http://graphplus.ssau.ru.
РАСПРЕДЕЛЕНИЕ РЕСУРСОВ МНОГОПРОЦЕССОРНЫХ СИСТЕМ ПРИ ВЫЧИСЛЕНИИ СОГЛАСОВАННЫХ ОЦЕНОК ПО МАЛОМУ ЧИСЛУ НАБЛЮДЕНИЙ

А.В. Гаврилов, В.А. Фурсов
Самарский государственный аэрокосмический университет, г. Самара, Институт систем обработки изображений, г. Самара
Введение
Часто задачу идентификации параметров систем приходится ре­шать по малому числу наблюдений [1], например, при определении из­меняющихся параметров модели управляемого объекта [2].
Основное условие предельных теорем теории вероятностей (суще­ствование большого числа случайных явлений) при этом не выполняет­ся, поэтому основанная на них теория статистического оценивания и рассматриваемые в рамках этой теории методы построения оценок яв­ляются в таком случае недостаточно обоснованными.
В работе [3] было высказано предположение, что оценивание це­лесообразно проводить, используя только наиболее свободные от шума наблюдения. Эта идея получила свое развитие в виде принципа согласо­ванных оценок [1], представляющего собой методологию получения не­статистических оценок параметров c для уравнения вида
y = Xc + x, (1)
где матрица X размера N х M и вектор y размера N х 1 доступны для непосредственного наблюдения, а вектор ошибок ? размера N х 1 неиз­вестен. К виду (1) сводится большое количество задач.
Одной из проблем реализации этого подхода является существен­ное увеличение объема вычислений, необходимых для получения оце­нок, вследствие переборного характера задачи поиска таких наблюде­ний. Для решения задач оценивания больших размерностей неизбеж­ным становится применение параллельных вычислений. В данной рабо­те рассматриваются вопросы построения параллельного алгоритма вы­числения согласованных оценок по малому числу измерений, а также вопросы распределения ресурсов гетерогенных кластеров при выполне­нии этого алгоритма.
1. Последовательный алгоритм
Исходными данными для решения задачи служат матрица X, век­тор y, а также размерность подсистем верхнего уровня P [4].
На первом этапе строятся всевозможные подсистемы верхнего уровня HP (i = 1,cN ), в каждую из которых входит P исходных наблю­дений системы (1).
На втором этапе для каждой из подсистем верхнего уровня стро­ятся всевозможные подсистемы нижнего уровня LPj (j = 1, CPM ) размер­ности M . Для каждой из них находится оценка cPj. Способ нахождения
оценки может различаться в зависимости от требований по точности и ограничений по вычислительной сложности.
На третьем этапе вычисляются значения функции взаимной бли­зости [5] a(hp ) для каждой из подсистем верхнего уровня на основании
оценок, полученных для подсистем нижнего уровня, и выбирается под­система верхнего уровня с минимальным значением этой функции.
В результате происходит полный перебор всех возможных сочета­ний наблюдений исходной системы (1). При этом большое количество подсистем нижнего уровня, входящих в различные подсистемы верхнего уровня, будут совпадать. Очевидно, что всего подсистем нижнего уровня будет cNj . Поэтому работу программы можно построить в виде следую­щих шагов:
получение всевозможных подсистем нижнего уровня и построение для них оценок;
получение всевозможных подсистем верхнего уровня и вычисление значений функции взаимной близости для них;
нахождение минимума среди полученных значений и вычисление искомой оценки параметров.
2. Логика построения параллельного алгоритма
Пусть известны числа N, M, P, а также число процессов K.
Рассмотрим сначала изменения, возникающие в первом этапе. Ло­гично распределить между процессами построение подсистем нижнего уровня и нахождение оценок для них. Дальнейшее разделение по функ­циональности (распараллеливание решения конкретных систем) нецеле­сообразно в виду резкого возрастания количества передаваемых по сети данных и ощутимого преобладания числа подсистем нижнего уровня над возможным числом процессов.
Для получения комбинаций индексов в (1), характеризующих под­системы верхнего и нижнего уровней, предлагается использовать ре­куррентный алгоритм, позволяющий получить следующую комбинацию на основании предыдущей. В основу его работы положена возможность биекции множества возможных комбинаций индексов и множества чи­сел, имеющих заданные двоичную разрядность и норму Хэмминга. В


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

Т\\ ? Tn + 2˜/t к (д^ х c, qk х комбинация)
к=2

(7)

Очевидно, что распараллеливать имеет смысл только первые два этапа работы, как наиболее трудоемкие. При этом выигрыш в скорости вычислений в основном будет достигаться на первом этапе. Рассмотрим более подробно его характеристики.
3. Оценка ускорения
Рассмотрим гомогенный кластер из K компьютеров. Пусть tL -латентность используемой сети, a tb - добавочное время на пересылку
одного байта. Будем считать, что время передачи в сети линейно зави­сит от объема передаваемой информации, и все целочисленные значе­ния двубайтовые, а дробные - восьмибайтовые. Далее приведем оценки времени, необходимого для выполнения различного рода операций:


(8)

(9)

хк (комбинация, qk )= t l + 2 -(M + 1)-tb (10)
w(k, N, M ) = w(N, M )<(2 + 2M )-t=+(4 + 6M )-t++t P (Ц)
k
TjLcc = Y„tk(qk х С,qk х комбинация) < CNJ(tL + 8M-tь + 2M-tь)

Здесь tx, t+, t=, t+ соответственно время выполнения умножения, деления, проверки условия и сложения, a tР - время, необходимое для решения системы выбранным методом. Соответственно,
"N"
То!' + ТЦ, < (K -1) - (2tL + (8N + 2)(M + l)tb + N(N - M)
0. (13)
В случае гомогенного кластера
Tj1 = max W(k,qk,N,M)<(\CN!/K] + 1)-w(N,M)
k=1,^ . (14)
Тогда ускорение [6] с учетом рассылки полученных результатов составит:
Т1
S
т II + т II + т II + т II
10 1предвп˜ *I ^˜1 расе (15)
Т1 = CNI-w(N,M)>CM -tp, (16)
где T1 - время работы последовательного алгоритма. Далее предполо­жим, что cNj ° o(mod K) и все арифметические операции имеют одина­ковую длительность ta, тогда будет справедлива следующая оценка:
K
S > K(K -1)-ф\) + Г1 + K V(6 + 8M)ta +tP) + K(tL + 10Mtb)
CN tP V CN 0 L-P L-P (17)
Таким образом, ускорение может приближаться к K, особенно при N и M существенно больших K.
4. Распределение ресурсов
В рассматриваемом выше алгоритме считались известными числа qk. Собственно, к их определению и сводится задача оптимального рас­пределения ресурсов кластера для изложенного алгоритма.
Пусть кластер состоит из K компьютеров, для каждого из которых эмпирическим путем получена функция W(k, n, N,M). Тогда при фикси­рованных значениях N и M определение qk примет вид задачи цело­численной оптимизации с нелинейной целевой функцией (18).
max W(k, qk, N, M )® min,
k =1, K
<fqk = cNf, k=1
qk e N, k = 1K.
(18)
В такой постановке она может быть решена, например, полным перебором, поскольку решение проводится один раз для дальнейшего многократного использования основного алгоритма.
Таким образом, основной проблемой является построение зависи­мостей W(k, n, N,M) для конкретного кластера, на котором будут произ­водиться вычисления. При этом необходимо ограничить диапазон изме­нения значений N и Mb зависимости от типа задач оценивания, кото­рые будут решаться.
Следует отметить, что вычислительные затраты на определение
W(k, n, N, M) для n = 1, cNf соизмеримы с затратами на решение задачи с
использованием последовательного алгоритма. Поэтому полезно ис­пользовать априорную информацию о вычислительных мощностях кла­стера для выбора верхней границы порядка CNJ / K . Для гетерогенного кластера эта граница может заметно колебаться.
Благодарности
Работа выполнена при поддержке российско-американской про­граммы «Фундаментальные исследования и высшее образование» и РФФИ (грант №03-01-00109)
Литература
Фурсов В.А. Проблемы вычисления оценок по малому числу наблюде­ний // Современные методы математического моделирования (Сб. лекций). Самара, 2001.
Fursov V.A., Gavrilov A.V. Conforming Identification of the Controlled Ob­ject // Computing, Communications and Control Technologies - CCCT 2004: In­ternational Conference Austin, Texas, USA, Proceedings.
КалманР.Е. Идентификация систем с шумами // Успехи математиче­ских наук, 1985. Т. 40. Вып. 4 (244).
4. Фурсов В.А. Построение оценок по нестатистическим критериям //
Труды международной конференции «ТВП-2001». Самара, 2001.
ГавриловА.В. Сравнительный анализ критериев идентификации по ма­лому числу наблюдений в рамках принципа согласованности оценок // Сбор­ник трудов участников II летней школы по дифракционной оптике и обработ­ке изображений. Самара, 2004.
ГоловашкшД.Л., ГоловашкинаС.П. Методы параллельных вычисле­ний (Часть 2) // Самара: СГАУ, 2003.
АЛГОРИТМЫ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ ДЛЯ ЗАДАЧ МОДЕЛИРОВАНИЯ СЛОЖНЫХ СИСТЕМ
Ф.Г. Гаращенко, Г.И. Ниссенбаум
Киевский националъныйуниверситет им. ТарасаШевченко, г. Киев
Введение
Использование алгоритмов параллельных вычислений позволяет эффективно решать задачи управления динамическими объектами и мо­делирования сложных систем. В данной работе рассмотрены аспекты разработки соответствующего программного обеспечения для решения задач управления пучками, анализа практической устойчивости и структурно-параметрической оптимизации. Изложена технология и ал­горитмы решения задач на параллельных вычислительных системах. В работе используется вычислительная система типа MIMD. Как язык программирования используется язык C++ с вызовом коммуникацион­ных примитивов из системной библиотеки. В качестве коммуникацион­ной библиотеки используется интерфейс MPI (Message Passing Interface), какой в последнее время de-facto стал общепризнанным стан­дартом передачи сообщений. При выполнении работы использовались компиляторы Microsoft Visual C++ 6.0, gcc-3.0.2 и разработанный на ка­федре MCC комплекс программ для проведения вычислительных экспе­риментов «Моделирование динамических систем» (MDS).
Постановка задачи
Рассматривается трудоемкая с вычислительной точки зрения зада­ча нахождения оптимальных параметров ускоряюще-фокусирующей системы при отсутствующих кулоновских взаимодействиях. Полную постановку задачи можно найти в [1], [2].
Использование параллельной вычислительной техники для данно­го класса задач проиллюстрируем на примере решения задачи Коши. Пусть имеем систему дифференциальных уравнений с начальными ус­ловиями. Использован стиль «одна программа - много данных» (SPMD): каждый процесс выполняет один и тот же код, но обрабатывает разные части данных, т.е. вычисляется одна система дифференциальных уравнений, но для разных начальных условий. Возникает проблема ба­лансирования нагрузки на каждый из процессорных элементов. Необхо­димо также минимизировать временные затраты на взаимодействие ме­жду процессами.
Решение задачи
Для решения задачи использовался вычислительный кластер Ки­евского национального университета имени Тараса Шевченко. Кластер построен на базе двухпроцессорных узлов с процессорами PentiumIII-933Mhz и 1Ghz. В роли служебной сетки применяется Gigabit Ethernet.
Были проведены вычислительные эксперименты над матрицами больших размеров. Рассматривались алгоритмы распределенного умно­жения матриц с помощью парадигм взаимодействия между процессами «управляющие - рабочие» (распределенный портфель задач) и конвейер.
Важным условием распараллеливания программы является нали­чие независимых вычислений, т.е. вычислений с множествами записи, которые не пересекаются.
Результаты моделирования динамики пучков заряженных частиц в ускоряюще-фокусирующих системах.
При разработке алгоритмов эффективного моделирования были использованы результаты распараллеливания градиентного метода и распределенного умножения матриц.
Будем рассматривать уравнение движения без учета кулоновских сил в системе резонансного ускорения. E=(Ex Ey Ez)T - вектор напряженно­сти ускоряющего поля. Внешнее поле описывается соотношением E=(Ex
Ey Ez)T cos ф , где ф =-2pЈ (t- t*)-j (0) - фаза ускоряющей волны, которая
1
действует на частицу в момент t, ^-время прохождения волны от началь­ной точки z=0 в точку z, ф (0)-фаза ускоряющей волны, при которой ион входит в процесс ускорения, 1 - длина волны ускоряющего поля, Е - век­тор, что определяет амплитуду его напряженности. Если z-независимая координата, то уравнение движения будут иметь вид:
dg h E — = — Ez coSj, dz c

dj = 2p g ; dz 1 2 _ 1'


(4.1)


-ГТ = — ˜2—1 L(-0-5' + g(z))x - Ez -Hcos ф,
dz c у _ 1 Sz dz

d2 2 2 ,{(-0.5-f-_ g(z))x-Ez^d^]cos j,
dz c у _ 1 Sz dz
=h g Г( 0 5 SEz g(z))x E dx-|w^)
(4 2)

где
g (z) = 05fSEx (0,0, z) SEy(0,0, z) л
z e [0, T].
Система (4.1) описывает продольное движение, а система (4.2 ) ра­диальное движение частиц.
Ниже приведена упрощенная модель ускоряюще-фокусирующей системы при отсутствующих кулоновских взаимодействиях [1].
<dg = u(x )cos(cp), dj = 2py
. (4.3)
На функцию управления u(x ) наложим одно из следующих ограни­чений [1]:
u(X ) eWu = {u(X ):0 ? u(X ) ? c,X e [0, Г]}, (4.4)
u(X)= {и(X):| и(X)|Ј c,X e [0,Г]}.
Моделирование было проведено при следующих значениях пара­метров
о=1,15; b=1,17 (для j о); У 0=1,5; с=-0,03, T=3,54.
Анализ полученных рисунков подтверждают устойчивость системы.








\/
у




У>˜-УУу ^






Ж ш





:^\^УУ/





ЧгУ1



Рис. 1. Пучокзаряженных частиц, который состоит из 20 траекторий (координата j)
Использование параллельной вычислительной техники и разра­ботка соответствующих алгоритмов разрешит эффективно моделиро­вать и решать сложные задачи управления пучками, практической стой­кости и структурно-параметрической оптимизации. Важной является также оценка зависимости времени выполнения программы от количе­ства процессов.
Таким образом, главным в работе является: реализация подхода крупноблочного распараллеливания алгоритмов на кластерной архитек­туре, описание численного эксперимента по решению оптимизацион­ных задач и задач численного моделирования на примере задач модели­рования траекторий заряженных частиц, исследование практической стойкости и структурно-параметрической оптимизации.
Литература
БубликБ.Н., Гаращенко Ф.Г., КириченкоН.Ф. Структурно-параметрическая оптимизация и устойчивость динамики пучков // К.: Науч­ная мысль, 1985. - 304 с.
Башняков О.М., Гаращенко Ф.Г., Лежебока В.В. Практическая стой­кость и структурная оптимизация динамических систем // К.: Издательско-полиграфическийцентр «Киевскийуниверситет», 2000. - 197 с.
Воеводин Вл.В. Курс лекций «Параллельная обработка данных» // http://kiev.parallel.ru/.
Gregory R. Andrews. Foundations of Multithreaded, Parallel, and Distrib­uted Programming-University of Arizona: Addison-Wesley, 2000, ISBN: 0-201­35752-6


РАЗРАБОТКА ИНТЕГРИРОВАННОЙ СРЕДЫ ВЫСОКОПРОИЗВОДИТЕЛЬНЫХВЫЧИСЛЕНИЙ ДЛЯ КЛАСТЕРА НИЖЕГОРОДСКОГО УНИВЕРСИТЕТА

В.П. Гергель, А.Н. Свистунов
Нижегородский государственныйуниверситет им. Н.И. Лобачевского,
г. Нижний Новгород
В работе рассматриваются проблемы создания интегрированной среды высокопроизводительных вычислений для кластера Нижегородско­го университета, который был предоставлен ННГУ в рамках академиче­ской программы Интел в 2001 г. [3]. Важной отличительной особенностью кластера является его неоднородность (гетерогенность). В состав кластера входят рабочие места, оснащенные процессорами Intel Pentium 4 и соеди­ненные относительно медленной сетью (100 Мбит), а также вычислитель­ные 2- и 4-процессорные серверы, обмен данными между которыми вы­полняется при помощи быстрых каналов передачи данных (1000 Мбит). Основной операционной системой, установленной на узлах кластера явля­ется ОС Windows (на рабочих станциях установлен Windows 2000 Professional, на серверах установлена Windows 2000 Advanced Server).
Дополнительная информация о структуре кластера ННГУ доступ­на в сети Интернет по адресу http://www.software.unn.ac.ru/cluster.htm.
Эффективное использование быстродействующего компьютерно­го оборудования предполагает решение двух основных проблем, возни­кающих при эксплуатации кластера - проблему предоставления удален­ного доступа к вычислительной среде кластера и проблему эффективно­го управления и мониторинга вычислительных задач, выполняющихся на кластере [1].
На сегодняшний день известно довольно много различных про­граммных систем, позволяющих решать отмеченные проблемы. Боль­шинство подобных систем традиционно разрабатывались для ОС UNIX, однако, в последнее время появились подобные системы и для ОС се­мейства Windows. К числу таких систем относится, например LSF (Load Sharing Facility, http://www.platform.com), или Cluster CoNTroller (http://www.mpi-softtech.com/).
Однако использование готовых систем управления кластером затруд­нено рядом обстоятельств. Прежде всего, это высокая стоимость подобных систем, достигающая, для кластера подобного кластеру Нижегородского университета, десятков тысяч долларов. Вторым, не менее важным обстоя­тельством, является закрытость подобных систем, что осложняет проведе­ние работ по исследованию различных алгоритмов управления кластерных систем. Для кластера Нижегородского университета, в силу его неоднород­ности, планирование распределения вычислительной нагрузки по узлам кластера является практически важной задачей. Как результат, отмеченные факторы приводят к необходимости создания собственных средств под­держки организации высокопроизводительных вычислений на кластере.
В целом, для организации высокопроизводительных кластерных вычислений соответствующая программная среда поддержки должна обеспечивать:
реализацию достаточного набора операций для выполнения вы­числительных заданий на кластере (загрузка задачи, добавление задачи в очередь задач, получение текущего статуса очереди задач и текущей выполняемой задачи, получение результатов вычислений);
наличие простого и удобного способа удаленного доступа к кла­стеру, не требующего установки на рабочих станциях пользователей ка­кого-либо специального программного обеспечения;
создание собственной системы авторизации пользователей, не связанной напрямую с системой авторизации операционной системы;
организацию системы очередей задач;
сохранение задач пользователя после их выполнения и возмож­ность их повторного запуска;
запоминание результатов выполнения вычислительных заданий.
При построении программной системы за основу была взята сло­жившаяся архитектура системы мониторинга и управления [2], вклю­чающая, как правило, следующие составные части:
компонент для взаимодействия с пользователем (Менеджер доступа), позволяющий ставить задачи в очередь, удалять задачи из очереди, просматривать статус задач и т.д., а также ведущий базу данных пользователей и базу данных результатов;
компонент для организации очереди заданий (Диспетчер заданий), обеспечивающий выполнение работ по управлению потоком заданий (накопление, упорядочение, просмотр и выборку);
компонент для управления процессом выполнения заданий на кла­стере (Супервизор кластера), осуществляющий его мониторинг, вы­борку заданий из очереди и распределение вычислительных ресурсов кластера.
В настоящее время разработан и внедрен опытный вариант систе­мы, обладающий следующими возможностями:
обеспечение доступа к системе с любого компьютера, подключенно­го к сети Интернет;
использование в качестве средств доступа Web-браузера, telnet-клиента, различных специализированных программ (что позволяет, в частности, не устанавливать на компьютерах пользователей какого-либо дополнительного программного обеспечения);
организацию очереди заданий (как ждущих своей очереди на выпол­нение, так и уже завершившихся, сформировавших результат) во внешней базе данных, что позволяет обеспечить устойчивость систе­мы в случае сбоя;
замену (при необходимости) планировщика и изменение стратегии распределения вычислительных ресурсов кластера;
ведение статистики использования задачами пользователей вычислительных ресурсов кластера.
В настоящее время система активно используется широким кругом пользователей и сотрудников Центра компьютерного моделирования Нижегородского университета. Возможности, предоставляемые систе­мой, используются при разработке и эксплуатации учебных и исследова­тельских программных комплексов - таких, например, как программная система для изучения и исследования параллельных методов решения сложных вычислительных задач (ПараЛаб) и система параллельной мно­гоэкстремальной оптимизации Абсолют Эксперт.
Литература
1. Rajkumar Buyya. High Performance Cluster Computing // Volume1: Archi-
tectures and Systems. Volume 2: Programming and Applications. Prentice-Hall
Inc., 1999.
Saphir W., Tanner L.A., Traversat B. Job Management Requirements for NAS Parallel Systems and Clusters // NAS Technical Report NAS-95-006 February 95.
Гергелъ В.П., Стронгш Р.Г. Высокопроизводительный вычислительный кластер Нижегородского университета // Материалы конференции Relarn. -Н. Новгород, 2002.

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

В.П. Гергель, Р.Г. Стронгин
Нижегородский государственныйуниверситет им. Н.И. Лобачевского,
г. Нижний Новгород
Исследование многих математических моделей, рождаемых по­требностями приложений, часто включает построение оценок некоторой величины, характеризующей заданную область Q в многомерном евк­лидовом пространстве RN. В качестве типового примера таких задач может рассматриваться, например, задача нелинейного программирова­ния
j* =j(y*) = min{j(y): y e Q }, Q = {y e D : gi(y) Ј 0,1 Ј i Ј m } где область поиска определяется в некотором N -мерном гиперпаралле­лепипеде
D = {y e RN : a} ? y} ? Ъ, ,1 ? j ? N }
системой нелинейных ограничений gt (y) ? 0, 1 ? i ? m. В случае много-экстремальности функции j (y) рассмотренная постановка называется задачей глобальной оптимизации, для которой искомые оценки (y*,j* = j(y*)) являются интегральными характеристиками минимизи­руемой функции j (y) во всей области D.
1. Рассмотренный пример может быть расширен аналогичным описанием задач интегрирования, решения систем нелинейных уравне­ний, восстановления зависимостей и т.п. Как результат такого перечис­ления можно говорить о существовании широкого класса важных прикладных задач, требующих оценки некоторой величины (интегра­ла, глобального минимума, множества не доминируемых решений и т.п.) путем анализа поведения заданной функции F(y) в некотором ги­перпараллелепипеде D (в общем случае, функция F(y) может быть век­торной для учета, например, многокритериальное™ или ограничений задачи оптимизации).
2. Задача построения искомой оценки могла бы быть решена на основе анализа вычисленных в узлах некоторой сетки YT ={y' :1 ? t ? T } области D множества значений:
Zt = F(yt), yt e D, 1 ? t ? T.
Возможный (и широко используемый в практических приложени­ях) способ построения таких сеток состоит в равномерном расположе­нии узлов (равномерность расположения узлов позволяет уменьшить их общее число T и, следовательно, сократить вычислительные затра­ты). Однако проблема состоит в том, что число узлов этой сети экспо­ненциально увеличивается с ростом размерности N области D. Дейст­вительно, для равномерной сетки в области D, имеющей шаг А > 0, справедлива оценка:

j=1
В результате для многих актуальных прикладных задач реализация описанной схемы полного перебора на равномерной сетке оказывается не­возможной в силу ее высокой потребности в вычислительных ресурсах.
Дело усложняется еще и тем, что во многих приложениях выпол­нение операции оценки вектора F(y) для выбранной точки y e D связа­но с вычислительным анализом математических моделей, отличающих­ся высокой степенью сложности. Причем практика последних десятиле­тий показывает, что впечатляющий воображение быстрый рост произ­водительности компьютеров сопровождается столь же быстрым услож­нением рассматриваемых прикладных задач и описывающих их моде­лей. Разумеется, существуют и многие более простые задачи, решение которых вполне осуществимо описанным выше методом перебора узлов равномерной сетки. Основное предложение, направленное на повыше­ние эффективности анализа сложных задач, связано с переходом к це­ленаправленному анализу вариантов, в ходе которого вычисления, осу­ществленные в одних узлах сетки, позволяют исключить необходимость вычислений во многих других узлах, т.е. речь идет об использовании существенно не равномерных сеток. Так, например, применительно к рассмотренной выше задаче глобальной минимизации это означает, что сетка должна быть более плотной в окрестности искомого глобального минимума и - заметно менее плотной вдали от точки минимума. По существу это означает, что такая сетка не может быть задана априори (ибо расположение глобального минимума является не известным). Ее необходимо строить в процессе анализа.


щий информационный массив сое и множество Yq(j), что предполагает обмен информацией между процессорами. Подразумевается, что каж­дый процессор, завершив испытание, посылает сообщение с результа­тами вычислений, всем другим процессорам. Кроме того, выбрав неко­торую точку для очередного испытания, процессор информирует об этом выборе все остальные процессоры. При наличии указанных обме­нов каждый процессор рождает решение исходной задачи во всей об­ласти D (или Q). Следовательно, предлагаемая схема не включает како­го-либо выделенного (управляющего) процессора, что повышает на­дежность функционирования при возможных аппаратных или про­граммных сбоях отдельных процессоров, а также в случае передачи час­ти процессоров для обеспечения других клиентов или других нужд вы­числительной системы. В последнем случае (т.е. при уменьшении числа p используемых процессоров) не требуется какого-либо специального информирования об этом изменении значения p .
7. Для иллюстрации изложенного подхода приведем пример ре­шения 5-мерной задачи с 5 ограничениями вида [3]:
gi(w) = -(x + y + z + u + v )< 0,
g2(w) = (y/3)2 + (u/10)2 -1.4 < 0,
g3(w) = 3 - (x +1)2 - (y + 2)2 - (z - 2)2 - (v + 5)2 < 0,
g4(w) = 4x2 sin x + y2 cos(y + u) + z2[sin(z + v) + sin(10(z -u)/3)]-4 < 0,
g5(w) = x2 + y2 [sin((x + u)/3 + 6.6) + sin((y + v)/2 + 9) + 0.9]2 -
- 17cos2(z + x +1) +16 < 0,
где вектор параметров w = (x, y, z, u, v) принадлежит гиперпараллелепипеду:
-3 < x,y,z < 3, -10 < u,v < 10.
Минимизируемая функция является многоэкстремальной и опре­деляется выражением:
j (w) = sin( xz) - (yv + zu) cos(xy).
Равномерная сетка с шагом 0.01 (по каждой координате) содержит порядка 8 1014 узлов. Далее задача была редуцирована к 10 связанным задачам оптимизации; для их одновременного решения был использо­ван параллельный многомерный индексный метод [2] для вычислений в многопроцессорной системе с 10 процессорами. Общее число итераций составило 59697. Полученная оценка
w" = (-0.068,1.962, 3.431, 9.833, 9.833)
характеризуется значением j (wff) = -42.992, которое улучшилось (после локального уточнения решения) до значения j(w**) = -43.2985.
Для проведения рассмотренных экспериментов использовалось оборудование компаний Intel и Hewlett Packard, переданное в Нижего­родский госуниверситет в качестве грантов для образовательных и науч­но-исследовательских целей.
Исследования поддержаны грантом РФФИ № 04-01-00455-а.
Литература
Pfister G.P. (1995). In Search of Clusters. Prentice Hall PTR, Upper Saddle River, NJ (2nd edn., 1998).
Strongin R.G., Sergeyev Ya.D. (2000). Global optimization with non-convex constraints: Sequential and parallel algorithms. Kluwer Academic Publishers, Dordrecht.
Гергелъ В.П., Стронгш Р.Г. Параллельные вычисления в задачах выбо­ра глобально-оптимальных решений для многопроцессорных кластерных сис­тем // Материалы третьего Международного научно-практического семинара «Высокопроизводительные параллельные вычисления на кластерных систе­мах». Н. Новгород: Изд-во Нижегородского университета. 2003. С. 169-191.

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

Д.Л. Головашкин
Институт систем обработки изображений РАН, г. Самара Самарский государственный аэрокосмический университет имени академика СП. Королева, г. Самара
Введение
Моделирование физических процессов посредством численного ре­шения дифференциальных уравнений находит все более широкое приме­нение в различных отраслях науки. Этому способствует развитие вычис­лительной техники и численных методов, ориентированных на решение таких уравнений. Наиболее распространенные методы (разностные и про­екционные) сводят дифференциальную задачу к системе линейных алгеб­раических уравнений (СЛАУ) вида Ax=b, где матрица A - ленточная.
С появлением вычислительных систем, допускающих параллель­ные вычисления, связано создание параллельных алгоритмов решения таких систем, основанных как на ранее известных последовательных ал­горитмах (методы прогонки [1], циклической редукции [2]), так и алго­ритмов, изначально создававшихся как параллельные. По мнению авто­ра в данном случае уместна классификация, разделяющая параллельные алгоритмы на алгоритмы с функциональной декомпозицией и с деком­позицией данных [3].
В [4] опубликован один из первых алгоритмов, основанных на де­композиции данных, при которой производится распределение матрицы системы между задачами (в терминах модели канал/задача [3]), позво­ляющее каждой задаче алгоритма решать свою подсистему, выражая решение через значения на границах области данных, входящих в зада­чу. Для вычислительных систем с различной архитектурой синтезиро­вано целое семейство параллельных алгоритмов, основанных на этом принципе. К недостаткам данного подхода следует отнести высокие требования к сетевой конфигурации вычислительной системы (если вы­числения производятся на кластере, то необходимо «бинарное дерево») и отсутствие учета особенностей сеточной области, на которой решает­ся исходная дифференциальная задача.
Функциональная декомпозиция, применительно к данной задаче, была использована в работе [5]. Автор алгоритма, рассматривая разност­ное решение двумерного эллиптического уравнения на прямоугольной об­ласти, отказался от идеи одновременного решения одной СЛАУ несколь­кими задачами. Все задачи реализуют прямой или обратный проходы ска­лярной прогонки для своих участков различных СЛАУ. В случае вытяну­той в одном направлении сеточной области ускорение данного алгоритма превышает ускорение алгоритма из [4], при этом используется простейшая сетевая конфигурация «линия». Недостатком функциональной декомпо­зиции для алгоритма скалярной прогонки является простои задач, ограни­чивающий рост масштабируемости [3] алгоритма при сгущении сеточной области вдоль выбранного направления. Представляемая работа является развитием данного подхода. Применив его к методу встречных прогонок [1] автор вдвое сократил длительность простоев параллельного алгоритма, сохранив достоинства функциональной декомпозиции для вытянутых прямоугольных сеточных областей. Такие области встречаются, например, в задачах дифракционной оптики и теплопроводности при моделировании работы дифракционных оптических элементов.
1. Алгоритм для одномерной сеточной области
Очевидно, при разностном решении дифференциального уравне­ния (пусть эллиптического) на одномерной сеточной области с1 следует говорить об одной СЛАУ трехдиагонального вида (применяется про­стейшая неявная разностная схема из [6]). В этом случае наиболее уме­стны параллельные алгоритмы с декомпозицией данных, но для иллю­страции основной идеи данной работы построим параллельный алго­ритм с функциональной декомпозицией. Непосредственное использова­ние алгоритма из [3] невозможно в силу единственности решаемой СЛАУ. Однако, составление двухзадачного алгоритма, основанного на методе встречных прогонок возможно.
а)
Функциональная декомпозиция задается спецификой метода встречных прогонок, в котором прогоночные коэффициенты (a, b и л,, Z) вычисляются с двух сторон по направлению к центру матрицы А. В последовательном алгоритме этот прием используется, когда желают ограничиться нахождением не всего вектора x, а лишь его части. Так как вычисления двух пар коэффициентов прогонки независимы (информа­ционно, логически и конкуренционно [7]), то их можно находить парал­лельно. Произведем разбиение одномерной сеточной области ю1 на ю} и raj2 (рис. 1). Вычисления разделим на три этапа, соответствующие пря­мому (рис. 1а), обратному ходу (рис. 1в) встречной прогонки и обмену данными между задачами (рис. 16).
в)
Рис. 1. Этапы вычислений по двухзадачному параллельному алгоритму, реализующему метод встречных прогонок на одномерной сеточной области: а - прямой ход прогонок; б - обмен данными между задачами; в - обратный ход прогонок
В течение прямого хода прогонки первая задача находит прогоноч­ные коэффициенты a, b, вторая задача л, С Далее, первая задача переда­ет второй пару чисел a, b, необходимых для запуска обратного хода про­гонки во второй задаче, которая в это время производит аналогичную пе­редачу, необходимую первой задаче. На третьем этапе обе задачи одно­временно реализуют обратный ход прогонки, находя решение СЛАУ. Ускорение такого алгоритма можно оценить как:
s = Т а (N)
Vt а (N)+ 2t /
где N - размерность СЛАУ, xa(N)=3Nix+(2N+1)i^+3Ni+ - время расчета по последовательному алгоритму (т+ - длительность одной операции сложения и вычитания), тх - длительность одной операции умножения, т+ - длительность одной операции деления), тк - время передачи или прие­ма (считаем их равными) одного пакета по сети. При пакетной модели передачи данных время передачи разного объема информации будет ос­таваться константой до тех пор, пока объем передаваемого массива не превысит размер пакета. Здесь это условие соблюдается (передается все­го пара чисел), в дальнейшем также будем полагать его верным.
Очевидно, при N—»°о s®2. К сожалению, этот подход нельзя развить для большего количества задач, если сеточная область со одномерна.
2. Алгоритм для двумерной сеточной области
Для двумерной области со2 это ограничение снимается. Примени­тельно к ней будем говорить о прогонке по строкам (продольной про­гонке) и столбцам (поперечной прогонке) сеточной области, как это принято в методах расщепления и переменных направлений [6].
Если алгоритм состоит из двух задач, то модификации, по сравне­нию с предыдущим алгоритмом, не требуется, каждая СЛАУ в продоль­ном направлении решается одновременно двумя задачами. Пусть размер сеточной области со2 - NxM узлов (разбиение производится по M), тогда ускорения такого алгоритма s2 и известного алгоритма из [5] ˜2 составят
^ = Nt а (N)+ Mt а M) ˜ = Nt a (N)+ Mt a (M)
2 N M N M '
-t а (N)+ -t а (M)+ 2Nt k -t а (N)+ — t а (M)+ 2Nt k + Vt а (M)

Четвертое слагаемое в знаменателе последней формулы есть вре­мя ожидания для задачи в известном алгоритме. Двухзадачный алго­ритм, основанный на методе встречных прогонок, свободен от задержек вычислений, связанных с ожиданиями.
Для алгоритма из четырех задач производится следующее разбие­ние сеточной области (рис. 2).
На рис. 2а-2в представлены начальные этапы вычислений по алго­ритму. Задачи 1, 4 (рис. 2а) начинают прямой ход прогонки для строки 1 и передают прогоночные коэффициенты задачам 2, 3, которые на первом этапе простаивают.
Далее не будем специально говорить об обмене данными между задачами, подразумевая, что перед прямым ходом они принимают про­гоночные коэффициенты, после прямого хода передают их. Перед об­ратным ходом принимают значение сеточной функции, после - переда­ют его. Первая и последняя задачи начинают прямой ход без принятия прогоночных коэффициентов, а задачи под номерами L/2 и L/2+1 (L -общее число задач, в данном алгоритме L=4) начинают обратный ход принятием прогоночных коэффициентов (друг от друга).
На втором этапе (рис. 26) задачи 2, 3 продолжают прямой ход для строки 1, задачи 1, 4 начинают прямой ход для строки 2. Третий этап (рис. 2в) характеризуется простоем задач 1, 4 и началом обратного хода прогонки для строки 1 задачами 2, 3. Четвертый этап (рис. 2г) - прямой ход, задачи 1, 4 осуществляют его для строки 3, задачи 2, 3 для строки 2.










<2J
ы
и

О
Ж
О
ffi
ST
о Н го
(D
о
К И
о

д) °
Рис. 2. Этапы вычислений по четырехзадачному параллельному алгоритму для двумерной сеточной области. а, б, г- прямые ходы прогонок; в, д- обратныеходы. Задачи, помеченные символом «*»,
простаивают
Пятый этап (рис. 2д) - обратный ход, задачи 1, 4 осуществляют его для строки 2, задачи 2, 3 для строки 3. Далее прямой и обратный ходы чере­дуются, пока задачи 2, 3 не произведут прямой ход прогонки для последней строки. На следующем этапе задачи 1, 4 будут простаивать, задачи 2, 3 нач­нут обратный ход. Заключительный этап алгоритма характеризуется про­стоем задач 2, 3, в то время, как задачи 1, 4 завершат обратный ход прогон­ки для последней строки сеточной области. Прогонка по столбцам осуще­ствляется каждой задачей самостоятельно, эти вычисления независимы.
Ускорения данного алгоритма и известного из [5] оценивается ве-

Nt а (N)+Mt a (M )
личинами
s 4
4 ta (N)+ M ta (M)+ 4Ntk + 0,25ta (m)

N ta (N) + M ta (M)+ 4Ntk + 0,75ta (M)+ 4tk
где 0,25xa(M) - время ожидания в разработанном алгоритме, 0,75xa(M)+4xK - время ожидания в известном алгоритме.
Распространим данный подход на произвольное число задач L. На
начальном этапе такого алгоритма в течении первых L/2 шагов произво-
дится только прямой ход прогонки. Задача l (пусть l<L/2) простаивает l-
1 шаг, затем производит прямой ход прогонки для строк 1,2, L/2-/+1.
Затем происходит чередование прямого и обратного хода, причем зада-
ча l простаивает шаги, связанные с обратным ходом в течении L/2-l ша-
гов обратного хода. Далее происходит чередование без простоев. Если в
течение прямого хода задача 1 производит прямой ход прогонки для
строки i, то задача l производит прямой ход для строки Когда пер-
вая задача начинает обратный ход для строки i, задача l начинает обрат-
ный ход для Последние шаги алгоритма опять связаны с просто-
ями, когда во время прямого хода простаивают задачи (для l<L/2) с
меньшими номерами, во время обратного - с большими номерами. Ана-
логично проводятся рассуждения для l>L/2.
Ускорения такого алгоритма и традиционного из [5] составят:
L I" a (N)+ У" a (M)+ 4Nt k + L2L2T a M)+(L — 4> ,
и S =. Nt a (N)+ Mt a (M)
'L
N t a (N)+ M t a (M)+ 4 Nt k +L-11 a M )+ 2(L - 2> к
По сравнению с известным алгоритмом, основанном на функцио­нальной декомпозиции длительность простоев сокращена в два раза.
Оценка сверху для ускорения лучшего алгоритма, основанного на декомпозиции данных составит
Nt a (N)+Mt a (M )
Lxa (N)+ Lta (M)+ 2N(log2 L>ck
Определим пороговую величину f -log2 L , где
2 + l(M)+
4LN 2N
i(m) -ta (m). При f> 1 можно утверждать, что ускорение представленного
t k
алгоритма превзойдет ускорение лучшего, основанного на декомпозиции данных. Чем больше значения принимают величины L, N и чем меньше l (лучше быстродействие процессора и медленнее передача данных по се­ти), тем уместней использование разработанного алгоритма.
Nt a (N)+ Mt a (M)

Например, положив L=16 и Z(M)=200, исследуем зависимость fN) (рис. 3). При N>24 представленный алгоритм характеризуется большим ускорением, чем известные.
/ 1,4
1,2 1,0 0,8 0,6 0,4
10 20 30 40 50
Рис. 3. Зависимость параметра f
от количестваузлов сеточной области N
Отметим, однако, что как только увеличение параметра N позво­лит предпочесть двумерную декомпозицию области со2 одномерной (так как область более нельзя будет считать вытянутой в выбранном направ­лении), алгоритм с декомпозицией данных станет оптимальнее в смысле ускорения. Вопрос о применении к исследуемой сеточной области того или иного алгоритма в каждом конкретном случае решается с учетом особенностей имеющейся в распоряжении исследователя вычислитель­ной системы (задающей 1).
К достоинству представленного подхода следует отнести более мяг­кие требования к конфигурации сети, соединяющей процессоры вычисли­тельной системы. Если организация вычислений по параллельному алго­ритму с декомпозицией области потребует сетевую конфигурацию «би­нарное дерево», то использование предложенного алгоритма позволяет ограничиться «процессорной линией».
Выводы
Применение функциональной декомпозиции к синтезу параллель­ных алгоритмов, основанных на методе встречных прогонок, для реше­ния сеточных уравнений трехдиагонального вида оправдано для вытя­нутых прямоугольных сеточных областей и для реализации на класте­рах, процессоры которых соединены в линию. Представляется целесо­образным развитие данного подхода для алгоритма циклической про­гонки и ленточных систем с большим количеством диагоналей.
Благодарность
Работа выполнена при поддержке Министерства образования РФ, Администрации Самарской области и Американского фонда граждан­ских исследований и развития (CRDF) в рамках Российско-американской программы «Фундаментальные исследования и высшее образование» (BRHE), а также Фонда содействию отечественной науке.
Литература
СамарскийА.А., Николаев Е.С. Методы решения сеточныхуравнений // М.: Наука. 1978. - 561 с.
Ортега Джеймс М. Введение в параллельные и векторные методы ре­шения линейных систем // Перевод с англ. Х.Д. Икрамова, И.Е. Капорина; под ред. Х.Д. Икрамова. М.: Мир, 1991. - 364 с.
Braunl T. The art of parallel programming // Prentice Hall International (UK) Limited, 1993. 378 p.
Яненко H.H., Коновалов A.H., Бугров A.H., Шустов Г.В. Об организа­ции параллельных вычислений и «распараллеливание» прогонки // Числен­ные методы механики сплошной среды / ИТПМ СО АН СССР. Новосибирск, 1978. Т. 9. С. 139-146.
5. Миренков Н.Н. Параллельные алгоритмы для решения задач на
однородных вычислительных системах // Вычислительные системы. ИМ СО
АН СССР. Новосибирск, 1973. Вып. 57. С. 3-32.
6. СамарскийА.А. Теория разностных схем // М.: Наука, 1989. - 614 с.
7. Валъковский В.А., Котов В.Е., Марчук А.Г., Миренков Н.Н. Элементы
параллельного программирования // М.: Радио и связь, 1983. - 239с.


ПОВЫШЕНИЕ ПРОИЗВОДИТЕЛЬНОСТИ КОЛЛЕКТИВНЫХ ОПЕРАЦИЙ MPICH-2
А.В. Гришагин
Нижегородский государственныйуниверситет, г. Нижний Новгород
Введение
Распространенность кластерных установок в мире параллельного ап­паратного обеспечения, а так же невысокая стоимость и простота построе­ния приводят к огромному количеству разнообразных конфигураций. Фактически, каждый кластер в некотором роде «уникален», кроме тех, ко­торые специально разрабатываются и продаются единым комплексом. Ещё большее разнообразие вносит программное обеспечение: известно, например, что смена версий ядра Linux может изменить коммуникацион­ные задержки вплоть до 2-х раз. Такое разнообразие в производительно­сти, и, более того, отсутствие стабильности в производительности должно учитываться при создании средств параллельного взаимодействия, ведь разные режимы передачи для «больших» и «маленьких» сообщений появ­ляются почти повсеместно. При определении того, что есть «большое» и «маленькое», обычно господствует голая эмпирика (показательна в этом смысле работа [1]). Ясно, что проблема это достаточно общая, и необхо­димо вырабатывать общие подходы к её решению. В данной работе ука­занные проблемы рассматриваются на примере коллективных операций в библиотеке MPICH-2 (http://www-unix.mcs.anl.gov/mpi/mpich2/).
Алгоритмы коллективных операций в MPICH-2
Библиотека MPICH-2 использует несколько алгоритмов для каж­дой коллективной операции. Например, в MPI_Bcast(...) есть три спосо­ба разослать «всем» сообщение. Это бинарное дерево, рассылка частей сообщения и последующий сбор, а так же кольцевая рассылка (подроб­нее см. [1]). При этом в исходный код MPIBcast жестко зашит меха­низм выбора алгоритма для рассылки: для размера сообщения менее 12К всегда используется бинарное дерево (независимо от размера ком­муникатора), для размера коммуникатора более 8 и объема данных ме­нее 512К используется рассылка частей и последующий сбор, а для дан­ных больше 512К - кольцевая рассылка.
Естественно, раз и навсегда запрограммированная схема никогда не покажет наилучшей производительности. Поэтому было принято ре­шение добавить в библиотеку MPICH-2 механизмы выбора наилучшего алгоритма для каждого вызова коллективной операции.
Технология измерения производительности
Первый шаг - изменение исходного кода MPI-библиотеки, здесь и далее речь идет именно о MPICH-2, разбирается пример MPIBcast, хо­тя схема работает для любой коллективной операции. В библиотеку до­бавляется измененная коллективная операция, с тем же кодом, что и из­меряемая, но с одним дополнительным параметром - номером алгорит­ма для пересылки.
int MPI_Bcast(void*, int, MPIDatatype, int, MPIComm );
int MPI_Bcast_bnchmrk(void*, int, MPIDatatype, int, MPIComm, int alg).
Далее, создание параллельного приложения выбора лучшего алго­ритма. Идея следующая: как и любая MPI-программа, приложение со­бирается с библиотекой MPICH-2 (уже измененной), и запускается на всем кластере. Размер MPI_COMM_WORLD в этом случае будет коли­чество доступных узлов.
Далее, в приложении перебираются все возможные размеры ком­муникаторов, начиная с 2, и заканчивая MPI_Comm_size (MPI_COMM_WORLD, ...) с единичным шагом. Для каждого размера коммуникатора перебираются размеры буферов пересылаемых сообще­ний, начиная с 0 и заканчивая определенным пользователем значением (как правило, несколько мегабайт) с некоторым промежутком. Реализо­ваны линейная и логарифмическая шкалы изменения размеров буферов. Теперь последовательно вызываются все алгоритмы из имеющихся (в MPICH-2 для MPIBcast их три) с выбранными размерами коммуника­тора и буфера. Каждый алгоритм вызывается подряд по несколько раз, и измеряется время всех вызовов. Несколько одних и тех же вызовов де­лается того, что бы получить усредненное время.
В итоге, для каждого размера коммуникатора и размера буфера получается три (MPICH-2, MPIBcast) времени выполнения.
Для каждого размера коммуникатора после перебора всех разме­ров буферов вычисляются лучшие алгоритмы, а так же размер буфера, начиная с которого этот алгоритм нужно применять. Например:
0:Btree 200000:Ring 900000:ScGather, т.е., начиная с 0 байт выгод­нее использовать алгоритм «бинарное дерево», с 200000 байт «кольце­вую рассылку», а с 900000 - «рассылка и сбор».
Такая информация для каждого размера коммуникатора сохраня­ется в результирующий файл.
В вызов MPI_Init добавляются процедуры чтения сгенерированных файлов и заполнения внутренних структур данными из этого файла. Вы­зов MPIBcast никак не меняется, однако внутри устроен совсем иначе -на основе размера коммуникатора и буфера сначала из внутренних дан­ных выбирается номер лучшего способа передачи, а затем вызывается алгоритм именно с этим номером.
Предложенная схема работает только на гомогенных кластерах по следующей причине: все узлы кластера имеют одинаковую конфигура­цию, и запуск алгоритма, выбранного на этапе измерения, покажет та­кую же производительность на некотором подмножестве компьютеров исходной конфигурации. При этом порядок и количество узлов в файле запуска реального параллельного приложения не будут иметь никакого значения, т.к. все узлы одинаковы. Здесь же нужно отметить, что узлы должны иметь по одному процессору, поскольку, очевидно, результаты запуска, например, конфигурации, 2 узла по 2 процесса и 4 узла по од­ному, даст совершенно разные результаты, т.к. в этом случае латент-ность пересылок будет играть самую важную роль.
Можно было бы организовать подобную схему и для кластеров разнородных компьютеров, но придется изменить алгоритм перебора узлов, а именно, придется для каждого возможного размера коммуника­тора строить перестановки попавших в него узлов и запускать вычисле­ние на каждом таком варианте. Время работы такой схемы имеет почти факториальное значение от количества узлов кластера. Кроме того, если бы даже удалось провести такие эксперименты, при запуске приложе­ний пришлось бы анализировать файл запуска с именами узлов, что то­же не ускорит выполнение параллельной программы.
Так же, нельзя перенести сгенерированные файлы на совершенно другой кластер (с отличной аппаратной конфигурацией), т.к. измерен­ные величины корректны только для того суперкомпьютера, на котором были получены, на других же установках можно получить даже замед­ление по сравнению со стандартной схемой, а вовсе не выигрыш.
Тестирование кластеров
Реализованная схема для MPIBcast была протестирована на 2-х кластерах: кластер Нижегородского государственного университета (12 узлов Pentium III 1GHz, 256 Mb RAM, Gigabit Ethernet, OS Win2000AS) и установка MBC-1000/32, установленная в ИММ УрО РАН (16 узлов 2xPentium 4 2GHz, OS Linux Fedora Core 1, HyperThreading включен).
Нижегородский кластер показал полное превосходство бинарного дерева, лишь для больших буферов (более 1-х Мб) лучше оказалась кольцевая рассылка.
МВС-1000/32 показывает наилучшее время для бинарного дерева при данных в среднем менее 800Кб, и кольцевую рассылку в противном случае. Алгоритм «рассылка-сбор» и на этом кластере лучшим не ока­зался ни разу, хотя в стандартной схеме используется часто. Видимо, это связано с очень высокой латентностью кластера, а «рассылка-сбор» использует много маленьких пересылок, тогда как другие алгоритмы выполняют по одной пересылке всего буфера целиком.
Заключение
Реализованная схема определения лучших алгоритмов коллектив­ных операций была протестирована на двух кластерах, и в результате экспериментов новая схема операции MPIBcast показывает выигрыш по времени до 1,6 раза для большинства вызовов по сравнению со стан­дартной схемой.
Сейчас ведется подключение других коллективных операций к приложению и MPICH-2 и проведение соответствующих экспериментов. Как видно из результатов для MPIBcast, предложенный подход позволя­ет во многих случаях существенно сократить время вызовов коллектив­ных операций.
Автор выражает благодарность Александру Коновалову и Антону Пегушину (ЗАО «Интел АО») за помощь в разработке, а также ИММ УрО РАН за предоставленные вычислительные ресурсы.



z
cd q.
о С
о
a
x
it-Hi о
1,8 1,6 1,4 1,2
о
0,8 0,6 0,4 0,2
" "стандартная схема "новая схема

0
4-ч839-чо)-чо-ч-ч2018380133010824 240-ч81228121183-ч401010)010)0-ч
слсл-^слосо-^сосо-^ю-ч-чсоослю-ч-^спо378
сою-^сл-чсоюслсл-^-^о9729984"^!-1
aia)oa)98o3i8ok)k)
к) о
буфер (байты)

Рис. 1. Время работы MPIBcast на 10 узлах кластера ИММ УрО РАН
Литература
Thakur R., Gropp W. Improving the Performance of Collective Operations in MPICH.
Лацис А. Как построить и использовать суперкомпьютер // М.: Бест­селлер, 2003.

ЭФФЕКТИВНОСТЬ РАСПАРАЛЛЕЛИВАНИЯ ХАРАКТЕРИСТИЧЕСКИХ АЛГОРИТМОВ ГЛОБАЛЬНОЙ ОПТИМИЗАЦИИ В МНОГОШАГОВОЙ СХЕМЕ РЕДУКЦИИ РАЗМЕРНОСТИ

В.А. Гришагин, Я.Д. Сергеев
Нижегородский государственныйуниверситет им. Н.И. Лобачевского,
г. Нижний Новгород
Задачи многоэкстремальной многомерной оптимизации, в кото­рых требуется найти глобальный оптимум функции многих перемен­ных, имеющей несколько локальных экстремумов, обладают высокой вычислительной сложностью и требуют разработки новых подходов к их эффективному решению. Одним из современных подходов такого плана в настоящее время является подход, основанный на редукции размерности решаемой многомерной задачи и применении параллель­ных методов оптимизации для решения редуцированных задач [1, 2].
Идея редукции размерности состоит в сведении исходной много­мерной задачи к решению одной или нескольких одномерных задач. Ре-


Напомним, что вычисление целевой функции на всех уровнях, кроме по­следнего, состоит в решении новой оптимизационной подзадачи.
Пусть на i -м уровне рекурсии применяется синхронная схема ор­ганизации параллельной итерации одномерного алгоритма, когда ите­рация считается завершенной только после проведения всех p i испыта­ла
ний. В этом случае по меньшей мере ]]p i процессоров, которые уже
завершили решение своих подзадач, будут простаивать до тех пор, пока не завершится решение остальных подзадачi -го уровня. Это означает, что для повышения производительности процесса решения в многоша­говой схеме необходимо использовать асинхронные параллельные ал­горитмы глобальной оптимизации, в которых вычислительные ресурсы используются сразу же по их освобождении.
В работе [5] предложен широкий класс параллельных методов од­номерной глобальной оптимизации, в котором решающие правила алго­ритмов обладают так называемой характеристической структурой. Данные алгоритмы могут реализовывать как синхронные, так и асинхронные ме­ханизмы распараллеливания. В ряде работ (см., например, работы [2], [6], [8]) проведено экспериментальное тестирование конкретных параллель­ных характеристических алгоритмов в сочетании со схемой вложенной оптимизации, в том числе на классах существенно многоэкстремальных функций нескольких переменных, включая тестовый класс [7].
Соединяя одномерные характеристические параллельные алго­ритмы с многошаговой схемой редукции размерности, мы конструиру­ем новый класс параллельных алгоритмов многомерной оптимизации. Для данного класса проведено обобщение теоретических результатов работы [5], справедливых для одномерной оптимизации, на многомер­ный случай. Получены оценки эффективности многошаговых характе­ристических алгоритмов, связанные с понятиями безызбыточности рас­параллеливания и ускорения поиска. В частности, установлены условия, при которых многомерные характеристические алгоритмы являются бе­зызбыточными и обеспечивают ускорение поиска при решении задачи (2) до 2л раз. Полученные ранее экспериментальные результаты пока­зали хорошее согласование с теоретическими оценками.

Работа выполнена при поддержке РФФИ (грант № 04-01-00455-а).
Литература
1. Strongin R.G., Sergeyev Ya.D. Global optimization with non-convex con­straints: Sequential and parallel algorithms // Kluwer Academic Publishers, Dordrecht, Netherlands. 2000.
Sergeyev Ya.D., Grishagin V.A. Parallel asynchronous global search and the nested optimization scheme // Journal of Computational Analysis & Applica­tions, 3(2), 2001. P. 123-145.
Carr C.R., Howe C.W. Quantitative Decision Procedures in Management and Economics // Deterministic Theory and Applications. McGraw Hill, New York, 1964.
Стронгш Р.Г. Численные методы в многоэкстремальных задача // Информационно- статистическийподход. М.: Наука, 1978.
Strongin R.G., Sergeyev Ya.D., Grishagin V.A. Parallel Characteristical Al­gorithms for Solving Problems of Global Optimization // Journal of Global Optimi­zation, 10, 1997. P. 185-206.
Гришагин B.A., Филатов A.A. Параллельные рекурсивные алгоритмы многоэкстремальной оптимизации // Материалы второго Международного научно-практического семинара «Высокопроизводительные параллельные вычисления на кластерных системах» / Под ред. проф. Р.Г. Стронгина. Н. Новгород: Изд-во Нижегородского госуниверситета, 2002. С. 88-90.
Gaviano M., Kvasov D.E., Lera D., Sergeyev Ya.D. Software for Genera­tion of Classes of Test Functions with Known Local and Global Minima for Global Optimization // (Принято к опубликованию в ACM Transactions on Mathemati­cal Software).
Гришагин B.A., Песков B.B. Повышение эффективности параллельных рекурсивных схем редукции размерности // Высокопроизводительные парал­лельные вычисления на кластерных системах: Материалы Международного научно-практического семинара / Н. Новгород: Изд-во ННГУ. 2002. С. 56-60.

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

О.А. Дмитриева
Донецкий национальный технический университет, г. Донецк
Данная статья является продолжением работ [1-3], которые посвяще­ны проблемам создания и исследования параллельных алгоритмов числен­ного решения систем ОДУ, используемых для моделирования сложных ди­намических систем с сосредоточенными параметрами. Предлагаемые алго­ритмы ориентированы на использование в многопроцессорных вычисли­тельных системах SIMD (single instruction stream - multiple data stream) структуры с решеткой или линейкой процессорных элементов. Набор про­цессоров известен до начала вычислений и не меняется в процессе счета, при этом каждый процессорный элемент может выполнить любую арифме­тическую операцию за один такт, временные затраты, связанные с обраще­нием к запоминающему устройству, отсутствуют.
Пусть математическую модель динамической системы можно представить в виде системы ОДУ с постоянными коэффициентами и начальными условиями:
^ = Ax + f(t), ˜x(t0) = 7 = (x0, x°,..., xl)t, (1)
dt
где x - вектор неизвестных сигналов, f(t) - вектор воздействий, t g [0,T], A - матрица коэффициентов системы.
В этом случае решение можно получить последовательно по ша­гам с помощью численных методов заданного порядка точности.
Здесь вычисление значения вектора неизвестных x на очередном
шаге требует предварительного определения значений x . В [1] рассмот­рены вопросы, связанные с возможностью параллельной реализации таких алгоритмов. В частности, если система (1) является однородной, т.е. f(t)=0, i=1,2,...m, тогда, в зависимости от выбранного метода интегриро­вания, можно искать решение в виде:
-n+1 -п
x = G- , (2)
где G- оператор (матрица) переходов.
Полученный оператор перехода G, который необходимо опреде­лить один раз до начала вычислений, позволяет вычислять значения вектора неизвестных параллельно [2, 3]. Для методов Рунге-Кутты, на­пример, этот оператор может быть представлен, в зависимости от точ­ности метода, как
t A t A t A G = E +t A(E + — (E + — (E + —)))
2 3 4 , (3)
который обеспечивает точность 4-го порядка, или, например, как
tA t A tA t A t A
G = E + tA(E + — (E + — (E + — (E -(E -)))))
2 3 4 5 4, (4)
точность которого оценивается 6-м порядком.
При решении неоднородной системы необходимо дополнительно вы­числить на каждом шаге значения всех функций fi(t), i =1,тъ нескольких
промежуточных точках. Поскольку все эти функции могут быть различны­ми, одновременное вычисление их на SIMD компьютере невозможно.
В связи с этим можно предложить два основных подхода, первый из которых состоит в том, что все промежуточные значения функций fi(t)
могут быть вычислены заранее. При этом если количество промежуточных точек метода определяется как r, то можно оценить количество тактов рас­чета на топологических структурах линейке из m процессоров и решетке из mxm процессоров (размерность процессорного поля выбрана совпадающей с размерностью системы уравнений исключительно для удобства изложе­ния). Определим для этого трудоемкость реализации правых частей систе­мы, как Q fi, и при расчете будем оперировать с максимальным значением,
которое обозначим, как Qf = max\@f.}. Если расчет осуществляется для об­щего количества узлов, равного N, то общее число тактов работы на линей­ке процессоров составит для одного уравнения ближайшее целое сверху
r*Q *n \r*Qf*N˜\
соотношения или +1. Тогда вся система может быть
m m
рассчитана за r*Qf*N + m тактов. На решетке процессоров одно уравнение
^ r*Qf*N
будет решаться за ближайшее целое сверху к - тактов, а время, ко-
m

\r*Q f*N
торое потребуется для расчета всей системы составит 1 J
+1. По

m
каждому уравнению системы придется хранить двумерные массивы раз­мерностью rxN и использовать коэффициенты с нужными индексами при расчете.
Второй подход, который позволит избежать последовательных участ­ков при параллельной реализации системы, основывается на предваритель­ном интерполировании правых частей (1). В вычислительной практике с таким подходом сталкиваются, если приходиться заменять одну функцию f(t) (известную, неизвестную или частично известную) некоторой функ­цией j (t), близкой к f(t) и обладающей определенными свойствами, по­зволяющими производить над нею те или иные аналитические или вычис­лительные операции. Такую замену называют приближением функции f(t) . Тогда при решении задачи вместо функции f(t) оперируют с функ­цией j (t), а задача построения функции j (t) называется задачей прибли­жения. Исходя из проблематики задачи, т.е. принимая во внимание боль­шое количество узлов, которые будут участвовать в расчете, и, задаваясь требуемой точностью приближения функций, можно утверждать, что наи­более перспективным является случай, когда используются кусочно-полиномиальная аппроксимация, или сплайны, так как при этом интерпо­ляционный многочлен строится не на весь интервал решения задачи, а на подынтервалах, что позволит избежать накопления ошибок приближения.
Основная идея такого подхода заключается в следующем: исход­ный отрезок решения для (1) [0,T] разбивается на несколько подынтер­валов V с шагом, определяющимся из соотношения точности методов численного интерполирования и интегрирования, а затем на каждом та­ком интервале строится интерполяционный многочлен. Поскольку в ка­честве интерполяционной функции обычно выбирают многочлены сте­пени не выше 3-4-й, что соответственным образом влияет на точность интерполяции, то необходимо предварительно согласовать порядки точности методов численного интегрирования и предварительного ин­терполирования .
Если порядок метода численного интегрирования (1) определяет­ся, как O(xv), а порядок сплайна, как O(h4), то между шагами двух ре­шающихся задач должно выполняться соотношение tv = h4. Если поря­док точности метода интегрирования v=4 или более, т.е. между количе­ством узлов задач интерполирования и интегрирования выполняется со­отношение V>N, то использование интерполирования для восстановле­ния значений правых частей является нерациональным. Проще заранее вычислить значения правых частей на промежутке [0,T]. Если же речь идет о методах интегрирования, которые имеют порядок погрешности ниже 4, то тогда V<N и при этом значения Vn N можно связать с помо­щью некоторого коэффициента Д т.е.
N = b *V, где b >>1. (5)
При этом желательно выбирать множитель b целым, т.к. предпоч­тительнее, чтобы на одном такте расчета использовались коэффициенты одного интервала сплайна, что значительно упростит алгоритм вычис­ления и выбор нужного интервала по заданному аргументу.
Если исходить из (5), то узлов интерполирования будет в b Раз меньше, чем узлов интегрирования. К тому же оценку погрешности для сплайна порядка O(h4) можно считать завышенной. Тогда исходная за­дача может быть сведена к двум подзадачам, каждая из которых легко распараллеливается.
Первая подзадача будет заключаться в нахождении коэффициен­тов сплайна. Замену исходных функций f(t) в (1) на сплайн-функции
будем осуществлять в виде:
aii + biit + ciit 2 + dilt3 + eiit 4,i =1,m,! =1,V (6)
Тогда, во время реализации второй подзадачи, вместо разнородных операций (которые на SIMD-структурах выполняются последовательно), все правые части системы (1) будут считаться параллельно по одним и тем же аргументам t, но с разными коэффициентами сплайн-функций ail,bil,cil,dil,eil, i = 1,m,l = 1,V . Для нахождения неизвестных коэффициен­тов по каждому уравнению системы (1) придется решать систему линей­ных алгебраических уравнений размерностью 4V*4V. Формирование системы линейных уравнений будет исходить из принципов совпадения значений функции, ее первых, вторых и третьих производных на сосед­них подынтервалах слева и справа от узла интерполяции.
Пусть {Pl} - множество узлов интерполяции, l = 0,V. Причем, для любой правой части системы (1) это множество узлов будет постоянным.
Между узлами pl-1 и pl будем представлять функцию i-ro уравне­ния системы в виде:
Si(p) = au + bu(p - pl-1) + cu(p - pl-1)2 + du(p - pl-1)3 + eu(p - pl-1)4 (7) pl-1 Ј p Ј pl i = 1,m,l = 1,V
Исходя из постановки задачи интерполирования, в узлах интерпо­ляции значения исходной функции и интерполяционного многочлена должны совпадать, т.е.:
Si(pl) = fu i = = 0V (8)
С другой стороны, если аргумент сплайна совпадает с узлом ин­терполяции, тогда из (7) и (8)
Si(pl-1) = au = i = \m,l = Ту . (9)
Поскольку интерполяционный многочлен строится для равно­стоящих узлов, т.е.:
pl - pl-1 = h, (10)
то, используя полученные соотношения, можно переписать формулу для сплайна в /-ом узле в следующем виде:
fil = fil-1 + bilh + cilh 2 + dilh 3 + eilh 4.
Для построения оставшихся соотношений воспользуемся согла­шением о совпадении 1-ой, 2-ой и 3-ей производных справа и слева от узлов интерполяции, т.е. для первых производных
Si (p) = ba + 2ca (p - pl-1) + 3d, (p - pl-1)2 + 4el7 (p - pl-1 )3
pl-1 Ј p Ј pl (12)
S, (p) = bu+1 + 2cl7+1 (p - pi ) + 3d,+1 (p - pl )2 + 4el7 (p - pl )3
pl Ј p Ј pl+1.
Для каждого уравнения системы (1) будем приравнивать (12) в точке pl, тогда:
= ba + 2cah + 3dah2 + 4eah3 (13)
Аналогично приравнивая значения полученных выражений для 2-ой и 3-ей производных в узлах интерполяции и добавив граничные ус­ловия, получаем m систем линейных уравнений.
Сформированные системы относительно вектора неизвестных ко­эффициентов можно представить в общем виде, как:
Qiyi = gi, i = (14)
Векторы неизвестных будут иметь вид:
yi = (ai1 ,bi1 ,ci1 ,di1 ,ei1 ,-,aiV,biV,ciV,diV,eiV), i = 1,m . (15)
Особенностью полученных систем является ленточный вид мат­рицы Q, т.к. каждое уравнение системы (за исключением первого и по­следнего) будет содержать только 4 неизвестных. В этом случае систему можно преобразовать так, чтобы ее можно было решать методом встречной прогонки [4]. Трудоемкость решения таких систем на парал­лельных SIMD структурах линейно зависит от размерности решаемой системы и для системы размерностью к оценивается, как O(k). Тогда для нашего случая трудоемкость нахождения коэффициентов сплайн-функции для одного уравнения системы будет оцениваться на уровне O(4V). А для исходной задачи (1) число операций приближенно будет оцениваться на уровне 4*V*m.
Еще один возможный подход к решению полученных систем (14), которые имеют большую размерность и разреженную матрицу коэффи­циентов, заключается в приведении ее к блочно-диагональной форме с обрамлением [5, 6] и формировании вспомогательной системы значи­тельно меньшей размерности, которая определит вектор определяющих величин, или переменных связи. Трудоемкость реализации такого подхо­да на параллельных вычислительных структурах будет, как и в преды­дущем случае, линейно зависеть от размерности системы.
Кроме того, для интерполирования необходимо предварительно вы­числить значения правых частей в V точках, которые будут использоваться в качестве исходных данных для построения интерполяционного многоч­лена, тогда для системы из m уравнений потребуется m*(4V + V*Qf) так­тов. Также возникает необходимость в восстановлении значений правых частей по полученным коэффициентам интерполяционных многочленов в N основных и r вспомогательных узлах интегрирования. Последователь­ность выполняемых операций при этом составит для многочлена общего вида a + bt + ct2 + dt3 + et4 на SIMD-структуре:
умножения
1-й такт - t*t
2-й такт - t2 *t, t2 *t2 - параллельно 3-йтакт- b*t,c*t2,d*t3,e*t4 - параллельно сложения
4-й такт - a + b*t,c*t2 + d*t3
5-Й такт - a + b*t + c*t2 + d*t3 + e*t4
Таким образом, на определение одного значения правой части не­обходимо 5 временных тактов. Если учесть, что число точек, в которых необходимо восстанавливать значение правой части каждого уравнения определяется как r*N, то всего на восстановление значений функции по интерполяционному многочлену для системы потребуется 5*m*r*N временных тактов.
Сведем полученные приближенные результаты для 2-х описанных способов реализации правых частей в следующую таблицу.
Таблица 1

Общее число операций
r* Q f*N*m

m*( 4V + V* Q f + 5*r*N)
Число операций на линейке процессоров
[r* Q f*N ]+1

4V + V* Q f + 5*r*N
Число операций на решетке процессоров
˜r*Qf *N' m
+1
(4V + V* Q f + 5*r*N)/m

Поскольку изначально предполагалось, что трудоемкости вычисле­ния правых частей 0f являются высокими [7], то оценка трудоемкости всего алгоритма может осуществляться относительно этих значений. То­гда очевидно, что в случае выполнения соотношения (5), предпочтитель­нее интерполировать правые части, хотя этот подход и сопряжен с алго­ритмическими сложностями, но имеет безусловные преимущества.
Таким образом, в представляемой работе исследованы возможности распараллеливания известных последовательных алгоритмов численного решения систем обыкновенных дифференциальных уравнений и переноса их на параллельные вычислительные структуры с целью получения мак­симальной реальной производительности. Предложены подходы, позво­ляющие избегать последовательных участков работы многопроцессорных вычислительных SIMD систем, один из этих подходов основан на предва­рительном вычислении правых частей неоднородной линейной системы ОДУ, который предпочтительнее использовать, если точность метода ин­тегрирования, с помощью которого решается задача, высока. Разработан также подход, исключающий последовательные вычисления, который ос­новывается на предварительном интерполировании правых частей систе­мы (1) с помощью сплайнов. Выявлены соотношения между порядками погрешностей методов численного интегрирования системы (1) и метода­

ми интерполирования, которые позволяют определить оптимальный вы­бор метода параллельной реализации правых частей.
Литература
Дмитриева О.А. Анализ параллельных алгоритмов численного реше­ния систем обыкновенных дифференциальных уравнений методами Адамса-Башфорта и Адамса-Моултона // Математическое моделирование, 2000. Том 12. № 5. С. 81-86.
Фельдман Л.П., Дмитриева О.А. Эффективные методы распараллелива­ния численного решения задачи Коши для обыкновенных дифференциальных уравнений // Математическое моделирование, 2001. Том 13. № 7. С. 66-72.
Дмитриева О.А. Параллельное моделирование динамических объектов с сосредоточенными параметрами // Тезисы докладов XII Юбилейной между­народной конференции по вычислительной механике и современным при­кладным программным средствам. М.:МГИУ, 2003.
Гаранжа В.А., Конъшин В.Н. Прикладные аспекты параллельных высо­коточных алгоритмов решения задач вычислительной гидродинамики // Тези­сы докладов Всероссийской научной конференции «Фундаментальные и при­кладные аспекты разработки больших распределенных программных комплек­сов». М.: Изд-во МГУ. 1998. С. 34-38.
Джорт А., Лю Д. Численное решение больших разреженных систем уравнений // М.: Мир, 1984. - 333 с.
Дмитриева О.А. Анализ параллельных алгоритмов численного реше­ния систем линейных уравнений итерационными методами // Научн. тр. Дон-ГТУ. Серия: Проблемы моделирования и автоматизации проектирования ди­намических систем, Донецк. 2000. Вып. 10. С. 15-22.
Feldman L., Dmitrieva O., Gerber S. Abbildung der blockartigen Algoritmen auf die Parallelrechnerarchitekture // 16 Symposium Simulationstechnik ASIM 2002, Rostock, 10.09 bis 13.09 2002. Erlangen: Gruner Druck, 2002. P. 359-364.

РАСПАРАЛЛЕЛИВАНИЕ ПРОГРАММ ДЛЯ МНОГОПРОЦЕССОРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ
С ПОМОЩЬЮ ЭКСПЕРИМЕНТАЛЬНОЙ МНОГОЦЕЛЕВОЙ СИСТЕМЫ ТРАНСФОРМАЦИЙ ПРОГРАММ
О.А. Жегуло
Ростовский государственный университет, г. Ростов-на-Дону
Введение
Разработка систем эффективного распараллеливания для много­процессорных суперкомпьютеров с распределенной памятью является предметом активных исследований, хотя для векторных и некоторых других архитектур построены приемлемые решения [1].
Один из способов распараллеливания программ - систематическое выполнение трансформаций программ, представленных в виде схемных правил трансформации [2] некоторого расширенного вида [3]; примене­ние этих правил к распараллеливаемой программе должно обеспечи­ваться разрабатываемой экспериментальной многоцелевой системой трансформаций программ (МСТП) [3]. Выгода от представления распа­раллеливающих преобразований программ в виде схемных правил за­ключается в упрощении модификации и добавления преобразований.
В настоящей работе рассматривается экспериментальная транс­формационная система распараллеливания на основе макетной реализа­ции МСТП на языке Пролог и набора правил распараллеливания [4]. Система предназначена для автоматического, полуавтоматического и ручного распараллеливания.
1. Схемные правила трансформации
В общем случае [2] схемное правило представляет собой пару из входного и выходного образцов (схем заменяемой и заменяющей про­граммных конструкций), снабженных логическим условием примени­мости. Схема получается путем параметризации программы или про­граммной конструкции по вложенным компонентам.
Применение правила заключается в поиске некоторой конструк­ции программы, сопоставимой с входным образцом, при этом парамет­ры входного образца получают значения; затем, если условие примени­мости удовлетворено, вместо найденного фрагмента вставляется конст­рукция, полученная из выходного образца подстановкой параметров.
2. Схемные правила трансформации для распараллеливания
Расширенный вид правил трансформации [3] допускает использо­вание многокомпонентных образцов, которые позволяют записывать нелокальные преобразования.
В случае необходимости допускается использование не схемных правил, а процедурных трансформаций на языке реализации трансфор­мационной системы, в данном макете - на Прологе.
Параметр образца задается своим именем; также должен быть ука­зан его синтаксический тип.
В состав простого образца, кроме параметризованного текста про­граммы, могут входить идентифицирующие выражения [3]. С помощью идентифицирующего выражения можно кратко сослаться на сопостав­ленную с ним синтаксическую конструкцию, задать ее синтаксический тип или указать ее положение относительно других синтаксических конструкций.
Схемное правило может содержать вызовы оператора языка зада­ния правил apply применения заданного правила к множеству про­граммных конструкций.
Условия применимости правил представляют собой логические выражения с использованием предикатов, зависящих от входных пара­метров правила, переменных среды МСТП, логических переменных, квантора всеобщности all, а также присваивания выходным параметрам правила значений. В основном в условиях применимости участвуют ба­зовые предикаты и функции [4]; большинство этих предикатов и функ­ций задано на графовых и других вспомогательных представлениях про­граммы. Пользователь может также определять собственные служебные предикаты на языке реализации макета МСТП, Прологе.
3. Общая структура макета МСТП
Макет МСТП состоит из следующих подсистем.
1) Синтаксический анализатор входного языка и языка схемных
правил со сканером, и соответствующая грамматика.
Шаблоны правил транслируются в семантические деревья, полно­стью совместимые с деревом программы. Параметры правил могут за­нимать место любого поддерева или деревьев нескольких последова­тельно идущих операторов. Логическое условие применимости транс­лируется в предикат на Прологе.
Пока в качестве входного языка возможен только Фортран.
2) Административный модуль доступа к абстрактным семантиче-
ским деревьям программы и образцов правил, обеспечивающий базовые
операции с деревьями и скрывающий реализующую их структуру данных.
3) База правил трансформации.
Таблица имен правил, их исходные тексты и совокупности семан­тических деревьев входного и выходного шаблона и предиката условия применимости.
Набор имеющихся схемных правил включает традиционные пре­образования нормализации, оптимизации и распараллеливания [4].
4) Синтаксический анализатор со сканером языка сценариев и со-
ответствующая грамматика.
Макет МСТП может функционировать в автоматическом режиме: выполнение трансформаций происходит согласно сценарию примене­ния правил [3]. В интерактивном режиме пользователю предлагаются возможные варианты преобразований и по его команде применяются указанные им правила.
Язык сценариев является подмножеством языка С и включает операторы циклов, условные операторы, описания переменных и опера­торы применения правил трансформации. Оператор apply_once означа­ет применение правила к первой сопоставимой конструкции внутри программы или программной конструкции-аргумента, apply - примене­ние правила до исчерпания возможности, apply_set - асинхронное применение независимого набора правил [5].
Сценарий транслируется в предикат на Прологе с тем же именем, что и сценарий.
5) Хранилище сценариев.
К каждому сценарию прилагается список вызываемых правил.
6) Переменные среды системы.
Определяют среду выполнения программы (целевую архитектуру, класс задач и другие требования к выходной программе).
7) Синтаксический анализатор со сканером и грамматика для
фильтров правил и сценариев их применения.
Для гибкой настройки на внешние условия набор преобразований и сценариев их применения может быть сужен с помощью логических условий фильтрации правил трансформации [6].
Фильтры содержатся в базе Пролога в виде ограничений (constraints).
8) Машина вывода, формирующая множество допустимых правил
и сценариев их применения.
9) Модуль вычисления зависимостей по данным.
10) Модуль со встроенными предикатами
Трансформационная машина, реализующая процесс поиска сопоставимых фрагментов и замены в семантических деревьях про­граммы.
Генератор текста на выходном языке по абстрактному дереву программы.
13) Модуль для диалогового применения трансформаций.
Демонстрирует допускающие преобразование фрагменты про­граммы и принимает от пользователя инструкции по запуску трансфор­маций для указанных им синтаксических конструкций.
Пользователь вызывает функции системы из оболочки.
В качестве редактора исходных текстов правил, сценариев их применения и фильтров правил и сценариев предполагается использо­вание внешнего простейшего текстового редактора.
4. Особенности работы трансформационной машины
Для унификации данных различных типов (семантических деревь­ев, арифметических выражений и отдельных вхождений переменных) система использует нестандартные алгоритмы, учитывающие специфи­ку данных и обладающие большей функциональностью и эффективно­стью, чем встроенный в систему универсальный алгоритм унификации.
5. Пример работы экспериментальной системы распараллеливания
Будем считать, что построены внутренние представлений правил и программы, и выбран набор классических преобразований распараллели­вания и оптимизации в Fortran77 с параллельными конструкциями. В данном примере рассмотрим автоматическое преобразование примера по следующему сценарию:
void classic () {
int i;
apply normalize; /* нормализация (стандартизация) циклов */ apply induct; /* удаление индуктивных переменных */ apply wraparound; /* удаление охватывающих переменных */ cr_dep; /* построение графа зависимостей по данным */ apply deadelimination /* удаление мертвых операторов */ apply_set(loop_fusion, loopdistribution); /* слияние и разбиение циклов*/
apply interchange; /* перестановка циклов */ apply unfold; /* развертка циклов*/
for (i=1; i< MaxNest; apply parallelize(M); /* распараллелива­ние циклов разной вложенности, начиная с самых внешних и кончая са­мым глубоким уровнем вложенности в программе */ }.
Преобразования на самом деле выполняются над внутренним
представлением, но здесь мы продемонстрируем текст, сгенерирован-
ный по дереву программы. Первый этап, нормализация цикла, нужна
для приведения цикла к стандартному виду, чтобы его счетчик изменял-
ся от 1 до целой верхней границы.
jj=0 jj=0
do 10 j=1,10,2 do 10 j_new_1=1,5
jj= jj + 1 jj= jj + 1
ii=0 ii=0
do 10 i=1,20,2 do 10 i_new_5=1,10
ii= ii + 1 ii= ii + 1
xx(ii,jj,1 )= x(iij, 1) xx(ii,jj ,1)= x(ii,2 * j_new_1 - 1,1)

xx(ii,jj,2)= x(iij,2) xx(ii,jj,2)= x(ii,2 * j_new_1 - 1,2)
10 continue 10 continue
jj=0 =$expr1
do 10 j_new_1=1,5 =$Ub jj= jj + 1 = $inc_expr ii=0
do 10 i_new_5=1,10 i = i_new_5 * 2 - 1 $sts2 ii= ii + 1
xx(ii,jj,1)= x(ii,2*j_new_1 - 1,1)
xx(ii,jj,2)= x(ii,2*j_new_1 - 1,2)
10 continue
Теперь избавимся от индуктивных переменных [4]. Для нахождения зависимостей по данным индексные выражения массивов должны зави­сеть только от счетчиков циклов. Рассмотрим подробнее процесс преобра­зования первого цикла: текст правила преобразования, найденные значе­ния его параметров и результат. rule induct1:
var <sts> sts1, sts2, <var> i, id,
<num_expr> Ub, Incexpr; $id = jj
<loop: L> ( do $i=1 to $Ub
$sts1 $i=j_new_1
<assign: S2> $id=$inc_expr $sts1=[]
$sts2
continue )| L
<before(L): S1> ($id =$expr1)
&& full_reachable_c(S1, loop) & lin-
ear(inc_expr, $id, 1, $b) & un- $b=1
changed_between($id, S1, S2) &
no_jumps(L) & $id_v=$b*($Ub)+ =1*5+0
($expr1) => ( <S1>() |
do $label $i =1 to $Ub
apply (($id => $b*($i-1) + ($expr1)),
$sts1)
apply (($id => $b*$i + ($expr1)), jj =>
$sts2) 1*j_new_1
$label: continue ) +0
$id = $id_v
end
do 10 j_new_1=1,5 do 10 i_new_5=1,10 xx(i_new_5, j_new_1,1)= =x(i_new_5, 2*j_new_1 -1,1) xx(i_new_5, j_new_1,2)= =x(i_new_5, 2*j_new_1 -1,2) 10 continue
jj=5
ii=10
Данное преобразование применяется, пока не останется индуктив­ных переменных.
do 10 j_new_1=1,5
ii=0
do 10 i_new_5=1,10 ii= ii + 1
xx(ii, j_new_1,1)= =x(i_new_5, 2*j_new_1 -1,1) xx(ii, j_new_1,2)= =x(i_new_5, 2*j_new_1 -1,2) 10 continue
jj=5
Теперь строим граф зависимостей по данным. Если значения ii и jj не используются, можно избавиться от лишних присваиваний. Итерации внутреннего цикла независимы и могут исполняться параллельно. Но, поскольку нет дуг зависимостей противоположных направлений по раз­ным счетчикам, можно выполнить перестановку внутреннего цикла на­ружу [4], а параллельное исполнение более длинного цикла выгоднее. В итоге получим следующий распараллеленный код:
doall 10 i_new_5=1,10
do 10 j_new_1=1,5
xx(i_new_5, j_new_1,1)= x(i_new_5, 2*j_new_1 -1,1) xx(i_new_5, j_new_1,2)= x(i_new_5, 2*j_new_1 -1,2) 10 continue
Макетная реализация МСТП осуществляется в Пролог-системе Eclipse. Частично используется (после портирования) код модулей рас­параллеливающего компилятора на Прологе [7], обеспечивающих по­строение внутренних представлений программы.
Развитие экспериментальной системы распараллеливания предпо­лагается в двух направлениях: во-первых, внедрение новых схематиче­ских преобразований и методик распараллеливания, во-вторых, разви­тие средств визуализации и диалога с пользователем макета МСТП.
Литература
Евстигнеев В.А., Спрогис СВ. Векторизация программ (обзор) // В сб. Векторизация программ: теория, методы, реализация. М., Мир, 1991. С.246-271.
Partsch H., Steinbruggen R. Program transformation systems // ACM Com­puter Survey, 1983. V. 15, № 3. P. 199-236.
Bukatov A.A. Building the Program Parallelization System Based on a Very Wide Spectrum Program Transformation System // Slot P.M.A. at al (Eds.) Interna­tional Conference on Computer Science 2003, Proceedings, Part II: Lecture Notes on Computer Science, vol. 2658, Berlin, Heidelberg, New York, Hong Kong, Lon­don, Milan, Paris, Tokyo: Springer, 2003. P. 945-954.
Жегуло О.А. Непроцедурное представление преобразований программ в системе поддержки распараллеливания // В сб. «Компьютерное моделирование. Вычислительные технологии», Ростов-на-Дону: изд-во ООО «ЦВВР», 2003. С. 27-40.
Букатов А.А., Коваль В.В. Методы реализации трансформационной ма­шины в многоцелевой системе преобразований программ // «Искусственный интеллект», журнал Института проблем искусственного интеллекта Нацио­нальной академии наук Украины, Донецк: Наука i освгга, 2003. №3. С. 6-14.
Жегуло О.А. Методы настройки трансформационной системы автома­тического распараллеливания программ на параметры условий применения // «Искусственный интеллект», журнал Института проблем искусственного ин­теллекта Национальной академии наук Украины, Донецк: Наука i освгга, 2003. №3. С. 88-94.
Адигеев М.Г., Дубров Д.В., Лазарева С.А., Штейнберг Б.Я. Экспери­ментальный распараллеливающий компилятор на Супер-ЭВМ со структурной реализацией вычислений // Фундаментальные и прикладные аспекты разра­ботки больших распределенных программных комплексов. Тезисы докладов всероссийской научной конференции. Новороссийск. 21-26.09.98. Москва: МГУ, 1998. С. 101-108.


О ПОДГОТОВКЕ СПЕЦИАЛИСТОВ ПО ПАРАЛЛЕЛЬНОМУ ПРОГРАММИРОВАНИЮ НА КАФЕДРЕ МАТЕМАТИЧЕСКОГО ОБЕСПЕЧЕНИЯ ВС ПГУ
Е.Б. Замятина, К.А. Осмехин
Пермский государственныйуниверситет, г. Пермь
Введение
В настоящее время роль многопроцессорных и распределенных вычислительных систем при обработке, хранении и передаче информа­ции существенно выросла. Поэтому подготовка специалистов в области системного программного обеспечения предполагает введение дисцип­лин, охватывающих область параллельных вычислений, а также парал­лельных и распределенных архитектур вычислительных систем. На ка­федре математического обеспечения вычислительных систем механико-математического факультета Пермского государственного университета читается ряд специальных курсов, посвященных этой тематике. К этим дисциплинам относятся:
Параллельные вычисления.
Параллельные архитектуры.
GRID.
Распределенные алгоритмы.
Современные компьютерные технологии.
Содержание курсов, связанных с параллельным программированием
Первые знания, связанные с построением и организацией вычисли­тельных систем с параллельной архитектурой студенты приобретают ещё на первом курсе обучения(1, 2 семестр), изучая курс «Информатика». В этом курсе студенты получают сведения об архитектуре ВС, в том числе сведения о ВС с параллельной архитектурой, классификацией ЭВМ по Флинну, с принципами параллельной и конвейерной обработки информации.
На втором курсе, изучая дисциплину «Системное прикладное про­граммное обеспечение», студенты рассматривают материал, связанный с синхронизацией параллельных процессов, вопросы обнаружения, пре­дотвращения тупиков и т.д.
Студенты приступают к изучению специального курса «Парал­лельное программирование» в восьмом семестре, прослушав к этому времени такие общие и специальные курсы, как «Дискретная математи­ка», «Теория графов», «Архитектура ЭВМ», «Языки программирования и методы трансляции», «Операционная система Unix», «Автоматизация проектирования ВС» и др.
Материал этих курсов позволяет студентам лучше усвоить новый материал, связанный с параллельным программированием.
Специальный курс «Параллельное программирование» включает три раздела:
Архитектурные принципы построения вычислительных систем с параллельной обработкой.
Математические схемы и методы анализа, отладки и тестирования параллельных и распределенных программ.
Языки и системы параллельного программирования.
Специальный курс «Параллельное программирование» начинается с изложения теоретических и прикладных проблем параллельного про­граммирования. В материале излагаются вопросы, в которых рассмат­ривается необходимость использования параллельного программирова­ния и пути увеличения эффективности его использования. Кроме того, рассматриваются проблемы, препятствующие широкому использова­нию параллельного программирования. Это-закон Амдаля, законы Мура и Гроша, потери, связанные с передачей данных, потери, зависящие от взаимодействия процессов, зависимость эффективности параллельных вычислений от используемой аппаратуры, сложность разработки парал­лельных алгоритмов, проблемы отладки параллельных алгоритмов.
Вслед за этим студенты изучают принципы построения ЭВМ с па­раллельной архитектурой. На лекциях рассматриваются архитектуры ЭВМ с общей и распределенной памятью, различные схемы коммута­ции, приводятся сведения о различных классификациях многопроцес­сорных ВС (классификация по Флинну, Шору и т.д.), кратко излагаются вопросы организации транспьютеров, кластеров, приводятся примеры конкретных ВС. Внимание уделяется и потоковым ЭВМ. Здесь же рас­сматриваются различные схемы коммутации, типовые топологии (коль­цо, шина, гиперкуб и т.д.), их преимущества и недостатки.
Затем студентам предлагается познакомиться с двумя основными парадигмами параллельного программирования - с параллелизмом дан­ных и параллелизмом задач.
Далее рассматриваются такие вопросы, как декомпозиция алгорит­ма на параллельно исполняемы фрагменты, распределение заданий по процессорам, вопросы балансировки, синхронизации и взаимоисключе­ния, организация взаимодействия параллельных процессов. Как уже го­ворилось ранее, с некоторым механизмами синхронизации (критические секции, семафоры) и проблемами тупиков, студенты знакомятся ещё в курсе «Системное прикладное программное обеспечение» (3, 4 семест­ры). В этом курсе их знания углубляются, в частности, они получают представления о таких механизмах, как мониторы, рандеву, барьеры.
При изложении этого материала студенты знакомятся с конкрет­ными примерами создания параллельных алгоритмов при решении та­ких простых задач, как умножение матрицы на вектор, перемножение двух матриц и т.д.
В курсе рассматриваются вопросы реализации этих и более слож­ных параллельных алгоритмов на многопроцессорной ВС той или иной топологии, анализируется эффективность выполнения параллельных ал­горитмов с учетом топологии вычислительной среды.
В разделе «Математические схемы и методы анализа, отладки и тестирования параллельных и распределенных программ» студенты знакомятся с такими известными математическими схемами и методами анализа параллельных и распределенных программ, как схемы Карпа-Миллера, сети Петри , ит.д. При изложении материала, связанного с се­тями Петри, студенты рассматривают проблемы решения задач «Чита­тели-писатели», «О пяти философах» и т.д..
В этом же разделе изучаются вопросы, связанные с характерными особенностями отладки и тестирования параллельных программ.
В разделе языки и системы параллельного программирования студен­ты изучают язык АДА, язык ОККАМ. Далее студенты знакомятся с пото­ковыми языками, расширениями языков и, наконец, приступают к изуче­нию системы программирования MPI. Кроме того, излагается материал, связанный с другими системами параллельного программирования (PVM, например, Т-система, система программирования НОРМА). При изучении языков программирования АДА и системы параллельного программирова­ния MPI студентам предлагается разработать параллельный алгоритм для решения поставленной перед ним задачи, оценить его эффективность и реализовать алгоритм: написать программу на языке АДА и программу, с использованием системы параллельного программирования MPI.
В этом же разделе рассматривается вопросы построения оптимизи­рующих компиляторов, вопросы векторизации и конкуррентизации циклов.
На семинарских занятиях обсуждаются вопросы, которые не во­шли в лекционный материал, студенты выступают с докладами (приме­ром может служить вопрос организации параллельных баз данных и др.). Материалами для обсуждения являются материалы из Internet (в основном это материалы портала www.parallel.ru, журнала «Програм­мирование»).
Специальный курс «Параллельные архитектуры» введен с 2003 года для студентов-магистрантов первого года обучения. В этом курсе студенты изучают в основном вычислительной системы кластерной ар­хитектуры.
В курсе приводится классификация ВС с кластерной архитекту­рой, рассматриваются архитектурные принципы организации МВС-
1000.
Далее студенты изучают вопросы, связанные с аппаратным и про­граммным обеспечением ВС с кластерной архитектурой, а именно, во­просы, связанные с выбором рабочей станции, коммуникационного компонента, операционной системы и т.д..
В специальном курсе «GRID» (магистры 1 года обучения) студенты знакомятся с современным положением дел, связанных с развитием Grid-технологий и метакомпьютинга, рассматривают различные стратегии по­строения метакомпьютера и организации вычислений в этой среде.
Специальный курс «Распределённые алгоритмы» направлен на уг­лубление знаний распределенной и параллельной обработки информа­ции, подробно изучаются распределённые алгоритмы, в том числе, ал­горитмы маршрутизации, волновых алгоритмы, алгоритмы обхода, вы­бора и т.д.
В общем курсе «Современные компьютерные технологии», мате­риал которого предназначен для изучения студентами-магистрами 2 го­да обучения, студенты подробно знакомятся ещё с одной системой па­раллельного программирования. А именно, с системой программирова­ния PVM. Курс включает четыре раздела, одним из которых является материал, связанный с распознаванием образов. В частности, в этом разделе затрагивается вопрос распознавания образов с помощью ней­ронных сетей. Студентам предлагается реализовать трехслойный пер-септрон (с использованием системы параллельного программирования MPI), предназначенный для распознавания символов. При этом оцени­вается эффективность разработанного алгоритма.
Заключение
В настоящее время на механико-математическом факультете Перм­ского государственного университета функционирует кластер, используя вычислительные средства которого студенты выполняют свои индивиду­альные задания. Наряду с этим, студентами выполняются курсовые, ди­пломные и магистерские работы. Так несколько студентов заняты созда­нием программных средств для отладки параллельных программ, а ряд других участвует в разработке параллельной системы имитационного мо­делирования. Ведутся также исследования в области моделирования пове­дения параллельных программ с целью обнаружения в них ошибок.
РЕГИОНАЛЬНЫЙ НАУЧНО-ОБРАЗОВАТЕЛЬНЫЙ КОМПЛЕКС ВЫСОКОПРОИЗВОДИТЕЛЬНЫХВЫЧИСЛЕНИЙ

С.А. Запрягаев, С.Д. Кургалин
Воронежский государственный университет, г. Воронеж
В 2002 г. на кафедре цифровых технологий Воронежского госу­дарственного университета (ВГУ) при поддержке гранта VZ-010 Фонда CRDF создан 20-процессорный высокопроизводительный вычислитель­ный кластер с пиковой производительностью 28 Gflops.
Работа кластера существенно увеличила возможности компьютерно­го моделирования сложных процессов и систем при проведении ресурсо­емких расчетов. Оборудование кластера и телекоммуникационные уст­ройства сформировали лабораторию высокопроизводительных вычисле­ний ВГУ, которая включена в региональную информационно-образовательную среду, созданную на базе Воронежского университета, и открывшую новые перспективы для проведения научных исследований.
Лаборатория высокопроизводительных вычислений интегрирована с лабораторией дистанционного образования ВГУ высокоскоростными оп­товолоконными каналами доступа к их ресурсам. На их совместной базе организован универсальный научно-образовательный комплекс, в котором ведутся учебные занятия, проходят научные семинары, а также разраба­тывается программное обеспечение для моделирования с использованием возможностей компьютерного кластера.
В последние годы высокопроизводительные вычислительные кла­стеры получают все большее распространение и используются для ком­пьютерного моделирования при решении задач на приоритетных науч­ных направлениях. Решение ряда актуальных задач не всегда может быть проведено на традиционных последовательных компьютерах из-за экспоненциально большого времени выполнения программ, поэтому использование компьютерных кластеров часто становиться единствен­ной возможностью получения новых научных результатов. Построение и дальнейшее изучение математических моделей дает возможность, с одной стороны, исследовать сложные физические, химические и биоло­гические процессы и явления, а, с другой стороны, широкое применение современных методов математического моделирования позволяет по-новому подойти и к решению многих традиционных задач.
Комплекс последовательных программ для анализа сложных реаль­но протекающих процессов на традиционных компьютерах не обеспечи­вает необходимых объемов моделирования, и проведения полного цикла расчетов из-за существенного возрастания времени вычислений с ростом числа входных параметров или данных и не позволяет получить желаемый результат за приемлемое время. Этим вызывается необходимость приме­нения вычислительных систем с использованием алгоритмов распаралле­ливания процессов. При реализации конкретных вычислений распаралле­ливание осуществляется как на основе известных алгоритмов, так и на ба­зе вновь разрабатываемых процедур для обеспечения эффективной работы конкретной параллельной программы в среде MPICH 1.2.5.
Для дистанционного доступа по сети Интернет к вычислительным ресурсам кластера на базе программного обеспечения Microsoft Internet Information Service создан специализированный Web-сервер. Его интер­фейс разработан на основе технологии Active Server Pages на языке Java Script. Зарегистрированным пользователям предоставляется возможность размещать через Web-браузер для выполнения на кластере свои програм­мы, созданные в среде Microsoft Visual Fortran, а также дистанционно компилировать и исполнять их. Результаты работы программы перено­сятся на компьютер пользователя средствами Web-браузера.
Объединение параллельного кластера и образовательного Интер­нет-портала «Voronezh.OpeNet.ru» создало условия для проведения слож­ных вычислительных экспериментов в учебных целях. Осуществляемые вычислительные эксперименты ориентируются не только на проведение расчетов по существующим методикам и компьютерное моделирование, но и на поиск пределов применимости расчетных методов, проверку эф­фективности алгоритмов и достоверности полученных результатов.
Использование высокопроизводительного вычислительного кла­стера позволяет продвинуться вперед в решении ряда задач и приобре­сти опыт разработки параллельных алгоритмов и программ, необходи­мых для применения новых методов компьютерного моделирования в различных направлениях исследований, а также включить комплекс в европейский проект EGEE создания глобальной вычислительной ин­фраструктуры для науки и высоких технологий.


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

И.И. Захарчук
Военно-космическая академия им. А.Ф. Можайского
Известные модели параллельной сортировки на линейных сетях [1] основаны на PRAM-модели (parallel random access memory) вычис­лений. Особенностью такой модели является общая память параллель­ных процессоров, доступ к которой происходит в конкурентном и (или исключительном режимах чтения) записи. Такая модель не отвечает требованиям предельной параллельности в работе (наличие общего ре­сурса), локальности связей и однородности структуры, которые харак­терны для кластерных систем.
В качестве вычислительной модели, лишенной указанных недос­татков, может быть клеточный автомат - бесконечная сеть одинаковых автоматов Мура, расположенных в точках пространства с целочислен­ными координатами, связанных одинаковым образом друг с другом и изменяющих состояние в зависимости от состояния соседей и своего собственного.
Формально клеточный автомат K есть упорядоченное множество из четырех компонент
к=< zd, n , е,Ф>,
где Zd - множество d -мерных векторов с целочисленными координа­тами - клеточное пространство;
N - конечное множество мощности m векторов из Zd:
N = {щ\щ = (xu—xdi X $ni = 0Ki = m
с нулевым вектором - шаблон соседства клеточного автомата;
Q - конечное множество мощности к состояний клетки c выде­ленным состоянием покоя 0 - алфавит клеточного автомата;
Ф - локальная функция переходов, определенная на множестве
элементов окрестности в дискретные моменты времени
Ф : Qm ® Q,
Ф :(0 0,01,..., 0 m-1) = 0 .
Состояния всех клеток на момент времени t образуют текущую конфигурацию ct:
ct : Zd ® Q.
Применение локальной функции переходов к текущей конфигура­ции cj задает глобальную функцию переходов g(c):

g : cj ® cj +1.
Упорядоченная совокупность конфигураций, получаемая из на­чальной последовательным применением глобальной функции перехо­дов, образует эволюцию e клеточного автомата
e = <С0,c1,...,cT>,e е E.
В процессе исследований клеточных автоматов сформировались две задачи. В первой задаче задан клеточный автомат и законы его функционирования. Требуется определить состояние каждого элемента после определенного количества тактов (под одним тактом подразуме­вается один процесс перехода элементов из старого состояния в новое согласно законам данного клеточного автомата). Вторая задача является обратной первой. Есть клеточный автомат и задано первоначальное и конечное состояние системы, к которому необходимо прийти в резуль­тате выполнения конечного числа тактов. Требуется найти законы, по которым элементы системы будут изменять свое состояние.
Примером здесь может служить ставшая уже классической извест­ная задача о синхронизации цепи стрелков (firing squad synchronization problem - FSSP), предложенная Дж. Майхиллом. В терминах клеточных автоматов задача может быть формализована так: синтезировать одномер­ный клеточный автомат с тремя соседними клетками, осуществляющий одновременный переход всех клеток в заключительную однородную кон­фигурацию (самосинхронизация). Эта задача являются частным примером общей задачи организации информационного обмена внутри однородной сети с локальными связями и децентрализованным управлением.
В настоящем докладе представлено одно из решений другой част­ной задачи. Эта задача в биологической постановке и без ограничений в локальности связей и однородности структуры известна как модель кле­точной дифференциации Вольперта - задача о французском флаге (French flag problem -FFP), или как задача о сортировке Дайкстры - за­дача о датском флаге (Dutch national flag problem) [2]. Отличие от задачи Майхилла заключается в том, что начальное состояние клетки - одно из множества красок: «красной», «синей», «белой». Распределение красок в начальный момент - произвольное. Требуется установить в финаль­ном состоянии конфигурацию французского флага.
Клеточный автомат, в данной постановке задачи, представляет со­бой строку - одномерный клеточный автомат, элементы которого распо­ложены последовательно один за другим. Задача решена для любого ко­личества логических состояний элемента системы. Время решения ли­нейно зависит от числа непустых элементов клеточного автомата (длины активной зоны клеточного автомата) и числа возможных состояний.
Ниже приводится RAM-модель (программа на языке C++), кото­рая моделирует работу клеточного автомата, используя разработанный алгоритм.
Так как в клеточном автомате все состояния меняются одновре­менно (клетки работают параллельно), а процессор в RAM-модели мо­жет выполнять команды программы только последовательно, то были созданы два массива a[n] и b[n], где a[n] - старые состояния клеток, b[n] - новые, n - число клеток. Также был введен массив флагов и двух бу­ферных массива forleft[n] и forright[n].
Конкретизируем задачу: пусть существует пять типов клеток (1,2,3,4,5). Первоначально состояния каждой клетки клеточного были за­даны случайным образом. Требуется отсортировать клетки таким образом, чтобы они располагались слева направо по возрастанию своих номеров.
Действие алгоритма основано на том, что если a[i-1] > a[i], то a[i-1] присваивается значение a[i] и наоборот a[i] присваивается значение a[i-1]. Таким образом, состояния клеток «бегут» так, что «большие» со­стояния «бегут» вправо, а «меньшие - влево».
Трудности возникают, когда состояния непрерывно и последова­тельно расположены в обратном порядке, например 5-4-3-1 или 5-3-2-1. В этом случае невозможно определить, руководствуясь вышеизложен­ным правилом, состояния элементов 4 и 3 в первом приведенном при­мере и 3 и 2 - во втором.
Для преодоления этой трудности, весь «проблемный» блок клеток изолируется от других элементов клеточного автомата посредством флагов (flag[n]). Блок делится на логические элементы по три клетки, состояния крайних двух клеток запоминаются в буфере forlen"[n] и for-right[n] и в следующем такте происходит обмен «крайними» состояния­ми, после чего «изоляция» снимается.
#include <iostream.h>
int a[n],b[n],flag[n],forleft[n],forright[n],i;
void main()
{
for (i=1,i=n,i++) cin>>a[i]; st: for (i=1,i=n,i++)
{
if a[i-1]>a[i] & a[i]>a[i+1] then
{
forleft[i]=a[i+1];
forright[i]=a[i-1];
flag[i]=2;
}
}for (i=1,i=n,i++)
{
if a[i-1]>a[i] & a[i]<a[i+1] & flag[i-2]=0 & flag[i+1]=0 & flag[i-1]=0
& flag[i] =0 then b[i]=a[i-1];
if a[i-1]<a[i] & a[i]>a[i+1] & flag[i-2]=0 & flag[i+1]=0 & flag[i-1]=0
& flag[i] =0 then b[i]=a[i+1];
}
for (i=1,i=n,i++)
{
if flag[i]=2 & flag[i-2]!=0 then
{
flag[i]=1;
forleft[i]=0;
forright[i]=0;
} }
for (i=1,i=n,i++)

стр. 1
(всего 4)

СОДЕРЖАНИЕ

>>