автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Графическая объектная модель параллельных процессов и ее применение в программных комплексах численного моделирования

На правах рукописи

Востокин Сергей Владимирович

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

Специальность: 05.13.18 —Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ

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

□ОЗОБ4Э52

Самара 2007

003064952

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

Научный консультант: доктор технических наук, профессор

Прохоров Сергей Антонович

Официальные оппоненты: доктор технических наук, профессор

Гергель Виктор Павлович

доктор технических наук, профессор Олейников Александр Яковлевич

доктор технических наук, профессор Кораблин Михаил Александрович

Ведущая организация: Федеральное государственное унитарное

предприятие Государственный научно-производственный ракетно-космический центр «ЦСКБ-Прогресс», г. Самара

Защита состоится 19 октября 2007 г. в 10 часов на заседании диссертационного совета Д 212.215.05 при Государственном образовательном учреждении высшего профессионального образования «Самарский государственный аэрокосмический университет имени академика С.П. Королева» по адресу: 443086, г. Самара, Московское шоссе, 34, ауд. 209.

С диссертацией можно ознакомиться в библиотеке СГАУ.

Автореферат разослан «23» августа 2007 г.

Ученый секретарь диссертационного совета

д.т.н., профессор

Калентьев А.А.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Новые возможности численного моделирования связаны с интенсивным развитием сетевых технологий. Агрегация вычислительных ресурсов позволяет добиться очень высокой пиковой производительности и снижения стоимости вычислительных экспериментов. С другой стороны, имеется ряд важных задач математического моделирования, которые обуславливают потребность во все более мощной вычислительной технике. Это задачи параметрической оптимизации; задачи исследования асимптотического поведения моделей, основанных на системах дифференциальных уравнений; сеточные и конечноэлементные модели; модели взаимодействия частиц.

Однако применение агрегированных вычислительных ресурсов в численном моделировании сдерживается из-за отсутствия средств и методов организации вычислений, адекватных новому типу вычислительной среды. В агрегированной среде исполнения возникают проблемы организации вычислений, обусловленные программной и аппаратной гетерогенностью, ненадежностью и распределенным характером среды исполнения, большим числом процессов, сложностью управления ресурсами. Обычные методы реализации параллельных численных алгоритмов с использованием MPI сложно масштабируются на новый тип вычислительных сред. Технологии, реализованные в грид-системах на основе программного обеспечения Globus, gLite, ARC, решают задачу организации крупно-гранулярных вычислений. В альтернативных индустриальных технологиях, например, в системе координации Jini, технологиях RMI, CORBA, DCOM не предлагается способов описания вычислительных процессов в целом.

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

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

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

Традиционный подход к преодолению сложности разработки численных методов для параллельных компьютеров лежит в области автоматизации программирования. Ведутся исследования, цель которых создание распараллеливающих компиляторов, анализаторов последовательного кода на предмет выявления параллелизма. Разрабатываются непроцедурные методы программирования численных моделей. В данном направлении известны работы А.П. Ершова, В.В. Воеводина, В.А. Вальковского, Л.Дж. Баера (L.J. Ваег) и многих других отечественных и зарубежных ученых. Такие подходы являются эффективными для узкого класса алгоритмов и вычислительных систем.

Представление алгоритма и среды его исполнения в форме модели дискретной системы широко применяется для анализа. В этой области работали такие ученые как А. Нуэли (А. Pnueli), K.M. Чанди (K.M. Chandy), Я. Мизра (J. Misra), Л. Лампорт (L. Lamport) и другие. Однако анализу подвергаются готовые реализации алгоритмов. Поэтому методы анализа обычно не учитывают вопрос о существовании эффективной реализации той или иной модели, хотя известно, что некоторые простые дискретные модели не возможно эффективно реализовать в распределенных средах.

В диссертации рассматривается альтернативный подход, использующий специальные модели в качестве основы алгоритмизации и программирования численных методов. Эти модели представляют собой схемы параллельных алгоритмов численного моделирования. Данный подход был предложен М.И. Коулом (M.I. Cole) и развивается в работах С. Макдональда (S. MacDonald), П.К. Берзигиярова и других авторов. Тем не менее, недостаточно исследованными следует считать вопросы построения эффективно реализуемых универсальных моделей дискретных систем с использованием объектно-ориентированной парадигмы и методов

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

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

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

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

1) Проанализировать известные модели, методы и программные системы в области параллельного и распределенного программирования с целью определения требований к модели дискретной системы.

2) На основе сформулированных требований построить модель дискретной системы, которая описывает алгоритмы численного моделирования в произвольной среде исполнения.

3) Обосновать пригодность построенной модели для описания алгоритмов численного моделирования и возможность эффективного исполнения модели в распределенной вычислительной среде.

4) Разработать язык и метод описания прикладных программ численного моделирования в терминах предложенной модели дискретной системы.

5) Выполнить исследование адекватности предложенной модели дискретной системы в вычислительных экспериментах с использованием дискретно-событийной имитационной модели.

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

Методы исследования. При проведении исследований были использованы элементы теории множеств, математической логики, теории графов. Результаты теоретических исследований подтверждены вычислительными экспериментами, экспериментами с имитационными моделями, а также реализацией прикладных алгоритмов численного моделирования в разных предметных областях.

Основные научные результаты, полученные автором и выносимые на защиту.

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

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

3) Методика построения параллельных алгоритмов численного моделирования, включающая средства описания схем вычислений, алгоритмы кодирования схем, примеры прикладных численных методов.

4) Результаты анализа эффективности предложенного метода моделирования.

5) Программный комплекс дискретного моделирования вычислительных процессов и библиотека прикладных программ численного моделирования.

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

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

2) Описан метод визуализации модели, на котором основывается декомпозиция параллельного вычислительного алгоритма на совокупность последовательных процедур, а также метод построения алгоритмов, реализующих функциональные отношения модели по ее визуальному представлению в виде множества диаграмм. Данный метод, в отличие от известных подходов (CODE, HeNCE), соответствует современной практике программирования.

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

4) Предложена общая структура алгоритмов управления вычислениями с использованием модельного описания в форме паттерна, названного «Постоялец-Посетитель». Ее применение, в отличие от известных подходов, позволяет отделить код численного метода от управляющего кода при сохранении эффективности вычислений; она пригодна для широкого класса вычислительных сред.

5) Предложен метод имитационного моделирования вычислительных процессов, описанных в терминах графической объектной модели, и получены новые экспериментальные результаты дискретно-событийного моделирования исполнения вычислений в гетерогенных вычислительных средах с флуктуирующими характеристиками производительности и пропускной способности.

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

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

Построенные в работе модели процессов базируются на использовании апробированных формальных методов спецификации дискретных систем. Достоверность выводов подтверждена результатами проведенных вычислительных экспериментов на реальном оборудовании и имитационными экспериментами с моделями.

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

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

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

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

4) упростить подготовку модельных экспериментов с привлечением больших вычислительных ресурсов на основе применения каркасных библиотек, описывающих типовые вычислительные процессы.

Практическим результатом диссертации является разработка программного комплекса параллельных и распределенных вычислений GraphPIus, включающего утилиты описания визуального представления схем вычислительных процессов, транслятор схем процессов, кодогенератор, интерпретатор, различные варианты среды времени исполнения, в том числе для проведения имитационных экспериментов с моделями процессов, и другие. Основные компоненты программного комплекса официально зарегистрированы Федеральной службой по интеллектуальной собственности, патентам и товарным знакам: «Модуль многопоточного исполнения моделей программного комплекса проекта Граф Плюс» — свидетельство об официальной регистрации №2007611206; «Транслятор моделей программного комплекса проекта Граф Плюс» — свидетельство об официальной регистрации №2007611201. Общий объем исходного кода данных компонент превышает 8000 строк.

Результаты диссертации внедрены в ГОУ ВПО «Самарский государственный аэрокосмический университет», ГОУ ВПО «Самарский государственный технический университет», ГОУ ВПО «Поволжская государственная академия телекоммуникаций и информатики», ГОУ ВПО «Самарский государственный экономический университет», ОАО «Самаранефтегаз» (в разработках ООО ИК «СИБИНТЕК»), ООО «Mercury

Development Russia», ГУЗ «Самарский областной медицинский информационно-аналитический центр». Программный комплекс дискретного моделирования вычислительных процессов, примеры алгоритмов и технические описания доступны на официальном сайте Самарского государственного аэрокосмического университета по адресу http://graphplus.ssau.ru.

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

Связь исследований с научными проектами. Теоретические и практические результаты диссертационной работы использованы при выполнении госбюджетных работ в рамках персонального гранта Министерства образования Российской Федерации и Правительства Самарской области на проведение исследований в области гуманитарных, общественных, технических наук и естествознания по теме «Разработка методов визуального проектирования управляющих алгоритмов для систем распределенной пакетной обработки заданий», шифр темы 17Г-Р077-090-050 В2; при выполнении исследовательских работ по гранту Американского фонда гражданских исследований и развития (CRDF Project SA -014-02).

Апробация работы. Результаты работы докладывались и обсуждались на всероссийских и международных научно-технических конференциях:

- Научно-технической конференции с международным участием «Перспективные информационные технологии в научных исследованиях, проектировании и обучении», Самара, 2006 г.;

-Третьей Всероссийской научной конференции «Математическое моделирование и краевые задачи», Самара, 2006 г.;

- Второй международной конференции «Распределённые вычисления и грид-технологии в науке и образовании», Дубна, 2006 г.;

- Третьей международной конференции «Параллельные вычисления и задачи управления», Москва, 2006 г.

- Международных конференциях «Надежность и качество», Пенза, 1999, 2002-2006 гг.;

- Всероссийской межвузовской научно-практической конференции «Компьютерные технологии в науке, практике и образовании», Самара, 2005 г.;

- Четвертом международном научно-практическом семинаре «Высокопроизводительные параллельные вычисления на кластерных системах», Самара, 2004 г.;

- Международной конференции «Интерактивные системы. Проблемы человеко-машинного взаимодействия», Ульяновск, 2003 г.;

а также на Всероссийской молодежной научной конференции «XXIII Гагаринские чтения», Москва, 1997; Всероссийской студенческой научной конференции «Королевские чтения», Самара, 1997; Первой и Второй международной молодежной школе-семинаре БИКАМП, Санкт-Петербург, 1998 и 1999; IV Всероссийской научной конференции студентов и аспирантов

«Техническая кибернетика, радиоэлектроника и системы управления», Таганрог, 1998; VI Международной конференции "Математика, компьютер, образование", Москва, Пущино, 1999.

Публикации. По теме диссертации опубликовано 42 работы, в том числе 3 монографии, 29 статей, из них 13 — в изданиях, входящих в перечень ведущих рецензируемых научных журналов и изданий, выпускаемых в Российской Федерации, в которых должны быть опубликованы основные научные результаты диссертации на соискание ученой степени доктора наук; а также получено 2 свидетельства о регистрации программ для ЭВМ, опубликован сайт в сети Интернет на сервере Самарского государственного аэрокосмического университета.

Структура и объем работы. Диссертация состоит из введения, пяти глав, заключения, библиографического списка и приложений; содержит 266 страниц основного текста, 84 рисунка, 18 таблиц. Библиографический список включает 206 наименований литературы.

СОДЕРЖАНИЕ РАБОТЫ

Во введении обоснована актуальность работы, дана ее общая характеристика, сформулированы цель и задачи исследования.

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

Модель вычислений должна иметь четкую и однозначную интерпретацию. Поэтому представляет интерес способ описания семантики исполнения модели. Обычно в моделях предполагается наблюдаемость глобального состояния. Примером являются модели Р. Милнера (R. Milner), Ч. Хоара (C.A.R. Ноаге), темпоральная логика А. Нуэли (A. Pnueli), сеть Петри. Дж. Халперн (J. Haipern) и И. Мозес (Y. Moses) предложили модель, в которой глобальное состояние неизвестно, а вычисления интерпретируются как накопление сведений при взаимодействии. Все эти модели основаны на принципе локальности действий и представлении вычислений в форме истории. Историю представляют как последовательность, дерево событий (метод Р. Милнера (R. Milner)) либо состояний. Использование состояний или смешанная форма представления историй характерна для логических моделей, например, в логике Л. Лампорта (L. Lamport). Существует несколько способов применения формализмов. Выделяются методы, целью которых является синтез параллельных программ с желаемыми свойствами. Методы распараллеливания используются в процедурных описаниях (проект V-Ray), в функциональных и логических

языках (проект Т-системы) и непроцедурных предметно-ориентированных описаниях (язык Норма). При распараллеливании процедур различают задачи о распараллеливании циклических, ациклических фрагментов и распараллеливании выражений. Исследовались методы статического и динамического распараллеливания. Специальным методом синтеза является предложенный K.M. Чанди (K.M. Chandy) и Я. Мизра (J. Misra) метод последовательного улучшения, позволяющий постепенно переходить от спецификации к реализации параллельного алгоритма. Наиболее популярны методы анализа, обосновывающие свойства имеющихся объектов. Большинство методов используют подход, предложенный С. Овицки (S. Owicki) и Д. Грисом (D. Gries). Формальные теории имеют форму алгебр или логик. Исследование моделей может выполняться путем «исчерпывающего» анализа историй, обобщенных рассуждений и имитационными методами.

Новая модель вычислений должна учитывать особенности известных моделей. В ■ параллельном программировании выделяют модели, не использующие понятие потока исполнения или асинхронные (Б.Б. Нестеренко, В.А. Марчук). Это модели с событийным, потоковым и динамическим управлением. Более традиционными и удобными в реализации являются модели с потоком управления. При реализации также имеет значение способ структурирования кода, который может соответствовать модели SPMD «одна программа - много данных» либо MPMD «много программ - много данных».

