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

• Автор: Редькин, Андрей Владимирович
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2009
• Место защиты: Красноярск
• Количество страниц: 135 с. : ил.

Оглавление
Введение.

1 Динамические параллельные вычисления на основе асинхронных списков.

1.1 Iсети для описания асинхронных вычислений.

1.2 Асинхронные вычисления в схемах потока данных Денниса.

1.3 Асинхронные списки в языке Пифагор

1.4 Использование асинхронных списков для управления параллельными вычислениями.

1.4.1 Конвейерное взаимодействие асинхронных функций.

1.5 Использование асинхронного списка в алгоритмах сортировки.

1.5.1 Асинхронная сортировка перебором.

1.5.2 Быстрая асинхронная сортировка.

1.6 Расширение возможностей языка Пифагор дополнительными встроенными функциями
1.6.1 Операция i
1.6.2 Операция x
1.6.3 Операция
1.6.4 Операция .
1.6.5 Операции и .
1.7 Операция прямой интерпретации в языке Пифагор.
1.8 Выводы
2 Организация управления вычислениями в функциональнопотоковых параллельных программах.
2.1 Методы организации потоковых параллельных вычислений
2.1.1 Организация вычислений в языке i.
2.1.2 Организация потоковой вычислительной системы с использованием императивных языков программирования
2.1.3 Управление в модели функциональнопотоковых параллельных вычислений на основе информационного и управляющего графов
2.2 Информационный граф функциональнопотоковой параллельной программы.
2.3 Управляющий граф функциональнопотоковой параллельной прсираммы
2.3.1 Генератор сигнала.
2.3.2 Смеситель сигналов
2.3.3 Асинхронный смеситель сигналов
2.3.4 Интерпретатор сигналов
2.3.5 Синхронизатор сигналов
2.3.6 Управление вычислениями в задержанных подграфах.
2.4 Формирование управляющего графа.
2.5 Реализация стратегий управления посредством преобразования управляющих графов
2.6 Выводы
3 Событийный процессор для функциональнопотоковых параллельных вычислений
3.1 Внутренние представления графов и данных
3.1.1 Внутреннее представление информационного графа
3.1.2 Представление констант и данных.
3.1.3 Внутреннее представление функции
3.1.4 Внутреннее представление управляющего графа.
3.2 Структура событийного процессора
3.2.1 Структура события.
3.2.2 Событийное управление для параллельных списков
3.2.3 Поток событий.
3.2.4 Событийное управление для задержанных списков.
3.3 Параллельные вычисления с использованием событийного процессора. .
3.4 Выводы
4 Инструментальная поддержка разработки параллельных программ на языке Пифагор.
4.1 Общая структура системы.
4.2 Модель данных системы.
4.3 Транслятор.
4.4 Хранение информационных, управляющих графов и вспомогательных структур данных..
4.5 Использование внешних функций
4.6 Визуализация графов
4.7 Реализация возможностей отладки программ.
4.7.1 Отладка в режиме трассировки событий.
4.8 Интерфейс пользователя.
4.8.1 Среда доступа к хранилищу функций и графов.
4.8.2 Графический интерфейс событийного отладчика программ.
4.9 Выводы
Заключение.ИЗ
Список используемых источников


Разработан событийный процессор, обеспечивающий повышение эффективности асинхронного управления выполнением функциональнопотоковых параллельных программ за счет обработки событий, задаваемых управляющим графом. Предложена архитектура инструментальной системы, обеспечивающей трансляцию и архитектурно-независимую отладку функциональнопотоковых параллельных программ. Методы исследования. В диссертационной работе использовались методы и понятия теории графов, теории алгоритмов, элементы теории множеств, теории языков и формальных грамматик. Для описания синтаксиса языка программирования использовались расширенные формы Бэкуса-Наура (РБНФ), диаграммы Вирта. В экспериментальной части работы применялись методы синтаксического анализа и компиляции. Практическая значимость. На основе разработанной архитектуры реализована инструментальная система функционально-потокового параллельного программирования, обеспечивающая трансляцию, отладку и выполнение функциональнопотоковых параллельных программ с применением предложенных подходов к организации функционально-потоковых параллельных вычислений. Полученные научные и практические результаты использованы в учебном процессе по дисциплинам «Технология программирования» и «Модели параллельных вычислений» в ФГОУ НПО «Сибирский федеральный университет». Апробация работы. Параллельные вычислительные технологии (ПаВТ'), Нижний Новгород. Сведения о внедрении. Результаты работы использованы при выполнении: научно-методического проекта Сибирского Федерального университета № «Решение некоторых задач прикладной математики и информатики для повышения потенциала образовательного процесса»; проекта Сибирского Федерального университета «Использование технологий параллельной обработки в научной, образовательной и организационной деятельности»; проекта № «Среда разработки для языка параллельного программирования Пифагор» в рамках «Программы развития СФУ па - годы». Программный комплекс «Инструментальная система поддержки программирования на языке Пифагор с возможностями визуализации» используется в учебном процессе, что подтверждено актами внедрения. Публикации. По теме диссертации опубликовано девять научных работ, из которых одна статья в издании, рекомендуемом ВАК. Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и трех приложений. Робота содержит 9 страниц основного текста, рисунков и 6 таблиц. Список литературы содержит 0 наименований. В первой главе приведен обзор моделей параллельных вычислений, в ходе которого анализируются реализованные в них механизмы управления асинхронными вычислениями. Предлагается расширение модели вычислений языка программирования Пифагор за счет применения асинхронных списков. Представленный механизм описания асинхронных вычислений предоставляет в распоряжение программиста дополнительные алгоритмические средства для создания функционально-потоковых параллельных программ. Асинхронные списки обеспечивают конвейеризацию вычислений и, в том числе, могут динамически выстраивать в конвейер функции программы. Программирование при помощи асинхронных списков позволяет задавать динамический параллелизм, зависящий от соотношения времени, затрачиваемого на выполнение операций, и времени, затрачиваемого на передачу данных. Рассмотрены возможности применения асинхронных списков для решения задач сортировки различными методами. Показано, что при их использовании осуществляется динамическое изменение параллелизма алгоритма решения задачи. На основе анализа функционально-потоковых параллельных программ предложены дополнительные операции, расширяющие язык функциональнопотокового параллельного программирования. Предложенные языковые средства позволяют создавать более эффективные архитектурно-независимые параллельные алгоритмы. Во второй главе предлагается подход к организации асинхронного управления функционально-потоковыми параллельными вычислениями, основанный на разделении информационного и управляющего графов программы. При трансляции функционально-потоковых параллельных программ осуществляется их преобразование в информационный и управляющий графы.