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

• Автор: Казаков, Фёдор Александрович
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2003
• Место защиты: Красноярск
• Количество страниц: 170 с. : ил.

Содержание
Введение.

1 Анализ принципов разработки мобильного параллельного программного обеспечения1

1.1 Вопросы управление в параллельном программировании.

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

1.2.1 Язык функционального программирования .

1.2.2 Функциональный язык программирования

1.2.3 Функциональный язык параллельного программирования i.

1.3 Управление вычислениями по готовности данных

1.3.1 Система программирования .

1.3.2 Система программирования и язык потоков данных

1.4 Общее состояние языков параллельного программирования
Выводы по главе 1.
2 Функциональнопотоковая модель параллельных вычислений
2.1 Общие принципы организации модели
2.2 Программоформирующие операторы
2.3 Описание динамики функционирования.
2.3.1 Правила межоператорных переходов
2.3.2 Правила срабатывания программоформирующих операторов .
2.4 Эквивалентные преобразования.
Выводы по главе 2.
3 Функциональный язык параллельного программирования
3.1 Используемый метаязык
3.2 Элементарные конструкции.
3.2.1 Разделители.
3.2.2 Комментарии.
3.2.3 Идентификаторы
3.2.4 Зарезервированные слова.
3.3 Обозначения
3.4 Объекты
3.5 Сигналы
3.6 Значащие величины константы
3.6.1 Целые константы.
3.6.2 Действительное число
3.6.3 Символьные константы
3.6.4 Логическая константа
3.6.5 Специальные знаки.
3.6.6 Константы ошибок
3.7 Составные объекты
3.8 Функция
3.8.1 Организация обычной функции.
3.9 Блок.
3. Выражение
3. Структура программы
3. Предопределенные функции и данные
31 Использование специальных знаков
32 Использование данных
33 Использование специальных функций.
3. Использование предопределенных типов.
3. Правила эквивалентных преобразований.
Выводы по главе 3.
4 Реализация среды исполнения программ
4.1 Последовательная интерпретация функциональнопараллельных
программ
4.1.1 Транслятор
4.1.2 Интерпретатор.
4.1.3 Модуль управления.
4.2 Примеры программ на ФЯПП
4.2.1 Использование параллельного списка аргументов
4.2.2 Использование параллельного списка функций.
4.2.3 Использование задержанных списков
4.2.4 Использование параллельной рекурсии
4.2.5 Использование функций в качестве параметров
4.2.6 Программа умножения двух матриц
Выводы по главе 4.
5 Применение функциональнопотокового языка для анализа и синтеза алгоритмов
5.1 Реализация основных программных конструкций.
5.1.1 Реализация последовательного выполнения
5.1.2 Альтернатива.
5.1.3 Итерация.
5.2 Использование максимального параллелизма для анализа параллельных алгоритмов с заданными ограничениями.
5.2.1 Теоретическая сортировка.
5.2.2 Вывод ограниченных алгоритмов
5.3 Эквивалентные функциональные преобразования с использованием обобщенных функций
5.4 Использование разных форм одной и той же функции для повышения
эффективности вычислений
Выводы по главе 5.
Заключение
Литература


Входные данные (I;) определяют исходный информационный набор необходимый для выполнения процесса; выходные данные () - набор, формируемый к моменту завершения процесса. Возникновение разрешающего состояния для каждой связи процесса, как информационной, так и ресурсной, должно сопровождаться формированием соответствующего управляющего сигнала. При наличии всех разрешающих сигналов процесс может и должен выполняться. Всего определенно три класса управляющих сигналов: сигналы, определяющие готовность всех типов вычислительных ресурсов; сигналы, регулирующие информационное взаимодействие с другими процессами; сигналы, задающие следование одного процесса за другими, последовательность выполнения элементарных процессов. Одной из характеристик МПВ является методы формирования управляющих сигналов при выполнении программ. ПВС обеспечивает корректное выполнение. Неявный метод управления может поддерживаться двумя способами: с отсутствием сигналов управления и с автоматическим формированием таких сигналов на уровне функций ПВС. При отсутствии сигналов предполагается, что независимо от состояния системы на момент выполнения процесса все условия готовности будут соблюдены. Это возможно в том случае, если при описании алгоритма вводятся некоторые дополнительные ограничения, например: переменные можно использовать только после их инициализации. Автоматическое формирование сигналов готовности осуществляется непосредственно исполняющей ВС. И тот и другой метод на уровне языка программирования неотличим и не требует от программиста дополнительного определения сигналов управления. Классический императивный стиль программирования в последовательном варианте предполагает наличие единственной нити передачи управления. Вышестоящий по тексту оператор выполняется ранее нижестоящего [, ]. Для изменения «последовательности по умолчанию» необходимо введение дополнительных операторов задания управления. При этом последовательность выполнения ни как не анализирует готовность вычислительных ресурсов и готовность информационных ресурсов. Предполагается наличие единственного набора вычислительных ресурсов и он «всегда готов»; в этом случае управляющий сигнал формируется ВС. Для информационных ресурсов управляющих сигналов не формируется, считается, что сама последовательность операторов обеспечивает их корректность использования. Императивное программирование можно представить как автомат, который последовательно изменяет свои состояния под управлением некоторой схемы переходов. При разработке параллельных программ на основе императивного стиля с явным определением управления основное внимания уделяется описанию порядка синхронизации между отдельными нитями вычислений. В языки вводятся дополнительные конструкции, обеспечивающие распараллеливание последовательных ветвей и их синхронизацию. Процесс описывается как совокупность явных директив управления вычислениями. Условно можно выделить два направления развития языковых конструкций в рамках императивного стиля: создание специализированных языков, с примитивами управления на уровне синтаксиса, и наборы библиотечных процедур, как параллельное расширение существующих универсальных языков. Развитие инструментальных средств программирования сильно связанно с архитектурными решениями. Создавались языки предназначенные для использования только на одной ПВС. Например, язык Occam [, ] был создан для создания программ на транспьютерных системах. Средства поддержки параллелизма на уровне передачи сообщений и механизмов явной синхронизации были предусмотрены в языке ADA [, ]. Так, язык HPF [] (высокопроизводительный FORTRAN) был создан для разработки программ на. Разработчики добавили стандартный язык дополнительными средствами распределения данных и вычислений по узлам ПВС. При появлении архитектур с общей памятью (SMP) были созданы ряд программных систем [, , , ] и адаптирован HPF. Так же была разработана библиотека ОрепМР []. Она представляет собой набор директив, которые позволяют преобразовать программы на стандартных языках Fortran, С, C++ до параллельной версии.