Для описания распределенных вычислений наиболее адекватны модели процессов. Необходимыми допущениями в таких моделях являются рассмотрение отказов и учет времени доставки сообщений. Н. Линч (N. Lynch) и Л. Лампорт (L. Lamport) классифицируют модели процессов на три группы: модели с разделяемыми переменными, модели распределенных процессов и другие модели, к числу которых относят модель Ч. Хоара (C.A.R. Ноаге), рандеву, удаленный вызов процедуры (RPC). Группу моделей распределенных процессов разделяют по признакам топологии коммуникаций, синхронности, отказам и способам буферизации. Несмотря на отсутствие единой теории, объединяющей модели, описаны алгоритмы, обосновывающие возможность организации вычислений в распределенных ненадежных средах, например, алгоритм распределенной транзакции М.Д. Скина (M.D. Skeen); методы синхронизации часов Д. Долева (D. Dolev), Дж. Халперна (J. Halpern), Х.Р. Стронга (H.R. Strong); алгоритм получения мгновенного снимка K.M. Чанди (K.M. Chandy) и Л. Лампорта (L. Lamport); протоколы линка, систематизированные A.B. Ахо (A.V. Aho), Дж. Ульманом (J. Ullman), и другие. Поэтому необходимо, чтобы специальная модель распределенных вычислений очевидным образом сводилась к известным моделям, для которых получены эффективные алгоритмы реализации.

При разработке новой модели вычислительных процессов требуется учитывать влияние системного программного обеспечения, а также средств автоматизации программирования. От этого зависит удобство использования и совместимость нового метода с другими аналогичными технологиями. В качестве общепринятых средств программирования в главе 1 рассмотрены API

операционных систем (Win32, POSIX); стандартные средства Open MP, MPI, PVM; сокеты; механизмы удаленного вызова; промежуточное программное обеспечение грид-систем (GT, gLite, ARC и др.). Также рассмотрены языковые средства; прикладные библиотеки на основе MPI и PVM; библиотеки и системы программирования, использующие каркасы; инструменты автоматизированного распараллеливания; средства автоматизированного проектирования.

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

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

Предлагаемая модель основана на объектной декомпозиции параллельного алгоритма, реализующего численный метод. Все используемые в алгоритме переменные сгруппированы в объекты. Структура произвольного параллельного алгоритма образуется объектами двух типов — «неподвижными» или Р-объектами и «подвижными» или М-объектами.

Обозначим символом Р множество всех Р-объектов, а М — множество всех М-объектов. Для изображения Р-объектов на рис. 1 используются квадраты (объекты р\...р6 из множества Р). Для изображения М-объектов используются кружки (объекты /Н|.../и5 из множества М). При помощи сплошных и пунктирных линий на рис. 1 показаны статические (не меняющиеся в процессе исполнения) отношения между объектами. Пунктирной линией показаны связи между Р- и М- объектами. Р-объект может

р2бр

ПЪеМ J р5еР

Рис. 1. Мгновенный снимок структуры параллельного вычислительного процесса в модели ОгарЬР1из

быть связан с несколькими М-объектами: í.: Рх м {0,1}. При этом М-объект связан строго с одним Р-объектом: Vx е М: Зрир2: р, * р2 л L(pux) = 1 л L(p2,x) = 1. Отношение L задает подмножество «локальных» М-объектов для каждого Р-объекта, которое может быть пустым. Но каждый М-объект обязательно связан с Р-объектом: V*e М.Зу е Р: L(y,x) = 1. Связи между Р-объектами показаны сплошными ориентированными линиями. Соответствующее данной связи отношение обозначается как /У:РхР->-{0,1}. Подграф, описывающий отношение N, является ориентированным, то есть для произвольной модели N(x,y) = 1 Ф N(y,x) = 1.

Вычисления на модели интерпретируются как одновременный обход несколькими М-объектами структуры из Р-объектов. Часть М-объектов в некоторый момент времени может находиться в неактивном состоянии. На рис. 1 это объект /и4, обозначенный пунктирным контуром. Находясь в активном состоянии, М-объекты могут либо перемещаться по связям между Р-объектами (показано стрелками), либо посещать Р-объект (передается помещением кружка внутрь квадрата). В момент посещения происходит изменение состояния взаимодействующей пары объектов, и возможна активация неактивных М-объектов, связанных с посещаемым Р-объектом. После посещения объекта р М-объект может направиться к любому из соседних объектов р': N(p,p') = 1, снова посетить объект р или перейти в неактивное состояние.

Далее в главе 2 на основе рассмотренного вербального описания строится формальная спецификация модели. Она использует математический аппарат TLA (temporal logic of actions), предложенный Лампортом (L. Lamport) Введем функции, сопоставляющие объект модели GraphPlus переменной: о[]: Obj —> Var. Будем считать, что все темпоральные переменные в формулах модели вычислений заданы через функции о, а темпоральные константы заданы обычным способом. Определим множества объектов модели GraphPlus:

Р с Obj, М с: Obj, ^sObj;

PnM = 0, Po{£> = 0, Mn{s) = 0;

Pt = Pu{£), M,=Mu¡s}. Здесь £ описывает специальный «нуль» объект, а Р, и М, — множества Р- и М-объектов, расширенные «нуль» объектом. Обозначим домены значений объектов модели, как DP с Val и DM с Val. Каждому М-объекту будут соответствовать переменные модели, задаваемые функциями m[]:M->Vö, /?i[]: М -> VM, а каждому Р-объекту — функциями ?[]:P->V„ £>[]: Р-» VP, »I]:P->VN.

Переменные М-объектов íñ[] принимают значения Р-объектов, которые они собираются посетить. Переменные Р-объектов в свою очередь, принимают значения М-объектов, посещающих их в некоторый момент времени. Переменные и[] служат для хранения Р-объектов, к которым

" Lamport L. Specifying Systems. The TLA+ Language and Tools for Hardware and Software Engineers. Addison-Wesley, 2002.

произойдет переход после «посещения». Наконец, переменные т[] и р[] определяют состояние конкретного моделируемого вычислительного процесса. Множества переменных различны и попарно не пересекаются: V- с Уаг, Ум с Уаг, Ур с Уаг, Ур с Уаг, Ум с Уаг; V« о (Ум и УР и Ур о Ун) = 0 ; Ум о (Уй о УР и Ур о Ум ) = 0 ;

о (Ум и УЙ и Ур и Уы) = 0; УР о (Ум и УЙ и УР и Уы) = 0; Умп(УмиУЙиУриУР)=0.

Отношения инцидентности N и £ между объектами модели будем записывать в префиксной форме в виде специальных предикатов //(■,•) и £(■,■).

Для описания динамики изменения состояния в модели СгарИПиБ определим четыре функции:

пекР{-,-): Ор х Ом -» —новое состояние посещаемого Р-объекта; пек\Ц-,-): й,, х Ом -> — новое состояние посещающего М-объекта; асИ\<а1е(-,-,-): М х Б,, х -> Р+— функция активации локальных М-объектов; пех1(-,-): О,, х Р+ — переход М-объекта к следующему Р-объекту. Обозначив множество всех отношений в модели через 9? = //и^ипеп'Ри/?еи'Л/ иасИ\>а!еипех1, определим модель ОгарЬР1из как

Ч" = (Р,М,9!,Ф), (1)

где Ф — формула TLA, описывающая динамику поведения вычислительного процесса. Структура формулы определяется выражениями (2)-(9) в соответствии с графом модели, пример которого показан на рис. 1. Формула строится с учетом обеспечения минимальной подробности, необходимой для адекватной передачи состояния Р- и М- объектов; минимального влияния на реализацию модели; возможности изучения на модели состояний, отображающих одновременность выполнения переходов и посещений для М-объектов.

Формула, описывающая дискретную систему в логике TLA по Лампорту,

ф== / л ll[n]y af . (2)

Предикат начального состояния вычислений в модели GraphPlus

(3)

•t'T

