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

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

ПРИВАЛИХИН Денис Викторович

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

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

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

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

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

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

доцент

Легалов Александр Иванович

Официальные оппоненты: доктор физико-математических наук, профессор Кытманов Александр Мечиславович

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

Сорокин Владимир Афанасьевич

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

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

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

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

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

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

Вейсов Е.А.

гад

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

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

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

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

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

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

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

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

анализа возможности использования рассмотренных методов в функционально-потоковом языке параллельного программирования «Пифагор».

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

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

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

Методы исследования. В диссертационной работе использовались методы и понятия теории графов, теории алгоритмов, теории рекурсивных функций, элементы теории множеств, теории языков и формальных грамматик. В качестве формальных моделей анализа параллелизма применялись различные классы схем потоков данных. Для описания синтаксиса языка программирования использовались расширенные формы Бэкуса-Наура (РБНФ), диаграммы Вирта. В экспериментальной части применялись методы синтаксического анализа и компиляции, методы объектно-ориентированного программирования, методы быстрой разработки приложений.

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

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

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

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

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

Практическая ценность. Разработанные автором диссертации языковая и инструментальная поддержка функционально-параллельного программирования позволили создать систему, содержащую транслятор, средства отладки и интерпретатор. Эта система использована для проведения дальнейших исследований в области функционально-потокового параллельного программирования. Ряд созданных модулей использован в кластерной системе, обеспечивающей реальное параллельное выполнение программ, написанных на языке «Пифагор» под управлением пакета Моз1х. Полученные научные и практические результаты использованы в учебном процессе по дисциплинам «Параллельное программирование» и «Параллельные вычисления» в Красноярском государственном техническом университете. Исследования также выполнялись при поддержке гранта РФФИ № 02-0790135, 2002-2003 г.

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

Публикации и личный вклад в решение проблемы. По теме диссертации опубликовано 10 печатных работ.

Диссертация основана на теоретических, методологических и экспериментальных исследованиях, выполненных на кафедре Нейро-ЭВМ КГТУ. Основные результаты, изложенные в работе, получены либо непосредственно автором, либо с его участием.

Апробация работы. Основные положения диссертации обсуждались на следующих конференциях и семинарах: межвузовских научных конференциях студентов, аспирантов и молодых учёных, г. Красноярск, (2001-2004 гг.); 2-ой - 4-й школах-семинарах «Распределенные и кластерные вычисления», г. Красноярск, (2002-2004 гг.); региональной конференции-конкурсе работ студентов; аспирантов и молодых учёных «Технологии Microsoft в информатике и программировании», г. Новосибирск, 2004 г.; 4-м международном научно-практическом семинаре и Всероссийской молодежной школе «Высокопроизводительные вычисления на кластерных системах», г. Самара, 2004 г.;

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

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

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

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

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

сутствующие в «Пифагоре». Рассмотрены функциональные языки параллельного программирования Haskell, Clean, Sisal, FPTL.

Анализ методов управления параллельными вычислениями показал, что языки Haskell и Clean поддерживают явное распараллеливание, аналогичное тому, которое используется в императивных языках. Подобный подход противоречит функциональному стилю и не обеспечивает описание максимального параллелизма решаемой задачи. Он ведет к тому, что программа делится на последовательно исполняемые базовые операции и параллельно запускаемые процессы. Механизмы управления вычислениями языка «Пифагор» обеспечивают большую гибкость в описании параллелизма на уровне операций, что автоматически ведет к поддержке параллелизма и на уровне более крупных функциональных единиц.

Управление параллельными вычислениями в языках программирования Sisal и FPTL организовано неявно и обеспечивает параллелизм на уровне операций. Однако если в Sisal используется непосредственное выполнение программы по описанной схеме потоков данных, в FPTL реализован редукционный принцип, заключающийся в том, что на первом этапе производится «развертка» фрагментов исходной программы в потоковый граф специальным интерпретатором, а лишь затем осуществляется непосредственное выполнение вычислений. Такая двухэтапная схема несколько замедляет процесс вычислений и больше привязана к синтаксису языка, чем к модели вычислений. Язык программирования «Пифагор» обеспечивает описание вычислительного процесса в терминах непосредственного управления потоками данных. Предложенный синтаксис является лишь одним из вариантов отображения функционально-потоковой модели параллельных вычислений, который достаточно просто может быть заменен другими формами представления программ.

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

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

