автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Разработка методов выполнения функционально-параллельных программ на основе сетей Петри

На правах рукописи

КАЛИНИЧЕНКО БОРИС ОЛЕГОВИЧ

РАЗРАБОТКА МЕТОДОВ ВЫПОЛНЕНИЯ ФУНКЦИОНАЛЬНО-ПАРАЛЛЕЛЬНЫХ ПРОГРАММ НА ОСНОВЕ СЕТЕЙ ПЕТРИ

Специальность 05.13.18 - Математическое моделирование, численные методы и комплексы программ

Автореферат

диссертации на соискание ученой степени кандидата физико-математических наук

Москва - 2005

Работа выполнена в Московском государственном горном университете

Научный руководитель:

доктор технических наук, профессор СЕРГЕЙ АЛЕКСЕЕВИЧ РЕДКОЗУБОВ

Официальные оппоненты:

доктор физико-математических наук, профессор

АЛЕСАНДР ВАСИЛЬЕВИЧ СТЕПАНОВ кандидат физико-математических наук, доцент НИКОЛАЙ ДМИТРИЕВИЧ СИМАЧЕВ

Ведущая организация:

Институт проблем управления РАН им. академика В.А. Трапезникова

Защита состоится «10» ноября 2005 года в 15 часов на заседании диссертационного совета Д212.128.02 в Московском государственном горном университете (119991, Москва, Ленинский проспект, д.6).

С диссертацией можно ознакомиться в библиотеке МГГУ

Автореферат разослан « октября 2005г.

Ученый секретарь диссертационного совета кандидат технических наук, доцент

Адигамов А.Э.

йоой-ч

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

з

2/?

Актуальность. Использование параллельных вычислений связано с созданием систем программирования и архитектур, существенно отличающихся от тех, что применяются при последовательной обработке данных. Существуют различные подходы к разработке параллельных программ и их выполнению.

Исторически сложившаяся практика разработки систем программирования, ориентированных на поддержку конкретных архитектур, несмотря на эффективное решение задач для различных параллельных вычислительных систем (ЛВС), привела к проблемам переносимости программного обеспечения (ПО). Ситуация усугубляется развитием неоднородных архитектур: адаптация уже существующего ПО для таких систем является неординарной задачей даже для опытных программистов.

Теория сетей Петри широко применяется для моделирования и анализа поведения распределительных вычислительных систем. В терминах сетей Петри достаточно адекватно выражаются многие важные явления параллельных вычислений, такие как взаимное блокирование процессов, состязательное распределение ресурсов, взаимное исключение доступа к ресурсам и другие.

Такие системы параллельной обработки информации, как многопроцессорные вычислительные машины, параллельные программы, моделирующие параллельные дискретные системы и их функционирование, мультипрограммные операционные системы, асинхронные электронные схемы и другие моделируются при помощи сетей Петри.

Развитие теории сетей Петри проводилось по двум направлениям. Прикладная теория сетей Петри связана главным образом с применением сетей Петри к моделированию систем, их анализу и получающимся в результате этого глубоким проникновением в моделируемые системы. Это требует хорошего знания предметной области применения, сетей Петри и методов теории сетей Петри. Чистая теория сетей Петри занимается разработкой основных средств, методов и понятий, необходимых для применения сетей Петри, для чего необходим прочный теоретический фундамент.

Помимо этого аппарат сетей Петри обладает большой гибкостью, позволяющей осуществлять моделирование параллельных вычислений в различных семантиках. В теории параллельных вычислений наиболее употребительными являются семантики чередования и частичного порядка. В семантике чередования параллельное вычисление представляется последовательностью действий, в которой параллельное выполнение нескольких действий подменяется недетерминированным выбором порядка их выполнения. В семантике частичного порядка на множестве действий устанавливается птыпщгнир—частичного порядка, отражающее причинно-следственны! мости между

событиями. Параллельно выполняемые действия при этом оказываются несравнимыми. Семантика чередования находит отражение в последовательностях срабатывания переходов сети, семантика частичного порядка приводит к рассмотрению специального класса так называемых сетей происшествий, отражающих упорядоченность событий. Каждая из упомянутых семантик обладает своими особенностями и достоинствами, и поэтому в целях наиболее полного анализа поведения распределенных систем необходимо иметь разработанную технику перехода от одной семантики моделирования параллельных вычислений к другой.

В моделировании и исследовании поведения сложной распределенной системы большую трудность представляет задача 1

синтезирования всей глобальной информации о системе по времени, когда известна информация о каждом подпроцессе и нет буферной памяти для ее запоминания. Поэтому разработка необходимого формализма в сетях Петри для распределенных систем для определенного класса является актуальной.

Попытки создания инструментальных средств, обеспечивающих переносимость параллельных программ, предпринимались неоднократно и осуществлялись по нескольким направлениям. Все они, тем или иным образом, связаны с написанием программ для некоторой обобщенной архитектуры. Выполнение таких программ на ПВС осуществляется после их предварительного преобразования с использованием специализированных средств распараллеливания (десеквенторов). Одним из вариантов классификации методов десеквенции является деление по способам представления исходного параллелизма:

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, ccNUMA, МРР и кластерные архитектуры. Анализируется динамика развития современных суперкомпьютеров за последние 5 лет по материалам официального списка 500 самых производительных компьютеров (www.top500.org). По результатам общего анализа обосновывается выбор МРР и кластерной архитектуры для проведения исследований по созданию среды выполнения функционально-параллельных программ. Одним из основных критериев выбора является масштабируемость ПВС. Основной акцент делается на однородную кластерную архитектуру, как более доступный вариант МРР систем. Далее в главе формулируются подходы к исполнению ФП программ. Делается

вывод о предпочтении реализации эмулирующей исполняемой среды для проведения исследований модели вычисления и функционального языка параллельного программирования.

Для выбранной архитектуры анализируются библиотеки и инструментальные средства (MPI, PVM, T-System, MOSIX), реализующие различные стратегии управления распределенными вычислениями. Обосновывается выбор средств для организации выполнения функционально-параллельных программ.

Предлагается модель, описывающая поведение ФП программ, построенных на основе функционально-потоковой модели вычислений. Функционально-потоковая модель задает программу в виде i

информационного графа, обладающего рядом специфических особенностей. В основе лежит управление по готовности данных, определяемое для процессов, протекающих внутри бесконечных ресурсов. Это позволяет описать параллелизм задачи без ресурсных конфликтов. Выбор набора операций и аксиом, определяющих набор примитивов, ориентирован на наглядное текстовое представление информационного графа. Первое требование обеспечивает ресурсную независимость предлагаемой модели, что позволяет описать максимальный параллелизм, ограниченный только информационными связями, присущими данной задаче.

Во второй главе для описания предлагается информационно-управляющая ресурсная модель, задающая динамику функционирования вычислений. Используется представление вычислительного процесса в виде суперпозиции трех графов: информационного, управляющего и ресурсного. Исходя из того, что в функционально-потоковой модели управление ресурсами осуществляется неявно, в работе рассматривается только её информационно-управляющая составляющая.