/== лЗу б М : (т[у]# £лт[у]е Р)дУхеР: р[дг] = Я|>] = в

л Vx е Р.Ууе М : р[х] е DP лт[у] е

Начальное состояние системы (3) предусматривает наличие хотя бы одного М-объекта в состоянии перемещения и правильно проинициализированных переменных численного метода. Функция состояния, представляющая собой кортеж из всех переменных, используемых для представления конкретной модели,

/== (рМ:лбР;й[Я:уеМ;л[*]:*еР;рМ:хеР;1и[Я:^бМ). (4)

Формула для N описывает множество допустимых действий (событий) в модели вычислений. Это множество разбито на два подмножества А\ и Л2. Их атомарность (взаимная независимость) следует из определений (7)-(9). Формула для N имеет вид

л/

Ы== \/Зхе Р,Эу е М : Л,(х,у) ^

\/Эх е Р,3уе М : Аг(х,у)

Формула, описывающая условия «справедливости» выполнения действий для модели, записывается в виде

л-г

л V* е Р,Уу е М: 5РГ(А,(х,у)) ^

а \/лг е Р, V)/ & М : И-7^ (у1г(х, у))

Группа действий А, задается формулами (7), (8).

А,(х,у)=-л р[х] = елт[у] = х л = у

лр'М = пеыР(р[х],т\у))

лт'[у] = пе\уМ(р[х~\,т[у}) (7)

л п'[х] = пех1(р[х],т[у])

лЬоса!(х,у)

липсИапвесЦ УпМ{р[х1 рЫ,п[х],т[у]}^ {"Ш-Щ,к)}))

А/

Ьоса1(х,у)== Мк е М,£(*,£) : улйщ= б

л т'[£] = асШа1г(к,х,у) улйЩ/Е л т'[к]= т[А]

(8)

В формулах (7), (8) переменные х и у являются темпоральными константами. Каждой паре из Р-объекта и М-объекта сопоставляется индивидуальное действие А\. Формула (7) утверждает, что действие А\ возможно, если Р-объект не занят (р[х\ = е), а М-объект из рассматриваемой пары (лг^у) направляется к Р-объекту х (т[у] = х). Результатом действия А, являются следующие изменения в состоянии модели. Пара объектов (х,у) переходит в состояние посещения (р'[х] = у). Изменяется состояние Р-объекта, описывающего моделируемый вычислительный процесс

(р'[х] = пгыР(р[х},т[у'\)). Изменяется состояние посещающего М-объекта

(л)'0] = newAf(p[x],m[y])). Вычисляется следующий Р-объектдпя посещения, и он сохраняется в специальной переменной (л'[х] = лех/(р[х],т[у])). Происходит активация некоторых неактивных М-объектов, связанных с рассматриваемым Р-объектом = activate(k,x,y)).

Для соблюдения атомарности в формулах (7) и (9) учитывается, что остальные переменные модели не изменяются. Для этого служит специальное действие unchanged. В нем Уф— все переменные, входящие в формулу Ф (2).

Действие Аг описывает, каким образом изменяется состояние Р-объекта после посещения (9).

а/

Аг (,Х, у) ==А /)[*] = у л = л

А Е

А«Т[у]=ЙВД (9)

AN(m[y],m'iy})

л unchanged(V„, \ 1р[х],т[у)})

Условием готовности действия Ai является наступление состояния посещения (р[х] = улт[у] = х). Действие состоит в присвоении переменной М-объекта iii[y] значения следующего посещаемого Р-объекта или нуль-объекта в случае перехода в неактивное состояние. Направление перехода предварительно сохраняется в переменной «[jr] в действии А\. Признаком перехода Р-объекта в свободное состояние является смена значения переменной р[х] на е. Другие переменные, кроме переменных Дх] и т[у], при выполнении действия Аг не изменяются.

Множество допустимых действий связано с графической структурой модели. Действия (7) соотносят каждый подвижный М-объект каждому неподвижному Р-объекту, определяя, при каких условиях возможно соответствующее посещение и последующая активация новых М-объектов. Они также описывают, как изменяется состояние взаимодействующей пары объектов. Действие (7) должно быть «справедливо в строгом смысле» для предотвращения ситуации отталкивания одного М-объекта другим во время посещения некоторого Р-объекта. При реализации модели на многопоточной машине это обеспечивается путем организации очереди запросов на посещение с операцией помещения в очередь, реализованной в критической секции.

Действия (9) задают переход Р-объекта в исходное состояние после посещения, а также управляют переходом М-объекта к следующему Р-объекту или в неактивное состояние после посещения Р-объекта. Для действий (9) достаточна «справедливость в слабом смысле», так как выполнение других действий не может отменить условий их готовности. При реализации модели это гарантируется диспетчером потоков операционной системы.

Далее для исследования адекватности приводится анализ простейших моделей процессов, описывающих взаимодействие конкурентного и кооперативного типа. Для этого выполняется табличное определение функций вычислительной модели activate, next, newP, newM, отношений L,N и предиката

начального состояния. В предположении о временах выполнения действий модели строятся истории, для которых формулы вида (2) интерпретируются в истину и выполняются соответствующие утверждения о возможности эффективной реализации модели в распределенной среде исполнения.

Для практического использования модели предложен способ графического представления функций activate, next, newP, newM и отношений инцидентности L, N. Идея заключается в изображении каждого Р-объекта в виде ориентированного размеченного графа. Граф описывает алгоритм вычисления функций activate, next, tiewP, newM, а также представляет локальные М-объекты и связи с остальными Р-объектами.

Определим для графа Р-объекта множество пометок вершин. Данное множество будет включать в себя четыре попарно не пересекающихся класса пометок: In с {in} x F, Out с {out}* Fx Р , Do с {do} х F и Count с {count} xfxN, где N — множество натуральных чисел. Пометки из данных классов на графе будем записывать в виде ш(-), out(v), do(-) и count{-,-). Элементами множества F в определении классов пометок вершин являются функции, изменяющие состояние пары из М- и Р-объекта: F : DP х DM -> Dp х DM. Пусть для каждого графа, обозначающего Р-объект, определен способ нумерации вершин. Тогда функцию пометок вершин для графа можно записать в виде М(У) : N -> InvOutvDokjCoum.

Аналогичным образом введем функцию пометок дуг графа M(E):NxN Ifi^jlf и New. Множество пометок дуг включает три класса: Ift с (///} х м х N, If с {if} х я х N и New ç {new} x м x N, где P обозначает предикат на паре состояний М- и Р-объектов Р : D,, x DM -» {0,1}. Пометки из данных классов на графе будем записывать в виде yï(v), </(•,•), new(у).

Примером использования пометок служат графы кооперативного взаимодействия процессов, показанные на рис. 2. Здесь использованы специальные обозначения для функции, не изменяющей состояние М- и Р-объекта из пары (=), и предиката, возвращающего истинное значение для произвольных значений состояний М- и Р-объекта из пары (И). Для наглядности вершины и дуги обозначены способом, соответствующим классу пометок.

иек'(/)!,,2) йеи>(т2>1)

new(m},2) /îe,w(m4,1)

Рис, 2. Пример представления кооперативного взаимодействия процессов множеством графов Р-объектов

Пусть состояние взаимодействующих Р- и М-объектов, хранимое в переменных р[] и т[] модели GraphPlus, отображается на переменные алгоритма sp, nxt, ch sm, ptype, mtype, node, ay. Переменная sp является частью состояния, хранимого в переменной модели р[]. Она описывает особенности моделируемого вычислительного процесса. Переменная nxt хранит идентификатор Р-объекта, который будет являться значением функции next модели GraphPlus. С каждой вершиной графа Р-объекта, помеченной меткой count{), связывается специальная переменная-счетчик с,. Индекс переменной с,-соответствует числовой пометке вершины. Переменные принимают значения в диапазоне от 0 до числа в метке countQ. Эти значения сохраняются между последовательными посещениями. Переменная sm является частью состояния, хранимого в переменной модели ш[]. Она, аналогично sp, описывает особенности моделируемого вычислительного процесса. Переменная mtype принимает значение «посещающего» М-объекта. Переменная ptype принимает значение «посещаемого» Р-объекта. Переменная node хранит числовую метку текущей вершины на графе Р-объекта. Номер вершины, с которой начнется выполнение алгоритма, определяется тем, был ли М-объект только что активирован или переходит из некоторого Р-объекта по функции next. Переменные atj принимают значения Р-объекта, в который направляется активированный М-объект. Каждая из переменных а,-; ставится в соответствие дуге на графе Р-объекта, имеющей пометку newQ и обозначающей активируемый локальный М-объект. В начале каждого посещения все переменные аи имеют значение е. Значения переменных a,j в конце посещения являются вычисленными значениями функции activate модели GraphPlus. Первый аргумент функции activate соответствует М-объекту, указанному в пометке пен>(), у дуги, с которой сопоставлена переменная а,,. Значение переменных a,j вычисляется заново при каждом посещении. Пусть также имеется вспомогательная функция initjiode. Данная функция для М-объекта определяет номер вершины, с которой, будучи активированным, начнет посещение графа Р-объекта рассматриваемый М-объект. Эта вершина однозначно определяется из диаграммы Р-объекта: в нее ведет дуга с меткой new, содержащей этот М-объект.

С учетом введенных обозначений классам пометок сопоставляются семь фрагментов алгоритма «посещения».

(* ПОМЕТКА: /«(X), ВЕРШИНА 1 *)

ШАГ 1: ДЛЯ ВСЕХ аи, ВЫПОЛНИТЬ a, j :=е

ЕСЛИ node * 1 ТО ПЕРЕЙТИ К ШАГУ node

ЕСЛИ < инициализация > ТО ДЛЯ ВСЕХ с, ВЫПОЛНИТЬ с, := О

ВЫЧИСЛИТЬ (sp.sm) := X(sp,sm)

ПЕРЕЙТИ К ШАГУ 1.1

(* ПОМЕТКА: out(X, Y), ВЕРШИНА N *)

ШАГ N : ВЫЧИСЛИТЬ (sp,sm) := X(sp,sm) nxt := Y node := 1 КОНЕЦ

(* ПОМЕТКА: do(X), ВЕРШИНА N *)

ШАГ N: ВЫЧИСЛИТЬ (sp.sm) := X(sp,sm) ПЕРЕХОД К ШАГУ N. 1

(* ПОМЕТКА: counl(X, Y), ВЕРШИНА N *)

ШАГ N : ВЫЧИСЛИТЬ (sp.sm) := X(sp,sm) су := cv +1 ЕСЛИ cv = У ТО сл, := О

ДЛЯ ВСЕХ (Л',;) с меткой new() ВЫПОЛНЯТЬ ял , := pfvpe КОНЕЦ ЕСЛИ

ЕСЛИ L(ptype,mtype)/\aXim„XSimwr) Фе 70 nxt := ро^е

ИНАЧЕ nxt := е

nodeinil_node(mtype)

КОНЕЦ

(*ПОМЕТКА: ф(Х,У),ДУГА: (N,M)*)

ШАГ N.Y : ЕСЛИ mtype = ^ ТО ПЕРЕХОД К ШАГУ М ИНАЧЕ ПЕРЕХОД К ШАГУ N.(Y +1)

(*ПОМЕТКА: if (X J\ ДУГА: (N,M)*)

ШАГ N.Y : ЕСЛИ X(sp,sm) ТО ПЕРЕХОД К ШАГУ М ИНАЧЕ ПЕРЕХОД К ШАГУ N.{Y +1)

(*ПОМЕТКА: new(X, У),ДУГА: (N.M)*)

ШАГ N.Y : aNM := ptype

ПЕРЕХОД К ШАГУ N.{Y +1)

Очевидным образом из перечисленных фрагментов для произвольного графа Р-объекта можно построить конкретный алгоритм «посещения». Таким образом, множеству размеченных графов Р-объектов соответствует алгоритм, вычисляющий функциональные отношения модели activate, next, newP, newM. Поэтому, с учетом описания начального состояния вычислений, графическое представление модели GraphPIus эквивалентно ее точному описанию (1) в терминах темпоральной логики.

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

моделирования, а также построения кода каркасных библиотек требуется метод машинно-ориентированного представления моделей. Метод основан на графической форме спецификации Р-объектов, пример которой представлен на рис. 2.

Математическое описание разработанного языка моделирования выполнено с использованием Расширенных Бэкуса-Наура Форм (РБНФ). Сохраняя семантику диаграмм процессов (описываемую алгоритмом «посещения» в главе 2), язык моделирования GraphPlus вводит следующее добавление. Предполагается, что граф из Р-объектов (рис. 1) для произвольной модели имеет вид дерева. Тогда, добавив новую метку в язык диаграмм для ссылки на диаграмму Р-объекта на более низком уровне иерархии и введя систему типов Р- и М-объектов, мы получим инструмент для моделирования сложного вычислительного процесса.

Дополнительно для возможности компактного описания сложных систем Р-объектов в язык моделирования GraphPlus введен механизм модулей с параметрами:

<module> == MODULE <ident> [PARAM <ident>{,<ident>}] [COMMENT <str>] { <import>I <type> t <var>I <job>I<proc_ref>I <action>|<condition>| <port>

)

END.

<import> IMPORT <ident> [AS <ident>J

[PARAM <ident>( ,<ident>) ] .

Его применение иллюстрируется при описании каркасов распределенных алгоритмов в главе 4. Для связи с языком реализации используются предложения <action> (процедура на языке реализации); «condition» (логическая функция на языке реализации); <port> (взаимодействие с окружением для ввода-вывода). Предложение <var> обозначает переменные численного метода, a <type> — их тип в языке реализации. Терминами process и job обозначены классы Р- и М-объектов.

Граф Р-объекта описывается как последовательность предложений <noda>:

<process> PROCESS <id_def> ENTRY <label> [COMMENT <str>] {<proc_j2om>| <node>)

end.

<node> —=> <label> (CALL <id_use> I STUB) [EXIT [<num>]] [PIC <num> <nura>3

{

(IP <id_usa> THEN I CONTINUE) <label>

[PIC <num> ",» <nura>] | (NEW <id_use> TO <label>

[PIC <num> <num>J)

).

Каждое предложение обозначает вершину графа и список дуг, исходящих из вершины. Координатная привязка вершин и дуг к плоскости диаграммы выполняется путем указания координат после слова pic. Координата дуги обозначает положение ее изгиба. Текст описания Р-объекта можно формировать и отображать с помощью специального графического редактора, входящего в программный комплекс моделирования.

В главе 3 подробно описывается язык моделирования GraphPlus с примерами использования синтаксических конструкций. Также рассмотрены особенности синтаксического анализа на основе дополнительной формы представления моделей — машинно-ориентированного описания в виде сети структурных элементов. Этот способ представления эквивалентен текстовой и графической форме и предназначен для трансляции и анализа.

В четвертой главе на основе языка моделирования GraphPlus построены библиотеки численных методов, использующие графическое объектное представление схем параллельных алгоритмов.

На примере простейшей схемы MAP «применить ко всем» рассмотрен принцип описания каркасной библиотеки, то есть семейства алгоритмов с общим способом организации вычислений.

Описание состоит из следующих частей. Вначале приводится неформальное объяснение принципа работы схемы. Так схема map образована из п независимых Р-объектов F, каждый из которых вычисляет функцию/() для своего значения аргумента х,. Вычисления заканчиваются, когда все объекты F вычислят свои _Дх,). Затем записывается алгоритм для эквивалентной последовательной схемы, который в случае map имеет вид (10). Дополнительно могут быть указаны ограничения, выраженные через абстрактные функции и предикаты последовательной схемы, используемые при ее распараллеливании.

ДАНО xt:i= ÏTn

НАЙТИ у, :i = Ui

ДЛЯ ВСЕХ / = Пп ВЫПОЛНЯТЬ ( 10)

УГ=/М

КОНЕЦ

Далее следует определение структуры схемы. Оно представляет собой набор параметров, часть из которых задает масштаб (максимальное число параллельных процессов в реализации), а другая часть является определением специальных подклассов Р- и М-объектов модели вычислений. Подклассы Р- и М-объектов конкретизируются в терминах функций, предикатов и переменных, использованных в последовательной схеме. Для схемы MAP определение структуры описывается формулой (11).

А - ^шр с Т," б N

F = F(x,y\f){y' = Ax)},Fc Р 1 '

Формула (11) описывает множество реализаций параллельных алгоритмов А, использующих предлагаемую вычислительную модель на основе Р- и М-объектов и распараллеливающих последовательный алгоритм (10). Алгоритмы по схеме MAP принадлежат к множеству всех реализуемых моделью алгоритмов Т. Схема имеет единственный параметр масштаба и, который задает количество Р-объектов. Параметр F определяет класс Р-объектов схемы. Формула (11) показывает, что каждый Р-объект схемы F содержит переменные объекта х и у. За вертикальной чертой в списке параметров объекта F следует список функций, связанных с переменными объекта. В данном случае это функция f. В определении функций объекта, которое заключено в фигурные скобки, могут присутствовать произвольные переменные, а также переменные состояния объекта, перечисленные в списке параметров. Если связанная с состоянием объекта переменная употребляется в списке вычисляемых параметров функции, то это новое значение переменной объекта обозначается при помощи штриха

С).

Определение (11) позволяет воспользоваться готовой библиотекой для реализации параллельных вычислений, эквивалентных алгоритму (10). Для этого требуется определить f, х, у, расширяя библиотечный класс F (определив пользовательский подкласс F' класса F). Однако определение (11) скрывает способ реализации параллельного алгоритма. Реализация схемы map в терминах модели Р- и М- объектов может быть формализована на языке GraphPlus следующим образом.

MODULE MAIN PROCESS MAIN IMPORT STUFF AS stuff IMPORT MAP AS map

IMPORT rMAP AS M4 PARAM map, stuff IMPORT rMAP AS Ml б PARAM M4 , stuff IMPORT rMAP AS Мб4 PARAM Ml6, stuff IMPORT rMAP AS M256 PARAM Мб4, stuff IMPORT rMAP AS Ml024 PARAM M256, stuff

END

PROCESS MAIN ENTRY Sbegin Sbegin CALL F FROM Ml024

END

MODULE STUFF

JOB О EXPORT END

MODULE rMAP PARAM Tr,S

PROCESS F; — диаг^ракдеа END

MODULE MAP PROCESS F

ACTION f РАНАМ X IN, у OUT END VAR X TYPE X VAR у TYPE Y TYPE X TYPE Y END

PROCESS F EXPORT ENTRY @begin

Sbegin CALL f END

Описание алгоритма содержится в четырех модулях: MAIN, STUFF, MAP и гМАР. Назначение модуля MAIN заключается в формировании дерева Р-объектов нужного размера методом рекурсивного импорта модулей. Шаг рекурсии определяет модуль гМАР. В случае, когда первый параметр этого модуля связан с модулем типа MAP, например, в модуле М4, модуль гМАР представляет четыре Р-объекта. В случае, когда первый параметр модуля гМАР связан с модулем типа гМАР, представляющим п Р-объектов, модуль г MAP представляет 4п Р-объектов. Таким образом, число Р-объектов в нашей модели экспоненциально зависит от числа предложений импорта и может быть достаточно большим. Число Р-объектов в описываемом примере равно 1024. Процесс F из модуля гМАР описывается диаграммой, показанной на рис. 3.

Рис. 3. Диаграмма процесса F из модуля гМАР схемы «применить ко всем»

Разработанная библиотека каркасов также включает схемы TASKBAG и CHAIN. Схема TASKBAG «портфель задач» описывает вычислительный процесс, в котором участвует Р-объект В, отвечающий за выдачу заданий, и группа Р-объектов Т, обрабатывающих задания. При этом запрос новых заданий и возвращение обработанных (в М-объектах М2, М,) организуется асинхронно по готовности. Последовательная схема алгоритма вычислений имеет вид (12). Для ее корректного распараллеливания должно выполняться ограничение р(р(>-,у,),у2) = р(р(г,у2),у,).

Tjrf

ДАНО s — исследуемое множество НАЙТИ г - множество результатов ПОКА ВЫПОЛНЯТЬ (s,Jt):=g(i) (12)

у-т

г-= Р(г,у) КОНЕЦ

Параллельная декомпозиция схемы (12) представлена выражением (13). Диаграмма процесса верхнего уровня схемы «портфель задач» на языке моделирования GraphPlus показана на рис. 4.

Л = Агл.жю (п,В,Г,М„М2 ), Лл.тоио с Т, n s N В = B(s,r | g.p.e) {(*',*) = g(s),r' = p(r,y),e(s) c= {0,1Ц,Вс P

Т=Т(/){у = Дх)),ГсР _ (13)

А/, = Мх(ах | mx,mx){a'x = тх(х),х = тх(ах)},М, с М Мг = Мг(ау |ту,ту){а'у = ту(у),у = ту(ау)),М2 с М

Л' = (ВМ - Ä]N

h = (bM-а)п + DAn

М = Q-GM-CN-cn + /(г,О

Применение схемы «портфель задач» проиллюстрировано на примере задачи аппроксимации интеграла непрерывной функции методом адаптивной квадратуры. В качестве задачи, имеющей прикладное значение, рассмотрено сканирование параметрического пространства для модели Лотки-Вольтерра с диффузионным и стохастическим членами (14), применяемой для исследования процессов межвидовой конкуренции. Для одномерного пространства требуется найти частные решения системы (15) в стационарном состоянии при разных значениях параметров. Особенностями поведения модели являются большая вычислительная сложность и зависимость времени достижения стационарного состояния от текущих параметров. Схема «портфель задач» при данных особенностях обеспечивает балансировку загруженности и скрывает интерфейс использованной для управления вычислениями пакетной системы Condor.

N' = т(м,н - 1)А'/-'+N,h

Схема «цепь асинхронно взаимодействующих процессов» chain описывает вычисления на цепи попарно связанных Р-объектов L, С и R (L замыкает цепь слева, R — справа). При вычислениях происходит перенос информации в оба направления по цепи М-объектами Rm и Lm. Последовательная схема алгоритма вычислений имеет вид (16).

ДАНО I, v, г,: / = Пл; I НАЙТИ /, v, г, ВЫПОЛНЯТЬ t РАЗ ДЛЯ ВСЕХ/ = \~п ВЫПОЛНЯТЬ ЕСЛИ / = 1 ТО /, := АД.У,) ИНАЧЕ /(:= ^.„/„v,) (16)

v, := c,(i„v„r,)

ЕСЛИ / = п ТО r„ := b2(v„,r„) ИНАЧЕ г, := i2(v„/;,/,t,) КОНЕЦ( КОНЕЦ

Параллельная декомпозиция схемы (16) представлена выражением (17). Пример диаграммы процесса для схемы «цепь асинхронно взаимодействующих процессов» на языке моделирования GraphPlus приведен на рис. 5.

.-г

(15)

А = Асит (п, 1,Ь,С, Л, Л„,, ¿„, ), Ааик с Т, п е N , / б N

С = СО„/2,У2,гг>/, 1 = з,(г,,/2,у2),у^ = с,(/2,у2,г2),г2' = х2(у2,г2,/3)},с с Р

к = /г(г2,/3,у„/-3и1,с|,б2){/5 = ^(/-^у,)^; = с,(/„Уз,г3),г3' = у»,/,)!,^ р /?,„ = Н„(аг | /п,.,о1г){£7,'. = т,(г),г = т, (аг)),Иш с М

¿,„ = £,„(а/1){"/' = "*,(/),/ = и,(а,)},£,„ с М

Л

Рис. 5. Диаграмма процесса С схемы «цепь асинхронно взаимодействующих

процессов»

Применение схемы «цепь асинхронно взаимодействующих процессов» проиллюстрировано на задаче о распараллеливании решения уравнения Лапласа на основе метода Гаусса-Зейделя. В качестве задачи, имеющей прикладное значение, описан способ параллельного моделирования распространения световых волн в диэлектрике. В работе Головашкина Д.Л. и Сойфера В.А.2' предложена математическая модель распространения световой волны в диэлектрике, применение которой заключается в решении системы уравнений вида (18). Особенностью решения является необходимость итеративного пересчета трех матриц проекций электрического и магнитного полей, это требует значительных вычислительных мощностей.

ЕТ = -

! е^-Е'У

н" = ——--

МеМ К ' И, ( -//2 - Н"

и:

К К

и яг' - яг'

--г-

/V К

(18)

В диссертации показано, что алгоритм решения системы (18), аналогично типовому методу Гаусса-Зейделя, удается свести к последовательной схеме (16), а затем к параллельной схеме (17).

21 Головашкнн Д.Л., Сойфер В.А. Анализ прохождения электромагнитного излучения через дифракционную линзу// Автометрия. 1999. Вып.6. С. 119-121.

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

Инструментальная среда моделирования GraphPIus включает графический редактор, компилятор, кодогенератор, интерпретатор, варианты среды времени исполнения для имитационных экспериментов и многопоточного исполнения, службу управления вычислениями в системе Condor.

Предложен метод исполнения моделей, представленный в виде паттерна проектирования, названного «Постоялец-Посетитель». Метод заключается в выделении специальных объектов Room , связанных с потоками управления, перестраивающих списковые структуры из объектов Resident и visitor, являющихся родовыми для Р- и М- объектов модели GraphPIus. Метод проверен нагрузочными испытаниями на разных типах компьютеров. Таблица 1 иллюстрирует высокую эффективность данного решения.

Таблица 1

Число сегментов Тмп рабочей станции

Однопроцессорная 11 Однопроцессорная гнперпоточная 2> Двухпроцессорная 3)

Время, с Ускор. Время, с Ускор. Время, с Ускор.

Оптимизированный код 2 2,1050 1,0024 1,4171 1,5393 1,7406 1,9668

50 2,1661 0,9710 1,4516 1,5026 1,8172 1,8830

Каркас 2 2,1120 0,9996 1,4203 1,5358 1,7516 1,9571

50 2,1431 0,9846 1,4781 1,4758 1,8672 1,8359

Примечание: ускорение вычислялось относительно длительности счета эквивалентной последовательной программы, результаты усреднены по 10 реализациям; использовались следующие конфигурации:

1) CPU AthlonXP 1700+ 1.47 GHz RAM 256MB OS MS Windows XP 2002 SP2;

2) CPU Pentium4 3.4 GHz RAM 2GB OS MS Windows XP 2002 SP2;

3) CPU PentiumIIIx2 1 GHz RAM 512MB OS MS Windows 2000 SP4.

В диссертации также приведены результаты нагрузочного тестирования системы Condor, работающей под управлением сервера объектов модели GraphPIus для организации распределенного исполнения по схеме TASKBAG. Тесты показали, что метод управления вычислениями целесообразен, когда общее количество заданий велико, и нет возможности использования кластера в выделенном режиме весь период расчета. В данном случае преимуществом, компенсирующим невысокую эффективность (порядка 70% для 1 минуты автономного счета), является автоматическая поддержка непрерывных вычислений при сбоях, выключении питания, использовании компьютеров локальными привилегированными пользователями.

Далее в главе 5 описан метод проведения имитационных экспериментов с использованием модели GraphPIus для вычислительной среды с флуктуирующими характеристиками производительности и пропускной способности. Предложен метод измерения и учета влияния фоновых процессов операционной системы и коммуникационной среды на разбалансировку вычислений. Выполнено подробное исследование вычислительного процесса

схемы CHAIN имитационным методом. В результате были построены пространственно-временные диаграммы, показывающие, что схема CHAIN позволяет совместить вычисления и обмен данных. Изучены виды переходных процессов (рис. 6) при различных интенсивностях случайного воздействия на систему процессов.

О 100 200 300 400 500 600 700 600 0 100 200 300 400 500 600 700 800

0 100 200 300 400 500 600 700 800 О 100 200 300 400 500 600 700 800

Рис. 6. Изменение эффективности вычислений в модельном времени при различных типах возмущающего воздействия

Получен важный результат: у вычислительной модели CHAIN имеется «интервал устойчивости», в котором как величина, так и характер распределения времен задержек не оказывают существенного влияния на эффективность. Этому эффекту соответствует тип поведения, показанный на первых трех графиках рис. 6. Таким образом, модель CHAIN применима для распределенных вычислений в гетерогенных средах с флуктуирующими параметрами эффективности и пропускной способности.

Также проведено исследование влияния флуктуации производительности, вызванной фоновыми процессами операционной системы. Показано, что фоновые процессы приводят к снижению эффективности примерно на 2% внутри «интервала устойчивости». После увеличения времени передачи сообщений более критического, когда происходит частичный простой Р-объектов, влияние флуктуации производительности стремится к нулю.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

1. Предложена новая графическая объектная модель параллельных и распределенных вычислений GraphPlus. С использованием темпоральной логики Лампорта построена спецификация модели GraphPlus для представления вычислительных процессов произвольного вида в форме удобной для реализации в распределенных гетерогенных вычислительных средах.

2. На основе интерпретации формул для моделей конкурентного и кооперативного взаимодействия процессов, являющихся типовыми при реализации вычислительных алгоритмов, показана адекватность модели GraphPlus при описании параллельных вычислительных алгоритмов для распределенных и гетерогенных вычислительных сред.

3. Определен способ наглядного изображения моделей процессов в виде множества ориентированных помеченных графов с семантикой, соответствующей представлению в виде темпоральной формулы. По графическому описанию модели GraphPlus построен метод порождения алгоритмов для вычисления функций, определяющих динамические свойства модели.

4. Формализован синтаксис языка моделирования пространственно-распределенных дискретных систем, включающий текстовую и графическую нотации для описания структуры и логики работы процессов. Предложен метод машинно-ориентированного описания моделей пространственно-распределенных дискретных систем, используемый в алгоритмах программного комплекса.

5. Разработано представление схем параллельных вычислительных процессов для реализации прикладных алгоритмов численного моделирования, включающее определение семантики в форме схемы последовательного алгоритма; способ отделения численного метода от реализующего алгоритма; параллельную схему алгоритма вычислений в терминах объектной модели на языке GraphPlus.

6. Реализованы схемы процессов MAP «применить ко всем», TASKBAG «портфель задач» и CHAIN «цепь асинхронно взаимодействующих процессов». С использованием разработанных схем рассмотрены примеры распараллеливания тестовых, а также практически значимых задач математического моделирования, имеющих высокую вычислительную сложность, таких как задача моделирования процесса межвидовой конкуренции и задача моделирования распространения света на основе решения уравнений Максвелла.

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

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

8. Предложен метод исследования работы вычислительного приложения на аппаратуре с нестабильными характеристиками производительности и пропускной способности коммуникационной среды. Метод основан на использовании специальной среды времени исполнения моделей, представляющей собой монитор дискретно-событийного моделирования с механизмом продвижения времени, основанном на событиях. Также предложены методики измерения и имитации параметров вычислительной среды при проведении имитационных экспериментов. Проведены детальные исследования каркасной библиотеки CHAIN методом имитации гетерогенной асинхронной вычислительной среды с различными параметрами, демонстрирующими пригодность библиотеки для данного типа вычислений.

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

Основное содержание работы полностью раскрывается в следующих публикациях:

Монографии:

1. Востокин C.B. Графическая объектная модель параллельных процессов и ее применение в задачах численного моделирования. Самара: Издательство Самарского научного центра РАН, 2007. 286 с. ISBN 978-593424-284-9.

2. Востокин C.B. Метод описания пространственно-распределенных параллельных процессов. Самара: Издательство Самарского научного центра РАН, 2004. 86 с. ISBN 5-93424-141-9.

3. Востокин C.B. Спецификация языка программирования ГРАФ ПЛЮС. Самара: Издательство Самарского научного центра РАН, 2003. 86 с. ISBN 5-93424-101-Х.

Публикации в периодических изданиях из списка ВАК:

4. Востокин C.B. Спецификация модели параллельных и распределенных вычислений GraphPIus на основе логики TLA // Известия Самарского научного центра РАН. 2006. Т.8, №3(17). С.875-881.

5. Востокин C.B. Особенности реализации процедур сканирования параметрических пространств для сложных численных моделей // Математическое моделирование. 2006. Т. 18, №12. С. 125-128.

6. Востокин C.B. Технология визуального проектирования параллельных и распределенных приложений // Системы управления и информационные технологии. 2006. №2 (24). С.39-43.

7. Востокин C.B. Объектно-ориентированный метод структурирования кода метакомпьютерного приложения // Информационные технологии. 2006. №5. С.40-45.

8. Востокин C.B. Инструментальная среда метакомпьютинга проекта GraphPIus // Вестник Самарского государственного аэрокосмического университета им. С.П. Королева. 2006. №3(11). С.60-65.

9. Востокин C.B. Применение метода парного взаимодействия объектов для построения сред разработки распределенных приложений // Вестник Самарского государственного технического университета. Серия: Физико-математические науки. 2005. №38. С.26-28.

10.Востокин C.B., Курушина С.Е. Численное моделирование процесса конкуренции во флуктуирующих средах на кластерных вычислительных системах // Известия Самарского научного центра РАН. 2005. Т. 7, №1(13). С. 143-148.

11.Востокин C.B. Применение интерпретатора сценария GraphPIus для управления распределенными вычислениями // Известия Самарского научного центра РАН. 2005. Т. 7, №1(13). С.138-142.

12.Востокин C.B., Прохоров С. А. Пример визуальной модели распределенного вычислительного процесса // Известия Самарского научного центра РАН. 2004. Т. 6, №1(10). С. 180-185.

13.Востокин C.B. Технология моделирования распределенных систем, основанная на визуальном языке, и ее приложения // Известия Самарского научного центра РАН. 2004. Т. 6, №1(10). С.185-193.

14.Востокин C.B. Графический метод проектирования параллельных программ с использованием асинхронной событийной модели вычислений // Вестник Самарского государственного технического университета. Серия: Физико-математические науки. 2004. №30. С. 178183.

15.Востокин C.B. Модель параллельных вычислений визуального граф-ориентированного языка // Сб. Вестник Самарского государственного аэрокосмического университета им. С.П. Королева. Серия: Актуальные проблемы радиоэлектроники. 2000. Вып. 4. С.96-100.

16.Востокин C.B. Автоматизация параллельного программирования с использованием визуального языка // Сб. Вестник Самарского государственного аэрокосмического университета им. С.П. Королева, Серия: Актуальные проблемы радиоэлектроники. 2000. Вып. 1. С.80-83.

Свидетельства о регистрагцт программ для ЭВМ:

17.Востокин C.B. Модуль многопоточного исполнения моделей программного комплекса проекта Граф Плюс. Свидетельство об официальной регистрации программы для ЭВМ №2007611206.

18.Востокин C.B. Транслятор моделей программного комплекса проекта Граф Плюс. Свидетельство об официальной регистрации программы для ЭВМ №2007611201.

Другие публикации:

19.Востокин C.B. Технология визуального программирования каркасов параллельных и распределенных приложений на основе объектно-

ориентированной модели вычислений GraphPlus // Труды III Международной конференции «Параллельные вычисления и задачи управления». М.: ИПУ РАН им. Трапезникова, 2006. С. 634-646.

20.Востокин C.B. Каркас «пакет с заданиями» для программирования grid-приложений поисково-переборного типа на базе системы Condor // Распределённые вычисления и грид-технологии в науке и образовании: тез. докл. 2-й междунар. конф. Дубна: ОИЯИ, 2006. С.146-147.

21.Востокин C.B. Объектная модель для разработки параллельных вычислительных приложений // Математическое моделирование и краевые задачи: труды третьей всероссийской научной конференции. Самара: изд-во СамГТУ, 2006. 4.4 С.36-39.

22.Востокин C.B. Исследование связи между эффективностью распределенных вычислений и качеством обслуживания коммуникационной среды с использованием имитационной модели // Надежность и качество. Пенза: Инф.-изд. центр Пенз. гос. ун-та, 2006. С.225-226.

23.Востокин C.B. Визуальное проектирование каркасов параллельных и распределенных приложений в технологии GraphPlus // Перспективные информационные технологии в научных исследованиях, проектировании и обучении: труды научно-технической конференции с международным участием. Самара, 2006. Т.1. С. 51-58.

24.Востокин C.B. Курушина С.Е. Применение вычислительного кластера для моделирования процесса конкуренции во флуктуирующих средах // Компьютерные технологии в науке, практике и образовании: труды всероссийской межвузовской научно-практической конференции. Самара, 2005. С.6-9.

25.Востокин C.B. Инструментальная система проектирования GRID приложений для архитектур Master-Worker // Надежность и качество. Пенза: Инф.-изд. центр Пенз. гос. ун-та, 2005. С.243.

26.Востокин C.B. Моделирование распределенного вычислительного процесса на визуальном языке // Информационные технологии моделирования и управления. Междунар. сборник научн. труд. Воронеж: Изд-во Научная книга, 2004. Вып. 17. С.37-45.

27.Востокин C.B. Проект ГРАФ ПЛЮС. Визуальный язык распределенного и параллельного программирования, http://graphplus.ssau.ru. 2004-2007.

28.Востокин C.B. Язык моделирования пространственно распределенных параллельных процессов // Четвертый международный научно-практический семинар «Высокопроизводительные параллельные вычисления на кластерных системах». Самара, 2004. С.40-41.

29.Востокин C.B. Технология построения распределенных приложений проекта ГРАФ ПЛЮС // Надежность и качество. Пенза: Инф.-изд. центр Пенз. Гос. ун-та, 2004. С.166.

30.Востокин C.B. Графический метод проектирования и исследования свойств параллельных программ с использованием асинхронной событийной модели вычислений // Электронный журнал "Исследовано в России". 2004. Вып. 54. С. 613-627.

31.Востокин C.B. Визуальный язык ГРАФ ПЛЮС: свойства и цели проектирования // Математическое моделирование информационных и технологических систем: Сб. науч.тр. Воронеж: Воронеж, гос. технол. акад., 2003. Вып. 6. С.150-152.

32.Vostokin S.V. Computer Aided Engineering of Distributed and Parallel Systems Using GRAPH Plus language // Interactive Systems: The Problems of Human-Computer Interaction. Proc. of the Int. Conf., 23-27 September 2003. Ulyanovsk: U1STU, 2003. P.56-59.

33.Востокин C.B. Использование визуального языка Граф Плюс для повышения надежности параллельных программ // Надежность и качество. Пенза: Инф.-изд. центр Пенз. гос. ун-та, 2003. С.182-183.

34.Востокин C.B. Метод автоматического извлечения информации из свободного текста и оценка его надежности // Надежность и качество. Пенза: Инф.-изд. центр Пенз. гос. ун-та, 2002. С. 124-126.

35.Востокин C.B. Графическая модель программирования параллельных вычислений // Перспективные информационные технологии в научных исследованиях, проектировании и обучении. Самара: изд-во СГАУ, 2001. С.7-12.

36.Востокин C.B. Визуальный язык параллельного программирования системы ГРАФ // Надежность и качество. Пенза: Инф.-изд. центр Пенз. гос. ун-та, 1999. С.553-555.

37.Востокин C.B. Концепция разработки визуального языка параллельного программирования системы ГРАФ // БИКАМП-99: тез. докл. С.Петербург, 1999. С. 121.

38.Востокин C.B. Разработка многопоточных программ в системе визуального программирования ГРАФ // Математика, компьютер, образование: тез. докл. Москва, 1999. Т.6. С.59.

39.Востокин C.B. Генерация текстов программ на основе графической модели системы ГРАФ // Техн. кибернетика, радиоэлектроника и системы управления: тез. докл. Таганрог, 1998. С. 105.

40.Востокин С.В.Технология генерации текстов параллельных программ по графической модели алгоритма И БИКАМП-98: тез. докл. С.-Петербург, 1998. С.57-58.

41 .Востокин C.B. Компилятор подсистемы отладки системы графического программирования ГРАФ // Королевские чтения: тез. докл. Самара, 1997. С.56-57.

42.Востокин C.B. Подсистема отладки графо-символических объектов // XXIII Гагаринские чтения: тез. докл. Москва, 1997. 4.5. С.88.

Подписано в печать: 01.08.2007 г. Бумага офсетная. Печать оперативная. Объем: 2 печ.л. Тираж: 100 экз. Заказ № 804

Отпечатано в типографии AHO «Издательство СНЦ РАН» 443001, Самара, Студенческий пер., За тел.:(846) 242-37-07

СПИСОК УСЛОВНЫХ ОБОЗНАЧЕНИЙ

ВВЕДЕНИЕ

1. ОБЗОР МЕТОДОВ, МОДЕЛЕЙ И ПРОГРАММНЫХ СИСТЕМ В

ОБЛАСТИ ПАРАЛЛЕЛЬНОГО И РАСПРЕДЕЛЕННОГО

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

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

1.1.1. Формальные методы в области параллельных и распределенных вычислений

1.1.2. Классификация моделей распределенных систем

1.1.3. Основные параллельные и распределенные алгоритмы

1.2. Системное программное обеспечение параллельных и распределенных вычислений

1.2.1. Прикладные интерфейсы операционных систем

1.2.2. Стандарт Open MP

1.2.3. Библиотеки стандарта MPI и PVM

1.2.4. Сокеты и средства удаленного вызова процедур

1.2.5. Грид-технологии и подобное промежуточное программное обеспечение

1.2.5.1. Предпосылки исследований по грид-технологиям

1.2.5.2. Определение грид-системы

1.2.5.3. Архитектура грид-систем

1.2.5.4. Программное обеспечение грид-систем

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

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

Новые возможности численного моделирования связаны с интенсивным развитием сетевых технологий. Агрегация вычислительных ресурсов позволяет добиться очень высокой пиковой производительности и снижения стоимости вычислительных экспериментов. С другой стороны, имеется ряд важных задач математического моделирования, которые обуславливают потребность во все более мощной вычислительной технике. Это задачи параметрической оптимизации; задачи исследования асимптотического поведения моделей, основанных на системах дифференциальных уравнений; сеточные и конечноэлементные модели; модели взаимодействия частиц.

Однако применение агрегированных вычислительных ресурсов в численном моделировании сдерживается из-за отсутствия средств и методов организации вычислений, адекватных новому типу вычислительной среды. В агрегированной среде исполнения возникают проблемы организации вычислений, обусловленные программной и аппаратной гетерогенностью, ненадежностью и распределенным характером среды исполнения, большим числом процессов, сложностью управления ресурсами. Обычные методы реализации параллельных численных алгоритмов с использованием MPI сложно масштабируются на новый тип вычислительных сред. Технологии, реализованные в грид-системах на основе программного обеспечения Globus, gLite, ARC, решают задачу организации крупно-гранулярных вычислений. В альтернативных индустриальных технологиях, например, в системе координации Jini, технологиях RMI, CORBA, DCOM не предлагается способов описания вычислительных процессов в целом.

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

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

Традиционный подход к преодолению сложности разработки численных методов для параллельных компьютеров лежит в области автоматизации программирования. Ведутся исследования, цель которых создание распараллеливающих компиляторов, анализаторов последовательного кода на предмет выявления параллелизма. Разрабатываются непроцедурные методы программирования численных моделей. В данном направлении известны работы А.П. Ершова, В.В. Воеводина, В.А. Вальковского, Л.Дж. Баера (L.J. Ваег) и многих других отечественных и зарубежных ученых. Такие подходы являются эффективными для узкого класса алгоритмов и вычислительных систем.

Представление алгоритма и среды его исполнения в форме модели дискретной системы широко применяется для анализа. В этой области работали такие ученые как А. Нуэли (А. Pnueli), K.M. Чанди (K.M. Chandy), Я. Мизра (J. Misra), Л. Лампорт (L. Lamport) и другие. Однако анализу подвергаются готовые реализации алгоритмов. Поэтому методы анализа обычно не учитывают вопрос о существовании эффективной реализации той или иной модели, хотя известно, что некоторые простые дискретные модели не возможно эффективно реализовать в распределенных средах.

В диссертации рассматривается альтернативный подход, использующий специальные модели в качестве основы алгоритмизации и программирования численных методов. Эти модели представляют собой схемы параллельных алгоритмов численного моделирования. Данный подход был предложен М.И. Коулом (M.I. Cole) и развивается в работах С. Макдональда (S. MacDonald), П.К. Берзигиярова и других авторов. Тем не менее, недостаточно исследованными следует считать вопросы построения эффективно реализуемых универсальных моделей дискретных систем с использованием объектно-ориентированной парадигмы и методов визуализации алгоритмов, а также вопросы изучения взаимосвязи между алгоритмом и реализующей вычислительной средой методами имитационного моделирования.

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

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

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

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

2) На основе сформулированных требований построить модель дискретной системы, которая описывает алгоритмы численного моделирования в произвольной среде исполнения.

3) Обосновать пригодность построенной модели для описания алгоритмов численного моделирования и возможность эффективного исполнения модели в распределенной вычислительной среде.

4) Разработать язык и метод описания прикладных программ численного моделирования в терминах предложенной модели дискретной системы.

5) Выполнить исследование адекватности предложенной модели дискретной системы в вычислительных экспериментах с использованием дискретно-событийной имитационной модели.

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

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