граммирования, широко используемых на практике. К ним, в частности следует отнести:

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

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

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

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

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

Дания другого метода управления «бесконечными» рекурсиями, аналогичного по свойствам.

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

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

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

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

Перегруженная_функция :=

имя "{"ранг"]""Гипс<1еГ' [ аргумент | "{" тело функции "}".

Пример объявления перегруженной функции ОуегКипс: СНгегЕЧтс [2.5] « £ипсс1е£ Рагат { // Тело функции } ОуегРипс [15] << £ипс«1е£ Рагат { // Тело функции } 0<гегРш1С [-10] << £ипс<1е£ Рагат { // Тело функции } ОуегРипс [] << £ипс<1е£ Рагат { // Тело функции } Это число является рангом и определяет отношения порядка между перегруженными функциями в формируемом параллельном списке этих функций при интерпретации. Если ранг не указан, то считается, что он равен нулю.

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

В:ОуегРипс = В:[(^егРипс, С^егРипс, С^егРипс, ОуегРипс], где перегруженные функции упорядочены в параллельном списке в соответствии с рангом (-10, 0, 2.5, 15).

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

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

Определены правила преобразования типов, которые используются по принципу формирования «обертки» вокруг преобразуемых данных. Данный механизм является расширением операций преобразования базовых типов и хорошо согласуется с ним. Суть заключается в получении элемента, следующей структуры:

Элемент пользовательского типа :=

(пользовательский тип, преобразуемый элемент).

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

1. Если тип аргумента совпадает с типом в операции преобразования, то возвращается значение исходного аргумента;

2. Преобразование осуществляется только в том случае, если проверка аргумента на принадлежность функцией in, осуществляемая неявно, дает «истину»;

3. Во всех остальных случаях функция преобразования в пользовательский тип возвращает соответствующую ошибку.

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

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

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

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

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

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

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

В третьей главе рассматриваются особенности программирования с использованием предложенных расширений.

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

overfact[]« funcdef х { // Отрицательный аргумент

"Ошибка! Отрицательный аргумент":[ (х,О):<] »return;

}

overfact[]« funcdef х { // Аргумент больше 10 "Ошибка! Большой аргумент":[(х,10):>] »return;

}

overfact []<< funcdef х { // Аргумент равен 0 1: [ (х, 0) : =] »return;

}

overfact[]<< funcdef х { // Аргумент равен 1 1: [ (х, X) : =] »return;

}

overfact []<< funcdef х { // Аргумент больше 1 ({(х, (х,1)-.overfact) :*})

:[((х,1):>, (х,п):<=):*]:[]:. >> return

}

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

fact « funcdef х {(х:overfact):[] » return}

Использование подобного приема в более сложных программах повышает гибкость разработки и обеспечивает эволюционное расширение.

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

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

Triangle << typedef X { // Описание треугольника [(((X:type,datalist):=,(X:|,3):=):*:int,l):+]Л (false,

{([(X:l:type,int),

(X:2:type,int),(X:3:type,int)]:=):*} ) : . >> return

}

Rectangle << typedef X { // Описание прямоугольника [(((X:type,datalist):=,(X:|,2):=):*:int,l):+]A ( false,

{([(X:l:type,int),(X:2:type,int)]:=):*} ):. >> return

}

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

IsFigure[]<< funcdef figure { // Треугольник? figurestype >> t; (t. Triangle):= » return;

}

IsFigure[] « funcdef figure { // Приоугояьник? figureitype >> t; (t. Rectangle):» » return;

}

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

Figure « typedef X { (X:IsFigure):+ >> return; };

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

Circle << typedef X { // Описание круга (X:type,int):= >> return;

}

IsFigure[] << funcdef figure { // Круг?

figure:type >> t; (t. Circle):= >> return;

}

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

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

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

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

Оболочка пользователя реализована в виде графического приложения, состоящего из следующих визуальных объектов:

- многооконного текстового редактора;

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

- окна с информацией о работе транслятора;

- окна для ввода аргумента выполняемой или отлаживаемой функции;

- окна с информацией о работе пошагового отладчика;

- окна для отображения результатов выполнения программы.

В главе также представлена информация о практическом использовании разработанных транслятора и интерпретатора в системе интерпретации функционально-потоковых параллельных программ на вычислительном кластере под управлением пакета Моз1х.

В приложении приведено полное описание текущей версии функционального языка параллельного программирования «Пифагор».

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

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

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

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

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

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

1. Привалихин, Д. В Транслятор и интерпретирующая система функционального языка параллельного программирования / Д. В. Привалихин // В кн.: Информатика и информационные технологии. Тезисы докладов межвузовской научной конференции студентов, аспирантов и молодых учёных -Красноярск, 2001. - С. 110-115.

2. Привалихин, Д. В. Транслятор функционального языка параллельного программирования / Д. В. Привалихин // В кн.: Информатика и информационные технологии. Материалы межвузовской научной конференции. -Красноярск, 2002 - С. 228-232.

3. Привалихин, Д. В. Интегрированная среда разработки программ на функциональном языке параллельного программирования «Пифагор» / Д. В. Привалихин // В кн : Информатика и информационные технологии. Материалы межвузовской научной конференции. - Красноярск, 2002. - С. 232236.

4. Легалов, А. И. Использование типов в языке программирования Пифагор / А. И. Легалов, Д. В. Привалихин // В кн.: Проблемы информатизации региона. Сборник научных трудов. - Красноярск, 2002. - С. 55-61.

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

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

7. Легалов, А. И. Эволюционное расширение пользовательских типов в языке программирования «Пифагор» / А. И. Легалов, Д. В. Привалихин // В кн.: Распределённые и кластерные вычисления. Избранные материалы третьей школы-семинара. - Красноярск, 2004. - С. 141-153.

8. Привалихин, Д. В. Интегрированная среда разработки программ для функционального языка параллельного программирования «Пифагор» / Д. В. Привалихин // В кн.: Технологии Microsoft в информатике и программировании. Тезисы докладов конференции-конкурса работ студентов, аспирантов и молодых учёных. - Новосибирск, 2004. - С. 32-34.

9. Легалов, А. И. Перегрузка функций и пользовательские типы в языке программирования «Пифагор» / А. И. Легалов, Д. В. Привалихин // Вестник Красноярского государственного технического университета. Выпуск № 33. Математические методы и моделирование. - Красноярск, 2004. - С. 228-234.

10.Легалов, А. И. Особенности функционального языка параллельного программирования «Пифагор» / А. И. Легалов, Д. В. Привалихин // В кн.: Высокопроизводительные вычисления на кластерных системах. Материалы четвертого Международного научно-практического семинара и Всероссийской молодежной школы. Под редакцией В. А. Сойфера. - Самара, 2004. -С. 173-179.

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

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

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

# 25 9 97

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

2006-4 3718

»

Введение.

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

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

1.2 Язык функционального программирования Haskell.

1.3 Функциональный язык программирования Clean.

1.4 Функциональный язык параллельного программирования Sisal.

1.5 Язык FPTL.

1.6 Функциональный язык параллельного программирования Пифагор

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

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

2.1 Система типизации, строгого контроля типов и введение типов, определяемых пользователем.

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

2.1.2 Пользовательские типы.

2.2 Перегрузка функций с одинаковой сигнатурой.

2.3 Определение функции с предусловием и постусловием.

2.4 Возврат задержанных списков в качестве результата вычисления функций.

2.5 Модульное построение программ на языке Пифагор.

2.6 Использование функций, написанных на других языках программирования, расположенных во внешних модулях.

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

3 Использование расширений функционального языка параллельного программирования Пифагор.

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

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

3.3 Применение предусловий и постусловий.

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

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

4 Инструментальная поддержка функционально-потокового параллельного программирования.

4.1 Структура блока трансляции-интерпретации программ на ФЯПП.

4.2 Структура транслятора.

4.2.1 Лексический анализатор или сканер.

4.2.2 Синтаксический анализатор.

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

4.3.1 Интерпретация объектов TProgram, TFunction и TBlock.

4.3.2 Интерпретация объекта TExpression.

4.3.3 Интерпретация объектов TAtom и TKW.

