<<

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

СОДЕРЖАНИЕ

>>

При выбранном в рамках КА-технологии методе интерпретации автоматов является принципиальным отделение множества операторов программы от ее управления. Это полностью соответствует формально­му определению программы в виде так называемой схемы програм­мы^], где программа представлена тройкой - память, операторы, управление. Такое представление удобно и для реализации выбранного способа интерпретации автоматов. Оно же оказывает сильное влияние на содержание дальнейших этапов разработки программ.
Кроме того, применение ООП и метода интерпретации автоматов позволяют достичь уровня абстракции, когда кодирование требует зна­ний, связанных только с самой автоматной моделью, но не с особенно­стью ее реализации.
Таким образом, кодирование автоматов в рамках КА-технологии основано на введении понятия динамичного объекта, когда любой объект может быть наделен алгоритмом поведения во времени. Алгоритм поведения объекта задается моделью конечного автомата. Язык описания автомата основан на табличной форме представления автоматов. Логика поведения объекта (таблица переходов автомата) от­делена от методов автоматного объекта (предикатов и действий), свя­занных с реализацией его поведения во времени. Любые динамичные объекты могут выполняться параллельно.
Тестирование
После этапа кодирования приступают к процедуре тестирования отдельной программы и проекта в целом. Считается, что стоимость вы­явления ошибки на этапе кодирования в два раза выше, чем на этапе проектирования, а ее обнаружение при тестировании обходится уже в 10 раз дороже.
Ошибки, к сожалению, есть всегда. Теория конечных автоматов определяет более высокий уровень защиты от ошибок уже на стадии проектирования. Существуют математические приемы, позволяющие не только проверить корректность алгоритма, но и применить к нему фор­мальные операции - умножение, деление и т.п. для синтеза и анализа но­вых алгоритмов из уже проверенных.
В рамках КА-технологии применимы приемы тестирования и отладки, которые зачастую невозможны при других подходах. От­деление множества операторов от управления КА-программы позволяет проводить их независимый анализ. Можно легко строить и модифици­ровать логику работы программы на множестве ее операторов, проводя эксперименты чисто с логикой программы. Можно даже использовать одну уже проверенную и отлаженную логику (управление) в разных программах/объектах, т.е. наследовать алгоритм по аналогии с насле­дованием методов или данных в ООП.
Работу КА-программы легко отслеживать с помощью понятия со­стояния конечно-автоматного управления КА-программы. Множество таких состояний отражают состояние всей системы в целом. Тем самым легко выявляются точки зацикливания и/или некорректной работы, как отдельной подсистемы/подсистем, так и всей системы. При этом ошиб­ки КА-программы сосредоточены в ее четко определенных структурных компонентах - предикатах, действиях или управлении.
В расширение методов проектирования программных систем свойства базовой автоматной модели позволяют использовать зареко­мендовавшие себя формальные математические методы и другие эф­фективные методы проектирования и тестирования из теории и практи­ки проектирования аппаратных средств.
Эксплуатация и сопровождение
Удачно разработанные проекты «живут» долго. При этом их сопро­вождением и эксплуатацией занимаются часто специалисты, не участво­вавшие в их разработке. Для этого им нужна эксплутационная докумен­тация. Но если через некоторое время даже сам программист может с трудом разобраться в своей программе, то понятно, насколько сложен процесс сопровождения другими лицами.
Самым точным источником информации о программе является листинг. С листингом КА-программ работать очень легко, т.к. отделе­ние логики программы (управления) от ее операторов делает ее «самодокументируемой». Это свойство позволяет быстро и точно вос­становить алгоритм работы программы/объекта. Тот, кто хоть раз пы­тался построить по листингу программы ее блок-схему, знает о сложно­сти такой процедуры.
Модель КА обобщает такие методы разработки программ, как таблицы решений и программирование с использованием переменной состояния. Эти методы удобны и эффективны не только для разработки программ, но и для последующего их сопровождения. Они часто пред­лагаются в качестве подходов, расширяющих возможности блок-схем.
Примеры применения
Автоматная модель и ее параллельный вариант - это универсальная алгоритмическая модель, пригодная для применения в любой прикладной области. На текущий момент она реализована в форме DLL библиотеки (см. [4]). Микроядро или, другими словами, виртуальная КА-машина, вы­полняет функции интерпретации модели КА, реализует параллельную ра­боту компонент, управляя их запуском, синхронизацией и т.п. Разработан­ные на языке С++ средства описания автоматов расширяют объектные возможности языка, реализуя динамическую работу классов.
Прикладные области, где проходила «обкатку» данная параллель­ная модель и ее технология, достаточно разнообразны. Их диапазон - от простых в алгоритмическом плане бухгалтерских программ типа расчета заработной платы до сложных проектов типа системы управления техно­логическим процессом выращивания кристаллов с множеством динами­чески порождаемых параллельно функционирующих объектов. Послед­ние реализуют процессы съема данных с датчиков, выдачу управляющих воздействий на объект и автоматные алгоритмы работы драйверов с раз­нообразной аппаратурой, а также процессы отображения и расчета.
Одна из сложных областей эффективного применения КА - игры. Другая предметная область такого же класса - системы управления и/или функционирования в реальном времени. В этих областях в полной мере присутствуют элементы, которые сложно реализовать при обычных под­ходах. Это, прежде всего, параллельный характер работы составных час­тей системы и их синхронизация в реальном времени. В основу решения данных задач положена концепция микроядра, которое реализует парал­лельные механизмы среды функционирования процессов.
Еще раз подчеркнем, что КА-технология хорошо подходит для ра­боты в реальном времени. Реализованный проект системы управления технологическим процессом обеспечивает реакцию системы в пределах 0.01 сек (можно обеспечить и лучшую) в среде Windows. Это не хуже, чем гарантируют специализированные системы такого же типа.
Выводы
Чем сложнее проект, тем эффективнее применение конечно-автоматной модели. КА-технология решает проблемы структурного и алгоритмического проектирования систем. Она органична для любой прикладной области и потому может быть легко внедрена всюду. Это аналогично распространению ООП на достаточно специализированные прикладные области и системы программирования.
КА-технология позволяет внедрить весьма эффективные матема­тические методы разработки, тестирования и отладки программ. Авто­матная модель стандартизирует процесс разработки, соединяя в себе наиболее общие подходы проектирования программ, которые в малой степени зависят от способа их дальнейшей реализации.
Табличное представление КА легко реализовать аппаратно, что позволяет говорить уже не об интерпретации, а о прямой реализации ав­томатов. И хотя метод интерпретации снижает скорость работы про­граммы, современный уровень развития аппаратных средств практиче­ски снимает эту проблему. В то же время аппаратная реализация - пер­спективное направление, которое определяет новые архитектурные принципы построения вычислительных систем. Реально значительное увеличение быстродействия аппаратных средств.
КА-технология - параллельная технология. Параллельное решение по структуре проще последовательного. Такую структуру легче изме­нять, т.к. затрагиваются компоненты, которые в достаточной степени не­зависимы. Сопровождение и эксплуатация параллельной системы также гораздо проще и дешевле.
Автоматная модель наделяет объекты динамическими свойствами. Это расширяет возможности технологии ООП, устраняя один из основ­ных ее недостатков. Включение в описание класса алгоритма его рабо­ты во времени делает это описание действительно всеобъемлющим. По­ка же вопросы динамики работы объектов в ООП выходят за рамки оп­ределения классов.
Отделение управления от операторов программы позволяет созда­вать совершенно уникальный тип библиотек - библиотеки алгоритмов. Создание коллекций, будь то библиотеки программ, объектов, шабло­нов и т.д. и т.п., обычно создает хорошие предпосылки для развития технологий. По крайней мере, об этой возможности нужно знать, а реа­лизация и механизмы ее применения во многом могут быть аналогичны уже существующим.
Литература
1. Питерсон Дж. Теория сетей Петри и моделирование систем // Пер. с англ. - М.: Мир, 1984. - 264с.
Юдицкий СЛ., Магергут В.З. Логическое управление дискретными про­цессами // Модели, анализ, синтез: - М.: Машиностроение, 1987. - 176.: ил.
Рамбо Дж., Якобсон А., Буч Г. UML: специальный справочник // -СПб.: Питер, 2002. - 656 с.
Любченко B.C. От машины Тьюринга к машине Мили // «Мир ПК», 2002. №8. http://www.osp.ru/pcworld/2002/08/130.htm
Любченко B.C. О бильярде с Microsoft C++ 5.0 // «Мир ПК», 1998. № 1. С. 202-206.
Любченко B.C. Новые песни о главном (римейк для программистов). «Мир ПК», 1998. № 6. С. 114-119.
Буч Г. Объектно-ориентированное проектирование с примерами применения // Пер. с англ. - М.: Конкорд, 1992. - 519 с.
Шлеер С, Меллор С. Объектно-ориентированный анализ: моделирова­ние мира в состояниях:// Пер. с англ. - Киев: Диалектика, 1993. - 240 с.
Баранов СИ. Синтез микропрограммных автоматов // Л.: Энергия, 1979. - 232 с.
10. Любченко B.C. Автоматные схемы программ (с исторической ремар-
кой автора). http://www.softcraft.ru/auto/ka/ash/ash.shtml


К РЕШЕНИЮ ПРОБЛЕМЫ ОБЕДАЮЩИХ ФИЛОСОФОВ ДЕЙКСТРЫ

B.C. Любченко
ООО Специальное конструкторское бюро «Локальные автоматизированные системы», г. Новочеркасск
Введение
В [1] приведено решение задачи Дейкстры и описана модель фи­лософа. Чтобы в ней исключить тупики, нужно попытаться или совсем устранить переходы, ведущие в соответствующее состояния, или хотя бы попытаться уменьшить их число, а циклы, порождающие тупики, желательно «разорвать». В этих целях мы далее 1) внесем изменения в поведение компонентов системы и в их связи между собой, 2) после ка­ждого изменения «вычислим» новое поведение системы, 3) проведем анализ нового поведения системы.
Цель данной работы - демонстрация математического аппарата точного расчета поведения сложных систем. Приложение его к задаче Дейкстры, как мы увидим, позволяет строго доказать наличие тупиков в ней, выявить их причину, а уж затем внести коррективы в поведение элементов системы.
Подобные результаты для данной задачи получены, пожалуй, впервые, т.к. известные решения часто ограничиваются лишь общими рассуждениями о возможных тупиках и подходах к их устранению.
Не спеши, если сам не готов, или ... модель «умного» слуги!
Из анализа модели слуги (см. рис. 8, 9 в [1]) и эквивалентной мо­дели философа (рис. 10 в [1]) следует, что он может попросить вилку у соседа даже в том случае, когда его вилка отдана другому. Логичнее же просить вилку когда, когда своя вилка не занята. Признак ее свободы -состояние ps (см. рис.7 [1]). И если ранее было: слуга переходит из со­стояний f1 в состояние f2 сразу при поступлении сигнала «хочу есть» (x5=1) от философа, то теперь синхронизируем этот переход с состояни­ем ps модели вилки.
Дополним модель слуги входным каналом - x8. По нему будет по­ступать информация о внутреннем состоянии ps вилки. Теперь аналити­ческая форма автомата слуги может иметь следующий вид:
F:
f1 = (/2(x5x8/-)} (1)
f2 = f1(x6x7/y1)}.
При этом дополнение автомата F - автомат AF, который нам будет необходим для вычисления эквивалентного автомата системы, будет следующим:
AF:
f1 = {f1(Ax5x8/-),f1(x5Ax8/-),f1(Ax5Ax8/-)} = {f1(Ax5/-),f 1(x5Ax8/-)}, (2)
f 2 = {f 2(Ax6/-), f 2(Ax7/-)}.
Сетевая модель блока «философ/вилка» - первое решение
Сетевая модель философа, отражающая новое поведение слуги, будет следующей: P:
ps = {pl(f 2/-), prf 1x2/-)},
pl = {ps(f 1/-)}, (3)
pr = {ps(x1/-)}.
F:
f 1 = { f 2(psx5/-)}, (4)
f2 = {f 1(plx6/y1)}.
Здесь переменной x8 соответствует состояние ps, а ее отрицанию -состояние pl. При этом дополнения компонентных автоматов P и F будут следующими:
AP:
ps = {ps(f1Ax2/-)}, (5)
pl = {pl(f 2/-)}, pr = { pr(Ax1/-)}.
AF:
f 1 = { f 1(psAx5/-), f 1(plx5/-), f 1(prx5/-)}, (6)
f 2 = {f 2(pr/-), f 2(ps/-), f 2(Ax6/-)}.
Вычислим эквивалентный автомат M1, определяющий новое по­ведение системы - отдельного философа, где:
M1 = P®F = PxAFuApxFuPxF,
В результате (опустив промежуточные вычисления) автомат М будет следующим:
M1:
psf1 = {pf1(x2Ax5/-), psf2(Ax2x5/-), prf2(x2x5/-)}, (7)
psf2 = {plf2(-/-)},
plf1 = {psf1(Ax5/-)},
plf2 = {plf1(x6/y1)},
prf1 = {psf1(x1/-)},
prf2 = {psf2(x1/-)}.
Граф автомата M1 показан нарис. 1.

Рис. 7. автоматам!
Видно, что поведение философа изменилось и в автомате стало меньше переходов в состояние «r2» (напомним, что оно может быть причиной тупика). Хотя нам и не удалось совсем исключить попадание в него. Исчез переход между состояния в «s2»! Это один из перехо­дов цикла, определяющего поведение очень жадного до еды философа. Причина также не устранена совсем, но длина цикла увеличилась. Те­перь «жадность» философа ограничена тем, что после поглощения оче­редной порции спагетти он должен отказаться на какое-то время от еды (x5=0). За это время его голодный сосед, который ждет освобождения вилки, возможно, успеет ее «умыкнуть».
Поешь сам, а потом помоги соседу
Из анализа сетевой модели следует, что вилка может быть отдана соседу и в тот момент, когда сам философ запросил есть. Это видно из следующего. Пусть слуга находится в состоянии f1 и его вилка свобод­на. Если в какой-то момент приходит запрос от соседа дать ему вилку (x2=1), то она будет отдана, если даже если в этот же самый момент появится сигнал «хочу есть» (x5=1). Произойдет это потому, что слуге нужен будет один такт, чтобы перейти в состояние f2, которое перево­дит вилку из состояния ps в состояние pl. Но вилка-то будет в этот мо­мент в состоянии pr, т.к. она уже взята соседом на предыдущем такте работы вилки.
В эквивалентной модели (7) этот момент отражает состояние r2, в которое автомат перейдет из состояния s1. Но состояние r2 - это со­стояние возможного тупика: из него философ не выйдет до тех пор, по­ка сосед не вернет ему вилку (пока x1 не примет значение истинно). Но сосед в это время тоже может ждать уже свою вилку, которую он точно также до этого в такой же ситуации мог опрометчиво отдать.
Такую ситуацию можно исключить, если разрешить отдавать свою вилку только в том, случае, когда ее владелец не голоден, т.е. только при x5=0. Но для этого нужно добавить в модель вилки еще один вход­ной канал. А раз уж мы ввели в модель вилки сигнал «хочу есть» - x5, то это повлечет за собой изменение условия перехода из состояния ps в pl. Уберем синхронизацию с состоянием f2 слуги (x4), а разрешим взять вилку, если x5=1. С одной стороны это равносильно, т.к. и состояние f2 философа и сигнал x5 соответствуют желанию философа поесть. Но есть и отличие: сигнал x5 примет раньше истинное значение, чем сигнал x4 (переход слуги в состояние f2). В результате вилка будет выделена быстрее.
Модель вилки, которая больше любит своего философа, следую­щая:
P:

ps
pl
{pl(x5/-), pr(x2Ax4Ax5/-)}, {ps(x3/-)}, pr = {ps(x1/-)}.
(8)


Теперь вилка перейдет из состояния ps в состояние pl сразу при получении сигнала от своего философа «хочу есть». Это более «незави­симая» вилка, т.к. меньше связана с поведением слуги. Сосед не сможет забрать вилку до тех пор, пока «свой» философ не будет накормлен.
Сетевая модель блока «философ/вилка»
Сетевая модель, отражающая еще одно поведение вилки будет сле­дующей: P:
ps = {pl(x5/-), рг(х2лх5Д/-)},
pl = {ps(f\/-)}, (9)
pr = {ps(x\l-)}.

F:
fl = {f2(x5psl-)}, (10)
f2 = {f1(x6plly1)}.
Дополнения компонентных автоматов сети примут следующий
вид:

ps = ^(Лх2лх5!-), ps^x5f2l-)}, (11)
pl = {plf2l-)}, pr = {prCx1l-)}.