Информационно-управляющий граф формируется наложением на информационный граф схем управления вычислениями вдоль информационных связей и задает управление в каждом из узлов программы с их последующим связыванием.

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

M = (G,GmP,PmS,eSM),

где G, - информационный ориентированный ациклический граф, задающий структуру программы, Gm - граф управления, Р, - набор правил, определяющих динамику функционирования модели (механизм формирования и распространения разметки по информационному графу), Рга - механизмы формирования и распространения разметки по графу управления, Бю - начальная разметка информационного графа, S„,o - начальная разметка управляющего графа. Информационный граф определяется как

где V - множество вершин определяющих программо-формирующие

операторы, а А - множество дуг, задающих пути передачи информации между операторами графа.

Управляющий граф определяется как

где Ут - множество вершин, соответствующих элементам управления, а Ат-множество дуг, задающих потоки управления.

Далее в главе представлены разработанные правила срабатывания и алгоритмы интерпретации узлов модели, которые описывают формирование разметок на выходных информационных и управляющих дугах для каждого из используемых операторов.

Примеры основных операторов модели:

Оператор интерпретации (рис. 1) описывает функциональное преобразование аргумента. Имеет два входа, на которые, через информационные дуги поступают некоторая функция Б и аргумент X. Управляющий граф оператора видоизменяется в зависимости от типов входных данных, появляющихся на его информационном и функциональном входах.

5Х и Бр - сигналы готовности на информационном и функциональном входе соответственно. Срабатывание операции интерпретации определяется появлением этих сигналов. В результате на выходе операции появляется выходная разметка.

I

V,. ФУ

Рис. 1 - Обобщенный граф управления вычислениями в операции интерпретации

Конструкция, обеспечивающая массовый параллелизм параллельный список. В текстовом виде группировка в параллельный список задается ограничением его элементов квадратными скобками "[" и "]". С точки зрения управления узел интерпретируется как упорядоченный набор независимых элементов. Каждый элемент списка может обрабатываться независимо по мере готовности данных (появление сигнала готовности рис. 2). В соответствии с графом управления, при поступлении на вход операции интерпретации параллельного списка, производится интерпретация независимых элементов X, и Б (рис. 2). На рисунке демонстрируется пример вычисления функции от