Теоретические и практические результаты диссертационной работы использованы при выполнении госбюджетных работ в рамках персонального гранта Министерства образования Российской Федерации и Правительства Самарской области на проведение исследований в области гуманитарных, общественных, технических наук и естествознания по теме «Разработка методов визуального проектирования управляющих алгоритмов для систем распределенной пакетной обработки заданий», шифр темы 17Г-Р077-090-050 В2; при выполнении исследовательских работ по гранту Американского фонда гражданских исследований и развития (CRDF Project SA -014-02).

Апробация работы. Результаты работы докладывались и обсуждались на всероссийских и международных научно-технических конференциях:

- Научно-технической конференции с международным участием «Перспективные информационные технологии в научных исследованиях, проектировании и обучении», Самара, 2006 г.;

- Третьей Всероссийской научной конференции «Математическое моделирование и краевые задачи», Самара, 2006 г.;

- Второй международной конференции «Распределённые вычисления и грид-технологии в науке и образовании», Дубна, 2006 г.;

- Третьей международной конференции «Параллельные вычисления и задачи управления», Москва, 2006 г.

- Международных конференциях «Надежность и качество», Пенза, 1999, 2002-2006 гг.;

- Всероссийской межвузовской научно-практической конференции «Компьютерные технологии в науке, практике и образовании», Самара, 2005 г.;