f1 = {f1(pll-), fl(prl-), f1Cx5l-)}, (12)
f2 = {f2(psl-), f2(prl-), f2Cx6l-)}.
Эквивалентный автомат M2, определяющий новое поведение сис­темы, будет следующим:
M2 = P0F = РхЛБ и лрхБ u PxF:
psf1 = {prf1(x2Лx5l-), plf2(x5l-)}, (13)
psf2 = {plf2(x5l-)}, plf1 = {psf1(-l-)}, plf2 = {plf1(x6ly1)}, prf1 = {psf1(x1l-)}, prf2 = {psf2(x1l-)}.
Графическая форма эквивалентного автомата представлена на рис. 2.
Введенные ограничения еще больше упростили поведение систе­мы: исключен переход из состояния s1 в r2, а переход из состояния s1 направлен сразу в состояние l2, а не в состояние s2, как было до этого (см. (7).
Теперь, во-первых, мы, наконец-то, избавились от перехода в одно из тупиковых состояний r2. И это существенное достижение. Вообще-то из результирующего автомата можно исключить переходы, связанные не только с состоянием r2, но и с состоянием s2, т.к. в него возможен переход только из состояния r2, которое мы собираемся исключить, т.е. в окончательном виде эквивалентный автомат будет следующим:
М3:
psfl = (prf1(x2Ax5/-), plf2(x5/-)}, (14)
plf1 = {psf1(-l-)}, pf2 = {plf1(x6ly1)}, pf1 = {psf1(x1l-)},
Формально состояния r2, s2 в системе все же есть, но в них, если мо­дели элементов системы функционируют в соответствии с заданным по­ведением, система не должна попасть. Но если по каким-то внешним при­чинам это все же случится, то из r2 система перейдет в s2, далее в 12 (см. граф М2), а уж потом все пойдет обычным путем. Главное, что и в этом случае будет выход из состояния r2.
Сравнение решений
Мы имеем три решения задачи. Первое решение представлено в [1], вторую модель представляет эквивалентный автомат (7), третью -(13). Первое решение дает большую свободу для компонентных моде­лей философа. Но оно же и наименее надежно, т.к. система имеет боль­где шансов попасть в тупиковые состояния или в циклы. И если строить эквивалентный автоматный граф для всей задачи, то он будет содержать в данном случае 65=7776 внутренних состояний, из которых какое-то число будут тупиковых.
Как минимум одно тупиковое состояние мы можем сразу назвать. Оно соответствует состояниям 12 всех пяти философов (его можно обо­значить как - 1212121212). Какие другие существуют комбинации тупико­вых состояния среди всего множества состояний системы дать ответ сложно. Можно лишь сказать, что их количество ограничено числом 35=243. В принципе можно разработать процедуру, которая, анализируя общий граф, определит, есть ли в нем состояния, соответствующие ком­бинации состояний из множества тупиковых состояний, и есть ли в них и из них переходы в другие состояния.
Эквивалентный граф для системы из автоматов (7) имеет то же число состояний. Единственное отличие - меньшее число переходов. Существенные отличия от двух предыдущих автоматов иметь автомат (13). Он формально тоже имеет это же число состояний, но среди них рабочих - 45=1024, из которых тупиковых состояний - одно! Это упо­мянутое выше 1212121212. Все философы не могут находиться одновре­менно в состоянии rl, а в остальных случаях в системе тупики возни­кать не должны. Эта модель сразу определяет множество состояний, в которые она, просто не должна попасть. Их число - 7776-1024=6752. Из этого видно соотношение между рабочими состояниями системы и ее возможными тупиковыми состояниями. Среди них истинно тупиковые ограничены числом - 243 (см. выше), а в остальные состояния система либо не попадет, либо найдет из них выход.
Выводы
Известно множество разных решений данной задачи. Из исполь­зованных базовых моделей, возможно, самые популярные сети Петри. Примером решения на базе другой модели служит решение, рассмот­ренное в [2]. Приведенное автоматное решение позволит с иных пози­ций взглянуть на проблемы реализации параллельных систем вообще и на вопросы применения автоматов для реализации параллелизма в част­ности. Как правило, понятие конечного автомата связывается только с последовательными процессами и мало используется при переходе к параллельным системам.
Действительно, конечный автомат, как модель отдельной компо­ненты, больше приспособлен для описания последовательного процес­са, хотя и на этом уровне у него есть возможности для задания паралле­лизма. Но, как видно, множество автоматов моделирует системы парал­лельного типа не хуже, чем специально разработанные для таких систем модели (например, те же сети Петри). Представленное решение задачи Дейкстры служит достаточно убедительным аргументом в пользу дан­ного высказывания.
Литература
1. Любченко B.C. Обедающие философы Дейкстры (о модели парал­лельных процессов) // http://www.softcraft.ru/auto/ka/fil/fil.shtml


ВЫЧИСЛИТЕЛЬНЫЙ КЛАСТЕР ВЦ РАН

Г.М. Михайлов1, М.А. Копытов1, Ю.П. Рогов1, A.M. Чернецов , А.И. Аветисян , О.И. Самоваров
1 Вычислительный центр имениА. А. Дородницына Российской академии наук (ВЦ РАН), г. Москва Институт Системного Программирования Российской академии наук (ИСПРАН)
Введение
Высокопроизводительный вычислительный кластер ВЦ РАН [1] был введен в эксплуатацию в 2003 г. Кластер построен на базе процес­соров Intel Xeon с использованием высокопроизводительной сетевой технологии Myrinet 2000. Кластер представляет собой единый вычисли­тельный комплекс коллективного пользования и предназначен для вы­полнения широкого класса параллельных программ.
Кластер ВЦ РАН спроектирован и построен в соответствии с
требованиями, предъявляемыми к архитектуре
высокопроизводительных кластерных вычислительных систем [2]. Вычислительные системы данной архитектуры позволяют эффективно решать параллельные задачи, характеризующиеся наличием интенсивных обменов данными в процессе вычислений.
В статье описывается системное программное обеспечение, уста­новленное на кластере ВЦ РАН, представлены результаты тестирования кластера, а также результаты и опыт эксплуатации кластера при реше­нии реальных прикладных задач.
Системное программное обеспечение
Системное программное обеспечение кластера строится на базе операционной системы Linux RedHat и системы управления кластера­ми OSCAR [3].
В состав OSCAR входят средства, позволяющие инсталлировать узлы кластера с общего, заранее настроенного образа операционной сис­темы, что обеспечивает однородность узлов кластера. Это так же позво­ляет легко модифицировать конфигурацию кластера, добавляя новые вы­числительные узлы, сохраняя при этом однородность настроек системно­го программного обеспечения. В случаях аппаратных или программных сбоев вычислительные узлы могут быть легко восстановлены.
В состав OSCAR также входит набор утилит, обеспечивающих управление и администрирование кластера.
Так же в состав OSCAR включены система пакетной обработки заданий OpenPBS и планировщик очередей MAUI.
OpenPBS и MAUI обеспечивают эффективную эксплуатацию кла­стера, как единого вычислительного ресурса коллективного пользова­ния и позволяют решать следующие задачи:
формирование очередей заданий пользователей;
гибкое управление очередями заданий;
выделение ресурсов кластера по запросам;
освобождение ресурсов кластера после выполнения заданий;
поддержка гибкой системы приоритетов, позволяющей распределять ресурсы по заданным правилам;
поддержка алгоритмов, обеспечивающих равномерную и максималь­но полную загрузку вычислительной системы в целом.
Удаленный доступ на кластер через защищенный протокол SSH (Secure Shell) может быть организован с любой рабочей станции (в том числе и WINDOWS), имеющей доступ в ту же сеть, что и управляющий узел кластера.
В качестве базового параллельного окружения на кластер уста­новлена специально оптимизированная для работы с Myrinet 2000 реа­лизация MPI - mpich-gm.
В состав mpich-gm входят утилиты и библиотеки, которые совме­стно со свободно распространяемыми компиляторами gcc 3.2.2 (C/C++, Fortran 77), а также коммерческим компилятором Intel Fortran 77/90 7.1 позволяют разрабатывать параллельные MPI программы.
Результаты тестирования
На кластере ВЦ РАН был проведен комплекс тестов определяю­щих характеристики, как его отдельных систем: коммуникационных сред, вычислительных узлов, так и всего кластера в целом.
При тестировании коммуникационных сред кластера определя­лись такие характеристики, как пропускная способность и латентность. Наибольший интерес представляют характеристики вычислительной се­ти кластера, которые определялись как для низкоуровневых коммуни­каций, так и для коммуникаций уровня MPI. В качестве тестовых про­грамм использовались PMB (Pallas MPI Benchmark) [4], а также тесты,

предоставленные производителем Myrinet 2000. На рис.1 и 2 представ­лены результаты тестирования пропускной способности вычислитель­ной сети кластера для случая односторонней передачи данных.

Рис. 2. Пропускная способность вычислительной сети кластера ВЦ РАНдляразныхреализаций MPI - mpich-gm-1.2.4 и mpich-1.2.4
На рис. 3 и 4 представлены результаты тестирования латентности вы­числительной сети кластера для случая односторонней передачи данных.

0

Рис. 3. Латентность вычислительной сети кластера
ВЦРАИдля односторонних обменов низкого уровня (уровень GM) и уровня MPI
Результаты тестирования показали, что:

пропускная способность вычислительной сети кластера ВЦ РАН для коммуникаций низкого уровня (уровня GM) равна не менее 237.5 MB/sec и латентность не более 10.2 usec. В тоже время по результа­там тестирования представленным на Web-сайте производителя Myrinet 2000 [5] для узлов построенных на базе процессоров Intel P4 и материнской платы Supermicro P4DL6 (64bit/66Mhz PCI) были по­лучены следующие характеристики: пропускная способность 240 MB/sec, латентность 8.5 usec;
пропускная способность вычислительной сети кластера ВЦ РАН для базовых коммуникаций уровня MPI в случае реализации оптимизи­рованной для работы с Myrinet 2000 составляет не менее 224.4 MB/sec, латентность не более 11.06 usec;
пропускная способность вычислительной сети кластера ВЦ РАН для базовых коммуникаций уровня MPI в случае реализации исполь­зующей стек протоколов TCP/IP составляет не менее 101.09 MB/sec, латентность не более 43.18 usec.
Анализируя полученные результаты, следует подчеркнуть, что:
параметры (пропускная способность, латентность) вычислительной се­ти кластера ВЦ РАН, полученные экспериментально соответствуют эталонным параметрам, представленным производителем Myrinet 2000;
эффективность оптимизированной под Myrinet 2000 (mpich-gm) реализации MPI близка эффективности коммуникаций низкого уровня (уровня GM);
накладные расходы на стек протоколов TCP/IP серьезно снижают эффективность коммуникаций уровня MPI. Следовательно, эффек­тивные межузловые взаимодействия могут быть обеспечены только с использованием специально оптимизированной для работы с Myrinet 2000 реализации MPI.
Необходимо отметить, что в данной статье проводится анализ па­раметров вычислительной сети для базовых коммуникаций типа «точка-точка», однако аналогичные результаты были получены также для групповых и коллективных коммуникаций.
Также проводилось тестирование кластера, которое предполагало определение таких характеристик, как его производительность и эффек­тивность. Данные характеристики были получены для задачи уровня MPI приложения - теста HPL (High Performance Linpack) [6]. Отметим, что на основе теста HPL строится список Top500[7], а также список Top50 России [8].
Максимальная производительность (Rmax) на тесте HPL была по­лучена при размерности задачи (TVmax) 57000x57000 и равнялась 59.4 Gflops. При этом эффективность, то есть отношение полученной на тес­

те HPL производительности (Rmax) к пиковой производительности кла­стера (Rpic), равна 71,4%.
Анализ первых 100 кластеров из Top500 показал, что эффектив­ность кластеров на базе платформы Xeon с использованием сетевой тех­нологии Myrinet находится в диапазоне 50-70%, т.е. эффективность кла­стера ВЦ РАН близка к максимально возможной. Необходимо отметить, что данный результат получен для увеличенной с 16 до 32-х гигабайт оперативной памяти кластера. В исходной конфигурации кластера (16 гигабайт оперативной памяти) была получена эффективность 67% (см. рис. 5-6). Таким образом, увеличение памяти в два раза позволило под­нять общую эффективность кластера на ˜5%.



83,2

? Пиковая
? HPL (2GB/node)




˜ ? HPL (4GB/node) ˜



56,0 59,4










ИВ

























'о. о:
Е

о
100,0% -90,0% -
80,0%
70,0% -
60,0% 50,0% 40,0% 30,0% 20,0% 10,0% 0,0%
100,0%



67%

Пиковая
HPL (2GB/node)
? HPL (4GB/node)

71,4%


Ж"


I"



Рис. 5. Производительность кластера ВЦ РАН дляразного объема оперативной памяти -2GB на узел и 4GB на узел
Рис. 6. Эффективность кластера ВЦРАНдляразного объема оперативной памяти -2GB на узел и 4GB на узел

Важным преимуществом кластерных вычислительных систем яв­ляется оптимальное соотношение цена/качество. Для данной системы это соотношение составляло чуть менее 1 доллара США за Mflops, что являлось одним из лучших на момент построения системы. В настоящее время соотношение цена/качество не более 0,5 доллара США за Mflops.
Заключение
В процессе эксплуатации кластера на нем решались различные классы задач:
1) длительные задачи-тесты (HPL, PMB, Perftect), требующие за-
грузки всех узлов кластера;
длительные задачи от 3-х до 5-ти суток, от 4-х до 8-ми узлов;
средней длительности от 2-х до 4-х суток, от 3-х до 5-ти узлов;
отладка - до 2-х узлов, в пределах одних суток.

На базе кластера был организован учебный класс для обучения студентов МФТИ курсу параллельных вычислений.
В настоящее время ведутся работы по модернизации кластера ВЦ РАН, включающие в себя установку последних версий системного про­граммного обеспечения. ИСП РАН, как член ассоциации Gelato [9] ве­дет работы по интеграции в OSCAR программных продуктов собствен­ной разработки, часть из которых будет также установлена на кластер ВЦ РАН. В частности предполагается установить:
интегрированный интерфейс системы управления кластера, который обеспечивает безопасный доступ пользователей к ресурсам вычисли­тельного кластера через интерфейс Web-броузера;
систему активного мониторинга аппаратуры, которая обеспечивает мониторинг жизненно важных параметров аппаратуры кластера. При этом обеспечивается автоматическое завершение работы, как от­дельных узлов, так и кластера в целом в случаях возникновения ава­рийных ситуаций;
систему управления питанием кластера, обеспечивающую удаленное управление питанием, как отдельных узлов, так и кластера в целом.
Кластер ВЦ РАН был построен, введен в эксплуатацию и поддер­живается специалистами ИСП РАН, ВЦ РАН и компании C.I. Technology
[10].
С 2004 года работа поддерживается грантом РФФИ 04-07-90346 (руководитель проекта академик РАН А.А. Петров).
Литература
Михайлов Г.М., Копытов М.А., Рогов Ю.П., Самоваров О.И., Чернецов A.M. Параллельные вычислительные системы в локальной сети ВЦ РАН // Вычислительный Центр им. А.А. Дородницына РАН. Москва. 2003.
ISP HPC. http://www.ispras.ru/groups/ctt/clusters.html
OSCAR. http://www.gelato.org/software/view.php?id=1_18
Pallas MPI Benchmark. http://www.pallas.com/e/products/pmb/
Myricom Inc. http://www.myri.com
HPL (High Performance Linpack). http://www.netlib.org/benchmark/hpl/
Top500. http://www.top500.org
Top50. http://www.parallel.ru
Gelato. http://www.gelato.org/
10. C.I. Technology. http://www.citech.ru/
РЕГУЛЯРИЗУЮЩИЕ АЛГОРИТМЫ ГРАНИЧНО-ЭЛЕМЕНТНОГО РАСЧЕТА УПРУГИХ ТЕЛ С ТОНКИМИ ЭЛЕМЕНТАМИ СТРУКТУРЫ, РАСПРЕДЕЛЕННОГО НА КЛАСТЕРЕ РАБОЧИХ СТАНЦИЙ

А.И. Олейников, К.С. Бормотин
Комсомолъский-на-Амуре государственный технический университет,
г. Комсомольск-на-Амуре
Введение
Для описания напряженно-деформированного состояния сред применяется подход, основанный на теории интегральных уравнений, и его численная реализация методом граничных элементов (МГЭ).
Решение задач при наличии малых и тонких областей, в связи с близостью границ тонких элементов структуры и использованием инте­гральных уравнений для перемещений, сопряжено с очень высоким по­рядком и плохой обусловленностью соответствующей системы алгеб­раических уравнений. Эти обстоятельства приводят к потере точности, вычислительной неустойчивости и, в конечном итоге, к некорректности расчета. В этих условиях получение удовлетворительного численного решения представляет собой одну из важных задач вычислительного моделирования.
Эта задача решается различными методами регуляризации и опре­деляется наиболее эффективный.
1. Математическая постановка задачи и гранично-интегральная формулировка
Рассмотрение метода расчёта напряжённого состояния кусочно-однородных тел основывается на непрямом методе граничных элемен­тов, предназначенного для решения двумерных краевых задач в случае однородного изотропного линейно-упругого тела [1].
Рассматривается двумерная линейно-упругая область, ограничен­ная контуром. При заданных на контуре значениях (т.е. поверхностных нагрузках, перемещениях) требуется определить напряжения (и пере­мещения) внутри данной области. Напряжения и смещения во внутрен­ней точке плоскости, вызванные действием фиктивной нагрузки (неиз­вестной, действующей вдоль контура), представляются в интегральном виде, где плотность потенциала представляется функцией Грина. Так как интегральные уравнения представляют суперпозицию фундамен­тальных решений, то будут удовлетворены все уравнения линейной теории упругости.
Чтобы решить некоторую заданную граничную задачу, необходи­мо ещё удовлетворить граничным условиям на контуре. Для этого в ин­тегральных уравнениях нужно перейти к пределу при стремлении поле­вой точки к контуру. Удовлетворение заданным граничным значениям приводит к системе сингулярных уравнений.
Для решения интегрального уравнения применяется квадратурный метод прямоугольников, при котором интегральное уравнение аппрок­симируется системой линейных алгебраических уравнений. Граничный контур разбивается на отрезки, в средней точке которого определяются результирующие граничные значения.
Метод граничных элементов, рассмотренный выше, предназначен для решения двумерных краевых задач в случае однородного изотроп­ного линейно-упругого тела.
Задача теории упругости для кусочно-однородных тел основыва­ется на рассмотрении тела, состоящего из фаз. Каждая из фаз считается однородной изотропной и линейно-упругой со своими упругими посто­янными. Описание напряжённо-деформированного состояния всего тела осуществляется вектором перемещения, тензорами деформаций и на­пряжений для каждой фазы.
Краевая задача для кусочно-однородного тела заключается в зада­нии обычных условий для смещений и напряжений на «свободной» час­ти контуров, а также условий непрерывности смещений и усилий на по­верхности контакта подобластей.
2. Методы решения интегральных уравнений для тел с тонкими
слоями
При численном решении система интегральных уравнений с ис­пользованием квадратурной формулы прямоугольников приводится к системе линейных алгебраических уравнений
Ax = b.
Для определения эффективности методов решалась тестовая зада­ча о тонком покрытии отверстия в пластине в условиях плоской дефор­мации. При толщине кольца h = 0.01мм порядок матрицы системы ли­нейных уравнений достигал 7624, определитель оценивался равным 3,189-24313. Это говорит об ухудшении вычислительных качеств задачи. Вычислительный процесс на основе метода Зейделя или квадратного корня терял устойчивость.
Задача регуляризации сводится к минимизации функционала
/(x) =|| Ax - B||2 (1)
или


Регуляризованный проксимальный метод, подобно проксималь­ному методу, состоит в минимизации (3), но только функция f (x) имеет вид (2) [3]. Уравнение для нахождения минимума следующее
A*A + 2bpapE + E)x = 2ppA*b + x0,
где в качестве x0 на нулевом шаге используется вектор граничных усло­вий, а на каждой последующей итерации - регуляризованное прибли­жение x, полученное на предыдущей.

