Алгоритмы анализа и синтеза управляющих графов в задачах организации параллельных вычислений тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат наук Попова-Коварцева, Дарья Александровна

• Попова-Коварцева, Дарья Александровна
• кандидат наук
• 2013

Оглавление диссертации кандидат наук Попова-Коварцева, Дарья Александровна

Содержание

Введение

1. СОВРЕМЕННОЕ СОСТОЯНИЕ МЕТОДОВ СИСТЕМНОГО АНАЛИЗА МОДЕЛЕЙ ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ

1.1. Методы анализа моделей параллельных алгоритмов

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

1.3. Современные методы глобальной оптимизации

Выводы и основные результаты

2. СТРУКТУРНОЕ ПРЕОБРАЗОВАНИЕ ГРАФА УПРАВЛЕНИЯ ПАРАЛЛЕЛЬНЫМИ ВЫЧИСЛЕНИЯМИ ДЛЯ СИСТЕМ С РАСПРЕДЕЛЕННОЙ ПАМЯТЬЮ MPI

2.1. Концептуальная модель технологии ГСП

2.2. Управление вычислительными процессами. Граф-машина

2.2.1. Представление графа управления агрегатов

2.2.2. Граф-машина

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

2.3.1. Синхронный параллелизм

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

2.3.3. Межмодульный интерфейс параллельного обмена данными

2.3.4. Десуперпозиция Р-графа

2.3.5. Сложность алгоритма F-нумерации вершин Р-графа

2.4. Алгоритм F-нумерации вершин Р-графа

2.4.1. Головная программа алгоритма F-нумерации Р-графа

2.4.2. Агрегат «Разметка вершин преемников для дуг типа 1»

2.4.3. Агрегат «Разметка вершин преемников для дуг типа 2»

2.4.4. Агрегат «Разметка вершин преемников для дуг типа 3»

2.5. Алгоритм десуперпозиции Р-графа

2.5.1. Агрегат «Построение графа, содержащего подграфы»

2.5.2. Агрегат «Вершина ветвления графа, содержащего подграфы»

2.5.3. Агрегат «Параллельный граф без вложений»

2.6. Преобразование графа управления модели параллельного алгоритма к стандартному виду

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

2.7.1. Дерево вложенности агрегатов

2.7.2. Алгоритм операции суперпозиции двух агрегатов

Выводы и основные результаты

3. ОПТИМИЗИРУЮЩИЕ ПРЕОБРАЗОВАНИЯ ПРОГРАММ. АЛГОРИТМ ГЛОБАЛЬНОЙ ОПТИМИЗАЦИИ

3.1. Введение

3.2. Методы глобальной оптимизации функций многих переменных

3.3. Постановка задачи глобальной оптимизации. Метод половинных делений

3.4. Оценка сложности алгоритмов глобальной оптимизации

3.4.1. Полный перебор метода половинных делений

3.4.2. Метод половинных делений с учётом отбраковки параллелепипедов

3.4.3. Метод редукции

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

3.5. Модифицированный метод половинных делений глобальной оптимизации функции многих переменных

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

3.7. Двухфазный алгоритм метода половинных делений (ДАМПД)

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

3.9. Исследование сходимости двухфазного алгоритма метода

половинных делений

ЗЛО. Схема «менеджер-исполнитель» ДАМПД

3.11. Генератор тестовых многоэкстремальных функций многих переменных

3.12. Исследование эффективности алгоритма ДАМПД

Выводы и основные результаты

4. СТРУКТУРНАЯ ОПТИМИЗАЦИЯ АГРЕГАТОВ ТЕХНОЛОГИИ ГСП

4.1. Введение

4.2. Структурное тестирование агрегатов технологии ГСП

4.3. Схемы маршрутов в технологии ГСП

4.4. Метрики оценки структурной сложности программы

4.5. Алгоритм структурного преобразования программы

4.6. Алгоритм топологической сортировки

4.6.1. Топологическая сортировка

4.6.2. Алгоритм Р-нумерации

Выводы и основные результаты

Заключение

Список литературы

Приложение 1

П1.1 Агрегат "Десуперпозиция параллельного графа на составляющие"

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

Приложение 2 Акты внедрения

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

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4. Предложен новый метод оценки сложности тестирования графа

7

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

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

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

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

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

Внедрение результатов работы

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

(национальный исследовательский университет).

