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

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

ГОРСКИЙ СЕРГЕЙ АЛЕКСЕЕВИЧ

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

05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Иркутск-2008

003457994

Работа выполнена в Институте динамики систем и теории управления Сибирского отделения Российской академии наук (ИДСТУ СО РАН).

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

Феоктистов Александр Геннадьевич

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

Массель Людмила Васильевна

кандидат технических наук, доцент Хмельное Алексей Евгеньевич

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

моделирования СО РАН

(г. Красноярск)

Защита состоится 25 декабря 2008 г. в 10 часов на заседании диссертационного совета Д 003.021.01 при Институте динамики систем и теории управления СО РАН по адресу: 664033, г. Иркутск, ул. Лермонтова, 134.

С диссертацией можно ознакомиться в библиотеке ИДСТУ СО РАН.

Автореферат разослан 24 ноября 2008 г.

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

д.ф.-м.н.

А.А. Щеглова

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

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

На сегодняшний день разработаны разные модели, методы, алгоритмы и средства, ориентированные на поддержку различных этапов создания и выполнения параллельных программ (см., например, работы С.М. Абрамова, O.JI. Бандман, А.Б. Барского, В.В. Воеводина, Вл.В. Воеводина, И.Б. Задыхайло, В.Д. Корнеева, В.А. Крюкова, А.О. Лациса, И.А. Легалова, В.Э. Малышкина, Г.А. Опарина, Т.П. Плакса, В.В. Топоркова, Д. Ивенса, Э. Гейтса, Н. Макдонал-да, Д. Гелернтера, Г.Р. Эндрюса, Ф.Г. Энслоу и др.). Однако массовое создание и использование таких программ сдерживается рядом нерешенных до конца проблем параллельного программирования, возникающих перед рядовым пользователем. В числе таких проблем: сложность выявления параллелизма алгоритма решаемой задачи и учета всех специфических особенностей аппаратного обеспечения и коммуникационных сред, возникающая в процессе разработки параллельной программы, выбора нужного языка (или системы) параллельного программирования и дальнейшего написания текста программы; необходимость обеспечения эффективного выполнения параллельной программы и ее переносимости; специфичный по сравнению с ПЭВМ интерфейс для доступа к вычислительной установке и управления процессом решения задачи.

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

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

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

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

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

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

Объектом исследования являются теория и практика параллельного программирования.

Предметом исследования являются методы и инструментальные средства построения асинхронных параллельных программ.

Методы исследования. Для решения поставленных задач использованы методы объектно-ориентированного и сборочного программирования, теории построения трансляторов, баз данных, создания языков и инструментальных средств параллельного программирования.

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

1 Горбунов-Посадов М.М. Системное обеспечение пакетов прикладных программ / М.М. Горбунов-Посадов, Д.Л. Корягин, В В. Мартынюк. - М.: Наука, 1990. - 208 с.

2 Инструментальные средства построения и эксплуатации пакетов знаний / Г. А. Опарин, А.Г. Феоктистов,

Д.Г. Феоктистов, А Е. Журавлев // Управляющие системы и машины. - 1997.-№1-3.-С.138-143.

4

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

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

Исследование, разработка и применение рассматриваемых в диссертации программных средств выполнялись в рамках проекта СО РАН 3.2.6 «Интегрированные информационно-вычислительные и коммуникационные ресурсы: ин-теллектные методы организации, автоматизации разработки и применения» (2004-2006 гг., блок 1 «Распределенная вычислительная САТУРН-среда»); проекта СО РАН «Разработка научных основ распределенной информационно-аналитической системы на основе ГИС и Веб-технологий для междисциплинарных исследований» междисциплинарной программы 4.5.2 (2007-2009 гг., блок 2 «Интеллектные методы и инструментальные средства разработки и ком-плексирования распределенных информационно-вычислительных ресурсов»); проекта РФФИ № 06-01-00340 «Разработка и исследование булевых моделей предметной области в задаче планирования при синтезе программ».

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

Апробация. Основные результаты работы были представлены на V - VIII Школах-семинарах молодых ученых «Математическое моделирование, управление и информационные технологии» (Иркутск, 2004 г., 2005 г., 2006 г.), на XLIII Международной научной студенческой конференции «Студент и научно-технический прогресс» (Новосибирск, 2005 г.), на III Всероссийской молодежной конференции «Под знаком £» (Омск, 2005 г.), на V и VI Межрегиональных школах-семинарах «Распределенные и кластерные вычисления» (Красноярск, 2005 г., 2006 г.), на Всероссийском конкурсе инновационных проектов аспирантов и студентов по приоритетному направлению развития науки и техники «Информационно-телекоммуникационные системы» (Москва, 2005 г.), на XI Байкальской Международной конференции «Информационные и математические технологии в научных исследованиях» (Иркутск, 2006 г.), на III Междуна-

родной конференции «Параллельные вычисления и задачи управления (РАСО)» (Москва, 2006 г.), на Второй школе-семинаре молодых ученых «Управление большими системами» (Воронеж, 2007 г.), на Международных научных конференциях «Параллельные вычислительные технологии (РАУТ)» (Челябинск, 2007 г.; Санкт-Петербург, 2008 г.), а также неоднократно на семинарах ИДСТУ СО РАН.

Публикации и личный вклад автора. Результаты диссертации отражены в 14-ти научных работах (в том числе 2 статьи в журналах, рекомендованных ВАК для опубликования основных научных результатов диссертации на соискание ученой степени доктора или кандидата наук). В перечисленных публикациях все результаты, связанные с алгоритмизацией, программной реализацией и вычислительным экспериментом на ЭВМ, получены автором лично. Результаты по моделям и методам организации интеллектуальных пакетов для вычислительных кластеров получены совместно с Феоктистовым А.Г. и являются неделимыми. Из совместных работ с Опариным Г.А. и Новопашиным А.П. в диссертацию включены только те результаты, которые принадлежат лично автору.

Структура работы. Диссертация состоит из введения, четырех глав, заключения, библиографии из 91 наименований и 6 приложений. Общий объем работы - 145 страниц, из которых 117 страниц основного текста, включающего 30 рисунков и 7 таблиц.

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

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

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

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

