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

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

V- - .1 и

Редькин Андрей Владимирович

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

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

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

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

003472933

Работа выполнена в Федеральном государственном образовательном учреждении высшего профессионального образования «Сибирский федеральный университет», г.Красноярск.

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

доктор технических наук, профессор Легалов Александр Иванович

Официальные оппоненты: доктор технических наук, профессор

Рубан Анатолий Иванович доктор технических наук, профессор Опарин Геннадий Анатольевич

Ведущая организация: Институт систем информатики имени А.П. Ершова

Защита состоится 26 июня 2009 года в 14 часов на заседании диссертационного совета ДМ 212.099.05 при Сибирском федеральном университете по адресу: г. Красноярск, ул. Киренского, 26, ауд. УЛК-115.

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

Автореферат разослан 26 мая 2009 г.

СО РАН

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

Вейсов Е.А.

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

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

На сегодняшний день получили широкое распространение несколько, принципиально отличающихся друг от друга, систем параллельного программирования. Например, для многоядерных вычислительных систем (ВС) и параллельных ВС с общей памятью используются многопоточные библиотеки и система программирования ОрепМР. При разработке программ для систем с распределенной памятью наибольшую популярность получил стандарт MPI. Следует отметить, что программы, созданные с применением этих средств, эффективно выполняются только на соответствующих им ВС. При переносе приложения на параллельную ВС с другой архитектурой его, как правило, приходится переписывать заново. Архитектурная зависимость параллельных программ порождается не только различиями в организации ВС. Даже в рамках одной архитектуры перенос программы с одной системы на другую может привести к разбалансировке вычислений из-за отличий в скоростных соотношениях процессоров и каналов передачи данных. Это ведет к использованию методов архитектурно-независимого параллельного программирования.

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

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

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

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

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

Для достижения указанной цели в работе решаются следующие задачи.

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

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

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

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

Научная новизна и положения, выносимые на защиту.

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

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

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

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

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

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

2 Полученные научные и практические результаты использованы в учебном процессе по дисциплинам «Технология программирования» и «Модели параллельных вычислений» в ФГОУ ВПО «Сибирский федеральный университет».

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

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

- третья Сибирская школа-семинар по параллельным вычислениям, Томск, 2006;

- шестая межрегиональная школа-семинар «Распределенные и кластерные вычисления», Красноярск, 2006;

- четвертая Российско-германская школа по параллельным вычислениям, Новосибирск, 2007;

- четвертая Сибирская школа-семинар по параллельным вычислениям, Томск, 2007;

- Всероссийские научно-технические конференции «Молодежь и наука —■ XXI век», Красноярск, 2005-2008;

- третья международная конференция «Параллельные вычисления и задачи управления» РАСО '2006, Москва;

