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

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

КУЗЬМИН

Дмитрий Александрович

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

05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Красноярск - 2004

Работа выполнена в Красноярском государственном техническом университете

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

доцент Легалов А.И.

Официальные оппоненты: доктор физико-математических наук, профессор Добронец Б. С.

кандидат физико-математических наук Мурзин Ф.А.

Ведущая организация: Институт вычислительного моделирования СО РАН

(г. Красноярск)

Защита состоится « 18 » марта 2004 г. в 14— часов на заседании диссертационного совета Д 212.098.03 в Красноярском государственном техническом университете по адресу: 660074, г. Красноярск, ул. Киренского, 26, ауд Г4-17, тел 49-73-81, факс (8-3912)-49-79-90

С диссертацией можно ознакомится в научной библиотеке Красноярского государственного технического университета.

Автореферат разослан «// » фе/рС^ 2004 г.

2005-Ц

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

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

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

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

1) использование последовательного программирования с дальнейшим автоматическим распараллеливанием разработанных программ;

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

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

Каждый из подходов в настоящее время представлен семейством соответствующих инструментальных средств.

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

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

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

программ на конкретную архитектуру, используется сжатие максимального параллелизма.

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

Достижение цели связывается с решением следующих задач:

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

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

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

Научная новизна. В ходе проведенных исследований автором получены следующие результаты.

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

2. Предложена многоуровневая архитектура параллельной виртуальной машины обеспечивающей выполнение ФП программ.

3. Предложен механизм отображения методов интерпретации ФП программ на ОС Linux с поддержкой системы MOSIX в соответствии многоуровневой архитектурой параллельной виртуальной машины.

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

Практическая ценность.

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

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

3. Для проведения экспериментов на базе учебных компьютерных классов создана кластерная система под управлением ОС Linux с поддержкой MOSIX и MPI, позволившая провести работы по созданию и отладке параллельного интерпретатора, а также провести оценочные эксперименты параллельной интерпретации ФП программ.

4. Реализованы методы переноса ФП программ на последовательную и кластерную архитектуры. Методы основаны на сжатии максимального параллелизма задачи за счет изменения стратегии управления вычислениями.

Публикации. Основные результаты опубликованы в 19 печатных работах, из них 9 статей и 10 тезисов докладов.

Результаты исследований использовались в научно-технических отчетах по грантам: ККФН № 4F0093,1995 г.; ФЦП «Интеграция», проект 68, направление 21,1998 г.; РФФИ№ 02-07-90135,2002,2003 г.

Апробация работы. Основные положения и результаты работы докладывались на 1,2, 6 Всероссийских рабочих семинарах «Нейроинформатика и ее приложения», Красноярск (1993, 1994, 1998); Межреспубликанской научной конференции «Методы и средства управления технологическими процессами», Саранск, 1993; научно-технической конференции «Проблемы техники и технологий XXI века», Красноярск (1994); 1, 5, 6 Всероссийских научно-практических конференциях «Проблемы информатизации региона», Красноярск (1995, 1999, 2000); третьем Сибирском конгрессе по прикладной и индустри-

альной математике (ИНПРИМ-98), Новосибирск, 1998; Всероссийской научно-практической конференции с международным участием «Достижения науки и техники - развитию сибирских регионов», Красноярск, 1999; 1-3 школах-семинарах «Распределенные и кластерные вычисления», Красноярск (2001,2002, 2003); Международной конференции «Перспективы систем информатики» (рабочий семинар «Наукоемкое программное обеспечение»), Новосибирск, 2003 г.

Структура и объем работы. Диссертация состоит из введения, 4-х глав, заключения, списка литературы и двух приложений. Работа изложена на 129 страницах, содержит 33 рисунка и 4 таблицы. Список литературы включает 115 наименований.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении дается краткая характеристика работы, обосновывается ее актуальность, цель, приводится перечень вопросов, выносящихся на защиту.

