Содержание к диссертации
Введение
1 Анализ параллельных архитектур, языковых и инструментальные средств параллельного программирования 15
1.1 Архитектуры параллельных ВС 15
1.1.1 SMP-системы 15
1.1.2 Система NUMA 18
1.1.3 МРР системы 19
1.1.4 Кластерная архитектура 22
1.3 Общие подходы к реализации исполнения ФП программ 2S
1.4 Системы, обеспечивающие параллельное выполнение на МРР и кластерных архитектурах 29
1.4.1 PVM 31
1.4.2 MPI 33
1.4.3 Система MOSIX 36
1.4.4 «Т-система» 38
1.5 Выбор среды для построения эмулирующей системы 40
Выводы по главе 1 41
2. Управление вычислениями в функционально-потоковой модели 43
2.1 Описание динамики вычислений функционально-потоковой модели.43
2.2 Программо-формиругощие операторы 47
2.2.1 Оператор интерпретации 47
2.2.2 Константный оператор 50
2.2.3 Оператор копирования 50
2.2.4 Оператор группировки в список 52
2.2.5 Оператор создания параллельного списка 53
2.2.6 Оператор группировки в задержанный список 56
2.3 Правила срабатывания операторов 63
2.4 Влияние эквивалентных преобразований на формирование информационно-управляющего графа 65
Выводы по главе 2 67
3. Анализ и разработка методов выполнения функционально-параллельных программ 68
3.1 Способы реализации системы исполнения функционально-параллельных программ 68
3.2 Организация процесса интерпретации ФП программ 71
3.2.1 Методы последовательного выполнения ФП программ 73
3.2.2 Методы параллельного выполнения ФП программ 77
Выводы по главе 3 91
4 Разработка инструментальной системы для выполнения функционально-параллельных программ на кластерной архитектуре 92
4.1. Реализация последовательно-параллельного интерпретатора с использованием системы динамического распараллеливания MOSIX 93
4.1.1 Структура интерпретатора 93
4.1.2 Описание входного представления 94
4.1.4 Алгоритм параллельной интерпретации 101
4.1.5 Алгоритм эквивалентных преобразований списков 104
4.1.6 Описание протокола взаимодействия процессов при передаче результатов 104
4.1.7 Описание входных параметров командной строки интерпретатора 106
4.2 Оценка интерпретации ФПП 107
4.3 Методы повышения эффективности интерпретации 112
4.3.1 Оценка вычислительной сложности интерпретируемой функции 113
Выводы по главе 4 115
Заключение 116
- Системы, обеспечивающие параллельное выполнение на МРР и кластерных архитектурах
- Влияние эквивалентных преобразований на формирование информационно-управляющего графа
- Методы последовательного выполнения ФП программ
- Описание протокола взаимодействия процессов при передаче результатов
Введение к работе
Параллельное программирование является достаточно трудоемким процессом. Необходимо заниматься не только поиском эффективных алгоритмов решения прикладных задач, но и увязывать их с существующими параллельными вычислительными системами (ПВС), каждая из которых обладает своими особенностями [1]. Кроме того, существенным отличием такого программирования от последовательного является еще и многообразие вариантов исполнения параллельной программы, в котором легко скрываются ошибки, связанные с последовательностью исполнения параллельных фрагментов программ. Программист должен обеспечивать синхронизацию процессов, отслеживать возникновение проблем с общими ресурсами и т.п. При этом не существует никаких гарантий того, что при переходе на другую параллельную архитектуру не придется заново переписывать программный код. В связи с этим построение таких программ является почти искусством, где всё зависит от степени подготовленности специалиста.
Исторически разнообразие архитектур породило множество методов написания параллельных программ. Во многом это было обусловлено тем, что языки программирования непосредственно разрабатывались под особенности ПВС. Такой подход, несмотря на эффективное решение задач на конкретных архитектурах, привел к проблемам переноса программного обеспечения. Появление неоднородных систем еще более усложняет этот процесс. Соответственно не всякий инструмент, обеспечивающий эффективность и переносимость в рамках одной архитектуры, также поддерживает аналогичную эффективность и переносимость для другой. Действительно, если некоторые инструмент позволяет кому-то написать переносимое приложение, хорошо оптимизируемое для отдельной представленной архитектуры, это не означает, что оно будет эффективно выполняться на любой другой системе без изменения исходного кода [2].
Попытки создания инструментальных средств, обеспечивающих переносимость параллельных программ, предпринимались неоднократно и осуществлялись по нескольким направлениям. Все они, тем или иным образом, связаны с написанием программ для некоторой обобщенной архитектуры. Выполнение подобных программ на конкретной ПВС осуществляется после их предварительного преобразования с использованием специализированных средств распараллеливания (десеквенторов) [3].
Существуют различные варианты классификации методов десеквенции программ. Одним из них является деление по способам представления исходного параллелизма [4, 5, б, 7]:
1. использование последовательного программирования с дальнейшим автоматическим распараллеливанием разработанных программ [8];
2. применение языков программирования, обеспечивающих непосредственное описание любых потоков параллельного управления, по сути являющихся расширениями традиционных последовательных языков за счет добавления разнообразных примитивов распараллеливания и синхронизации, при этом уровень параллелизма полностью контролируется разработчиком и может задаваться в зависимости от конкретных условий [9, 10]. Десеквенция подобных программ является переводом одной параллельной формы в другую;
3. опора на языки, неявным образом описывающие максимальный параллелизм, что обеспечивается заданием только информационных связей. Предполагается, что программа будет рассчитана на выполнение в виртуальной машине с неограниченными ресурсами, а запуск операторов будет происходить по готовности их данных. Адаптация программы к конкретной ПВС обычно осуществляется путем сжатия параллелизма с учетом ресурсных и архитектурных ограничений.
Каждый из подходов в настоящее время представлен семейством соответствующих инструментальных средств.
В данной работе исследуются методы разработки и выполнения функционально-параллельных программ. Рассматривается функционально-потоковый язык программирования, неявным образом описывающий максимальный параллелизм задачи, позволяющий соответственно: создавать мобильные программы с параллелизмом на уровне операторов, ограниченным лишь методом решения задачи [11]; обеспечивать перенос программы на конкретную архитектуру, не распараллеливая программу, а сжимая ее максимальный параллелизм; проводить оптимизацию программы по множеству параметров с учетом специфики архитектуры ВС, для которой осуществляется трансляция без учета управляющих связей программы.
Основной упор делается на исследование общих принципов построения и использования исполняемой среды на кластерной архитектуре и создание средств выполнения функционально-параллельных (ФП) программ.
Актуальность этого направления обуславливается следующими причинами.
Развитие современных суперкомпьютеров привело к появлению параллельных архитектур, предусматривающих высокую степень распараллеливания и теоретически предоставляющих разработчикам возможность добавлять неограниченное число процессоров [12], с другой стороны в настоящее время более 30 % высокопроизводительных систем реализованы на смешанных архитектурах и прослеживается тенденция к росту неоднородных систем в будущем. Соответственно, возникает дисбаланс между возможностями архитектуры и возможностями программного обеспечения. Можно утверждать, что существует необходимость в создании таких средств параллельного программирования, которые бы с одной стороны обеспечивали бы возможность реализовать максимальный параллелизм задачи, а с другой обладали бы свойством переносимости и соответственно избавили бы программистов от необходимости всякий раз переписывать программный код при переносе программного обеспечения на изменившуюся архитектуру ПВС.
Одним из направлений по решению проблемы переносимости параллельных программ является создание функциональных языков [13, 14, 15, 16] параллельного программирования, в которых выполнение каждого оператора осуществляется по готовности его данных. Они не требуют явного описания параллелизма задачи. Достаточно указать информационную взаимосвязь между функциями, осуществляющими преобразование данных.
Разработанный на основе функционально-потоковой модели вычислений язык функционально-параллельного программирования [17, 18, 19, 20, 21] относится именно к этому направлению.
Развитие языка диктует необходимость в создании систем программирования, обеспечивающих разработку функционально-параллельных программ и их выполнение на ПВС.
В работе предлагается модель, описывающая динамику поведения ФП программ, построенных на основе функционально-потоковой модели вычислений [22, 23, 24, 25, 26], Демонстрируются разработанные обобщенные алгоритмы функционирования базовых операторов модели. Исследуются методы выполнения ФП программ, на основании которых предлагаются различные стратегии управления функционально-потоковыми вычислениями.
Целью работы является исследование средств и методов выполнения функционально-потоковых параллельных программ.
В рамках поставленной цели решаются следующие основные задачи: разработка модели, описывающей динамику поведения ФП программ, построенных на базе функционально-потоковой модели вычисления; разработка обобщенных алгоритмов функционирования узлов модели; исследование и разработка методов построения виртуальной машины, обеспечивающей выполнение функционально-параллельных программ, и ее отображения на вычислительную среду.
В работе получены следующие научные результаты.
Предложена модель, описывающая поведение функционально-параллельных программ, построенных на основе функционально-потоковой модели параллельных вычислений. Разработаны обобщенные алгоритмы выполнения предопределенных операций функционально-потоковой модели вычислений.
Предложена многоуровневая архитектура параллельной виртуальной машины обеспечивающей выполнение ФП программ. Предложен механизм отображения методов интерпретации ФП программ на ОС Linux с поддержкой системы MOSIX [27] в соответствии многоуровневой архитектурой параллельной виртуальной машины. В рамках развития функционального языка параллельного программирования предложены предопределенные функции, обеспечивающие параллельное выполнение независимых модулей (программ), позволяющих реализовать крупноблочное распараллеливание.
К практическим результатам работы следует отнести.
Разработан последовательный интерпретатор, обеспечивающий выполнение и отладку функциональных параллельных программ. Разработан параллельный интерпретатор, обеспечивающий выполнение функциональных параллельных программ на кластерных системах, одно-и многопроцессорных архитектурах под управлением ОС Linux с поддержкой системы динамического распараллеливания MOSIX [27]. Для проведения экспериментов на базе учебных компьютерных классов создана кластерная система под управлением ОС Linux RedHat с поддержкой MOSIX и MPI [28, 29], позволившая провести работы по созданию и отладке параллельного интерпретатора, а также провести оценочные эксперименты параллельной интерпретации ФП программ. Реализованы методы переноса ФП программ на последовательную и кластерную архитектуры. Методы основаны на сжатии максимального параллелизма задачи за счет изменения стратегии управления вычислениями.
На защиту выносятся: модель, описывающая динамику поведения функционально-потоковых программ с рассмотрением алгоритмов предопределенных операций; архитектура параллельной виртуальной машины обеспечивающей выполнение функционально-параллельных программ; механизмы отображения методов интерпретации ФП программ на ОС Linux с поддержкой системы MOSIX в соответствии многоуровневой архитектурой параллельной виртуальной машины; программная реализация параллельного интерпретатора ФП программ разработанного для кластерной архитектуры под управлением ОС Linux с поддержкой системы динамического распараллеливания MOSIX.
Публикации
По теме диссертации опубликовано 19 печатных работ, из них 3 в центральной печати и 1 международная публикация [21].
Результаты исследований использовались в научно-технических отчетах по грантам: ККФН № 4F0093, 1995 г.; ФЦП «Интеграция», проект 68, направление 21, 1998 г.; РФФИ№ 02-07-90135, 2002,2003 г.
Апробация работы
Основные положения и результаты работы докладывались на:
1, 2, б Всероссийских рабочих семинарах «Нейроинформатика и ее приложения», Красноярск (1993, 1994, 1998);
Межреспубликанской научной конференции «Методы и средства управления технологическими процессами», Саранск, 1993; научно-технической конференции «Проблемы техники и технологий XXI века», Красноярск (1994);
1, 5, б Всероссийских научно-практических конференциях «Проблемы информатизации региона», Красноярск (1995, 1999, 2000); третьем Сибирском конгрессе по прикладной и индустриальной математике (ИНПРИМ-98), Новосибирск, 1998;
Всероссийской научно-практической конференции с международным участием «Достижения науки и техники - развитию сибирских регионов», Красноярск, 1999;
1-3 школах-семинарах «Распределенные и кластерные вычисления», Красноярск (2001, 2002, 2003);
Международной конференции «Перспективы систем информатики» (рабочий семинар «Наукоемкое программное обеспечение»), Новосибирск, 2003 г.
Структура диссертации
Диссертация состоит из введения, четырех глав, заключения, списка используемых источников и двух приложений.
В первой главе проводится анализ архитектур параллельных вычислительных систем (ПВС) на основании которого обосновывается выбор системы для проведения исследований по созданию среды выполнения функционально-параллельных программ. Одним из основных критерием выбора является масштабируемость ПВС. Формулируются подходы к исполнению функционально-параллельных программ. Делается вывод о предпочтении реализации эмулирующей исполняемой среды для проведения исследований модели вычисления и функционально-параллельного языка программирования.
Для выбранной архитектуры анализируются библиотеки и инструментальные средства, реализующие различные стратегии управления распределенными вычислениями. Обосновывается выбор средств, для организации интерпретации функционально-параллельных программ.
Во второй главе предлагается модель, описывающая поведение ФП программ, построенных на основе функционально-потоковой модели вычислений. Функционально-потоковая модель задает программу в виде информационного графа, обладающего рядом специфических особенностей, В основе лежит управление по готовности данных, определяемое для процессов, протекающих внутри бесконечных ресурсов. Основной акцент делается на описание динамики поведения функционально-потоковых программ, построенных на основе рассматриваемой модели.
При описании используется информационно-управляющая ресурсная модель [30, 31, 6], задающая динамику вычислений. В модели вычислений используется представление вычислительного процесса в виде суперпозиции трех графов: информационного, управляющего и ресурсного. Исходя из того, что в функционально-потоковой модели вычислений управление ресурсами осуществляется неявно, ресурсный граф из рассмотрения исключается, и основной акцент делается на описание только информационно-управляющей составляющей.
На основании анализа управления узлами ФП модели вычислений предлагаются методы наложения управляющих воздействий, обеспечивающих неявное управление вычислениями на основе заданного информационного графа. Далее, определяются принципы преобразования информационно графа в информационно-управляющий. Для каждого из узлов модели предлагаются алгоритмы функционирования.
В третьей главе рассматривается методы построения виртуальной машины, обеспечивающей выполнение функционально-параллельных программ, и ее отображение на вычислительную среду. Предлагается многоуровневая архитектура параллельной виртуальной машины, обеспечивающая последовательное выполнение низкоуровневых операций, параллельное выполнение на уровне отдельных процессов, а в более общем случае, на уровне потоков и процессов (крупноблочное распараллеливание) и последовательное выполнение независимых процессов при наличии ресурсных ограничений.
Рассматриваются методы последовательного и параллельного исполнения функционально-параллельных программ. Исследуются пути повышения производительности интерпретации функционально- параллельных программ. Предлагается вариант применения интерпретирующей системы в случае использования ФП языка для написания управляющих командных файлов (скриптов), обеспечивающих контроль и запуск параллельных программ на кластерной архитектуре.
В четвертой главе рассматривается один из вариантов реализации экспериментальной системы интерпретации функционально-параллельных программ, реализованный на базе кластерной архитектуры под управлением ОС Linux с поддержкой системы динамического распараллеливания MOSIX. Интерпретатор реализует виртуальную машину с трехуровневой архитектурой и является составной частью технологической цепочки, обеспечивающей выполнение функциональных параллельных программ.
Создание интерпретатора позволяет решать следующие задачи: исследование общих принципов построения и использования интерпретирующей среды для языка функционально-параллельного программирования; анализ методов повышения производительности в зависимости от состава и конфигурации используемой кластерной системы. Полученная система представляет собой лабораторный макет, допускающий гибкую настройку, возможность быстрой модификации в условиях развития ФП языка программирования. Система позволила провести анализ эффективности разработанной трехуровневой модели виртуальной машины. Полученные результаты показали способность такой системы обеспечивать сбалансированную загрузку узлов кластера.
Приложение А содержит описание функционального языка параллельного программирования «ПИФАГОР».
В Приложении В приведен полный листинг программ, используемых по тексту диссертации.
Работа изложена на 129 страницах, содержит 33 рисунка и 4 таблицы. Список литературы включает 115 наименований.
Системы, обеспечивающие параллельное выполнение на МРР и кластерных архитектурах
Самый быстрый российский суперкомпьютер МВС-1000М [59] имеет кластерную архитектуру. Кластер МВС-ЮООМ содержит 768 процессоров Alpha 21264 667 МГц, сгруппированных в шесть базовых блоков по 64 двухпроцессорных вычислительных узла в каждом. Система работает под управлением ОС RedHat Linux и достигает производительности 734,6 Гфлоп/с. Сегодня кластерные системы есть в списке предложений таких производителей высокопроизводительных серверов, как HP, IBM, SUN, DELL, NEC и др. [38].
HP предлагает кластеры в разнообразных конфигурациях - от систем начального уровня на базе SCSI до кластеров масштаба предприятия с виртуализацией дисковых массивов. Сегодня это более 300 кластерных конфигураций на базе процессоров Intel, Alpha (EV68 и EV7) и PA-RISC (8700+) с широким выбором серверов, систем хранения и сетевого оборудования, поддерживающих ПО Windows, Linux, HP-UX, Tru64 UNIX (TruCluster), Open VMS (OpenVMS Clusters), Novell и Oracle9i RAC. Среди решений HP на платформе Intel кластеры серии ProLiant, например конфигурация из двух стандартных серверов DL380 с процессорами Хеоп и общей системой хранения данных. Особые надежды возлагаются на кластеры на базе Itanium 2 под управлением ОС Linux и HP-UX, для которых появляется все больше приложений независимых разработчиков. Эта платформа должна прийти на смену кластерам HP на базе процессоров Alpha и PA-RISC. Кластер из восьми серверов HP гх2600 на базе Itanium 2 вошел в первую десятку рейтинга Тор500. Для создания кластеров из узлов гх2600 и rx5670 HP предлагает ПО hptc/ClusterPack V2.0.
Кластерные решения IBM известны на рынке более десяти лет. Спектр ее нынешних предложений включает в себя как кластеры Intel/Linux, так и платформы RISC/UNIX. К первым относится кластерная система Cluster 1350 из серверов IBM xSeries 335, 345, 360 или BladeCenter. Такие высокопроизводительные системы для научных, технических расчетов и коммерческих задач с межузловым соединением Ethernet, Gigabit Ethernet или Myrinet-2000 содержат до 512 узлов с одним-двумя процессорами Intel Хеоп (2,4-3,06 МГц) и работают под управлением ОС Red Hat Linux или SuSE Linux Enterprise Server с кластерным ПО CSM for Linux или GPFS for Linux. В июле 2003 IBM выпустила серию серверов eServer 325 на базе процессора AMD Opteron 246 под управлением ОС Linux или Windows [60, 61,62,63,64].
Независимые рейтинги лучших суперкомпьютеров мира [42] позволяют проследить динамику и оценить тенденции развития современных параллельных архитектур. По текущей редакции списка высокопроизводительных ПВС (таблица 1.1) видно, что на сегодняшний день доля МРР и кластерных систем является наиболее весомой(составляет более 60 %) и почти треть составляют смешанные (Constellations) системы, a SMP системы практически вытеснены. Это связанно с тем, что МРР и кластерные системы хорошо масштабируются и, соответственно позволяют легко наращивать производительность, которая ограничивается только возможностями ПО и коммуникационными средами. Если проследить динамику развития ПВС (таблица 1.2), то можно отметить две тенденции: активное внедрение в список высокопроизводительных компьютеров систем с кластерной архитектурой [38, 51, 53, 56, 58] (если доля кластеров на 1997 г. составляла всего 0,2 %, то в 2002 и 2003 годах кластерные системы входили в первую десятку в ТОР 500 и доля их составляла 16,2 % и 29,8 % соответственно); развитие неоднородных систем (Constellations), в основном представленных высокопроизводительными компьютерами, реализованными на базе ccNuma архитектуры [45]. Одной из особенностей программирования на функционально-параллельных языках является то, что в результате исполнения ФП программы может появляться множество независимых функций (распараллеливание на уровне функций). Эффективное исполнение ФП программы, реализующей распараллеливание на уровне крупноблочных функций, предъявляет определенные требования к архитектуре ПВС, а именно: архитектура должна обладать свойством масштабируемости что, в идеале, позволяет «неограниченно» наращивать вычислительные ресурсы. Это связано с тем, что при программировании на функционально-параллельном языке возможно увеличение числа слабо зависимых крупноблочных функций (число таких функций будет определяться только параллелизмом задачи) [11].
В большей степени масштабируемость присуща МРР и кластерным архитектурам. Принимая во внимания тот факт, что кластерные системы могут быть собраны в лабораторных условиях (в научно-исследовательских учреждениях и вузах) [28, 29, 56, 62, 63, 64], а так же то, что в них используется одинаковая с МРР-системами парадигма программирования, можно сделать вывод, что кластерная архитектура является оптимальной для проведения исследований функционально-параллельного языка и его модели.
Влияние эквивалентных преобразований на формирование информационно-управляющего графа
В динамике это будет выглядеть следующим образом. На первом этапе I) (рисунок 2.19) константная разметка Zconst представляющая задержанный подграф и сигнал готовности Sz присутствуют на входе операции интерпретации (рисунок 2.19 вариант «а»). Появление на функциональном входе функции F и сигнала готовности функции Sf приводит к формированию сигнала Sr (рисунок 2.19, вариант «Ь» и «с») — сигнала раскрытия задержанного подграфа. В результате раскрытия задержанного подграфа вычисляется значение С = [(а,Ь):+], которое поступит на вход операции интерпретации - этап \{ (рисунок 2.19, вариант «d»), на функциональный вход поступит ретранслированная функция F и сигнал готовности функции Sf, что обозначает готовность данных на функциональном входе. Окончание вычисления [(а,Ь):+] сопровождается появлением сигнала Sc, что приведет к окончательному срабатыванию функции интерпретации (рисунок 2,19, вариант «е») и вычислению F(C).
В том случае, если и на информационном и на функциональном входах находится список задержанных вычислений — сигнал раскрытия задержанного подграфа все равно будет сформирован, поскольку данные на входах операции интерпретации присутствуют в виде Zcons, и соответственно присутствуют сигналы готовности константных данных Sz. Сигнал Sr поступит на задержанные подграфы и раскроет их, в результате они будут вычислены.
В соответствии с рассмотренными выше вариантами поведения операции интерпретации обобщенный алгоритм поведения операции интерпретации выглядит следующим образом: 1. появление сигналов готовности на информационном и функциональном входах активируют анализатор типа данных на этих входах; 2. если на информационном входе присутствует задержанный список, то сигнал готовности данных на функциональном входе приведет к раскрытию задержанного списка; 3. если на функциональном входе присутствует задержанный список, то сигнал готовности данных на функциональном входе, присутствующий в виде сигнала готовности задержанного списка приведет к раскрытию задержанного списка на этом входе; 4. раскрытие задержанного списка представляет собой вычисление задержанного внутри него информационно-управляющего подграфа; 5. результат вычисления этого подграфа оформляется в параллельный список и передается на динамически формируемую операцию интерпретации (Ij на рисунке 2.18); 6. появление параллельного списка том или ином входе операции интерпретации вызовет набора независимых операций интерпретаций; 7. число операций интерпретаций и данные на их информационных и функциональных входах будет определено на основании правил срабатываний операторов и кратности данных в интерпретируемом параллельном списке. Правила срабатывания конкретизируют формирование разметок на выходных дугах для каждого из ранее введенных операторов. Оператор интерпретации обеспечивает преобразование входного набора данных X (аргумента), в выходной набор V (результата), используя при этом входной набор F в качестве функции, определяющей алгоритм преобразования. В постфиксной нотации, выбранной для дальнейших иллюстраций, данное преобразование можно записать следующим образом: X:F= Y. Можно рассмотреть множество унарных функций F, разделив его при этом на два подмножества: F = {і\, f2}, где fi — множество предопределенных функций языка, для каждой из которых аксиоматически задаются области определения и изменения, f2 - множество функций, порождаемых при программировании. Следует отметить, что выбор базового набора предопределенных функций осуществляется в некоторой степени субъективно, исходя из соображений удобства пользования разрабатываемым языком. Введены арифметические функции, функции сравнения и прочие, аналогично тому, как это сделано и в других языках программирования. Например, функция сложения двух чисел х(, х2, порождающая в качестве разметки число у, задается следующим образом: (х1} х2):+ = у, где первый аргумент оператора интерпретации является двухэлементным списком данных. Каждый элемент этого списка должен быть числом. Второй аргумент оператора интерпретации является функцией сложения, обозначенной значком "+м. Результат функции сложения, значение у, является атомарным элементом. Наряду с определением функций, присущих всем языкам программирования, целесообразно определить множество функций, нестандартных в традиционном понимании. Например, целое число может непосредственно интерпретироваться как функция выбора элемента списка: где і - натуральное число, х, - элемент списка. Данная функция выделяет из списка данных і-й элемент, который и определяет разметку выходной дуги. Другой полезной предопределенной функцией является: (bi, b2, b3, ... bn):? = [ii, i2,... ik] , где (bi,...bn) - список булевских величин; Пі»—, kl — параллельный список натуральных чисел, определяющих номера тех компонент булевского списка, которые имеют истинные значения. Наличие данной функции позволяет формировать условия, обеспечивающие выполнение нескольких альтернативных ветвей программы. Полный список предопределенных функций представлен в описании языка (Приложение А). Наряду с определением операции интерпретации для аксиоматически определенных функций, она также определяется и для уже существующих операторов.
Методы последовательного выполнения ФП программ
Для обеспечения выполнения функционально параллельных программ на реально существующих параллельных вычислительных системах можно определить два основных подхода,
Первый подход заключается в преобразовании функциональных параллельных программ в параллельные программы, соответствующие конкретной архитектуре ВС. В этом случае возможно достижение максимальной производительности, если удастся обеспечить эффективность процесса преобразования. Этот подход реализуется написанием компилятора языка под конкретную платформу ВС. Однако, для получения результата, необходимо тщательное исследование принципов преобразования одного вида параллелизма, в другой. При этом не всегда удается получить эффективные эквивалентные представления и приходится заниматься динамической эмуляцией в ходе вычислений.
Второй подход - непосредственная интерпретация функциональных параллельных программ с использованием специально разработанного эмулятора для конкретной архитектуры ВС. Несмотря на падение производительности, подход интерпретации ФП допускает более простую реализацию и позволяет достаточно быстро приступить к разработке и отладке ФП программ. Он является удобным для решения задач исследовательского характера, поскольку позволяет провести эксперименты с меньшими трудозатратами, обеспечивая формирование некоторой архитектурной модели за счет непосредственной интерпретаци существующей модели, тем самым обеспечивает прохождение этапа имитационного моделирования, без которого невозможно будет реализовать компилятивный вариант.
Потеря производительности будет невысокой, если операциями будут являться достаточно крупные программные модули. Это вполне возможно при использовании функционального языка в качестве языка сценариев, осуществляющего диспетчеризацию параллельно исполняемых вычислительных процессов. Интерпретатор моделирует некоторую виртуальную вычислительную машину, для которой базовыми инструкциями служат не элементарные команды процессора, а операторы языка программирования. Задача интерпретатора — провести разметку информационно-управляющего графа ФП программы в соответствии с алгеброй преобразований, аксиомами языка и правилами интерпретации. Можно выделить несколько вариантов реализации процесса интерпретации, основанных на различных алгоритмах обхода и н формацион но-управляющего графа: - последовательный, основанный на принципе последовательного обхода информационного графа; - редукционный, вариант последовательного обхода, основанный на принципе редукции графов; - событийный, основанный на обработке потока событий. Все эти варианты могут быть использованы для организации как последовательного, так и параллельного выполнения функционально-параллельных программ. В соответствии с определенной выше трехуровневой архитектуры виртуальной машины необходимо выделить элементы ФП программы, которые: - распараллеливаются в процессе выполнения; - выполняются последовательно; - могут выполняться автономно в рамках последовательного процесса. Распараллеливание ФП программы может осуществляться: - по операциям интерпретации; - по управляющим элементам интерпретатора. Варианты распараллеливания по операциям интерпретации: - максимальное распараллеливание - до уровня элементарных операций; - директивное, основанное на использовании управляющих конструкций языка, задающих параллелизм (такими конструкциями в языке являются параллельные списки функций или данных). Под распараллеливанием управляющих элементов подразумевается параллельный запуск виртуальной машины. Выбор элементов распараллеливания и алгоритма обхода информационно-управляющего графа определяет соответствующие варианты организации процесса выполнения. Последовательная интерпретация основана на полном обходе информационно-управляющего графа программы в соответствии с выбранным алгоритмом обхода (последовательным, редукционным, событийным). Каждому ребру информационного графа ставится в соответствие специальная структура - фишка, отражающая обрабатываемые данные. Базовым оператором, задающим все действия, предусматриваемые правилами функционирования модели вычислений, является оператор интерпретации, соответствующий одноимённому программо формирующему оператору информационного графа. Оператор интерпретации имеет два входа и один выход. На его входы поступают две фишки любого типа, одна из которых будет интерпретироваться как аргумент, а другая - как функция. На выходе оператора, после окончания всех действий, предусматриваемых моделью вычислений, появляется выходная фишка (в том числе, возможно, и фишка ошибки), которая становится выходной разметкой.
Перед выполнением операции интерпретации, над обеими входными фишками, в случае необходимости, выполняются действия в соответствии с правилами эквивалентных преобразований и правилами интерпретации списков. В ряде случаев это приводит к рекурсивным вызовам функции, осуществляющей операцию интерпретации. Затем выполняется операция интерпретации для предопределённых операций, описанных ниже.
В случае, когда в качестве функции выступает функциональная фишка, производится запрос на вычисление к объекту, указатель на который она содержит. При этом в качестве аргумента запроса передаётся фишка, интерпретируемая данным оператором как аргумент.
Интерпретация всех предопределенных операций задается правилами их выполнения, перечисленными в описании функционально параллельного языка программирования (приложение Л). Как уже было сказано выше, порядок обхода информационного графа задается соответствующим алгоритмом, реализованным в ФП программе.
Описание протокола взаимодействия процессов при передаче результатов
Из результатов видно, что при уменьшении времени выполнения (в данном случае из-за уменьшения размера матрицы) большое влияние оказывают потери при миграции процессов, в результате чего падает эффективность. Для измерения влияния времени миграции проводился тест с использованием интерпретатора с принудительной программной миграцией. Выигрыш по времени выполнения в случае с матрицей 8x8 составил 8,5 %, что связанно с особенностями работы алгоритма балансировки загрузки, использованного в системе MOSIX, согласно которому существует определенное время задержки (время принятия решения), в течении которого принимается решение о необходимости миграции процесса.
Очевидно, что необходим какой либо метод предварительного определения стоит ли, в каждом конкретном случае, запускать параллельную обработку или нет. Возможны следующие варианты решения этой задачи: 1)на этапе трансляции проводить предварительный анализ вычислительной сложности функции и отображать полученный результат в промежуточном представлении, которое в свою очередь разбирается интерпретатором и позволяет ему принять решение о необходимости параллельной обработки данного участка программы; 2) непосредственно в ходе интерпретации анализировать параллельные участки программы и принимать решение о необходимости их параллельной обработки; 3)запускать параллельную обработку только тогда, когда на функциональный вход операции интерпретации поступает неэлементарная функция или список функций. При этом сокращаются накладные расходы на анализ параллельных участков, но могут возникнуть некоторые издержки в случае если время вычисления такой функции сравнимо с временем миграции её на свободный узел кластера; 4) позволить программисту, на основании предварительного анализа программы, давать указания о необходимости параллельной обработки (путем задания параметров интерпретации). Для оценки сложности можно использовать такой показатель, как среднее число операций интерпретации, необходимых для выполнения конкретной функции. В случае, когда аргументом функции является список, число операции интерпретации в общем случае будет являться функцией от размерности входных данных. Примером такой функции является рассмотренная (в задаче 1) функция SortLess (SortGreat). Сложнее оценить рекурсивную функцию, входными данными для которой служит список данных, а глубина рекурсии зависит от размера этих данных. Попробуем оценить функцию SortLess. Для ее интерпретации необходимо 5+n N (TwoSwap) операций, где п - размер вектора входных данных. Определив число операций и сравнив его с заданным временем миграции, выраженным в операциях интерпретации, можно оценить необходимость параллельной интерпретации той или иной функции. Реализуется данный подход следующим образом. При установке и настройке под конкретный кластер производится тестирование кластера. По результатам тестирования определяются весовые коэффициенты порождения и миграции процесса, которые в свою очередь будет использовать интерпретатор. На транслятор возлагается задача оценки каждой функции в виде определения функции зависимости вычислительной сложности, от размера входных данных. В некоторых случаях это будет постоянная величина. Эти оценки формируется во время дополнительного прохода транслятора по сформированному объектному представлению. Далее эти оценки записываются в оттранслированный файл. Интерпретатор на их основании принимает решение о параллельном исполнении соответствующей функции. 1. Разработка интерпретатора обеспечила практическую поддержку экспериментов, связанных с исследованием параллельного выполнения функциональных программ, написанных на ФП языке программирования. Полученные результаты показывают, что использование многоуровневой архитектуры виртуальной машины в системе выполнения ФП программ позволяет обеспечивать сбалансированную загрузку узлов кластера под управлением ОС Linux с поддержкой MOSIX. Параллельная интерпретация позволила повысить производительность вычислений по сравнению с последовательным выполнением одних и тех же задач (в идеальных условиях, когда число используемых узлов кластера было больше числа одновременно выполняющихся «тяжелых» функций). 2. Программы, написанные на ФП языке программирования, и оттестированные на последовательном интерпретаторе выполнялись на параллельном интерпретаторе без модификации кода и достигали эталонных результатов решения. 3. Полученные данные позволяют определить направления дальнейших работ по повышению эффективности интерпретатора, улучшению транслятора и модификации языка программирования. Получены следующие научные и практические результаты работы. 1. Предложена модель, описывающая динамику поведения функционально-потоковых параллельных программ. Разработаны обобщенные алгоритмы функционирования узлов модели. Разработаны методы наложения управляющих воздействий, обеспечивающих неявное управление вычислениями на основе заданного информационного графа, 2. Предложена многоуровневая архитектура параллельной виртуальной машины, обеспечивающей выполнение функционально-параллельных программ. Виртуальная машина реализует трехуровневую схему выполнения ФП программ, которая обеспечивает:
