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

Палагин Владимир Владимирович

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

ПРОГРАММАХ

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

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

г г иди ¿он

Москва 2014

005548718

005548718

Работа выполнена на кафедре «Персональные компьютеры и сети» (ИТ-4), факультета «Информатики» Федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Московский государственный университет приборостроения и информатики» (МГУПИ)

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

Баканов Валерий Михайлович, профессор кафедры «Персональные компьютеры и сети» МГУПИ

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

Гостев Иван Михайлович,

профессор кафедры «Управления разработкой

программного обеспечения» НИУ ВШЭ

кандидат технических наук, доцент

Рязанова Наталья Юрьевна,

доцент кафедры «Программное обеспечение ЭВМ

и информационные технологии»

МГТУ им. Н.Э. Баумана

Ведущая организация: ОАО «Научно-исследовательский институт

вычислительных комплексов им. М.А. Карцева»

Защита диссертации состоится 18.06.2014 г. в 16:00 часов на заседании диссертационного Д 212.131.05 в МГТУ МИРЭА по адресу 119454 г. Москва, пр. Вернадского, д.78, ауд. Д412.

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

Отзывы на автореферат в двух экземплярах, заверенные печатью, просим направлять по адресу: 119454, г. Москва, пр. Вернадского, д. 78, МГТУ МИРЭА, Д212.131.05.

Автореферат разослан 10.05.2014 г.

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

кандидат технических наук, доцент Андрианова Е.Г.

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

Актуальность темы исследований. Актуальность исследований в области разработки эффективных параллельных программ в первую очередь определяется необходимостью решения широкого спектра национально-значимых задач в соответствии с приоритетными направлениями развития науки, технологий и техники в Российской Федерации и перечнем критических технологий Российской Федерации, утверждёнными указом Президента от 7 июля 2011 г. № 899. Широкий спектр задач моделирования использует алгоритмы, в которых вычисления производятся во вложенных циклах над значениями функции на границах элементов (узлах сетки). Проблемно-ориентированные параллельные программы, реализующие подобные алгоритмы, требуют значительных вычислительных ресурсов, формируя тем самым большую часть нагрузки на суперкомпьютерные системы.

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

Эффективность программного обеспечения для многопроцессорных вычислительных систем (МВС) определяется приемлемыми временными рамками обсчёта целевой задачи и объёмом потребляемых при этом ресурсов аппаратной платформы. Ручная модификация существующих, и разработка новых параллельных программ эффективных по одному из вышеприведённых критериев является трудоёмкой и затратной процедурой. Использование оптимизирующих/распараллеливающих компиляторов/систем не всегда оправдано с точки зрения проблемы «стена памяти» (memory wall), заключающейся в отставании скорости подготовки данных при их передачи по коммуникационной сети от скорости обсчёта на вычислительных узлах (ВУ) и

з

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

Здесь необходимо отметить, что по данным в последние годы акцент в рейтинге проекта ТОР500 сместился в сторону вычислительных кластеров - НРС (High-Performance Computing), реализующих архитектуру МРР (Massive Parallel Processing) и занимающих более 84% от общего числа суперкомпьютеров мира с неизменным наращиванием преимущества. В этом контексте ещё более ужесточаются требования к программному обеспечению в части касающейся временной эффективности и ресурсоёмкости.

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

В разное время вопросами параллельных вычислений занимались такие исследователи как Воеводин В.В., Воеводин Вл.В., Тыртышников Е.Е., Жуматий С.А., Стефанов К.С., Антонов А.С., Гергель В.П., Вальковский В.А., Кутепов В.П., Соколинский Л.Б., Букатов А.А., Дацюк В.Н., Жегуло А.И., Корнеев В.Д., Крюков В.А., Андрианов А.Н., Бугеря А.Б., Ефимкин К.Н.

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

4

распределения данных в рамках блоков исходного кода с набором гнёзд циклов (cycle nest).

Объектом исследования являются МВС с распределённой памятью. Под термином МВС с распределённой памятью понимаются такие классы суперкомпьютеров как кластерные НРС и массово-параллельные МРР вычислительные системы.

Предмет исследования определён областью исследования № 3 паспорта специальности 05.13.11 «Модели, методы, алгоритмы и программные инструменты для организации взаимодействия программ и программных систем», а также перечнем задач, решаемых в диссертации.

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

Задачи исследования. Достижение поставленной цели предполагает решения следующих основных задач:

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

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