В первой главе проводится анализ архитектур параллельных вычислительных систем (ПВС). Рассматриваются основные классы аппаратных архитектур параллельных вычислительных систем: SMP, NUMA, ccNUMA, MPP и кластерные архитектуры. Анализируется динамика развития современных суперкомпьютеров за последние 5 лет по материалам официального списка 500 самых производительных компьютеров (www.top500.org). По результатам общего анализа обосновывается выбор МРР и кластерной архитектуры для проведения исследований по созданию среды выполнения функционально-параллельных программ. Одним из основных критериев выбора является масштабируемость ПВС. Основной акцент делается на однородную кластерную архитектуру, как более доступный вариант МРР систем. Далее в главе формулируются подходы к исполнению ФП программ. Делается вывод о предпочтении реализации эмулирующей исполняемой среды для проведения исследований модели вычисления и функционального языка параллельного программирования.

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

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

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

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

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

M = (G|, Gm, P|, Pm, S,с» Smo),

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

Информационный граф определяется как

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

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

= (Ут, Ат),

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

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

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

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

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

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

I Т

V. р(Х)

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

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

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

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

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

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

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

Поэтому необходимо использовать комбинированные виртуальные машины, обеспечивающие решение следующих задач:

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

- параллельное выполнение на уровне «крупных» единиц информации (крупноблочное распараллеливание);

- обеспечение гибкости распределения вычислительной нагрузки;

- настройка и развитие модели виртуального вычислителя;

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

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

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

- низкоуровневые операции выполняются последовательно;

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

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

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

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

Далее в главе рассматриваются методы последовательного и параллельного исполнения ФП программ. Исследуются пути повышения производительности интерпретации ФП программ.

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

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

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

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

Получены следующие научные и практические результаты работы.

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

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

- последовательное выполнение низкоуровневых операций;

- параллельное выполнение на уровне отдельных процессов, а в общем случае, на уровне потоков и процессов (крупноблочное распараллеливание);

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

3. Предложены механизмы отображения методов интерпретации ФП программ на ОС Linux с поддержкой системы MOSIX в соответствии многоуровневой архитектурой параллельной виртуальной машины, на основании которых были разработаны:

- последовательный интерпретатор, обеспечивающий выполнение отладку ФП программ;

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

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

Результаты работы отражены в следующих публикациях:

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

2. Казаков, Ф. А. Параллельно-функциональный язык программирования / Ф. А. Казаков, Д. А. Кузьмин, А. И. Легалов // В кн.: Методы и средства управления технологическими процессами. Тезисы докладов 3-й Межреспубликанской научной конференции. - Саранск, 1993. - С. 35-37.

3. Кузьмин, Д. А. Применение гипертекстовой среды в обучающей системе / Д. А. Кузьмин, А. И. Легалов // В кн.: Высшее техническое образование в новых социально-экономических условиях. Сборник тезисов межвузовской научно-методической конференции с международным участием. - Красноярск, 1994.-С. 155.

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

5. Казаков, Ф. А. Язык программирования параллельных процессов / Ф. А. Казаков, Д. А. Кузьмин, А. И. Легалов / В кн.: Проблемы информатизации города: Материалы конференции. - Красноярск, 1994. - С. 203-204.

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

7. Kuzmin, D. A. Description ofparallel-functional programming language / D. A. Kuzmin, F. A. Kazakov, A. I. Legalov // Advances in Modeling & Analysis, A, AMSE Press, 1995. -Vol.28. -No. 3. -pp. 1-17.

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

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

10. Казаков, Ф. А. Обучающая система на основе отображаемой среды с элементами управления. / Ф. А. Казаков, Д. А. Кузьмин, А. И. Легалов // В кн.: Новые технологии обучения и реализация государственного образовательного стандарта в технических вузах. Сб. тезисов МНМК КГТУ. - Красноярск, 1995.-С. 22.

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

12. Легалов, А. И. Модель параллельных вычислений функционального языка / А. И. Легалов, Ф. А. Казаков, Д. А. Кузьмин, А. И. Водяхо // Известия ТЭТУ, Сборник научных трудов. Выпуск 500. Структуры и математическое обеспечение специализированных средств. - С.-Петербург, 1996. - С. 56-63.

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

14. Легалов, А. И. Функциональная модель параллельных вычислений и соответствующий ей язык программирования / А. И. Легалов, Ф. А. Казаков, Д. А. Кузьмин // Третий сибирский конгресс по прикладной и индустриальной математике (ИНПРИМ-98). Тезисы докладов, часть 5. - Новосибирск, Изд-во Института математики СО РАН, 1998. - С. 85-86.