4.3.4 Интерпретация объекта TList.

4.3.5 Интерпретация объекта TID.

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

4.4 Интегрированная среда разработки программ на ФЯПП.

4.4.1 Текстовый редактор.

4.4.2 Панель инструментов и управление транслятором и интерпретатором.

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

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

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

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

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

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

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

В настоящее время основным подходом к созданию параллельных программ является использование явных методов управления вычислениями. Большинство современных языков программирования включают примитивы для написания параллельных программ [4, 5] или используют для этого библиотечную поддержку [6, 2].

Однако степень определения параллелизма целиком зависит от знания разработчиком особенностей конкретной архитектуры ПВС [7, 8] и/или библиотеки программирования [2]. Все это приводит практически к невозможности переноса программных модулей с одной архитектуры на другую.

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

Обладая рядом потенциальных преимуществ, такой подход долгое время не получал развития из-за высокой ресурсоемкости этапа подготовки вычислений. Однако, в настоящее время, уровень развития ПВС, их широкое распространение привело к повышению интенсивности исследований в данном направлении [10, 11, 12, 13].

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

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

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

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

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

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

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

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

Методы исследования. В диссертационной работе использовались методы и понятия теории графов, теории алгоритмов, теории рекурсивных функций, элементы теории множеств, теории языков и формальных грамматик. В качестве формальных моделей анализа параллелизма применялись различные классы схем потоков данных. Для описания синтаксиса языка программирования использовались расширенные формы Бэкуса-Наура (РБНФ), диаграммы Вирта.

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

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

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

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

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

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

Полученные научные и практические результаты использованы в учебном процессе по дисциплинам «Параллельное программирование» и «Параллельные вычисления» в Красноярском государственном техническом университете.

Исследования также выполнялись при поддержке гранта РФФИ № 0207-90135, 2002-2003 г.

Публикации. По теме диссертации опубликовано 10 печатных работ. Апробация работы. Основные положения диссертации обсуждались на следующих конференциях и семинарах:

- межвузовские научные конференции студентов, аспирантов и молодых учёных, г. Красноярск, (2001-2004 гг.);

- 2, 3, 4 школы-семинары «Распределенные и кластерные вычисления», г. Красноярск, (2002-2004 гг.);

- региональная конференция-конкурс работ студентов, аспирантов и молодых учёных «Технологии Microsoft в информатике и программировании», г. Новосибирск, 2004 г.;

- 4-й международном научно-практическом семинаре и Всероссийской молодежной школе «Высокопроизводительные вычисления на кластерных системах», г. Самара, 2004 г.

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

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

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

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

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

3. Графическая оболочка, предназначенная для взаимодействия с пользователем и осуществляющая координацию взаимодействия транслятора и интерпретатора.

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

Заключение

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

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

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

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

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

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

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

1. American National Standard Programming Language С / ANCI X3.159 1989 American National Standards Institute, New York.

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

3. Нортон, П. Программирование на Java. / П. Нортон//Руководство П.Нортона (в 2-х томах). "СК-Пресс", 1998 900 с.

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

5. Коновалов Н.А. Fortran-DVM язык разработки мобильных параллельных программ. / Н.А. Коновалов, В.А. Крюков, С.Н. Михайлов, JI.A. Погребцов // Программирование. 1995, № 1. 49-54. с.

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

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

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

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

10. Achten, P.M. The ins and outs of Clean I/O / P.M. Achten, M J. Plas-meijer // In Journal of Functional Programming, 5(1), Januaiy 1995, pages 81-110.

11. Leroy, X. The Objective Caml system release 3.04 / X. Leroy // Documentation and user's manual. Institut National de Recherche en Informatique et en Automatique. December 10,2001.

12. Thompson S. Haskell: The Craft of Functional Programming. / S. Thompson // 2-nd edition, Addison-Wesley, 1999.

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

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

15. Kuzmin, D.A. Description of parallel-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.

16. Легалов, А.И. Модель функционально-потоковых вычислений и язык программирования «Пифагор» / А.И. Легалов, Ф.А. Казаков,

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

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

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

20. Hudak, P. Para-Functional Programming in Haskell. / P. Hudak // In Parallel Functional Languages and Computing, ACM Press (New York) and Addison-Wesley (Reading, MA), (1991), pp. 159-196.