- международная научная конференция Параллельные вычислительные технологии (ПаВТ'2009), Нижний Новгород.

Сведения о внедрении. Результаты работы использованы при выполнении: научно-методического проекта Сибирского Федерального университета №10 «Решение некоторых задач прикладной математики и информатики для повышения потенциала образовательного процесса»; проекта Сибирского Федерального университета «Использование технологий параллельной обработки в научной, образовательной и организационной деятельности»; проекта №25 «Среда разработки для языка параллельного программирования Пифагор» в рамках «Программы развития СФУ на 2007-2010 годы».

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

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

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

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

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

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

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

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

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

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

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

Обозначим асинхронный список через Ам, где N - количество порождаемых в нем элементов. Тогда ее структуру можно описать следующим рекурсивным выражением:

= если N=0

Аи = ((¡, А), если N>0.

где (Л - головной элемент порождаемого списка, А^'1 - асинхронный список из оставшихся N-1 элементов, А0 - пустой асинхронный список, (.) - пустой список данных.

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

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

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

N

с = АХВ=^а1хЬ1

1=1

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

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

//суммирование элементов вектора S_BinTreeSum « funcdef А { Len « А:|;

return« . А [ ( (Len, 2) : [<, = ,>]) :?]А ( {А:[]J, {А:+}, { block {

OddVec « А: [ (l,Len,2) -...]; EvenVec « А: [(2,Len,2) :..]; {[OddVec,EvenVec]: S_BinTreeSum):+ »break;

}

}

)

>

//перемножение пар из векторов S_PairProduct « funcdef A {

VI« A:l; V2<< A:2; return« (VI ,V2) :#: []:*:(.);

}

//скалярное перемножение векторов S_VecScalProd « funcdef A{

return« A:S_PairProduct:S_BinTreeSum;

}

Временные соотношения между выполняемыми функциями представлены на рисунке 1.

Функция 1 Синхронизация данных

tl Передача данных

td Функция 2 к М к

^ w Ч W ^ w

Получение аргумента Получение аргумента 1

функции 1 функции 2

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

Даже при частичной готовности результатов первой функции выполнение второй функции невозможно, что ограничивает скорость вычислений и парал-

лелизм. Если время выполнения первой функции t/, второй -12, и время затрачиваемое на передачу данных - fc , то общее время выполнения двух функций будет равно сумме временных затрат: to6u,=ti+t2+td.

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

// Функция, возвращающая сумму элементов // асинхронного списка A_AsyncSum<< funcdef А {

// Формат аргумента: A=asynch(xl, х2, ... , хп) // где xl, х2, ... , хп - числа

х1<< А:1; // Поступивший головной элемент данных

tail_l« А:-1; // Хвост асинхронного списка // Проверка на пустоту остатка списка [(tail_l:[IsEmptyDataList, IsNotEmptyDataList]:?]л (

xl, //В списке, только один элемент,

// определяющий сумму { // Выделение второго аргумента // с последующим суммированием block {

х2<< tail 1:1; // второй аргумент

s« (xl,x2): + ; // сумма двух элементов

tail_2<< tail_l:-l; // "хвост" от "хвоста" // Рекурсивная обработка оставшихся элементов [(tail_2:[IsEmptyDataList,

IsNotEmptyDataList]:?]А

(

s,

{ asynch( tail_2:[], s):A_AsyncSum } ) : . »break

}

>

) : . »return;

}

//перемножение пар из векторов A_PairProduct«funcdef А{ VI «А: 1 ; V2«A:2;

return« (VI, V2) :#:[]:* : asynch ;

}

//скалярное перемножение векторов A_VecScalProd«funcdef А{

re turn«A: A_PairPr oduc t: A_AsyncSum ;

}

Функция перемножения A_PairProduct обеспечивает формирование на выходе асинхронного списка, элементы которого, по мере появления, поступают в функцию суммирования A_AsyncSum (рисунок 2).

А, Аз В, Вг

Рисунок 2 - Пример вычислений с применением асинхронных списков

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

Функция 1

Передача данных

Функция 2

Получение аргумента Получение первого функции 1 элемента аргумента

функции 2

Рисунок 3 - Конвейерное взаимодействие функций при использовании асинхронного списка

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

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

На основе анализа функционально-потоковых параллельных программ предложены дополнительные операции, расширяющие язык функционально-потокового параллельного программирования. Это ряд встроенных функций для работы со списками (insert, exchange, append, permute, drop, take) и операция «прямой интерпретации», позволяющая производить не доступные ранее действия с параллельными списками. Предложенные языковые средства позволяют создавать архитектурно-независимые параллельные программы с применением более мощных конструкций.

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

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

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

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

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

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

Рисунок 4 - Трансляция функционально-потоковых программ

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

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

Abs« funcdef X {

[((X,О):[<,>=]):?]" ({X:-}, X):. »return

}

О 5

X 0 < >=

* Р

б ±+9

(С) (С) © © (с)

I I

ПЬ:

:---V--!

>

т ▼

N

а

&

14

0

а @

,6 ц

17 (Я)

11 (с) 12

13

15

а) информационный граф

б) управляющий граф

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

Управление вычислениями осуществляется посредством вызова вершин информационного графа из вершин управляющего графа. Такая связь обеспечивает активацию вычислений (рисунок 6).

Информационный граф

Управляющий граф

Запуск обработчика вершин ИГ

Завершение обработчика вершин ИГ

Рисунок 6 - Связь вершин информационного и управляющего графов

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

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

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

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

Поступающие Порождаемые

Рисунок 7 - Функциональная схема событийного процессора

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

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

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

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

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

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

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

Модуль

Рисунок 8 - Структура системы инструментальной поддержки

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

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

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

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

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