15.Кузьмин, Д. А. Создание М08ГХ кластера на базе компьютерного класса / Д. А. Кузьмин, А. И. Легалов // Проблемы информатизации региона ПИР-2001: Материалы Седьмой Всероссийской научно-практической конферен-

ции (Красноярск, 18-19 декабря 2001 г.) / Под ред. Е. А. Вейсова, В. И. Под-шивалова. - Красноярск: КГТУ, 2001. - С. 66-73.

16. Кузьмин, Д. А. Использование MPI для организации кластерных систем на основе компьютерных классов / Кузьмин Д. А., Легалов А. И. // Проблемы информатизации региона. ПИР-2001: Материалы Седьмой Всероссийской научно-практической конференции (Красноярск, 18-19 декабря 2001 г.) Под ред. Е. А. Вейсова, В. И. Подшивалова. - Красноярск: КГТУ, 2001. - С. 42-47.

17. Легалов, А. И. Модель функционально-потоковых вычислений и язык программирования «Пифагор» / Легалов А. И., Казаков Ф. А., Кузьмин Д. А., Привалихин Д. В. // 2-ая школа семинар. Распределенные и кластерные вычисления. Избранные материалы. -Красноярск, 2002. - С. 101-120.

18.Кузьмин, Д. А. Интерпретация функциональных программ на кластере под управлением MOSIX / Д. А. Кузьмин, И. Н. Рыженко, А. И. Легалов // Вестник Красноярского государственного технического университете. Выпуск № 33. Математические методы и моделирование. Под редакцией В. И. Быкова. Красноярск. ИПЦ КГТУ, 2003. - С. 196-205.

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

Подписано в печать 11.02.2004. Формат бумаги 60x84 1/16

Усл. печ. л. 2,0 Тираж 100 экз. Заказ т.

Отпечатано на ризографе КГТУ 660074, Красноярск, Корейского 26

€- 33 9 0

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

2005-4 20173

Введение.

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

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

1.1.1 SMP-системы.

1.1.2 Система NUMA.1В

1.1.3 МРР системы.

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

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

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

1.4.1 PVM.

1.4.2 MPI.

1.4.3 Система MOSIX.

1.4.4 «Т-система».

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

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

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

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

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

2.2.1 Оператор интерпретации.

2.2.2 Константный оператор.

2.2.3 Оператор копирования.

2.2.4 Оператор группировки в список.

2.2.5 Оператор создания параллельного списка.

2.2.6 Оператор группировки в задержанный список.

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

Выводы по главе 2.

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

3.1 Способы реализации системы исполнения функционально-параллельных программ.

3.2 Организация процесса интерпретации ФП программ.

3.2.1 Методы последовательного выполнения ФП программ.

3.2.2 Методы параллельного выполнения ФП программ.

Выводы по главе 3.

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

4.1 Реализация последовательно-параллельного интерпретатора с использованием системы динамического распараллеливания МОБГХ.

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

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

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

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

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

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

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

4.3 Методы повышения эффективности интерпретации.

4.3.1 Оценка вычислительной сложности интерпретируемой функции.

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

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

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

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

Существуют различные варианты классификации методов десеквенции программ. Одним из них является деление по способам представления исходного параллелизма [4, 5, 6, 7]:

1. использование последовательного программирования с дальнейшим автоматическим распараллеливанием разработанных программ [8];

2. применение языков программирования, обеспечивающих непосредственное описание любых потоков параллельного управления, по сути являющихся расширениями традиционных последовательных языков за счет добавления разнообразных примитивов распараллеливания и синхронизации, при этом уровень параллелизма полностью контролируется разработчиком и может задаваться в зависимости от конкретных условий [9, 10]. Десеквенция подобных программ является переводом одной параллельной формы в другую;

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

Каждый из подходов в настоящее время представлен семейством соответствующих инструментальных средств.

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

• создавать мобильные программы с параллелизмом на уровне операторов, ограниченным лишь методом решения задачи [11];