- Четвертом международном научно-практическом семинаре «Высокопроизводительные параллельные вычисления на кластерных системах», Самара, 2004 г.;

- Международной конференции «Интерактивные системы. Проблемы человеко-машинного взаимодействия», Ульяновск, 2003 г.; а также на Всероссийской молодежной научной конференции «XXIII Гагаринские чтения», Москва, 1997; Всероссийской студенческой научной конференции «Королевские чтения», Самара, 1997; Первой и Второй международной молодежной школе-семинаре БИКАМП, Санкт-Петербург, 1998 и 1999; IV Всероссийской научной конференции студентов и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления», Таганрог, 1998; VI Международной конференции "Математика, компьютер, образование", Москва, Пущино, 1999.

По теме диссертации опубликовано 42 работы, в том числе 3 монографии, 29 статей, из них 13 — в изданиях, входящих в перечень ведущих рецензируемых научных журналов и изданий, выпускаемых в Российской Федерации, в которых должны быть опубликованы основные научные результаты диссертации на соискание ученой степени доктора наук; а также получено 2 свидетельства о регистрации программ для ЭВМ, опубликован сайт в сети Интернет на сервере Самарского государственного аэрокосмического университета.

Основное содержание работы полностью раскрывается в следующих публикациях:

Монографии:

1. Востокин C.B. Графическая объектная модель параллельных процессов и ее применение в задачах численного моделирования. Самара: Издательство Самарского научного центра РАН, 2007. 286 с. ISBN 9785-93424-284-9.

2. Востокин C.B. Метод описания пространственно-распределенных параллельных процессов. Самара: Издательство Самарского научного центра РАН, 2004. 86 с. ISBN 5-93424-141-9.