8

Апробация работы

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

Публикации

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

Объем и структура работы

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

1. СОВРЕМЕННОЕ СОСТОЯНИЕ МЕТОДОВ СИСТЕМНОГО АНАЛИЗА МОДЕЛЕЙ ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ

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

Современное состояние теории программирования уже неотделимо от применения теоретико-графовых методов и соответствующих алгоритмов. Широкое использование выразительных возможностей графов объясняется тем, что они предоставляют естественные возможности объяснения сложных ситуаций на интуитивном уровне. Преимущества описания сложных структур и процессов графами еще более усиливается при наличии хороших средств их визуализации. Неслучайно, что в настоящее время одним из наиболее актуальных направлений применения графов в программировании является визуализация информации на основе графов и графовых моделей [30, 32, 68, 77].

1.1. Методы анализа моделей параллельных алгоритмов

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

Важно отметить и то обстоятельство, что в области параллельных вычислений привычное программирование, без использования и анализа моделей разрабатываемых алгоритмов, становится малоэффективным. Модель алгоритма должна выполнять роль некоторого ядра, очищенного от всех языковых наслоений. После такой очистки остается лишь некоторая совокупность выполняемых операций, связанных между собой отношениями "результат-аргумент". Тогда математическую модель алгоритма можно описать графом, который часто называют графом алгоритма [10, 12, 23, 32, 36, 39]. Естественно, что для того, чтобы в одинаковых условиях разные записи алгоритмов приводили к одним и тем же результатам, необходимо и достаточно, чтобы были изоморфны их графы. Построенные графы описывают информационные сущности алгоритмов. Они не зависят ни от используемых языков описания, ни от применяемых вычислительных средств. Поэтому, вполне естественно, их считать информационными ядрами самих алгоритмов. Граф алгоритма имеет очень прозрачный смысл. Поэтому его легко применять в теоретических исследованиях [12].

Основы математических методов исследования алгоритмов заложили А.А.Ляпунов и его ученики фактически в середине прошлого столетия [23, 43, 60]. A.A. Ляпунов исходил из необходимости выработки нового подхода к определению алгоритма, поскольку известные на тот момент традиционные модели теории алгоритмов (машины Тыоринга, продукции Поста,

11

нормальные алгоритмы Маркова, исчисление Чёрча-Клини) были хороши для исследования природы вычисления, но непригодны для описания алгоритмов в форме, удобной для решения практических задач [51]. Предложенный A.A. Ляпуновым операторный метод базируется на следующих концепциях: понятии алгоритма как объекта математической модели вычислений; введении для алгоритмов понятий эквивалентности и эквивалентных преобразований; введении понятия схемы алгоритма.

Сформулированная проблема эквивалентных преобразований, т.е. построение такой системы преобразований, в рамках которой любые два эквивалентных объекта с помощью эквивалентных преобразований трансформировались друг в друга, в дальнейшем нашли широкое распространение при изучении моделей алгоритмов и в практическом программировании. В частности, предложенные Ю.И. Яновым [60] схемы описания программ позволили доказать для них разрешимость проблемы эквивалентности и проблемы эквивалентных преобразований, что стало первым результатом в теории схем программ.

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

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

в мире, были разработаны опытно-экспериментальные версии оптимизирующих трансляторов (проекты Альфа и БЕТА) [7]. В Альфа-трансляторе использовался богатый набор оптимизирующих преобразований. Была предложена смешанная стратегия программирования таких конструкций, как процедуры, циклы, индексные выражения. На основании анализа контекста выбирался способ генерации конструкций, наиболее эффективный из допустимого набора. В результате, процедуры, при всей мощности этого механизма, программировались оптимальным образом. Существовавшая ранее оптимизация математических выражений была существенно развита - полностью учитывались свойства коммутативности и ассоциативности; она уже стала квазилокальной. Впервые была реализована глобальная чистка циклов. Тщательной оптимизации подвергались операции над многомерными значениями - то, чего не было в стандартном Алголе, но активно использовалось вычислителями. Впервые была реализована глобальная экономия памяти, опирающаяся на теоретические работы А.П. Ершова и С.С. Лаврова. Альфа-транслятор стал первым в мире транслятором с Алгола с большими оптимизирующими возможностями. Успеху способствовало не только механическое соединение многих оптимизаций, но и существенное развитие известной методологии оптимизации программ.

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

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

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

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

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

