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

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

Введение
1 Анализ параллельных архитектур, языковых и инструментальные средств параллельного программирования.

1.1 Архитектуры параллельных ВС.

1.1.1 системы

1.1.2 Система .

1.1.3 МРР системы

1.1.4 Кластерная архитектура.

1.3 Общие подходы к реализации исполнения ФГ1 программ

1.4 Системы, обеспечивающие параллельное выполнение на МРР и кластерных архитектурах

1.4.1 V
1.4.2 I
1.4.3 Система IX
1.4.4 Тсистема
1.5 Выбор среды для построения эмулирующей системы
Выводы по главе
2. Управление вычислениями в функциональнопотоковой модели
2.1 Описание динамики вычислений функциональнопотоковой модели .
2.2 Программоформирующис операторы.
2.2.1 Оператор интерпретации.
2.2.2 Константный оператор.
2.2.3 Оператор копирования.
2.2.4 Оператор группировки в список
2.2.5 Оператор создания параллельного списка.
2.2.6 Оператор группировки в задержанный список
2.3 Правила срабатывания операторов
2.4 Влияние эквивалентных преобразований на формирование информационноуправляющего графа.
Выводы по главе 2.
3. Анализ и разработка методов выполнения функциональнопараллельных программ
3.1 Способы реализации системы исполнения функциональнопараллельных программ
3.2 Организация процесса интерпретации ФП программ.
3.2.1 Методы последовательного выполнения ФП программ.
3.2.2 Методы параллельного выполнения ФП программ.
Выводы по главе 3.
4 Разработка инструментальной системы для выполнения функциональнопараллельных программ на кластерной архитектуре.
4.1 Реализация последовательнопараллельного интерпретатора с использованием системы динамического распараллеливания М1Х.
4.1.1 Структура интерпретатора
4.1.2 Описание входного представления.
4.1.4 Алгоритм параллельной интерпретации
4.1.5 Алгоритм эквивалентных преобразований списков
4.1.6 Описание протокола взаимодействия процессов при передаче результатов
4.1.7 Описание входных параметров командной строки интерпретатора.
4.2 Оценка интерпретации ФПП
4.3 Методы повышения эффективности интерпретации
4.3.1 Оценка вычислительной сложности интерпретируемой функции
Выводы по главе
Заключение.
Список использованных источников
Приложение А Функциональный язык параллельного программирования
Пифагор
Л.1 Используемый метаязык
А.2 Элементарные конструкции.
А.2.1 Разделители.
А.2.2 Комментарии.
А.2.3 Идентификаторы
А.2.4 Зарезервированные слова.
А.З Обозначения
А.4 Объекты
А.5 Сигналы
А.6 Значащие величины константы
Л.8 Функция
и А.9 Блок.
А. Выражение
А. Структура программы
А. Предопределенные функции и данные.
А. Использование предопределенных типов
А. Пользовательские типы.
Л. Правила эквивалентных преобразований.
Приложение В Примеры реализации функций на языке Пифагор
Введение
Параллельное программирование является достаточно трудоемким процессом. Необходимо заниматься не только поиском эффективных алгоритмов решения прикладных задач, но и увязывать их с существующими параллельными вычислительными системами ПВС, каждая из которых обладает своими особенностями 1. Кроме того, существенным отличием такого программирования от последовательного является еще и многообразие вариантов исполнения параллельной программы, в котором легко скрываются ошибки, связанные с последовательностью исполнения параллельных фрагментов программ. Программист должен обеспечивать синхронизацию процессов, отслеживать возникновение проблем с общими ресурсами и т.п. При этом не существует никаких гарантий того, что при переходе на другую параллельную архитектуру не придется заново переписывать программный код. В связи с этим построение таких программ является почти искусством, где вс зависит от степени подготовленности специалиста.
Исторически разнообразие архитектур породило множество методов написания параллельных программ. Во многом эго было обусловлено тем, что языки программирования непосредственно разрабатывались под особенности ПВС. Такой подход, несмотря на эффективное решение задач на конкретных архитектурах, привел к проблемам переноса программного обеспечения. Появление неоднородных систем еще более усложняет этот процесс. Соответственно не всякий инструмент, обеспечивающий
эффективность и переносимость в рамках одной архитектуры, также поддерживает аналогичную эффективность и переносимость для другой. Действительно, если некоторые инструмент позволяет комуто написать переносимое приложение, хорошо оптимизируемое для отдельной представленной архитектуры, это не означает, что оно будет эффективно выполняться на любой другой системе без изменения исходного кода 2.
Попытки создания инструментальных средств, обеспечивающих переносимость параллельных программ, предпринимались неоднократно и осуществлялись по нескольким направлениям. Все они, тем или иным образом, связаны с написанием программ для некоторой обобщенной архитектуры. Выполнение подобных программ на конкретной ПВС осуществляется после их предварительного преобразования с использованием специализированных средств распараллеливания десеквенторов 3.
Существуют различные варианты классификации методов десеквенции программ. Одним из них является деление по способам представления исходного параллелизма 4, 5, 6,
1. использование последовательного программирования с дальнейшим автоматическим распараллеливанием разработанных программ
2. применение языков программирования, обеспечивающих непосредственное описание любых потоков параллельного управления, по сути являющихся расширениями традиционных последовательных языков за счет добавления разнообразных примитивов распараллеливания и синхронизации, при этом уровень параллелизма полностью контролируется разработчиком и может задаваться в зависимости от конкретных условий 9, . Дссеквснция подобных программ является переводом одной параллельной формы в другую
3. опора на языки, неявным образом описывающие максимальный параллелизм, что обеспечивается заданием только информационных связей. Предполагается, что программа будет рассчитана на выполнение в виртуальной машине с неограниченными ресурсами, а запуск операторов будет происходить по готовности их данных. Адаптация программы к конкретной ПВС обычно осуществляется путем сжатия параллелизма с учетом ресурсных и архитектурных ограничений.
Каждый из подходов в настоящее время представлен семейством соответствующих инструментальных средств.
В данной работе исследуются методы разработки и выполнения функциональнопараллельных программ. Рассматривается функциональнопотоковый язык программирования, неявным образом описывающий максимальный параллелизм задачи, позволяющий соответственно
создавать мобильные программы с параллелизмом на уровне операторов, ограниченным лишь методом решения задачи
обеспечивать перенос программы на конкретную архитектуру, не распараллеливая программу, а сжимая ее максимальный параллелизм
проводить оптимизацию программы но множеству параметров с учетом специфики архитектуры ВС, для которой осуществляется трансляция без учета управляющих связей программы.
Основной упор делается на исследование общих принципов построения и использования исполняемой среды на кластерной архитектуре и создание средств выполнения функциональнопараллельных ФП программ.
Актуальность


