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

Актуальность темы

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

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

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

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

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

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

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

В то же время широкое распространение новых нетрадиционных принципов программирования МВС МП затруднительно без использования высокоуровневых средств и методов разработки.

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

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

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

На данный момент фирмой Star Bridge Systems, Inc. (США) предлагается среда разработки «Viva» [5], предназначенная для создания параллельных решений для семейства «гиперкомпьютеров» в виде граф-схем, в которой используется независимый от аппаратуры графический язык описания параллельных алгоритмов, на основе которого возможно создавать масштабируемые решения.

Компанией Xputer Lab (Kaiserslautern) (Германия) [6] разрабатывается специализированный «пространственно-ориентированный» (Map-Oriented) язык программирования для оригинальных реконфигурируемых вычислительных систем [7,8], который позволит программировать детерминированный процесс выборки операндов из пространства памяти, при этом через вычислительную структуру системы организуется детерминированный поток данных. Данный язык наиболее эффективен на систолических либо сводимых к ним классах задач, в которых присутствуют регулярные зависимости между данными.

В России можно выделить работы, проводимые в Институте программных систем РАН и Исследовательском центре мультипроцессорных систем по созданию системы автоматического динамического распараллеливания программ [9]. Известна система программирования Норма [10], разработанная в Институте прикладной математики им. М. В. Келдыша, которая обеспечивает высокую эффективность реализации вычислительных процессов для многопроцессорных систем с различной архитектурой, но она ориентирована на решение класса задач математической физики.

В Институте проблем информатики РАН под руководством академика РАН B.C. Бурцева разрабатывается вычислительная система с автоматическим распределением ресурсов [11], в которой, благодаря оригинальной архитектуре, основанной на потоках операндов (так называемых «токенов»), осуществляется динамическое распараллеливание задач, обеспечивая при этом высокий коэффициент использования оборудования.

Одним из перспективных направлений в области построения высокопроизводительных вычислительных систем являются МВС со структурно-процедурной организацией вычислений (СПОВ) и программируемой архитектурой (ПА). В Научно-исследовательском институте многопроцессорных вычислительных систем Таганрогского государственного радиотехнического университета (НИИ МВС ТРТУ) под руководством академика РАН А. В. Каляева была разработана основная концепция технологии создания МВС СПОВ и ПА [12,13,14,15].

Основная идея параллельных вычислений, реализуемых в МВС СПОВ и.

ПЛ, заключается в том, чтобы позволить пользователю с помощью предоставляемых программных средств и соответствующей аппаратной поддержки программировать и формировать в исходной универсальной системе на время решения специализированные вычислители, адекватные структуре решаемой задачи, что позволяет достигать максимальной производительности, соизмеримой со специализированными аппаратными системами, разработанными специально для решения данной задачи. При этом для широкого класса задач достигается реальная производительность системы, близкая к пиковой. Существенное отличие создания параллельных программ для МВС СПОВ заключается в том, что для таких систем формируется не столько структура задачи, адекватная структуре системы, а, наоборот, отталкиваясь от структуры задачи, формируются конфигурация вычислительной системы и процедуры организации потоков данных решаемой задачи [16,17,18].

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

При создании МВС СПОВ число объектов системы конечно, что накладывает ряд ограничений на структурную реализацию вычислений, в связи с этим информационный граф задачи разбивается на множество последовательно реализуемых фрагментов задачи — кадров, каждый из которых реализуется на оборудовании МВС СПОВ структурно. Такую организацию вычислений принято называть структурно-процедурной [20,21].

В НИИ МВС ТРТУ разрабатываются не только технологии создания суперкомпьютеров, но и средства программирования, в том числе, для создания масштабируемых параллельных решений прикладных задач. В работах Л. В. Каляева, И. И. Левина, И. М. Пономарева были заложены базовые принципы технологии разработки масштабируемых параллельных программ для МВС МП различных конфигураций [22,23,24]. Однако не были созданы инструментальные средства и методы разработки масштабируемых параллельных программ, соответствующие современным концепциям быстрой разработки (RAD) [25]. Использование таких инструментов позволило бы не только ускорить процесс создания параллельных программ, но и поднять его на новый уровень, не требующий высокой квалификации от разработчиков прикладных программ.

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

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

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

Для достижения этой цели в работе решаются следующие задачи:

1) исследуются средства и методы организации параллельных вычислений для МВС с массовым параллелизмом;

2) исследуются формы представления структурно-процедурных параллельных программ;

3) разрабатываются формы представления масштабируемых параллельных алгоритмов как в текстовом виде, так и в виде граф-схем;