| Разработка пакетов прикладных программ (пакетный подход) [

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

Методы разработки модульной системы "с нуля"

Автоматизация сборки целевых программ из

компонентов библиотек модулей

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

| Нисходящие методы разработки |-

Классический подход

-----Конструктивный подход г

-| Восходящие методы разработки |

Классический подход | >| Архитектурный подход ----

-включает

---применяет

|Целенаправленная конструктивная реализация!

Рис. I. Подходы к созданию модульных систем

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

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

В простейшем случае концептуальная схема предметной области интеллектуального пакета определяется структурой4 S=<Z, W, F>, где Z={zt, z2.....

- множество параметров предметной области; W={wi, ..., if*} - множество допустимых типов данных; F={f,,/2, ...,/„} - множество вычислительных модулей5 предметной области. С каждым модулем f, связано два множества параметров IN', OUT' с Z, называемых соответственно его входом и выходом. Вход модуля /^'определяет параметры, значения которых необходимо задать, чтобы

3 Тыугу Э.Х. Концептуальное программирование / Э.Х. Тыугу. - М.: Наука, 1984. - 256 с.

4 Опарин Г.А. Булево моделирование планирования действий в распределенных вычислительных системах / Г.А. Опарин, А.П. Новопашиц // Теория и системы управления. - 2004. - № 5. - С. 105-108.

5 Далее в диссертации модуль рассматривается как объект концептуальной схемы предметной области.

получить значения параметров, представленных выходом OUT'. План решения задачи строится автоматически по непроцедурной постановке задачи, формулируемой на S, и является в общем случае параллельным.

В третьем разделе первой главы проведен анализ существующих методов и средств поддержки параллельного программирования с точки зрения их использования для достижения поставленной в рамках диссертационной работы цели. Из известных моделей параллельного программирования (модели передачи сообщений, использования общей памяти, прямого доступа к удаленной памяти) наиболее эффективной является модель, основанная на использовании общей памяти. Однако вычислительный кластер представляет собой вычислительную установку с распределенной памятью (его вычислительные узлы могут быть представлены SMP-машинами, ко на сегодняшний день, как правило, с ограниченным числом процессоров). В этом случае наиболее целесообразным является выбор модели, базирующейся на передаче сообщений. В большинстве случаев реализация данной модели осуществляется с помощью одной из двух наиболее популярных коммуникационных библиотек: MPI или PVM. Обе библиотеки имеют свои сильные и слабые стороны. Существенными преимуществами PVM, с точки зрения решения прикладной задачи, являются наличие динамической системы управления вычислительными процессами и поддержка межъязыкового взаимодействия между С и Fortran. Последнее обстоятельство особенно важно для пользователя, так как именно эта языки использованы в большинстве библиотек алгоритмов и программ прикладного характера.

Анализ систем, предназначенных для автоматизации параллельного программирования, показывает, что для интеллектуальных пакетов требуется создание специализированных средств решения данной проблемы. Это продиктовано тем, что одни системы (например, CODE, HeNCE, Grade, EDPEPPS, T-система) нацелены в основном на описание алгоритма решения отдельно взятой задачи, что делает их мало пригодными в рамках технологии интеллектуальных пакетов, а другие системы (например, НОРМА или СиКруС) не обладают достаточными возможностями для эффективного построения и выполнения асинхронной параллельной программы.

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

6 Гэри М. Вычислительные машины и трудно решаемые задачи / М. Гэри, Д Джонсон. -8

М.: Мир, 19S2. -416 с

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

Итак, в первой главе диссертации на основе анализа методов и средств модульного и параллельного программирования были определены основные аспекты технологии конструирования и выполнения параллельных программ в интеллектуальных пакетах. Такая технология ориентирована на класс задач вычислительного эксперимента, в которых анализируются свойства некоторого объекта посредством проведения параллельных многовариантных расчетов над его математической моделью. В частности, были выделены основные этапы построения интеллектуального пакета и выбраны программно-аппаратные и языковые составляющие технологии параллельного программирования в этой системе: вычислительный кластер + модель передачи сообщений + библиотека PVM + языки программирования С и Fortran + авторские система автоматизации параллельного программирования и статико-динамический алгоритм выполнения асинхронного вычислительного процесса.

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

В первом разделе второй главы множество допустимых типов данных W концептуальной схемы предметной области S расширяется новым типом данных параметр-список (здесь термин список понимается в смысле Д. Кнута4), предназначенным для определения параллельных структур данных9. Параметр-список создается на основе одного параметра любого типа (скалярного, векторного или матричного) и включает множество вариантов значений этого параметра. Число элементов параметра-списка задается параметром-скаляром целого типа Основное отличие параметра-списка от параметра-массива заключается в способе обработки элементов параметров таких типов. Параметр-массив целиком передается в вычислительный модуль, в котором далее осуществляется его обработка, в то время как параметр-список может обрабатываться поэлементно (в общем слу-

7 Гершуни Д.С. Планирование вычислений в системах жесткого реального времени (обзор и перспективы) / ДС. Гершуни // Вычислительная техника. Системы управления. -1991. Выл. 6. - С. 4-51.

8 Кнут Д. Искусство программирования / Д. Кнут. - М; СПб.; Киев: ИД «Вильяме», 2000. Т. 1-3.

9 Под параллельной структурой данных здесь понимается способ организации данных, позволяющий выполнять независимую параллельную обработку элементов этой структуры в рамках конкретной вычислительной системы (например, параллельный список в языке программирования Пифагор [Легалов А.И. Функциональный язык для создания архитектурно-независимых параллельных программ / А.И. Легалов // Вычислительные технологии. - 2005, №1(10). -С.71-89.].

чае параллельно) множеством экземпляров вычислительного модуля на разных процессорах. Наличие в концептуальной схеме предметной области параметров-списков приводит к появлению в процессе вычислений новых объектов (элементов параметров-списков и обрабатывающих их экземпляров модулей) и требует построения модели с более высоким уровнем детализации объектов предметной области и отношений между ними. Определим модель вычислений в виде структуры CM=<S, PE, FE>, где S - это рассмотренная выше концептуальная схема предметной области, РЕ={рги реъ ..., pev} - множество элементов параметров-списков, FE={fehfeb ■■■,fea} - множество экземпляров модулей предметной области, v,ueN. Для формального описания модели вычислений применим следующую нотацию10: Р(0\(п\,п2):02(щ,щ)/с), где 0\, 02 - множества объектов предметной области, связанные бинарным отношением R; щ, п2 - числа, которые означают соответственно минимальное и максимальное число элементов 0\, связанных с элементом 02; щ, щ - числа, которые означают соответственно минимальное и максимальное число элементов 02, связанных с элементом Ой с- ограничение целостности, накладываемое на элементы 02, участвующие в отношении R. Тогда связи между множествами основных объектов модели вычислений зададим следующими отношениями" (рис. 2):

1) /?i(Z(l, т): l¥(l, 1)) - типизированные параметры;

2) R2(Z(l, m):F( 1, rí)/ci) - входные параметры из ZI с Z для модулей из F; c¡ - ограничение на множество входных параметров модуля (/jV'n OUT' =0);

3) R}{Z{\, m):F(l, п)/с\) - выходные параметры из ZO с Z для модулей из F; с i - ограничение на множество выходных параметров модуля (ОиТ'гл IN' =0);

4) Ra(ZB( 1, 2);Z4(1, ma)/c2) - параметры из ZB a Z, задающие границы изменения индексов параметров-массивов из ZA с Z, 1 < та < т\ с2 - ограничение, требующее, чтобы эти параметры были скалярами целого типа;

5) Ri(ZL{\, \):ZU(\, 1)/с3) - параметры-списки из ZL с Z, создаваемые на основе параметров из ZU czZ;c¡- ограничение, накладываемое на тип параметра, на основе которого создается список (он может быть параметром любого типа, кроме списка);

6) R6(ZB( 1, \):ZL{\, ml)/c2) - параметры из ZB с: Z, задающие число элементов параметров-списков из ZL с Z, 1 < mi <т; с2 - ограничение целостности, требующее, чтобы эти параметры были скалярами целого типа;

7) ñ7(F( 1, l):FE(l, г)) - экземпляры модуля, г е N;

Рис.2. Модель вычислений 8) R%(ZL(l, \):PE(l, s)) - элементы

параметров-списков, s е N;

10 Цикритзис Д. Модели данных / Д. Цикритзис, Ф. Лоховски. - М.: Финансы и статистика, 1985. - 344 с. "Следует отметить, что для задания некоторых из этик отношений используются вспомогательные объекты предметной области.

10

9) R9(FE(l, r):PE{ 1, i)/c4) - входные элементы параметров-списков экземпляра модуля, г, s е N; с4 - ограничение, требующее, чтобы индексы этих элементов и обрабатывающего их экземпляра модуля совпадали;

\0)R\d{FE(\, г):РЕ{ 1, s)/cs) - выходные элементы параметров-списков экземпляра модуля, г, s е N; cs - ограничение, требующее, чтобы индексы этих элементов и обрабатывающего их экземпляра модуля совпадали.

В процессе вычислений параметры-списки могут обрабатываться как неделимые структуры данных. В первом случае обработка параметра-списка осуществляется аналогично обработке параметра-массива. Во втором случае под поэлементной обработкой параметров-списков подразумевается следующее: пусть х', у'- параметры-списки, созданные на основе параметров х и у, модуль /,: Ш'—> OUT' предназначен для их поэлементной обработки, хе IN', ye OUT'. Интерпретация модуля /, выполняется следующим образом: 1) происходит параллельный запуск г экземпляров (г - размерность списков х', у') модуля ftj-щ экземпляру модуля $ передается j-й элемент списках'- 2) результат присваивается y-му элементу списка у'.

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

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

Второй способ предусматривает предварительное (до начала вычислений) назначение пользователем приоритетов модулей на основе своих экспертных знаний. Модули размещаются в очереди на выполнение в порядке убывания их приоритетов. Дальнейшая обработка очереди осуществляется аналогично первому способу.

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

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

12 Новопашин А.П. Методы и инструментальные средства крупноблочного синтеза параллельных программ для вычислительных кластеров. Автореф. дис. кавд. техн. наук. Иркутск: ИДСТУ СО РАН, 2005. - 26 с.

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

