RSS    

   Управление потоками данных в параллельных алгоритмах вычислительной линейной алгебры - (диплом)

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 можно вычислить следующим образом

Страницы: 1, 2, 3, 4, 5


Новости


Быстрый поиск

Группа вКонтакте: новости

Пока нет

Новости в Twitter и Facebook

                   

Новости

© 2010.