3. разработка метода лексико-синтаксического анализа исходного кода проблемно-ориентированных параллельных программ для построения абстрактного синтаксического дерева (АСД) и его декомпозиции, с целью поиска гнёзд циклов со связью по данным и объединения их в блоки;

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

5. разработка метода перераспределения времени выполнения между гнёздами циклов со связью по данным в рамках блоков исходного кода;

6. реализация и тестирование препроцессора для выполнения модификации исходного кода проблемно-ориентированных параллельных программ. Методы исследования включают в себя методы теории компиляции

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

Научную новизну результатов работы определяют:

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

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

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

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

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

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

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

Достоверность и обоснованность полученных результатов, приведенных в диссертационной работе, обеспечивается:

• использованием надежных методов исследования и результатами, полученными в ходе экспериментов по уменьшению времени выполнения параллельных программ на различных аппаратных платформах МВС;

• апробацией и обсуждением результатов работы на международных и Всероссийских научных конференциях, научными статьями, опубликованными в ведущих научных журналах из перечня ВАК РФ;

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

Внедрение результатов работы. Разработано программное обеспечение «Препроцессор РуЫогша», на которое получено свидетельство о государственной регистрации программ для ЭВМ Роспатента №2013612115 от 12.01.2013 г. Данный программный продукт использовался в научно-исследовательских работах в ЗАО «Энергокомплект» (акт о внедрении) и в ОАО «Праймтек» (акт о внедрении). Результаты исследования используются в учебном процессе при подготовке специалистов на кафедре «Персональные компьютеры и сети» МГУПИ в рамках дисциплины «Параллельные вычисления».

Апробация работы. Основные положения и результаты диссертационной работы докладывались на международных и Всероссийских конференциях, и семинарах: международной научно-практической конференции «Современные направления теоретических и прикладных исследований», Одесса, 2008, 2010, 2011, 2012 г.; 2, 3, 4, 5 международной научно-практической интернет-конференции «Актуальные проблемы аппаратно-программного и информационного обеспечения науки, образования, культуры и бизнеса», Москва, 2009, 2010, 2011, 2012 г.; ежегодной Всероссийской научной конференции

7

«Современные тенденции развития теории и практики управления в системах специального назначения», Москва, 2011, 2012, 2013 г.; 13 Всероссийской научно-технической конференции «Новые информационные технологии», Москва, 2010 г.; научном семинаре «Проблемы современных информационно вычислительных систем» под руководством д.ф.-м.н., проф, В.А. Васенина, МГУ имени М. В. Ломоносова, Москва, 2012 г.; международной заочной научно-практической конференции «Современные тенденции экономики, управления, права, социологии, образования, медицины, физики, математики: Новый взгляд», Санкт-Петербург, 2013 г.;

Публикации. По материалам диссертации опубликованы 21 печатная работа, из них 4 статьи в ведущих научных журналах и изданиях, рекомендованных ВАК РФ, 4 статьи в сборниках научных трудов, зарегистрированных в системе Российского индекса научного цитирования (РИНЦ), 6 публикаций в научных трудах международных и Всероссийских конференций, 7 публикаций в журналах и межвузовских сборниках научных трудов.

Структура и объём работы. Диссертация состоит из введения, 4 глав, заключения, библиографического списка и приложений. В конце работы помещены акты о внедрение результатов работы, и справка о регистрации программ. Общий объем работы - 149 страниц машинописного текста, из них 118 страниц - основное содержание, 19 страниц - библиографический список (168 наименований).

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

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

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

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

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

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

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

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

Вторая глава посвящена разработке математического обеспечения распределения данных в проблемно-ориентированных параллельных программах. Формализована задача исследования, определены основные понятия и термины. Разработана математическая модель распределения времени выполнения для проблемно-ориентированных параллельных программ. Проработан вопрос

9

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

Проработан класс вычислительных задач, реализуемый параллельными программами для научно-технических расчётов, с целью выделения специфики/особенностей построения исходного кода и времени выполнения. Формализовано понятие блока исходного кода, объединяющего в себе одно или несколько гнёзд циклов - структуру вложенных до некоторого уровня циклов. Обоснованием для рассмотрения нескольких гнёзд циклов в рамках блока является зависимость по данным, возникающая в случае доступа по чтению или по записи к одному и тому же массиву переменных. В рамках блока средствами программных механизмов, которые поддерживаются большинством современных систем параллельного программирования фУМ/трС/НОРМА), распределение данных задаётся единожды и неизменно во время выполнения программы (рис. 1).

Распределение данных по ВУ в 1. DISTRIBUTE massive_name format (формат распределения для каждого массива)

