Языковая и инструментальная поддержка функционально-потокового параллельного программирования

• Автор: Привалихин, Денис Викторович
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2004
• Место защиты: Красноярск
• Количество страниц: 154 с.

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

1.1 Разработка параллельных программ с использованием

функциональной парадигмы программирования

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

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

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

1.5 Язык .

1.6 Функциональный язык параллельного программирования Пифагор

1.7 Выводы по главе 1.

2 Языковые конструкции, расширяющие функциональные возможности языка параллельного программирования Пифагор.
2.1 Система типизации, строгого контроля типов и введение типов,
определяемых пользователем.
2.1.1 Работа с альтернативами в языках с динамической типизацией .
2.1.2 Пользовательские типы
2.2 Перегрузка функций с одинаковой сигнатурой
2.3 Определение функции с предусловием и постусловием.
2.4 Возврат задержанных списков в качестве результата вычисления
функций
2.5 Модульное построение программ на языке Пифагор
2.6 Использование функций, написанных на других языках
программирования, расположенных во внешних модулях.
2.7 Выводы по главе 2.
3 Использование расширений функционального языка параллельного программирования Пифагор.
3.1 Использование перегруженных функций с одинаковой сигнатурой
для обработки альтернативных ветвей алгоритмов.
3.2 Применение типов, определяемых пользователем и перегруженных
функций для описания обобщнных типов
3.3 Применение предусловий и постусловий
3.4 Использование задержанных списков, возвращаемых в качестве
результата вычисления функции
3.5 Выводы по главе 3.
4 Инструментальная поддержка функциональнопотокового параллельного программирования.
4.1 Структура блока трансляцииинтерпретации программ на ФЯПП
4.2 Структура транслятора.
4.2.1 Лексический анализатор или сканер
4.2.2 Синтаксический анализатор.
4.3 Структура интерпретатора для последовательной интерпретации
программ на функциональном языке параллельного программирования Пифагор
4.3.1 Интерпретация объектов , i и ТВ
4.3.2 Интерпретация объекта xi.
4.3.3 Интерпретация объектов Т и
4.3.4 Интерпретация объекта i.
4.3.5 Интерпретация объекта I.
4.3.6 Оператор интерпретации
4.4 Интегрированная среда разработки программ на ФЯПП.
4.4.1 Текстовый редактор
4.4.2 Панель инструментов и управление транслятором и
интерпретатором
4.5 Разработка инструментальной системы для выполнения функциональнопараллельных программ на кластерной архитектуре
4.5.1 Реализация последовательнопараллельного интерпретатора с использованием системы динамического распараллеливания М1Х
4.5.2 Описание входного представления.
4.6 Выводы по главе 4
Заключение
Список использованных источников


В третьей главе примеры разработки программ с использованием предлагаемых конструкций и эквивалентность различных подходов для решения тех или иных задач. В четвертой главе дается описание инструментальной среды трансляции и интерпретации программ, включая подробное описание работы последовательного интерпретатора и описание интегрированной среды разработки. В приложении приведено полное описание языка с учётом новых конструкций (приложение 1). Работа изложена на 8 страницах, содержит рисунков. Список литературы включает 6 наименований. Разработка параллельных программ с использованием функциональной парадигмы программирования. Использование функциональной парадигмы для создания параллельных языков программирования дает несколько существенных преимуществ. Изначально, на уровне модели, все функциональные языки явно не определяют последовательность передачи управления между функциями. Функциональная программа представляет собой набор определений функций, одна из которых, является стартовой. Функции определяются через другие функции или рекурсивно - через себя. В качестве входных параметров функции принимают результаты вычисления других функций []. В процессе выполнения программы, функции получают параметры, вычисляют и возвращают результат, в случае необходимости вычисляя значения других функций. Каждый вызов возвращает некоторое значение в вызвавшую его функцию, вычисление которой после этого продолжается; этот процесс повторяется до тех пор, пока запустившая вычисления функция не вернет конечный результат пользователю. Передача управления, активизация функции, определяется не явно, а необходимостью получения результата вычисления какой-либо из функций. В отличие от императивного программирования, когда программы описывают процесс последовательного, пошагового решения задачи с четко заданным процессом передачи управления []. Современные функциональные языки позволяют писать мощные и, в то же время, компактные программы. Использование параллелизма было реализовано в одной из версий Haskell [] и в схожем языке программирования Clean []. Sisall [, ]. Язык Haskell является современным развитием языков редукции графов. Программа определяет информационный граф программы и варианты его расширения при вызове функций. В качестве основных характеристик нужно отметить «чисто» функциональный стиль и использование механизма «ленивых» вычислений [, ]. Для организации параллельных вычислений в язык введены две конструкции, обеспечивающие явное управление. Комбинатор par, получает два параметра, являющиеся параллельно выполняемыми функциями. Выражение р 'par' е имеет значение, определяемое е. Помимо этого, конструкция указывает на то, что р может быть выполнен новой нитью, параллельной с родительской нитью, продолжающей выполнение е. Специфика языка, поддерживающего «ленивые» вычисления накладывает свою специфику на параллелизм. Считается, что функция р может быть выполнена тогда, когда потребуется результат ее вычисления. В этом случае будет создана дополнительная нить, осуществляющая поддержку параллельного процесса. Для синхронизации ранее инициированных параллельных вычислений введен оператор последовательной композиции, seq. Если el - не пустая конструкция, то выражение el 'seq' е2 имеет значение е2; иначе результат -«пустое значение». Декларируется, что конструкция el должна быть обработана перед возвратом результата е2. В качестве примера, использующего эти конструкции, рассмотрим вычисление числа Фибоначчи по заданному его порядковому номеру. Тело функции определенно как две альтернативы: если входной параметр п меньше либо равен единицы, то возвращается 1; во всех остальных случаях порождается параллельная ветвь для вычисления п-1, вычисляется п-2, а затем их сумма. Подобный прием можно использовать и для обработки списков. Простейшее преобразование функции быстрой сортировки quicksort. Делается попытка создавать две нити, каждая из которых должна осуществлять сортировку своего подсписка: одна нить сортирует значения меньшие чем первый элемент списка, а другая - большие, либо равные ему.