В приложении А перечислены синтаксические и семантические изменения языка Пифагор предлагаемые в данной работе.

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

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

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

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

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

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

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

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

1 Редькин, A.B. Событийное управление выполнением функционально-потоковых параллельных программ / A.B. Редькин, А.И. Легалов // Научный вестник Новосибирского государственного технического университета. - №3(32). - 2008. - С. 111-117.

2 Легалов, А.И. Функционально-потоковое параллельное программирование при асинхронно поступающих данных / А.И. Легалов, A.B. Редькин, И.В. Матковский // Параллельные вычислительные технологии (ПаВТ'2009): Труды международной научной конференции (Нижний Новгород, 30 марта - 3 апреля 2009 г.). Челябинск: Изд. ЮурГУ, 2009. -С. 573-578.

3 Редькин, A.B. Промежуточное представление функционального языка потокового программирования / A.B. Редькин // Третья Сибирская шко-лы-семинар по параллельным вычислениям ; под ред. проф. A.B. Стар-ченко. Томск: изд-во Том. ун-та, 2006. - С. 121-125.

4 Легалов, А.И. Расширение асинхронного управления по готовности данных / А.И. Легалов, A.B. Редькин // Труды III Международной конференции «Параллельные вычисления и задачи управления» РАСО '2006. Москва, Институт проблем управления им. В.А. Трапезникова РАН, -

2006.-С. 1272-1281.

5 Редькин, A.B. Событийная интерпретация функционально-потоковых параллельных программ // Четвертая Российско-германская школа по параллельным вычислениям. Научная сессия. Тез. докл. Новосибирск,

2007.-С. 29-30.

6 Редькин, A.B. Среда разработки для языка параллельного программирования ПИФАГОР / A.B. Редькин // Четвертая Сибирская школа-семинар по параллельным вычислениям. Тез. докл. Томск, 2007. - С. 20-22.

7 Редькин, A.B. Система инструментальной поддержки языка параллельного программирования ПИФАГОР / A.B. Редькин // Молодежь и наука: начало XXI века: Сб. материалов Всероссийской научно-технической конференции студентов, аспирантов и молодых ученых: в 4 ч. - Ч. 1. Красноярск, 2007. - С. 26-29.

8 Редькин, A.B. Система интерпретации программ на языке ПИФАГОР / A.B. Редькин // Молодежь и наука: начало XXI века: Сб. материалов Всероссийской научно-технической конференции студентов, аспирантов и молодых ученых: в 5 ч. - Ч. 2. Красноярск, 2008. - С. 100-102.

9 Редькин, A.B. Промежуточное представление информационного графа для языка Пифагор / A.B. Редькин // Информатика и информационные технологии. Красноярск. - 2004. - С. 205-209.

Соискатель:

Подписано в печать 22.05.2009. Заказ № Формат 60x90/16. Усл. печ. л.1. Тираж 100 экз. ИПК Сибирского федерального университета 660074, Красноярск, ул. Киренского 28

Введение.

1 Динамические параллельные вычисления на основе асинхронных списков.

1.1 FIFO-сети для описания асинхронных вычислений.

1.2 Асинхронные вычисления в схемах потока данных Денниса.

1.3 Асинхронные списки в языке Пифагор.

1.4 Использование асинхронных списков для управления параллельными вычислениями.

1.4.1 Конвейерное взаимодействие асинхронных функций.

1.5 Использование асинхронного списка в алгоритмах сортировки.

1.5.1 Асинхронная сортировка перебором.

1.5.2 Быстрая асинхронная сортировка.

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

1.6.1 Операция insert.

1.6.2 Операция exchange.

1.6.3 Операция append.

1.6.4 Операция permute.

1.6.5 Операции drop и take.

1.7 Операция прямой интерпретации в языке Пифагор.

1.8 Выводы.

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

2.1 Методы организации потоковых параллельных вычислений.

2.1.1 Организация вычислений в языке Sisal.

2.1.2 Организация потоковой вычислительной системы с использованием императивных языков программирования.

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

2.2 Информационный граф функционально-потоковой параллельной программы.

2.3 Управляющий граф функционально-потоковой параллельной программы

2.3.1 Генератор сигнала.

2.3.2 Смеситель сигналов.

2.3.3 Асинхронный смеситель сигналов.

2.3.4 Интерпретатор сигналов.

2.3.5 Синхронизатор сигналов.

2.3.6 Управление вычислениями в задержанных подграфах.

2.4 Формирование управляющего графа.

2.5 Реализация стратегий управления посредством преобразования управляющих графов.

2.6 Выводы.

3 Событийный процессор для функционально-потоковых параллельных вычислений.

3.1 Внутренние представления графов и данных.

3.1.1 Внутреннее представление информационного графа.

3.1.2 Представление констант и данных.

3.1.3 Внутреннее представление функции.

3.1.4 Внутреннее представление управляющего графа.

3.2 Структура событийного процессора.

3.2.1 Структура события.

3.2.2 Событийное управление для параллельных списков.

3.2.3 Поток событий.

3.2.4 Событийное управление для задержанных списков.

3.3 Параллельные вычисления с использованием событийного процессора.

3.4 Выводы.

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

4.1 Общая структура системы.

4.2 Модель данных системы.

4.3 Транслятор.

4.4 Хранение информационных, управляющих графов и вспомогательных структур данных.:.

4.5 Использование внешних функций.

4.6 Визуализация графов.

4.7 Реализация возможностей отладки программ.

4.7.1 Отладка в режиме трассировки событий.

4.8 Интерфейс пользователя.

4.8.1 Среда доступа к хранилищу функций и графов.

4.8.2 Графический интерфейс событийного отладчика программ.

4.9 Выводы.

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

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

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

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

Методы архитектурно-независимого параллельного программирования опираются на использование функциональных и потоковых языков, описывающих только информационный граф программы без привязки к системе исполнения. К таким языкам относятся Пифагор [5, 6, 7], Sisal [8], FPTL [9] и ряд других. Управление вычислениями в таких языках, как правило, задается неявно, что позволяет использовать различные подходы к его реализации [10, 11, 12].

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

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

Для достижения указанной цели в работе решаются следующие задачи:

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

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

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

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

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

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

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

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

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

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

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

2 Полученные научные и практические результаты использованы в учебном процессе по дисциплинам «Технология программирования» и «Модели параллельных вычислений» в ФГОУ ВПО «Сибирский федеральный университет».

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

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

- третья Сибирская школа-семинар по параллельным вычислениям, Томск, 2006;

- шестая межрегиональная школа-семинар «Распределенные и кластерные вычисления», Красноярск, 2006;

- четвертая Российско-германская школа по параллельным вычислениям,

Новосибирск, 2007;

- четвертая Сибирская школа-семинар по параллельным вычислениям, Томск, 2007;

- Всероссийские научно-технические конференции «Молодежь и наука -XXI век», Красноярск, 2005-2008;

- третья международная конференция «Параллельные вычисления и задачи управления» РАСО '2006, Москва;