Условия, возникающие в процессе вычислений, при которых возможен запуск модуля или одного из его экземпляров, определим следующим образом. Пусть тип задают, соответственно, число параметров и модулей в модели вычислений СМ. Введем в рассмотрение следующие множества: С' = {c¡, Сп, ..., cg} - множество входных параметров модуля/„ значение которых вычислены на данный момент времени, С'с IN', ie{l, 2, .... и}; Р' = {р\,рь ••■, Рь} - множество входных параметров-списков модуля f„ обрабатываемых экземплярами этого модуля f¡ поэлементно, Р' aZLnlN'; Е' = {ci, еъ ..., eq} - множество индексов элементов параметров-списков из Р\ значения которых вычислены для каждого параметра-списка из Р', N. Тогда можно сформулировать условия, при которых возможен запуск модуля f¡ или его экземпляра

Условие 1. Модуль f, может быть запущен на выполнение, если

(|Р'| =0)h{\lN'\Cl\ =0). Условие 2. f! (J-й экземпляр /-го модуля) может быть запущен на выполнение, если (\Р'\ *0)Л (IN' \ С'сР') Л (3k:eksE') л (J- ек).

Определим следующие структуры данных: булеву матрицу предшествования Y размерности пхп, y,¡=1 означает, что модуль^ предшествует модулю f¡ (вычисляет значение хотя бы одного из его входных параметров); булеву матрицу зависимостей D размерности пхп, d,j=l означает, что модуль/, транзитив-но зависит от модуля^; матрицу PR размерности 2хп (первая строка содержит номера модулей, вторая - соответствующие им приоритеты). Приведем основные этапы работы алгоритма выполнения асинхронного вычислительного процесса. После наименования этапа в скобках указаны номера способов выполнения плана решения задачи, использующих данный этап алгоритма.

Статическая фаза - инструментальный комплекс ORLANDO TOOLS, стадия компиляции.

I. Инициализация структур данных Y, D, PR (сп. 1,2,3).

II. Составление расписания (сп. 4).

III. Построение матрицы предшествования Y (сп. 3).

IV. Построение матрицы зависимостей D (сп. 3).

V. Заполнение матрицы PR (сп. 1,2,3).

VI. Выполнение упорядочения матрицы PR с помощью алгоритма быстрой сортировки по приоритетам (сп. 2,3).

Динамическая фаза - параллельная программа, стадия выполнения.

VII. Выполнение вычислительного процесса.

а) Выбор готового к запуску модуля с наивысшим приоритетом (сп. 1, 2, 3).

б) Запуск модуля (сп. 1,2,3).

в) Вызов модулей в соответствии с составленным планом (сп. 4).

VIII.Если все модули выполнены, то происходит завершение работы, иначе -ожидание завершения какого-либо модуля с помощью функции блокирующего приема. После завершения работы какого-либо модуля осуществляется прием данных от этого модуля и переход на этап VII (сп. 1, 2,3).

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

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

В последнем разделе второй главы разработан и реализован специализированный непроцедурный язык ORLANDO (Objects Relations in LANguage of Descriptions), предназначенный для спецификации задач вычислительного характера, решение которых может быть представлено в виде композиции функциональных блоков из заранее определенного базиса. Язык ORLANDO обеспечивает описание объектов предметной области: параметров, модулей, операций14 и их взаимосвязей, а также постановок задач. Все конструкции языка носят декларативный характер и задают правила вычисления значений параметров (модель вычислений). При спецификации предметной области на языке ORLANDO не требуется указывать порядок выполнения модулей, участвующих в решении задачи. Все информационно-логические связи выявляются и учитываются на этапах анализа содержимого файла спецификации и формирования модели вычислений. Язык позволяет сформировать запрос на решение задачи на модели вычислений, не уточняя, каким образом следует организовать вычислительный процесс.

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

" Ершов А.П. Научные основы доказательного программирования / АЛ. Ершов II Вестник АН СССР. -1984, №10.-С. 9-19.

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

Инструментальный комплекс ORLANDO TOOLS ориентирован на вычислительные системы, работающие под управлением ОС Linux. Архитектура инструментального комплекса (рис. 3) включает следующие основные компоненты: многооконный текстовый редактор, транслятор, подсистему компиляции, подсистему запуска, базы расчетных данных. Все эти компоненты устанавливаются и запускаются на рабочей станции пользователя.

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

Транслятор осуществляет разбор описания предметной области на языке ORLANDO и его перевод на язык С++. При этом используется разработанный автором синтаксический анализатор языка ORLANDO, созданный с помощью инструментального средства создания синтаксических анализаторов ANTLR.

Рис. 3. Архитектура инструментального комплекса ORLANDO TOOLS

Подсистемы компиляции и запуска программ реализованы в виде единого программного приложения, которое может быть запущено из текстового редактора ORLANDO TOOLS. Подсистема компиляции параллельных программ выполняет следующие основные функции: осуществляет подключение к вычислительному кластеру; копирует исходные файлы программы на языке С++ на вычислительный кластер; производит трансляцию и компиляцию основной программы и программ модулей с использованием штатных транслятора и компилятора языка С++ (в случае возникновения ошибок пользователю выводятся соответствующие сообщения). При компиляции используются необходимые программные библиотеки: библиотека классов объектов предметной области и системные библиотеки, разработанные автором; библиотека вычислительных модулей пользователя; коммуникационная библиотека PVM.

Библиотека классов объектов предметной области предназначена для реализации объектов модели вычислений. Эта библиотека может использовать-14

ся автономно от ORLANDO TOOLS в программах, работающих под управлением ОС семейства UNIX. Системные библиотеки обеспечивают выполнение следующих функций: работа с внутренними структурами данных; асинхронное исполнение плана решения задачи; управление запуском вычислительных модулей; ввод/вывод данных. Использование библиотеки классов объектов предметной области и системных библиотек позволяет также получить более компактный текст генерируемой программы и повысить его читабельность. Библиотеки вычислительных модулей включают функции пользователя, которые создаются с помощью сторонних средств разработки. Коммуникационная библиотека PVM обеспечивает поддержку параллельного программирован™.

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

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

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

В первом разделе данной главы приводится пример, демонстрирующий работу статико-динамического алгоритма выполнения асинхронного вычислительного процесса. Пусть множество модулей модели вычислений задано следующим образом: F= {/,(.::,), /2(z6, zn;), /3(-i,-2), Д^-з), /5(-з."Д /б(-зг-з).

/8("7.'-9). /ю(-З.'^п), /иО-5, 2,з,' Г8), /п(-8, ^9.' ¿ю)> /|з(~8. >9,' Гц),

/м(-ю.' мг)}, где запись /¡(IN'; OUT') определяет множество входных и выходных параметров модуля. Схема информационно-логических зависимостей между модулями базируется на графе, построенном для задачи упорядочения последовательности асинхронных работ15. Время выполнения модулей: tji=0, //2=0, /,з=1, ifi=2, tfi=2, tjs=3, íp=2, /,8=5, í,9=l, {/io=2, tju=2, tñ-¿=\, tju=4, tfl4=2. Модули/ и /2 моделируют постановку задачи «по заданному значению параметра z\ вычислить значения параметров z6, г, ь zu».

Бьш промоделирован процесс решения данной задачи на 2, 4 и 10 процессорах (дня тестирования алгоритма как в случае ограниченности вычислительных ресурсов, так и в противоположном случае). В табл. 1 представлены результаты вычислительных экспериментов, полученные различными способами выполнения плана решения задачи, реализованными в инструментальном комплексе ORLANDO TOOLS. В табл. 1 приведены следующие характеристики: № - это номер вычислительного эксперимента; Пр, - число процессоров; Seq - вариант последовательности модулей в очереди (приоритеты модулей указаны в круглых скобках после их номеров) для третьего способа выполнения задания со временем решения задачи t, равным t¿ !„„„ и tnax - соответственно минимальное и максимальное время

,г Лорьер Ж.-Л. Системы искусственного интеллекта / Ж.-Л. Лорьер. - М.: Мир. - 1991. -568 с.

решения задачи. Значения и /„и были получены в результате выполнения всех возможных вариантов планов решения задачи, что стало возможным вследствие небольшой размерности задачи. В табл. приведены варианты, актуальные с точки зрения демонстрации различных способов выполнения алгоритма. Вычислительные эксперименты для вариантов №№ 5-8 проводились с включением в модель вычислений модулей, предназначенных для поэлементной обработки параметров-списков. Номера таких модулей выделены в табл. 1 жирным шрифтом.

Таблица 1. Результаты вычислительных экспериментов

№ "г вея ^ТОП 1.

1 2 1(13),3(12),4(11),5(7),6(6),10(5).7(5),ШШШ,12(2),9(1),13(1),14(1)Д(0) 16 16 19

2 2 1(13), 3(12), 4(11), 5(7), 6(6), 10(5),7(5), ШЩ4Ц2(2), 9(1), 13(1), 14(1), 2(0) 16 17 19

3 4 1(13), 3(12),4(11), 5(7), 6(6), 10(5), 7(5),8ЩЩ4), 12(2), 9(1), 13(1), 14(1), 2(0) 16 16 16

4 4 1(13),3(12),4(11),5(7),6(6),10(5),7(5),ДМШ4),12(2),9(1),13(1),14(1),2(0) 16 16 16

5 2 1(13),3(12),4(11),5(7),6(6),7{5Щ5},8(4),11(4),12(2),9(1),14(1),13(1),2(0) 15.6 15.6 20

6 2 1(13), 3(12), 4(11), 5(7),6(6), Щ5Щ), 8(4), 11(4), 12(2), 9(1), 14(1), 13(1)Д(0) 15.6 16.6 20

1 4 1(13),3(12),4(11),5(7),6(6),10(5),7(5),8(4),11(4),12(2),9(1),14(1),13(1)Д0) 15 15 15.8

8 10 1(13),3(12),4(11),5(7),6(6),Ю(5),7(5),8(4),11(4),12(2),9(1).14(1),13(1),2(0) 15 15 15.4

Для четвертого способа работы алгоритма время выполнения плана решения задачи г равняется /,„,„. Это обусловлено тем, что в случае наличия информации о времени выполнения модулей для данной задачи можно построить оптимальный план выполнения вычислительного процесса. В случае, когда информация о времени выполнения модулей не известна, применяются оставшиеся три способа выполнения алгоритма. Для первого способа работы алгоритма время / изменяется в пределах от 1тт до 1тах, в зависимости от случайного порядка модулей в очереди. Для данного примера это может давать погрешность, равную 22% относительно /„„■„. При задании приоритетов модулей пользователем (второй способ выполнения алгоритма) время / зависит от его экспертных знаний с точки зрения логики схемы решения задачи. Для третьего способа /=/„. Следует отметить, что порядок модулей в очереди может быть неоднозначным для данного способа выполнения алгоритма из-за того, что приоритеты разных модулей могут совпадать. При этом может изменяться время счета (см. варианты №№ 1,2 и 5,6; модули с одинаковыми приоритетами, перестановка которых в очереди влияет на время решения задачи, выделены подчеркиванием).

Анализ результатов вычислительных экспериментов показывает, что при увеличении количества процессоров стремится к !„„„, соответственно погрешность для первого, второго и третьего способов стремится к нулю (см. варианты №№ 2-3,6-8). Отметим, что порядок модулей в очереди не имеет значения, когда количество процессоров больше степени максимального параллелизма плана решения задачи, так как отсутствуют задержки, связанные с ожиданием модулем свободного процессора, и все четыре способа выполнения алгоритма дают одинаковый результат. Примером тому служат варианты №№ 3 и 4, в которых использовались четыре процессора, в то время как степень макси-

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

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

Пакет ГРАДИЕНТ использовался для поиска глобального минимума ряда многоэкстремальных функций (Катковника, Растригина, Опеиапк), относящихся к классу сложных задач оптимизации. Изображение поверхностей этих функций представлено на рис. 4.

Ш'

Штат

а) б) в)

Рис. 4. Графики функций: Катковника (а). Растригина (б), йпе\\'апк (в)

1) Функция Катковника (рис. 4, а):

Лх,у)=0.5(х2+у2)( 1 +0.5«м( 1. 5х)сох( ггу)+0. 5сс«( -75 *)с<м(3.5у)).

2) Функция Растригина (рис. 4, б): Лх,у)=0Лх2+ 0.1/-4со5(0.&с)-4соу(0.8у) + 8.

3) Функция Опе\уапк (рис. 4, в):

/М=-т-—-~ гт +Ю

0.005 ■ (х2 +/)-

+ 2

Все функции имеют глобальный экстремум в начале координат, равный 0. Информационный двудольный ориентированный граф, представляющий модель вычислений пакета ГРАДИЕНТ, изображен на рис. 5.

Количество координат

Функция в текстовом виде| Длина текста функции Смещение для расчета градиента_

Число границ О0\_

ílKno/wl

ОблаСТЬ Генерация

...... начальных точ

начальных С ; \ -

точек / Начальное

Начальные точки N

НаЧвлЫ1аят< Нач&льнаят)

Координаты глобального минимума

к-0

точек — начальное значение .. ,, шага смещения

Число точек (1 Максимальное число ^ вызовов функции Точность вычислений Количество координат и, значение лок. миниму,

Значение глобального минимума

Рис. 5. Информационный двудольный ориентированный граф

Вычислительные эксперименты были проведены на вычислительном кластере МВС-1000М/16 ИДСТУ СО РАН. Для проведения расчетов на вычислительном кластере создавались параллельные виртуальные машины, включающие от 1 до 8 двухпроцессорных узлов кластера. Результаты расчетов представлены в табл. 2.

Таблица 2. Время поиска глобального минимума многоэкстремальных функций

№ Функция Область (х,У) Число точек Время в секундах/Эффективность распараллеливания в %

Число процессоров

1 2 4 8 16

1 Катковника [-20i20J*[-20:20] 1000 490 245/100 123/99,6 64/95,7 31/95

2 Растригина !-200.200П-2№.200) 10000 426 213/100 112/95 60/89 34/78

3 Griewank [-2020П-20:20] ЮОООО 10796 5398/100 5048/53 4838/28 4316/8

4 Griewank |-20:20П-20:20] 100000 626 313/100 157/99,7 82/95,4 42/93,2

Проведенные вычислительные эксперименты позволяют сделать следующие выводы. Методы, алгоритмы и средства, реализованные в инструментальном комплексе ORLANDO TOOLS, обеспечивают достижение хорошей эффективности при распараллеливании процесса вычислений для научных прикладных задач, позволяющих осуществлять их разбиение на независимые части с большой вычислительной мощностью (см. табл. 2, варианты №№ 1,2,4).

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

В третьем разделе главы представлен пакет R-SIM, используемый при моделировании экономических показателей процесса реорганизации объектов ком-18

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

Приложения содержат описания предметных областей пакетов ГРАДИЕНТ и R-SIM, библиотеки классов объектов предметной области, тексты сгенерированных на основе этих описаний параллельных программ и другие дополнительные материалы.

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

На защиту выносятся следующие основные результаты:

1. Модель вычислений, ориентированная на представление и поэлементную обработку параллельных структур данных в рамках интеллектуальных пакетов прикладных программ.

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

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

4. Системная архитектура и алгоритмы функционирования инструментального комплекса ORLANDO TOOLS и его программная реализация.

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Инструментальный комплекс ORLANDO TOOLS / Г.А. Опарин, А.Г. Феоктистов, А.П. Новопашин, С.А. Горский // Программные продукты и системы. - 2007. - № 4. - С. 63-65.

2. Феоктистов А.Г. Реализация метода мультистарта в пакете Градиент / А.Г. Феоктистов, С.А. Горский // Всстник НГУ. Сер.: Информационные технологии. - 2007. - Т. 5, вып. 2. - С. 78-82.

3. Горский С.А. Динамический алгоритм выполнения асинхронного вычислительного процесса / С.А. Горский // Прикладные алгоритмы в дискретном анализе: Сб. науч. тр. / Под ред. Ю.Д. Королькова. - Иркутск: Изд-во Иркутского гос. ун-та, 2008. - С. 4-22.