21. Plasmeijer, R. Concurrent Clean. Language Report. / R. Plasmeijer, M. van Eekelen // Hilt High Level Software Tools B.V. and University of Ni-jmegen, 1998 r. (www.cs.kun.nl/~clean).

22. Feo, J. Sisal 90. / J. Feo, P. Miller, S. Skedziewlewski, S. Denton, C. Soloman // Proc. HPFC '95 — High Performance Functional Computing, Denver, CO, April 9-11, (1995), pp. 35-47.

23. Бирюкова, Ю. В. Sisal 90, руководство пользователя. / Ю. В. Бирюкова // Новосибирск: Препринт № 72 ИСИ СО РАН 2000. 84 с.

24. Бажанов, С. Е. Язык функционального параллельного программирования и его реализация на кластерных системах. / С.Е. Бажанов, В.П. Кутепов, Д.А. Шестаков // Теория и системы управления (в печати).

25. Кутепов, В. П. Функциональные системы: теоретический и практический аспекты. / В.П. Кутепов, В.Н. Фальк // Кибернетика, 1979. №1. С. 46-58.

26. Кутепов, В. П. Об интеллектуальных компьютерах и больших компьютерных системах нового поколения / В.П. Кутепов // Изв. РАН. Теория и системы управления, 1996. №5. С. 97-114.

27. Кутепов, В. П. Направленные отношения: теория и приложения. /

28. B.П. Кутепов, В.Н. Фальк // Изв. РАН. Техническая кибернетика. 1994. № 4, 5.

29. Кутепов, В. П. Теория направленных отношений и логика. / В.П. Кутепов, В.Н. Фальк // Изв. РАН. Теория и системы управления. 2000. №5.

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

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

32. Легалов, А.И. Использование типов в языке программирования Пифагор. / А.И. Легалов, Д.В. Привалихин // Проблемы информатизации региона. ПИР-2001: Сб. науч. трудов. Красноярск: ИПЦ КГТУ, 2002. С. 55-61.

33. Привалихин, Д. В. Транслятор функционального языка параллельного программирования. / Д.В. Привалихин // Информатика и информационные технологии. Материалы межвузовской научной конференции. Красноярск, 2002, с. 228-232.

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

35. Привалихин, Д. В. Интегрированная среда разработки программ на функциональном языке программирования «Пифагор» / Д.В. Привалихин // Информатика и информационные технологии. Материалы межвузовской научной конференции. Красноярск, 2002, с. 232-236.

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

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

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

39. Arvind Gostelow К.Р. A new interpreter for data flow schemas and its implications for computer architecture / Arvind Gostelow K.P. // TR 72, Dept. Inform. and Comput. Sci. Univ. Calif., Irvine: 1975, Nov.

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

41. 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.

42. 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.

43. Gelly, O. LAU system software: A high level data driven language for parallel programming. / O. Gelly //In: Proc. of the 1976 Intern. Conf on Parallel Processing, p.255-262.

44. Steele Guy L. Common Lisp the Language / L. Steele Guy //2nd Edition. (http://www.cs.cmu.edu/).

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

46. Казаков, Ф.А. Семантическая модель функционального языка параллельного программирования / Ф.А. Казаков, Д.А. Кузьмин,

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

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

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

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

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

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

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

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

55. Александреску А. Современное проектирование на С++. / А. Александреску // Пер. с англ. М.: Издательский дом «Вильяме», 2002. - 336 с.

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

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

58. Воеводин, В. В. Информационная структура алгоритмов. / В. В. Воеводин // М.: МГУ, 1997 139 с.

59. Бабичев, А. В. Распараллеливание программных циклов./ А.В. Бабичев, В.Г. Лебедев // Программирование. 1983. № 5, с 52-63.

60. Барендрегт, X. Ламбда-исчисление. Его синтаксис и семантика. / X. Барендрегт //Пер. с англ. М.: Мир, 1985. - 606 с.

61. Барский, А. Б. Параллельные процессы в вычислительных системах. Планирование и организация. / А. Б. Барский // М.: Радио и связь, 1980. -256 с.