Данное обстоятельство доводит используемое формальное представление модели алгоритма программы до уровня самой программы, поскольку граф-модель алгоритма в ГСП является образным представлением разрабатываемой программы, т.е. является своеобразным языком

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

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

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

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

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

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

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

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

Графические модели на основе графов переходов используются в SWITCH-технологии [59] и графическом языке Statecharts. Графы переходов (диаграммы состояний, диаграммы изменений состояний) представляют собой графическую форму описания конечных автоматов. Вершины графа переходов соответствуют состояниям автомата, а дуги определяют возможные переходы из одного состояния в другое. Традиционно графы переходов используются для описания «последовательных» автоматов, так как одновременные переходы по двум и более дугам, исходящим из одной вершины, считаются запрещенными. Если такие переходы разрешены, то графы переходов, в которых допустимо одновременное существование нескольких «активных» вершин, называются графами переходов с параллелизмом. Математический базис для такого подхода обеспечивает теория автоматов.

В Институте кибернетики имени В.М.Глушкова ещё в 70-х годах XX века была разработана Р-технология программирования, использующая графическую модель описания алгоритмов, близкую к автоматным, и получившую название Р-схем [10]. Р-схема - нагруженный по дугам ориентированный граф, изображаемый с помощью горизонтальных и вертикальных линий и состоящий из структур с одним входом и одним выходом. Построение Р-схем осуществляется из базовых графических структур двух видов, представленных на рисунке 1.1а. Остальные конструкции получаются с помощью операций последовательного, параллельного и вложенного соединения базовых элементов. Примеры таких конструкций приведены на рисунках 1.16, в и г соответственно. Для Р-схем разработан и введен в действие ГОСТ 19.005-85, определяющий внешнюю форму их представления.

Список литературы диссертационного исследования кандидат наук Попова-Коварцева, Дарья Александровна, 2013 год

Список литературы

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

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

A3 Коварцев А.Н., Попова-Коварцева Д. А., Аболмасов П.В. Исследование эффективности глобальной параллельной оптимизации функций многих переменных // Труды международной научной конференции «Параллельные вычислительные технологии. Челябинск, 2013. С. 155-166

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

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

А6 Коварцев А.Н., Попова-Коварцева Д.А., Жидченко В.В., Аболмасов П.В. Использование средства визуального моделирования PGRAPH при изучении параллельных вычислительных технологий // Материалы докладов выездного заседания Научно-методических

советов по математике и по информатике Министерства образования и науки РФ/ Самара: СГАУ, 2012. - С. 86-90.

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

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

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

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

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

1 Абрамов С.М., Кузнецов A.A., Роганов В.А. Кроссплатформенная версия Т-системы с открытой архитектурой // Вычислительные методы и программирование. - 2007. - Том 8, Раздел 2. - С. 18-23.

2 Айвазян С.А., Евшоков И.С., Мешалкин Л.Д. Прикладная статистика: Основы моделирования и первичная обработка данных. - М.: Финансы и статистика, 1983. - 471 с.

3 Б. Страуструп Язык программирования С++. Специальное издание. -М.: Бином, 2001.- 1099 с.

4 Б. Страуструп Язык программирования С++. Специальное издание. - М.: Бином, 2001. - 1099 с.

5 Баранов С. И., Журавина JI. Н., Песчанский В. А. Метод представления параллельных граф-схем алгоритмов совокупностями последовательных граф-схем // Автоматика и вычислительная техника. 1984. № 5. С. 74—81.

6 Баркалов К.А., Рябов В.В., Сидоров С.В. О некоторых способах балансировки локального и глобального поиска в параллельных алгоритмах глобальной оптимизации // Вычислительные методы и программирование. 2010. Т. 11, № 2. 189-194

7 Берс A.A. Отдел программирования ВЦ СО АН СССР и языки. // Тр. 2-ой Межд. Конф. «Развитие вычислительной техники и её программного обеспечения в России и странах бывшего СССР», Великий Новгород, 2011. С.56-64

8 Богомолов A.M., Салий В.П. Алгебраические основы теории дискретных систем. - М.: Наука Физматлит, 1997. - 380 с.

9 Бусленко Н.П. Моделирование сложных систем. - М.: Наука, 1968. -356 с.