1,00 1,03 1,05 1,08 1,10 1,00 1,03 1,05 1,08 1,10
Рис. 1. Сравнение численныхрезулътатов с аналитическими. (Сплошная линия - аналитическиерезулътаты)
Для данного метода характерно то, что при использовании норми­ровки невязка имеет большее значение, чем без нормировки. Таким об­разом, по наблюдению изменения невязки регуляризованный прокси­мальный метод лучше использовать без нормировки. Хотя решение все равно достигается медленно.
Следовательно, из рассмотренных методов наиболее эффектив­ным является проксимальный.
3. Алгоритм и результаты расчета
Математической основой, позволившей распараллелить вычисле­ния, является принятый в алгоритме способ минимизации функционала. Во-первых, постоянная часть, а именно произведения A*A и AAb, могут быть вычислены единовременно. При этом, операция умножения транс­понированной матрицы на саму себя может быть легко распараллелена между процессорами (рабочими станциями) по тому же математическо­му алгоритму, что и на суперкомпьютерах с разделяемой памятью. Дан­ная операция составляет первый этап работы программы.
Оставшаяся часть алгоритма регуляризации, состоящая в последо­вательном решении линейных систем с разными параметрами, однако, может быть проведена параллельно. Это возможно благодаря использо­ванию для решения таких систем метода квадратного корня - неитера­ционного метода, прямой ход которого состоит в преобразовании мат­рицы коэффициентов уравнений, а обратный в последовательном полу­чении вектора-решения. Так как не требуется знать результатов вычис­лений предыдущей итерации во время прямого хода, то эти вычисления для разных параметров могут проходить параллельно. По окончании же расчета одним из компьютеров p-ой итерации результат должен быть передан компьютеру, рассчитывающему p+1-ю итерацию и т.д.. Выиг­рыш по времени следует из того, что время, тратящееся на прямой ход, намного больше времени проведения обратного. Данная операция со­ставляет второй этап работы комплекса.
Были проведены расчеты режущих инструментов с моно и много­слойными покрытиями. Решение данной задачи было проведено с ис­пользованием программы, вычисляющей на кластере рабочих станций.
Та же задача расчета напряженно-деформированного состояния износостойких покрытий была проведена методом конечных элементов в MSC.Nastran с использованием MSC.Patran.
Результаты, произведенные с помощью разных комплексов про­грамм, полностью совпадают, причем расчет на MSC.Nastran проходил быстрее, но подготовка конечно-элементной сетки с использованием препроцессора MSC.Patran потребовала подбора геометрии задачи для каждой толщины покрытия, что сильно снижает эффективность данных комплексов.
В таблице 1 приведены времена распределённого расчёта решения
T
задачи, а также коэффициенты ускорения Sm = — и эффективности
Tm
S
Em = — (где Tm - время параллельного алгоритма на кластере из m ра-m
бочих станций, T1 - время выполнения последовательного алгоритма на одной машине; Tm представляет собой совокупность чистого времени счёта и накладных расходов на подготовку и пересылку дынных).
мов и обмены результатами, можно прогнозировать стабильное увеличе­ние производительности при дальнейшем росте числа компьютеров в кла­стере вплоть до числа, равного количеству итераций внутреннего цикла метода регуляризации.
Литература
Олейников А.И. и др. Расчет напряжений в породных массивах мето­дом граничных интегральных уравнений // Кривой рог: НИГРИ, 1982. - 24с.
Тихонов А.Н., Арсении В.Я. Методы регуляризации некорректных задач // Главная редакция физико-математической литературы изд-ва «Наука», М., 1974.
Васильев Ф.П., Обрадович О. Регуляризованный проксимальныйметод для задач минимизации с неточными исходными данными // ЖВМиМФ, 1993. Т. 33, №2. С. 182-188.


ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛЕНИЯ ДЛЯ ИДЕНТИФИКАЦИИ ПАРАМЕТРОВ В МОДЕЛЯХ ЭКОНОМИКИ [1
Работа выполнена при финансовой поддержке Российского фонда фунда­ментальных исследований (коды проектов 04-07-90346, 04-01-00606), по программе государственной поддержки ведущих научных школ (код проекта НТТТ-1843.2003.01), при поддержке программы № 3 фундаментальных исследований ОМН РАН «Вычислительные и информационные проблемы решения больших за­дач» и при поддержке программы фундаментальных исследований РАН № 16 «Ма­тематическое моделирование и интеллектуальные системы».]
Н.Н. Оленев [2
Работа выполнена при финансовой поддержке Российского фонда фунда­ментальных исследований (коды проектов 04-07-90346, 04-01-00606), по программе государственной поддержки ведущих научных школ (код проекта НТТТ-1843.2003.01), при поддержке программы № 3 фундаментальных исследований ОМН РАН «Вычислительные и информационные проблемы решения больших за­дач» и при поддержке программы фундаментальных исследований РАН № 16 «Ма­тематическое моделирование и интеллектуальные системы».]
Вычислительный центр им. А.А. Дородницына РАН, г. Москва
Введение
Огромный возможный набор сочетаний значений параметров не позволял до появления кластерных суперкомпьютеров точно определять эти значения. Использование высокопроизводительных параллельных вычислений на суперкомпьютере благодаря достаточно полному пере­бору позволяет точно решить задачу идентификации параметров слож­ных математических моделей экономических систем.
Дело в том, что в моделях экономики имеется немало параметров, которые не удается найти напрямую из данных экономической стати­стики. В случае же, когда данных статистики хватает, качество исход­ных статистических данных, как правило, таково, что их хватает только для определения интервалов, в которые попадают параметры модели. Кроме того, и начальные значения некоторых переменных модели часто оказываются неизвестными и поэтому должны рассматриваться как та­кого рода параметры.
Неизвестные параметры экономической модели определяют кос­венным образом, сравнивая выходные временные ряды переменных мо­дели с доступными статистическими временными рядами. В качестве критериев близости расчетного Xt и статистического Yt временных рядов удобно (см. [1, 2]) использовать коэффициент корреляции Пирсона Ре [­1, 1] и индекс несовпадения Тэйла [Те [0,1] [3]. Коэффициент корреля­ции является мерой силы и направленности линейной связи между сравниваемыми временными рядами и, чем он ближе к +1, тем более схоже поведение этих рядов. При этом следует учитывать, что инфля­ционная составляющая может преувеличивать линейную связь рядов, поэтому при использовании коэффициента корреляции нужно сравни­вать показатели в реальных величинах. Индекс Тэйла U измеряет несов­падение временных рядов Xt и Yt и чем ближе он к нулю, тем ближе сравниваемые ряды:
U=[S(X - Yt)2]1/2/ [(SXt2)1/2+(SYt2)1/2].
Поскольку параметров довольно много, вначале следует провести естественное распараллеливание процессов, описываемых моделью: разбить модель на отдельные блоки, идентификацию параметров в ко­торых можно производить независимо. Это дает возможность за разум­ное время определить независимые параметры. При этом временные ря­ды переменных, определяемые в модели из других блоков и используе­мые в данном блоке, как внешние переменные, можно задавать либо на основе данных, полученных из уже откалиброванных блоков модели, либо на основе статистических данных.
После декомпозиции модели по блокам, благодаря параллельным вычислениям на суперкомпьютере становится реальной возможность полного перебора параметров модели на заданном интервале их изме­нения с последовательно уменьшающимся интервалом изменения пара­метров. Для однозначности выбора оптимального варианта можно ис­пользовать ту или иную свертку коэффициентов корреляции и индексов Тэйла, например, если искомые параметры имеют примерно равную важность, можно максимизировать отношение среднегеометрической величины корреляции к среднегеометрическому коэффициенту Тэйла. При этом следует перебирать только те варианты значений параметров, коэффициент корреляции для которых выше некоторой положительной величины, например, 0.75.
В качестве примера в данной работе рассмотрена задача иденти­фикации параметров производственной функции, используемой в новой модели переходной экономики России, разрабатываемой в ВЦ РАН для оценки динамики теневого оборота в 1995-2003 гг.
Производственная функция
Обычно параметры производственной функции определяют по данным экономической статистики для временных рядов переменных, непосредственно входящих в производственную функцию. Такой под­ход может быть оправдан отсутствием модели, в которой используется данная производственная функция. Кроме того, найти параметры про­изводственной функции, внутренне согласованные с поведением других переменных модели весьма сложно в силу чрезвычайно большого числа возможных вариантов. Однако высокопроизводительные вычисления на суперкомпьютере позволяют найти параметры производственной функ­ции, согласованные с поведением других переменных математической модели экономики.
Однородная степени 1 производственная функция с постоянной эла­стичностью замещения (CES-функция) успешно применялась при иссле­довании экономики СССР (см., например, [4]). В качестве производствен­ной функции экономики России 1995-2003 гг., описывающей в каждый момент времени t зависимость валового внутреннего продукта Y от коли­честв используемых производственных факторов: труда R и капитала C, -возьмем однородную степени g CES - функцию.

(1)
где параметры производственной функции удовлетворяют нера­венствам

0<a <1, р >0, g >1, 5 >0.
(2)

Суммарные производственные фонды (капитал) в постоянных це­нах в соответствии со статистическими данными практически не меня­ются, а занятость даже слегка уменьшается. Чтобы описать рост ВВП с помощью выбранного типа производственной функции сделаем допол­нительные предположения об органическом строении капитала. Будем считать, что капитал C(t) состоит из двух частей: «старого капитала» A, который только падает
dA/dt=-\\A A(t), (3)
и «нового капитала» B, который растет за счет введения в строй новых производственных фондов J(t)
dB/dt=J(t)-mB B(t), (4)
так что

C(t) = A(t) + B(t).
(5)


Параметры амортизации \iA>0, mB >0 наряду с параметрами произ­водственной функции предстоит определить косвенным образом.
Статистические данные по ВВП испытывают заметные сезонные колебания от квартала к кварталу. Однако ни капитал, ни реальная зар­плата таких колебаний не испытывают. Что касается труда, то если его выражать, как это обычно принято, в миллионах человек занятых, то он также не испытывает сезонных колебаний. Однако если труд выразить в количестве отработанного в каждом квартале времени (в миллиардах человеко-часов), то он испытывает колебания, четко повторяющим ко­лебания ВВП.
Экономический агент «Производитель»
Ответственный за производственный блок экономический агент, которого логично назвать производителем, получает доходы производ­ства и торговли, делает инвестиции и нанимает трудящихся, может брать срочные кредиты у коммерческих банков, выплачивает дивиден­ды собственникам производственных фирм в соответствии с заданной им политикой накопления капитала.
Считаем, что объем банковских ссуд L ограничен основным капи­талом в соответствии с его органическим строением:
L(t)=(aAA+aBB)p(t), (6)
где индекс цен на основные фонды p(t) считается заданным в данном блоке, а параметры aA > 0, aB >0 следует определить.
Изменение банковских ссуд и расчетного счета определяются из баланса доходов и расходов. Для простоты налоговые отчисления в консолидированный бюджет задаются с помощью двух видов налогов: налога на добавленную стоимость n (НДС), включающего налог на при­быль, и единого социального налога m (ЕСН), включающего подоход­ный налог.
Считается, что производитель функционирует с целью максими­зации его капитализации. Это совпадает с максимизацией дисконтиро­ванных доходов, причем процент дисконтирования совпадает с соответ­ствующей двойственной оценкой роста активов, внутренне присущей рассматриваемой задаче оптимального управления.
Полученные в результате решения задачи оптимального управле­ния формулы, определяют загрузку производственных фондов трудом, процент дисконтирования, ставку заработной платы, ВВП, дивиденды, объем банковских ссуд, остаток расчетного счета.
Параллельные вычисления
Параллельные вычисления основаны на распараллеливании цик­лов, осуществляющих полный перебор значений искомых параметров в заданных интервалах их изменения с последовательно уменьшающимся шагом равномерной разбивки интервалов.
В первой серии параллельных вычислений был осуществлен пере­бор указанных выше 8 параметров модели и, кроме того, начального значения нового капитала B(0). Оптимальные значения параметров оп­ределялись косвенным образом, сравнивая по введенной свертке крите­риев Тэйла и коэффициентов корреляции, рассчитанные по модели вре­менные ряды и статистические временные ряды для следующих показа­телей: выпуска Y, капитала C и объема банковских ссуд L при заданном труде R, заданном индексе цен p, заданных капиталовложениях J. Пара­метры производственного блока: 8=130 тыс. руб 2000 г., a=0,91, b=0,68, g=5,68, да=0,0675, цв=0,0273, aA=0,0005, aB=0,188. Амортизация нового капитала оказалась ниже амортизации старого, а норма обеспечения банковских ссуд для нового капитала значительно выше соответствую­щей нормы для старого капитала.
При этом ставка заработной платы получилась примерно в три раза выше статистической, что на первый взгляд не противоречит ре­альностям нашей жизни. Однако при таком подходе дивиденды оказы­ваются меньше нуля.
10 I

Рис. 1. ВВПрасчетный и статистический
В следующей серии параллельных вычислений наряду с указан­ными выше показателями подгонялось к статистическим значениям и значения для ставки заработной платы s. Такой подход можно оправ­дать предположением, что статистические органы уже учли теневой до­ход в заработной плате. В результате, как и следовало ожидать, диви­денды оказались положительными. Параметры производственного бло­ка: 8=16 тыс. руб 2000 г., a=0,93, р=0,08, g=4,9, да=0,064, дв=0,009, aA=0,001, aB=0,11. Полученные данные подтверждают необходимость

совокупного согласованного изменения параметров при изменении ис­ходных предположений.
Однако сезонные колебания расчетных значений выпуска стали намного меньше статистических. Это означает, что используемый труд должен колебаться значительно больше, чем показывает статика.
Это можно учесть, если увеличить амплитуду колебаний выпуска предполагая, что фактический труд R (измеряемый в млрд. человеко-часов) имеет большую амплитуду колебаний, чем статистический труд Rs:
R=k(Rs-R0). (6)
Возможная интерпретация (6):
R0 - «балласт», труд, учитываемый в статистике, но не принося­щий добавленной стоимости (оплачиваемый по статистической зарпла­те), Ro<Rs.
k>1 - коэффициент фактической занятости оставшихся. Другими словами, те занятые, что приносят добавленную стоимость, работают не 8 часов в день, ав k раз больше.
Кроме того, в дальнейших расчетах следует учесть, что фактиче­ский фонд и фактическая ставка заработной платы не ниже статистиче­ской, фактическая ставка единого социального налога не превышает статистическую ставку, а доход консолидированного бюджета от ЕСН совпадает со статистическим доходом. Таким образом, будет получена нижняя оценка теневой составляющей в заработной плате.
Литература
1. Olenev N. Production Function of Skilled and Unskilled Labour in a Model
of a Non-Growing Russian Economy // International Labour Market Conference
Proceedings. - Aberdeen: Robert Gordon University, 1999. P. 560-575.
Web: http://ideas.repec.org/p/wpa/wuwpla/0309005.html.
Оленев Н.Н. Параллельные вычисления при калибровке моделей эконо­мики // Декомпозиционные методы в математическом моделировании и ин­форматике. Тезисы докладов 2-й Московской конференции. Москва, Россия (21-24 июня 2004 г.). С. 81-82.
Theil H. Economic Forecasts and Policy. North-Holland Publishing Com­pany, Amsterdam, 1961.
Weitzman M.L. Soviet Postwar Economic Growth and Capital-Labor Substitu­tion // The American Economic Review, (Sep.). 1970. Vol. 60, No. 4. P. 676-692.

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

СИ. Олзоева
Восточно-Сибирский государственный технологический университет,
г. Улан-Удэ
Введение
Имитационное моделирование сложных систем в настоящее время является одним из ключевых направлений развития интеллектуальных компьютерных технологий. В последнее время доминирует тенденция внедрения методов имитационного моделирования в различные интерак­тивные системы оптимизации, экспертные системы. Активное использо­вание систем поддержки принятия решений в задачах планирования, управления и проектирования в реальных производственных структурах ведут к интеграции этих систем с проблемно-ориентированными имита­ционными моделями (ИМ) на основе объектной ориентированности про­граммных компонентов. Имитационное моделирование позволяет осу­ществлять анализ динамических процессов в условиях неопределенности действия стохастических факторов различной природы, исследовать большое количество алгоритмов, сценариев развития и является основой для поиска и формирования варианта решения.
Однако, несмотря на большие функциональные возможности у всех ИМ есть одна общая проблема - это проблема производительности. Это обусловлено: во-первых, огромными объемами данных, которые необхо­димо обработать; во-вторых, получение статистически обоснованных оценок исследуемых характеристик требует больших вычислительных затрат. Стремление ускорить вычисления, либо получить большую точ­ность, либо усложнить модель изучаемого явления требуют более мощ­ную вычислительную технику. Таковыми являются сегодня параллель­ные вычислительные системы - кластерные многопроцессорные систе­мы. Программы ИМ, предназначенные для выполнения на однопроцес­сорной ЭВМ, не переносятся эффективно на параллельные системы. Требуется переделка, сопровождаемая дополнительным анализом задачи. Приобретает наибольшую важность и значимость автоматизированное конструирование структуры программного обеспечения ИМ для распре­деленного моделирования. Это требует расширения и разработки про­граммно-технического инструментария имитационных систем.
Существующие сегодня методы автоматического синтеза имитаци­онных моделей и соответствующие им алгоритмы не позволяют про­граммно и в полном соответствии требованиям разработки реализовать всю совокупность свойств распределенных имитационных систем в рам­ках допустимых временных ограничений при имитационном моделирова­нии. Поэтому их недостатки должны компенсироваться программной поддержкой функций распараллеливания алгоритмов имитационного мо­делирования, измерения параметров качества получаемого проекта рас­пределенного имитационного моделирования (РИМ).
К рассмотрению предлагаются подходы к реализации автоматизи­рованного инструментария для оптимальной по критерию времени ор­ганизации распределенного вычислительного процесса ИМ.
Функциональное содержание инструментария для распределения вычислительного процесса ИМ
Функциональное содержание такого инструментария определяется тем, что значительные резервы повышения эффективности имитацион­ных систем скрыты в способах организации вычислительного процесса на многопроцессорной платформе, соответствующем построении вы­числительных схем моделирующих алгоритмов, управляющей про­граммы имитационной модели, а также в способах организации и пред­ставления базы данных модели.
Сложившиеся подходы к имитационному моделированию сложных систем предполагают проведение анализа динамических свойств систем на основе экспериментов с их дискретно-событийными имитационными моделями. При всем многообразии и различии предметных областей имитационного моделирования, все ИМ дискретно-событийных систем состоят из следующих составляющих:
модулей S^...Sn, воспроизводящих поведение различных элемен­тов и подсистем моделируемого объекта;
управляющей программы (УП), реализующей логику поведения модели, т.е. квазипараллельное и коррелированное течение модельных процессов;
модулей, обслуживающих процесс моделирования (ввод - вы­вод, планирование машинного эксперимента, статистическая обработка результатов моделирования).
Таким образом, современная концепция построения имитационных моделей сложных систем естественным образом вписывается в модель параллельных вычислений MPMD (Multiple Program - Multiple Data). Для реализации на параллельных вычислительных платформах имитационно­го моделирования сложных систем наиболее подходит модель вычисле­ний MPMD по следующим причинам:
- Внутренний параллелизм. Сложные системы состоят, как прави­ло, из параллельно функционирующих компонент на разных уровнях иерархической структуры системы. Поэтому имитационная модель
сложной системы содержит множество модулей, соответствующих раз­личным элементам и подсистемам моделируемого объекта.
- Разнородность подсистем и элементов, составляющих сложную систему, порождает и разнородность математических схем, описываю­щих функционирование различных элементов. Отдельные элементы и подсистемы могут быть описаны, например, дифференциальными урав­нениями, системами массового обслуживания, конечными автоматами и т.д. Отсюда следует разнородность программной реализации модулей ИМ.
На основании изложенного, назначение программного инструмента­рия для организации распределенного имитационного моделирования со­стоит в отделении аспектов, связанных с разработкой программного обес­печения ИМ, от вопросов организации распределенных (параллельных) вы­числений. Что и определяет технологические этапы функционирования программного инструментария:
1. анализ структуры программного обеспечения (ПО) имитацион-
ной модели, выбор алгоритма распараллеливания (декомпозиции) ИМ;
2. декомпозиция ИМ;
3. оценка качества вариантов проектов распределенной имитаци-
онной модели, определение возможных временных факторов;
4. выбор окончательного проекта РИМ.
Алгоритмы технологических этапов
Алгоритмическим наполнением технологических этапов являются методы декомпозиции имитационной модели систем, а также методы оценки возможных временных факторов РИМ.
Для программ имитации характерно то, что они представляют со­бой сильно-связный код. Это обусловлено традиционной организацией управляющей программы имитации и централизацией базы данных мо­делирования, с которой работают и управляющая программа, и програм­мы имитации процессов, т.е. взаимодействие моделируемых процессов происходит через обращение к общим наборам данных. Поэтому простое распределение модулей моделирующей программы по процессорам не будет способствовать эффективному ускорению процесса имитации из-за многочисленных передач информации между компонентами имитацион­ной модели. Следовательно, задача декомпозиции ПО ИМ сложных сис­тем на блоки, по критерию минимизации обмена данными между блока­ми ИМ, состоит именно в оптимальном распараллеливании алгоритмов управления имитационной моделью. Что автоматически определит вари­ант декомпозиции ПО ИМ и базы данных модели.
Задача декомпозиции управляющей программы требует такого формального описания логики управления имитационной моделью, ко­торое можно подвергать математическому анализу. Чтобы математиче­ское представление логики управления можно было сравнивать между собой, подвергать декомпозиции и перестраивать разными способами. Этот формализм должен отвечать на вопрос об эквивалентности моделей управления: централизованной и распределенной.
С этой целью рассмотрим математические модели представления дискретно-событийных систем (ДСС) каковыми являются ИМ. Логиче­ское поведение ДСС может моделироваться с помощью конечных авто­матов и сетей Петри, которые подчеркивают лишь последовательность состояний дискретных систем и полностью опускают описание времени пребывания в каждом из состояний. С их помощью можно исследовать вопросы лишь качественного или логического характера. Временные же и стохастические дискретно-событийные модели обеспечивают более полное описание поведения систем, поэтому больше приспособлены для ответа на вопросы, связанные с характеристиками функционирова­ния. Кроме того, полнота описания достигается за счет уменьшения общности. На практике менее сложный формализм, как более ограни­ченный, может оказаться полезнее.
В нашем случае преследуется цель такой декомпозиции ИМ, что­бы сохранялась глобальная логика поведения модели. Поэтому предла­гается управляющую программу описать математической моделью расширенного конечного автомата. Работу УП можно представить в ви­де многополюсника, который коммутирует сигналы от группы входов w к группе выходов z под управлением сигналов x. Работа такого автомата описывается специальными рекурсивными функциями. Они определяют переход системы из предыдущего состояния в последующее и выходной сигнал. Математически это выражается с помощью следующей системы уравнений:
S(t+1)=f(S(t),X(t)),
Z(t+1)=f(S(t),X(t)),
где X(t)=[x1(t), ...xp(t)] - значения сигналов на входе автомата, S(t)=[S1(t),...Sn(t)] - внутренние состояния, Z(t+1)= [z1(t),...,zk(t)] - значе­ния сигналов на выходе автомата. При получении внешнего сигнала счи-тывается состояние системы. После этого паре «входной сигнал - состоя­ние» сопоставляются действия перехода и корректируется состояние. При этом внутренним состояниям Si(t) соответствуют модули ИМ, воспроизво­дящие поведение подсистем моделируемого объекта.
При таком описании логики поведения задача декомпозиции УП сводится к задаче разложения автоматного описания управляющей про­граммы на ряд функционально несвязных друг с другом автоматов мень­шей размерности, обеспечивающих реализацию необходимых воздейст­вий на объект управления, т.е. ИМ. Задача декомпозиции автомата сво­дится к разложению графа переходов исходного автомата в частичное де­картово произведение более простых по числу вершин графов переходов функционально несвязных друг с другом подавтоматов. Эту задачу пред­лагается решить методом многокомпонентной раскраски графов с исполь­зованием характеризационного метода [1], удобного для реализации на ЭВМ и позволяющего существенного сократить перебор вариантов.
На основании проведенных преобразований формируется децентра­лизованная УП имитационной модели дискретно-событийных систем, обеспечивающая синхронизацию работы модельных блоков, выполняю­щихся на разных процессорах и работающая с подчиненными диспетче­рами модельных блоков. В соответствии с полученной структурой УП ав­томатически формируется распределенная база данных моделирования.
Для оценки качества полученного варианта декомпозиции ИМ пред­ложен способ оценки потенциального параллелизма для заданного вари­анта декомпозиции ИМ, позволяющий определить возможный временной фактор. Предлагаемый способ основан на применении математического аппарата теории случайных импульсных потоков и позволяет учесть ха­рактеристики неоднородности вычислительной платформы, на которой предполагается реализация РИМ. Определение возможного временного фактора до начала процесса моделирования позволит эффективно органи­зовать вычислительный процесс. Описание способа изложено в [2].
Заключение
Таким образом, разработка методов и программных средств рас­пределенного имитационного моделирования, сочетающих сложившие­ся приемы имитационного моделирования систем и методов обработки информации на многопроцессорных системах, создает благоприятную основу для решения задач ускорения имитационного моделирования систем большой сложности и размерности и придает современным ими­тационным системам новые системные свойства. Последние заключа­ются в возможности получения статистически обоснованных результа­тов моделирования с требуемой точностью и детальностью исследова­ния, без существенных ограничений на размерность модели и модели­руемого объекта и, как следствие, возможность широкого использова­ния в автоматизированных системах реального времени.
Литература
Горбатов В.А. Теория частично-упорядоченных систем // М.: Совет­ское радио, 1976, - 336 с.
Kutuzov O. I., Olzoeva S. I. Some questions of the simulation of complex sys­tems onto message-passing parallel architectures // In: Proceedings of International Conference on Soft Computing and Measurements, 2003, St. Petersburg, Russia, 2003. Vol. 1. P. 187-120.
ПРОГРАММЫЕ СРЕДСТВА ДЛЯ УПРАВЛЕНИЯ ПАРАЛЛЕЛЬНЫМ ВЫПОЛНЕНИЕМ ГРАФ-СХЕМНЫХ ПОТОКОВЫХ ПРОГРАММ НА КЛАСТЕРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ
М.А. Осипов
Московский энергетический институт (ТУ), г. Москва
Введение
В докладе описаны программные средства, реализованные в про­цессе выполнения проекта [3 работа выполнена при поддержке рффи, проект 03-01-00588], нацеленного на создание системы граф-схемного потокового программирования для кластерных вычислитель­ных систем (ВС) (руководитель проекта профессор Кутепов В.П.) [1]
Следующие три основные проблемы были поставлены и решались в рамках этого проекта:
создание визуального граф-схемного языка крупно-блочного потоко­вого параллельного программирования,
разработка инструментальной среды, предназначенной для програм­мирования параллельных программ на языке граф-схем,
создание операционных средств, осуществляющих управление па­раллельным выполнением граф-схемных потоковых программ (ГСПП) на различных конфигурациях кластерных ВС.
Созданный язык и разработанная для него инструментальная сре­да программирования описаны в [2].
Ниже мы остановимся на основных решениях, которые были по­ложены в основу создания программных средств, предназначенных для эффективного управления процессом выполнения граф-схемных парал­лельных программ (ГСПП) на кластерных ВС.
1. Операционная семантика параллельного выполнения ГСПП
ГСПП представляется в виде пары <ГС,Г>, где ГС - граф-схема, I -интерпретация. Граф-схема или просто схема позволяет визуально представлять строящуюся из модулей программу решения задачи; ин­терпретация сопоставляет каждому модулю множество подпрограмм, а связям между модулями - типы данных, передаваемых между подпро­граммами модулей в процессе выполнения ГСПП.
Основным «строительным» блоком ГСПП является модуль, гра­фическое представление которого приведено на рис. 1. Все входы и вы­ходы модулей строго типизированы и разделены на группы (они назы­ваются конъюнктивными группами входов (КГВх) и конъюнктивными

int
int
О—I
группами выходов (КГВых), соответственно) и отражают структуру по­токов данных, передаваемых между подпрограммами модулей. Каждой КГВх модуля однозначно сопоставляется подпрограмма на одном из последовательных языков программирования (C/C++, Pascal, Java и др.). Кроме того, в качестве формального параметра в списке параметров подпрограмме добавляется параметр tag, который указывается первым. На ГС этот параметр не изображается, поскольку он идентифицирует данные, передаваемых между модулями ГСПП в процессе его выполне­ния (рис. 1).
int float[]
int float\\ floatU
КГ входов 2
Назначение:
Вычисление определителя матрицы
КГ входов 3
Назначение:
Построение обратной матрицы
э-о-о
КГ входов 1
Назначение:
Перемножение матриц

Модуль: Matrix
КГ выходов 1
-о о-

int float[]
Рис. 1. Графическое изображениемодуля
ГС представляет блочную структуру, построенную из модулей пу­тем соединения выходов КГВых модуля с входами КГВх другого или этого же модуля, причем типы соединяемых входов и выходов должны совпадать.
В модели параллельного выполнения ГСПП реализуются три вида параллелизма:
пространственный, являющийся следствием информационной неза­висимости модулей ГСПП и, как следствие, процессов, сопоставляе­мых их КГВх,
потоковый, параллелизм множества данных (SIMD - один поток ко­манд, множество потоков данных), т.е. тот случай параллелизма, когда одна и та же программа (или подпрограмма модуля в случае языка ГСПП) одновременно выполняется для разных данных на ее входе.
Для того чтобы различать последние два вида параллелизма при выполнении ГСПП, используется механизм тегирования. В операцион­ной семантике языка ГСПП это выражается в том, что при наличии на всех входах конъюнктивной группы входов модуля данных, помечен­ных соответствующими тегами, параллельно запускаются на выполне­ние несколько процессов, каждый из которых однозначно идентифици­руется тегом и сопоставленными ему данными.
Модуль ГСПП считается готовым для выполнения по любой из своих КГВх, если на всех входах этой КГВх (в соответствующих входам буферах) есть данные, помеченные одним и тем же тегом.
Различные теги идентифицируют различные данные, к которым одновременно применяется ГСПП, точнее, подпрограммы, отнесенные к соответствующим КГВх ее модулей (таким образом, реализуется па­раллелизм множества данных).
При выполнении процесса в его подпрограмме могут использо­ваться специальные системные команды (реализуемые посредством обычного обращения к специальным функциям) WRITE (запись), READ (чтение), OUT (выход) - позволяющие осуществлять межмо­дульное взаимодействие, т.е. строить различные схемы взаимодействия по данным между подпрограммами различных модулей путем чтения данных из буферов или записи данных в буферы, сопоставляемые вхо­дам КГВх модулей.
Команда WRITE имеет формат: WPJTE(<HOMep КГВых>,<тег>,<список выходов><список переменных>), где список выходов есть перечисление номеров выходов КГВых, на которые пере­даются значения.
Команда OUT имеет аналогичный формат аргументов, однако по­сле ее выполнения процесс, в котором она возникла, считается завер­шенным и его контекст может быть уничтожен.
Команда READ имеет формат: READ (<номер КГВх>, <тег>, <список входов>, <список переменных>). При ее выполнении также со­храняется контекст процесса, а после ее завершения процесс продолжа­ет свое выполнение в старом контексте. Команда READ позволяет про­цессу читать данные с указанным тегом из буферов, сопоставленных КГВх, по которой процесс был инициирован.
Для более «тонкой» работы с поступающими на КГВх модулей данными, в частности работы с сопоставляемыми им буферами, преду­смотрена команда CHECK(<HOMep КГВх>.<тег>,<список входов>, <пе­ременная>), которая проверяет наличие данных с указанными тегами на указанных входах КГВх.
Для того, чтобы уничтожить процессы (удалить их контексты), которые оказываются ненужными, в подпрограммах модулей может ис­пользоваться команда KILL(<cnncoK имен уничтожаемых процессов>).
Отметим еще ряд существенных элементов операционной семан­тики языка ГСПП, которые также важны при его реализации на парал­лельных системах:
порядок выполнения множества процессов, существующих на каж­дом шаге выполнения ГСПП, не существенен,
определение готовых для выполнения процессов следует дисциплине FIFO: проверка на наличие в буферной памяти КГВх данных с одним и тем же тегом на всех ее входах осуществляется в порядке занесе­ния этих данных в буферную память.
• поскольку с одним и тем же буфером данных могут одновременно работать несколько процессов (чтения или записи), поэтому в реали­зации нужно обеспечить взаимное исключение одновременных по­добных действий.
2. Реализация языка граф-схем параллельных алгоритмов
на кластерных ВС
Локальная сеть (в том числе сеть персональных компьютеров) яв­ляется основным «строительным блоком» или узлом вычислительной системы или кластера. Узел кластера - хорошо сбалансированная по от­ношению, к быстродействию компьютеров, их количеству и пропускной способности коммуникации вычислительная система, так что на ней можно эффектно осуществлять реализацию параллельных вычислений в достаточно широком диапазоне вариаций степени распараллеливания программ от «крупнозернистого» до «мелкозернистого» параллелизма.
Для параллельного выполнения ГСПП на ВС разработана система программных средств - система управления. Эта система обеспечивает корректность параллельного выполнения программ на кластерной ВС, возможность отладки этих программ, хранение граф-схем и модулей, надёжную передачу данных между процессами модулей и пр.
Помимо перечисленных выше основных задач, связанных с вы­полнением граф-схем, система должна выполнять и другие функции. Следующий список содержит основные функциональные требования к реализации системы управления параллельным выполнением граф-схемных программ на кластерах:
инициализация выполнения граф-схем,
определение готовности процессов для выполнения,
назначение процессов на выполнение, контроль их состояния,
реализация команд языка: Read, Write, Out, Kill и Check,
контроль состояния компьютеров кластера,
планирование процессов с целью оптимизации использования ресур­сов и уменьшения времени выполнения граф-схемы,
реализация интерфейса взаимодействия компьютеров кластера,
параллельное выполнение нескольких процессов,
общая (для всех узлов ВС) система хранения данных,
возможность мониторинга процессов системы,
возможность выполнения подпрограмм модулей в различных ОС.
Система управления также должна обеспечить:
устойчивость к изменениям конфигурации кластера,
надёжный протокол обмена данными между узлами кластера,
высокую производительность.
Система управления параллельным выполнением ГСПП представ­ляет собой набор программных средств, устанавливаемых на каждом компьютере или узле кластера. Состав и организация устанавливаемых программных средств приведена на рис. 2:

Service Manager

Service
Configuration



Client Sender / Receiver
Service Loader



Sender Dispatcher
Receiver Dispatcher



Sender
Receiver




TCP/IP
Рис. 2. Архитектурапрограммных средствуправления процессом выполнения ГСПП
Центральным элементом данной архитектуры является сервис. Сервис - это набор функций системы, выполняющих одну общую зада­чу. Сервис выполнения содержит все функции, необходимые для вы­полнения ГСПП на кластере. Именно сервисы реализуют функции, не­посредственно связанные с процессом выполнения ГСПП, описанном в предыдущем разделе. Все остальные элементы архитектуры выполняют системные функции:
инициализация сервисов,
управление конфигурацией кластера,
передача данных между узлами кластера,
взаимодействие с внешними системами,
управление сервисами.
Передача данных между узлами кластера осуществляется компо­нентом Sender, а получение - компонентом Reciever. Для каждого внешнего (по отношению к данному) узла сети в локальной версии сис­темы существуют свои Sender и Reciever. Управление этими компонен­тами осуществляют соответственно Sender Dispatcher и Reciever Dis­patcher. Компонент Client Sender/Reciever осуществляет обмен данными с внешними системами. При запуске системы создаётся компонент Ser­vice Manager, который при помощи Service Loader'a загружает сервисы и инициализирует их.
В сущности, предустановленный на компьютере набор программ­ных компонентов является контейнером сервисов. Контейнер организует вызов необходимых сервисов, предоставляет сервисам функции высоко­го уровня, создаёт окружение. На различных узлах кластера в принципе могут функционировать различные наборы сервисов. Набор сервисов уз­ла кластера определяет роль данного узла в системе. Назовём некоторые сервисы из системы управления:
сервис конфигурации контролирует конфигурацию узла кластера и предоставляет её остальным узлам,
сервис реестра предоставляет другим узлам интерфейс реестра сис­темы. Реестр - это база данных системы, которая имеет иерархиче­скую структуру. Реестр содержит информацию, необходимую для работы системы: программы граф-схем, конфигурацию кластера, информацию о пользователях и т.д. Также реестр может использо­ваться граф-схемами для хранения данных в ходе выполнения,
сервисы управления выполнением - это набор сервисов, которые выполняют функции по запуску, контролю выполнения граф-схем, управлению буферами и планированию.
Сервис выполнения - это основной сервис системы, отвечающий за выполнение ГСПП, соответственно он должен работать на всех узлах кластера, которые участвуют в параллельных вычислениях. Во время инициализации данный сервис получает модули и граф-схемы, инстал­лированные на данном узле. Инсталляция производится при помощи специального программного средства, входящего в состав системы, и заключается в копировании файлов модулей, а также описаний модулей и граф-схем и регистрацию данных сущностей в системе.
Описание модуля содержит идентификатор адаптера для данного модуля. Адаптер - это подключаемый компонент системы, осуществ­ляющий запуск и остановку процесса модуля. Таким образом, один адап­тер может использоваться для определённого класса модулей. Классифи­кация определяется сценарием запуска. Например, для модулей, напи­санных на языке C++ в виде консольных приложений, будет применяться один адаптер, а для модулей, представляющих собой динамическую биб­лиотеку DLL - другой. Также есть специальный регламент поведения модуля и спецификация интерфейса взаимодействия процесса модуля с системой. Таким образом, если программисту необходимо реализовать модуль на каком-нибудь языке программирования, он должен создать библиотеку для работы с системой на этом языке программирования и придерживаться установленного регламента. Данная библиотека может далее использоваться для реализации любого модуля на этом языке про­граммирования. Библиотека предоставляет программисту модулей функ­ции высокого уровня, такие как запись данных на конъюнктивную груп­пу выходов, завершение процесса граф-схемы и т.д. Подобная стратегия (рис. 3) позволяет программировать модули на разных языках програм­мирования и даёт возможность выбора наиболее подходящего языка.

Рис. 3. Взаимодействие процесса модуля с системой
Взаимодействие между локальными компонентами системы управ­ления осуществляется при помощи протокола TCP/IP посредством пере­дачи сообщений определённого формата. Каждое сообщение имеет имя и тело сообщения. При получении сообщения компонент системы Service Manager по имени сообщения определяет сервис, которому предназначе­но это сообщение и передаёт его найденному сервису, который выполня­ет обработку данного события. Список сообщений, обрабатываемых сер­висом, предоставляется системе самим сервисом. По такому же сцена­рию проходит взаимодействие системы с модулями и внешними систе­мами. У каждого типа сообщений есть набор метаданных, который включает вид возможных отправителей для данного сообщения: локаль­ный компонент системы, модуль или внешняя система.
Функции системы по управлению выполнением граф-схем рас­пределены между несколькими сервисами. Набор этих сервисов должен присутствовать на каждом узле кластера, участвующем в вычислениях. Список данных сервисов следующий:
сервис выполнения. Данный сервис отвечает за запуск граф-схем, управление процессами, индуцируемыми при выполнении. Этот сер­вис осуществляет также все взаимодействия между процессами мо­дулей, получает запросы на выполнение функций WRITE, READ, CHECK, KILL, OUT, KILL,
сервис управления буферами. Данный сервис реализует функции WRITE, READ, CHECK и OUT,
сервис планирования. Осуществляет планирование выполнения граф-схемы, а именно определяет узлы кластера, на которых будут выпол­няться процессы модулей
Для того чтобы понять принципы взаимодействия данных серви­сов, приведём несколько сценариев:
Запуск граф-схемы: Пользователь инициирует команду запуска граф-схемы, которая передаётся на выполнение сервису выполнения. Этот сервис создаёт контекст выполнения граф-схемы. Контекст содер­жит идентификатор контекста и имя граф-схемы. Контекст необходим для того, чтобы пользователь имел возможность выполнять несколько граф-схем в системе.
Запись данных на висящие входы граф-схемы: Пользователь инициирует команду записи данных на висящие входы граф-схемы, ко­торая перенаправляется сервису выполнения. Сервис выполнения опре­деляет контекст выполнения и запрашивает у сервиса планирования узел кластера или компьютер, на котором должен располагаться буфер для данного модуля. На указанном узле или компьютере создаётся бу­фер, и в него записываются данные. Данные действия выполняет сервис управления буферами на этом узле.
Запись данных в буфер: При записи данных сервис управления буферами проверяет наличие в буфере готовых кортежей данных. Если в буфере есть кортеж, данный сервис сообщает об этом сервису управле­ния. После получения уведомления от сервиса управления буферами о наличии готового кортежа данных, сервис выполнения запрашивает у сервиса планирования компьютер, на котором должен выполняться про­цесс для этого набора данных. Далее сети сервис выполнения запускает процесс модуля по соответствующей конъюнктивной группе входов.
Заключение
В настоящий момент реализован прототип системы на языке про­граммирования Java. Выбор языка Java обусловлен в первую очередь та­ким требованием к системе, как поддержка различных операционных систем. К плюсам данного языка программирования можно отнести под­держку параллельного программирования и синхронизации, а также про­стоту документирования системы. Минусом является то, что программы на языке Java работают медленнее, чем программы на таких языках про­граммирования, как C/C++. В дальнейшем предполагается перепрограм­мирование критических компонентов системы или всей системы на более «быстрых» языках программирования для нескольких популярных опе­рационных систем, в частности для платформ Win32 и Unix/Linux.
Литература
1. Кутепов В.П., Котляров Д. В., Лазуткин В.А., Осипов М.А. Граф-схемное потоковое параллельное программирование и его реализация на кла­стерных системах // Журнал «Программирование» (в печати).
2. Кутепов В.П., Котляров Д.В., Лазуткин В.А. Система граф-схемного потокового параллельного программирования: язык и инструментальная сре­да построения программ // (В материалах конференции).


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

К.А. Осмехин
Пермский государственныйуниверситет, г. Пермь
Введение
Сегодня понятие кластерных архитектур становится всё более и более известным.
Под кластером обычно понимают множество взаимосвязанных вычислительных систем, которые, как правило, могут работать незави­симо, но также в нужное время способны объединятся для решения од­ной общей задачи.
Наиболее распространённым типом кластеров в университетской среде являются кластеры на основе технологии Fast Ethernet или Gigabit Ethernet. В таких кластерах узлами зачастую являются обычные персо­нальные компьютеры или возможно машины с архитектурой SMP, но построенные на базе процессоров Intel. К таким кластерам относится и кластер созданный у нас в университете. Этот кластер включает в себя обычные персональные ЭВМ, на которых могут работать студенты, а также пять выделенных двухпроцессорных серверов с SMP архитекту­рой на базе процессоров Intel.
Развитие кластерных архитектур в настоящее время происходит, как и развитие любой технологии связанной с компьютерами, высокими темпами. В данной области нет большого объёма накопленных знаний, и потому решение каждой задачи связано с исследованием, опираю­щимся скорее на эмпирические данные, нежели на опыт предыдущих исследователей.
После появления в университете кластера возникла проблема ис­следования возможностей его использования и настройки для работы.
Изначально кластер нельзя было назвать таковым, так как кластер - это программно-аппаратный комплекс, и вот программной части как раз не было.
Поэтому первой проблемой был выбор и тестирование операци­онных систем для установки на кластере. Обязательным требованием выбора операционной системы была её бесплатность. Поэтому и по ря­ду других причин все исследования проводились среди операционных систем семейства Unix. При тестировании операционных систем необ­холимо было учесть их совместимость с аппаратным обеспечением, а это было не так просто вследствие, во-первых, его разнородной струк­туры, и, во-вторых, специфичностью аппаратных компонент.
В результате проведённого исследования в области применения кластеров были выделены следующие проблемы, которые могут быть решены с использованием кластерной архитектуры:
создание систем высокой производительности;
создание систем высокой доступности;
более полное использование вычислительных ресурсов.
Ниже описан состав программного и аппаратного обеспечения, которое используется на кластере.
Аппаратное обеспечение
Кластер состоит из набора 12-ти рабочих станций, на базе процес­соров Intel Celeron 1.2 МГц, которые расположены как обычные рабочие места. Также в состав кластера входит блок серверов, смонтированный в отдельную стойку и имеющий в своём составе: четыре 2-х процессор­ных сервера на базе процессоров Intel Pentium III 1.2МГц и один 2-х процессорный сервер на базе процессоров Intel XEON 2.0ГГц.
Программные компоненты
Встала задача создания на базе имеющегося аппаратного обеспе­чения системы способной решать вышеуказанные проблемы.
Основным и самым широко распространённым способом использо­вания кластеров является их использование в научных областях для ре­шения сложных задач. Этот подход имеет место, так как зачастую созда­ние кластера из "обычных" машин является гораздо более дешёвым ре­шением, нежели покупка специального суперкомпьютера. К тому же во многих организациях такая обычная техника простаивает и потому ло­гично её использовать как часть кластера.
Между тем, для тех же задач в кластер могут быть объединены и более мощные компьютеры, специально приобретённые для этих целей. В таком случае предполагается, что помимо самих вычислителей в со­став кластера должно входить более совершенное коммуникационное оборудование. Так как основным стремлением при создании кластера является желание создать некоторый параллельный компьютер, при работе на котором создавалось бы ощущение, что вы работаете с одной машиной, то увеличение производительности средств связи является совершенно необходимым, ибо позволит сократить временные задерж­ки при взаимодействии отдельных узлов кластера.
В рамках создания на кластере высокопроизводительной вычисли­тельной системы способной решать сложные расчётные задачи, были установлены библиотеки параллельного программирования и средства управления параллельными задачами (PVM, MPI).
Как уже было сказано, использование кластеров для научных рас­чётов является наиболее широко используемым направлением работы в кластерной архитектуре, но естественно не единственным.
Огромное значение для современных прикладных задач имеет создание отказоустойчивых систем, и здесь на помощь снова приходят кластеры. Современные отечественные разработки в области создания кластеров в университетских центрах, в основном, направлены на соз­дание систем высокой производительности. Исследованию же создания систем высокой доступности посвящено очень мало работ, поскольку в них могут быть заинтересованы крупные компании, использующие тя­желовесные системы управления предприятием, системы поддержки принятия решений и тому подобное. В этой области пока ещё не сфор­мирована большая потребность.
Естественно, что, заменяя единичную систему многозвенной, мы уве­личиваем её сложность и это может привести к недостаткам, но несомнен­ны и преимущества, даваемые кластерными системами в системах ориен­тированных на поддержание корпоративных решений (распределённые ба­зы данных компании, интранет порталы, системы поддержки принятия ре­шений). Кластеры помогают решить множество проблем возникающих в таких системах. Среди них такие как: балансировка загрузки, создание рас­пределённых хранилищ данных, создание систем работающих в режиме 7x24. Поэтому создание подобных систем сейчас так широко поддержива­ется ведущими производителями программного обеспечения программных систем, такими как Microsoft, IBM, SUN Microsystems, Oracle и др. Созда­ние с помощью кластера системы высокой надёжности реализовано на ос­нове продукта Oracle Real Application Clusters. Данный продукт позволяет создавать базы данных высокой доступности за счёт распределения загруз­ки по нескольким узлам кластера. Основным замечанием является то, что в списке совместимых операционных систем компании Oracle нет ни одной свободно доступной системы, поэтому, делая попытку использовать про­граммный продукт Oracle, мы понимали, что гарантий успеха нет. Тем не менее, после испытаний на кластере девяти операционных систем удалось установить Oracle Real Application Clusters. Следует отметить, что это по­зволит использовать кластер не только для научных расчётов, но и для реа­лизации прикладных проектов, в которых требуется использование высо­конадёжной и производительной базы данных.
Следующим направлением, в котором проводятся сейчас исследо­вания в области кластерных архитектур, является метакомпьютинг или «технология GRID». Данная технология позволяет использовать про­стаивающие вычислительные ресурсы, которых достаточно много в со­временных организациях. Для этого в кластер объединяются все вычис­лительные ресурсы организации, предприятия, а зачастую узлами кла­стера становятся машины находящиеся на большом расстоянии друг от друга и соединённые глобальной сетью Internet.
Технология GRID применяется ещё менее интенсивно. Сама идея GRID родилась около пяти лет назад, но её полезность очевидна. Исполь­зование GRID на предприятиях и в организациях позволит увеличить по­лезность использования вычислительных ресурсов, а в глобальном мас­штабе, если GRID- сети будут объединены также как Internet, позволит получать доступ к распределённой информации, находящейся в инфор­мационном пространстве. Данную технологию можно сравнить с созда­нием электросети, когда конечный пользователь не знает, из какого ис­точника получает электроэнергию, и точно также запрос к GRID должен автоматически порождать механизмы поиска нужного сервиса и конеч­ный пользователь не будет знать, кто ему это сервис предоставил.
В рамках исследования технологии GRID на кластере была установлена система Sun One Grid Engine, которая позволяет распределять нагрузку в сети, планируя выполнение отдельных заданий на компьютерах кластера.
Заключение
Итак, в Пермском государственном университете на механико-математическом факультете была создана вычислительная система с кластерной архитектурой. В настоящее время её ресурсами пользуются студенты, в рамках учебных курсов. Следует отметить, что пока нет «серьёзных» задач, успешно реализованных средствами этой системы.


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

Н.Д. Пиза, Р.К. Кудерметов
Запорожский национальный технический университет, г. Запорожье, Украина
Введение
Для обеспечения качественной наземной отработки и испытаний высокоточных систем управления космических аппаратов (КА) в соста­ве полунатурных моделирующих комплексов (ПНМК) постоянно воз­растают требования к точности моделей, описывающих движение КА, процессов его взаимодействия с внешней средой, работу элементов сис­темы управления. Это достигается применением все более сложных и полных моделей, организацией моделирования в реальном времени, что, в свою очередь, приводит к необходимости увеличения вычислительной мощности компьютеров, которые используются в ПНМК. Одним из на­правлений повышения производительности и сокращения времени ре­шения задач является использование параллельных вычислений.
Авторами исследована возможность применения параллельных блочных методов интегрирования [1] и разработаны параллельные про­граммно-алгоритмические средства для моделирования движения КА. В данной статье приведены результаты экспериментальных исследований ускорения и эффективности разработанных параллельных программно-алгоритмических средств, полученные для различных типов вычисли­тельных систем.
Структуры параллельных вычислительных систем для исследова­ния разработанных программно-алгоритмических средств.
Для экспериментальных исследований выбраны четыре парал­лельных вычислительных системы, которые представляют основные типы современных высокопроизводительных систем:
компьютерная сеть Fast Ethernet;
SCI-кластер (Петродворцовый телекоммуникационный центр Санкт-Петер-бургского государственного университета (СПбГУ));
SMP-узлы (symmetric multiprocessors - симметричные мультипроцес­соры, кластер Нижегородского государственного университета (ННГУ));
суперкомпьютер CRAY T3E (Штутгартский вычислительный центр).
Экспериментальные исследования разработанных параллельных программных моделей проводились на конфигурациях параллельных вычислительных систем, представленных на рис. 1-4 (серым цветом обо­значены неиспользуемые процессоры). В составе кластера ННГУ (рис. 2) исследовалась реализация параллельной модели движения КА на процес­сорах в режиме SMP. NN-two и NN-four - обозначения вариантов конфи­гураций, в которых используются двухпроцессорные и четырехпроцес-сорные узлы кластера, соответственно.

p1
M

p2
M

p1
M

p2
M

p3
M

p4
M

















Fast Ethernet
Коммуникационная среда Fast Ethernet
а) два процессора б) четыре процессора
Рис. 1. Сеть Fast Ethernet (Intel Pentium IV 1.76 ГЕц)

