Управление потоками данных в параллельных алгоритмах вычислительной линейной алгебры - (диплом)
p>Введение необязательных входов выводит данную модель за рамки стандартной модели управления потоком данных, но придает системе дополнительную гибкость.Первым запускается на выполнение процесс, помеченный как стартовый. После этого параллельная выполняется до тех пор, пока не завершится процесс, помеченный как завершающий. Программа может включать несколько стартовых и завершающих процессов, причем один и тот же процесс может быть одновременно и стартовым и завершающим.
После запуска процесс может взаимодействовать с другими процессами только через каналы. Когда процесс читает данные из входа, его работа приостанавливается до момента поступления данных (предусмотрены функции для асинхронного обмена сообщениями). Входы используются как очереди, и они, подобно каналам в ОС UNIX, буферизуют одно или несколько сообщений до тех пор, пока их не получит адресат. Объем буфера ограничен только доступной емкостью памяти. Каждый вход может быть связан с несколькими выходами.
Далее будут рассмотрены структуры данных для записи ГПД.
2. 1. ГПД
ГПД (Граф Потока Данных) — ориентированный граф, вершинами которого являются процессы, а дугами — каналы. Каждому процессу сопоставлена пара чисел, однозначно определяющая этот процесс, — номер класса процесса и номер экземпляра процесса (о необходимости введения двумерной нумерации процессов будет рассказано несколько позже).
Различие между классом и экземпляром процесса такое же, как и в объектно-ориентированных языках программирования.
Канал определяет однонаправленный поток данных между процессами, он всегда направлен от входа канала к выходу. Между каналами и выходами имеется взаимооднозначное соответствие; в то же время вход может быть соединен с несколькими выходами. Каждому каналу приписывается вес — величина, характеризующая примерный объем данных, пересылаемых по каналу.
Процесс — структура данных, состоящая из набора входов и выходных портов (не путать с выходами). Входы и выходные порты занумерованы. Вход может быть помечен как обязательный. Каждому процессу приписывается вес — величина, характеризующая примерный объем вычислений, выполняемых этим процессом.
Выходной порт — массив выходов.
Выход — тройка чисел , однозначно определяющая вход, к которому подключен данный выход.
Введем систему обозначений.
ГПД обозначим через G (P, C), где P — множество процессов, C — множество каналов. Pi — процессы с номером (i, x), где x < | Pi |.
Pij — процесс с номером (i, j).
In Pij — множество входов процесса (i, j).
| In Pij | — число входов процесса (i, j).
In k Pij — k-й вход процесса (i, j).
Out Pij — множество выходов процесса (i, j).
Out k Pij — выходы процесса (i, j) с номерами (k, x), где x < | Out k Pij | Out kl Pij — выход с номером (k, l).
Пусть X = Out kl Pij, тогда выход X соединен с входом h = X. in процесса с номером (s, w), где s = X. proc, w = X. copy. Т. е. существует канал c = (X, Y), где Y = In h Psw.
2. 2. Шаблон ГПД
Шаблоны ГПД имеют сходные черты с шаблонами в языке С++. Каждый шаблон ГПД обладает набором параметров, после определения которых из шаблона получается конкретный экземпляр ГПД. От параметров может зависеть число процессов ГПД, число выходов процесса. Параметры шаблона вводятся на этапе запуска программы. Это позволяет настраивать программу под конкретные требования пользователя.
Для записи шаблона ГПД был разработан специальный язык DGL (Dataflow Graph Language). Более подробно о DGL можно прочитать в главе “Язык DGL”.
Шаблон ГПД — это ориентированный граф, вершинами которого являются классы процессов, а дугами — каналы, и набор параметров. Каждому классу процесса сопоставлен номер.
Параметры — вектор переменных.
Канал определяет однонаправленный поток данных между процессами, он всегда направлен от входа к выходу.
Класс процесса — структура данных, состоящая из набора входов и выходов. Входы и выходы занумерованы. Вход может быть помечен как обязательный.
Введем систему обозначений.
TG (TP, TC, A) — шаблон ГПД, где TP — множество шаблонов процесса, TC — множество шаблонов канала, A — вектор параметров. Ai — i-й параметр (целое число).
TPi — i-й процесс.
In TPi — множество входов процесса i.
In k TPi — k-й вход процесса i.
Out TPi — множество выходов процесса i.
Out k TPi — k-й выход процесса i.
Пусть X = TPi. Тогда
X. ncopies = ncopies (A) — целочисленная функция от параметров, которая задает число копий процесса X.
Пусть X = Out k TPi. Тогда
X. ncopies = ncopies (p, A) — целочисленная функция, которая задает число копий выхода X. Здесь p — целое число, А — параметры. X. proc — номер процесса, с входом которого соединен данный выход. X. copy = copy (c, p, A) — целочисленная функция. Здесь p и c — целые числа, А — параметры. X. in — номер входа, с которым соединен данный выход.
2. 3. Связь ГПД и шаблона ГПД
Пусть TG (TP, TC, TA) — шаблон ГПД, A — конкретные значения параметров. Введем операцию подстановки Subst параметров А в шаблон TG.
G = Subst A TG — ГПД такой, что
Каждому процессу TPi сопоставлено множество процессов Pi.
| Pi | = (TPi). ncopies (A).
In Pij = In TPi, где j < | Pi |.
Каждому выходу Out k TPi сопоставлено множество выходов Out k Pij, где j < | Pi |. | Out k Pij | = (Out k TPi). ncopies (j, A), где j < | Pi |. (Out kl Pij). proc = (Out k TPi). proc, где l < | Out k Pij |, j < | Pi |. (Out kl Pij). copy = (Out k TPi). copy (l, j, A), где l < | Out k Pij |, j < | Pi |. (Out kl Pij). in = (Out k TPi). in, где l < | Out k Pij |, j < | Pi |.
ЗАМЕЧАНИЕ: при некоторых значениях вектора параметров операция подстановки может быть не определена.
Г Л А В А 3
ЯЗЫК DGL
Язык DGL был специально разработан для описания ГПД. Для ввода програмы на языке DGL можно использовать как простой текстовый редактор, так и специальную программу Rose, которая рисует ГПД на экране компьютера.
Рассмотрим как зписываются графы на языке DGL на основе элементарных примеров.
Выход Out вершины V1 связан со входом In вершины V2.
process V1 { export: Out а V2: In; }
process V2 { import: In; }
2. Имеется N вершин V0, …, VN-1. Вершина W содержит N выходов Out0, …, OutN-1. Выход Outk соединен со входом In вершины Vk, k = 0, …, (N-1).
process V[N] { import: In; }
process W { export: Out [N] а V[c]: In; }
3. Имеется N вершин V0, …, VN-1. Выход Out вершины k соединен со входом In вершины W, k = 0, …, (N-1).
process W { import: In; }
process V[N] { export: Out а W: In; }
4. Имеется N вершин V0, …, VN-1 и N вершин W0, …, WN-1. Выход Out вершины Vk связан со входом In вершины Wk, k = 0, …, (N-1).
process V[N] { export: Out а W[p]: In; }
process W[N] { import: In; }
5. Имеется N вершин V0, …, VN-1 и M вершин W0, …, WM-1. Каждая вершина типа V содержит M выходов Out0, …, OutM-1, причем выход Outk связан со входом In вершины Wk, k = 0, …, (M-1).
process W[M] { import: In; }
process V[N] { export: Out [M] а W[c]: In; }
6. Имеется N вершин V0, …, VN-1. Выход Out вершины Vk связан со входом In вершины V(k+1) mod N, k = 0, …, (N-1).
process V[N] { export: Out а V[(p+1) mod N]: In; import: In; }
Значение N может быть объявлено как внешний параметр. В этом случае N определяется во время запуска программы.
В дальнейшем планируется ввести в язык многомерные массивы процессов, а так же добавить условные операторы if…then…else и case…of. Это позволит описывать более сложные ГПД, в частности, многомерные решетки.
Синтаксис
DGL : :=
“DATAFLOW” “PROGRAM” name “; ”
{“EXTERN” name [“=” integer] “; ”}
{“CONST” name “=” expression “; ”}
{process}
process : :=
“PROCESS” name [“[”number_of_instances “]”]
{directive “; ”}
“{”
{process_attr “; ”}
“EXPORT: ” {export}
“IMPORT: ” {import}
“}”
directive : :=
“LOCAL” | “START” | “TERMINATION”
process_attr : :=
“weight” “=” integer
import : :=
name [“{” import_attr {“; ” import_attr} “}”] “; ”
export : :=
name [“[” number_of_instances “]”]
“-->”
process_name
[“[” process_index “]”]
“: ”
import_name
[“{” export_attr {“; ” export_attr} “}”]
“; ”
number_of_instances : :=
expression
process_index : :=
expression
import_attr : :=
“ARGUMENT”
export_attr : :=
“DATASIZE” “=” integer
Г Л А В А 4
ПРИМЕР ПАРАЛЛЕЛЬНОЙ ПРОГРАММЫ
