Управление потоками данных в параллельных алгоритмах вычислительной линейной алгебры - (диплом)
p>В качестве примера рассмотрим задачу приближенного вычисления числа Пи с использованием правила прямоугольников для вычисления определенного интегралагде
Согласно правилу прямоугольников,
где , а .
Следует отметить, что это “процессорная” программа. Она не затрагивает многие проблемы параллельного программирования, например критическое влияние процессов ввода-вывода. Тем не менее эта задача поможет ознакомиться с основными принципами построения программ, работающих в соответствии с методом управления потоком данных.
Существует множество подходов к решению контрольной задачи. Решение, приведенное ниже, иллюстрирует все основные шаги разработки программы.
4. 1. Конструирование ГПД программы
В пределе разрабатываемая программа может быть создана в виде одного процесса, но при этом теряется параллелелизм. Можно создать множество мелких процессов, таких как один оператор или даже одна арифметическая операция, что приведет к резкому увеличению расходов, связанных с запуском каждого процесса и обменом данных между ними. Следует отметить, что структура решаемой задачи часто наводит на хорошее первое приближение.
Для подсчета числа Пи используется несколько рабочих процессов, которые вычисляют свои части интеграла и пересылают результат суммирующему процессу. Рабочие процессы обращаются за очередным заданием к процессу распределения работ. Вся работа не распределяется заранее равномерно между процессами: один рабочий процесс, если он запущен на более быстрой машине, может выполнить львиную долю работы.
4. 2. Запись ГПД на языке DGL
После того, как граф данных нарисован, каждый процесс, начало и конец каждой дуги помечаются буквенно-цифровым именем, которое используется в языке DGL. Перевод графа потока данных в язык DGL совершается однозначным образом. Каждой вершине ГПД соответствует процесс DGL с тем же именем.
Теперь нарисуем ГПД с помощью программы Rose и запишем его на диск в формате DGL.
DATAFLOW PROGRAM PI;
EXTERN NProcs = 5;
CONST nw = MAX (1, NProcs - 2);
PROCESS Summer [1]; LOCAL;
{
IMPORT:
NumIter {};
PartSum {};
}
PROCESS Worker [nw];
{
EXPORT:
PartSum [1] --> Summator [0] : PartSum {DATASIZE = 0};
Demand [1] --> Manager [0] : DemandList {DATASIZE = 0};
IMPORT:
Arg {};
}
PROCESS Manager [1]; LOCAL; START; TERMINATION;
{
EXPORT:
Done [1] --> Summator [0] : DoneSignal {DATASIZE = 0};
Worker [nw] --> Worker [c] : Arg {DATASIZE = 0};
IMPORT:
DemandList {};
}
4. 3. Компиляция процессов
После того, как ГПД записан на языке DGL, его нужно обработать транслятором dglc. В результате работы транслятора на диске должны появиться следующие файлы: PI. dpr, Manager. pas, ManagerBody. pas, Worker. pas, WorkerBody. pas, Summator. pas, SummatorBody. pas. Далее, программист записывает код каждого процесса в файлах SummatorBody. pas, WorkerBody. pas, ManagerBody. pas, а затем компилирует проектный файл PI. dpr.
Ч А С Т Ь 2
РЕАЛИЗАЦИЯ НЕКОТОРЫХ АЛГОРИТМОВ ВЛА В
СИСТЕМЕ FLOWer
В данной части рассматривается реализация в системе программирования FLOWer некоторых алгоритмов ВЛА, в число которых входят умножение матриц, LU-разложение, решение треугольных СЛУ, QR-разложение, итерационные методы решения СЛУ. Для каждого алгоритма приводятся теоретические оценки ускорения, описание параллельного алгоритма, экспериментальные данные. Для проведения экспериментов использовалась локальная сеть FastEthernet, состоящая из 4-х компьютеров Pentium II 333MHz.
Г Л А В А 1
УМНОЖЕНИЕ МАТРИЦ
Рассмотрим задачу вычисления произведений Ax и AB, где А и В – матрицы, а х — вектор. Отдельно будут рассмотрены ленточные и блочно-диагональные матрицы.
1. 1. Умножение матрицы на вектор
Пусть А – матрица mґn, а х — вектор длины n. Тогда произведение можно записать двумя способами или ,
где аi — i-я строка матрицы А, аi — i-й столбец матрицы А, а (x, y) — скалярное произведение. Различие способов записи можно рассматривать как различие двух способов доступа к данным, что приводит к разным алгоритмам и для задач матричного умножения и решения линейных систем.
Пусть система состоит из р процессоров. Рассмотрим сначала векторно-матричное произведение с помощью линейных комбинаций: . Предположим, что p = n и xi и ai приписаны процессору i. Все произведения xiai вычисляются с максимальным параллелизмом, а затем выполняются сложения по методу сдваивания. Причем синхронизация в данной модели не требуется.
Алгоритм скалярных произведений в некоторых отношениях более привлекателен. Пусть p = m, x и ai приписаны процессору i. Каждый процессор выполняет свое скалярное произведение, и при этом паралелизм максимален.
Выбор алгоритма вычислений зависит от целого ряда обстоятельств. Матрично-векторное умножение неизбежно является частью более широкого процесса вычислений, и основную роль играет способ хранения матрицы А и вектора х. Еще одно существенное соображение — желаемое расположение результата по окончании умножения: в первом случае результат размещается в памяти одного процессора, тогда как в другом он размещен между процессорами.
В реальных системах n и m значительно больше числа процессоров, и каждому процессору передаются несколько строк или столбцов.
1. 2. Матричное умножение
Аналогично рассматриваются алгоритмы умножения матриц А и В.
Пусть матрицы разбиты на блоки
Пусть число процессоров р равно числу st блоков матрицы С. Тогда все блоки можно вычислять одновременно. Рассмотрим специальные случаи разбиения:
s = 1 — матрица А разбита на группы столбцов;
t = 1 — матрица В разбита на группы строк;
s = t = 1 — алгоритм блочного скалярного произведения;
r = 1 — алгоритм блочного внешнего произведения.
Для блочного внешнего произведения распределение блоков по процессорам будет выглядеть следующим образом:
Для простоты будем считать, что матрицы А и В имеют размерность nґn, n=sm, где s — число блоков, m — число строк (столбцов) в блоке. Далее, пусть умножение двух чисел происходит за время Tmul, а пересылка одного числа — за время Tsend.
Процесс вычисления состоит из трех этапов:
пересылка исходных данных на каждый процессор;
вычисление произведения блоков;
пересылка результата.
Пусть t1(n) — время умножения матриц на одном процессоре, tp(n) — время умножения матриц в системе из p = s2 процессоров.
В случае последовательного алгоритма произведение матриц требует n3 операций умножения, пересылки данных не требуются.
В случае параллельного алгоритма пересылка исходных данных выполняется за время 2nmTsend, умножение блоков — за время m2nTmul, пересылка результата — за время n2Tsend. Тогда
Построим график Sp(n) при p=4 и при различных значениях отношения Tsend/Tmul.
При достаточно больших значениях n
Т. е. получаем линейный прирост производительности при n®Ґ.
Совсем другая картина получается, если строить строить график Sp(n) как функции от р при некотором фиксированном значении n. В этом случае Sp(n) сначала резко возрастает до некоторого экстремального значения S’=Sp’(n), а затем начинает плавно убывать. Т. е. мы достигли некоторого оптимального значения числа процессоров p’ и дальнейшее увеличение числа процессоров будет приводить только к замедлению программы. Это объясняется тем, что при увеличении числа процессоров увеличивается и объем передаваемых данных.
Значение p’ в данном конкретном случае несложно вычислить. Оно находится из уравнения p і 1
Решая уравнение, получим . Следует отметить, что при p=p’ максимум эффективности Ep скорее всего не будет достигнут.
Результаты эксперимента
n
t1(n), сек
tp(n), p=2, сек
Sp(n)
1000
1069, 195
571, 646
1, 870
1100
1081, 161
784, 325
1, 378
1200
1870, 029
987, 869
1, 893
1300
2367, 853
1293, 355
1, 831
1400
2966, 311
1618, 987
1, 832
1500
3647, 515
1999, 783
1, 824
1600
5011, 064
2812, 082
1, 782
Возведение в степень блочно-диагональных матриц
Пусть матрица А имеет блочно-диагональный вид, т. е.
где Аii — квадратная матрица.
Очевидно, что Аn можно вычислить следующим образом