M

p1
p2

M




p1
p2

3
p4
M




p1
p2
PP
34



а) два процессора, б) два процессора, в) четыре процессора, вариант NN-two вариант NN-four вариант NN-four
Рис. 2. Конфигурации процессоров при экспериментах на кластере
ННГУ (двухпроцессорный узел: Intel Pentium IIIXeon 1000 МГц,
четырехпроцессорныйузел: Intel Pentium IIIXeon 700 МГц)

б) два процессора, вариант single





SCI
в) четыре процессора, г) четыре процессора,
вариант double вариант single
Рис. 3. Конфигурации процессоров при экспериментах на SCI-кластере (Intel Pentium III Copermine 933 M^)

P1
M P2
M

P1
M P2
M P3
M P4
M









Коммуникационная среда GigaRing



Коммуникационная среда GigaRing




а) два процессора б) четыре процессора
Рис. 4. Конфигурации процессоров в экспериментах на CRAY T3E
Для исследования на SCI-кластере (Scalable Coherent Interface -масштабируемый когерентный интерфейс) были проведены два вариан­та экспериментов, условно названные single и double (рис. 3). В вариан­те single на каждом узле кластера использовался только один процессор, т.е. для двухточечного метода интегрирования был задействован один канал SCI, а для четырехточечного - три канала SCI. В варианте double использовались два процессора в узлах кластера, т.е. двухточечный ме­тод интегрирования выполнялся в режиме SMP на одном узле, а четы­рехточечный - с использованием двух узлов в режиме SMP и одного канала SCI между узлами.
Результаты исследования характеристик быстродействия параллельных средств моделирования движения КА
В качестве меры вычислительной сложности моделируемых сис­тем (уравнений движения КА) принято время выполнения операции ум­ножения вещественных чисел типа double. Сложность типовой про­граммной модели движения КА, описываемой системой дифференци­альных уравнений 13 порядка, содержащей в правых частях упрощен­ные функции моделирования возмущающих и управляющих воздейст­вий, экспериментально оценена как 10 тыс. операций умножения. Путем последовательного увеличения сложности исходной модели и измере­ния затрат времени на моделирование 10000 с полета КА получены за­висимости ускорения и эффективности параллельных вычислений от сложности модели, характеристик процессоров и быстродействия ком­муникационных сред перечисленных выше вычислительных систем.
На рис. 5 представлены результаты экспериментальных исследова­ний. В экспериментах измерялись затраты времени при параллельном и последовательном интегрировании движения КА с использованием од-ношаговых блочных методов и вычислялись ускорение и эффективность параллельных вычислений на вычислительных системах: сети Fast Ethernet (рис. 5 а, б), узлах и каналах связи SCI-кластера СПбГУ (рис. 5 в, г), SMP-узлах кластера ННГУ (рис. 5 д, е), суперкомпьютере CRAY T3E (рис. 5 ж, з). На оси абсцисс представлено количество вычис­лительных операций.
Для ссылок на результаты экспериментов введены следующие обо­значения: NET - результаты, полученные на сети Fast Ethernet; SCI-single и SCI-double - результаты, полученные на SCI-кластере в вариантах single и double, соответственно; NN-two - результаты, полученные на двухпроцессорном узле кластера ННГУ, NN-four - на четырехпроцес-сорном узле; CRAY - результаты, полученные на CRAY T3E, цифры 2 и 4 указывают на двухточечный и четырехточечный блочные методы ин­тегрирования.
Как видно из рис. 5 а, в, д, ж, параллельное решение типовой зада­чи моделирования движения КА выполняется быстрее, чем последова­тельное (ускорение больше 1) на всех параллельных вычислительных системах, кроме сети Fast Ethernet. Это объясняется тем, что затраты времени на вычисления для сети Fast Ethernet значительно ниже по сравнению с затратами времени на обмен данными. Однако, с увеличе­нием сложности модели (начиная, примерно, с 25 тыс. вычислительных операций) решение с использованием параллельных методов выполня­ется быстрее, чем с использованием последовательных методов и на се­ти Fast Ethernet. Это справедливо как для двухточечного, так и для че­тырехточечного блочных методов.