• обеспечивать перенос программы на конкретную архитектуру, не распараллеливая программу, а сжимая ее максимальный параллелизм;

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

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

Актуальность этого направления обуславливается следующими причинами.

Развитие современных суперкомпьютеров привело к появлению параллельных архитектур, предусматривающих высокую степень распараллеливания и теоретически предоставляющих разработчикам возможность добавлять неограниченное число процессоров [12], с другой стороны в настоящее время более 30 % высокопроизводительных систем реализованы на смешанных архитектурах и прослеживается тенденция к росту неоднородных систем в будущем. Соответственно, возникает дисбаланс между возможностями архитектуры и возможностями программного обеспечения. Можно утверждать, что существует необходимость в создании таких средств параллельного программирования, которые бы с одной стороны обеспечивали бы возможность реализовать максимальный параллелизм задачи, а с другой обладали бы свойством переносимости и соответственно избавили бы программистов от необходимости всякий раз переписывать программный код при переносе программного обеспечения на изменившуюся архитектуру ПВС.

Одним из направлений по решению проблемы переносимости параллельных программ является создание функциональных языков [13, 14, 15, 16] параллельного программирования, в которых выполнение каждого оператора осуществляется по готовности его данных. Они не требуют явного описания параллелизма задачи. Достаточно указать информационную взаимосвязь между функциями, осуществляющими преобразование данных.

Разработанный на основе функционально-потоковой модели вычислений язык функционально-параллельного программирования [17, 18, 19, 20, 21] относится именно к этому направлению.

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

В работе предлагается модель, описывающая динамику поведения ФП программ, построенных на основе функционально-потоковой модели вычислений [22, 23, 24, 25, 26]. Демонстрируются разработанные обобщенные алгоритмы функционирования базовых операторов модели. Исследуются методы выполнения ФП программ, на основании которых предлагаются различные стратегии управления функционально-потоковыми вычислениями.

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

В рамках поставленной цели решаются следующие основные задачи:

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

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

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

В работе получены следующие научные результаты.

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

2. Предложена многоуровневая архитектура параллельной виртуальной машины обеспечивающей выполнение ФП программ.

3. Предложен механизм отображения методов интерпретации ФП программ на ОС Linux с поддержкой системы MOSIX [27] в соответствии многоуровневой архитектурой параллельной виртуальной машины.

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

К практическим результатам работы следует отнести.

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

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

3. Для проведения экспериментов на базе учебных компьютерных классов создана кластерная система под управлением ОС Linux RedHat с поддержкой MOSIX и MPI [28, 29], позволившая провести работы по созданию и отладке параллельного интерпретатора, а также провести оценочные эксперименты параллельной интерпретации ФП программ.

4. Реализованы методы переноса ФП программ на последовательную и кластерную архитектуры. Методы основаны на сжатии максимального параллелизма задачи за счет изменения стратегии управления вычислениями.

На защиту выносятся:

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

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

- механизмы отображения методов интерпретации ФП программ на ОС Linux с поддержкой системы MOSIX в соответствии многоуровневой архитектурой параллельной виртуальной машины;

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

Публикации

По теме диссертации опубликовано 19 печатных работ, из них 3 в центральной печати и 1 международная публикация [21].

Результаты исследований использовались в научно-технических отчетах по грантам: ККФН № 4F0093, 1995 г.; ФЦП «Интеграция», проект 68, направление 21, 1998 г.; РФФИ№ 02-07-90135, 2002,2003 г.

Апробация работы

Основные положения и результаты работы докладывались на:

• 1, 2, 6 Всероссийских рабочих семинарах «Нейроинформатика и ее приложения», Красноярск (1993, 1994, 1998);

• Межреспубликанской научной конференции «Методы и средства управления технологическими процессами», Саранск, 1993;

• научно-технической конференции «Проблемы техники и технологий XXI века», Красноярск (1994);

• 1, 5, 6 Всероссийских научно-практических конференциях «Проблемы информатизации региона», Красноярск (1995, 1999, 2000);

• третьем Сибирском конгрессе по прикладной и индустриальной математике (ИНПРИМ-98), Новосибирск, 1998;

• Всероссийской научно-практической конференции с международным участием «Достижения науки и техники - развитию сибирских регионов», Красноярск, 1999;

