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

Попова-Коварцева Дарья Александровна

АЛГОРИТМЫ АНАЛИЗА И СИНТЕЗА УПРАВЛЯЮЩИХ

ГРАФОВ В ЗАДАЧАХ ОРГАНИЗАЦИИ ПАРАЛЛЕЛЬНЫХ

ВЫЧИСЛЕНИЙ

05.13.01 – Системный анализ, управление и обработка информации

(технические системы и связь)

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

Самара 2013

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

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

Официальные оппоненты: Гергель Виктор Павлович, д.т.н., профессор, ФГБОУ ВПО «Нижегородский государственный университет им. Н.И. Лобачевского», декан факультета вычислительной математики и кибернетики Пиявский Семен Авраамович, д.т.н., профессор ФГБОУ ВПО «Самарский государственный архитектурно-строительный университет», заведующий кафедрой « Прикладная математика и вычислительная техника»

Ведущая организация: ФГБУН Институт проблем управления сложными системами РАН (г. Самара)

Защита состоится 18 декабря 2013 г. в 12 часов на заседании диссертационного совета Д 212.215.07, созданного на базе ФГБОУ ВПО «Самарский государственный аэрокосмический университет имени академика С.П. Королва (национальный исследовательский университет)», по адресу: 443086, г. Самара, Московское шоссе, 34.

С диссертацией можно ознакомиться в библиотеке ФГБОУ ВПО «Самарский государственный аэрокосмический университет имени академика С.П. Королва (национальный исследовательский университет)».

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

Ученый секретарь диссертационного совета д.т.н., профессор И. В. Белоконов

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

Актуальность работы.

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

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