Из рис. 5 а, в, д, ж видно, что с усложнением правых частей урав­нений ускорение для всех параллельных вычислительных систем в слу­чае двухточечного метода стремится к двум, в случае четырехточечного метода - к четырем, что согласуется с максимальными теоретически возможными значениями.
На рис. 5 б, г, е, з представлена эффективность - отношение уско­рения к количеству процессоров, на которых решается задача.
Используя тесты скорости обменов [2], оценены затраты времени на коммуникации (табл. 1).
Таблица 1

Блочный метод
Время, секунды






NET
SCI-single
SCI-double
NN-two
NN-four
CRAY
двухточечный
2,139
0,208
0,043
0,404
0,660
0,219
четырехточеный
8,200
1,027
0,926

3,431
0,525

На основании экспериментальных данных получены формулы для оценки эффективности применения параллельных вычислительных сис­тем для моделирования движения КА в зависимости:
от сложности модели m (коэффициент сложности правых частей уравнений),
характеристик процессоров и быстродействия коммуникационной среды системы,
методов блочного интегрирования.
Для двухточечного блочного одношагового метода:

m >
3t

f
(1)

для четырехточечного блочного одношагового метода:

m>
15t,
f , (2)
где C1 и Cp - суммарные затраты времени на выполнение арифметиче­ских операций для последовательной и параллельной реализаций мето­дов интегрирования, соответственно;
tc - время, необходимое для обмена данными между процессора­ми;
tf - время вычисления правых частей уравнений.
С помощью этих формул можно определить во сколько раз исход­ная задача должна быть сложнее, чтобы ее решение на параллельной вычислительной системе стало эффективно (ускорение больше едини­цы). Так, для используемой сети Fast Ethernet при усложнении правых частей уравнений модели движения в 2.43 раза применение двухточеч­ного метода становится эффективным. Для четырехточечного метода этот коэффициент равен 2.19.
Выводы
Экспериментальные исследования показывают, что моделирова­ние динамических объектов, описывающихся системами обыкновенных дифференциальных уравнений и решаемых с помощью блочных мето­дов интегрирования, может быть реализовано на кластерных и парал­лельных вычислительных системах. Эффективность такого моделиро­вания зависит как от производительности процессоров, коммуникаци­онных средств, так и от сложности модели. Наиболее эффективными для построения ПНМК являются SMP-системы с узлами из двух и че­тырех процессоров.
Литература
Пиза Н.Д., Кудерметов Р.К. Применение кластерных систем для мо­делирования движения космического аппарата // Высокопроизводительные параллельные вычисления на кластерных системах. Материалы третьего ме­ждународного научно-практического семинара / Под ред. проф. Р.Г. Стронгина. - Нижний Новгород: Изд-во Нижегородского госуниверсите­та. 2003. С. 127-135.
Андреев А.Н., Воеводин Вл.В. Методика измерения основных характе­ристик программно-аппаратной среды // (www.dvo.ru/bbc/benchmarks.html).


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

