Содержание к диссертации
Введение
Глава 1. Анализ параллельных архитектур, языковых и инструментальных средств параллельного программирования
1.1 Архитектуры параллельных ВС
1.2. Выбор архитектуры для проведения исследований по созданию среды выполнения программ, написанных на языке функционально-параллельного программирования
1.3.Общие подходы к реализации исполнения ФП программ
1 4 Системы, обеспечивающие параллельное выполнение наМРР и кластерных архитектурах 1.5.Выбор среды для построения эмулирующей системы
Глава 2. Управление вычислениями в функционально-потоковой модели
2.1.Описание динамики вычисления функционально-потоковой модели 2.2.Программо-формирующие операторы
2.3.Правила срабатывания операторов
2.4. Влияние эквивалентных преобразований на формирование информационно-управляющего графа
Глава 3. Последовательность срабатываний переходов в сетях Петри и связанные с ней проблемы
3.1.Некоторые аспекты теории сетей и основные определения
3.2.Выражение предиката (ргех) и поведение сетей Петри
З.З. Последовательности срабатываний переходов в сетях Петри и параллелизм внутри них
3 АРаспределенная система вычислений
систем
3.4.1 -Некоторые определения и понятия
3.4.2.Методы описания распределенных (А вычисления
3.4.3.Распределенная система вычисления 126
3.4.4.Алгоритм сохранения глобальной информации 140
системы в локальном состоянии процесса 146
Глава 4. Разработка инструментальной системы для выполнения функционально-параллельных программ на кластерной архитектуре
4.1 Реализация последовательно-параллельного интерпретатора с использованием системы динамического распараллеливания MOSK-146
4.1.1 Структура интерпретатора
4.1.2 Описание входного представления 147
4.1.3 Общий алгоритм работы интерпретатора 153
4.1.4 Алгоритм параллельной интерпретации 154
4.1.5 Алгоритм эквивалентных преобразований списков 157
4.1.6 Описание протокола взаимодействия процессов при передаче результатов 157
4.1.7 Описание входных параметров командной строки интерпретатора 158
4.2 Оценка интерпретации ФПП 160
4.3 Методы повышения эффективности интерпретации 165
4.3.1 Оценка вычислительной сложности интерпретируемой функции 166
Список использованных источников
- Выбор архитектуры для проведения исследований по созданию среды выполнения программ, написанных на языке функционально-параллельного программирования
- Влияние эквивалентных преобразований на формирование информационно-управляющего графа
- Последовательности срабатываний переходов в сетях Петри и параллелизм внутри них
- Описание протокола взаимодействия процессов при передаче результатов
Введение к работе
Акіуальность. Использование параллельных вычислений связано с созданием систем программирования и архитектур, существенно отличающихся от тех, что применяются при последовательной обработке данных. Существуют различные подходы к разработке параллельных программ и их выполнению.
Исторически сложившаяся практика разработки систем программирования, ориентированных на поддержку конкретных архитектур, несмотря на эффективное решение задач для различных параллельных вычислительных систем (ЛВС), привела к проблемам переносимости программного обеспечения (ПО). Ситуация усугубляется развитием неоднородных архитектур: адаптация уже существующего ПО для таких систем является неординарной задачей даже для опытных программистов.
Теория сетей Петри широко применяется для моделирования и анализа поведения распределительных вычислительных систем. В терминах сетей Петри достаточно адекватно выражаются многие важные явления параллельных вычислений, такие как взаимное блокирование процессов, состязательное распределение ресурсов, взаимное исключение доступа к ресурсам и другие.
Такие системы параллельной обработки информации, как многопроцессорные вычислительные машины, параллельные программы, моделирующие параллельные дискретные системы и их функционирование, мультипрограммные операционные системы, асинхронные электронные схемы и другие моделируются при помощи сетей Петри.
Развитие теории сетей Петри проводилось по двум направлениям. Прикладная теория сетей Петри связана главным образом с применением сетей Петри к моделированию систем, их анализу и получающимся в результате этого глубоким проникновением в моделируемые системы.
Это требует хорошего знания предметной области применения, сетей Петри и методов теории сетей Петри. Чистая теория сетей Петри занимается разработкой основных средств, методов и понятий, необходимых для применения сетей Петри, для чего необходим прочный теоретический фундамент.
Помимо этого аппарат сетей Петри обладает большой гибкостью, позволяющей осуществлять моделирование параллельных вычислений в различных семантиках. В теории параллельных вычислений наиболее употребительными являются семантики чередования и частичного порядка. В семантике чередования параллельное вычисление представляется последовательностью действий, в которой параллельное выполнение нескольких действий подменяется недетерминированным выбором порядка их выполнения. В семантике частичного порядка на множестве действий устанавливается отношение частичного порядка, отражающее причинно-следственные и временные зависимости между событиями. Параллельно выполняемые действия при этом оказываются несравнимыми. Семантика чередования находит отражение в последовательностях срабатывания переходов сети, семантика частичного порядка приводит к рассмотрению специального класса так называемых сетей происшествий, отражающих упорядоченность событий. Каждая из упомянутых семантик обладает своими особенностями и достоинствами, и поэтому в целях наиболее полного анализа поведения распределенных систем необходимо иметь разработанную технику перехода от одной семантики моделирования параллельных вычислений к другой.
В моделировании и исследовании поведения сложной распределенной системы большую трудность представляет задача синтезирования всей глобальной информации о системе по времени, когда известна информация о каждом подпроцессе и нет буферной памяти для ее запоминания. Поэтому разработка необходимого формализма в сетях Петри для распределенных систем для определенного класса является актуальной.
Попытки создания инструментальных средств, обеспечивающих переносимость параллельных программ, предпринимались неоднократно и осуществлялись по нескольким направлениям. Все они, тем или иным образом, связаны с написанием программ для некоторой обобщенной архитектуры. Выполнение таких программ на ПВС осуществляется после их предварительного преобразования с использованием специализированных средств распараллеливания (десеквенторов). Одним из вариантов классификации методов десеквепции является деление по способам представления исходного параллелизма:
1) использование последовательного программирования с дальнейшим автоматическим распараллеливанием разработанных программ;
2)применение языков программирования, обеспечивающих непосредственное описание любых потоков параллельного управления, по сути являющихся расширениями традиционных последовательных языков за счет добавления разнообразных примитивов распараллеливания и синхронизации. При этом уровень параллелизма полностью контролируется разработчиком и может задаваться в зависимости от конкретных условий. Десеквенция подобных программ является переводом одной параллельной формы в другую;
3)опора на языки, неявным образом описывающие максимальный параллелизм, что обеспечивается заданием только информационных связей. Предполагается, что программа будет рассчитана на выполнение в виртуальной машине с неограниченными ресурсами, а запуск операторов будет происходить по готовности их данных. Адаптация программы к конкретной ПВС обычно осуществляется путем сжатия параллелизма с учетом ресурсных и архитектурных ограничений.
Каждый из подходов в настоящее время представлен семейством соответствующих инструментальных средств.
Использование третьего подхода позволяет выстраивать архитектурно независимые программы, однако приводит к необходимости решения проблем отображения этих программ на различные архитектуры.
Все это определяет актуальность исследований в области создания новых средств параллельного программирования, позволяющих писать мобильные, архитектурно независимые программы, а так же актуальность создания систем, обеспечивающих исполнение таких программ.
Цель работы состоит в исследовании средств и методов выполнения функционально-параллельных программ, базирующихся на функционально-потоковой модели вычислений, в разработке методов анализа сетей Петри для моделирования параллельных и распределенных систем на основе предложенного формализма сетей Петри, обеспечивающих эффективное поведение многовариантного анализа систем на этапе их алгоритмического проектирования. Для достижения поставленной цели необходимо решить следующие задачи:
1. разработать модель, описывающую поведение функционально-параллельных программ, построенных на основе функционально-потоковой модели параллельных вычислений. Разработаны обобщенные алгоритмы выполнения предопределенных операций функционально-потоковой модели вычислений.
2. разработать многоуровневую архитектуру параллельной виртуальной машины обеспечивающей выполнение ФП программ.
3. разработать формализм сети Петри для распределенной системы, функционирование которой может быть описано либо в семантике чередования последовательности срабатываний переходов, либо в семантике частичного порядка на множестве происшествий процесса. Установить соответствие между классами эквивалентности процессов и классами эквивалентности последовательностей срабатывания переходов в распределенной системе.
4. создать размеченную переходную систему для распределенной системы для определения глобального состояния распределенной системы с использованием логических часов между событиями,
5. разработать алгоритм сохранения глобальной информации в моделируемой распределительной системе вычислений.
6. разработать алгоритмы анализа сетей Петри для распределенных систем.
Методы исследования. Исследования осуществлялись на основе: теории сетей Петри; теории алгоритмов; теории формальных грамматик, и языков; формальной, предикатной логики; теории множеств.
На защиту выносятся следующие положения, имеющие научную новизну.
1. Исследована взаимосвязь в конкуренции (параллелизме) событий между двумя основными подходами при моделировании и анализе поведения распределенных систем в теории сетей Петри: первый подход привлекает понятие последовательности срабатываний переходов и соответствует семантике чередования параллельных вычислений, второй подход отражает понятие сети-процесса, соответствующее семантике частичного порядка.
2. Для класса сетей (без самоконкурирующих процессов) получены необходимые и достаточные условия, при которых сеть-процесс однозначно восстанавливается по заданной последовательности срабатываний переходов
3. Введено описание формализма распределенной системы вычисления в виде временной алгебры взаимодействующих процессов сети Петри на основе предложенной размеченной переходной системы без буферизации информации.
4. Разработка алгоритма для сохранения глобальной информации в распределенных системах вычислений.
5. Предложен механизм отображения методов интерпретации ФП программ на ОС Linux с поддержкой системы MOSIX в соответствии многоуровневой архитектурой параллельной виртуальной машины.
6. В рамках развития функционального языка параллельного программирования предложены предопределенные функции, обеспечивающие параллельное выполнение независимых модулей (программ), позволяющих реализовать крупноблочное распараллеливание.
Научная ценность работы состоит в создании математических моделей и формализма анализа распределенных систем, создающих основу разработки программных комплексов в задачах спецификации и верификации дискретных параллельных и распределенных систем.
Практическая ценность.
1. Разработан последовательный интерпретатор, обеспечивающий выполнение и отладку функционально-параллельных программ.
2. Разработан параллельный интерпретатор, обеспечивающий выполнение функциональных параллельных программ на кластерных системах, одно и многопроцессорных архитектурах под управлением ОС Linux с поддержкой системы динамического распараллеливания MOSIX.
3. Для проведения экспериментов на базе учебных компьютерных классов создана кластерная система под управлением ОС Linux с поддержкой MOSIX и MPI, позволившая провести работы по созданию и отладке параллельного интерпретатора, а также провести оценочные эксперименты параллельной интерпретации ФП программ.
4. Реализованы методы переноса ФП программ на последовательную и кластерную архитектуры. Методы основаны на сжатии максимального параллелизма задачи за счет изменения стратегии управления вычислениями.
Апробация работы. Основные результаты диссертационной работы докладывались на следующих научных конференциях: Третья международная научно-техническая конференция «Кибернетика и технологии XXI века», Воронеж, 2002 г. Третий Всероссийский симпозиум по прикладной промышленной математике, Сочи, 2003 г., Шестая международная конференция. «Современные сложные системы управления», Воронеж 2004 г.
Седьмой Всероссийский симпозиум по прикладной промышленной математике, Сочи, 2005 г., Седьмая международная конференция «Современные сложные системы управления», Воронеж 2005 г.
Внедрение результатов работы.
Результаты диссертационной работы использованы при выполнении НИР «Разработка теории сетей Петри в распределенных системах информации» и в учебном процессе курсов численных методов Московского государственного горного университета.
Публикации: основное содержание работы отражено в 6 публикациях.
Объем и структура диссертации.
Диссертация состоит из введения, четырех глав, заключения и списка литературы из 127 наименований.
Выбор архитектуры для проведения исследований по созданию среды выполнения программ, написанных на языке функционально-параллельного программирования
В соответствии с классификацией вычислительных систем по наличию общей или распределенной оперативной памяти, различают следующие основные классы аппаратных архитектур параллельных вычислительных систем: SMP, МРР, кластерная и NUMA [1,32,33,34,35,36,37, 38,39,40].
SMP-систеиы (Symmetric Multi Processors) построены на основе общей памяти и однородных процессоров [35, 37, 41], каждый из которых имеет равноправный доступ к любому участку памяти. Для достижения хорошей производительности каждый процессор имеет собствешгую кэш-память, поскольку основная память работает слишком медленно по сравнению со скоростью работы процессоров. Когерентность кэш памяти процессоров поддерживается аппарат. SMP архитектура симметрична - общая память является способом передачи сообщений между процессорами, при этом все вычислительные устройства при обращении к ней имеют равные права и одну и ту же адресацию для всех ячеек памяти. Последнее обстоятельство позволяет эффективно обмениваться данными с другими вычислительными устройствами. SMP-система строится на основе высокоскоростной системной шины (SGI PowerPath, Sun Gigaplane, DEC TurboLaser), к слотам которой подключаются функциональные блоки трех типов: процессоры (ЦП), операционная система (ОП) и подсистема ввода/вывода (I/O). Для подсоединения к модулям I/O используются уже более медленные шины (PCI, VME64). Наиболее известными SMP-системами являются SMP-сервера и рабочие станции на базе процессоров Intel (IBM, HP, Compaq, Dell, ALR, Unisys, DG, Fujitsu и др.) [38]. Вся система работает под управлением единой операционной системы (ОС) (обычно UNIX-подобной, например HP-UX 1 li, Sun Solaris и т.п., но для Intel-платформ поддерживается Windows NT, 2000, 2003). ОС автоматически (в процессе работы) распределяет процессы по процессорам, но иногда возможна и явная привязка. Обмен сообщениями в SMP-системах организован через общую память, что существенно упрощает взаимодействие процессоров между собой. При работе с SMP-системами используют так называемую парадигму программирования с разделяемой памятью (shared memory paradigm).
В списке 500 высокопроизводительных компьютеров мира [42] на ноябрь 2003 года SMP архитектура представлена единственной Fujitsu PrimePower НРС2500 с 2304 процессорами, установленной в Национальной аэрокосмической лаборатории Японии в 2002 году.
Основные преимущества SMP-систем: простота и универсальность для программирования. Архитектура SMP не накладывает ограничений на модель программирования, используемую при создании приложения: обычно используется модель параллельных ветвей, когда все процессоры работают абсолютно независимо друг от друга - однако, можно реализовать и модели, использующие межпроцессорный обмен. Использование общей памяти увеличивает скорость такого обмена, пользователь также имеет доступ сразу ко всему объему памяти. Для SMP-систем существуют сравнительно эффективные средства автоматического распараллеливания; легкость в эксплуатации. Как правило, SMP-системы используют систему охлаждения, основанную на воздушном кондиционировании, что облегчает их техническое обслуживание; относительно невысокая цена.
Недостатки: системы с общей памятью, построенные на системной шине, плохо масштабируемы. Этот важный недостаток SMP-системы не позволяет считать их по-настоящему перспективными. Причины плохой масштабируемости заключаются в том, что в данный момент шина способна обрабатывать только одну транзакцию, вследствие чего возникают проблемы разрешения конфликтов при одновременном обращении нескольких процессоров к одним и тем же областям общей памяти. Момент, когда произойдет такой конфликт, зависит от скорости связи и от количества вычислительных элементов. В настоящее время конфликты могут происходить при наличии 8-24-х процессоров. Кроме того, системная шина имеет ограниченную (хоть и высокую) пропускную способность (ПС) и ограниченное число слотов.
Все это с очевидностью препятствует увеличению производительности при увеличении числа процессоров и числа подключаемых пользователей. В реальных системах можно использовать не более 32 процессоров [43]. Для построения масштабируемых систем на базе SMP используется NUMA-архитектура.
Влияние эквивалентных преобразований на формирование информационно-управляющего графа
MPI обладает хорошо проработанными средствами для организации взаимодействия процессов. Также как и в PVM для организации межзадачного обмена предусмотрено использование блокирующих и не блокирующих алгоритмов. Существует возможность объединения запросов на прием или передачу для запуска одной командой, при этом способ приема сообщения никак не зависит от способа его посылки: сообщение, отправленное с помощью объединения запросов либо обычным способом, может быть принято как обычным способом, так и с помощью объединения запросов. Для облегчения управление введена возможность управления группами параллельных процессов и т.п.
Стандарт MPI предлагает больший спектр возможностей, нежели стандарт PVM [88, 89]. Так, например, по сравнению c.PVM MPI имеет более разветвленный инструментарий для организации взаимодействия задач. Можно сказать, что реализованное одним-единственным способом в PVM, в MPI может быть сделано несколькими и при этом эффективнее (только для организации коллективных коммуникаций в MPI предусмотрено 9 функций 5-ти различных типов, а в PVM используется только одна).
Система MOSIX [84, 28], представляет собой кластерное программное обеспечение, встраиваемое в ядро ОС Unix [90], которое расширяет ядро Unix систем механизмами автоматического распределения процессов между различными узлами кластера, при этом сохраняя модель управления, реализованную в Unix-системах (интерфейс ядра остается немодифицированным).
Управляющее ядро MOSIX обеспечивает адаптивную балансировку нагрузки и вытесняющий перенос "Unix процессов" в пределах кластерной системы. В системе управления MOSIX можно выделить две основные части: механизм вытесняющего переноса процессов (preemptive process migration -PPM) и набор алгоритмов для адаптивного разделения ресурсов. Эти управляющие модули следят за выполнением процессов и переносят их с одного узла на другой с целью достижения максимально возможной производительности. Механизмы управления MOS1X, встраиваемые на уровне ядра системы, являются полностью прозрачными для прикладного уровня.
Единицей управления в MOSIX является процесс. Пользователи могут выполнять параллельные приложения, инициализируя множественные процессы в одном узле, затем позволять системе назначать эти процессы на лучшие доступные в это время узлы кластера. Если в течение выполнения процессов станут доступными новые ресурсы, то алгоритмы совместного использования ресурсов, должны их задействовать, возможно, обеспечивая перераспределение процессов между узлами. Способность назначать и переназначать процессы, особенно важна для легкости использования.
Еще одной особенностью MOSIX является отсутствие централизованного управления, т. е., каждый узел кластера может работать, как автономная система, и самостоятельно управлять вычислительными процессами. Каждый кластерный узел выступает в роли хоста для локально созданных процессов и используется в качестве сервера для процессов, перенесенных с других узлов. Узлы можно добавлять к кластеру и удалять из него, не оказывая воздействия на уже выполняющиеся процессы.
Такая идеология позволяет динамически конфигурировать кластер, достаточно просто наращивая или сокращая количество узлов без каких-либо остановок системы. Алгоритмы масштабирования гарантируют, что система будет хорошо работать и на больших конфигурациях.
Последовательности срабатываний переходов в сетях Петри и параллелизм внутри них
Правила эквивалентных преобразований определяют алгебру модели и языка программирования [17, 20? 21], Они позволяют осуществить трансформацию информационно-управляющего графа, обеспечивающую сведение сложных структурированных операций к набору элементарных действий над предопределенными компонентами. Возможна также обратная структуризация элементарных действий, полезная при адаптации полученной функциональной параллельной программы к архитектуре конкретной ПВС Эквивалентные преобразования определены на множестве операторов язьжа и отражают общие алгебраические свойства модели. Их проведение может происходить как перед началом вычислений, когда они применяются к исходному информационно-управляющему графу, так и непосредственно в ходе выполнения программы. В этом случае преобразования проходят на частично размеченном графе.
Из всего разнообразия эквивалентных преобразований, определенных в описании модели вычислений, остановимся на обработке параллельных списков, которая сводится к формированию множества отдельных операторов интерпретации. Параллельный список функций над некоторым аргументом эквивалентен параллельному списку операций интерпретации для каждой из функций над одним и тем же аргументом: X:[fb f2,.„MX:fb X:f2,. - .XrfJ
Функция, выполняемая над параллельным списком аргументов эквивалентна параллельному списку операций интерпретации для этой функции над каждым из аргументов:
Эти выражения показывают, каким образом кратную разметку некоторой дуги можно представить эквивалентной одноэлементной разметкой множества дуг. В более общем случае, когда разметка с кратностью больше единицы имеется на обеих входных дугах оператора интерпретации (то есть, как для функций, так и для аргументов), на выходе формируется параллельный список кратностью, равной произведению кратностей разметок его входных дуг. Порядок следования элементов сформированного параллельного списка определен таким образом, что функция выступает в качестве приоритетного параметра независимо от префиксной или постфиксной формы записи:
Правила эквивалентных преобразований и интерпретации списков тесно взаимосвязаны с набором предопределенных функций. Их комбинации определяют широкие возможности по формированию структуры функциональной параллельной программы.
Выводы по главе 2
1. Представляемая функционально-потоковая модель параллельных вычислений задает неявное управление данными и ресурсами. Для задания программы достаточно только описать ее информационных граф. Использование модели в качестве основы языка программирования позволяет создавать архитектурно независимые параллельные программы.
2. Предложена модель, описывающая динамику поведения функционально-параллельных программ в виде информационно-управляющего графа построенного на основе информационного графа функционально-потоковой модели параллельных вычислений. В результате анализа методов управления узлами в ФП модели вычисления разработаны методы наложения управляющих воздействий, обеспечивающих неявное управление вычислениями на основе заданного информационного графа,
3. Определены принципы трансформации информационно-управляющего графа в процессе вычислений. Разработаны обобщенные алгоритмы функционирования узлов модели.
Описание протокола взаимодействия процессов при передаче результатов
Все процессы в одной точке распараллеливания используют одну очередь сообщений. Эта очередь является общим разделяемым ресурсом (критическим ресурсом). Доступ к очереди регулируется на уровне ядра Тем не менее, существует вероятность возникновения ситуации взаимоблокировки. В этом случае необходимо обеспечивать синхронизацию процессов. Для регулирования доступа к очереди создаются 3 семафора (seml,sem2,sem3): первый показывает, свободен ли серверный (принимающий) процесс (0-свободен), второй и третий служат для взаимодействия серверного процесса и текущего работающего с ним клиента. Они регулируют передачу больших списков, которые целиком не помещаются в очереди. Алгоритм синхронизации процессов при сборке результатов L В начальный момент времени все семафоры установлены в 1 -состояние занят. 2. Если сервер готов принимать результаты он сбрасывает semi (semil=0 - состояние свободен) и ждет равенства sera2 нулю. 3. Клиент захватывает сервер (semi = 1), пишет в очередь порцию данных и устанавливает sem2 = 0. Если у него есть еще порция данных, то он ждет sem3 = 0. 4. Сервер получает порцию результата, и если это не все данные от этого клиента, то sem3 = 0, если все, то на шаг 2.
Структура сообщения повторяет структуру фишки для несписковых данных, В ней содержится два дополнительных поля - порядок и размер. Поле "порядок" содержит идентификатор процесса, передающего сообщение, и служит для правильного порядка сборки сообщений в результирующем списке. Поле "размер" для списка содержит размер списка и -1 для скалярных значений.
Передача списков происходит следующим образом: 1. Передается сообщение с размером списка; Ъ По протоколу, описанному выше, передаются элементы списка В случае, если результат содержит задержанный список, передается не сам список, а его номер. Серверный процесс по этому номеру выбирает указатель на выражение из объектного представления.
Интерпретатор реализован в виде исполняемого файла, запускаемого из командной строки, в которой передаются все необходимые параметры: - файл на языке XML с промежуточным представлением, созданный транслятором; - имя функции, запускаемой на интерпретацию; - параметры, определяющие уровень параллелизма» в настоящее время используется два параметра: Р - задание уровня параллелизма; # L—управление глубиной рекурсии. Возможными значениями параметра Р, определяющего уровень параллелизма, являются: 1. Р=0 - последовательная интерпретация функциональной программы; 2. Р=1 - параллельная интерпретация списка функций в функциональной части операции интерпретации; 3. Р=2 - параллельная интерпретация в случае, если аргумент является параллельным списком, а функция не является элементарной операцией.
Если функция на входе операции интерпретации является рекурсивной, то второй параметр L задает глубину рекурсии, до которой происходит распараллеливание с порождением новых процессов. Пока эти оценки формируются вручную. В дальнейшем планируется ввести в транслятор блок оценки сложности функций и формировать ряд указанных параметров автоматически, используя их для принятия решений по управлению параллелизмом.
Пример запуска. interpr detlYLxml -F dctM -P 2 -L1 где detM-xml - оттранслированное объектное представление программы в XML формате, параметр F - задает запускаемую на нтерпретацию начальную функцию, в данном случает это функция detM.
