Введение к работе
Актуальность работы.
Современный этап развития информационных технологий в области повышения производительности вычислительных систем в значительной степени связан с переходом производителей компьютерного оборудования на выпуск многоядерных процессоров. Появившаяся возможность более быстрого решения прикладных задач на вычислительной технике с параллельной архитектурой вынуждает разработчиков программных систем изменять свой привычный стиль взаимодействия с компьютерами. Параллельные вычисления, традиционно относившиеся к компетенции узкого круга программистов, стали приобретать массовый характер, что требует разработки программных комплексов, обеспечивающих автоматизацию процессов разработки эффективных параллельных программ в интересах специалистов в соответствующих областях знаний.
Данное обстоятельство особенно важно, если учесть, что в настоящее время наиболее популярный способ разработки моделей параллельных алгоритмов для высокопроизводительных систем с распределенной памятью основывается на использовании библиотек MPI или подобных им средств.
Известно, что основными потребителями суперкомпьютерных технологий являются специалисты в предметных областях, которые используют сложные математические или вычислительные модели газовой динамики, молекулярной химии, решающие задачи математической физики, обработки изображений, динамики движения механических систем с распределенными параметрами и т.п. Данный круг пользователей, обладающий хорошими знаниями в области математики, как раз и способен предлагать в своих предметных областях алгоритмы распараллеливания вычислительных процессов, но от них сложно требовать глубоких знаний в области администрирования суперкомпьютерных систем, системного и прикладного программирования. Возникающая необходимость равнозначного владения технологиями программирования на языках высокого уровня (C++, С#) и средством распараллеливания программ MPI еще дальше отдаляет «конечных» пользователей от возможности участия в разработке авторских параллельных приложений. Кроме того, эффективность моделей параллельных алгоритмов часто определяется их согласованностью с архитектурой высокопроизводительных систем, когда приходится учитывать и коммуникационные затраты на передачу информации между процессорами.
Естественным выходом из сложившейся ситуации является приближение технологий разработки параллельных алгоритмов к специалистам-предметникам. Для конечных пользователей желательно иметь достаточно простые выразительные визуальные средства описания параллельных алгоритмов, в то время как вопросы преобразования алгоритмов к виду, который можно исполнить на высокопроизводительной ЭВМ, с учетом их архитектуры и используемых системных средств распараллеливания
вычислений, необходимо автоматизировать.
Для описания информационной структуры алгоритма (ИСА) часто используют понятие управляющего графа алгоритма (уграфа). Такая форма представления модели алгоритма лаконично описывает его информационную сущность, является удобным формализмом для системного анализа свойств разрабатываемого алгоритма и производства необходимого количества изоморфных преобразований ИСА под особенности используемых вычислительных средств и системного программного обеспечения.
Исследования в области системного анализа и оптимизирующих преобразований моделей алгоритмов достаточно подробно рассмотрены в работах: А.А.Ляпунова, Ю.А. Янова, В.М. Глушкова, А.П. Ершова, М.Р. Шуры-Буры, С.С. Лаврова, В.Н. Касьянова, В.А. Евстигнеева, А.А. Берса, Р.И. Подловченко, А.Н. Терехова, Э.В.Дейкстры, Д. Кнута, Дж. Маккарти, В.М. Тарского, Р. Флойда, Ч. Хоара, Н. Вирта и др.
Методы моделирования параллельных процессов рассматривались в работах В.В. Воеводина, Вл.В. Воеводина, И.В. Вельбицкого, В.П. Гергеля, В.А. Фурсова, СВ. Востокина, А.Н. Коварцева, В.Е Котова и др.
В связи с чем актуально направление исследований, связанное с разработкой методов анализа и синтеза ИСА, которые осуществляют преобразование моделей параллельных алгоритмов к унифицированному виду, пригодному для реализации на высокопроизводительных системах с распределенной памятью, использующих MPI.
Результаты исследования соответствуют пунктам: 4 - «Разработка методов и алгоритмов решения задач системного анализа, оптимизации, управления, принятия решений и обработки информации.», 5 - «Разработка специального математического и алгоритмического обеспечения систем анализа, оптимизации, управления, принятия решений и обработки информации», 8 -«Теоретико-множественный и теоретико-информационный анализ сложных систем» паспорта научной специальности 05.13.01 - Системный анализ, управление и обработка информации (технические системы и связь).
Целью работы является разработка алгоритмов анализа и синтеза управляющих графов параллельных вычислений, формирующих дружественную среду разработки и исполнения параллельных алгоритмов для высокопроизводительных систем с распределённой памятью, использующих MPI.
Основные задачи диссертационной работы, определяемые поставленной целью, состоят в следующем:
-
Исследование современного состояния методов системного анализа моделей параллельных алгоритмов для высокопроизводительных систем, основанных на использовании MPI.
-
Разработка алгоритмов структурных преобразований управляющих графов моделей алгоритмов организации параллельных вычислений применительно к высокопроизводительным системам с распределённой памятью, использующих MPI.
-
Разработка параллельного алгоритма глобальной оптимизации функции многих переменных для решения задачи структурной оптимизации управляющих графов программ.
-
Разработка метода структурной оптимизации моделей граф-алгоритмов, снижающего сложность тестирования соответствующего программного обеспечения.
Научная новизна. При выполнении работы получены следующие новые результаты:
-
Для описания параллельных вычислений предложена новая модель уграфа - двухполюсный последовательно-параллельный Р-граф, на основе которого разработаны алгоритмы декомпозиционных эквивалентных преобразований исходного Р-графа к унифицированному виду, пригодному для реализации параллельных вычислений на кластерной системе с распределённой памятью в среде MPI.
-
Разработана двухфазная модель организации параллельного процесса поиска глобальных экстремумов функций многих переменных, основанная на рациональном использовании методов локальной оптимизации и снижающая сложность решения задачи оптимизации.
-
Предложен и обоснован алгоритм топологической сортировки управляющих графов моделей алгоритмов для направленных контурных графов, содержащих начальную и конечную вершины.
-
Предложен новый метод оценки сложности тестирования графа алгоритма, позволяющий сформулировать безусловную оптимизационную задачу структурного преобразования уграфа, решение которой снижает трудоемкость оценки качества разрабатываемой модели алгоритма.
Практическую ценность работы составляют:
Алгоритмы и соответствующее программное обеспечение,
позволяющие исследовать корректность графа управления моделями сложных
параллельных и последовательных алгоритмов, а также скрыть от пользователя
специфические особенности использования системы MPI для организации
параллельных вычислений на высокопроизводительных компьютерных
системах с распределённой памятью.
Разработанные алгоритмы структурных преобразований управляющего
графа модели параллельных алгоритмов используются в комплексе программ
PGRAPH, ориентированном на специалистов в наукоёмких предметных
областях, где велика потребность в распараллеливании вычислительных
процессов, и где можно ожидать хорошую результативность от использования
суперкомпьютерных технологий.
Достоверность научных результатов и выводов подтверждается обоснованностью применения и корректной реализацией используемого
математического аппарата, результатами вычислительных экспериментов и тестирования алгоритмов и программного обеспечения, научной экспертизой на научных конференциях и при публикации в научной печати.
Внедрение результатов работы
Результаты работы внедрены в ФГБОУ ВПО Самарском государственном аэрокосмическом университете имени академика СП. Королева (национальный исследовательский университет), Институте акустики машин при ФГБОУ ВПО Самарском государственном аэрокосмическом университете имени академика СП. Королева (национальный исследовательский университет).
На защиту выносятся:
-
Алгоритмы анализа и синтеза информационных структур управляющего графа модели параллельных вычислений.
-
Алгоритм F- нумерации вершин управляющего графа.
-
Двухфазный алгоритм модифицированного метода половинных делений, предназначенный для глобальной оптимизации функции многих переменных.
-
Алгоритм топологической сортировки вершин орграфа и метод структурной оптимизации управляющих графов.
Апробация работы
Основные положения и результаты работы докладывались и обсуждались на Международной конференции с элементами научной школы для молодежи «Перспективные информационные технологии для авиации и космоса» (Самара, 2010 г.), XI Всероссийской конференции «Высокопроизводительные параллельные вычисления на кластерных системах» (Нижний Новгород, 2011 г.), Всероссийской научно-технической конференции «Актуальные проблемы радиоэлектроники и телекоммуникаций» (Самара, 2012 г.), Международной научной конференции «Параллельные вычислительные технологии» (Челябинск, 2013 г.), III Международной научно-технической конференции «Открытые семантические технологии проектирования интеллектуальных систем» (Минск, 2013 г.).
Публикации
Соискатель имеет 14 опубликованных работ, в том числе, по теме диссертации 11 работ, из них 5 работ опубликованы в ведущих рецензируемых научных журналах и изданиях, определенных Высшей аттестационной комиссией, 1 свидетельство о государственной регистрации программы для ЭВМ.
Объем и структура работы
Диссертация состоит из введения, четырёх глав и заключения. Основное содержание работы изложено на 168 страницах, включая 56 рисунков и 25 таблиц. Список использованных источников включает 101 наименование, 2 приложения размещены на 6 страницах.