10 Вельбицкий И.В. Технология программирования. - Киев: Техника, 1984.-279 с.

11 Виттих В. А., Коварцев А.Н., Кораблин М.А. Имитация автоматизированных систем с использованием концепции состояний. - М: Известия АН СССР, Техническая кибернетика, 1981, №4

12 Воеводин В.В. Математические проблемы параллельных вычислений. // Тр. 2 Всеросс. научн. Конф. «Методы и средства обработки информ.», Изд-во МГУ, 2005. С.133-145

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

14 Гергель В.П. Теория и практика параллельных вычислений. - М.: Бином, 2007. - 423 с.

15 Гома X. иМЬ. Проектирование систем реального времени, параллельных и распределенных приложений - М.:ДМК Пресс, 2002. - 704 с.

17 Долгов Ю.Г. Метод глобальной оптимизации на основе метода ветвей и границ // Труды рабочего совещания, МКВМ-2004, 2004. С 184-192

18 Дыханов А.Е., Постовалова И.П. Десуперпозиция ациклических двухполюсных сетей // Известия Челябинского научного центра, вып. 1 (27), 2005. С. 13-18

19 Евстигнеев В.А. Применение теории графов в программировании. -М.: Наука, 1985.-352 с.

20 Евтушенко Ю.Г., Посыпкин М.А. Параллельные методы решения задач глобальной оптимизации // Труды четвертой международной конференции «Параллельные вычисления и задачи управления». М., 2008. С. 18-39.

21 Евтушенко Ю.Г., Ратькин В.А. Метод половинного деления для глобальной оптимизации функции многих переменных. // Техническая кибернетика, №1, 1987. с 119-127

22 Елсаков С.М., Ширяев В.И. Однородные алгоритмы многоэкстремальной оптимизации для целевых функций со значительным временем вычисления значения // Вычислительные методы и программирование, Т. 12, 2011. - с 48-68

23 Ершов А. П. Введение в теоретическое программирование (беседы о методе). -М.: Наука, 1977. - 288 с.

24 Жидченко В.В. Автоматизация разработки параллельных программ в технологии графо-символического программирования // Материалы второго Международного научно-практического семинара / Под ред. проф. Р.Г. Стронгина. Нижний Новгород: Изд-во Нижегородского

госуниверситета, 2002. - С. 341-347.

25 Жидченко В.В., Коварцев А.Н. Моделирование синхронных параллельных вычислений при построении математических моделей сложных систем // Первая международная конференция «Системный анализ и информационные технологии» САИТ-2005: Труды конференции. В 2т. Т.2. - М.: КомКнига, 2005. - С. 154-160

26 Иванов В.В. Методы вычислений на ЭВМ: Справочное пособие . -Киев: Наук. Думка, 1986. - 584 с.

27 Калентьев A.A., Тюгашев A.A. ИПИ/CALS технологии в жизненном цикле комплексных программ управления. - Самара: Изд-во Самарского научного цента РАН, 2006.

28 Каляев И. А., Левин И. И., Семерников Е. А., Шмойлов В. И. Реконфигурируемые мультиконвейерные вычислительные структуры: 2-е издание. Ростов н/Д: изд-во ЮНЦ РАН, 2009. 344 с

29 Канторович Л. В. О методе Ньютона для функциональных уравнений //Доклады АН СССР. 1948. 59 (7). С. 1237-1240.

30 Касьянов В. Н., Касьянова Е. В. Визуализация графов и графовых моделей. - Новосибирск: Сибирское Научное Издательство, 2010. -123 с.

31 Касьянов В.Н. "Оптимизирующие преобразования программ", М., "Наука", 1988.336 с.

32 Касьянов В.Н., Евстигнеев A.B. Графы в программировании: обработка, визуализация и применение - СПб.. БХВ Петербург, 2003. - 1104 с.

33 Касьянов В.П. Оптимизирующие преобразования программ. _ М.: Наука, 1988.-336 с.

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

35 Квасов Д.Е., Сергеев Я.Д. Многомерный алгоритм глобальной

оптимизации на основе адаптивных диагональных кривых // ЖВМ и МФ, 2003, Т.43, № 1. С. 42-59..

36 Коварцев А.Н. Автоматизация разработки и тестирования программных средств. - Самар. гос. аэрокосм, ун-т., Самара, 1999. -150 с.