4. Горский С.А. ORLANDO TOOLS: Свидетельство об официальной регистрации программы для ЭВМ № 2007611625 / С.А. Горский, А.Г. Феоктистов. - М.: Федеральная служба по интеллектуальной собственности, патентам и товарным знакам, 2007.

5. Высокопроизводительные вычисления в пакетах прикладных программ / Г.А. Опарин, А.Г. Феоктистов, А.П. Новопашин, С.А. Горский // Парал-

лельные вычислительные технологии: Тр. Междунар. науч. конф. (PAVT'2007). - Челябинск: Изд-во ЮУрГУ, 2007. - Т. 2. - С. 193-200.

6. Феоктистов А.Г. Работа с параллельными структурами данных в инструментальном комплексе ORLANDO TOOLS / А.Г. Феоктистов, С.А. Горский / Параллельные вычислительные технологии (ПаВТ'2008): Тр. Междунар. науч. конф. - Челябинск: Изд-во ЮУрГУ, 2008. - С. 482-487.

7. Горский С.А. Создание пакетов программ в инструментальном комплексе ORLANDO TOOLS / С.А. Горский, А.Г. Феоктистов // Сб. тр. II школы-семинара молодых ученых «Управление большими системами». - Воронеж: Научная книга, 2007. - Т. 2. - С. 33-39.

8. Феоктистов А.Г. Технология построения пакетов прикладных программ для вычислительных кластеров / А.Г. Феоктистов, С.А. Горский // Параллельные вычисления и задачи управления: Тр. III Междунар. конф. РАСО'2006. - М.: ИПУ РАН, 2006. - С. 498-504.

9. Горский С.А. Средства автоматизации процесса создания параллельных программ / С.А. Горский // Информационные и математические технологии в научных исследованиях: Тр. XI Байкальской междунар. конф.; в 2-х ч. -Иркутск: ИСЭМ РАН, 2006. - Ч. 2. - С. 20-26.

10. Горский С.А. Исполнение параллельных программ в инструментальном комплексе ORLANDO / С.А. Горский // Математическое моделирование и информационные технологии: Материалы VIII школы-семинара молодых ученых. - Иркутск: ИДСТУ СО РАН, 2006. - С. 50-53.

П.Горский С.А. Инструментальные средства для построения и применения параллельных пакетов прикладных программ / С.А. Горский // Студент и научно-технический прогресс. Информационные технологии. Материалы XLIII Междунар. науч. студ. конф. - Новосибирск: НГУ, 2005. - С. 15-17.

12. Горский С.А. Языковые средства для построения и применения параллельных пакетов прикладных программ / С.А. Горский // Под знаком 2: III Всерос. науч. молодежной конф. - Омск: ОНЦ СО РАН, 2005. - С. 232233.

13. Горский С.А. Инструментальные средства для построения параллельных программ / С.А. Горский // Распределенные и кластерные вычисления: Избранные материалы V школы-семинара / Под ред. В.В. Шайдурова. - Красноярск: ИВМ СО РАН, 2005. - С. 36-39.

14. Горский С.А. Методы и инструментальные средства автоматизации конструирования параллельных программ / С.А. Горский // Материалы Всерос. конкурса инновационных проектов аспирантов и студентов по приоритетному направлению развития науки и техники Информационно-телекоммуникационные системы / Под ред. А.О. Сергеева. - М.: ГНИИ ИТТ Информика, 2005. - С. 30-31.

Редакционно-издательский отдел Института динамики систем и теории управления СО РАН 664033, Иркутск, Лермонтова, 134 Подписано к печати 20.11.2008 г. Формат бумаги 60x84 1/16, объем 1,2 пл. Заказ №8. Тираж 100 экз.

Отпечатано в ИДСТУ СО РАН

Введение.

Глава 1. Параллельное программирование в модульных системах.

1.1. Модульное программирование.

1.1.1. Модуляризация программы.

1.1.2. Методы'и'средства создания модульных систем.

1.2. Интеллектуальные пакеты.

1.2.1. Концептуальная схема предметной области интеллектуального пакета.

1.3. Технология создания параллельных программ.

1.3.1. Архитектура.

1.3.2. Модели параллельного программирования.

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

1.3.4. Язык.

1.3.5. Средства автоматизации параллельного программирования.

1.3.6. Алгоритмы управления вычислительным процессом.

Глава 2. Методы, алгоритмы и языковые средства конструирования параллельных программ в интеллектуальных пакетах.

2.1. Модель вычислений интеллектуального пакета.

2.1.1. Параллельные структуры данных.

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

2.1.3. Обработка параметра-списка как единого параметра.

2.1.4. Поэлементная обработка параметров-списков.

2.2. Конструирование параллельных программ.

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

2.2.2. Базовый модуль.

2.2.3. Головной модуль.

2.2.4. Описание предметной области.

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

2.4. Язык ORLANDO.

2.4.1. Описание языка ORLANDO.

2.4.2. Составные части программы пользователя.

2.4.3. Объекты предметной области.

Глава 3. Архитектура инструментального комплекса ORLANDO TOOLS.

3.1. Обобщенная схема конструирования параллельных программ.

3.2. Архитектура инструментального комплекса.

3.3. Многооконный текстовый редактор.

3.4. Транслятор.

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

3.5.1. Подсистема компиляции.

3.5.2. Конфигурация параллельной виртуальной машины.

3.5.3. Подсистема запуска.

3.6. Базы расчетных данных.

Глава 4. Применение инструментального комплекса ORLANDO TOOLS для создания интеллектуальных пакетов.

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

4.2. Пакет ГРАДИЕНТ.

4.3. Пакет R-SIM.

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

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

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

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

На сегодняшний день для решения подобных задач существует большой набор средств подготовки и написания параллельной программы [5]. Их можно условно разделить на следующие группы:

1. Традиционные последовательные языки программирования, расширенные наборами специальных директив и библиотеками вспомогательных функций, например, Fortran-DVM [79] или C-DVM [74].

2. Системы программирования на основе передачи сообщений между параллельными процессами программы. Эти средства базируются на использовании различных коммуникационных библиотек, таких, например, как PVM [86] и MPI [90].

3. Системы программирования, ориентированные на предметную область решаемых задач. В качестве примеров подобных программных комплексов можно привести Т-систему [71], систему НОРМА [47] и др.

4. Функциональные языки параллельного программирования, например, SISAL[83], Erlang [70], Пифагор [39, 44].

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

Однако массовое использование такого рода вычислений сдерживается рядом нерешённых на сегодняшний день проблем параллельного программирования, возникающим перед рядовым пользователем высокопроизводительной вычислительной установки (см., например, [5, 36, 69]). В числе таких проблем: сложность выявления параллелизма алгоритма решаемой задачи и учета всех специфических особенностей аппаратного обеспечения и коммуникационных сред, возникающая в процессе разработки параллельной программы, выбора нужного языка (или системы) параллельного программирования и дальнейшего написания текста программы; необходимость обеспечения эффективного выполнения параллельной программы и ее переносимости; специфичный по сравнению с ПЭВМ интерфейс для доступа к вычислительной установке и управления процессом решения задачи.

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

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

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

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

Одним из подходов, позволяющих частично реализовать эти средства, является применение пакетов прикладных программ [10, 61] для организации параллельных и распределенных вычислений в рамках технологии модульного программирования [26, 42].

Пакет программ рассматривается в диссертации традиционно - как совокупность прикладного и системного программного обеспечения [10]. Прикладное программное обеспечение (функциональное наполнение пакета программ) представляет собой набор (библиотеку) вычислительных модулей. Под модулем понимается подпрограмма на языках программирования С или Fortran, спецификации по ее назначению, применению, формату входных и выходных формальных параметров, времени выполнения для той или иной программно-аппаратной платформы, инструкции по ее трансляции, компиляции и дальнейшему размещению объектных и загрузочных модулей и т.п. Системное программное обеспечение включает средства для описания модели предметной области, формирования постановок исследовательских задач и организации процесса их решения.

Естественной формой развития пакетов программ можно считать интеллектуальные пакеты [27, 29, 32, 53, 58]. Такие интеллектуальные пакеты, включающие средства синтеза в общем случае параллельных планов решения задач [4, 49, 55, 59, 84], можно рассматривать как интеллектуальные системы [43], которые, кроме знаний о предметной области и алгоритмах решения задач, способны накапливать знания о методах и средствах создания расчетных программ по планам решения этих задач, о свойствах и правилах включения в расчетную программу модулей, задающих содержательную интерпретацию вычислительных моделей, о способах управления вычислительным процессом.

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

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

Объектом исследования являются теория и практика параллельного программирования.

Предметом исследования являются методы и инструментальные средства построения асинхронных параллельных программ.

Методы исследования. Для решения поставленных задач использованы методы объектно-ориентированного и сборочного программирования, теории построения трансляторов, баз данных, создания языков и инструментальных средств параллельного программирования.

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

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

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

Исследование, разработка и применение рассматриваемых в диссертации программных средств выполнялись в рамках проекта СО РАН 3.2.6 «Интегрированные информационно-вычислительные и коммуникационные ресурсы: ин-теллектные методы организации, автоматизации разработки и применения» (2004-2006 гг., блок 1 «Распределенная вычислительная САТУРН-среда»); проекта СО РАН «Разработка научных основ распределённой информационно-аналитической системы на основе ГИС и Веб-технологий для междисциплинарных исследований» междисциплинарной программы 4.5.2 (2007-2009 гг., блок 2 «Интеллектные методы и инструментальные средства разработки и ком-плексирования распределенных информационно-вычислительных ресурсов»); проекта Российского фонда фундаментальных исследований № 06-01-00340 «Разработка и исследование булевых моделей предметной области в задаче планирования при синтезе программ».

Научно-исследовательская работа Горского С.А. «Методы и инструментальные средства автоматизации конструирования параллельных программ» вышла в финал Всероссийского конкурса инновационных проектов аспирантов и студентов (по направлению "Информационно-телекоммуникационные системы"), проводившегося в рамках Федеральной целевой научно-технической программы "Исследования и разработки по приоритетным направлениям развития науки и техники" на 2002-2006 годы (проект 2005-РИ-18.0/007).

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

Апробация. Основные результаты работы были представлены на V - VIII Школах-семинарах молодых ученых «Математическое моделирование, управление и информационные технологии» (Иркутск, 2004 г., 2005 г., 2006 г.), на XLIII Международной научной студенческой конференции «Студент и научно-технический прогресс» (Новосибирск, 2005 г.), на III Всероссийской молодежной конференции «Под знаком Е» (Омск, 2005 г.), на V и VI Межрегиональных школах-семинарах «Распределенные и кластерные вычисления» (Красноярск, 2005 г., 2006 г.), на Всероссийском конкурсе инновационных проектов аспирантов и студентов по приоритетному направлению развития науки и техники «Информационно-телекоммуникационные системы» (Москва, 2005 г.), на XI Байкальской Международной конференции «Информационные и математические технологии в научных исследованиях» (Иркутск, 2006 г.), на III Международной конференции «Параллельные вычисления и задачи управления (РАСО)» (Москва, 2006 г.), на Второй школе-семинаре молодых ученых «Управление большими системами» (Воронеж, 2007 г.), на Международных научных конференциях «Параллельные вычислительные технологии (PAVT)» (Челябинск, 2007 г.; Санкт-Петербург, 2008 г.), а также неоднократно на семинарах ИДСТУ СО РАН.

Публикации и личный вклад автора. Результаты диссертации отражены в 14-ти научных работах [6, 12-20, 28, 62-64] (в том числе 2 статьи в журналах, рекомендованных ВАК для опубликования основных научных результатов диссертации на соискание ученой степени доктора или кандидата наук). В перечисленных публикациях все результаты, связанные с алгоритмизацией, программной реализацией и вычислительным экспериментом на ЭВМ, получены автором лично. Результаты по моделям и методам организации интеллектуальных пакетов для вычислительных кластеров получены совместно с Феоктистовым А.Г. и являются неделимыми. Из совместных работ с Опариным Г.А. и Новопашиным А.П. в диссертацию включены только те результаты, которые принадлежат лично автору.

Структура работы. Диссертация состоит из введения, четырех глав, заключения, библиографии из 91 наименований и 6 приложений. Общий объем работы - 145 страниц, из которых 117 страниц основного текста, включающего 30 рисунков и 7 таблиц.

Выводы.

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

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

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

4.2. Пакет ГРАДИЕНТ

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

Сутью метода мультистарта [24] является сведение поиска глобального минимума функции к поиску локальных минимумов. При этом для поиска ло

94 кальных минимумов используется тот или ином алгоритм локального спуска, производимого из некоторого множества N начальных точек. Из полученных точек локальных минимумов выбирается точка с наименьшим значением, которая принимается за точку глобального минимума.

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

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

Но применение метода кластеризации имеет ряд недостатков [24], влияющих на вероятность нахождение глобального минимума:

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

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

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

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

Рассмотрим пакет ГРАДИЕНТ, предназначенный для поиска глобального минимума некоторой функции f(x) методом мультистарта. Описание предметной области пакета ГРАДИЕНТ включает следующие параметры:

• PointCount - количество начальных точек для метода мультистарта;

• SPxy - количество координат начальной точки;

• StartPoint [SPxy] - вектор, содержащий координаты начальной точки;

• ParStartPoint[PointCount] - параметр-список, созданный на основе параметра StartPoint;

• EPxyv - число элементов вектора EndPoint;

• EndPoint [EPxyv] - вектор, содержащий координаты точки и значение локального минимума;

• ParEndPoint[PointCount] - параметр-список, созданный на основе параметра EndPoint;

• Flen - длина текстовой строки, которая задает функцию;

• Function [Flen] - минимизируемая функция в текстовом виде;

• BCount - количество границ на координату (минимальное и максимальное значение координат);

• Bounds [SPxy, BCount] - матрица, задающая границы изменения координат;

• Val - значение глобального минимума;

• MPoint - координаты точки глобального минимума;

• Grlnc — приращение, с помощью которого вычисляется значение градиента в точке;

• InitialShifit - начальное значение шага смещения;

• MaxCall - максимальное число вызовов функции;

• Accuracy - точность вычисления локального минимума.

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

Схемы операций предметной области определенны следующим образом:

- Gen(BCount, PointCount, SPxy, Bounds —» ParStartPoint) осуществляет генерацию начальных точек для запуска метода градиента;

- Grad(SPxy, StartPoint, EPxyv, Grlnc, InitialShift, MaxCall, Accuracy, Flen, Function -> EndPoint) осуществляет спуск методом градиента;

- Res(PointCount, ParEndPoint, EPxyv, SPxy —» MPoint, Val) находит минимальное значение функции.

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

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

Function (2) Flen Q.

SPxy

BCount CC\ Bounds O

Grlnc Q

ParStartPoint

Gen StartPoiKVCSN ' StaitPoiaV^y) Grad *

PointCount Qf^ InitialShift О

MaxCall О Accuracy (3 EPxyv О

Рис. 4.6. Информационный двудольный ориентированный граф

Описание модели вычислений пакета ГРАДИЕНТ на специализированном входном языке ORLANDO приведено в Приложении 1.

Пакет ГРАДИЕНТ использовался для поиска глобального минимума ряда многоэкстремальных функций (Катковника [31], Растригина [65], Griewank [89]), относящихся к классу сложных задач оптимизации [24, 31]. Расчеты выполнялись на вычислительном кластере МВС-1000М/16 с различными конфигурациями виртуальных машин, включающих от 1 до 8 двухпроцессорных узлов кластера.

1) Функция Катковника определяется следующим соотношением:

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

Рис. 4.7. Функция Катковника в области [-5;5]х[-5;5]

2) Функция Растригина определяется следующим соотношением с коэффициентом А равным 4:

Дх,у)=0Лх2 + 0 Ay2- 4соу(0.8х) - 4cos(0.8y) + 8.