4) разрабатывается новый метод описания структурных компонентов масштабируемых параллельных программ в виде граф-схем для реализации на МВС СПОВ различной конфигурации;

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

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

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

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

К числу наиболее важных результатов диссертации относятся:

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

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

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

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

Практическую ценность работы представляют:

— алгоритм синтеза структурных компонентов параллельных программ, обеспечивающий автоматическое формирование вычислительных структур для заданной конфигурации МВС СПОВ из ресурсонезависимого описания параллельного алгоритма на основе структурно-декларативного метода;

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

— база данных параллельных программ и программных компонентов, представленных в структурно-функциональной и структурно-декларативной формах для МВС СПОВ различной конфигурации, обеспечивающая сокращение времени создания параллельных масштабируемых программ в 2−4 раза.

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

Наиболее важными из них являются:

— «Синтез унифицированных алгоритмов решения военно-прикладных задач на суперкомпьютере», руководитель — академик РАН А. В. Каляев, зарег. в ЦВНИ, ИН-858;

— «Исследование и разработка фундаментальных принципов и методов программирования многопроцессорных вычислительных систем с массовым параллелизмом, программируемой архитектурой и структурно-процедурной организацией вычислений», руководитель — академик РАН А. В. Каляев, № гос. per. 01.2.100 686;

— «Разработка и исследование системы программирования и настройки архитектуры многопроцессорной системы под структуру задачи», руководитель — академик РАН А. В. Каляев, № гос. контракта 37.011.1.1.0013;

— «Создание экспериментального образца ВПА и компонентов системного программного обеспечения», руководитель НИР — член-корреспондент РАН И. А. Каляев;

— «Разработка и исследование математической модели, структуры и принципов построения многопроцессорной вычислительной системы с динамически программируемой архитектурой», руководитель — к.т.н. И. И. Левин, № гос. per. 01.2.316 409;

— «Создание экспериментального образца МНМС и компонентов системного программного обеспечения», руководитель — к.т.н. И. И. Левин;

— «Разработка математической модели МВС с многоуровневой организацией программирования», руководитель — к.т.н. И. И. Левин, № гос. per. 01.20.31 382;

— «Разработка и исследование методов реализации задачи в самонастраиваемой под структуру задачи вычислительной системе», руководитель — к.т.н. И. И. Левин, № гос. per. 01.20.301 381;

— «Разработка методов и аппаратно-программных средств программирования и настройки архитектуры мультимикропроцессорных систем под структуру решаемой задачи», руководитель — академик РАН А. В. Каляев, № гос. per. 01.2.104 214;

— «Исследование и разработка методов преобразования алгоритма задачи в унифицированную параллельную форму и ее адаптации к архитектуре ВВК», руководитель НИР — член-корреспондент РАН И. А. Каляев.

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