М.С. Седельников
Сибирский государственный университет телекоммуникаций и информатики, г. Новосибирск
Введение
Решение сложных задач требует применения параллельных вычис­лительных систем (ВС). Эффективность использования ВС определяется тем, как организован процесс их функционирования. Как правило, ВС используются в монопрограммном режиме. В данной работе рассматри­вается одна из проблем, возникающих при одновременном решении на ВС нескольких параллельных задач.
Постановка задачи
Пусть имеется ВС, на каждую из элементарных машин (ЭМ) кото­рой поступают параллельные задачи. Каждая задача характеризуется рангом (требуемым числом ЭМ) и временем решения. Любая ЭМ со­держит расписание для исполнения распределенных на неё задач. Под временем загрузки ВС понимается максимум времени решения всех за­дач по всем ЭМ. Требуется распределить поступающие задачи по ЭМ системы (т.е. создать для каждой из них подсистему) так, чтобы время загрузки ВС было минимально.
Такая задача является TVP-полной [1], что является достаточным основанием для отказа от поиска точного алгоритма для её решения. Интерес представляют приближенные и эвристические алгоритмы, ко­торые позволяют получить субминимальное значение времени загрузки [2, 3]. Среди них можно выделить централизованные и децентрализо­ванные алгоритмы. Тенденции к повышению производительности ВС путем увеличения числа ЭМ [4] заставляют отдавать предпочтение вто­рым. В данной работе предлагается эвристический децентрализованный алгоритм диспетчера распределения параллельных задач по вычисли­тельной системе.
Схема алгоритма
Пусть всем ЭМ присвоены уникальные номера. На ЭМ с номером k имеется очередь Qk поступающих задач. Диспетчер ЭМ извлекает задачу
ранга r из своей очереди и создаёт подсистему размера r путем, по воз­можности, равномерного распределения требуемого числа ЭМ среди своих соседей. Другими словами, диспетчер строит дерево подсистемы, в котором корнем является ЭМ k, инициирующая создание подсистемы, а ЭМ каждого следующего уровня являются соседями одной или несколь­ких ЭМ с предыдущего. Листьями дерева являются ЭМ, на которые рас­пределена одна ЭМ.
Работа алгоритма диспетчера основана на событиях, обмене со­общениями между ЭМ и их состояниях. Каждая ЭМ может находиться в одном из 3-х состояний. I (idle) - ЭМ не участвует в создании подсис­темы. PD (primary distribution) - ЭМ распределяет поступившую на нее задачу и создает подсистему для неё. SD (secondary distribution) - ЭМ создает подсистему по запросу от другой ЭМ. Имеются 6 видов сооб­щений: запрос, согласие, отказ, подтверждение, отмена и информацион­ное.
Далее примем следующие условные обозначения: Mkq - множество, состоящее из ЭМ k и множества её соседей, сре­ди которых распределено требуемое число ЭМ.
STATE - состояние текущей ЭМ;
Ms = {j}, Ts = Tj} - множество соседей ЭМ s и их загрузка соот­ветственно;
Msq - множество, состоящее из ЭМ s и множества опрашиваемых соседей;
Rq = Ь} - числ0 ЭМ, которые распределены по соседям ЭМ s; Lsq ={j} - множество предельных соседей (lj = 1, если rj макси­мально, иначе lj =0);
M + е Msq - подмножество соседних с s ЭМ, приславших отказ или
согласие;
kq - номер ЭМ, от которой ЭМ s был получен запрос на создание
подсистемы;
N*, r*, t* - параметры обрабатываемой задачи.
КОНЕЦ - окончание работы алгоритма обработки события.
Решение о включении соседей в множество Mq, принимаемое ЭМ
s, основано на критерии F (Ts, Tk , r, А), где Ts - загрузка ЭМ s, Tk - за­грузка ЭМ k, инициирующей создание подсистемы, r - требуемое число ЭМ, А - параметр (отклонение от загрузки ЭМ k).
Приведем алгоритмы обработки каждого события.
Событие 1: на ЭМ k из очереди Qk поступила задача вида {N, r,
t}.
Шаг 1. Если STATE Ф I, то задача возвращается в очередь КО­НЕЦ.
Шаг 2. Если r=1, то Tk := Tk +1, подсистема для задачи {N, r, t} соз­дана, всем ЭМ из множества Ms отправляется информационное сооб­щение {Tk}, STATE:= i, КОНЕЦ.
Шаг 3. STATE := pd, N* := N, r*:= r, t*:=t.
Шаг 4. Согласно критерию F (Ts, Tk, r, А) из множества соседей Mk формируется множества Mkq, Rkq, Lkq, M + := {k}.
Шаг 5. Всем ЭМ s из множества Mkq отправляется запрос {N, rs, t,
Ts, Tk}, rs ? Rkq .
Событие 2: на ЭМ s пришёл запрос от ЭМ i, вида {N, r, t, T, Tk}. Шаг 1. Если STATE ф SD и STATE Ф I, то ЭМ i отправляется отказ {N, 0, T}, КОНЕЦ.
Шаг 2. Если STATE = SD и kq Ф i, то ЭМ i отправляется отказ {N,
0, T}, КОНЕЦ.
Шаг 3. Если Ts Ф T, то ЭМ i отправляется отказ {N, 0, Ts }, КОНЕЦ. Шаг 4. Если STATE = i, то переход на шаг5, иначе на шаг11. Шаг 5. N* := N, r* := r, t* := t, kq := i, STATE = sd.


сформировать указанные множества, то подсистему под задачу {N*, r*, t*} создать невозможно, всем ЭМ j из множества Msq отправляется от­мена вида {N*}, STATE := I, КОНЕЦ.
Шаг 13. Всем ЭМ j из множества Msq отправляется запрос {N, rj, t,
Tj, Tk}, rj e r; .
Событие 4: на ЭМ s пришел отказ от ЭМ i, вида {N, r, T}.
Шаг 1. Если T ф T, то T := T*, Msq := Msq \ {i}, R6q := R6q \ {},
Lsq := Lsq \ {{}, иначе r := r, U := 1.
Шаг 2. Если M+ фMsq, то КОНЕЦ, иначе на шаг 3.
Шаг 3. Если STATE=PD, то переход на шаг4, иначе на шаг 8. Шаг 4. Если FJlj = 1, то переход на шаг5, иначе на шаг 6.

Шаг 5. Подсистему под задачу {N*, r*, t*} создать невозможно. Всем ЭМ j из множества Msq отправляется отмена вида {N*}, STATE =
I, КОНЕЦ.
Шаг 6. Согласно критерию F (Tj, Tk, r, А) из множества соседей Ms переформируются множества Msq, Rq, Lsq и M +. Если невозможно
сформировать указанные множества, то подсистему под задачу {N*, r*, t*} создать невозможно, всем ЭМ j из множества Msq отправляется от­мена вида {N*}, STATE=I, КОНЕЦ.
Шаг 7. Всем ЭМ j из множества Msq отправляется запрос {N, rj, t,

Шаг 8. Если STATE = SD, то переход на шаг 9, иначе КОНЕЦ. Шаг 9. Если FJlj = 1, то переход на шаг 10, иначе на шаг 11.
hELSq
Шаг 10. ЭМ kq отправляется отказ вида {N*, rs, Ts}, КОНЕЦ.
rsERq
Шаг 11. Согласно критерию F (Tj, Tk, r, А) из множества соседей Ms переформируются множества Msq, Rq, Lsq и M +. Если невозможно
сформировать указанные множества, то ЭМ ksq отправляется отказ {N,
, Ts}, КОНЕЦ.
rsERSq
Шаг 12. Всем ЭМ j из множества Msq отправляется запрос {N, rj, t,

Событие 5: на ЭМ s пришло подтверждение от ЭМ i, вида {N}. Шаг 1. Всем ЭМ j из множества Msq отправляется подтверждение
вида {N*}, загрузка ЭМ j e M6q Tj := Tk +1 *, подсистема для задачи {N*,
r*, t*} создана.


Полученные результаты показывают, что предложенный алгоритм позволяет распределить большую часть задач, даже в случае одновре­менного поступления их на все ЭМ системы.
Литература
Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые за­дачи // М.: Мир, 1982.
Евреинов Э.В., Хорошевский В.Г. Однородные вычислительные системы // Новосибирск: Наука, 1978.
Седельников М.С Параллельный алгоритм распределения набора задач по машинам вычислительной системы // Материалы всероссийской научной конференции «Наука. Техника. Инновации. - 2003», 2003. Ч. 2. С. 24-25.
Top500 Список 500 самых мощных компьютеров мира. 22-я редакция [Электронный ресурс] / Информационно-аналитический центр по параллель­ным вычислениям ; Электрон. дан. - М.: Лаборатория Параллельных информа­ционных технологий НИВЦ МГУ, 2004. Режим доступа: http://www.parallel.ru/ computers/top500.list.html свободный. - Загл. с экрана. - Яз. рус.
Хорошевский В.Г., Майданов Ю.С., Мамойленко СИ., Павский К.В., Моренкова О.И. Живучая кластерная вычислительная система // Труды шко­лы-семинара «Распределенные кластерные вычисления», Красноярск, изд-во Красноярского государственного университета, 2001.
СЕРВИС МЕЖКЛАСТЕРНЫХ КОММУНИКАЦИЙ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ

А.В. Селихов
Институт вычислительной математики и математической геофизики
СО РАН, г. Новосибирск
Введение
Рост потребности в высокопроизводительных вычислительных ре­сурсах привел к необходимости объединения имеющихся вычислитель­ных систем на разных уровнях и с разной степенью интеграции. Резуль­татом стало появление SMP-систем, мультикомпьютеров, кластеров и сетей рабочих станций. Следующий шаг в увеличении доступной вы­числительной мощности ведет к созданию распределенных информаци­онно-вычислительных сетей. Работы в направлении создания единого представления глобальных информационно-вычислительных ресурсов привели к созданию концепции Grid [1,2], одной из реализаций которой стала система Globus [3].
Несмотря на большое количество работ в области организации па­раллельных вычислений с использованием Grid-систем, до сих пор не решены все проблемы, связанные с объединением вычислительных кла­стеров с целью запуска на них параллельного приложения, использую­щего библиотеку MPI. В частности, такие проблемы существуют для кластеров, все рабочие узлы которых имеют только локальные IP-адреса и поэтому не могут быть получателями или отправителями информации при взаимодействии с узлами внешней сети по протоколу TCP/IP, ис­пользуемому для низкоуровневой передачи сообщений в MPICH-реализации библиотеки MPI. Единственным узлом такого кластера, имеющим доступ во внешнюю сеть, является хост-узел. Такая ситуация является следствием различных причин, в частности, установленной по­литики сетевой безопасности или ограничений на количество доступ­ных IP-адресов. Доступные реализации библиотеки MPI для организа­ции вычислений на Grid, такие как MPICH-G2 [4] для системы Globus и PACX-MPI [5], работоспособны только в случае наличия у всех узлов кластера глобальных IP-адресов и возможности обмена сообщениями между любыми двумя узлами.
Целью создания Сервиса межкластерных коммуникаций (СМКК) параллельных программ является преодоление этих трудностей путем организации передачи сообщений между узлами различных кластеров, объединенных в Grid-систему, через хост-узлы этих кластеров. Разра­ботка СМКК имеет также целью создание примера низкоуровневого сервиса, интегрируемого в программные системы организации парал­лельных вычислений на Grid-системах.
Основные понятия и принципы
Рассматриваемые вычислительные кластеры, отличительные свойства которых были указаны во Введении, могут быть названы «за­крытыми», а все вычислительные узлы таких кластеров, кроме хост-узла, - внутренними узлами кластера.
В этой работе под сервисом понимается совокупность функций, предоставляемых посредством интерфейсов, и реализуемых множест­вом взаимосвязанных программных компонент. СМКК обеспечивает передачу сообщений между внутренними узлами различных закрытых кластеров через имеющие непосредственную связь между собой хост-узлы этих кластеров.
Разрабатываемый Сервис межкластерных коммуникаций парал­лельных программ основан на следующих основных принципах.
Прозрачность. Этот принцип определяет неизменность исходного кода параллельного приложения, гарантируя, что параллельное прило­жение будет перенесено на Grid-систему без изменения (требуется только перекомпиляция исходного кода для каждой архитектуры), со­храняя его исходную работоспособность.
Атомарность. СМКК реализует только те функции, которые не­обходимы для обеспечения передачи MPI-сообщений от одного внут­реннего узла другому через хост-узлы. Обеспечение распределения процессов приложения по узлам кластеров, запуск параллельных про­цессов, обеспечение других функций, в том числе на основе СМКК, реализуется другими сервисами и программными компонентами, в том числе путем взаимодействия с СМКК на основе общих интерфейсов, встраиваемых в сервис при необходимости.
Динамизм. СМКК должен обеспечивать работу параллельного приложения в условиях изменяющейся конфигурации Grid-системы, при подключении и отключении кластеров, представляющих общий вы­числительный ресурс. Этот принцип может быть удовлетворен частич­но, путем реконфигурации сервиса только во время простоя, или полно­стью, обеспечивая реконфигурацию во время выполнения приложений.
Кроме этих общих принципов, в качестве отличительной особен­ности СМКК можно отметить осуществление всех коммуникаций, в том числе и между внутренними узлами кластера, через шлюз межкластер­ных коммуникаций. Такой выбор заведомо ухудшает производитель­ность коммуникаций «точка-точка», однако может существенно улуч­шить производительность групповых коммуникаций. Кроме того, такой подход не требует разработки системы поддержки очередей сообщений на вычислительных узлах, так как все сообщения буферизируются на шлюзовом сервере. Использование высокопроизводительного многопо­точного шлюзового сервера может существенно снизить дополнитель­ные накладные расходы на передачу синхронных сообщений, в то время как асинхронные пересылки могут сохранить свою производительность. Передача всех сообщений через шлюзовой сервер позволяет также реа­лизовать программную отказоустойчивость параллельного приложения по протоколу MPICH-V[6], основанному на временном хранении всех передаваемых между процессами сообщений.
Структура сервиса
Сервис межкластерных коммуникаций состоит из двух программ­ных компонент: коммуникационного драйвера библиотеки передачи со­общений MPICH (chiccs) и шлюза межкластерных коммуникаций (рис.1).
Вычислительные


Рис.1. Структура сервисамежкластерных коммуникаций параллельных программ
Коммуникационный драйвер библиотеки MPICH предназначен для реализации высокоуровневых коммуникационных функций MPI. На основе реализации базовых функций, таких как инициализация и завер­шение работы библиотеки, а также функции передачи, приема и про­верки наличия сообщений, коммуникационный драйвер осуществляет подключение процесса параллельной программы к шлюзу межкластер­ных коммуникаций и прием/передачу сообщений через шлюз. Как уже было указано ранее, передача всех сообщений осуществляется через шлюз, что исключает необходимость в организации очереди входящих сообщений, а также подключения процесса ко всем остальным процес­сам данного приложения.
Шлюз межкластерных коммуникаций является компонентом, обеспечивающим прием и буферизацию сообщений от процессов-источников в рамках своего кластера и от шлюзов других кластеров, пе­редачу этих сообщений по запросу процессам-приемникам своего кла­стера, а также передачу сообщений, адресованных процессам других кластеров, шлюзам этих кластеров. Для выполнения этих функций ШМК поддерживает Коммуникационную таблицу приложения (КТП), содержащую распределение ранков процессов параллельного приложе­ния по кластерам. Каждая строка с номером i содержит адрес локально­го узла, если i-й процесс параллельного приложения выполняется на данном кластере, иначе эта строка содержит адрес хост-узла того кла­стера, на котором этот процесс выполняется. Каждый ШМК имеет соб­ственную КТП. Пример коммуникационных таблиц приложения, ис­пользующего 8 процессов для трех ШМК, показан в Таблице 1.
Таблица 1. Коммуникационная таблица параллельного приложения, использующего 4 узла трех кластеров

Шлюз 1(194.226.195.11)

Шлюз 2(212.192.181.16)

Шлюз 3(194.226.185.99)

Ранк
Адрес
Ранк
Адрес
Ранк
Адрес
0
127.0.0.5
0
194.226.195.11
0
194.226.195.11
1
212.192.181.16
1
192.168.0.3
1
212.192.181.16
2
127.0.0.8
2
194.226.195.11
2
194.226.195.11
3
194.226.185.99
3
194.226.185.99
3
127.0.0.12
Любое сообщение, поступающее как от процесса-источника с ло­кального узла, так и от другого шлюза-источника, пересылается соот­ветствующему локальному узлу, если его ранк равен ранку процесса-приемника, иначе оно пересылается следующему шлюзу-приемнику.
На основе описанных свойств СММК, объединяемые кластеры образуют структуру, один из примеров которой показан на рис. 2.

Рис. 2. Пример объединения трех кластеров на основе Сервиса межкластерных коммуникаций
Связи между процессами кластера и шлюзом этого кластера обра­зуют топологию «звезда», в то время как шлюзы различных кластеров связаны между собой по топологии «полный граф».
Функционирование сервиса
Так же как и сервисы, определенные в OGSI [7], сервис межкла­стерных коммуникаций имеет три этапа функционирования: инициали­зация, обеспечение сервисных функций и завершение работы. Каждый этап может содержать различное количество шагов в зависимости от вы­бранной конфигурации сервиса.
Инициализация сервиса межкластерных коммуникаций включает в себя, в первую очередь, запуск шлюзов межкластерных коммуникаций на хост-узлах двух или более кластеров. Интерфейсом запуска ШМК является конфигурационный файл, содержащий адреса всех остальных хост-узлов кластеров. Используя эти адреса, каждый ШМК подключа­ется к соответствующим узлам, формируя полный граф коммуникаций. После окончания инициализации ШМК может быть выполнена инициа­лизация коммуникационного устройства библиотеки MPICH для каждо­го процесса параллельного приложения. Интерфейсом запуска комму­никационного устройства является командная строка приложения, со­держащая адрес ШМК, уникальный идентификатор приложения, общее количество процессов приложения и ранк данного процесса в этом при­ложении. Используя адрес, коммуникационное устройство подключает­ся к ШМК и передает ему остальные три параметра, на основе которых ШМК формирует КТП.
Коммуникации «точка-точка» между любыми двумя процессами одного приложения осуществляются через ШМК. Отправка сообщения от процесса с ранком i кластера A процессу с ранком j кластера B со­стоит из передачи этого сообщения на ШМК кластера A, пересылки этого сообщения на ШМК кластера B и, наконец, доставки этого сообщения от ШМК кластера B процессу с ранком j. В соответствии с такой схемой, для любой конфигурации Grid-системы на основе СМКК передача сооб­щения между любой парой процессов требует ровно три пересылки.
Групповые коммуникации с использованием СМКК могут быть оптимизированы с учетом особенности формируемой структуры связей. Например, рассылка сообщений «один-всем» состоит из передачи на ШМК сообщения с дополнительным флагом, указывающим специфику данной коммуникационной операции, рассылки этим ШМК данного со­общения всем остальным ШМК, адреса которых указаны в КТП, и дос­тавки сообщения всем процессам. Передача сообщения «все-одному» также может быть оптимизирована путем сборки и буферизации всех сообщений в ШМК кластера процесса-приемника, исключая ненужную синхронизацию и ожидание процессов-отправителей. Особенностью реализации групповых операций является необходимость переноса не­которых высокоуровневых операций библиотеки MPICH на уровень функций драйвера низкоуровневых коммуникаций.
В отличие от обычной коммуникационной среды, формируемой при использовании MPICH, процессы параллельного приложения свя­заны только с ШМК своего кластера и поэтому нечувствительны к от­ключениям или подключениям новых ресурсов к Grid-системе. Обеспе­чение динамизма вычислительных ресурсов в процессе выполнения приложения с использованием СМКК основывается на динамическом обновлении КТП, в случае подключения/отключения других ШМК, а также на использовании буферов сообщений, поддерживаемых Шлюза­ми межкластерных коммуникаций. Эти буферы позволяют реализовать протокол MPICH-V обеспечения отказоустойчивости параллельного приложения, используя Память Каналов и асинхронный откат процесса на последнюю контрольную точку. СМКК реализует Память каналов, обеспечивая восстановление сообщений, принятых после последней контрольной точки, однако реализация всего протокола MPICH-V тре­бует привлечения дополнительных компонент и реализации дополни­тельных протоколов, как это сделано, например, в системе CMDE [8].
Заключение
Разработка средств объединения вычислительных кластеров в Grid-системы представляется в настоящее время актуальной задачей. Представленный Сервис межкластерных коммуникаций параллельных программ нацелен на решение проблемы передачи сообщений библио­теки MPI между узлами кластеров, имеющих связь с глобальной сетью только через единственный хост-узел каждого кластера. Реализация компонентов СМКК основывается на опыте разработки системы CMDE, в частности, на использовании Серверов Памяти Каналов, позволяющих осуществлять конвейеризацию синхронной передачи больших сообще­ний, что дает производительность, близкую к передаче этих сообщений по непосредственному соединению между процессами. Использование СМКК предполагает наличие некоторого дополнительного программно­го окружения, осуществляющего распределение множества ранков про­цессов параллельного приложения по различным кластерам, распреде­ление кода приложения по узлам кластеров, формирование входных па­раметров процессов для использования СМКК, подключение узлов Шлюзов межкластерных коммуникаций в общую сеть и другие. На на­чальном этапе для этих целей предполагается использовать компоненты системы CMDE, модифицированные для реализации интерфейсов с СМКК. Дальнейшее развитие сервиса может включать в себя как реали­зацию интерфейсов в соответствии со спецификацией OGSI с целью включения этого сервиса в систему Globus, так и развитие набора сер­висов, включающих СМКК и являющихся более узко специализирован­ными для организации метавычислений.
Литература
Foster, What is the Grid? A Three Point Checklist. GRIDToday, July 20, 2002.
Foster, Kesselman C., Nick J., Tuecke S. The Physiology of the Grid: An Open Grid Services Architecture for Distributed Systems Integration. Open Grid Ser­vice Infrastructure WG, Global Grid Forum, June 22, 2002.
Foster, Kesselman C, Globus: A Metacomputing Infrastructure Toolkit. Intl J. Supercomputer Applications, 1997. 11(2). P. 115-128.
Karonis N., Toonen B. and I. Foster MPICH-G2: A Grid-Enabled Implementa­tion of the Message Passing Interface. Journal of Parallel and Distributed Com­puting, 2003.
Beisel T., Gabriel E., Resch M. An Extension to MPI for Distributed Computing on MPPs'. In Marian Bubak, Jack Dongarra, Jerzy Wasniewski (Eds.) 'Recent Advances in Parallel Virtual Machine and Message Passing Interface', Lecture Notes in Computer Science, Springer, 1997. P. 75-83.
Bosilca G., Bouteiller A., Cappello F., Djilali S., Fedak G., Germain C.,. Herault T, Lemarinier P., Lodygensky O., Magniette F., Neri V., Selikhov A.
MPICHV: Toward a Scalable Fault Tolerant MPI for Volatile Nodes, In Pro­ceedings of SuperComputing 2002. IEEE, Nov., 2002.
Tuecke S., Czajkowski K., Foster I., Frey J., Graham S., Kesselman C., Maguire T., Sandholm T., Vanderbilt P., Snelling D. Open Grid Services Infrastructure (OGSI) Version 1.0. Global Grid Forum Draft Recommendation, 6/27/2003.
Selikhov A., Germain C. CMDE: a channel memory based dynamic environment for fault-tolerant message passing based on MPICH-V architecture // Proc. of 7­th Int. Conference PaCT-2003, Springer Verlag, LNCS 2763, 2003. P. 528-537


ЭФФЕКТИВНОЕ РАСПАРАЛЛЕЛИВАНИЕ ВЫЧИСЛЕНИЙ ДЛЯ ЗАДАЧ ФИЗИКИ АТМОСФЕРЫ

Ю.М. Тырчак
Киевский национальный университет им. Тараса Шевченко, г. Киев,
Украина
Математическая модель задачи прогноза региональных атмосферных процессов
Современное развитие экологической науки ставит все более слож­ные вычислительные задачи, решение которых требует применение сложного математического аппарата при построении модели физических процессов и большого количества вычислений. Решение таких задач ста­новится возможной благодаря развитию мультипроцессорных систем и параллельных вычислений [6].
Сегодня моделирование региональных атмосферных процессов реализуется с учетом того, что поля метеорологических величин в огра­ниченной области формируются под влиянием макромасштабных цир­куляции атмосферы. Поэтому ограниченная область решения рассмат­ривается как часть некоторого целого, и нестационарные краевые усло­вия на его боковых границах формируются на основе данных, получен­ных для области, которая окаймляет. Кроме этого, при численном ре­шении задач прогноза состояния атмосферы для ограниченной террито­рии, появляется необходимость сгущать сетку для достижения необхо­димой точности решения задачи в местах больших градиентов зависи­мых функций.
Предполагая, что поля метеорологических величин на ограничен­ной территории формируются на фоне общей циркуляции атмосферы, задачу прогноза погоды для ограниченной области можно сформулиро­вать путем комбинации двух моделей разной полноты: 1) глобальной модели общей циркуляции атмосферы, которая включает упрощенные уравнения, численно решаемые на грубой сетке; и 2) региональной мо­дели, которая включает полные уравнения гидродинамики и тепло- мас-сопереноса, численно решаемые на мелкой сетке. Необходимые для ре­гиональной модели предельные условия отождествляются с решением глобальной модели, уравнения которой могут интегрироваться одно­временно с уравнениями региональной модели или заранее. Этот метод прогноза на вложенных сетках получил название метода «односторон­него воздействия», поскольку численные результаты внутренней моде­ли не влияют на интегрирование уравнений внешней модели [3].
Широкое применение в существующих моделях циркуляции атмо­сферы и прогноза погоды нашли фундаментальные уравнения динамики вяжущей сплошной среды, которые базируются на универсальных зако­нах, таких, как сохранение массы, сохранение количества движения, со­хранение энергии, сохранение скалярных величин, состояния среды.
Прогноз значений метеорологических величин над ограниченной
территорией G осуществляется на основе метода «одностороннего воз­действия». Другими словами, как предельные условия для региональной модели используются результаты анализа и прогноза, полученные с по­мощью макромасштабной модели (полушара или глобальной).
Пусть состояние атмосферы в пространстве r = (l,j, s) макро-
масштабной области G (r )c G (r ) определяется вектором
K(r, t) = (u, v, w, p, T, q, qL, qW, к, e) дискретных значений анализа и про-
гноза , полученных на основе макромасштабной модели
в моменты времени t = tm (m = 0,1,...,M) с шагом t = tm - tm-1. Тогда
для определения состояния атмосферы на ограниченной территории G
при условии "t e[tm-1, tm ] решается задача, которая в векторном пред-
ставлении имеет вид:
DK , "t e[tm-1, tm ], "r e G
dt
9i(r, tm )=Km (r) m = 0, 1,..., M
В дальнейшем схема интерполируется с помощью интерполяции с кратными узлами полиномом Эрмита при кратности три (используется предыстория значения для каждой точки, которая вычисляется)
Схема распараллеливания вычислений
Сложность написания параллельных программ состоит в том, что необходимо в явном виде согласовывать структуру алгоритма решаемой задачи с архитектурой и структурой вычислительной системы. Как платформа для реализации, выбрана кластерная система благодаря сво­ей дешевизне по сравнению с системами другой архитектуры, масшта­бируемости и простоте в эксплуатации. Ситуация осложнена еще и тем, что средств отладки параллельных программ практически нет.
В основе работы лежит метод крупноблочного распараллеливания [2], исследование эффективности применения которого к выбранному классу задач проводится. Приведем основные принципы, которыми сле­дует руководствоваться при распараллеливании последовательных ал­горитмов. Эффективность работы будущей параллельной программы прямо зависит от соблюдения этих правил:
Важнейшим принципом есть декомпозиция последовательной программы на информационно независимые и сбалансированные по на­грузке блоки вычислений. То есть программу следует поделить на мак­симальное количество блоков, одновременное выполнение которых не является взаимоисключающим (необходимым и достаточным условием этого есть непересечение входных данных одного процесса с выходны­ми данными другого) таким образом, чтобы объемы вычислений в бло­ках оставались приблизительно одинаковыми.
При написании параллельной программы следует обращать вни­мание на то, чтоб в процессе выполнения не было простоев вычисли­тельных узлов, или свести их количество к минимуму. Одним из вари­антов избежания таких ситуаций является организация программного буфера данных, необходимых для вычисления: во время выполнения вычислений над одним пакетом данных происходит запрос и пересылка данных, необходимых для следующего блока вычисления. Такой способ организации работы параллельной вычислительной системы напомина­ет конвейер обычного процессора.
В вычислительных узлах есть много уровней памяти: регистровые блоки процессора, буфер данных процессора, кэш-память процессора, оперативная память, память на дисковой подсистеме, общая память всей системы параллельной обработки (в разных архитектурах последняя по скорости может находиться выше, чем дисковая подсистема) Поэтому следует уменьшать количество обращений к памяти низших уровней, которые замедляют общую скорость обработки. Решением этого служит фоновая подкачка данных.
Результаты экспериментального программирования
В ходе выполнении работы были проведенные эксперименты, ис­пользовавшие метод крупноблочного распараллеливания той части за­дачи, которая относится к вычислению правых частей системы уравне­ний - следующего этапа после интерполяции данных, описание распа­раллеливания которого приводится в работе [1]. Согласно этому методу, основной целью при распараллеливании задачи должно быть уменьше­ние количества межпроцессного взаимодействия и достижение того, чтобы время работы одной задачи намного превышало время запуска процесса и время, которое теряется на передачу сообщений между про­цессами. Для достижения этих результатов в алгоритме интерполяции исходная сетка распределялась между вычислительными узлами поров­ну. После вычислений все результаты собираются на главном узле.
100x100x40
120x120x50
150x150x60
180x180x80
200x200x100
Ниже приведенная диаграмма времени вычислений (в сек., ось Z) на разном количестве процессоров (от 1 до 8, ось X) при разных разме­рах мезомасштабной сетки (ось Y). Результаты показывают высокую степень распараллеливаемости и масштабируемости прогнозных вы­числений, которые в дальнейшем предполагается выполнить полностью на параллельной системе.




Эксперименты проводились на локальном кластере из восьми компьютеров следующей конфигурации: Celeron 1.3G 256MB 10Mbit LAN, OS: RadHat Linux 7.3 kernel ˜2.4.20, OS: Windows 2000 Professional, MPICH 1.2.5.2, gcc 2.95
Выводы
При анализе результатов эксперимента оказалось, что имеет место явление суперлинейного ускорения времени выполнения. Это явление объясняется уменьшением количества памяти, которая необходимое для одного процесса задачи с увеличением количества процессоров (уменьше­нием размера задачи которая приходится на один вычислительный узел). С уменьшением необходимого количества оперативной памяти уменьша­ется использование файла подкачки и переключение страниц памяти.
Такой результат говорит о перспективности дальнейших работ в направлении крупноблочного распараллеливания остальных частей этой модели и целесообразность применения метода при вычислении других задач этого класса.
ЛИТЕРАТУРА
Прусов В.А., Дорошенко А.Ю., Приходъко СВ., ТырчакЮ.М., Черныш Р.И. Методы эффективного решения задач моделирования и прогнозирования региональных атмосферных процессов // Проблемы программирования. Сб. науч. тр. Киев-2004. №2-3. С. 556-569.
Дорошенко А.Э. Математические модели и методы организации высо­копроизводительных параллельных вычислений. Алгебродинамический под­ход. // Киев: Научная Мысль, 2000. - 177 с.
Довгий С.А., Прусов В.А., Копейка О.В. Математическое моделирова­ние техногенных загрязнений окружающей среды // Киев: Научная мысль, 2000. - 247 с.
Воеводин В.В., Воеводин Вл.В. Параллельные вычисления // Спб.: БХВ-Петербург, 2002. 608 с.
Валъковский В.А. Распараллеливание алгоритмов и программ. Струк­турный подход // М.: Радио и связь, 1989. - 176 с.
Параллельные вычисления /Под ред. Г. Родрига: пер. с англ. // Под ред. Ю.Г. Дадаева. - Г.: Наука, 1986. - 376 с.

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

Л.П. Фельдман, Т.В. Михайлова
Донецкий Национальный Технический Университет, г. Донецк
Введение
Кластеры обладают высокой производительностью и «живуче­стью» вычислительных ресурсов и являются одним из примеров вычис­лительных систем с распределенной обработкой. Одной из основных проблем, возникающих при проектировании, эксплуатации и оптимиза­ции ВС с распределенной обработкой является выработка рекомендации для рационального использования ресурсов этой вычислительной сре­ды. Для решения этой задачи можно использовать непрерывные [1] и дискретные [2] аналитические модели кластеров.
Дискретная модель кластера с совместным разделением дискового пространства [3] с использованием методики построения дискретных Марковских моделей [4] представлена в [5].
Однако анализ кластерных систем с помощью дискретных Марков­ских моделей затруднен при большом количестве решаемых задач (M) на ПЭВМ. Количество состояний (L) дискретной Марковской модели резко возрастает при увеличении количества задач. Одним из вариантов реше­ния такой задачи в течение реального времени является распараллелива­ние алгоритма построения дискретной модели, предварительно оценив трудоемкость последовательного алгоритма.
Оценка трудоемкости алгоритма расчета характеристик функционирования кластерной системы
Алгоритм построения дискретной Марковской модели состоит из двух частей: вычислений матрицы переходных вероятностей и вектора стационарных вероятностей. Трудоемкость первой части вычисляется как
LхLх 2(N +1) 1СЛ + Kj *3NtC]l + K}
N
(1)
{((2N + 1)Cn2-+2n-2 -1) ta + Cn2-+2n-2[(4k2 - 5) + Xks ] tyMH}
s =1