Изображение поверхности этой функции представлено на рис. 4.8. Глобальный минимум данной функции находится в точке [0;0] и равен 0.

Рис. 4.8. Функции Растригина в области [-20;20]х[-20;20] 3) Функция Griewank (рис. 4.9) определяется следующим соотношением:

Глобальный минимум данной функции находится в точке [0;0] и равен 0.

Рис. 4.9. Функция Griewank в области [-20;20]х[-20;20]

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

А*,У)=

-10 10 при распараллеливании процесса вычислений для научных прикладных задач, позволяющих осуществлять их разбиение на независимые части с большой вычислительной мощностью (см. табл. 7, варианты №№ 1, 5, 7).

Заключение

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

На защиту выносятся следующие основные результаты:

1. Модель вычислений, ориентированная на представление и поэлементную обработку параллельных структур данных в рамках интеллектуальных пакетов прикладных программ.

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

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

4. Системная архитектура и алгоритмы функционирования инструментального комплекса ORLANDO TOOLS и его программная реализация.

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

1. Бабаев И.О. Язык Декарт - входной язык системы СПОРА / И.О. Бабаев, Ф.А. Новиков, Т.И. Петрушина // Прикладная информатика. - М.: Финансы и статистика, 1981. - Вып.1. - С. 35-72.