параллельного списка [х].Р*[х, ,Р,Хг :Р,..Л„ :р\ где X - Х,,Х2,.--,Хп. Результат будет сгруппирован в параллельный список в соответствии с рангом входных данных.

'¡Г. 5»х

1111 тттт

• • л

\7

Р

5, Л» 5,

Х.\' '/,( Хг. \ • I' Р

(Х,ГД,'Г, ..ХлГ]

Х= [ХЛ „Хп! [X]:" —[Х,^, Дп-Р)

Рис. 2 - Информационно-управляющий граф вычисления операции интерпретации при поступлении на информационный вход

параллельного списка.

Задержанный список - оператор, обеспечивающий организацию откладываемых (задержанных) до определенного момента вычислений. Ограниченные оператором задержки вершины, представляющие другие операторы, не могут выполняться даже при наличии всех аргументов. Их активизация возможна только при снятии задержки.

Для всех узлов модели представлены обобщенные алгоритмы срабатывания.

В третьей главе предлагается новая формализация - сеть, обобщающая в себе положительные свойства сетей Петри, числовых и трансформационных сетей и лишенная вышеперечисленных недостатков.

Определение 1. Сетью называется тройка <8,Т,Р>, где Б -множество мест, Т - множество переходов, а Fe(Sx7')^J(Гx.s)-oтнoшeниe достижимости. При этом мы полагаем 5'о7' = 0 Тсс1от(р)глсос1от(р). Для всякого элемента г е 5 и Г положим г° = \'/грг\ "г = {г'У'^А-

Определение 2. Сеть К=<8,Т,Р> назовем сетью происшествий, если транзитивное замыкание Р* отношения Р иррефлексивно, и для всякого места ¿е 5 имеет место < 1, |.у°| .< 1 Для удобства отношение Р будем представлять иногда в виде функции Г: (5хт)и(т х 5) -> {ОД}.

Определение 3. Сетью Петри назовем четверку N = <8,Т,Р,М>, состоящую из сети <8Т,Р> и разметки М: 5 (0,1,2,...), указывающей количество фишек, помещенных в каждое место сети.

Пусть М - произвольная разметка сети К. Переход/е Т назовем М-активным, если М(8)>0 для любого В этом случае разметку М' такую, что М'(8)=М(8)-Р(8,1)+Р(1,з) для любого!е5 назовем и приемником М.

Последовательностью срабатывания переходов (Р-

последовательностъю) сети Петри К=<8,ТР,М> назовем конечную или бесконечную последовательность •■■, для которой существует

последовательность разметок М°, М1, М2,... такая, что М°=М, и для каждого ¡, ¡>0 переход 1, является М'-активным, а М'"1 является I,-приемником М'. Множество всевозможных Р-последовательностей сети Петри N обозначим Ь(М). Это множество определяет функционирование сети Петри в семантике чередования.

Для заданной сети Петри N = <8,ТР,М>, сети происшествий ¥ =<И,Т,Р>и функции маркировки р:§иТ ->5иГпару я =<Ы,р> назовем процессом, если выполнены следующие условия:

(»>!■ е 5, ,где50 = {*'<= V =

Переходы Т в процессе л мы будем называть происшествиями. На множестве происшествий процесса ж=<Ы,р> введем отношение строгого частичного порядка -<а„, полагая, ^ «(/¡,г!,)е Г<". Частично

упорядоченное множество ¥,-<, будем называть характеристикой процесса ж. Два процесса л-, =< БиТ„Р1,р1 >и я} -<§2,Т2,Рг,р2 >сети Петри N назовем сильно-эквивалентными, если существует биекция ->Г2такая, что

(«/)*/',/■ 6 7;:/' -<ч,/' о /(/'К, /И-

Нетрудно заметить, что каждый класс сильной эквивалентности процессов сети Петри N однозначно определяется характеристикой любого процесса этого класса.

Указанную выше функцию маркировки р мы будем обозначить пате, а множество всевозможных процессов сети Петри N будем

обозначать П(Ы). Функционирование сети Петри в семантике частичного порядка определяется совокупностью характеристик процессов из П(Ы)-

Сеть Петри представляет модель распределенной системы, в которой переходы сопоставлены задачам, а места - ресурсам, необходимым для решения задач. Тогда функционирование всей системы может быть описано либо последовательностью срабатываний переходов (семантика чередования), либо отношением порядка на множестве происшествий процесса (семантика частичного порядка). Одной из задач в теории сетей Петри является установление взаимосвязи между этими двумя формализациями вычислений распределенных систем.

Для последовательности происшествий р = (,, /2,... процесса я=< А',/;» будем полагать р(/?)=р(/Д/з(/2),... Тогда для заданных Р-последовательности а и процесса я сети Петри N обозначим: Ш(я)=^\а = гште(р)}, где р- линейное упорядочение

множества Т отношением Ргос,,(а)= {?г|аг е ¿ш(л-)}.Справедлива следующая

Теорема 1. Для заданной сети Петри N и последовательности переходов а включение а е ¿(А')справедливо в том и только том случае, когда а е Ш{л) для некоторого процесса п е я(//)

Для более точного изучения взаимосвязи Б-последовательностей и процессов сетей Петри введем ряд новых понятий.

Для заданного множества переходов А обозначим /Г/Г совокупность всех конечных (соответственно, бесконечных) последовательностей элементов А. Положим А" = А' и А". Пустую последовательность обозначим е, а множество всех префиксов последовательности ае Л" обозначим РгеДа) Для а в А" и а е ^обозначим #аа число вхождений элемента а в а и будем полагать 0(а)={(а,1) |# аа >0 и 0<1<# аа +1}.

Причинной зависимостью на А будем называть всякое рефлексивное бинарное отношение ОсАу.А. Для заданной последовательности ае А" причинная зависимость Б порождает частично упорядоченное множество 0{а\^аи, где <а0рефлексивное и транзитивное замыкание отношения «, определенного следующим образом: (а,п)«(Ь,т) тогда и только тогда, когда п-ое вхождение а в а предшествует т-ому вхождению Ь и при этом (а,Ь)е £>. Далее, для заданной причинной зависимости Б введем на множестве А" отношение частичного порядка <0 полагая, что для любой пары а,р е Л" сравнимость а р имеет место тогда и только тогда, когда ф) = 0(/?)и

Пример 1. Пусть А= {а,Ь}, 0={(а,а), (Ь,Ь), (Ь,а), {а) = (ааЪЬ)" = ааЬЬааЪЪ...,/} = {аЬУ =аЬаЬ... Тогда а<0 Р.

Для заданного отношения причинности Б на множестве переходов А определим систему переписывания слов (А,Р), где Ра = {аЬ Ъа\{а,ь) е

Теорема 2. (¡) Если ар е А', то а -<п ртогда и только тогда,

когда а-* р.

(И) Если ар € А", то a <D р тогда и только тогда, когда 0{a)=0(fi)v, при этом V/?' е Рге#(д)Ва' е ?ref(afiy е А':|а'4/?У|.

На множестве А" с фиксированной причинной зависимостью D определим отношение эквивалентности s0, полагая a=D р тогда и только тогда, когда -Из теоремы 2 следует

а ш р о а_Д_,а.

Мы будем рассматривать отношение причинной зависимости Dn между переходами, определяемое сетью Петри N=<S,T,F,M>

Dn= {(t,t)|teT}«

Теорема 3. Для всякой сети Петри N=<S,T,F,M> -последовательности а е L(n)vl процесса л- =< (S,o(a\F,p >е РгосЛ,а-отношение на множестве 0(a) не превосходит отношения <a,DN,т.е.

Из теоремы 3 следует, что для заданной F-последовательности a некоторая информация о структуре процессов п е Ргосл.(аг)может быть извлечена на основе анализа отношения ч a,DN.

Пример 2. Для сети Петри N, изображенной на рис. 3, причинная зависимость определяется множеством DN= {(а,а),(Ь,Ь),(Ь,а)}. Рассмотрим F-последовательность a=(ab)*. Тогда ProcN(a) содержит единственный процесс л, изображенный на рис. 4, причем о(а),~<ат является его характеристикой.

Теорема 4. Пусть а■<т р для некоторой сети Петри N, и а е L(n). Тогда P<lL{n)v Ъос„(а)с?гос,(р)

Рис. 3. Причинная зависимость сети Петри В дальнейшем мы ограничимся рассмотрением специального класса сетей Петри - так называемых сетей без самоконкурирующих переходов. Будем говорить, что переход I в сети N является самоконкурируюгцим, если существует процесс в котором происшествия (1,1),

несравнимы по отношению для некоторой пары различных натуральных чисел у. В частности, так называемые 1-безопасные сети Петри, в которых каждое место может быть размечено не более чем одной

фишкой, не содержат самоконкурирующих переходов. При этом класс сетей Петри без самоконкурирующих переходов охватывает также все сети, в которых для каждого перехода I существует место Б такое, что {г}и М(*)<>\.

Теорема 5. Если сеть Петри N не содержит самоконкурирующих переходов и а е £(#), то

геРг ос* (а)

Можно отметить, что теорему 5 нельзя распространить на класс всей сети Петри.

Рис. 4. Р-последовательность процесса п.

Теорема 6. Если сеть Петри N не содержит самоконкурирующих переходов и а,/?е£(Аг)то Ргос»(а)=Ргосы((3), тогда и только тогда, когда а а р.

Теорема 7. Если сеть Петри N не содержит самоконкурирующих переходов, то для любой Р-последовательности <х е ¿(л^все процессы в Ргосм(а) сильно-эквивалентны тогда и только тогда 0{а\^аШ является их характеристикой.

Таким образом, семантики чередования и частичного порядка совпадают для ограниченного класса сетей, включающего 1-безопасные сети.

В распределенной вычислительной сети рассмотрим состояние системы в момент действия процесса вычисления. Состояние системы в какой-то момент времени состоит из состояния локальных процессов в этот момент и состояния в каналах связи сети.

Самая трудная проблема в анализе процесса вычисления сети - это как отличить соотношение порядка появления двух каких-нибудь событий, когда два события имеют причинно-следственные отношения друг к другу и когда они конкурентны между собой. Таким образом,

кооперирование, сравнение и синхронизация между процессами в асинхронном сообщении крайне затруднено, если в системе нет понятия общего основного времени системы - ЬХатроП ввел это понятие, названное им логическими часами. Хотя логические часы ЬатроЛа описывают причинно-следственный характер между событиями, однако они оказались достаточно неэффективны для решения некоторых задач: задачи исключения параллельных сообщений или оценки глобального состояния системы.

Пусть {рь р2, ..., рп} есть распределительный способ вычисления, обладающий п процессами. Структура векторных часов для распределенной системы такова: время ставится в соответствие с событиями и регистрируется векторными часами, принадлежащими № такие часы называют векторными часами порядка п.

Пусть, каждый процесс р„ имеет часы их значения принадлежат Ы". Начальное значение 0, есть (О, О, ...О) и после свершения каждого события р„ ¡-тая компонента 0, повышается на 1 до появления любого события на Р,.

Как в схеме Ьашройа, каждое сообщение т из р, имеет временную метку точно соответствующую значению 0, .когда сообщение т послано. Получение сообщения, обозначенного временной меткой через ^ процесс воспринимает его время как:

0, =шах(0„1). Наконец, для любого события а, мы приписываем векторное время

Ъ(а)~ 0, (а), если событие а появляется в р;.

Показано, что для любого события а, 0(а)[^- есть именно число событий от р, появившихся до события а: = |с, п(4- а].

Это утверждение есть основное свойство при доказательстве того, что 0 характеризует конкуренцию между событиями.

Теорема 8. Если 9: С Л" есть векторные часы, характеризующие конкуренцию, то т>п, где п - число процессов в распределительной системе.

Рассмотрим конкретную модель распределенной системы как сеть процессов, соединенных каналами связи, по которым могут быть посланы сообщения. В такой системе имеются 3 типа событий: 1) посылки сообщения, 2) получения сообщения; 3) внутренние события в процессе.

В результате того, что каждый процесс локализован и каждое событие появляется в одном процессе, то в принципе мы можем наблюдать полное состояние этого процесса в любой момент времени

Если принять в рассмотрение "ннтерливинговую" модель функционирования параллельных и распределенных систем, где частичный порядок событий в системе представляется множеством всех возможных порядков этих событий, то при одновременной готовности нескольких компонентов параллельной системы к выполнению переходов в каждом конкретном вычислении случайно выбирается ровно один

переход системы в новое глобальное состояние. Если некоторое конкурирующее с выбранным действие (переход) т независимо от выбранного, то в новом глобальном состоянии готовое к выполнению (активное) действие т снова будет активно и может быть выбрано в качестве очередного действия системы.

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

Для определения глобального состояния распределенной системы предлагается понятие временного сечения. Его основная идея заключается в том, что временное сечение рассматривается как разделение событий на два множества: первое множество содержит события, появляющиеся до временного сечения, а второе множество содержит события, появляющиеся после временного сечения. Частичный порядок описывает временное упорядочение событий (_)

Определение 4. Конечное множество В событий называется временным сечением, если выполняется следующее: если ее В и / -» е, то feB.

Предложен алгоритм определения временного сечения.

Разработана модель распределенной вычислительной системы в виде временной алгебры, где для удобства описания поведения системы введено понятие размеченной переходной системы.

Определение 5: Размеченной переходной системой называется тройка Р = {в, ->,Л) где 9 - множество конфигураций; А -множество меток, и в* Ах в- переходное отношение.

Распределенная вычислительная система в данном рассмотрении состоит из атомарных процессов, не имеющих общей памяти и работающих совместно с посылкой сообщений в каналах связи, где сеть связи предполагается связанной.

В четвертой главе рассматривается один из вариантов реализации экспериментальной системы интерпретации функционально-параллельных программ, реализованный на базе кластерной архитектуры под управлением ОС Linux с поддержкой системы динамического распараллеливания MOSIX. Интерпретатор реализует виртуальную машину с трехуровневой архитектурой и является составной частью технологической цепочки, обеспечивающей выполнение функционально-параллельных программ.

За основу организации процесса параллельной интерпретации берется метод последовательно-параллельной интерпретации в системе с ресурсными ограничениями.

Создание интерпретатора обеспечивает решение следующих задач:

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

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

Полученная система представляет собой лабораторный макет, допускающий гибкую настройку, возможность быстрой модификации в условиях развития ФЯПП. Система позволила провести анализ эффективности разработанной трехуровневой модели виртуальной машины. Полученные результаты показали способность такой системы обеспечивать сбалансированную загрузку узлов кластера

Проводился предварительно анализ особенностей системы MOS IX и модели интерпретации, который позволил оценить узкие места в параллельной интерпретации и предложить варианты их решения.

Для организации экспериментов и тестирования эффективности работы интерпретатора была реализована кластерная система под управление ОС Linux с введенной в ядро системы поддержки динамического распараллеливания MOSIX.

ЗАКЛЮЧЕНИЕ

В диссертационной работе исследованы и разработаны новые методы параллельного программирования на основе сетей Петри. Основные выводы и результаты диссертационной работы, полученные лично автором:

1. Предложена модель, описывающая динамику поведения функционально-потоковых параллельных программ. Разработаны обобщенные алгоритмы функционирования узлов модели. Разработаны методы наложения управляющих воздействий, обеспечивающих неявное управление вычислениями на основе заданного информационного графа.

2. Доказана основная теорема, где установлены необходимые и достаточные условия, при которых процессы сетей Петри однозначно восстанавливаются по заданным последовательностям срабатывания переходов. Тем самым показано взаимнооднозначное соответствие распределенной системы, функционирование которой описано либо в семантике чередования последовательности срабатываний переходов, либо в семантике частичного порядка на множестве происшествий процесса.

3. Разработана модель описания поведения параллельных и распределенных вычислительных систем па основе предложенной распределенной переходной системы с целью определения глобального состояния всей распределенной системы с использованием векторных логических часов между событиями и отсутствия общей буферной памяти в системе.

4. Разработан алгоритм сохранения глобальной информации в моделируемой распределенной системе вычислений без буферизации на основе предложенной процедуры временного сечения и векторного логического времени.

5. В рамках создания функционального языка параллельного

программирования предложены функции, обеспечивающие параллельное выполнение независимых модулей (программ) и позволяющие использовать ФП язык, как язык управления крупноблочным распараллеливанием, а в комбинации с реализованной интерпретирующей средой, как систему управления для кластерной архитектуры.

Основные результаты диссертации опубликованы в работах

1. Калиниченко Б.О. О восстановлении сети процесса по последовательности срабатываний переходов сети Петри.// Международный сборник научных трудов, вып 17. Изд. «Научная книга», Воронеж, 2004, С.58-66.

2. Калиниченко Б.О., Редкозубое С.А. Фундаментальный подход к оценке результатов наблюдения.// Труды международной научно-технической конференции «Транском-2004». Санкт-Петербург, 2004. С. 264-269

3. Калиниченко Б.О. Стохастическая оптимизация в задаче размещения на сетях Петри.// Материалы отчетной научной конференции профессорско-преподавательского состава ВИВТ за 2004-2005 гг., Вып. 3. Воронеж: Воронежский институт высоких технологий, 2005. С.51 -53

4.. Калиниченко Б.О. Представление генетических алгоритмов сетями Петри в задаче размещения.// Материалы отчетной научной конференции профессорско-преподавательского состава ВИВТ за 2004-2005 гг., Вып. З.Воронеж: Воронежский институт высоких технологий, 2005. С.53-55

5. Калиниченко Б.О. Семантика чередования и частичного порядка в сетях Петри.// Труды седьмого Всероссийского симпозиума по прикладной и промышленной математике. Ж «ОП и ПМ», М, 2005, С. 586-588

6. Калиниченко Б.О. Функционально-потоковая модель параллельного программирования.// Труды седьмого Всероссийского симпозиума по прикладной и промышленной математике. Ж «ОП и ПМ», М, 2005, С. 588-590.

Подписано в печать Формат 60x90/16

Объем 1 п. л. •■ Тираж 100 экз. Заказ № ///£

Типография Московского гссударстсенного горного университета. Москва, Ленинский проспект, 6.

IH18 179

РНБ Русский фонд

2006-4 13331

ВВЕДЕНИЕ

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

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

1.2.Выбор архитектуры для проведения исследований по созданию среды выполнения программ, написанных на языке функционально-параллельного программирования

1.3.0бщие подходы к реализации исполнения ФП программ

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

1.5.Выбор среды для построения эмулирующей системы

Глава 2. Управление вычислениями в функционально-потоковой модели 2.1.Описание динамики вычисления функционально-потоковой модели

2.2.Программо-формирующие операторы

2.3.Правила срабатывания операторов

2.4.Влияние эквивалентных преобразований на формирование информационно-управляющего графа

Глава 3. Последовательность срабатываний переходов в сетях Петри и связанные с ней проблемы

3.1.Некоторые аспекты теории сетей и основные определения

3.2.Выражение предиката (ргех) и поведение сетей Петри

3.3.Последовательности срабатываний переходов в сетях Петри и параллелизм внутри них

3.4.Распределенная система вычислений

3.4.1.Некоторые определения и понятия

3.4.2.Методы описания распределенных систем вычисления

3.4.3.Распределенная система вычисления

3.4.4.Алгоритм сохранения глобальной информации 140 системы в локальном состоянии процесса

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

4.1 Реализация последовательно-параллельного 146 интерпретатора с использованием системы динамического распараллеливания MOSIX

4.1.1 Структура интерпретатора

4.1.2 Описание входного представления

4.1.3 Общий алгоритм работы интерпретатора

4.1.4 Алгоритм параллельной интерпретации

4.1.5 Алгоритм эквивалентных преобразований списков

4.1.6 Описание протокола взаимодействия процессов при 157 передаче результатов

4.1.7 Описание входных параметров командной строки 158 интерпретатора

4.2 Оценка интерпретации ФПП

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 наименований.

Выводы по главе 4

1. Разработка интерпретатора обеспечила практическую поддержку экспериментов, связанных с исследованием параллельного выполнения функциональных программ, написанных на ФП языке программирования. Полученные результаты показывают, что использование многоуровневой архитектуры виртуальной машины в системе выполнения ФП программ позволяет обеспечивать сбалансированную загрузку узлов кластера под управлением ОС Linux с поддержкой MOSIX. Параллельная интерпретация позволила повысить производительность вычислений по сравнению с последовательным выполнением одних и тех же задач (в идеальных условиях, когда число используемых узлов кластера было больше числа одновременно выполняющихся «тяжелых» функций).

2. Программы, написанные на ФП языке программирования, и оттестированные на последовательном интерпретаторе выполнялись на параллельном интерпретаторе без модификации кода и достигали эталонных результатов решения.

3. Полученные данные позволяют определить направления дальнейших работ по повышению эффективности интерпретатора, улучшению транслятора и модификации языка программирования.

ЗАКЛЮЧЕНИЕ

В диссертационной работе исследованы и разработаны новые методы параллельного программирования на основе сетей Петри. Основные выводы и результаты диссертационной работы, полученные лично автором:

1. Предложена модель, описывающая динамику поведения функционально-потоковых параллельных программ. Разработаны обобщенные алгоритмы функционирования узлов модели. Разработаны методы наложения управляющих воздействий, обеспечивающих неявное управление вычислениями на основе заданного информационного графа.

2. Доказана основная теорема, где установлены необходимые и достаточные условия, при которых процессы сетей Петри однозначно восстанавливаются по заданным последовательностям срабатывания переходов. Тем самым показано взаимнооднозначное соответствие распределенной системы, функционирование которой описано либо в семантике чередования последовательности срабатываний переходов, либо в семантике частичного порядка на множестве происшествий процесса.

3. Разработана модель описания поведения параллельных и распределенных вычислительных систем па основе предложенной распределенной переходной системы с целью определения глобального состояния всей распределенной системы с использованием векторных логических часов между событиями и отсутствия общей буферной памяти в системе.

4. Разработан алгоритм сохранения глобальной информации в моделируемой распределенной системе вычислений без буферизации на основе предложенной процедуры временного сечения и векторного логического времени.

5. В рамках создания функционального языка параллельного программирования предложены функции, обеспечивающие параллельное выполнение независимых модулей (программ) и позволяющие использовать ФП язык, как язык управления крупноблочным распараллеливанием, а в комбинации с реализованной интерпретирующей средой, как систему управления для кластерной архитектуры.

1. Воеводин, В.В, Параллельные вычисления / В,В, Воеводин, Вл.В. Воеводин СПб/. БХВ-Петербург. - 2002. ~ 608 с.

2. Крюков, В.А, Разработка параллельных программ дм вычислительных кластеров и сетей // В. А. Крюков "Информационные технологии и вычислительные системы". - 2003. - № 1-2. - С. 42-61.

3. Вальковский, В.А. Распараллеливание алгоритмов и программ. Структурный подход / В.А» Вальковскай-Мл Радио и связь. -1989. -176 с.

4. Алгоритмы, математическое обеспечение и проектирование архитектур, многопроцессорных вычислительных систем / Под ред. А.П. Ершова. М.: Наука.-1982 - 336 с.

5. Хоар, Ч. Взаимодействующие последовательные процессы / Ч. Хоар; пер. с англ.-М.: Мир, 1989.—264 с.

6. Лсгалов, А.И. Стратегии управления вычислениями /А,И. Лсгалов // В кн.; Проблемы техники и технологий XXI века. Материалы научной конференции. Красноярск, КГТУ. -1994. С. 122-126.

7. Легалов, А.И. Управление в вычислительных системах и языках программирования. / А.И. Легалов // Материалы конференции "Проблемы информатизации города". Красноярск. -1994. С. 198-202.

8. Антонов, А. С. Эффективная адаптация последовательных программ для современных векторно-конвеисрных и массивно-параллельных СуперЭВМ / А. С Антонов, В. В. Воеводин // Программирование. 1996. - X» 4. -С. 37-51.

9. Джоунз, Г. Программирование на языке Оккам / Г. Джоунз; пер. с англ. -М.: Мир, 1989.- 208 с.

10. Лацис, А.О. Разработка ОС коллективного использования для многопроцессорной супер-ЭВМ МВС 100/А.О. Лацис // Транспьютерныесистемы и их применение: Тез. докл. Всероссийск. науч. конф. М.: ИПМ им. Келдыша. -1995. - С. 17-24.

11. Легалов, А.И. На пути к переносимым параллельным программам / А.И. Легалов, Ф.А. Казаков, Д.А, Кузьмин, Д.В. Привалихин // Открытые системы. 2003, - № 5.— С. 36-42.

12. Чиди, Д. ASCI White впереди планеты всей / Д. Чиди // Открытые системы: Еженедельник «Computerword». 2000. — jf« 42. ~ http://www.osp.nl/cw/2000/42/0060.htm

13. Бэкус, Дж. Алгебра функциональных программ: мышление функционального уровня» линейные уравнения и обобщенные определения // Математическая логика в программировании: Сб. статей / Дж. Бэкус; пер. с англ.-М.: Мир.-1991. С.8-53.

14. Хендерсон, П. Функциональное программирование. Применение и реализация. / П. Хендерсон; пер. с англ. М.: Мир. -1983. - 349 с.

15. Маурер, У. Введение в программирование на языке ЛИСП / У. Маурер М.: Мир. -1976. - 104 с.

16. Пеплер, П. Функциональный подход к разработке программ с развитым параллелизмом / П. Пеппер, Ю. Эксиер, М. Зюдхольд // Системная информатика. Новосибирск: ВО «Наука». 1995. - С. 334-360. Вып. 4: Методы теоретического и системного программирования.

17. Казаков, Ф.А. Параллельно-функциональный язык программирования / Ф.А. Казаков, Д.А. Кузьмин, А.И. Легалов // В кн.: Негфоинформатика и нейрокомпьютеры. Тезисы докладов рабочего семинара. Красноярск. -1993. С. 14.

18. Казаков, Ф.А. Параллельный язык управления потоков данных / Ф.А. Казаков, Д.А. Кузьмин, А.Е Легалов И Математическое обеспечение и архитектура ЭВМ: Сб. научных работ. Вып. 2. КГТУ, Красноярск. 1997.1. C. 105-113.

19. Кузьмин, ДА. Язык программирования параллельных процессов / ДА. Кузьмин, Ф.А. Казаков, А.И. Легалов // В кн. Нейроинформатика и ее приложения. Программа и тезисы докладов всероссийского рабочего семинара, Красноярск, ~ 1994. G. 203-204.

20. Kuzmin, DA. Description of parallel-functional programming language /

21. D.A. Kuzmin, F.A. Kazakov, A.I. Legalov // Advances in Modeling & Analysis, A, AMSE Press, 1995,-VoK2£-No. 3,- pp. 1-17.

22. Казаков, Ф.А. Функциональная модель потоковых вычислений / Ф.А. Казаков, ДА. Кузьмин, А.И. Легалов // В кн.: Проблемы информатизации города: Вторая тучно-практическая конференция, сб. тезисов докл. Красноярск, 1995. G. 65-67.

23. Легалов, А.И. Модель вычислений функционального языка параллельного программирования / А.И. Легалов, Ф.А. Казаков // 6-й Всероссийский семинар "Нейроинформатика и ее приложения". Тезисы докладов. Красноярск. 199В. - 1 с.

24. Кузьмин, Д.А. Интерпретация функциональных программ на кластере под управлением MOSIX / Д.А. Кузьмин, НИ. Рыженко,

25. A.И. Легалов И Вестник Красноярского Государственного Технического университете. Выпуск № 33. Математические методы и моделирование. Под редакциейВ.И.Быкова.Красноярск.ИПЦКГТУ,2003.-С. 396-205.

26. B.И. Подшивалова. Красноярск.* КГТУ. -2001. С. 66-73.

27. Водяхо» АЖ Стратегии управления вычислительными процессами и их модели / А.И. Водяхо, В.П. Емелин, А.И. Легалов // В кн.: Математическое и программное обеспечение САПР сетевых систем, Йошкар-Ола, 1985. С. 135-142.

28. Водяхо, А.И. Функционально ориентированные процессоры /

29. A.И. Водяхо, В.Б. Смолов, В.У. Плюснин, Д.В. Пузанков / Под ред.

30. B.Б. Смолова Л.: Машиностроение. Ленингр. Отделение. - 1988. - 224 с.

31. Воеводин, Вл. В. Методы описания и классификации вычислительных систем. Учебное пособие. / Вл, В. Воеводин,

32. A.П. Капитонова М.:Изд.-во МГУ.-1994,- 103 с .

33. Корнеев, В.В. Параллельные вычислительные системы /

34. B,В. Корнеев- М: «Нолидж». 1999.-320 с.

35. Кузьминский, М. Современные суперкомпьютеры: состояние и перспективы / М. Кузьминский, Д. Волков // Открытые системы. 1995. -№6.- С. 33-40.

36. Амамия, М. Архитектура ЭВМ и искусственный интеллект / Е, Амамия, Ю. Танака; пер. с японск. Мл Мир, 1993. - 400 е.,ил.

37. Шнитман, В. Электронное пособие «Современные высокопроизводительные компьютеры» / В. Шнитман Информационно-аналитические материалы Центра Информационных Технологий. - 1996. -ht^://support.vologda.ruSook/ARCmTECTURE/Svk/contents.htrn

38. Aad, J. van der Steen Overview of Recent Supercomputers // Aad J. van der Steen, Jack J. Dongarra -http://mvvv.phys.uu.nl/~euroben/reports/web03/overview.html

39. Aad, J. van der Steen Overview of Recent Supercomputers // Aad J. van der Steen, Jack J. Dongarra -http://www.top500.org/ORSC/2002/overvievv02.htmi

40. Архитектура и проектирование вычислительных систем. Распределенные вычислительные системы. // Сборник статей. ~ Рига: РПИ. -1990.- С. 14-21.

41. Pfister, G. Sizing Up Parallel Architectures / G. Pfister — DataBase Programming & Design OnLine, May 1998. Vol. 11. - No. 5.

42. Amza, C. Shared memory computing on networks of workstations, to appear in IEEE Computer Treadmarks / C. Amza, A.L. Cox, S. Dwarkadas, P. Keleher, R. Rajamony H. Lu, W. Yu, and W. Zwaenepoel // in IEEE Computer, Volume 29, Number 2, February 1996.

43. Официальный список 500 самых производительных компьютеров -http://www.top500.org

44. Информационный портал НИВЦ МГУ Лаборатории Параллельных Информационных Технологий http://www.parallei.ru

45. Кузьминский; М. Кирпичные компьютеры* Серверы нового поколения архитектуры NUMA компании SGI // М. Кузьминский — Открытые системы.- 2000, № 9,-http://www.osp.ru/os/2000/09/0W.htm

46. Коваленко, Е. Система Sequent NUMA-Q // Е, Коваленко -Открытые системы. 1997. - Лг» 2. -http://www.osp.ru/os/1997/02/6.htm

47. Головкин, Б.А. Параллельные вычислительные системы, / Б.А. Головкин -М.: Наука, Гл. ред; физ.-мат. лит. -1980. 520 с*

48. System architecture description of the Hitachi SR2201 — http;//www.hitachi.co.jp/Prod/comp/hpc/eng/srl.htrnl

49. Елизарова, Т.Г. Применение многопроцессорных транспьютерных систем для решения задач математической физики / Т.Г. -Елизарова^. Б.Н. Четверушкии // Математическое моделирование. — 1992, т. 4, - Ks 1L - С. 75-100.

50. Гольдштейн, M.JI. Мультипроцессорная вычислительная система на базе транспьютерной идеологии / М.Л. Гольдштейн // Алгоритмы и программные средства параллельных вычислений. Сб. науч. тр. Екатеринбург. УрО РАН. -1995. С. 61-68.

51. Транспьютеры. Архитектура и программное обеспечение: Пср.с анг./ Под ред. Г. Харда. МлРадио и связь. - 1993. - 304 с.

52. Андреев, И. Славянский прорыв иа информационном поле / И. Андреев // «Академия Тринитаризма». 2002. - Эл. № 77-6567, публ. 10170.

53. The Earth Simulator Center http://www.es.jamstec.go.jp

54. Уильяме, M. Япония возглавила рейтинг Тор 500 / М. Уильяме // Открытые системы: Еженедельник "Computerworld". — 2002. X» 17. -http://vvww.osp.ru/cvv/2002/17/004l .htm

55. ASCI Program Plan http://wvvw.llnl.gov/asci

56. Андреев, А. Кластеры и суперкомпьютеры близнецы или братья? / : А. Андреев, В. Воеводин, С. Жуматий // Открытые системы. - 2000. - Кч 5. -http://www.osp.ru/os/2000/05-06/009.htm

57. Митрофанов, В, Направления развития отечественных высокопроизводительных систем / В. Митрофанов, А. Слуцкин, К. Ларионов, Л. Эйсымопт. // Открытые системы, 2003. - № 6. -http://www.osp.nl/os/2003/05/029.htm

58. Орлов, С. Искусство объединения / С. Орлов // Открытые системы: «LAN». 2003. ~ Хй 9. - http://www.osp.Tu/ian/2003/09/072Jrtm

59. Уильяме, М. Кластер Apple третий в Тор500 If М. Уильяме -Открытые системы: Еженедельник "Computerworld". - 2003. - М 47. - : http://www.osp.ru/cw/2003/47/028l.htm

60. Анненков, В.А. Анализ производительности межпроцессорного обмена в МВС 1000М / В.А. Анненков, Е.А. Нурминский, С.В. Смирнов // // «Информатика и системы управления». - 2002. - № 2. - С. 3-12.

61. Гедца, Р. В Австралии строят Linux-суперкомпьютер / Р. Геда // Открытые системы. 2003. - http://www.osp.ni/cw/2003/31/0251 .htm

62. Орлов, С. Российские кластеры на базе Opteron. / С. Орлов // Открытые системы: «LAN». 2003. - № 7-8. - http://www.osp.ru/lari/2003/07-08/006J Lhtm

63. Лацис, А. Как построить и использовать суперкомпьютер. / А. Лацис- М.: Бестселлер, 2003. 240 с. ' I

64. Михайлов, Г.М. Высокопроизводительный кластер ВЦ РАН им. А.А.Дородницына / Г.М. Михайлов, Ю.П. Рогов, М.А. Копытов // Научный сервис в сети Интернет. Труды Всероссийской научной конференции. 2003. - ■,. С. 60-62.

65. Букатов, А. А. Опыт создания высокопроизводительного кластера с использованием двух коммуникационных сетей / А.А. Букатов, В.Н. Дацюк, О.В. Дацюк и др. И Научный сервис в сети Интернет.Труды Всероссийской научной конференции. — 2003.- С. 110-112.

66. Ершов, А. П. Введение в теоретическое программирование (беседы о методе) / А. П. Ершов М.: Наука. Главная редакция физико-математической литературы. - 1977. - 288 с.

67. Кауфман, ВЛИ, Языки программирования. Концепции и принципы / В.Ш. Кауфман М.: Радио и связь. - 1993. - 432 с.

68. Ахо, А. Теория синтаксического анализа, перевода и компиляции: Том 1 / А. Ахо, Дж. Ульман- Мл Мир.- 1978.-612 с.

69. Ковалик, Я. Высокоскоростные вычисления. Архитектура, производительность, прикладные алгоритмы и программы суперЭВМ / Я. Ковалик М.: Радио и связь. - 1988. - 432 с.

70. Себеста, Роберт У. Основные концепции языков программирования, 5-ое изд. пер. с англ. / Роберт У. Себеста М.: Издательский дом «Вильяме». -2001.-672 с.

71. Трахтенгерц, Э.А. Программное обеспечение параллельных процессов / Э.А. Трахтенгерц ~ М.: Наука. 1987.- 272 с.

72. Трахтенгерц, Э.А. Введение в теорию анализа и распараллеливания программ ЭВМ в процессе трансляции / Э.А. Трахтенгерц М.: Наука. -1981.-279 с.

73. Корнеев, В.Д. Параллельное программирование в MPI / В.Д. Корнеев -Новосибирск: Изд-во СО РАН.-2000.-213 с.

74. Немнюгин, С.А. Параллельное программирование для многопроцессорных систем / С.А. Немшогин, ОЛ. Стесик СПб.: БХВ-Петербург. -2002. -400 с.

75. Евсеев, И. Использование PYM. Введение в программирование. / И. Евсеев http://www.csa.ru/41/pvmtutor/ Использование PVM.htm

76. Geist, А1 PVM: Parallel Virtual Machine. A User's Guide and Tutorial for Networked Parallel Computing / AI Geist, Adam Beguelin, Jack Dongarra, Weicheng Jiang, Robert Manchek, Vaidy Sundcram// The MIT Press. Cambridge, Massachusetts. London, England.

77. PVM: Parallel Virtual Machine http://wvwv.csm.ornl.gov/pvm/

78. Geist, A! PVM: Parallel Virtual Machine A Users' Guide and Tutorial for Networked Parallel Computing 7 Al Geist, Adam Beguelin, Jack Dongarra, Robert Manchek, Weicheng Jiang and Vaidy Sunderam / MIT Press. -1994.-299 pp.

79. Breshears, Clay A Beginners Guide to PVM Parallel Virtual Machine / Clay Breshears, Asim YarKlian~www-j4cs.cs.utk.edu/PV^pvm/guide.htmI.

80. Crawford, Emily Angerer PVM: An Introduction to Parallel Virtual Machine / Emily Angerer Crawford www.hpc.gatech.edu/seminar/pvm.html

81. Буч, Г. Объектно-ориентированное проектирование с примерами применения /Г. Буч; пер. с ант М.: Конкорд. -1992. - 519 е., ил.

82. Буч, Г. Объектно-ориентированный анализ и проектирование с примерами приложений на С++, 2-е изд. / Г. Буч; пер. с англ. -М.: "Издательства Бином", СПб: "Невский диалект". 1998. - 560 е., ил.

83. Средства динамического распараллеливания программ (Т-система) -http://cluster.msu.ru/skif/t-system.html

84. Евсееико, В .А. Адаптация системы параллельных вычислений Т-system к компьютерной сети МГИУ / В .А. Евсеенко, М.Н. Иванов, В.Ю. Радыгин http;//www.ctc.msiu.ru/program/t-system/firstindex.html

85. Official MOSIX web http://www.mosix.org/

86. McChire, S. MOSIX: How Linux Clusters Solve Real World Problems / S. MeClure, R. Wheeler//Proc. 2000 USENIX Annual Tech. Conf., San Diego, CA., June 2000.- pp. 49-56.

87. Barak, A. Scalable Cluster Computing with MOSIX for Linux / A. Barak, O. La'adan, A. Shiloh // Proc. Linux Expo '99,, Raleigh, N.C., May 1999. pp. 95-100.

88. Barak, A. The MOSIX Multicomputer Operating System for High Performance Cluster Computing / A. Barak, O. La'adan, // Journal of Future Generation Computer Systems, March 1998. Vol. 13. - No. 4-5. - pp. 361-372.

89. Рычков, B.H. Промежуточное программное обеспечение для высокопроизводительных вычислений / В.Н. Рычков, И.В. Красноперов, С.П.

90. Копысов // Вычислительные методы в программировании. 2001. - Том 2. -С. 109-124. - http://num-meth.srcc.msu.su/zHurnaI/tom2001/art28.html

91. Джоши, Рауль Параллельный процессинг в ОС Linux с использованием систем PVM и MPI / Рауль Джоши -http://li2mat.tspu.edu.ua/resources/mfo/mir/Ig/Ig65/articles/rus-joshi.html

92. Кернигшг, Б.В. UNIX универсальная среда программирования / Б.В. Керниган, Р. Пайк - Мл Финансы и статистика. - 1992.- 304 с.

93. Документация по Т-системе и Т-языку — ftp://ftp.botik.ru/pub/local/Sergei.Abramov/T-system/

94. Евсеенко, В;А. Сравнение Т-системы и MPI на задаче ЕР из пакета тестов NPB 2.3 / В .А. Евсеенко, М.Н. Иванов, B.IO. Радыгин // Вычислительные методы в программировании. -2001. -Том 2.-С. 17-21. -http://num-meth.srcc.msu.su/2hurnal/tom2001/art22.html

95. American National Stoidard Programming Language С / ANCI X3.159 -1989 American National Standards Institute, New York.

96. Ф 94. Робачевский, A. M. Операционная система UNIX /

97. A. M. Робачевский СПб/.BVH- Санкт-Петербург. - 1997. - 528 е., ил.95. Теренс, Чан Системноепрограммирование на G*H" для UNIX / Чан Теренс; пер. с англ. К.: Издательская группа BHV. - 1999. - 592 с.

98. Вольфенгаген, В.Э. Конструкции языков программирования. Приемы описания. / В.Э. Вольфенгаген -М.: АО «Центр ЮрИнфоР». 2001. - 276 с.

99. Казаков,, Ф.А. Функциональная модель потоковых вычислений / Ф.А. Казаков, Д.А. Кузьмин, А.И. Легалов // В кн.: Проблемы информатизации региона: труды межрегиональной конференции. Красноярск.- 1995.- C.I48.

100. Легалов, А.И. Потоковая модель параллельных вычислений / А.И. Легалов, Ф.А. Казаков, Д.А. Кузьмин // Вестник Красноярского государственного технического университета. Сб. научных трудов. Вып. б, Красноярск. -1996. С. 60-67.

101. Dennis, J.B. Weng Application of data flow computation for the weather problem, high speed computer and algorithm organization / J.B. Dennis, K.S. Ken // Acad. Press. -1977. p. 143-157.

102. Денис, Дж. Б. Схемы потоков данных /Дж. Б. Денис, Дж. Б. Фосснн, Дж. П. Линдерман // В кн. Теория программирования. Ч 2. Новосибирск: ВЦ СО АН СССР.-1972.-С. 7-43.

103. Бердж, В. Методы рекурсивного программирования. Пер. с англ. / В. Бердж М.: Машиностроение. - 1983.-248 с.

104. Головков, СЛ. О языке программирования для модели вычислений^ основанной на принципе потока данных / СЛ. Головков, К.Н. Ефимкин, Э.З. Любимский // препринт института прикладной математики им. М.В.Келдыша . РАН. 2002. - Аг272. - 20 с.

105. SIGMA-1: A Dataflow Computer for Scientific Computations / Т. Yuba, Т. Shimada, К. Hiraki,H. Kashiwagi it Computer Physics Communications. -1985. -pp. 141-148.

106. Казаков, Ф.А. Семантическая модель функционального языка параллельного программирования / Ф.А. Казаков, Д. А. Кузьмин,.; А.И, Легалов // В кн.: Проблемы техники и технологий XXI века. Материалы научной конференции. Красноярск, КГТУ. -1994. С. 85-88.

107. Казаков, Ф.А; Разработка функционально-параллельных программ / Ф.А. Казаков, ДА. Кузьмин, А.И. Легалов //В кн. Нейроинформатика и ее приложения. Программа и тезисы докладов всероссийского рабочего семинара. Красноярск. 1994. - С. 25.

108. Казаков, Ф.А. Организация условных вычислений в потоковых моделях / Ф.А. Казаков // В кн.: Проблемы информатизации региона: труды межрегиональной конференции. Красноярск. 1995. - С. 68-70.

109. Ластовецкий, AJI. Язык и система программирования для-высокопроизводительных параллельных вычислений на неоднородных сетях / А. Л. Ластовецкий, А. Я. Калинов, И, Н. Ледовских и др. // Программирование. 2000. - № 4. - С. 55-80.

110. Lastovetsky, A. L. Parallel Computing on Heterogeneous Clusters /А. L. Lastovetsky John Wiley & Sons, 2003. - 424 pp.

111. Котов, B.E. Сети Петри / B.E. Котов M: Наука. Главная редакция физико-математической литературы. - 1984. - 160 с.

112. Backus, J. Can Programming Be Liberated from von Neuman Style? A Functional Stile and Its Algebra of Programs. // J. Backus CACM, 1978. -vol.21.-№.8.-p.613-641

113. Кейслер, С. Проектирование операционных систем для малых ЭВМ/ С. Кейслер М.: Мир. - 1986. - 680 с.

114. Дейтейл, Г. Введение в операционные системы / Г. Дейтейл М: Мир.-1987.-231 с.

115. ПЗ.Столлингс, В. Операционные системы, 4-е издание / В. Столлингс; пер. с англ. М.: Издательский дом «Вильяме». - 2002. - 842 с.

116. Шоу, А. Логическое проектирование операционных систем/ А. Шоу; пер. с англ.-М,: Мир, 1981.-360 с.

117. Спенсер, Пол XML- Проектирование и реализация. / Пол Спенсер

118. Москва, Лори. -2001. 509 с.

119. Lamport L., Time, clocks and ordering of events in Distributed Systems,

120. Comm. Of ACM, 21,7, 558-564,1978.

121. Mazurkiewicz A., Concurrent program schemes and their Interpretation, DIAMI Report PB-78, Aarhus University, 1977.

122. Mazurkiewicz A., Semantics of Concurrent Systems:A modular fixed point trace approach, LNCS 188,353-357.

123. Mazurkiewicz A., Trace Theory, LNCS 255, 279-324. 20. Nielsen M., Plot kin G., Winskel C, Petri Nets, Event Structures and domains. Theoret Comp . Sci. 13 (1981), 85-108.

124. Pneuli A., The Temporal Logic of Programs, In 18-th Symp.On Foundation of computer Science 1977.

125. Nielsen M., Plot kin G., Winskel C, Petri Nets, Event Structures and domains. Theoret Comp. Sci. 13 (1981), 85-108.

126. Калиниченко Б.О. О восстановлении сети процесса по последовательности срабатываний переходов сети Петри.// Международныйсборник научных трудов, вып 17. Изд. «Научная книга», Воронеж, 2004, С.58-66.

127. Калиниченко Б.О., Редкозубов С,А. Фундаментальный подход к оценке результатов наблюдения.// Труды международной научно-технической конференции «Транском-2004». Санкт-Петербург, 2004. С. 264-269

128. Калиниченко Б.О. Семантика чередования и частичного порядка в сетях Петри.// Труды седьмого Всероссийского симпозиума по прикладной и промышленной математике. Ж «ОП и ПМ», М, 2005, С. 586-588

129. Калиниченко Б.О. Функционально-потоковая модель параллельного программирования.// Труды седьмого Всероссийского симпозиума по прикладной и промышленной математике. Ж «ОП и ПМ», М, 2005, С. 588-590.