K = N +V Cn_i (cn_i + cn_i + cn_1) +

где j=1
+ cm+n-1(cm +n-1 + cm+n-2),
Учитывая, что tCJl »tумн, формула (1) примет вид
Т1посл = L х L х 2(N +1) ton + K1 * 3N ton +
N
+ K1 {(2N + 4k2 + Xks-4)Cn2-+2n-2 } ton s=1







(2)

Для определения трудоемкости вычисления вектора стационарных вероятностей. Представим СЛАУ в виде _Р (k) = Р (0)Р K, (3)
где p (0) - начальное распределение вероятностей состояний, К - степень, при которой матрица не изменяется. Возведение матрицы Р в степень К потребует (1+log2K) операций
умножения матрицы. При последовательной реализации расчета векто­pa стационарных вероятностей общее количество вычислений опреде­ляется как
T2nocjl=(L3%MH + LL (L-1)*tCJl)* (1+logK)+L*(L* tyMH+ (L-1)* tCJl) или
72nocn=(L3 + L2 (L-1))*ton (1+log2K)+L* 2*(L-1)* ton (4)
Вычислительная сложность последовательного алгоритма по­строения дискретной Марковской модели кластера с разделяемой дис­ковой памятью определяется суммой формул (2) и (4) и составляет
Тпосл = L х L х 2(N +1) ton + K * 3N ton +
N