— Международная конференция «Интеллектуальные многопроцессорные системы (ИМС'99)», г. Таганрог, 1−5 сентября 1999 г.;

— Международная конференция «Искусственный интеллект — 2000», Кацивели, Украина, 11−16 сентября 2000 г.;

— 3-я международная научно-техническая конференция «Электроника и информатика — XXI век», Зеленоград-Москва, 2000 г.;

— Всероссийская научная конференция «Высокопроизводительные вычисления и их приложения», Черноголовка, 29 октября- 2 ноября 2000 г.;

— Международная конференция «Интеллектуальные и многопроцессорные системы-2001», Дивноморское, 2001 г.;

— Международная научно-техническая конференция «СуперЭВМ и многопроцессорные вычислительные системы», Таганрог, 26−30 июня 2002 г.;

— Международная конференция «Искусственный интеллект-2000», Кацивели, 2002 г.;

— Международная конференция «Интеллектуальные и многопроцессорные системы-2003», пос. Дивноморское, 2003 г.;

— Международная конференция «Интеллектуальные и многопроцессорные системы-2004», Кацивели, 2004 г.;

— Выставка «Информатика и информационные технологии», г. Берлин (Германия) 2002 г.

По теме диссертационной работы опубликовано 18 печатных работ, из них: 4 статьи, 12 тезисов и материалов докладов на российских и международных научно-технических конференциях, 2 свидетельства о регистрации программ для ЭВМ.

Наиболее важными из публикаций являются:

Левин И.И., Шматок А. В. Технология параллельных индуктивных программ // Труды международной конференции «Интеллектуальные многопроцессорные системы (ИМС'99)». — Таганрог: Изд-во ТРТУ, 1999. — С. 142−146.

Шматок А. В. Средства программирования суперкомпьютеров с программируемой архитектурой // Труды Всероссийской научной конференции «Высокопроизводительные вычисления и их приложения». — М.: Изд-во МГУ, 2000.-С. 168−170.

Левин И. Р1., Пономарев И. М., Шматок А. В. Методы преобразования параллельных программ под структуру вычислительной системы // Искусственный интеллект. — Донецк: Наука i освгга, 2001. — № 3. — С. 227−231.

Левин И.И., Шматок А. В. Сборочная система параллельного макропрограммирования «Интегрированная среда для МВС СПРВ» // Искусственный интеллект. — Донецк: Наука i освгга, 2001. — № 3. — С. 228−233.

Левин И. И, Пономарев И. М., Шматок А. В., Шахов Р. В. Многопроцессорные рабочие станции с ПА — эффективный инструмент решения сложных научно-технических задач // Материалы научно-технической конференции с международным участием «Компьютерные технологии в инженерной и управленческой деятельности». — Таганрог: изд-во ТРТУ, 2002. -№ 2.-С. 180−183.

Левин И.И., Шахов Р. В., Сластен JI.M. Математическое обеспечение многопроцессорных вычислительных систем с программируемой архитектурой // Искусственный интеллект. — Донецк: Наука i освгга, 2002. — № 3, — С. 286−294.

Левин И.И., Шматок А. В. Система разработки параллельных программ для многопроцессорных вычислительных систем с программируемой архитектурой // Материалы Международной научно-технической конференции «СуперЭВМ и многопроцессорные вычислительные системы». — Таганрог: Изд-воТРТУ, 2002.-С. 153−156.

Левин И.И., Шматок А. В., Каляев З. В. Средства разработки параллельных программ для многопроцессорных вычислительных систем с программируемой архитектурой // Искусственный интеллект. — Донецк: Наука i освгга, 2003. — № 3. — С. 147−149.

Шматок А.В., Каляев З. В. Декларативный и функциональный методы разработки компонентов масштабируемых параллельных программ // Искусственный интеллект. Интеллектуальные и многопроцессорные системы. Материалы международной научно-технической конференции, 20−25 сентября 2004 г. — Таганрог: Изд-во ТРТУ, 2004. — Т 1. — С. 227−229.

Шматок А.В., Каляев З. В. Декларативный и функциональный методы разработки компонентов масштабируемых параллельных программ // Высокопроизводительные вычислительные системы (ВПВС-2004). Материалы научной международной школы, 20−25 сентября 2004 г. — Таганрог: Изд-во ТРТУ, 2004. — С. 139−142.

Основные положения, выносимые на защиту:

— модернизированный структурно-функциональный метод разработки масштабируемых параллельных программ для МВС СПОВ;

— новый структурно-декларативный метод разработки масштабируемых параллельных программ для МВС СПОВ;

— алгоритм синтеза структурных компонентов параллельных программ, представленных в виде масштабируемых граф-схем;

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

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

4.5. Выводы.

1) Для реализации методов разработки масштабируемых программ для МВС СПОВ предложена структура комплекса математического обеспечения, основными компонентами которого являются: интегрированная среда разработки параллельных программ «Argus IDE» на базе языка структурно-процедурных вычислений «Argus», интегрированная среда разработки компонентов параллельных программ в виде граф-схем «Easyo IDE», интерактивный отладчик параллельных программ «Argus Debugger».

2) Для эффективной разработки параллельных решений прикладных задач на базе языка программирования структурно-процедурных вычислений «Argus» создана интегрированная среда разработки параллельных программ и программных компонентов «Argus IDE», которая за счет интеграции необходимых для процесса разработки средств в одну систему позволяет ускорить процесс создания параллельных программ для МВС СПОВ различной конфигурации.

3) Для эффективной разработки компонентов параллельных решений прикладных задач, представимых в виде граф-схем, создана интегрированная среда разработки программных компонентов в виде граф-схем «Easyo IDE», которая за счет интеграции необходимых для процесса разработки средств в одну систему позволяет ускорить процесс создания компонентов параллельных программ для МВС СПОВ различной конфигурации.

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

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

ЗАКЛЮЧЕНИЕ

.

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

При проведении исследований и разработок по теме настоящей работы получены следующие теоретические и прикладные результаты:

1) модернизирован комплекс математического обеспечения МВС СПОВ за счет расширения среды исполнения и средств разработки и взаимодействия с пользователем, что в несколько раз позволяет повысить продуктивность разработки масштабируемых приложений;

2) предложены принципы разработки и синтеза масштабируемых параллельных программ на основе идеологии компонентного программирования для МВС СПОВ различной конфигурации;

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

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

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

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

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

По теме диссертационной работы опубликовано 18 печатных работ, из них: 4 статьи, 12 тезисов и материалов докладов на российских и международных научно-технических конференциях, 2 свидетельства о регистрации программ для ЭВМ.

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