2. Барский А.Б. Параллельные процессы в вычислительных системах. Планирование и организация. / А.Б. Барский. М.: Радио и связь, 1990. - 256 с.

3. Вальковский В. А. Элементы параллельного программирования / В. А. Валь-ковский, В. Е. Котов, А. Г. Марчук, Н.Н. Миренков; Под ред. В.Е. Котова. -М.: Радио и связь, 1983. 240 с.

4. Вальковский В.А. Синтез параллельных программ и систем на вычислительных моделях / В.А. Вальковский, В.Э. Малышкин. Новосибирск: Наука, Сиб. Отд-ние, 1988. - 129 с.

5. Воеводин В.В. Параллельные вычисления / В.В. Воеводин, Вл.В. Воеводин. СПб.: БХВ-Петербург, 2002. - 608 с.

6. Гершуни Д.С. Планирование вычислений в системах жесткого реального времени (обзор и перспективы) / Д.С. Гершуни // Вычислительная техника. Системы управления. — 1991. В. 6. - С. 4-51.

7. Горбунов-Посадов М.М. Расширяемые программы / М.М. Горбунов-Посадов. М.: Полиптих, 1999. - 336 с.

8. Ю.Горбунов-Посадов М.М. Системное обеспечение пакетов прикладных программ / М.М. Горбунов-Посадов, Д.А. Корягин, В.В. Мартынюк. М.: Наука, 1990.-208 с.

9. П.Горский С.A. CPEL язык для конструирования параллельных программ / СА. Горский // Математическое моделирование и информационные технологии: VI школа-семинар молодых ученых. - Иркутск: ИДСТУ СО РАН, 2005.-С. 11.

10. Горский С.А. ORLANDO TOOLS: Свидетельство об официальной регистрации программы для ЭВМ № 2007611625 / С.А. Горский, А.Г. Феоктистов. -М.: Федеральная служба по интеллектуальной собственности, патентам и товарным знакам, 2007.

11. З.Горский С.А. Динамический алгоритм выполнения асинхронного вычислительного процесса / С.А. Горский // Прикладные алгоритмы в дискретном анализе: Сб. науч. тр. / Под ред. Ю.Д. Королькова. Иркутск: Изд-во Иркутского гос. ун-та, 2008. - С. 4-22.

12. Горский С.А. Инструментальные средства для построения параллельных программ / С.А. Горский // Распределенные и кластерные вычисления: Избранные материалы V школы-семинара / Под ред. В.В. Шайдурова. — Красноярск: ИВМ СО РАН, 2005. С. 36-39.

13. Горский С.А. Исполнение параллельных программ в инструментальном комплексе ORLANDO / С.А. Горский // Математическое моделирование и информационные технологии: Материалы VIII школы-семинара молодых ученых. Иркутск: ИДСТУ СО РАН, 2006. - С. 50-53.

14. Горский С.А. Создание пакетов программ в инструментальном комплексе ORLANDO TOOLS / С.А. Горский, А.Г. Феоктистов // Сб. тр. II школы-семинара молодых ученых «Управление большими системами». — Воронеж: Научная книга, 2007. Т. 2. - С. 33-39.

15. Горский С.А. Средства автоматизации процесса создания параллельных программ / С.А. Горский // Информационные и математические технологии в научных исследованиях: Тр. XI Байкальской междунар. конф.; в 2-х ч. — Иркутск: ИСЭМ РАН, 2006. Ч. 2. - С. 20-26.

16. Горский С.А. Языковые средства для построения и применения параллельных пакетов прикладных программ / С.А. Горский // Под знаком £: III Всерос. науч. молодежной конф. Омск: ОНЦ СО РАН, 2005. - С. 232-233.

17. Гэри М. Вычислительные машины и трудно решаемые задачи / М. Гэри, Д. Джонсон М.: Мир, 1982. - 416 с.

18. Дейкстра Э. Дисциплина программирования / Э. Дейкстра. М.: Мир, 1978. -274 с.

19. Ершов А.П. Научные основы доказательного программирования: На-учн.сообщ. / А.П. Ершов // Вестн. АН СССР. 1984. - № 10. - С. 9-19.

20. Жиглявский А.А. Методы поиска глобального экстремума / А.А. Жигляв-ский, А.Г. Жилинскас. -М.: Наука. Гл. ред. физ.-мат. лит., 1991. — 248 с.

21. Жоголев Е. А. Лекции по технологии программирования Электронный ресурс. / Е. А. Жоголев. — Электрон, дан. Режим доступа: http://sp.cmc.msu.ru/info/3/techprog.htm, свободный. - М.: Факультет ВМиК МГУ, 2000.

22. Жоголев Е.А. Технологические основы модульного программирования / Е.А. Жоголев // Программирование. 1980. - № 2. - С. 44-49.

23. Инструментальные средства построения и эксплуатации пакетов знаний / Г.А. Опарин, А.Г. Феоктистов, Д.Г. Феоктистов, А.Е. Журавлев // Управляющие системы и машины. 1997. - №1-3. - С. 138-143.

24. Инструментальный комплекс ORLANDO TOOLS / Г.А. Опарин, А.Г. Феоктистов, А.П. Новопашин, С.А. Горский // Программные продукты и системы. -2007.-№4. -С. 63-65.

25. Интеллектуальный пакет, использующий при планировании вычислений знания о предметной области и функциональных модулях / Ю.А. Бухштаб, А.И. Горлин, С.С. Камынин, Д.А. Корягин, Э.З. Любимский // Техническая кибернетика. 1981, № 5. - С.123-125.

26. Касьянов В.Н. Трансформационные методы и средства конструирования эффективных и надежных программ / В.Н. Касьянов // Кибернетика и системный анализ. 1993. - № 2. - С. 30-40.

27. Катковник В.Я. Линейные оценки и стохастические задачи оптимизации (метод параметрических операторов усреднения) / В.Я. Катковник. М.: Наука, 1976.-475 с.

28. Кахро М.И. Инструментальная система программирования ЕС ЭВМ (ПРИЗ) / М.И. Кахро, А.П. Калья, Э.Х. Тыугу. М.: Финансы и статистика, 1981. -158 с.

29. Кнут Д. Искусство программирования: в 3 т. Т. 1: Основные алгоритмы.-М., СПб., Киев: Вильяме, 2007. 712 с.

30. Корнеев В. Архитектуры с распределенной разделяемой памятью / В. Кор-неев // Открытые системы. 2001. - № 3. - С. 15-23.

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

32. Корнеев В.Д. Параллельное программирование в MPI / В.Д. Корнеев. — Москва-Ижевск: Институт компьютерных исследований, 2003. 304 с.

33. Лацис А.О. Как построить и использовать суперкомпьютер / А.О. Лацис. — М.: Бестселлер, 2003. 274 с.

34. Легалов А. И. Особенности процедурно-параметрической парадигмы программирования / А. И. Легалов // Радиоэлектроника. Информатика. Управление.-2001 г.-№ 1(5).-С. 102-106.

35. Легалов А.И. Функциональный язык для создания архитектурно-независимых параллельных программ / А.И. Легалов // Вычислительные технологии,-2005.-№ 1(10).-С. 71-89.

36. Липаев В.В. Технология сборочного программирования / В.В. Липаев, А.А. Штрик. М.: Радио и связь, 1992. - 272 с.

37. Лорьер Ж.-Л. Системы искусственного интеллекта: Пер. с франц. / Ж.-Л. Лорьер. -М.: Мир. 1991. - 568 с.