37 Коварцев А.Н. Вычислительная математика: учебн. Пособие -Самара, ООО «Офорт», 2011. - 230 с.

38 Коварцев А.Н., Жидченко В.В. Методы и средства визуального параллельного программирования - Самарский государственный аэрокосмический университет, Самара, 2010. 114 с

39 Котов В.Е. Сети Петри. - М.: Наука, 1984. - 160 е..

40 Кулямин В.В. Методы верификации программного обеспечения. // http://panda.ispras.ru/~kuliamin/docs/VerMethods-2008-ru.pdf (Актуально на 17.09.2012)

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

42 Липаев В.В. Тестирование компонентов и комплексов программ // Учебник, -м.: синтег, 2010.-270с.

43 Ляпунов A.A. О логических схемах программ // Проблемы кибернетики. Вып.1.- М: Физматгиз. 1958. - С.46-74.

44 Мак-Кракен Д., Дорн У. Численные методы и программирование на ФОРТРАНе.- М.: Мир, 1977. - 585 с.

45 Маслов В.Г., Кузьмичев B.C., Коварцев А.Н., Григорьев В.А. Теория и методы начальных этапов проектирования авиационных ГТД: Учебн. пособие. // Самара, Самар. гос. аэрокосм.ун-т, 1996. - 147 с.

46 Немировский A.C., Юдин Д.Б. Сложность задач и эффективность методов оптимизации. - М.: Наука, 1979. 384 с.

47 Орлянская И.В. Современные подходы к построению методов глобальной оптимизации [Электронный журнал «Исследовано

в России», 2007, с. 189-192]:

[web-сайт] <http://zhurnal.ape.relarn.ni/articles/2002/l 89.pdf >

48 Ортега Дж., Рейиболдт В. Итерационные методы решения нелинейных систем уравнений со многими неизвестными. М.: Мир, 1975.

49 Пароджанов В.Д. Язык ДРАКОН. Краткое описание. - М., 2009. -124 с.

50 Погребной В.К. Матричный алгоритм решения задачи разрезания графов // Изв. Томского политехнического университета. Томск, 2007. Т.311.91-96 с.

51 Подловченко Р.И. От операторного метода A.A. Ляпунова - к теории алгебраических моделей программ. // Тр. 2-ой Межд. Конф. «Развитие вычислительной техники и её программного обеспечения в России и странах бывшего СССР», Великий Новгород, 2011. С.250-252

52 Поляк Б.Т. Метод Ньютона и его роль в оптимизации и вычислительной математике // Труды ИСА РАН, Т.28, 2006. С.48 - 66

53 Посыпкин М.А. Параллельный эвристический алгоритм глобальной оптимизации. // Труды ИСА РАН, 2008, Т. 32. С. 166-179

54 Рамбо Дж., Блаха М. UML 2.0. Объектно-ориентированное моделирование и разработка - 2-е изд.-СПб: Питер, 2007. 544 с,

55 Сван Т. Программирование для Windows в Borland С++. - М.: БИНОМ, 1995. -480 с.

56 Стронгин Р.Г. Численные методы в многоэкстремальных задачах (информационно-статистические алгоритмы) - М.: Наука, 1978. - 240 с.

57 Т-система с открытой архитектурой /Абрамов С.М., Адамович А.И., Ишохин A.B. и др. // Труды Международной научной конференции "Суперкомпьютерные системы и их применение. SSA'2004", 26-28 октября 2004 г. Минск, ОИПИ HAH Беларуси, С.

18-22.

58 Успенский В.А., Семенов A.JI. Теория алгоритмов: основные открытия и приложения. - М.: Наука, 1987

59 Шалыто А.А. SWITCH-технология. Алгоритмизация и программирование задач логического управления. - СПб.: Наука, 1998.-628 с.

60 Янов Ю.И. О логических схемах алгоритмов // Проблемы кибернетики. Вып.1. -М: Физматгиз. 1958. - С.75-127.

61 A. Beguelin, J. J. Dongarra, G. A. Geist, R. Manchek, and V. S. Sunderam. Graphical development tools for network-based concurrent supercomputing. // Proceedings of Supercomputing 91, pages 435-444, Albuquerque, 1991.

62 Aarts E.H.L., van Laarhoven P.J.M. Simulated Annealing: Theory and Applications // London, Kluwer, 1987