• 1-3 школах-семинарах «Распределенные и кластерные вычисления», Красноярск (2001, 2002, 2003);

• Международной конференции «Перспективы систем информатики» (рабочий семинар «Наукоемкое программное обеспечение»), Новосибирск, 2003 г.

Структура диссертации

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

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

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

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

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

Заключение

Получены следующие научные и практические результаты работы.

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

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

- последовательное выполнение низкоуровневых операций;

- параллельное выполнение на уровне отдельных процессов, а в общем случае, на уровне потоков и процессов (крупноблочное распараллеливание);

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

3. Предложены механизмы отображения методов интерпретации ФП программ на ОС Linux с поддержкой системы MOSIX в соответствии многоуровневой архитектурой параллельной виртуальной машины, на основании которых были разработаны:

- последовательный интерпретатор, обеспечивающий выполнение отладку ФП программ;

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

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

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. - № 4. -С. 37-51.

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

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

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

12. Чиди, Д. ASCI White впереди планеты всей / Д. Чиди // Открытые системы: Еженедельник «Computerword». 2000. - № 42. — http://www.osp.ru/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. - С. 203-204.

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

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

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

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

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

25. A.И. Легалов // Вестник Красноярского Государственного Технического университете. Выпуск № 33. Математические методы и моделирование. Под редакцией В.И. Быкова. Красноярск. ИПЦ КГТУ, 2003. С. 196-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. -http://support.vologda.ru/Book/ARCHITECTURE/Svk/contents.htm

38. Aad, J. van der Steen Overview of Recent Supercomputers // Aad J. van der Steen, Jack J. Dongarra -http://www.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/overview02.html

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.parallel.ru

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

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

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

48. System architecture description of the Hitachi SR2201 -http://www.hitachi.co.jp/Prod/comp/hpc/eng/srl.html

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

50. Гольдштейн, M.J1. Мультипроцессорная вычислительная система на базе транспьютерной идеологии / 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. - № 17. -http://www.osp.rU/cw/2002/l 7/0041 .htm

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

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

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

58. Орлов, С. Искусство объединения / С. Орлов // Открытые системы: «LAN». 2003. - № 9. - http://www.osp.ru/lan/2003/09/072.htm

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

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

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

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

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

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

65. Букатов, А. А. Опыт создания высокопроизводительного кластера с использованием двух коммуникационных сетей / A.A. Букатов, В.Н. Дацюк, О.В. Дацюк и др. // Научный сервис в сети Интернет.Труды Всероссийской научной конференции. 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. Немнюгин, С. А. Параллельное программирование для многопроцессорных систем / С.А. Немнюгин, O.JI. Стесик СПб.: БХВ-Петербург. - 2002. - 400 с.

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

76. Geist, Al 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 Sunderam // The MIT Press. Cambridge, Massachusetts. London, England.

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

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

79. Breshears, Clay A Beginner's Guide to PVM Parallel Virtual Machine / Clay Breshears, Asim YarKhan www-jics.cs.utk.edu/PVM/pvm/guide.html.

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. McClure, S. MOSIX: How Linux Clusters Solve Real World Problems / S. McClure, 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/zhurnal/tom2001/art28.html

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

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

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

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

95. American National Standard Programming Language С / ANCI Х3.159 -1989 American National Standards Institute, New York.

96. Робачевский, A. M. Операционная система UNIX / A. M. Робачевский СПб.:ВУН - Санкт-Петербург. - 1997. - 528 е., ил.

97. Теренс, Чан Системное программирование на С++ для UNIX / Чан Теренс; пер. с англ. К.: Издательская группа BHV. - 1999. - 592 с.

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

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

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

101. Dennis, J.B. Weng Application of data flow compilation 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. Головков, C.JI. О языке программирования для модели вычислений, основанной на принципе потока данных / C.JI. Головков, К.Н. Ефимкин, Э.З. Любимский // препринт института прикладной математики им. М.В.Келдыша РАН. 2002. - № 72. - 20 с.

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

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

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

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

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

110. Lastovetsky, A. L. Parallel Computing on Heterogeneous Clusters / A. 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.-No. 8.- p. 613-641.

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

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

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

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

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