38. Майерс Г. Надежность программного обеспечения. / Г. Майерс М.: Мир, 1980.-360 с.

39. Малышкин В.Э. Введение в параллельное программирование мультикомпь-ютеров / В.Э. Малышкин. Новосибирск: ИВМиМГ СО РАН, 2003. - 268 с.

40. На пути к переносимым параллельным программам / А. Легалов, Д. Кузьмин, Ф. Казаков, Д. Привалихин. // Открытые системы. 2003. - № 05. - С. 36-42.

41. Немнюгин С. А. Параллельное программирование для многопроцессорных систем / С. А. Немнюгин, О. Л. Стесик. СПб.: БХВ-Петербург, 2002. -400 с.

42. Норма. Описание языка. Рабочий стандарт / А.Н. Андрианов, А.Б. Бугеря, К.Н. Ефимкин, И.Б. Задыхайло. М.: Препринт ИПМ им. М.В. Келдыша РАН, 1995.-№ 120.-50 с.

43. Опарин Г.А. Технология синтеза модульных параллельных программ для DVM-системы / Г.А. Опарин, А.П. Новопашин // Интеллектуальные системы: Труды VII Межд. симпозиума. Под ред. К.А. Пупкова. М.: РУСАКИ, 2006.-С. 468-471.

44. Опарин Г.А. Булево моделирование планирования действий в распределенных вычислительных системах / Г.А. Опарин, А.П. Новопашин // Теория и системы управления. 2004. - №5. - С. 105-108.

45. Опарин Г.А. Инструментальная распределенная вычислительная САТУРН-среда / Г.А. Опарин, А.Г. Феоктистов // Программные продукты и системы. -2002.-№2.-С. 27-30.

46. Опарин Г.А. Представление и использование пакетных знаний / Г.А. Опарин, А.Г. Феоктистов, С.А. Горский // Математическое моделирование и информационные технологии: V школа-семинар молодых ученых. Иркутск: Ангасолка, 2004. - С. 29.

47. Опарин Г.А. САТУРН метасистема для построения пакетов прикладных программ / Г.А. Опарин // Разработка пакетов прикладных программ. - Новосибирск: Наука, 1982. - С. 130-160.

48. Плакс Т.П. Синтез параллельных программ на вычислительных моделях / Т.П. Плакс // Программирование. 1977. - № 4. - С. 55-63.

49. Программирование на параллельных вычислительных системах / Р. Бэбб, Дж. Мак-Гроу, Т. Аксельрод и др.; под ред. Р. Бэбба. М.: Мир, 1991. -376 с.

50. Сиразетдинов Т.К. Динамическое моделирование экономических объектов / Т.К. Сиразетдинов. Казань: Фэн, 1996. -223 с.

51. СПОРА система программирования с автоматическим синтезом программ / И.О. Бабаев, С.С. Лавров, Г.А. Нецветаева, Ф.А. Новиков, Г.М. Шувалов // Применение методов математической логики. - Таллин: ИК АН ЭССР, 1983. -С. 29-41.

52. Топорков В.В. Модели распределенных вычислений / В.В. Топорков. М.: ФИЗМАТЛИТ, 2004. - 320 с.

53. Турский В. Методология программирования / В. Турский. М.: Мир, 1981. -264 с.

54. Тыугу Э.Х. Концептуальное программирование / Э.Х. Тыугу. М.: Наука, 1984.-256 с.

55. Феоктистов А.Г. Реализация метода мультистарта в пакете Градиент / А.Г. Феоктистов, С.А. Горский // Вестник НГУ. Сер.: Информационные технологии. 2007. - Т. 5, вып. 2. - С. 78-82.

56. Феоктистов А.Г. Технология построения пакетов прикладных программ для вычислительных кластеров / А.Г. Феоктистов, С.А. Горский // Параллельные вычисления и задачи управления: Тр. III Междунар. конф. РАСО'2006. М.: ИПУ РАН, 2006. - С. 498-504.

57. Функция Растригина Электронный ресурс. Электрон, дан. Режим доступа: http://www.cs.rtuJv/dssg/m/staff/rastrigin/rastr-function.html, свободный.

58. Хьюз Дж. Структурный подход к программированию / Дж. Хьюз, Дж. Мич-том. М.: Мир, 1980. - 280 с.

59. Цейтин Г.С. На пути к сборочному программированию / Г.С. Цейтин // Программирование. 1990. - №1. - С. 78-92.

60. Цикритзис Д. Модели данных / Д. Цикритзис, Ф. Лоховски. М.: Финансы и статистика, 1985. - 344 с.

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

62. Armstrong J. Programming Erlang: Software for a Concurrent World / J. Armstrong. The Pragmatic Bookshelf, 2007. - 536 p.

63. Biyabani S. The integration of deadline and criticalness in hard real-time scheduling / S. Biyabani, J. Stankovic, K. Ramamritham // IEEE 9th Real-time systems symp. 1988. - P. 152-160.

64. Brauni T. Parallel Programming. An Introduction / T. Brauni. Prentice Hall, 1993.

65. C-DVM язык разработки мобильных параллельных программ / Н.А. Коновалов, В.А. Крюков, А.А. Погребцов, Ю.Л. Сазанов // Программирование. -1999. -№1.- С. 20-28.

66. Chetto Н. Sheduling dynamically occurring tasks in hard real-time systems / H. Chetto, M. Silly // Proc. IFAC workshop on distributed computer control systems. 1986.-P. 181-186.

67. EDPEPPS: An environment for the design and performance evaluation of portable parallel software / T. Delaitre, G.R. Ribeiro Justo, F. Spies, S. Winter. // Submitted version of Euromicro Workshop PDP'97. London: 1996. - P. 401-406.

68. Flynn M. Some Computer Organisations and Their Effectiveness / M. Flynn // IEEE Trans. Computers. 1972. V. 21. - № 9. - P. 948-960.

69. Flynn M. Very high-speed computing system / M. Flynn // Proc. IEEE. 1966. № 54.-P. 1901-1909.

70. HeNCE: A Users' Guide Электронный ресурс. / A. Beguelin, J. Dongarra, G. A. Geist, R. Manchek, K. Moore, P. Newton, V. Sunderam. — Электрон, дан. -Режим доступа: http://www.netlib.org/hence, свободный. 1994.

71. Holt R.C. Structure of Computer Programs: A Survey / R.C. Holt // Proceedings of the IEEE. 1975. - № 63(6). - P. 879-893.

72. Kacsuk P. GRADE Graphical Environment for Parallel Programming P. Kac-suk, S. // Forrai ERCIM NEWS - №. 36. - 1999. - P. 30-32.

73. Parr T. The Definitive ANTLR Reference: Building Domain-Specific Languages / T. Parr. The Pragmatic Bookshelf, 2007. - 361 p.

74. PVM: Parallel Virtual Machine. A Users' Guide and Tutorial for Networked Parallel Computing / A. Geist., A. Beguelin, J. Dongarra, W. Jiang, R. Manchek, V. Sunderam. Cambridge: The MIT Press, 1994. - 298 p.

75. Rajeev V. Distributed Execution Environments for the CODE 2.0 Parallel Programming System / V. Rajeev.: Thesis, Dept. of Computer Sciences, Univ. of Texas at Austin, 1995. 85 p.

76. Stankovic J.A. The Spring kernel: a new paradigm for real-time operating systems / J.A. Stankovic, K. Ramamritham // Operating systems review. 1989. - V.3. -№ 3. - P. 54-71.

77. Test Functions for Unconstrained Global Optimization Электронный ресурс. Электрон. дан. Режим доступа: http://www-optima.amp.i.kyoto-u.ac.jp/member/student/hedar/Hedarfiles/TestGOfiles/Page 1905.htm, свободный.

78. Writing Message Passing Parallel Programs with MPI / N. MacDonald, E. Minty, T. Harding, S. Brown. Edinburgh: Edinburgh Parallel Computing Center, University of Edinburgh, 2000. - 80 p.

79. Zhao W. Preemptive scheduling under time and resource constraints / W. Zhao, K. Ramamritham, J. Stankovic // IEEE tr on computers. 1987. - V. C-36. - №8. -P. 949-960.