62. Беркс, А. Предварительное рассмотрение логической конструкции электронного вычислительного устройства. / А. Беркс, Г. Голдстейн, Дж. Нейман // Пер. с англ. В кн.: Кибернетический сборник. Вып. 9. М.: Мир, 1974, с. 7-67.

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

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

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

66. Вирт, Н. Алгоритмы + структуры данных = программы. / Н. Вирт // М.: Мир, 1985.

67. Водяхо, А.И. Стратегии управления вычислительными процессами и их модели / А.И. Водяхо, В.П. Емелин, А.И. Легалов //

68. В кн.: Математическое и программное обеспечение САПР сетевых систем, Йошкар-Ола, 1985.- С. 135-142.

69. Воеводин, Вл.В. Просто ли получить обещанный гигафлоп? / Вл. В. Воеводин // Программирование. 1995, № 4, С. 13-23.

70. Воеводин, В.В. Математические модели и методы в параллельных процессах. / В. В. Воеводин // М.: Наука, Гл. ред. физ.-мат. лит., 1986. -296 с.

71. Гамма, Э. Приемы объектно-ориентированного пректирования. Паттерны проектирования. / Э. Гамма, Р. Хелм, Р. Джонсон, Дж. Влиссидес // Пер. с англ. СПб: Питер, 2001. - 368 с.

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

73. Грицык, В. В. Распараллеливание алгоритмов обработки информации в системах реального времени. / В. В. Грицык // Киев, Наукова думка, 1981.216 с.

74. Дал, У. Структурное программирование. / У. Дал, Э. Дейкстра, К. Хоор // Пер с англ. М.: Мир, 1975. - 247 с.

75. Дейкстра, Э. Дисциплина программирования. / Э. Дейкстра // Пер. с англ. М.: Мир, 1978.

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

77. Зыков, А. А. Основы теории графов. / А. А. Зыков // М.: Наука, 1987.-384 с.

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

79. Системы параллельной обработки. / Под ред. Ивенс Д. // Пер с англ. М.: Мир, 1985. 416 с.

80. Свами, М. Графы, сети и алгоритмы. / М. Свами, К. Тхуласира-ман // Пер. с англ. М.: Мир, 1984. — 455 с.

81. Ильин, В. П. О стратегиях распараллеливания в математическом моделировании. / В. П. Ильин // Программирование. 1999, № 1, с. 41-46.

82. Кнут, Д. Искусство программирования для ЭВМ. Том 1. Основные алгоритмы. / Д. Кнут // Пер. с англ. М.: Мир, 1976. - 736 с.

83. Кнут, Д. Искусство программирования для ЭВМ. Том 2. Получисленные алгоритмы. / Д. Кнут // Пер. с англ. М.: Мир, 1977. - 726 с.

84. Кнут, Д. Искусство программирования для ЭВМ. Том 3. Сортировка и поиск. / Д. Кнут // Пер. с англ. М.: Мир, 1977. - 846 с.

85. Ки-Чанг Ким. Мелкозернистое распараллеливание неполных гнезд циклов. / Ки-Чанг Ким // Программирование. 1997, № 2, с. 52-66.

86. Корнеев, В. В. Параллельные вычислительные системы / В.В. Корнеев М: «Нолидж». - 1999. - 320 с.

87. Костенко, В. А. К вопросу об оценке оптимальной степени параллелизма. / В. А. Костенко // Программирование. 1995, № 4, с. 24-28.

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

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

90. Льюис, Ф. Теоретические основы проектирования компиляторов. / Ф. Льюис, Д. Розенкранц, Р. Стирнз // М.: Мир, 1979.

91. Майерс, Г. Архитектура современных ЭВМ: В 2-х книгах. Кн. 1. / Г. Майерс // М.: Мир, 1985. 364 с.

92. Мультипроцессорные вычислительные системы // Под ред. Ф.Г. Энслоу. Пер. с англ. М.: Энергия, 1976. - 384 с.

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

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

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

96. Уолренд, Дж. Введение в теорию сетей массового обслуживания. / Дж. Уолренд // пер с англ. М.: Мир 1993. - 336 с.

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

98. Языки программирования. / Под ред. Ф. Женюи // Пер. с англ. М.: Мир, 1972. 406 с.