+ K1 {(2N + 4k2 + Xks-4)CN2-+2N-2 } ton +
N - 2
s=1
+ (L3 + L2(L -+ loq2K) ton + L * 2(L -1) * ton
(5)
Отображение параллельного алгоритма Марковской модели
на решетку процессоров
Пусть процессор SIMD-структуры имеет топологию- решетку процессорных элементов (ПЭ) p=n типа двумерной прямоугольной ре­шетки-тора. Каждый ПЭ может выполнить любую операцию за один такт; время обращения к запоминающему устройству пренебрежительно мало по сравнению со временем выполнения операции.
На каждом ПЭ с индексами i, j вычисляется один элемент матрицы переходных вероятностей pj. Алгоритм вычисления переходной вероят­ности между двумя произвольными состояниями приведен в [6].
Отобразим параллельный алгоритм построения матрицы переход­ных вероятностей размерности L. Временная сложность вычисления од­ного элемента этой матрицы определяется как
Т1парал = 5N ton + (2N + 4k2 + X.ks-4)Cn+N-2 ton
s=1 (6)
Всего возможно ненулевых элементов определяется величиной K1. В этом случае временная сложность параллельного алгоритма вычисле­ния матрицы переходных вероятностей вычисляется следующим образом
K N
Т1парал = ([—] +1){5N ton + (2N + 4k2 + Xks-4)Cn+\-2 ton}
p s=1 2 (7)
Временная сложность последовательного алгоритма определяется (5). Ускорение параллельного алгоритма вычисления матрицы переход­

ных вероятностей на решетке процессоров, определяемое, как отноше­ние формул (6) и (7) для различных значений количества обрабатывае­мых на кластере задач представлено на рис.1 для решетки процессоров p=16. При этом изменялась конфигурация кластера, т.е. увеличивалось количество устройств (серверов и/или дисков) в узлах. Эффективность параллельного алгоритма вычисления матрицы переходных вероятно­стей на решетке процессоров с увеличением количества решаемых за­дач М незначительно растет (рис. 2.) и мало изменяется (в сотых долях) с ростом количества процессоров.





8 Й) " 12 - ¦ -14 _,_ 16 18˜ я
* *
Рис. 2. Эффективность параллельного алгоритма вычисления матрицы переходных вероятностей нарешетке процессоров в зависимости от количестварешаемых задач М
Эффективность параллельного алгоритма вычисления матрицы переходных вероятностей на решетке процессоров зависит от значений
М, k2,k3,p.
Распараллелим вычисление вектора стационарных вероятностей на решетку процессоров размерности p=n2 с использованием блочного подхода методом Фокса [5, 6]. Размер блоков матрицы Р равен
(L/Vp) х (L/jpj.
Временная сложность вычисления вектора стационарных вероят­ностей определяется как

T2 парал = {2L3 / p * tcn + L / p 4^ tcde } (loq2K + 1) + L2 / p * ^ + L/4p (-[p˜ - 1) tcde
+

3
где 2L / p -количество операций сложения для каждого процессора;
tcde _ максимальная длительность рассылки по строкам решетки;
L / p tc$e - длительность рассылки блоков на одной итерации;
¦yjpp - количество итераций.
Порядок вычислений последовательного алгоритма - L (1 +log2K).
Ускорение и эффективность параллельного алгоритма вычисления вектора стационарных вероятностей на решетке процессоров представ­лены на рис. 3 и 4.

8

0.9
0.8
0.7

0.6
0.5

»'.4
Рис. 4. Эффективность параллельного алгоритма вычисления вектора стационарных вероятностей нарешетке процессоров в зависимости от количестварешаемых задач и процессоров
Временная сложность алгоритма построения модели Маркова оп­ределяется суммой формул (7) и (8).
Ускорение параллельного алгоритма асимптотически приближает­ся к количеству процессоров тора (рис.5) и не зависит от количества устройств (серверов и/или дисков) в узлах кластера. Поэтому в форму­лах оценки трудоемкости алгоритма вычисления матрицы переходных вероятностей можно отбросить слагаемые, соответствующие количест­ву устройств в узлах.

15

14

13


- k2-2
k3 2

k2-4
k3 2
- ¦-
k2-4
k3 4

M
8 10 12 14 16 18 20
Рис. 5. Ускорение параллельного алгоритмарасчета модели Маркова нарешетке процессоров в зависимости от количестварешаемых
задачМ
Эффективность параллельного алгоритма расчета модели Маркова на решетке процессоров в зависимости от количества решаемых задач М от устройств не изменяется (рис. 6).
e

0.95 0.9 0.85


- k2-2
k3-2

k2-4
k3-2
- ¦-
k2-4
k3 4



Puc. 6. Эффективностъпараллелъногоалгоритмарасчетамодели Маркова нарешетке процессоров в зависимости от количества
решаемых задач М
Выводы
Получены оценки трудоемкости алгоритма дискретной Марков­ской модели кластера с совместным использованием дискового про­странства, которые зависят от структуры вычислительной среды, от ко­личества обрабатываемых задач и от особенностей матрицы переход­ных вероятностей и оценки распараллеливания этого алгоритма на SIMD-структуры, позволяющие считать аналитическую модель на вы­сокопроизводительных ВС.
Литература
Клейнрок Л. Вычислительные системы с очередями // М.:Мир, 1979, -600с.
Последовательно-параллельные вычисления // Пер. с англ. - М.: Мир, 1985. - 456 с.
Авен О.И. и др. Оценка качества и оптимизация вычислительных сис­тем // М.: Наука, 1982. - 464 с.
Шнитман В. Современные высокопроизводительные компьютеры. Информационно-аналитические материалы центра информационных техно­логий, 1996: http//hardware/app_kis.
Фельдман Л.П., Дедищев В.А. Математическое обеспечение САПР. Моделирование вычислительных и управляющих систем // Киев: УМК ВО, 1992. - 256 с.
Фельдман Л.П., Михайлова Т.В. Методы оптимизации состава и струк­туры высокопроизводительных систем // Научные труды Донецкого государ­ственного технического университета. Серия «Информатика, кибернетика и вычислительная техника» (ИКВТ-2000). Донецк: ДонГТУ. 2000.
Михайлова Т.В. Параллельная реализация алгоритма построения дис­кретных моделей Маркова // Научные труды Донецкого государственного технического университета. Серия «Информатика, кибернетика и вычисли­тельная техника»(ИКВТ-2003).-Донецк: ДонГТУ.2003 (в печати).
Гергелъ В.П., Стронгин Р.Г. Основы параллельных вычислений для многопроцессорных вычислительных систем // Н.Новгород, ННГУ, 2001.
9. Корнеев В.В. Параллельные вычислительные системы // М., 1999. - 312 с.

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

Л.П. Фельдман, И.А. Назарова
Донецкий Национальный Технический Университет, г. Донецк
Введение
Моделирование реальных экономических, технических и других процессов, описываемых системами обыкновенных дифференциальных уравнений (СОДУ), представляет собой обширный класс задач, для ре­шения которых применение высокопроизводительной вычислительной техники не только оправдано, но и необходимо. Об этом свидетельству­ет знаменитый список проблем «большой вызов», в котором такие зада­чи занимают одно из ведущих мест [1]. Как показала практика, наиболее эксплуатируемым способом создания параллельных методов является распараллеливание хорошо исследованных и многократно апробиро­ванных последовательных численных алгоритмов [2]. Современный ка­чественный численный алгоритм решения СОДУ обязательно должен содержать механизм управления шагом интегрирования на основе ин­формации о погрешности решения на каждом шаге интегрирования [3]. В данной статье рассматривается эффективность альтернативных мето­дов оценки апостериорной локальной погрешности на базе параллель­ных алгоритмов решения линейных однородных СОДУ с постоянными коэффициентами для многопроцессорных ВС SIMD-архитектуры с рас­пределенной памятью.
1. Общая характеристика способов оценки апостериорной локальной погрешности
Известными методами оценки локальной погрешности решения СОДУ являются: правило Рунге; вложенные методы Рунге-Кутты (ВМРК); метод локальной экстраполяции Ричардсона.
Наиболее простой способ достижения поставленной цели - это удвоение или дублирование шага по правилу Рунге. На основе одной и той же формулы Рунге-Кутты порядка p вычисляют два приближения к решению в одной и той же точке сначала с удвоенным шагом: 2h, а за­тем независимо, дважды, с половинным шагом: h. Для точного решения
при переходе из точки xn к точке xn + 2 • h, y(xn + 2 • h) получают две
аппроксимации шаг 2 • h) и У2(2 шага h). Разность между этими значениями используется в качестве оценки локальной погрешности ин­тегрирования, в качестве решения принимается аппроксимация, полу­ченная с половинным шагом, как наиболее точная:
y(x + 2h) @ yj + (2h)p j + O(hp ) y(x + 2h) @ y2 + 2(hp)j+ O(hp)
Dy = y2 - yJ (1)
y(x + 2h) @ y3 = y2 +-pDy- + O(hp+j).

Процесс уточнения решения с половинным шагом y2, как видно из (1), повышает точность решения на единицу, и получил название ло­кальной экстраполяции. Данный способ оценки погрешности достаточ­но прост, однако имеет большие накладные расходы: объем вычислений на один узел сетки возрастает почти втрое.
Второй способ оценки локальной погрешности метода - вложен­ные методы Рунге-Кутты. Этот способ основан на использовании двух приближенных значений решения в одной точке, но в отличие от прави­ла Рунге приближения вычисляются не по одной, а по двум формулам различных порядков точностиp и p с одним и тем же шагом [3-4]:




Ti,j+1 •'- Ti,j

+
Ti,j Ti - 1,j (Hi/Hi-j)b - 1

(4)

Здесь величина b равна единице в общем случае, в тоже время для симметричных опорных методов, имеющих разложение погрешности по
степеням h2, b равно двум (каждая экстраполяция исключает две степе­ни h вместо одной).
Таблица 1. Экстраполяционная таблица

p
p+b
p+2b

p + (k - 2)b
p + (k - 1)b






T21
T22




T31
T32
T33







Tk-1k-1

Tk1
Tk2
Tk3

Tk-1k


В таблице (1) Tj - есть приближенное решение задачи Коши, по­лученное численным методом порядка p + (j -1) ¦ b с шагом hi. Величи­на соответствует аппроксимации наивысшего порядка, равного 2k,
в случае, если вычислены первые k строк экстраполяционной таблицы, а величина Tk-1kk соответствует аппроксимации порядка 2k-2. Для управ­ления шагом интегрирования естественно использовать выражение:


Таким образом, экстраполяционная технология Ричардсона вклю­чает численный метод решения задачи Коши, последовательность сеток, рекуррентное правило вычисления значений приближенного решения. Эффективность применения технологии локальной экстраполяции на­прямую зависит от правильного выбора и сочетания всех трех состав­ляющих этого метода.
2. Анализ вычислительной сложности последовательных методов решения СЛОДУ с постоянными коэффициентами
Исследование эффективности предложенных альтернативных спо­собов оценки локальной погрешности проводилось на следующем мно­жестве методов одного и того же порядка p:
- явный метод Рунге-Кутты и правило Рунге;
- экспоненциальный метод и правило Рунге;
- вложенные методы Рунге-Кутты;
- вложенные методы на основе экспоненциального;
- метод Грэгга-Булирша-Штера;
- экспоненциальный метод с локальной экстраполяцией.
Экспоненциальный метод относится к специальным методам чис­ленного интегрирования линейных СОДУ с постоянными коэффициен­тами, основанными на точном представлении решения в аналитической форме и вычислении матричной экспоненты.
Точным решением задачи Коши вида:
\ У = A • у
[У( *о) = уо (6)
является матричная экспонента
/ 7 ч Ah Ah V1 (hA))
у(Хо + h) = e • уо, e =^
)=0
Приближенное решение (6) можно построить, аппроксимировав матричную экспоненту отрезком ряда Тейлора:




причем, (7) определяет численный метод решения (6) порядка p [6].
Наиболее эффективным из известных последовательным методом, реализующим технологию локальной полиномиальной экстраполяции считается алгоритм Грэгга-Булирша-Штера(ГБШ), базирующийся на модифицированном методе средней точки [3]. Сравнение перечислен­ных методов
Наиболее трудоемким из рассматриваемых алгоритмов является метод ГБШ, число арифметических операций для него имеет порядок O(p2 • m2), где m - размерность системы уравнений, ap - порядок мето­да. Наименее трудоемким является метод вложенных форм Рунге-Кутты: O([2 p + 2] • m2) и вложенный метод на основе экспоненты: O([2 p + 6] • m2).
3. Анализ эффективности параллельных алгоритмов решения СЛОДУ с постоянными коэффициентами с учетом локальной
погрешности
Рассмотрим отображение алгоритмических схем приведенных ме­тодов на многопроцессорные вычислительные системы SIMD-структуры с распределенной памятью. Конфигурацию системы считаем фиксированной: число процессорных элементов и схема их соединения не изменяются в процессе счета. Каждый процессор может выполнить



- 4- вложенная экспонента: O(0.6m);
2) худший метод - метод ГБШ: O(0.3 ¦ [p2 + 2p + 4] ¦ m).
В качестве показателей эффективности параллельных алгоритмов применялись такие характеристики, как коэффициенты ускорения и эф­фективности. На рисунке 2 приведены коэффициенты ускорения для оценки реального параллелизма с учетом обмена, как функции размер­ности задачи.
Кр m











m


1

2

3

4

5

6

1000
Рис. 2. Зависимостъкоэффициентовускорения от порядка системы с учетом операций обмена
Определение характеристик параллелизма осуществлялось с по­мощью пакета Mathematica® (Wolfram Research Inc.), численный экспе­римент проводился на базе тестов для СОДУ, разработанных в НИВЦ МГУ [8].
Анализ полученных результатов позволяет сделать следующие выводы:
самым эффективным из рассмотренных последовательных мето­дов является вложенный метод с контролем погрешности на шаге;
лучшими параллельными методами с точки зрения трудоемко­сти являются вложенный экспоненциальный метод и экспоненциальный с локальной экстраполяцией;
преимущества методов на базе локальной экстраполяции прояв­ляются при получении высокоточных решений (10 ˜15 -10 ˜20) и для сложных правых частей.
Заключение
Анализ вычислительной сложности различных технологий опре­деления апостериорной локальной погрешности при решении задачи Коши имел своей целью управление шагом интегрирования в достиже­ние некоторой заданной точности с минимальными вычислительными затратами. Перспективным направлением дальнейших исследований является оценка влияния различных топологий многопроцессорных ВС на характеристики качества параллельных алгоритмов, исследование устойчивости полученных методов.
Литература
Rajkumar Buyya. High Performance Cluster Computing. Volume 1: Archi­tectures and Systems. Volume 2: Programming and Applications. Prentice Hall PTR, Prentice-Hall Inc., 1999.
Воеводин B.B., Воеводин Вл.В. Параллельные вычисления // СПб.: БХВ-Петербург, 2002. - 608с.
Хайрер Э., Нёрсетт С, Ваннер Г. Решение обыкновенных дифферен-циальныхуравнений. Нежесткие задачи: Пер. с англ. - М.: Мир, 1990. - 512с.
Bergman S., Rauber T., Runger G. Parallel execution of embedded Runge-Kutta methods.International Journal of Supercomputer Applications, 1996. 10 (1). P. 62-90.
Houwen P.J., Sommeijer B.P. Parallel ODE solver // Proceedings of the In­ternational Conference on Supercomputing. - ACM Press, 1990. P. 71-81.
Арушанян О.Б., Залеткин С.Ф. Численное решение обыкновенных дифференциальных уравнений на Фортране // М.: МГУ, 1990. - 336 с.
Бройнлъ Т. Паралельне програмування: Початковий курс: Навч. по-шбник/ Вступ. слово А. Ройтера. Пер. з шм. В.А. Святного. - К.: Вища шк.. 1997. - 358 с.
Арушунян О.Б., Залеткин С.Ф., Калиткин Н.Н. Тесты для вычисли­тельного практикума по обыкновенным дифференциальным уравнениям // Вычислительные методы и программирование, 2002. Т. 3. С. 11-19.

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

Н.П. Фефелов
Томский государственный университет систем управления ирадиоэлектроники (ТУСУР), г. Томск
Изучение архитектуры современных супер-ЭВМ освоение прин­ципов составления параллельных программ должно непременно вхо­дить в систему образования профессиональных программистов, чтобы сделать их мастерство конкурентоспособным на мировом рынке. По го­сударственному стандарту высшего профессионального образования (ГОС) 1995 года предусмотрена учебная дисциплина «Параллельное программирование», основное назначение которой ознакомить с парал­лельными вычислительными системами, методами параллельной обра­ботки информации, языками параллельного программирования, в том числе для транспьютерных систем.
На кафедре АСУ ТУСУРа преподавание этой дисциплины ведется по учебному плану в седьмом семестре с 1998 года в следующем объе­ме: лекций - 36 часов, практических занятий - 10 часов, лабораторных занятий - 16 часов, самостоятельная работа - 56 часов. Обеспечивал дисциплину доцент с базовым математическим образованием, работав­ший в 80-х годах на вычислительной системе ПС-2000 в Томском СКБ Геофизики.
В лекциях давались принципы построения многопроцессорных вычислительных систем и их классификация (по Флинну), рассматрива­лись принципы конвейерной и матричной обработки данных, методы передачи данных и коммутации. Как пример разбиралась архитектура вычислительной системы ПС-2000. Основное внимание в лекциях уде­лялось параллельным алгоритмам: каскадным вычислениям выражений, векторным и матричным вычислениям, решению систем линейных уравнений. В заключительной части давался обзор языков параллельно­го программирования, основной упор делался на параллельные расши­рения языка С.
Практические и лабораторные занятия проводились на однопро­цессорных персональных компьютерах. Они имели цель научить алго­ритмам крупноблочного параллелизма матричных операций для задач линейной алгебры. Студент должен был распределить вычисления по узлам, а затем составить программу на алгоритмическом языке для од­ного узла. Передача данных между узлами не предусматривалась.
В 2000 году тематика дисциплины была перестроена с учетом со­временных достижений параллельных вычислений, требования ГОС 1995 к этому времени устарели. За основу были взяты материалы ин­формационно-аналитического центра по параллельным вычислениям (МГУ) [1].
Основные темы лекций (ссылки даны на основные источники):
принципы параллельной обработки и супер-ЭВМ [2];
архитектура параллельных вычислительных систем и их класси­фикация. Список TOP-500 [1];
коммуникации и сети [1-3];
производительность супер-ЭВМ и программ [4], тесты ее про­верки [2];
парадигмы и модели программирования [3];
технологии параллельного программирования [2,3];
системы программирования на основе передачи сообщений. Ин­терфейс MPI [5].
На практических занятиях разбираются графы параллельных алго­ритмов. На примере обобщенной схемы вычисления полинома выявля­ется возможность проведения каскадных параллельных вычислений над массивами и их реализация на векторных процессорах. Рассматривают­ся также методы крупноблочного разбиения в параллельных матричных вычислениях. В заключение происходит знакомство с основными функ­циями MPI путем составления простых программ передачи сообщений.
Для проведения лабораторного практикума на кафедре создан учебный кластер из восьми узлов на основе персональных ЭВМ и ло­кальной сети кафедры. На жестком диске каждого компьютера, входя­щего в кластер, выделен раздел, на котором размещается программное обеспечение (ОС Linux Red Hat 7, библиотека LAM и студенческие про­граммы). В другое время компьютеры кластера могут использоваться в обычном режиме учебной работы (раздел диска для кластера тогда не­доступен).
В первой лабораторной работе с помощью последовательных про­цедур моделируются векторные операции и на их основе составляются программы по алгоритмам каскадных вычислений, например численное интегрирование. Для освоения технологии MPI параллельную програм­му вычисления интеграла на языке Фортран предлагается переписать на языке С. Используются различные функции передачи данных. Далее студентам предлагается разобраться в программах, взятых из различных руководств по использованию MPI. Можно составить программу для матричных вычислений.
В ГОС 2000 дисциплина «Параллельное программирование» от­сутствует, но в рабочем учебном плане кафедры АСУ она оставлена как дисциплина, установленная вузом. Меняется ее содержание. В число обязательных дисциплин по новому стандарту включены «Теория вы­числительных процессов», где можно изложить парадигмы параллель­ного программирования, а также «Архитектура вычислительных сис­тем», где предусмотрено изучение принципов построения супер-ЭВМ. В дисциплине «Параллельное программирование» решено основное внимание уделить не алгоритмам (это удел прикладных математиков), а технологиям параллельного программирования, в частности MPI как наиболее распространенной.
Кафедра сотрудничает с институтом оптики атмосферы СО РАН. Обеспечен удаленный доступ на кластер института (10 двухпроцессор­ных узлов) для учебно-исследовательской работы студентов. Кроме то­го, кафедра АСУ имеет небольшой опыт сотрудничества с японским центром морских наук и технологий (Иокогама), где установлен самый мощный суперкомпьютер Earth-Simulator. Надеемся на продолжение со­трудничества.
Литература
http://www.parallel.ru - Информационно-аналитический центр по па­раллельным вычислениям в сети Интернет.
Воеводин В.В., Воеводин Вл.В. Параллельные вычисления // СПБ.: БХВ, 2002.
Немнюгин С.А., Стесик О.Л. Параллельное программирование для многопроцессорных вычислительных систем // СПБ.: БХВ, 2002.
Хокни Р., Джессхоуп К. Параллельные ЭВМ // М.: Радио и связь, 1986.
Шпаковский Г.И., Серикова Н.В. Программирование для многопро­цессорных систем в стандарте MPI // Минск: Изд-во БГУ, 2002.

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

С.К. Черников, А.Н. Ашихмин
Казанский физико-технический институт им. Завойского, г. Казань
Для многих образовательных и научно-исследовательских органи­заций России, у которых имеется потребность в мощных вычислитель­ных ресурсах, кластеры, созданные из общедоступных компьютеров на базе процессоров AMD и недорогих Ethernet-сетей, являются естествен­ной альтернативой недоступным из за высокой стоимости суперкомпью­терам. В то же время эффективность используемых алгоритмов в значи­тельной степени будет определяться быстродействием коммуникацион­ного оборудования, обеспечивающего среду передачи сообщений между вычислительными узлами. При создании программ ориентированных на использование на вычислительных кластерах необходимо специальным образом распределять данные между процессорами, чтобы минимизиро­вать число пересылок и объем пересылаемых данных. В этой связи пред­ставляется целесообразным проектирование вычислительного кластера под определенный класс задач одновременно с разработкой программно­го продукта, учитывающего как особенности задач класса, так и кон­кретную архитектуру кластера. Результатам создания такого программ­но-аппаратного комплекса для решения задач механики деформирования сложных машиностроительных конструкций методом конечных элемен­тов (МКЭ) и посвящен настоящий доклад.
1. Конструкция и технические характеристики кластера АРКО-9А2200
Кластер АРКО-9А2200 представляет собой 9-процессорный вы­числительный комплекс, построенный на базе процессоров AMD ATH­LON. Комплекс включает в себя:
• 2-х процессорный системный блок на базе системной платы TYAN Tiger с двумя процессорами ATHLON MP 2200+ и сетевым адапте­ром Gigabit Ethernet NARDLINK HA-64G, установленным на шине
PCI64;
7 1-процессорных системных блоков на базе системной платы MI-CROSTAR MS-6570 (nForce 2 chipset) с процессором ATHLON XP 2200+ и сетевым адаптером Gigabit Ethernet NARDLINK HA-32G, установленным на шине PCI32;
8-ми портовый Gigabit Ethernet-коммутатор NARDLINK HS-8G.

<<

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

СОДЕРЖАНИЕ

>>