Обосновывается выбор средств, для организации интерпретации функциональнопараллельных программ. Во второй главе предлагается модель, описывающая поведение ФП программ, построенных на основе функциональнопотоковой модели вычислений. Функциональнопотоковая модель задает программу в виде информационного графа, обладающего рядом специфических особенностей. В основе лежит управление по готовности данных, определяемое для процессов, протекающих внутри бесконечных ресурсов. Основной акцент делается на описание динамики поведения функциональнопотоковых программ, построенных на основе рассматриваемой модели. При описании используется информационноуправляющая ресурсная модель , , 6, задающая динамику вычислений. В модели вычислений используется представление вычислительного процесса в виде суперпозиции трех графов информационного, управляющего и ресурсного. Исходя из того, что в функциональнопотоковой модели вычислений управление ресурсами осуществляется неявно, ресурсный граф из рассмотрения исключается, и основной акцент делается на описание только информационноуправляющей составляющей. На основании анализа управления узлами ФП модели вычислений предлагаются методы наложения управляющих воздействий, обеспечивающих неявное управление вычислениями на основе заданного информационного графа. Далее, определяются принципы преобразования информационно графа в информационноуправляющий. Для каждого из узлов модели предлагаются алгоритмы функционирования. В третьей главе рассматривается методы построения виртуальной машины, обеспечивающей выполнение функциональнопараллельных программ, и ее отображение на вычислительную среду. Рассматриваются методы последовательного и параллельного исполнения функциональнопараллельных программ. Исследуются пути повышения производительности интерпретации функциональнопараллельных программ. Предлагается вариант применения интерпретирующей системы в случае использования ФП языка для написания управляющих командных файлов скриптов, обеспечивающих контроль и запуск параллельных программ на кластерной архитектуре. В четвертой главе рассматривается один из вариантов реализации экспериментальной системы интерпретации функциональнопараллельных программ, реализованный на базе кластерной архитектуры под управлением ОС 1лпих с поддержкой системы динамического распараллеливания М1Х. Интерпретатор реализует виртуальную машину с трехуровневой архитектурой и является составной частью технологической цепочки, обеспечивающей выполнение функциональных параллельных программ. ФП языка программирования. Система позволила провести анализ эффективности разработанной трехуровневой модели виртуальной машины. Полученные результаты показали способность такой системы обеспечивать сбалансированную загрузку узлов кластера. Приложение Л содержит описание функционального языка параллельного программирования ПИФАГОР. В Приложении В приведен полный листинг программ, используемых но тексту диссертации. Работа изложена на 9 страницах, содержит рисунка и 4 таблицы. Список литератгры включает 5 наименований. В главе проводится анализ архитектур параллельных вычислительных систем ПВС, на основании которого обосновывается выбор системы для проведения исследований по созданию среды выполнения функциональнопараллельных программ. Одним из основных критерием выбора является масштабируемость ПВС. Формулируются подходы к исполнению функциональнопараллельных программ. Делается вывод о предпочтении реализации эмулирующей среды для проведения исследований модели вычисления и функциональнопараллельного языка программирования. Для выбранной архитектуры анализируются библиотеки и инструментальные средства, реализующие различные стратегии управления распределенными вычислениями. Обосновывается выбор используемых средств, для организации интерпретации функциональнопараллельных программ. В соответствии с классификацией вычислительных систем по наличию общей или распределенной оперативной памяти, различают следующие основные классы аппаратных архитектур параллельных вычислительных систем , МРР, кластерная и 1, , , , , , , , , .