рамках целевого блока 2. DISTRIBUTE INDEX i=l..N (формат распределения по индексному направлению)

Начало блока № 1

(beginning of code block) MASS_X[N,N] Массив № 1 обрабатываемых данных

DO i=ii, i2> ¡з (BODY i,i) Начало гнезда циклов № 1 глубиной 3

DO j=ji, }2, j3 (BODY i,j) (beginning of cycle nest)

DO k=ki, k2/ k3

BODY i,k // операции с MASS_ *[N][N]

END k

END j

END i Конец гнезда циклов №1

DO ¡=¡1, i2, ¡3 (BODY 2.i) Начало гнезда циклов № 2 глубиной 2

DO j=ji, j2, js (beginning of cycle nest)

BODY 2,j //операции с MASS_*[N][N]

END j

END i Конец гнезда циклов № 2

Конец блока № 1

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

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

сообщений. Например, в DVM используется директива DISTRIBUTE (вариант 1 на рис. 1), в НОРМА применяется DISTRIBUTION INDEX (вариант 2 на рис. 1), при использовании MPI процесс распределения полностью перекладывается на программиста. Заданное распределение действует для некоторой программной области (блока исходного кода) и в её пределах не изменяется.

Распределение данных обозначим как список DK = {d1,d2,..,dk,..,dK}, где dk — элемент списка DK, описывающий заданное распределение. К - общее число вариантов распределения. Блок обозначим, как совокупность гнёзд циклов, и представим в виде списка FM = {fi, ■ ■, fm>■ ■<//!*}> где fm — элемент списка FM, описывающий цикл m, M - общее число сгруппированных в блоке циклов. Описание гнезда циклов включает ряд параметров, характеризующих тело цикла BODYml, где m - номер гнезда в блоке, L — глубина вложения.

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

Рисунок 2 - Схема поиска рационального распределения данных в рамках блоков

исходного кода на основе системы эвристических правил

Принципиально возможны три подхода к варьированию входных параметров D и F (символами var и const обозначены действия изменения и постоянства входных параметров соответственно):

1. D = var, F = const - поиск рационального варианта распределения исходных данных при котором времени выполнения блока минимально -подход представленный в данной работе;

2. D = const, F = var - эквивалентные преобразование циклов при неизменном

значение распределения в рамках блока - подход характерный для

оптимизирующих/распараллеливающих систем (FORGExplorer/V-Ray/OPC);

11

3. й = г?аг, = раг - одновременная модификация обоих параметров, что является наиболее сложным вариантом оптимизационной задачи. Тогда общий вид функции при решение задачи уменьшения общего времени выполнения параллельной программы с учётом варьируемых параметров и характеристик аппаратной платформы МВС будет иметь вид: г = /(0,Г^поае,Хпоае,Упе(), где (?пойе - число задействованных в процессе обработки данных ВУ, ХпоЛе — характеристики аппаратного обеспечения вычислительных улов, Упег - характеристики коммуникационной сети.

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

!:Тйпрвая операция в исходном tco^e р »define N 9000 Р Mass„A ¡NJiN]; 1,7 MPL" ■■ mpi ¡nit operation I fori i =0; i < N; !( I

I for(j = 0;j < N;j++) j щ И Max search operation I

I 1 I

|| }/■'' MPL* - rnp: send operation J

Шаблон выполнения типовой операции в системе эвристических правил

max_search - { # operation type

'info': {'operatfonjypi.1': 'maximum_search', 'opsration_def: False}, §

'input'. < 'matnxjd'. 1, "a atrix_narrse': 'Mass_A',' 'malriK_s<ze': 9000, |

'eiementjype': double'},

'output1:«'varjd': 1, 'var .name': 'max'.'eiementjype'. 'double'}, 1

'cycle_nest': {'cyc!e_id': ; depth': 2. 'order': i-j', 'options': False}, §

'distribution': {'dl_sty!e': alongJndex', 'dijndex': "j"},

'library': {library Дуре':' V1PI', iibrafy_versiO!V: 1.4 }} j

Рисунок 3 - Типовая операция поиска максимального элемента для матрицы в исходном коде и в шаблоне выполнения системы эвристических правил

Шаблон выполнения типовой операции хранит значение рационального распределения данных для каждой типовой операции, сформированное на основе данных, полученных в ходе практических экспериментов с использованием вычислительных ресурсов кластерной системы МГУПИ и суперкомпьютерного комплекса НИВЦ МГУ им. М.В. Ломоносова. Для каждой тестовой параллельной программы, реализующей одну типовую операцию в рамках блока, опытным путём было получено время выполнения в относительных единицах (для

12

устранения привязки к конкретной конфигурации аппаратной платформы), зависящее от выбранного параметра распределения данных (рис. 4).

Рисунок 4 - Формирование системы эвристических правил на основе результатов практических экспериментов

В процессе исследования была разработана математическая модель отражающая время выполнения параллельной программы Тргод с учётом распределения времени выполнения по блокам ТЫоск: Тргод = ^ь=-\(Уыоск,ь) + Тыоск' гДе Ь е {1< ■ ■. 6} — число блоков с набором гнёзд циклов в программе, Т^ск - время выполнения программного кода за пределами блоков. Соответственно, время выполнения блока ТЫоск формируется из времени выполнения гнезда циклов с зависимостью по данным Тпеп и программного кода за пределами циклов Тпезс■ ТЫоск = 1т=1(тпе^,т) + Т'пе/о где ш£{1,.,,М} — число гнёзд циклов с зависимостью по данным в блоке. Исходя из специфики целевого класса программ, для которых основная трудоёмкость сосредоточена в циклах, величины и

Тпеы примем как незначимые с точки зрения времени выполнения.

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

Для информации о трудоёмкости выполнения гнезда циклов дополним каждый элемент ^ компонентами, через которые получено время однократного выполнения тела цикла т глубиной /е{1../м): = СА^са;с ■ Гса/с) +

Штет' ТтетХ где Nса1с - число арифметических операций, Тса1с - время выполнения арифметической операции, Ытет - число операций индексирования (доступа к данным), Ттет - время выполнения операции индексирования. Величины Ыса1с и Ытет определяются реализацией целевого алгоритма, в то время

как Т,

тет

определяется расположением данных в локальной памяти

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

Полное время выполнения тела цикла тп глубиной I: — (¿2 — ¿х)/13, где ¿х, ¿2, ¿з - начальное, конечное значение и приращение индексной переменной. В случае неполного выполнения гнезда циклов при использовании операторов условного перехода формализация значительно усложняется. Время выполнения гнезда циклов Тпе5(т без учёта досрочного выхода из цикла будет

выполнения тела цикла на глубине 71(5) целевого гнезда циклов.

Для того, что бы обеспечить независимость от аппаратной реализации МВС величины Тса1с и Ттетп задаются в относительных единицах времени выполнения. Тогда, определив Ттет для каждой операции доступа к данным по индексу при заданном распределении й, получим функцию цели для поставленной задачи Тыоск = /в№> с12,..,(1к) тт. Таким образом, уменьшение времени выполнения целевого блока параллельной программы достигается поиском минимума в конечном списке £>, хранящем все варианты распределения. Программной реализацией данного алгоритма является препроцессор для метаязыка, позволяющий производить модификацию исходного кода проблемно-ориентированной параллельной программы.

В рамках диссертационного исследования подробно рассмотрены реализации механизмов распределения данных в современных системах параллельного программирования (БУМ/шрС/НОРМА). По причине невысокой трудоёмкости лексико-синтаксического анализа по сравнению с классическими языками программирования в качестве инструмента модификации исходного кода целевого класса программ выбран язык НОРМА, разработанный в ИПМ РАН им. М.В. Келдыша. Рассмотрены основные этапы проектирования и разработки, типовая структура исходного кода, функциональные операторы и синтаксические конструкции.

определяться: Тпе5(т = Пп™1

И1"-чу.

где Тп - время

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

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

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

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

Рисунок 6 - Влияние варианта распределения исходных данных по ВУ на время выполнения ГЦ в блоке

Рациональный вариант распределения по критерию времени выполнения для

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

15

рамках целевого блока, что приведёт к эффекту противоположному искомому. Задача может быть упрощена за счёт использования принципа выбора наиболее значимых по трудоёмкости гнёзд циклов. В этом случае определяем вес Рт каждого гнезда т в блоке b согласно: Рт = Tnestm/Tblockb. Таким образом, становится возможным произвести выбор рационального распределения D только для цикла с максимальным весом Tnest v = FP{du d2,.., dk) -> min, где номер гнезда цикла т = р. Адекватность применения веса ГЦ и его времени выполнения определяются правильностью оценки каждого Ттет для заданного распределения D, где ключевым моментом является система эвристических правил на основе шаблонов выполнения типовых операций.

Третья глава посвящена разработке препроцессора «PyNorma» для модификации исходного кода проблемно-ориентированных параллельных программ на метаязыке. Приводится описание основного управляющего скрипта программы и специализированных библиотек: ввода/вывода и хранения конфигурации, лексико-синтаксического анализа, работы с абстрактным синтаксическим деревом, балансировки времени выполнения гнёзд циклов, генерации тестов.

Входной последовательность для препроцессора является набор файлов с исходным кодом на метаязыке, который в процессе работы модифицируется и передаётся транслятору НОРМА для генерации результирующей параллельной программы на Си/Фортран с инкапсуляцией вызовов одной из поддерживаемых библиотек передачи сообщений (MPI/GNS/PVM). Затем следует этап компиляции/линковки стандартными средствами разработки и запуск на целевой аппаратной платформе МВС. В зависимости от флагов, с которыми был запущен препроцессор, результатом обработки входного потока будет один модифицированный файл с рациональным распределением данных по вычислительным узлам или набор файлов со всеми возможными вариантами распределения данных в блоке для последующего тестирования или дополнения системы эвристических правил.

Четвёртая глава посвящена тестированию препроцессора «РуЫогша» на различных аппаратных платформах МВС. Приведено описание технических характеристик и программного обеспечения выбранных задействованных МВС. Обсуждаются результаты тестирования препроцессора и формирование системы эвристических правил на вычислительном кластере МГУПИ и суперкомпьютере «Ломоносов».

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

По причине того, что реальные параллельные программы для научно-технических расчётов, обрабатывающие данных большого объёма имеют весьма сложную логику и структуру исходного кода, для оценки эффективности препроцессора в реальных условиях были проведены эксперименты с более сложными параллельными программами на аппаратной платформе НИВЦ МГУ им. Ломоносова.

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

На графике группой А обозначен пример двух вариантов распределения, иллюстрирующий максимальное ускорение при значениях параметра распределения в блоках ^¿/¿-/(-/¡///а-у-у, группой В - пример двух вариантов распределения, демонстрирующий относительно незначительное ускорение при значениях распределения ¿к/-(/-у/ук-у-у, группой С - пример двух худших

17

вариантов распределения без ускорения и принятый за точку отсчёта при значениях распределения к)1-][-]Ик[)-]1-)1 (рис. 7).

Язык программирования: НОРМА (FORTRAN + MPI)

Типы операций: транспонирование, умножение, поиск максимального

Размерность 1-мерных массивов (векторов): 6 * 104 Размерность 2-мерных массивов (матриц): 2 » 105 Тип данных: DOUBLE PRECISION

Число вариантов распределения: б Средняя глубина ГЦ: 2 Число ГЦ в блоке: 2 Число блоков: 3

«Л '

«г* § Ô-

! 8

ж®

ЧИСЛО ЗАДЕЙСТВОВАННЫХ ВЫЧИСЛИТЕЛЬНЫХ УЗЛОВ

Рисунок 7 - Зависимость коэффициента ускорения выполнения программы от распределения данных на аппаратной платформе суперкомпьютера НИВЦ МГУ им. Ломоносова

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

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

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

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

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

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

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

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

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

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

В журналах, входящих в перечень изданий, рекомендуемых ВАК.

1. Палагин В.В. Синтаксический анализ исходного кода на языке программирования НОРМА с целью оптимизации распределения данных в параллельных программах для научно-инженерных расчётов. // Современные тенденции развития теории и практики управления в системах специального назначения: Научно-технический сборник ОАО Концерн «Системпром». -М., 2012.-№1(2)-С. 559-566.

2. Палагин В.В. К вопросу об ускорении параллельных программ научно-технических расчётов путём использования архитектурных особенностей многопроцессорных вычислительных систем. // Программная инженерия. -

2013. -№2. -С. 21-25.

3. Палагин В.В. Препроцессирование исходного кода параллельных программ для научно-технических расчётов с целью оптимизации по времени выполнения. // Современные тенденции развития теории и практики управления в системах специального назначения: Научно-технический сборник ОАО Концерн «СистемПром». - М., 2013. - №2(4) - С. 421-429.

4. Палагин В.В., Баканов В.М. Повышение эффективности параллельных программ по времени их выполнения за счёт рационального размещения данных в распределённой памяти вычислителя. // Программная инженерия. -

2014,-№5.-С. 6-13.

В сборниках научных трудов, зарегистрированных в базе РИНЦ.

5. Палагин В.В. Обзор перспективных отечественных технологических направлений разработки параллельных программ для научно-инженерных расчётов. // Современные направления теоретических и прикладных исследований 2011: Сборник научных трудов по материалам международной научно-практической конференции. - Одесса, 2011. - Том 5. Технические науки. - С. 11-14.

6. Палагин В.В. Снижение времени выполнения параллельных программ за счёт рационального использования особенностей архитектуры

многопроцессорных вычислительных систем. // Современные направления теоретических и прикладных исследований 2012: Сборник научных трудов по материалам международной научно-практической конференции. - Одесса, 2012.-Выпуск 1.ТомЗ.-С. 76-79.

7. Палагин В.В. Использование препроцессора РуК'огта с целью оптимизации параллельных программ для научно-технических расчётов по времени выполнения. // Современные тенденции экономики, управления, права, социологии, образования, медицины, физики, математики: сборник научных статей по итогам международной заочной научно-практической конференции. - СПб., 2013. - С. 230-233.

8. Палагин В.В. Разработка системы правил препроцессора с целью оптимизации параллельных программ научно-технического характера по времени выполнения для вычислителей архитектуры МРР. // Вестник МГТУ МИРЭА. - 2014. №1(2) - С. 234-244.

В других изданиях.

9. Палагин В.В. Оптимизация процесса индексирования с целью наилучшего использования кэширования в системе НОРМА. // Актуальные проблемы аппаратно-программного и информационного обеспечения науки, образования, культуры и бизнеса: Сборник научных трудов по материалам 2 международной научно-практической конференции. - М., 2009. - С.35-38.

10. Палагин В.В. Современные проблемы оптимизации процесса распараллеливания вычислений при трансляции программ на языке НОРМА. // Новые информационные технологии: Сборник трудов XIII Всероссийской научно-технической конференции. -М., 2010. - С. 54-59.

11. Палагин В.В. Актуальные проблемы разработки и оптимизации параллельных программ на языке НОРМА. // Современные направления теоретических и прикладных исследований 2010: Сборник научных трудов по материалам международной научно-практической конференции. - Одесса, 2010. - Том 2. Технические науки. - С. 18-22.

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

многопроцессорных вычислительных систем. // Программное и информационное обеспечение систем различного назначения на базе персональных ЭВМ: Межвузовский сборник научных трудов - М., 2011. -Выпуск 14.-С. 39-44.

13. Палагин В.В. Проблематика балансировки вычислительной трудоёмкости многоуровневых гнёзд циклов с учётом затрат на передачи данных между вычислительными узлами кластерной системы. // Актуальные проблемы аппаратно-программного и информационного обеспечения, культуры и бизнеса: Сборник научных трудов по материалам 4 международной научно-практической конференции интернет-конференции. - М., 2011. - С. 56-62.

14. Палагин В.В. Специфика отображения параллельной программы на языке программирования НОРМА на архитектуру многопроцессорных вычислительных систем. // Современные тенденции развития теории и практики управления в системах специального назначения: Научная конференция в честь 20-летия ФГУП концерн «Системпром» (Москва, 15 мая 2011 г.) - М„ 2011. - С. 222-224.

15. Палагин В.В. Оптимизация по времени выполнения проблемно-ориентированных параллельных программ для научно-инженерных расчётов. // Программное и информационное обеспечение систем различного назначения на базе персональных ЭВМ: Межвузовский сборник научных трудов - М„ 2012. - Выпуск 15. - С. 84-89.

Патенты, свидетельства на программы для ЭВМ.

16. Свидетельство о государственной регистрации программы для ЭВМ Роспатента №2013612115 от 12.01.2013.

Подписано в печать: 28.04.2014 Объем: 1,3 усл.п.л. Тираж: 100 экз. Заказ №969 Отпечатано в типографии «Реглет» 107031, г. Москва, ул. Рождественка, д. 5/7, стр. 1 (495) 623 93 06; www.reglet.ru

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПРИБОРОСТРОЕНИЯ И ИНФОРМАТИКИ

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

04201458069

Палагин Владимир Владимирович

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

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

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

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

Москва 2014

ОГЛАВЛЕНИЕ

ОГЛАВЛЕНИЕ............................................................................................................2

ГЛОССАРИЙ...............................................................................................................4

ВВЕДЕНИЕ..................................................................................................................7

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

1.1 Архитектурные особенности построения многопроцессорных

вычислительных систем..................................................................................12

1.2 Технологические подходы к разработке параллельных программ.......19

1.3 Анализ возможностей автоматического распараллеливания................25

1.4 Формирование набора требований к параллельным программам........28

1.5 Выбор стратегии модификации параллельных программ.....................30

1.6 Постановка задачи......................................................................................37

Глава 2 Разработка математического обеспечения распределения данных в проблемно-ориентированных параллельных программах...................................41

2.1 Формализация задачи.................................................................................41

2.2 Математическая модель распределения времени выполнения

параллельных программ..................................................................................52

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

исходного кода..................................................................................................64

2.4 Лексико-синтаксический анализ исходного кода...................................75

2.5 Балансировка времени выполнения между гнёздами циклов...............81

2.6 Выводы по Главе 2.....................................................................................88

Глава 3 Разработка препроцессора «РуТЧогта» для модификации исходного кода параллельных программ..................................................................................92

3.1 Основной управляющий скрипт программы...........................................95

3.2 Библиотека ввода/вывода и хранения конфигурации............................97

3.3 Библиотека лексико-синтаксического анализа.......................................99

3.4 Библиотека работы с абстрактным синтаксическим деревом.............101

2

3.5 Библиотека балансировки времени выполнения гнёзд циклов...........103

3.6 Библиотека генерации тестов..................................................................106

3.7 Выводы по Главе 3...................................................................................107

Глава 4 Тестирование препроцессора «PyNorma» на различных аппаратных платформах..............................................................................................................109

4.1 Описание аппаратных платформ, на которых производилось тестирование...................................................................................................109

4.2 Результаты тестирования на вычислительном кластере МГУПИ......111

4.3 Результаты тестирования на суперкомпьютере «Ломоносов»............117

4.4 Выводы по Главе 4...................................................................................121

ЗАКЛЮЧЕНИЕ.......................................................................................................122

БИБЛИОГРАФИЧЕСКИЙ СПИСОК...................................................................127

ПРИЛОЖЕНИЯ.......................................................................................................146

Приложение 1. Свидетельство о государственной регистрации

препроцессора PyNorma................................................................................147

Приложение 2. Акт внедрения препроцессора PyNorma в компании ЗАО

Энергокомплект..............................................................................................148

Приложение 3. Акт внедрения препроцессора PyNorma в компании ООО Праймтек.........................................................................................................149

ГЛОССАРИЙ

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

МВС с распределённой памятью - класс массово-параллельных вычислительных систем, реализующий архитектуру Massive Parallel Processing (МРР), при которой память физически разделена между группой вычислительных узлов (ВУ), объединённых между собой коммуникационной средой [14]. Каждый ВУ имеет доступ к своей локальной памяти или к памяти других вычислительных узлов через интерфейс передачи сообщений - Message Passing Interface.

Интерфейс передачи сообщений (Message Passing Interface, MPI) -программный интерфейс (Application Programming Interface) для передачи сообщений, позволяющий организовать процесс обмена данными между процессами на разных вычислительных узлах в рамках одной вычислительно задачи [43]. Разработаны коммерческие и свободные реализации для большинства аппаратных конфигураций и программных платформ.

Интерфейс программирования приложений (Application Programming Interface, API) - набор готовых классов, процедур, функций, структур и констант, предоставляемых приложением (библиотекой, сервисом) для использования во внешних программных продуктах [139]. Используется программистами для написания всевозможных приложений.

Вычислительный кластер (High-Performance Computing Cluster, HPC) -подкласс МВС с распределённой памятью, физически представляющий собой набор вычислительных, управляющих и вспомогательных улов, объединённых высокоскоростными каналами связи. В настоящее время, по данным рейтинга наиболее производительных суперкомпьютеров мира Тор500 [21] вычислительные кластеры являются наиболее распространённой аппаратной платформой (более 80% от общего числа) для параллельных вычислений промышленного уровня. В России лидирующую позицию занимает суперкомпьютер «Ломоносов», построенный компанией «Т-Платформы» для МГУ им. М.В. Ломоносова. (37 место на ноябрь 2013 года).

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

Гнездо циклов (ГЦ) (cycle nest) - структура вложенных до некоторого уровня циклов [5], где последовательность инструкций для многократного выполнения является телом цикла; единичное выполнение тела цикла -интеграцией; глубина вложенности ограничена синтаксическими правилами реализацией языка программирования.

Блок исходного кода (unit source) - участок исходного кода программы, группирующий один или несколько гнёзд циклов, в котором распределение данных по ВУ задано и неизменно в процессе выполнения программы [165]. В

состав блока может входить один или более гнездо циклов, а также набор исходных данных

Балансировка времени выполнения циклов - перераспределение времени выполнения между гнёздами циклов с зависимостью по данным в рамках блока исходного кода с целью минимизации времени выполнения блока [131].

Абстрактное синтаксическое дерево (АСД) - внутренние представление целевой параллельной программы препроцессором в виде структуры данных конечного (количество элементов ограничено), ориентированного дерева, в котором внутренние вершины сопоставлены с блоками исходного кода, а листья - с гнёздами циклов [122].

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

ВВЕДЕНИЕ

Важность и актуальность темы исследований. Актуальность исследований в области разработки эффективных параллельных программ в первую очередь определяется необходимостью решения широкого спектра национально-значимых задач в соответствии с приоритетными направлениями развития науки, технологий и техники в Российской Федерации и перечнем критических технологий Российской Федерации, утверждёнными указом Президента РФ от 7 июля 2011 г. N 899.

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

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

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

Оптимизирующие/распараллеливающие компиляторы и системы не всегда эффективны с точки зрения проблемы «стена памяти» (memory wall) [16], заключающейся в отставании скорости подготовки данных при их передачи по коммуникационной сети от скорости вычислений на вычислительных узлах (ВУ) и являющейся одним из основных препятствий при достижении экзафлопсного барьера в суперкомпьютерных вычислениях.

Здесь необходимо отметить, что по данным в последние годы акцент в рейтинге проекта ТОР500 [21] сместился в сторону вычислительных кластеров (НРС), реализующих архитектуру МРР и занимающих более 80% от общего числа суперкомпьютеров мира с неизменным наращиванием преимущества. В этом контексте ещё более ужесточаются требования к программному обеспечению в части касающейся временной эффективности и ресурсоёмкости.

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

В разное время вопросами параллельных вычислений занимались такие исследователи как Воеводин В.В., Воеводин Вл.В., Тыртышников Е.Е., Жуматий С.А., Стефанов К.С., Антонов A.C., Гергель В.П., Соколинский Л.Б., Букатов A.A., Дацюк В.Н., Жегуло А.И., Корнеев В.Д., Крюков В.А., Андрианов А.Н., Бугеря А.Б., Ефимкин К.Н.

Наиболее близкими к тематике исследования и посвящённые вопросам

размещения данных в распределённой памяти являются работы Штейнберга Б.Я.

и Полуяна C.B. Однако, проблематика размещения данных для проблемно-

ориентированных параллельных программ, нацеленных на промышленное

использование, со сложной структурой исходного кода, остаётся решённой не

полностью. Описанные выше причины вынуждают развивать методы

минимизации времени выполнения параллельной программы за счёт

8

модификации распределения данных в рамках блоков исходного кода с набором гнёзд циклов (ГЦ).

Объектом исследования являются МВС с распределённой памятью. Под термином МВС с распределённой памятью понимаются такие классы суперкомпьютеров как кластерные (High Performance Computing, НРС) и массово-параллельные (Massive Parallel Processing, МРР) вычислительные системы.

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

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

Задачи исследования. Достижение поставленной цели предполагает решения следующих основных задач исследования:

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

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

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

• разработка системы эвристических правил, позволяющая производить выбор рационального варианта распределения данных для гнёзд циклов в рамках блоков исходного кода;

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

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

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

Структура и объём работы. Диссертация состоит из введения, 4 глав, заключения, списка литературы и приложения. В конце работы помещены акты об использовании результатов работы, акты о внедрении результатов в учебный процесс и справка о регистрации программ. Общий объем работы - 149 страниц машинописного текста, из них 120 страниц - основное содержание, 17 страниц-библиографический список (168 наименований).

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

В настоящее время спектр задач, требующих для своего решения значительных вычислительных ресурсов, постоянно расширяется. В первую очередь это связано с тем, что произошли фундаментальные изменения в самой организации научных исследований. Вследствие широкого внедрения вычислительной техники, значительно усилилось направление численного моделирования и численного эксперимента. Численное моделирование, заполняя промежуток между физическими экспериментами и аналитическими подходами, позволило изучать явления, которые представляются либо слишком сложными для исследования аналитическими методами [1, 70], либо слишком дорогостоящими или опасными для экспериментального изучения. При этом численный эксперимент позволил значительно удешевить процесс научно-технологического поиска [2, 33]. Стало возможным за приемлемое время решать обширный пласт таких инженерно- технических задач как:

• моделирование аэрогазодинамических процессов, механики жидкостей и газов, гидравлики, термодинамики, теплопроводности;

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

• моделирование физико-химических и ядерных реакций, глобальных атмосферных процессов, а также процессы экономического и промышленного развития регионов/городов [67].

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

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