3. Востокин C.B. Спецификация языка программирования ГРАФ ПЛЮС. Самара: Издательство Самарского научного центра РАН, 2003. 86 с. ISBN 5-93424-101-Х.

Публикации в периодических изданиях из списка ВАК:

4. Востокин C.B. Спецификация модели параллельных и распределенных вычислений GraphPlus на основе логики TLA // Известия Самарского научного центра РАН. 2006. Т.8, №3(17). С.875-881.

5. Востокин C.B. Особенности реализации процедур сканирования параметрических пространств для сложных численных моделей // Математическое моделирование. 2006. Т.18, №12. С. 125-128.

6. Востокин C.B. Технология визуального проектирования параллельных и распределенных приложений // Системы управления и информационные технологии. 2006. №2 (24). С.39-43.

7. Востокин C.B. Объектно-ориентированный метод структурирования кода метакомпьютерного приложения // Информационные технологии. 2006. №5.С.40-45.

8. Востокин C.B. Инструментальная среда метакомпьютинга проекта GraphPlus // Вестник Самарского государственного аэрокосмического университета им. С.П. Королева. 2006. №3(11). С.60-65.

9. Востокин C.B. Применение метода парного взаимодействия объектов для построения сред разработки распределенных приложений // Вестник Самарского государственного технического университета. Серия: Физико-математические науки. 2005. №38. С.26-28.

10.Востокин C.B., Курушина С.Е. Численное моделирование процесса конкуренции во флуктуирующих средах на кластерных вычислительных системах // Известия Самарского научного центра РАН. 2005. Т. 7, №1(13). С.143-148.

11.Востокин C.B. Применение интерпретатора сценария GraphPlus для управления распределенными вычислениями // Известия Самарского научного центра РАН. 2005. Т. 7, №1(13). С. 138-142.

12.Востокин C.B., Прохоров С.А. Пример визуальной модели распределенного вычислительного процесса // Известия Самарского научного центра РАН. 2004. Т. 6, №1(10). С.180-185.

13.Востокин C.B. Технология моделирования распределенных систем, основанная на визуальном языке, и ее приложения // Известия Самарского научного центра РАН. 2004. Т. 6, №1(10). С. 185-193.

14.Востокин C.B. Графический метод проектирования параллельных программ с использованием асинхронной событийной модели вычислений // Вестник Самарского государственного технического университета. Серия: Физико-математические науки. 2004. №30. С. 178183.

15.Востокин C.B. Модель параллельных вычислений визуального граф-ориентированного языка // Сб. Вестник Самарского государственного аэрокосмического университета им. С.П. Королева. Серия: Актуальные проблемы радиоэлектроники. 2000. Вып. 4. С.96-100.

16.Востокин C.B. Автоматизация параллельного программирования с использованием визуального языка // Сб. Вестник Самарского государственного аэрокосмического университета им. С.П. Королева, Серия: Актуальные проблемы радиоэлектроники. 2000. Вып. 1. С.80-83.

Свидетельства о регистрации программ для ЭВМ:

17.Востокин C.B. Модуль многопоточного исполнения моделей программного комплекса проекта Граф Плюс. Свидетельство об официальной регистрации программы для ЭВМ №2007611206.

18.Востокин C.B. Транслятор моделей программного комплекса проекта Граф Плюс. Свидетельство об официальной регистрации программы для ЭВМ №2007611201.

Другие публикации:

19.Востокин C.B. Технология визуального программирования каркасов параллельных и распределенных приложений на основе объектно-ориентированной модели вычислений GraphPlus // Труды III Международной конференции «Параллельные вычисления и задачи управления». М.: ИПУ РАН им. Трапезникова, 2006. С. 634-646.

20.Востокин C.B. Каркас «пакет с заданиями» для программирования grid-приложений поисково-переборного типа на базе системы Condor // Распределённые вычисления и грид-технологии в науке и образовании: тез. докл. 2-й междунар. конф. Дубна: ОИЯИ, 2006. С. 146-147.

21.Востокин C.B. Объектная модель для разработки параллельных вычислительных приложений // Математическое моделирование и краевые задачи: труды третьей всероссийской научной конференции. Самара: изд-во СамГТУ, 2006. 4.4 С.36-39.

22.Востокин C.B. Исследование связи между эффективностью распределенных вычислений и качеством обслуживания коммуникационной среды с использованием имитационной модели // Надежность и качество. Пенза: Инф.-изд. центр Пенз. гос. ун-та, 2006. С.225-226.

23.Востокин C.B. Визуальное проектирование каркасов параллельных и распределенных приложений в технологии GraphPlus // Перспективные информационные технологии в научных исследованиях, проектировании и обучении: труды научно-технической конференции с международным участием. Самара, 2006. Т.1. С. 51-58.

24.Востокин C.B. Курушина С.Е. Применение вычислительного кластера для моделирования процесса конкуренции во флуктуирующих средах // Компьютерные технологии в науке, практике и образовании: труды всероссийской межвузовской научно-практической конференции. Самара, 2005. С.6-9.

25.Востокин C.B. Инструментальная система проектирования GRID приложений для архитектур Master-Worker // Надежность и качество. Пенза: Инф.-изд. центр Пенз. гос. ун-та, 2005. С.243.

26.Востокин C.B. Моделирование распределенного вычислительного процесса на визуальном языке // Информационные технологии моделирования и управления. Междунар. сборник научн. труд. Воронеж: Изд-во Научная книга, 2004. Вып. 17. С.37-45.

27.Востокин C.B. Проект ГРАФ ПЛЮС. Визуальный язык распределенного и параллельного программирования. http://graphplus.ssau.ru. 2004-2007.

28.Востокин C.B. Язык моделирования пространственно распределенных параллельных процессов // Четвертый международный научно-практический семинар «Высокопроизводительные параллельные вычисления на кластерных системах». Самара, 2004. С.40-41.

29.Востокин C.B. Технология построения распределенных приложений проекта ГРАФ ПЛЮС // Надежность и качество. Пенза: Инф.-изд. центр Пенз. Гос. ун-та, 2004. С. 166.

30.Востокин C.B. Графический метод проектирования и исследования свойств параллельных программ с использованием асинхронной событийной модели вычислений // Электронный журнал "Исследовано в России". 2004. Вып. 54. С. 613-627.

ЗЬВостокин C.B. Визуальный язык ГРАФ ПЛЮС: свойства и цели проектирования // Математическое моделирование информационных и технологических систем: Сб. науч.тр. Воронеж: Воронеж, гос. технол. акад., 2003. Вып. 6. С. 150-152.

32.Vostokin S.V. Computer Aided Engineering of Distributed and Parallel Systems Using GRAPH Plus language // Interactive Systems: The Problems of Human-Computer Interaction. Proc. of the Int. Conf., 23-27 September 2003. Ulyanovsk: U1STU, 2003. P.56-59.

33.Востокин C.B. Использование визуального языка Граф Плюс для повышения надежности параллельных программ // Надежность и качество. Пенза: Инф.-изд. центр Пенз. гос. ун-та, 2003. С. 182-183.

34.Востокин C.B. Метод автоматического извлечения информации из свободного текста и оценка его надежности // Надежность и качество. Пенза: Инф.-изд. центр Пенз. гос. ун-та, 2002. С. 124-126.

35.Востокин C.B. Графическая модель программирования параллельных вычислений // Перспективные информационные технологии в научных исследованиях, проектировании и обучении. Самара: изд-во СГАУ, 2001. С.7-12.

36.Востокин C.B. Визуальный язык параллельного программирования системы ГРАФ // Надежность и качество. Пенза: Инф.-изд. центр Пенз. гос. ун-та, 1999. С.553-555.

37.Востокин C.B. Концепция разработки визуального языка параллельного программирования системы ГРАФ // БИКАМП-99: тез. докл. С.-Петербург, 1999. С. 121.

38.Востокин C.B. Разработка многопоточных программ в системе визуального программирования ГРАФ // Математика, компьютер, образование: тез. докл. Москва, 1999. Т.6. С.59.

39.Востокин C.B. Генерация текстов программ на основе графической модели системы ГРАФ // Техн. кибернетика, радиоэлектроника и системы управления: тез. докл. Таганрог, 1998. С. 105.

40.Востокин С.В.Технология генерации текстов параллельных программ по графической модели алгоритма // БИКАМП-98: тез. докл. С.Петербург, 1998. С.57-58.

41.Востокин C.B. Компилятор подсистемы отладки системы графического программирования ГРАФ // Королевские чтения: тез. докл. Самара, 1997. С.56-57.

42.Востокин C.B. Подсистема отладки графо-символических объектов // XXIII Гагаринские чтения: тез. докл. Москва, 1997. 4.5. С.88.

Основные научные результаты, полученные автором и выносимые на защиту.

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

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

3) Методика построения параллельных алгоритмов численного моделирования, включающая средства описания схем вычислений, алгоритмы кодирования схем, примеры прикладных численных методов.

4) Результаты анализа эффективности предложенного метода моделирования.

5) Программный комплекс дискретного моделирования вычислительных процессов и библиотека прикладных программ численного моделирования.

Структура диссертации. Диссертация состоит из введения, пяти глав, заключения, библиографического списка и приложений.

Основные результаты диссертации опубликованы в ведущих рецензируемых научных журналах и изданиях, в которых согласно перечню ВАК должны быть опубликованы основные научные результаты диссертации на соискание ученой степени доктора наук.

Предложенные в диссертации новые решения строго аргументированы и критически оценены по сравнению с другими известными результатами. Достоверность выводов подтверждена результатами проведенных вычислительных экспериментов на реальном оборудовании и имитационными экспериментами. В диссертации приведены рекомендации по использованию полученных научных выводов. Научные результаты применяются на различных предприятиях и в организациях РФ, что подтверждается соответствующими актами о реализации.

Таким образом, в диссертации решена новая крупная научная проблема, которая является актуальной и имеет важное научно-хозяйственное значение. Внедрение результатов вносит значительный вклад в развитие экономики страны.

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

ЗАКЛЮЧЕНИЕ

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

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

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

2) Описан метод визуализации модели, на котором основывается декомпозиция параллельного вычислительного алгоритма на совокупность последовательных процедур, а также метод построения алгоритмов, реализующих функциональные отношения модели по ее визуальному представлению в виде множества диаграмм. Данный метод, в отличие от известных подходов (CODE, HeNCE), соответствует современной практике программирования.

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

4) Предложена общая структура алгоритмов управления вычислениями с использованием модельного описания в форме паттерна, названного «Постоялец-Посетитель». Ее применение, в отличие от известных подходов, позволяет отделить код численного метода от управляющего кода при сохранении эффективности вычислений; она пригодна для широкого класса вычислительных сред.

5) Предложен метод имитационного моделирования вычислительных процессов, описанных в терминах графической объектной модели, и получены новые экспериментальные результаты дискретно-событийного моделирования исполнения вычислений в гетерогенных вычислительных средах с флуктуирующими характеристиками производительности и пропускной способности.

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

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

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

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

4) упростить подготовку модельных экспериментов с привлечением больших вычислительных ресурсов на основе применения каркасных библиотек, описывающих типовые вычислительные процессы.

Практическим результатом диссертации является разработка программного комплекса параллельных и распределенных вычислений ОгарЫЧиБ, включающего утилиты описания визуального представления схем вычислительных процессов, транслятор схем процессов, кодогенератор, интерпретатор, различные варианты среды времени исполнения, в том числе для проведения имитационных экспериментов с моделями процессов, и другие. Основные компоненты программного комплекса официально зарегистрированы Федеральной службой по интеллектуальной собственности, патентам и товарным знакам. Общий объем исходного кода данных компонент превышает 8000 строк.

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

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

1. Андрианов А.Н., Ефимкин К.Н., Задыхайло И.Б. Непроцедурный язык для решения задач математической физики // Программирование. 1991. №2. С. 80-94.

2. Антонов A.C., Воеводин Вл.В. Эффективная адаптация последовательных программ для современных векторно-конвейерных и массивно-параллельных супер-ЭВМ // Программирование. 1996. №4. С.37-51.

3. Берзигияров П.К. Программирование на типовых алгоритмических структурах с массивным параллелизмом // Вычислительные методы и программирование. 2001. Т. 2, Разд. 2. С. 1-16.

4. Буза М.К., Курбатский A.A. Об одной формальной модели программ // Программирование. 1984. №3. С. 16-20.

5. Буч Г. Объектно-ориентированный анализ и проектирование с примерами приложений на С++. М.: Издательство Бином; Пб.: Невский диалект, 1999.

6. Вальковский В.А., Котов В.Е., Марчук А.Г., Миренков H.H. Элементы параллельного программирования. М.: Радио и связь, 1983. 239 с.

7. Воеводин Вл.В., Филамофитский М.П. Суперкомпьютер на выходные // Открытые системы. 2003. №5. С. 43-48.

8. Ю.Вольтерра В. Математическая теория борьбы за существование. М.: Наука, 1976.

9. Востокин C.B. Метод описания пространственно распределенных параллельных процессов. Самара: изд-во СНЦ РАН, 2003. 84 с.

10. Востокин C.B. Объектно-ориентированный метод структурирования кода метакомпьютерного приложения // Информационные технологии. 2006. №5. С. 40-45.

11. Востокин C.B. Особенности реализации процедур сканирования параметрических пространств для сложных численных моделей // Математическое моделирование. 2006. Т. 18, №12. С. 125-128.

12. Востокин C.B. Применение метода парного взаимодействия объектов для построения сред разработки распределенных приложений // Вестник СамГТУ. 2005. №38. С.26-28.

13. Востокин C.B. Технология визуального проектирования параллельных и распределенных приложений // Системы управления и информационные технологии. 2006. №2 (24). С.39-43.

14. Востокин C.B. Технология моделирования распределенных систем, основанная на визуальном языке, и ее приложения // Известия СНЦ РАН. 2004. Т. 6, №1(10). С.185-193.

15. Востокин C.B., Курушина С.Е. Численное моделирование процесса конкуренции во флуктуирующих средах на кластерных вычислительных системах//Известия СНЦ РАН. 2005. Т. 7, №1(13). С.143-148.