63 АН M., Storey C. Aspiration Based Simulated Annealing Algorithm // J. of Global Optimization 11, 181-191, 1996

64 Backus J. Can Programming Be Liberated from von Neuman Style? A Functional Stile and Its Algebra of Programs. - Communications of ACM. 1978, v. 21, No. 8.

65 Booch G. Object-Oriented Design. Redwood City, Calif.: Benjamin/Cammings, 1991.

66 Booch G., Jacobson I., Rumbaugh J. The Unified Modeling Language for Object-Oriented Development: Documentation Set Version 1.1. September 1997.

67 Browne J.C., Azam M., and Sobek S. CODE: A Unified Approach to Parallel Programming. - IEEE Software, July, 1989, p.l 1.

68 Di Battista G., Eades P., Tamassia R., Tollis I.G. Graph Drawing: Algorithms for Vizualization of Graphs. - Prentice Hall, 1999. - 397 p.

69 Egorov, I.N., Kretinin, G.V., Leshchenko, I.A., "Optimization Algorithms as Tools for the Solution of Inverse Problems". WCCM V, July 7... 12,

70

71

72

73

74

75

76

77

78

79

80

81

82

83

2002, Vienna, Austria.

G. Hutton Programming in Haskell. - Cambridge University Press, 2007. -184 c.

Gaviano M., Kvasov D.E., Lera D., Sergeyev Ya.D. Softwere for generation of classes of test of functions with known local and global minima for global optimization // ASM TOMS/ 2003/ 29, № 4. 469-480 Harel D. On Visual Formalisms. - CACM 31, no. 5 (May 1988): 514530.

Harel D. Statecharts: A Visual Formalism for Complex Systems. // Science of Computer Programming. - 1987. №8. C. 231-274 Herman I., Melan?on G., Marshall M. S. Graph visualization and navigation in information visualization: a survey // IEEETrans. on Visualization and Computer Graphics. - 2000. - Vol. 6. - P. 24-43. Jacobson I. Object-Oriented Software Engineering.Reading, Mass.: Addison-Wesley, 1992.

Michalewicz Z. Genetic Algorithms + Data Structures = Evolution Programs (3rd Edn.) // New York, Springer-Verlag, 1996. Miller J.M. Elementary fanction: algorithms and implementatio, Birkhauser, 1997

Moore R. Interval Analysis // New Jersey, Prentice-Hall, 1966.

Nesterov Yu. Smooth minimization of nonsmooth functions. CORE DP

2003/12. Accepted by Mathematical Programming.

Nesterov Yu., Nemirovski A. Interior-Point Polynomial Algorithms in

Convex Programming // SIAM. Philadelphia, 1994.

Nesterov Yu., Polyak B. Cubic regularization of Newton method and its

global performance // Mathematical Programming. Ser. A. 2006. 108. pp.

177-205.

Powell M.J.D. Approximation Theory and Methods, Cambridge University Press, 1981

Rinnoy Kan A.H.G., Timmer G.T. Stochastic Global Optimization

Methods // Mathematical programming, 39, 27-78, 1987.

84 Robert B. France, Sudipto Ghosh, Trung Dinh-Trong, Arnor Solberg. Model-Driven Development Using UML 2.0: Promises and Pitfalls, IEEE Computer, February 2006. IEEE Computer Society, 2006.

85 Rumbaugh J., J.M. Blaha, W. Premerlani, F. Eddy, and W. Lorenson Object-Oriented Modeling and Design. Englewood Cliffs, N.J.: Prentice Hall, 1991.

86 Simon Peyton Jones Haskell 98 language and libraries: the Revised Report. - Cambridge University Press, 2003. - 272 c.

87 StronginR.G., Sergeyev Ya.D. Global optimization with non-convex constraints. Sequential and parallel algorithms. - Dordrecht: KluwerAcademic Publishers, 2000.

88 Sturua E.G., Zavriev S.K. A Trajectory Algorithm Based on the Gradient Method. The Search on Quasioptimal trajectories // J. of Global Optimization, №1, 1991

89 Tyugu, E., Valt, R. Visual programming in NUT.// Journal of visual languages and programming. -1997. - v. 8. - C. 523 - 544.

90 Yau S.S. Generation of all Hamiltonian circuits, paths and center of a graph, and related topics // IEEE Trans. Circuit Theory. - 1967. - CT-13, № 3. - P. 79-81