Известно, что основными потребителями суперкомпьютерных технологий являются специалисты в предметных областях, которые используют сложные математические или вычислительные модели газовой динамики, молекулярной химии, решающие задачи математической физики, обработки изображений, динамики движения механических систем с распределенными параметрами и т.п. Данный круг пользователей, обладающий хорошими знаниями в области математики, как раз и способен предлагать в своих предметных областях алгоритмы распараллеливания вычислительных процессов, но от них сложно требовать глубоких знаний в области администрирования суперкомпьютерных систем, системного и прикладного программирования. Возникающая необходимость равнозначного владения технологиями программирования на языках высокого уровня (C++, C#) и средством распараллеливания программ MPI еще дальше отдаляет «конечных» пользователей от возможности участия в разработке авторских параллельных приложений. Кроме того, эффективность моделей параллельных алгоритмов часто определяется их согласованностью с архитектурой высокопроизводительных систем, когда приходится учитывать и коммуникационные затраты на передачу информации между процессорами.

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

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

Исследования в области системного анализа и оптимизирующих преобразований моделей алгоритмов достаточно подробно рассмотрены в работах: А.А.Ляпунова, Ю.А. Янова, В.М. Глушкова, А.П. Ершова, М.Р. ШурыБуры, С.С. Лаврова, В.Н. Касьянова, В.А. Евстигнеева, А.А. Берса, Р.И.

Подловченко, А.Н. Терехова, Э.В.Дейкстры, Д. Кнута, Дж. Маккарти, В.М.

Тарского, Р. Флойда, Ч. Хоара, Н. Вирта и др.

Методы моделирования параллельных процессов рассматривались в работах В.В. Воеводина, Вл.В. Воеводина, И.В. Вельбицкого, В.П. Гергеля, В.А. Фурсова, С.В. Востокина, А.Н. Коварцева, В.Е Котова и др.

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

Результаты исследования соответствуют пунктам: 4 – «Разработка методов и алгоритмов решения задач системного анализа, оптимизации, управления, принятия решений и обработки информации.», 5 – «Разработка специального математического и алгоритмического обеспечения систем анализа, оптимизации, управления, принятия решений и обработки информации», 8 – «Теоретико-множественный и теоретико-информационный анализ сложных систем» паспорта научной специальности 05.13.01 – Системный анализ, управление и обработка информации (технические системы и связь).

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

Основные задачи

диссертационной работы, определяемые поставленной целью, состоят в следующем:

1. Исследование современного состояния методов системного анализа моделей параллельных алгоритмов для высокопроизводительных систем, основанных на использовании MPI.

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

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

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

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

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

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

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

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

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

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

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

Внедрение результатов работы Результаты работы внедрены в ФГБОУ ВПО Самарском государственном аэрокосмическом университете имени академика С.П. Королева (национальный исследовательский университет), Институте акустики машин при ФГБОУ ВПО Самарском государственном аэрокосмическом университете имени академика С.П. Королева (национальный исследовательский университет).

На защиту выносятся:

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

2. Алгоритм F- нумерации вершин управляющего графа.

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

4. Алгоритм топологической сортировки вершин орграфа и метод структурной оптимизации управляющих графов.

Апробация работы Основные положения и результаты работы докладывались и обсуждались на Международной конференции с элементами научной школы для молодежи «Перспективные информационные технологии для авиации и космоса»

(Самара, 2010 г.), XI Всероссийской конференции «Высокопроизводительные параллельные вычисления на кластерных системах» (Нижний Новгород, г.), Всероссийской научно-технической конференции «Актуальные проблемы радиоэлектроники и телекоммуникаций» (Самара, 2012 г.), Международной научной конференции «Параллельные вычислительные технологии»

(Челябинск, 2013 г.), III Международной научно-технической конференции «Открытые семантические технологии проектирования интеллектуальных систем» (Минск, 2013 г.).

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

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

изложено на 168 страницах, включая 56 рисунков и таблиц. Список использованных источников включает 101 наименование, приложения размещены на 6 страницах.

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

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

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

Известные подходы и методы моделирования алгоритмов приводятся в п.п. 1.1.

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

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

Центром развития графовых моделей и методов программирования является авторитетная Новосибирская школа, созданная академиком А.П.

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

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

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

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

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

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

Посыпкина, Я.Д. Сергеева и др.

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

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

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

формальные пользовательские требования к представлению модели параллельного алгоритма и фактическую форму его описания, приемлемого для реализации на высокопроизводительных кластерных системах под управлением MPI. Именно алгоритмы структурного преобразования исходной (пользовательской) модели описания параллельного алгоритма к «унифицированному» виду составляют основное содержание второй главы.

В п.п. 2.1, 2.2 и 2.3 приводятся основные положения технологии ГСП, используемые в диссертации. В частности, вычислительная модель параллельных алгоритмов описывается четверкой M G =, где D – множество данных некоторой предметной области, A – множество вычислимых функций, определенных над данными предметной области, – множество дуг управления, G { A, } – ориентированный помеченный граф, описывающий граф-модель вычислительного процесса.

Параллельные вычисления – это совокупность одновременно исполняемых вычислений. Для описания отдельного вычислительного процесса в ГСП вводится понятие параллельной ветви модели - подграфа графа G, начинающегося параллельной дугой (тип этой дуги T(ij) = 2, на схеме помечается «кружочком») и заканчивающегося терминирующей дугой (тип этой дуги T(ij) = 3, на схеме помечается перечркнутой дугой).

Формально параллельную ветвь можно определить тройкой:

где A – множество вершин ветви, – множество дуг управления ветви, R – отношение над множествами вершин и дуг ветви, определяющее способ их связывания.

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

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

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

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

В п.п. 2.3 приводится алгоритм десуперпозиции P-графа к совокупности примитивов, названных правильно построенными агрегатами (ППА) (см.

Рисунок 1 - Правильно ветвления обозначены символом “H”. Терминирующие построенный агрегат вершины - символом “E”. Вершины, принадлежащие Мастер ветвь агрегата G0 содержит 3 параллельные ветви, в каждую из которых вложены еще по две параллельные ветви, и в этом смысле G0 не является ППА. Для выполнения параллельных вычислений необходимо произвести разбиение структуры графа G0 на совокупность правильно построенных агрегатов (модель C), например так, как это показано на рисунке 3.

Можно сформулировать следующую формальную постановку задачи:

Пусть задан ориентированный граф G0 ( A, ), A n и пусть Требуется найти десуперпозицию R( A ) ( A( 1 ), A( 2 ),..., A( r ) ) (здесь A( i ) подмножество множества вершин A ) графа G0 на r правильно построенных подграфов Gi ( A (i ) Gi ), таких что Прежде чем производить десуперпозицию Р-графа, необходимо произвести системный анализ рассматриваемого объекта с целью сбора информации о строении графа, выделения требуемых подструктур с уточнением инфраструктуры графа относительно выделенных подструктур.

Рисунок 3 - Разбиение агрегата G0 на правильные компоненты (модель C) Введем понятие F-нумерациеи графа G, под которой будем понимать инъективное отображение множества вершин A(G) графа на множество слов X *, алфавита X :

Пусть алфавит имеет вид: X {" H", "V ", " E", ".", "0", "1", "2",...}. Слова нумерации имеют следующую семантику: M Nur.Type. N1. N2..NNur, где Nur - количество уровней иерархии при вложенности параллельных структур друг в друга; Ni - номер вершины на i-м уровне иерархии (если i=Nur) или номер иерархии вложения; Type – тип вершины (Type=H для вершины ветвления; Type=E для терминальных вершин; для остальных Type=V).

Представленный код вершины точно идентифицирует структуру направленного последовательно-параллельного Р-графа. На рисунке приведен пример разметки графа G0 (модель B).

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

Десуперпозиция реализуется в соответствии со следующими правилами:

Правило 1. Используя разметку F-нумерации, несложно идентифицировать вершины каждой из параллельных веток графа, находящиеся между параллельной и терминирующей вершинами одного уровня. Каждый из таких «наборов» вершин агрегируются в отдельный подграф. Вложенному агрегату присваивается новое имя. Выделенный подграф заменяется в исходном подграфе новой вершиной.

Правило 2. Если новый подграф не является ППА, то к нему применяется правило 1.

Правило 3. Процедура десуперпозиции завершается, если для исходного и всех новых подграфов невозможно применить правило 1.

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

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

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

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

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

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

Фаза глобальной оптимизации (см. рис. 6) реализуется с помощью модифицированного алгоритма половинных делений, с той лишь разницей, что двоичное деление параллелепипедов происходит до достижения заданных размеров радиусов параллелепипедов Ri. Величина Ri определяется размером «гарантированного радиуса» m ( m min i ) областей притяжения минимумов функции, чем обеспечивается существенное сокращение сложности задачи оптимизации в первой фазе.

Рисунок 6 – Двухфазный алгоритм метода половинных делений В фазе локальной оптимизации из точек, принадлежащих областям притяжения локальных минимумов, организуется поиск минимумов функции с помощью локальных алгоритмов оптимизации. В диссертации показано, что сложность двухфазного алгоритма метода половинных делений (ДАМПД) может быть оценена величиной N (n) 2(1 / 2 m ) n 1 r log 2 ( m / 2 ).

Важно отметить, что алгоритм ДАМПД легко распараллеливается, и его простейшая версия представлена на рисунке 6.

Тестирование алгоритма ДАМПД проводилось на наиболее сложном для реализации алгоритмов поиска глобального минимума классе недифференцируемых функций пакета генерации тестовых функций GKLS.

Для всех классов задач была задана стандартная конфигурация настраиваемых параметров: число экстремумов равно 10; глобальный минимум равен -1; радиус притяжения глобального оптимума – 0,33. Эксперименты проводились на суперкомпьютерном кластере СГАУ «Сергей Королев».

Кластер построен на базе линейки оборудования IBM BladeCenter с использованием блейд-серверов HS22 и обеспечивает пиковую производительность более 10 триллионов операций с плавающей точкой в секунду. Общее число процессоров/вычислительных ядер: 272/1184.

Глобальный минимум вычислялся с точность функции).

Эффективность алгоритма оценивалась по критерию количества испытаний оптимизируемой функции и была рассчитана с учетом распараллеливания вычислительных процессов (быстродействие). Для алгоритма ДАМПД этот показатель несложно вычислить по формуле:

на каждом i-м процессоре в фазе глобальной оптимизации; N ЛО - количество обращений к функции на каждом j-м процессоре в фазе локальной оптимизации. В таблице 1 приведены осредненные значения количества испытаний алгоритма ДАМПД для тестовых функций размерностей от 2 до 7.

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

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

Четвертая глава посвящена структурной оптимизации агрегатов технологии ГСП.

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

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

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

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

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

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

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

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

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

графа G на две части: G1 и G2, по линии разреза при x=2.

Если граф разбивается на N частей, то, введя вектор X можно поставить условную задачу глобальной оптимизации:

где C j - структурная сложность j-го подграфа, n – число вершин в исходном графе.

Задачу (2) можно существенно упростить, введя дополнительные переменные y1,..., y N [0; 1], и преобразование тогда задача условной оптимизации (2) сводится к задаче безусловной оптимизации (3):

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ:

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

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

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

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

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

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

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

1. Коварцев, А.Н. К вопросу об эффективности параллельных алгоритмов глобальной оптимизации функций многих переменных [Текст]/ Коварцеа А.Н., Попова-Коварцева Д.А. // Компьютерная оптика. 2011. – Т. 35, № 2.- С. 256 – 262.

2. Коварцев, А.Н. Многомерный параллельный алгоритм глобальной оптимизации модифицированным методом половинных делений [Текст]/ Коварцев А.Н., Попова-Коварцева Д.А. // В мире научных открытий. № 8.1(32), 2012. С. 80-108.

3. Попова-Коварцева, Д.А. Правильная нумерация двухполюсного ориентированного графа [Текст]/ Попова-Коварцева Д.А.// Вестник Самарского государственного аэрокосмического университета имени академика С.П. Королева. №7, 2012. С. 23-28.

4. Коварцев, А.Н. Структурная оптимизация управляющего графа на основе алгоритма топологической оптимизации [Текст]/ Коварцев А.Н., Попова-Коварцева Д.А. // Программная инженерия, №5, 2013. С. 31 – 37.

5. Коварцев, А.Н. Эффективность глобальной параллельной оптимизации функций многих переменных [Текст]/ Коварцев А.Н., Попова-Коварцева Д.А., Аболмасов П.В. // Вестник ННГУ №3, 2013. С. 189-198.

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

6. Коварцев, А.Н. Программное средство разработки и системного анализа алгоритмов и программ параллельных вычислений PGRAPH [Текст]/ Коварцев А.Н., Жидченко В.В., Попова-Коварцева Д.А., Аболмасов П.В. // Свидетельство о государственной регистрации программ для ЭВМ. Рег. № 2013616615 от 12.07.13.

Статьи:

7. Коварцев, А.Н. Алгоритм структурного преобразования графа управления параллельными вычислениями для систем с распределенной памятью MPI [Текст]/ Коварцев А.Н., Попова-Коварцева Д.А. // Перспективные информационные технологии для авиации и космоса: труды международной конференции с элементами научной школы для молодежи. / Изд-во СГАУ – Самара, 2010. – С. 515-520.

8. Коварцев, А.Н. Структурная декомпозиция графа управления параллельными вычислениями в интересах стандарта MPI [Текст]/ Коварцев А.Н., Попова-Коварцева Д.А. // Высокопроизводительные параллельные вычисления на кластерных системах : материалы XI всероссийской конференции./ Изд-во Нижегородского госуниверситета – Нижний Новгород, 2011. – С. 158-162.

9. Попова-Коварцева, Д.А. Использование средства визуального моделирования PGRAPH при изучении параллельных вычислительных технологий [Текст]/ Попова-Коварцева Д.А., Коварцев А.Н., Жидченко В.В., Аболмасов П.В. // Материалы докладов выездного заседания Научнометодических советов по математике и по информатике Министерства образования и науки РФ/ Самара: СГАУ, 2012. – С. 86-90.

10. Попова-Коварцева, Д.А. Алгоритм правильной нумерации двухполюсного ориентированного графа [Текст]/ Попова-Коварцева Д.А.// Актуальные проблемы радиоэлектроники и телекоммуникаций: труды Всероссийской научно-технической конференции, посвящнная 70-летию КуАИ - СГАУ и 50-летию РТФ./ Изд-во СГАУ – Самара, 2012. – С..

11. Коварцев, А.Н. Исследование эффективности глобальной параллельной оптимизации функции многих переменных [Текст]/ Коварцев А.Н., Попова-Коварцева Д.А., Аболмасов П.В. // Параллельные вычислительные технологии: труды международной научной конференции./ Издательский центр ЮУрГУ – Челябинск, 2013. – С.155- 167.

графосимволического программирования [Текст]/ Коварцев А.Н., Жидченко В.В., Попова-Коварцева Д.А., Аболмасов П.В. //Открытые семантические технологии проектирования интеллектуальных систем: труды III международной научно-технической конференции./ Изд-во БГУИР – Минск, 2013. – С. 195-204.