16. Гамма Э., Хелм Р., Джонсон Р., Влиссидес Дж. Приемы объектно-ориентированного проектирования. Паттерны проектирования. СПб.: Питер, 2003. 368 с.

17. Головашкин Д. Л., Сойфер В. А. Анализ прохождения электромагнитного излучения через дифракционную линзу // Автометрия. 1999. Вып.6. С. 119121.

18. Калентьев A.A., Тюгашев A.A. ИПИ/CALS технологии в жизненном цикле комплексных программ управления. Самара: изд-во СНЦ РАН, 2006. 285 с.

19. Кельтон В., Лоу А. Имитационное моделирование. Классика CS. 3-е изд. СПб.: Питер; Киев: Издательская группа BHV, 2004. 847 с.

20. Коварцев А.Н. Автоматизация разработки и тестирования программных средств. Сам. гос. аэрокосм.универ. Самара, 1999. 150 с.

21. Корнеев В.В. Параллельные вычислительные системы. М.: Нолидж, 1999. 320 с.

22. Костин А.Е. Программный комплекс для сетевого имитационного моделирования дискретных систем с параллельными процессами // Управляющие системы и машины. 1987. №4. С. 98-102.

23. Котов В.Е. Сабельфельд В.К. Теория схем программ. M.: Наука, 1991.

24. Котов В.Е. Сети Петри. M.: Наука, 1984. 158с.

25. Котов В.Е., Нариньяни A.C. Асинхронные вычислительные процессы над памятью // Кибернетика. 1966. № 3. С. 64-71.

26. Кровчик Э. и др. .NET Сетевое программирование для профессионалов. М.: Изд-во Лори, 2005.

27. Крюков В.А., Удовиченко Р.В. Отладка DVM-программ // Программирование. 2001. № 3. С. 19-29.

28. ЗО.Мак-Кракен Д., Дорн У. Численные методы и программирование на Фортране. М.:Мир, 1977.31 .Михайлов A.C. Неравновесный фазовый переход в биологическом сообществе // ДАН СССР. 1978. Т. 243. С. 786-788.

29. Михайлов A.C., Упоров И.В. Индуцированный шумом фазовый переход и перколяционная задача для флуктуирующих сред с диффузией // ЖЭТФ. 1980. Т.79, №5(11). С. 1958-1972.

30. Михайлов A.C., Упоров И.В. Критические явления в средах с размножением, распадом и диффузией // Успехи физических наук. 1984. Т. 144, вып. I. С.79-112.

31. Михайлов A.C., Упоров И.В.Кинетика гетерогенной цепной реакции со случайной вариацией центров размножения // ЖФХ. 1982. Т. 56, № 3. С. 606-609.

32. Нестеренко Б.Б., Марчук В.А. Основы асинхронных методов параллельных вычислений. Киев: Наук. Думка, 1989. 171 с.

33. Питерсон Дж. Теория сетей Петри и моделирование систем / Пер. с англ. М.: Мир, 1984. 264 с.

34. Поспелов Д.А. Введение в теорию вычислительных систем. М.: Сов. радио, 1972. 280 с.

35. Рихтер Дж. Windows для профессионалов: Программирование для Windows NT 4 на базе Win32 API / Пер. с англ. М.: Издательский отдел Русская редакция ТОО Channel Trading Ltd., 1997.

36. Скотт М., Джеймс Н., Ким У. Microsoft.NET Remoting. М.: Русская Редакция, 2003.

37. Страуструп Б. Язык программирования С++, 3-е изд. / Пер. с англ. СПб.; М.: Невский Диалект, Издательство Бином, 1999.

38. Хакен Г. Синергетика. М.: Мир, 1980.

39. Хоар Ч. Взаимодействующие последовательные процессы. М.: Мир, 1989.

40. Холодниок М., Клич А., Кубичек М., Марек М. Методы анализа нелинейных динамических моделей. М.: Мир, 1991. 368 с.

41. Хьюз К., Хьюз Т. Параллельное и распределенное программирование с использованием С++. М.: Издательский дом Вильяме, 2004. 672 с.

42. Эйген М. Самоорганизация материи и эволюция биологических макромолекул. М.:Мир, 1973.

43. Эндрюс Г.Р. Основы многопоточного, параллельного и распределенного программирования. М.: Издательский дом Вильяме, 2003.

44. Abrahamson К., Adler A., Higham L., Kirkpartrick D. Probabilistic solitude verification on a ring // In Proceedings of the Fifth Annual ACM Symposium on Principles of Distributed Computing. Calgary, Canada, August 1986. P. 161-173.

45. Abramson D., Giddy J., Kotler L. High performance parametric modeling with nimrod/g: Killer application for the global grid? // Proceedings of the 14th International Parallel and Distributed Processing Symposium (IPDPS 2000). April 2000. P. 520-528.

46. Adams J.C., Brainerd W.S., Martin J.T., Smith B.T., Wagener J.L. Fortran 90 Handbook: complete ANSI/ISO Reference. McGraw-Hill, 2000. 822 c.

47. Afek Y., Awerbuch В., Gafni E. Applying static network protocols to dynamic networks // In Proceedings of the 28th IEEE Symposium on Foundations of Computer Science. Los Angeles, California, October 1987. P. 358-370.

48. Aho A.V., Ullman J., Wyner A., Yannakakis M. Bounds on the size and transmission rate of communication protocols // Computers and Mathematics with Applications. 1982. No 8(3). P. 205-214.

49. Armstrong J., Virding R., Wikstrum C., Williams M. Concurrent programming in Erlang. 2:nd Edition. Prentice Hall, 1996.

50. Attiya H., Snir M., Warmuth M.K. Computing on an anonymous ring // Journal of the ACM. October 1988. No 35(4). P. 845-875.

51. Awerbuch B. Complexity of network synchronization // Journal of the ACM. October 1985. No 32(4). P. 804-823.

52. Aztec. A Massively Parallel Iterative Solver Library for Solving Sparse linear Systems. http://www.cs.sandia.gov/CRF/aztecl .html.

53. Babaoglu O. Paralex: An Environment for Parallel Programming in Distributed Systems // Proc. ACM Int. Conf. On Supercomputing. July, 1992.

54. Bacci В., Danelutto M., Pelagatti S., Vanneschi M. SklE: an heterogeneous environment for HPC applications II Parallel Computing. 1999. Vol 25, No 1314. P. 1827-1852.

55. Baer L.J., Bovet D.P. Compilation of arithmetic expressions for parallel computations // Proc. IFIP Congress 68. Amsterdam: North Holland Publ. Co., 1968. P. 340-346.

56. Bailey D., Cuny B., Loomis C. Paragraph: Graph editor support for parallel programming environments // International Journal of Parallel Programming. 1990. No 19(2). P. 75-110.

57. Bal H.E., Kaashoek M.E., Tanenbaum A.S. Orca: a language for parallel programming on distributed systems // IEEE Trans. Softw. Eng. 1992. Vol. 18, No 3. P. 190-205.

58. Bal H.E., Steiner J.G., Tanenbaum A.S. Programming languages for distributed computing systems // ACM Computing Surveys. September1989. No 21(3). P. 261-322.

59. Balay S., et al. PETSc Web page. 2001. http://www.mcs.anl.gov/petsc.

60. Baratz A.E., Segall A. Reliable link initialization prodecures // IEEE Transactions on Communications. February 1988. Vol. COM, No 36(2). P. 144-152.

61. Beguelin A., Dongarra J.J, Geist G.A., Manchek R., Sunderam V.S. Graphical development tools for network-based concurrent supercomputing // Proc. of Supercomputing 91. Albuquerque, 1991. P. 435-444.

62. Beguelin A., Nutt G., Collected Papers on Phred // Dept. of Computer Science, Univ. Of Colorado, CU-CS-511-91. Jan, 1991.

63. Ben-Or M. Another advantage of free choice: Completely asynchronous agreement protocols // In Proceedings of the Second Annual ACM Symposium on Principles of Distributed Computing. New York: Association for Computing Machinery, August 1983. P. 27-30.

64. Beowulf. http://www.beowulf.org.

65. Bernstein Ph.A, Hadzilacos V, Goodman N. Concurrency Control and Recovery in Database Systems. Massachusetts: Addison-Wesley Reading, 1987.

66. BERT 77: Automatic and Efficient Parallelizer for FORTRAN. http://basement-supercomputing.com/bert/.

67. Bloom B. Constructing two-writer atomic registers // IEEE Transactions On Computers. 1988. No 37(12). P.1506-1514.

68. Bracha G. An 0(log n) expected rounds randomized byzantine generals algorithm // In Proceedings of the 17th Annual ACM Symposium on Theory of Computing. IEEE, May 1985. P. 316-326.

69. Bratvold T.A. Skeleton-based parallelization of functional programs: PhD thesis. Dept. Of Computing and Electrical Engineering. Edinburgh: Heriot-Watt University, 1994.

70. Browne J.C., Azam M., Sobek S. CODE: A Unified Approach to Parallel Programming // IEEE Software. July, 1989. P. 11.

71. Bruno G., Harcheto G. Process tolerable Petri net for the rapid prototyping of process control systems // IEEE Transsoftware Eng. 1986. Vol. SE-12. P. 346357.

72. Burke S., Campana S., Peris A.D., Donno F., Lorenzo P.M., Santinelli R., Sciaba A. gLite 3.0 User Guide. Manuals Series. CERN-LCG-GDEIS-722398. May 19, 2006.

73. Carriero N., Gelernter D., Leichter J. Distributed Data Structures in Linda // Thirteenth ACM Symp. on Principles of Prog. Langs. 1986. P. 236-242.

74. Catlett Ch., Smarr L. Metacomputing // Comm. ACM. 1992. No 35(6) P. 44-52.

75. Chandy K.M., Kesselman C. Compositional C++: Compositional parallel programming. Technical Report Caltech-CS-TR-92-13. California Institute of Technology, 1992.

76. Chandy K.M., Haas L.M., Misra J. Distributed deadlock detection // ACM Transactions on Computer Systems. May 1983. No 1(2). P. 144-156.

77. Chandy K.M., Lamport L. Distributed snapshots: determining global states of a distributed system // ACM Transactions on Computer Systems. February 1985. No 3(1). P. 63-75.

78. Chandy K.M., Misra J. Parallel Program Design. Addison-Wesley, 1988.

79. Chandy K.M. Misra J. The drinking philosophers problem // ACM Transactions on Programming Languages and Systems. October 1984. No 6(4). P. 632-646.

80. Cole M.I. Algorithmic Skeletons: Structured Management of Parallel Computation. Massachusetts, Cambridge, Boston: MIT Press, 1989.

81. Commoner F., Holt A.W., Even S., Pnueli A. Marked directed graphs // Journal of Computer and System Sciences. December 1971. No 5(6). P. 511-523.

82. Condor® Version 6.6.8 Manual. Condor Team, University of Wisconsin-Madison. February 8, 2005.http://www.cs.wisc.edU/condor/manual/v6.6.8/ref.html.

83. Courtney A. Phantom: An Interpreted Language for Distributed Programming // Proceedings of the USENIX Conference on Object-Oriented Technologies (COOTS). Monterey, California, June 1995.

84. Darlington J., Guo Y., To H.W., Yang J. SPF: Structured parallel Fortran // Proc. Of the Sixth Parallel Computing Workshop. Japan. Kawasaki, 1996. P. 16.

85. DCOM Technical Overview. Redmond, Wash.: Microsoft Corp., 1996.

86. DeFanti T., Foster I., Papka M.E., Stevens R., Kuhfuss T. Overview of the I-WAY: Wide Area Visual Supercomputing // International Journal of Supercomputing Applications. 1996. No 10(2).

87. Diffe Wh., Hellman M.E. Privacy and authentication: an introduction to cryptography // Proceedings of the IEEE. March 1979. No 67(3). P. 397-427.

88. Dijkstra E.W. Hierarchical ordering of sequential processes // Acta Informática. 1971. No 1. P.l 15-138.

89. Dijkstra E.W. Self-stabilizing systems in spite of distributed control // Communications of the ACM. November 1974. No 17(11). P. 643-644.

90. Dijkstra E.W. Solution of a problem in concurrent programming control // Communications of the ACM. September 1965. No 8(9). P. 569.

91. Dijkstra E.W. The structure of the "the" multiprogramming system // Communications of the ACM. May 1968. No 11(5). P. 341-346.

92. Dijkstra E.W., Scholten C.S. Termination detection for diffusing computations // Information Processing Letters. August 1980. No 11(1). P. 1-4.

93. DOE Science Grid, http://doesciencegrid.org/.

94. Dolev D. The Byzantine generals strike again // Journal of Alorithms. March 1982. No 3(1). P. 14-30.

95. Dot NET Framework Developer Center, http://msdn2.microsoft.com/en-us/netframework/default.aspx.

96. DOUG — Domain decomposition On Unstructured Grids. http://www.maths.bath.ac.uk/~parsoflt/doug/.

97. Eerola P. et al. The NorduGrid production Grid infrastructure, status and plans // Proc. 4th Intel Workshop on Grid Computing (GRID'03). IEEE CS Press, 2003. P. 158-165.

98. Enabling Grids for E-sciencE project, http://www.eu-egee.org/.

99. Entropia. 1998. http://www.entropia.com/.

100. Erwin D. Snelling D. UNICORE: A Grid Computing Environment. Proceedings of 7th International Conference Euro-Par. LNCS. Manchester, UK: Springer, 2001. No 2150. P. 825-834.

101. Extensible Markup Language (XML). http://www.w3.org/XML/.

102. FAFNER. RSA Factoring By Web project. http://www.npac.syr.edu/factoring.html.

103. Fanning S. Napster: P2P file sharing. 1999. http://www.napster.com.

104. Feo J.T., Cann D.C., Oldehoeft R.R. A report on Sisal language project // Journal of Parallel and Dist. Comp. 1990. No 10. P. 349-366.