- международная научная конференция Параллельные вычислительные технологии (ПаВТ'2009), Нижний Новгород.

Сведения о внедрении.

Результаты работы использованы при выполнении: научно-методического проекта Сибирского Федерального университета №10 «Решение некоторых задач прикладной математики и информатики для повышения потенциала образовательного процесса»; проекта Сибирского Федерального университета «Использование технологий параллельной обработки в научной, образовательной и организационной деятельности»; проекта №25 «Среда разработки для языка параллельного программирования Пифагор» в рамках «Программы развития СФУ на 2007-2010 годы».

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

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

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

4.9 Выводы

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

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

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

Заключение

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

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

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

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

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

1. GNU Pthread The GNU Portable Threads Электронный ресурс. - Режим доступа : http://www.gnu.org/software/pth/, свободный. - Загл. с экрана.

2. The OpenMP API specification for parallel programming Электронный ресурс. Режим доступа : http://www.openmp.org, свободный. - Загл. с экрана.

3. Message Passing Interface Forum Электронный ресурс. Режим доступа : http://www.mpi-forum.org, свободный. - Загл. с экрана.

4. Легалов, А. И. На пути к переносимым параллельным программам / А. И. Легалов и др. // Открытые системы. 2003. - № 5. - С. 36-42.

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

6. 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, №3 - P. 1-17.

7. Касьянов, В. Н. Функциональный язык SISAL 3.0 / В. Н. Касьянов, Ю. В. Бирюкова, В. А. Евстигнеев // Поддержка супервычислений и Интернеториентированные технологии. Новосибирск - 2001. — С. 54-67.

8. Vijayaraghavan, V. Control flow extensions to the data flow language SISAL / V. Vijayaraghavan, K.M. Kavi, B. Shirazi //Applied Computing, 1991. -P. 130-38.

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

10. Легалов, А. И. Об управлении вычислениями в параллельных системах и языках программирования / А. И. Легалов // Научный вестник НГТУ.2004.-№3 (18).-С. 63-72.

11. Kahn, G. The semantics of a simple language for parallel programming / G. Kahn // Information processing / ed. by J. L. Rosenfeld. North Holland, Amsterdam, 1974. - P. 471-475.

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

13. Kahn, G. The semantics of a simple language for parallel programming / G. Kahn // Information processing / ed. by J. L. Rosenfeld. North Holland, Amsterdam, 1974.-P. 471-475.

14. Dennis, J. B. Data flow schemas / J. B. Dennis, J. B. Fosseen, J. P. Linderman // Proc. of the Internat. Symp. on Theoretical Programming. Lect. Notes Comput. Sci. London, UK: Springer-Verlag. - 1972. - Vol. 5. - P. 187-216.

15. Dennis, J. B. First Version Data of a Flow Procedure Language / J. B. Dennis // New York: Springer-Verlar. 1974. - P. 362-376.

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

17. Arvind A new interpreter for data flow schemas and its implications for computer architecture / Arvind, K.P. Gostelow // TR 72, Dept. Inform, and Com-put. Sci. Univ. Calif., Irvine. - 1975, -P.

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

19. Легалов, А. И. Построение параллельных алгоритмов'. / А. И. Легалов // Открытые системы. 2004. - № 9 (101). - С. 64-68.

20. Кормен, Т. Алгоритмы: построение и анализ. / Т. Кормен, Ч. Лейзерсон, Р. Ривест; пер. с англ. М.: МЦНМО, 1999. - 960 с.

21. Introduction to Parallel Computing, Second Edition./ A. Grama et al.. -Addison Wesley, 2003. 856 p.

22. Skedzielewski, S. К. IF1 An intermediate form for applicative languages, version 1.0 / S. K. Skedzielewski, J. Glauert; Tech. Rep. / Lawrence Livermore National Laboratory; M-170- Livermore, CA, 1985. - 68 p.

23. Welcome, M. L. IF2 An applicative language intermediate form with explicit memory management / M. L. Welcome et al. ; Tech. Rep. / Lawrence Livermore National Laboratory; M-195- Livermore, CA, 1986. - 37 p.

24. Стасенко, А. П. Внутреннее представление системы функционального программирования Sisal 3.0 / А. П. Стасенко; Препр. / РАН. Сиб. Отд-е. ИСИ; № 110.- Новосибирск, 2004. - 54 с.

25. Легалов, А. И. Функциональный язык для создания архитектурно-независимых параллельных программ. / А. И. Легалов // Вычислительные технологии. 2005. - № 1 (10). - С. 71-89.

26. Легалов, А. И. Влияние стратегии управления на организациюпараллельных вычислительных систем / А. И. Легалов // IV Всесоюзная школа-семинар "Распараллеливание обработки информации" ; Тезисы докладов и сообщений. Львов, 1983. — Часть 3. - С. 218-219.

27. Стасенко, А. П. Система интерфейсов транслятора во внутреннее представление IR1 / А. П. Стасенко // Методы и инструменты конструирования и оптимизации программ Новосибирск,: Институт систем информатики имени А. П. Ершова СО РАН, 2005. - С. 229-238.

28. Касьянов, В. Н. Реструктурирующие преобразования: алгоритмы распараллеливания циклов / В. Н. Касьянов, И. Л. Мирзуитова // Программные средства и математические основы информатики. -Новосибирск. 2004. - С. 142-188.

29. Барский, А.Б. Вычислительная система, управляемая потоком данных' / А.Б. Барский, В.В. Шилов // Приложение к журналу "Информационные технологии". 2000. - №8. - 24 с.

30. Барский, А.Б. Потоковая вычислительная система: программирование и оценка эффективности. / А.Б. Барский, В.В. Шилов // Приложение к журналу "Информационные технологии". 2003, №7. 24 с.

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

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

33. Легалов, А. И. Стратегии управления вычислениями / А. И. Легалов //

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

35. Редькин, А.В. Промежуточное представление информационного графа для языка Пифагор / А.В. Редькин // Информатика и информационные технологии. Красноярск. 2004. - С. 205-209.

36. Python Programming Language Official Website Электронный ресурс.,-Режим доступа : http://www.python.org/, свободный. - Загл. с экрана.

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

38. Blelloch, G. E. NESL: A Nested Data-Parallel Language (Version 3.1) / G. E. Blelloch. // Technical Report CMU-CS-95-170, Carnegie Mellon University, Pittsburgh, PA, 1995. - P.

39. Реконфигурируемые мультиконвейерные вычислительные структуры /

40. И.А. Каляев и др. Ростов-на-Дону. Издательство ЮНЦ РАН, 2008 -393 с.

41. D. G. Fritz. An overview of hierarchical control flow graph models. / D.G. Fritz, R. G. Sargent // Proceedings of the 27th conference on Winter simulation Arlington, Virginia, United States 1995. - p.1347-1355.

42. Comparison of Parallel Sorting Algorithms on Different Architectures. / Nancy M. A. et al.. // Technical Report 98-029, Department of Computer Science, Texas A&M University, 1996.

43. Wesley, M. J. Advances in Dataflow Programming Languages. ACM Computing Surveys, / M. J. Wesley, J. R. Paul Hanna, R. J. Millar // Vol. 36, No. 1, 2004.-P 1-34.

44. Corretjer, I. Configuration and Representation of Large-Scale Dataflow Graphs using the Dataflow Interchange Format / I. Corretjer, C.-J. Hsu, S. S. Bhattacharyya // Signal Processing Systems Design and Implementation, SIPS •06. IEEE, 2006, P. 10-15.

45. Полин, E.JI. Классификация моделей параллельных вычислительных процессов по признакам ширины и общности. / E.JI. Полин, К.В. Защелкин // Труды Одесского политехнического университета, 2004. -Вып. 1(21).-С. 1-6.

46. Matsubara, Y. Necessity of timing dependency in parallel programming languages. / Matsubara, Y. // High Performance Computing in the Asia-Pacific Region, 2000. Proceedings. The Fourth International Conference, 2000. vol.1 -P.19-21.

47. Dennis, J. B. A preliminary architecture for a basic data-flow processor. / J. B. Dennis, D. P. Misunas // In Proceedings of the 2nd Annual Symposium on

48. Computer Architecture, 1975.-P. 126-32.

49. Стасенко, А. П. Транслирующие компоненты системы функционального программирования SFP / А. П. Стасенко и др. // Современные проблемы конструирования программ. Новосибирск, 2002. - С. 69-87.

50. Stasenko, А. P. Sisal 3.1 language structures decomposition / A. P. Stasenko // Bull. Novosibirsk Сотр. Center. Ser. Computer Science. -Novosibirsk, 2006. Iss. 24. - 8 p.

51. Малышкин, В. Э. Введение в параллельное программирование мультикомпьютеров / В. Э. Малышкин Новосибирск, 2003. - 268 с.

52. Кутепов, В. П. Модель асинхронных вычислений значений функций в языке функциональных схем / В. П. Кутепов, В. Н. Фальк // Программирование. 1978. — № 3. - С. 3-15.

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

54. Легалов, А. И. Функциональный язык для создания архитектурно-независимых параллельных программ. / А. И. Легалов // Вычислительные технологии. 2005. -№ 1 (10). - С. 71-89.

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

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

57. Легалов, А. И. Эволюционное расширение программ в функциональном языке параллельного программирования / А. И. Легалов, Д. В.

58. Привалихин // Вестник Красноярского государственного университета. -Красноярск,2004. № 5/2. - С. 40-48.

59. Фридман, А. C/C++. Архив программ / А. Фридман, Л. Кландер, X. Шильдт; пер. с англ. М.: ЗАО «Издательство БИНОМ», 2001. - 638 с.

60. Керниган, Б. Язык программирования Си / Керниган Б., Ритчи Д.; пер. с англ. М.: Финансы и статистика, 1992. - 272 с.

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

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

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

64. Вирт, Н. Алгоритмы + структуры данных = программы / Н. Вирт; пер. с англ. М.: Мир, 1982. - 406 с.

65. Бентли, Д. Жемчужины программирования. / Д. Бентли; пер. с англ. -СПб.: Питер, 2002. 272 с.

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

67. Ахо, А. Построение и анализ вычислительных алгоритмов. / А. Ахо, Дж.Хопкрофт, Дж. Ульман; пер. с англ. М.: Мир, 1979. - 536 с.

68. Ахо А. Структуры данных и алгоритмы / А. Ахо, Дж. Хопкрофт, Дж. Ульман; пер. с англ. М.: Вильяме, 2001.- 384 с

69. Гудман, С. Введение в разработку и анализ алгоритмов. / С. Гудман, С.Хидетниеми; пер. с англ. М.: Мир, 1981. - 368 с.

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

71. Лингер, Р. Теория и практика структурного программирования / Р. Лингер, X. Миллс, Б. Уитт; пер. с англ. М.: Мир, 1982. - 406 с.

72. Растрнгин, JI. А. Адаптация сложных систем. Методы и приложения./ Л. А. Растригин. Рига, «Зинатне», 1981. -375с.

73. Редькин, А.В. Событийное управление выполнением функционально-потоковых параллельных программ / А.В. Редькин, А.И. Легалов // Научный вестник НГТУ. 2008. -№3(32), - С. 111-117.

74. Редькин, А.В. Промежуточное представление функционального языка потокового программирования / А.В. Редькин // Третья Сибирская школа-семинар по параллельным вычислениям / под ред. проф. А.В. Старченко. Томск: изд-во Том. Ун-та, 2006. С. 121-125.

75. Редькин, А.В. Событийная интерпретация функционально-потоковых параллельных программ // Четвертая Российско-германская школа по параллельным вычислениям. Научная сессия. Тез. докл. Новосибирск, 2007.-С. 29-30.

76. Редькин, А.В. Среда разработки для языка параллельного программирования ПИФАГОР / А.В. Редькин // Четвертая Сибирскаяшкола-семинар по параллельным вычислениям. Тез. докл. Томск, 2007. — С. 20-22.

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

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

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

80. Арыков, С.Б. Система асинхронного параллельного программирования "Аспект" / С.Б. Арыков, В.Э.Малышкин // Вычислительные методы ипрограммирование 2009. - Т.9 - С. 48-52.

81. Опарин, Г.А. Технология синтеза модульных параллельных программ для DVM-системы / Г.А. Опарин, А.П. Новопашин // Труды VII Международного симпозиума "Интеллектуальные системы". М.: РУСАКИ, 2006. - С. 468-471.

82. Рубан, А. И. Глобальная оптимизация методом усреднения координат: Монография / А. И. Рубан. Красноярск: ИПЦ КГТУ, 2004. 302 с.

83. Tamara Munzner. НЗ: Laying Out Large Directed Graphs in 3D Hyperbolic Space. // Proceedings of the 1997 IEEE Symposium on Information Visualization, October 20-21 1997, Phoenix, AZ, 1997. P. 2-10.

84. Drawing Graphs: Methods and Models // Lecture Notes in Computer Science) . Springer, 2001.

85. Удалова, Ю.В. Интегрированная среда разработки программ на параллельном функцио-нальном языке ПИФАГОР/ Ю.В. Удалова// Информатика и информационные техноло-гии. Красноярск 2004.

86. Удалова, Ю.В. Среда разработки программ на языке ПИФАГОР под ОС LINUX. /Ю.В. Удалова, Д.А. Кузьмин //Распределенные и кластерные вычисления. Красноярск 2005.

87. Удалова, Ю.В. О верификации функционально-потоковых параллельныхпрограмм на примере задачи разделения множеств. / Ю.В. Удалова //Распределенные и кластерные вычисления, Красноярск 2006.

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

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

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

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

92. Эндрюс, Г. Р. Основы многопоточного, параллельного и распределенного программирования.: Пер. с англ. / Г. Р. Эндрюс М.: Издательский дом «Вильяме», 2003. - 512 с.