105. Fischer M.J., Lynch N., Paterson M.S. Impossibility of distributed consensus with one faulty process // Journal of the ACM. April 1985. No 32(2). P. 374382.

106. Foster I. What is the Grid? A Three Point Checklist // GRIDToday, July 20, 2002.

107. Foster I., Kesselman C. Globus: A metacomputing intrastructure toolkit // International Journal of Supercomputer Applications. 1997. No 11(2). P. 115128.

108. Foster I., Kesselman C. The Grid: Blueprint for a New Computing Infrastructure. Morgan Kaufmann, 1998.

109. Foster I., Kesselman C., Tuecke S. The anatomy of the grid: Enabling scalable virtual organizations // International Journal of High Performance Computing Applications. 2001. No 15(3). P. 200-222.

110. Gafni E. Chou Ch.T. Understanding and verifying distributed algorithms using stratified decomposition // In Proceedings of the 7th annual ACM Symposium on Principles of Distributed Computing. Toronto, Ontario, Canada, August 1988. P. 44-65.

111. Gallager R.G., Humblet P.A., Spira P.M. A distributed algorithm for minimum-weight spanning trees // ACM Transactions on Programming Languages and Systems. January 1983. No 5(1). P. 66-77.

112. Gelernter D. Generative communication in Linda // ACM Trans. On Prog. Languages and Systems. 1985. No 1. P. 80-112.

113. Gray J.N. Notes on database operating systems // Operating Systems: An Advanced Course / Ed. by Bayer R., Graham R. M., Seegmuller G. Berlin, Heidelberg, New York: Springer-Verlag, 1978. P. 393-481.

114. GridCafe, CERN. http://gridcafe.web.cern.ch/gridcafe/.

115. Grimshaw A.S., Wulf W.A. The Legion Vision of a Worldwide Virtual Computer // Comm. of the ACM. January 1997. Vol. 40, No 1.

116. Halpern J.Y., Moses Y. Knowledge and common knowledge in a distributed environment // In Proceedings of the Third Annual ACM Symposium on Principles of Distributed Computing. New York: Association for Computing Machinery, 1984. P. 50-61.

117. Harel D. Statecharts: A Visual Formalism for Complex Systems // Science of Computer Programming. 1987. Vol. 8.

118. Herlihy M.P. Impossibility and universality results for wait-free synchronization // In Proceedings of the 7th annual ACM Symposium on Principles of Distributed Computing. Toronto, Ontario, Canada, August 1988. P. 276-290.

119. High Performance Fortran. 2006. http://dacnet.rice.edu/Depts/HPF/index.cfm.

120. Hoare C.A.R. Monitors: An operating system structuring concept // Communications of the ACM. October 1974. No 17(10). P. 549-557.

121. Horstmann C.S., Cornell G. Core Java™ 2: Volume II Advanced Features. Prentice Hall PTR, 2001.

122. Hoscheck W., Jaen-Martinez J., Samar A., Stockinger H., Stockinger K. Data management in an international data Grid project // Proceedings 1st IEEE/ACM International Workshop on Grid Computing (Grid 2000). December 2000. P. 77-90.

123. Hudak O. Conception, evolution, and application of functional programming languages // ACM Computing Surveys. September1989. No 21(3). P. 359-411.

124. International Standard Organization. Information Technology: Portable Operating System Interface. Pt. 1 System Application Program Interface. 2nd ed. Std 1003.1. ANSI/IEEE, 1996.

125. Jacobson I., Christerson M., Overgard G. Object-Oriented Software Ingineering. Workinggham, England: Addison-Wesley Publishing Company, 1992.

126. Java Technology. Sun Microsystems, http://java.sun.com/.

127. Jones M.T., Plassmann P.E. BlockSolve95 users manual: Scalable library software for the parallel solution of sparse linear systems. Report ANL-95/48. Argonne National Laboratory, 1995.

128. Kale L.V., Krishnan S. CHARM++: A Portable Concurrent Object Oriented System Based On C++ // Proceedings of the Conference on Object Oriented Programming Systems, Languages and Applications. ACM Sigplan Notes,1993. Vol. 28, No. 10. P. 91-108.

129. Krauter K., Buyya R., Maheswaran M. A taxonomy and survey of grid resource management systems for distributed computing // Software Practice and Experience. 2002. No 32. P. 135-164.

130. Lamport L. A new solution of Dijkstra's concurrent programming problem // Communications of the ACM. August 1974. No 17(8). P. 453^155.

131. Lamport L. How to write a long formula // Formal Aspects of Computing.1994. No 6. P. 580-584.

132. Lamport L. On interprocess communication // Distributed Computing. 1986. No 1(2). P. 77-101.

133. Lamport L. Specifying Systems. The TLA+ Language and Tools for Hardware and Software Engineers. Addison-Wesley, 2002.

134. Lamport L. The temporal logic of actions // ACM Transactions on Programming Languages and Systems. May 1994. No 16(3). P. 872-923.

135. Lamport L. Time, clocks, and the ordering of events in a distributed system // Communications of the ACM. July 1978. No 21(7). P. 558-565.

136. Lamport L. Using time instead of timeout for fault-tolerant distributed systems // ACM Transactions on Programming Languages and Systems. April1984. No 6(2). P. 254-280.

137. Lamport L., Shostak R., Pease M. The Byzantine general's problem // ACM Transactions on Programming Languages and Systems. July 1982. No 4(3). P. 382-401.

138. Levine D., Hailstorm Ph., Noelle D., Walenz B. Experiences with the PGAPack Parallel Genetic Algorithm Library. Technical Report ANL/MCS-TM-228. Argonne National Laboratory, July 1997.

139. Liskov B. The argus language and system // Distributed Systems: Methods and Tools for Specification / Ed. by Paul M., Siegert H.J. Springer-Verlag,1985. Ch. 7. P. 343-430.

140. Loyall J.P. Specification of Concurrent Systems Using Graph Grammars. PhD thesis, Dept. of Comp. Sci, Univ. of Illinois, Urbana-Champaign. May 1991.

141. M.Ellert et al. Advanced Resource Connector middleware for lightweight computational Grids // Future Generation Computer Systems. 2007. No 23. P. 219-240.

142. MacDonald S. Design patterns in enterprise // Proc. of CASCON'96. Toronto, 1996. P. 1-10.

143. MacDonald S., Szafron D., Schaeffer J. From patterns to frameworks to parallel programs // IEEE Concurrency. 1999. Vol. 7, No 1-4. P. 1-21.

144. Mascagni M. Serial and Parallel Random Number Generation // Quantum Monte Carlo in Physics and Chemistry / Ed. by Nightingale P., Umrigar C. New York, Berlin: Springer-Verlag, 1999. P. 277-288.

145. Milner R.A. Calculus of Communicating Systems // Lecture Notes in Computer Science. New York: Springer-Verland, 1980.

146. Modula-3 Resource Page, http://www.m3.org/.

147. Nahrstedt K., Chu H., Narayan S. QoS-aware resource management for distributed multimedia // Journal of High-Speed Networking (Special Issue on Multimedia Networking). December 2000. No 7(3-4). P. 227-255.

148. NAMD — Scalable Molecular Dynamics. http://www.ks.uiuc.edu/Research/namd/.

149. Newton P., Browne J.C. The CODE 2.0 Graphical Parallel Programming Language // Proc. of the Sixth ACM International Conference on Supercomputing. 1992. P. 167-177.

150. Next Generation Grid(s) European Grid Research 2005 2010 Expert Group Report. Monday, 16th June 2003.

151. Occam™ Programming Manual. Prentice-Hall International, 1984.

152. Owicki S., Gries D. An axiomatic proof technique for parallel programs // Acta Informática. 1976. No 6(4). P. 319-340.

153. Parallel Virtual Machine, http://www.csm.ornl.gov/pvm/.

154. Pease M., Shostak R., Lamport L. Reaching agreement in the presence of faults // Journal of the ACM. April 1980. No 27(2). P. 228-234.

155. Pelagatti S. Structured Development of Parallel Programs. London, Bristol: Taylor & Francis, 1997.

156. Peterson G. Fischer M. Economical solutions for the critical section problem in a distributed system // In Proceedings of the 9th Annual ACM Symposium on Theory of Computing. ACM, May 1977. P. 91-97.

157. Peterson G.L. An 0(n log n) unidirectional algorithm for the circular extrema problem // ACM Transactions on Programming Languages and Systems. October 1982. No 4(4). P. 758-762.

158. Peterson G.L. Concurrent reading while writing // ACM Transactions on Programming Languages and Systems. January 1983. No 5(1). P. 46-55.

159. Pnueli A. The temporal logic of programs // Proc. of the 18th Symposium on the Foundations of Computer Science. ACM, Nov. 1977. P. 46-57.

160. Pnueli A. The temporal semantic of concurrent programs // Theoretical Computer Science. 1981. No 13. P. 45-60.

161. Rabin M.O. N-process mutual exclusion with bounded waiting by 4 log n-valued shared variable // Journal of Computer and System Sciences. 1982. No 25(1). P. 66-75.

162. Ramamoorthy C.V., Park J.H, Li H.F. Compilation techniques for recognition of parallel processable tasks in arithmetic expressions // IEEE Trans. On Computers. 1973. Vol. C-22, No 11. P. 981-998.

163. Raynal M. Algorithms for Mutual Exclusion. Cambridge, Massachusetts: MIT Press, 1986.

164. Reference Manual for the Ada Programming Language. Ada Joint Program Office. Washington, D.C.: Department of Defense, February 1983.

165. Rost J. D2R: A Dynamic Dataflow Representation for Task Scheduling // ACM SIGPLAN Notices. August 1993. Vol. 28, No. 8.

166. Rumbaugh, J, Blaha, M, Premerlani, W, Eddy, F., Loresen, W. Object-Oriented Modeling and Design. Englewood Cliffs, New Jersey: Prentice-Hall, 1991.

167. Russian Data Intensive Grid, http://rus.egee-rdig.ru/.

168. Schloegel K, Karypis G, Kumar V. Parallel static and dynamic multi-constraint graph partitioning // Concurrency and Computation: Practice and Experience. 2002. Vol. 14, Issue 3. P. 219 240.

169. Schneider F.B. Andrews G.R. Concepts for concurrent programming // Current Trends in Concurrency / Ed. by de Bakker J.W, de Roever W.-P, Rozenberg G. Berlin, Heidelberg, New York: Springer-Verlag, 1986. P. 669716.

170. Schwartz R.L, Melliar-Smith P.M. From state machines to temporal logic: specication methods for protocol standards // IEEE Transactions on Communications. December 1982. Vol. COM-30, No 12. P. 2486-2496.

171. Serot J., Ginhac D., Derutin J-P. Skipper: A skeleton-based parallel programming environment for real-time image processing applications // LNCS, 1999. No 1662. P. 296-305.

172. Singh A., Schaeffer J., Szafron D. Views on template-based parallel programming//Proc. ofCASCON'96. Toronto, 1996. P. 1-12.

173. Siu S., De Simone M., Goswamiti D., Singh A. Design patterns for parallel programming // Parallel and Distributed Processing Techniques and Applications. California. Pasadena, 1996. P. 230-240.

174. Skeen M.D. Crash Recovery in a Distributed Database System. PhD thesis, University of California. Berkeley, May 1982.

175. Skillicorn D.B., Hill J., McColl B. Questions and answers about BSP // Scientific programming. 1997. Vol 6, No 3. P. 249-274.

176. Solomon .A., Russinovich M. Inside Microsoft Windows 2000. Microsoft Press, 2000.

177. Spector A.Z., Thompson D., Pausch R.F., Eppinger J.L., Duchamp D., Draves R., Daniels D.S., Bloach J.J. Camelot: A Distributed Transaction Facility for Mach and the Internet. Technical Report CMU-CS-87-129. Carnegie Mellon University, 1987.

178. Sulistio A., Yeo Ch.Sh., Buyya R. A taxonomy of computer-based simulations and its mapping to parallel and distributed systems simulation tools // Software — Practice and Experience. 2004. No 34. P. 653-673.

179. Sun Grid Engine, http://gridengine.sunsource.net.

180. Thain D., Tannenbaum T., Livny M. Distributed Computing in Practice: The Condor Experience // Concurrency: Pract. Exper. 2005. Vol. 17, No. 2-4. P. 323-356.

181. The Biomedical Informatics Research Network (BIRN) Portal. https://legacy-portal.nbirn.net/BIRN/.

182. The Common Object Request Broker: Architecture and Specification, Version 3.0. Framingham, Mass.: Object Management Group, 2002. http://www.omg.org.

183. The Grid3 collaboration, http://www.ivdgl.org/grid2003/.

184. The MPI Forum, http://www.mpi-forum.org/.

185. The ScaLAPACK Project, http://www.netlib.org/scalapack.

186. The Unified Modeling Language for Object-Oriented Development, Documentation set, ver. 1.1. Rational Software Corp., September 1997.

187. Thiagarajan P.S. Some aspects of net theory // The analysis of Concurrent Systems / Ed. by Denvir B.T., Harwood W.T., Jackson M.I., Wray M.J. Berlin, Heidelberg, New York: Springer-Verlag, 1985. P. 26-54.

188. ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

189. ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «САМАРСКИЙ ГОСУДАРСТВЕННЫЙ АЭРОКОСМИЧЕСКИЙ УНИВЕРСИТЕТ ИМЕНИ АКАДЕМИКА С.П. КОРОЛЕВА» (СГАУ)1. На правах рукописи

190. ВОСТОКИН СЕРГЕЙ ВЛАДИМИРОВИЧ

191. ГРАФИЧЕСКАЯ ОБЪЕКТНАЯ МОДЕЛЬ ПАРАЛЛЕЛЬНЫХ ПРОЦЕССОВ И ЕЕ ПРИМЕНЕНИЕ В ПРОГРАММНЫХ КОМПЛЕКСАХ ЧИСЛЕННОГО1. МОДЕЛИРОВАНИЯ

192. Специальность: 05.13.18 Математическое моделирование, численные методы и комплексы программ