Geum.ru

Скачать работу в формате MO Word.<

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

<

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

<

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

<

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

<

1.      Concurrent C++ (CC++) и Fortran M (FM). Эти языки предоставляют собой небольшой набор расширений языков C++ и Fortran и предоставляют программисту явное правление параллелизмом, коммуникациями и распределением заданий между процессорами. Языки CC++ и FM лучше всего подходят для реализации алгоритмов, в которых присутствуют динамическое создание заданий, нерегулярные схемы коммуникаций, а также для написания библиотек параллельного программирования. Недостатком программ, созданных с помощью данных языков программирования, является их недостаточная переносимость. Кроме того, компиляторы этих языков не всегда входят в стандартный комплект программного обеспечения, поставляемый с компьютером. <

2.      межпроцессных коммуникаций (interprocess communication) такие как разделяемая память (shared memory), семафоры (semaphores), очереди сообщений (message queues), сигналы (signals) удобно использовать при программировании в модели разделяемой памяти. При использовнии низкоуровневых средств межроцессных коммуникаций программисту кроме кодирования непосредственно вычислительного алгоритма, требуется самому создавать процедуры синхронизации процессов, что может быть источником дополнительных трудностей. <

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

4.      MPI называют ассемблером для параллельных систем).<

<

В рамках данной дипломной работы была создана система FLOWer Ч набор тилит, облегчающих написание параллельных программ. В основе системы лежит модель правления потоком данных. Обычно в вычислительных системах, управляемых потоком данных, команды машинного ровня правляются доступностью данных, проходящих по дугам графа потока данных (ГПД). В данной системе используется принцип правления крупненным потоком данных (Large-Grain Data Flow), в котором единица планирования вычислений - процесс - крупнее (возможно, намного крупнее), чем одна машинная команда. <

<

Для задания ГПД был разработан специальный язык DGL (Dataflow Graph Language). ГПД, записанный на этом языке, легко настраивается под конкретную многопроцессорную систему - число вершин и дуг графа может определяться через внешние параметры, которые вводятся пользователем, считываются из файла или задавются каким-либо другим способом. В качестве параметров можно использовать число процессоров в системе, степень загруженности системы и т.д.<

<

В состав системы FLOWer входят:<

<

      <

      DGL;<

      <

<

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

<

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

<

Основные понятия параллелелизма<

<

Определение.Степенью параллелизма численного алгоритма называется число его операций, которые можно выполнять параллельно.<

<

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

<

Определение.Ускорением параллельного алгоритма называется отношение<

Скачать работу в формате MO Word.<

Г Л А В 1

<

КРАТКИЙ ОБЗОР

<

Программный комплекс FLOWer спроектирован для работы в массивно-параллельной системе (MPP), которая состоит из однородных вычислительных злов, включающих в себя:<

<

      <

      <

      <

<

Узлы связаны через некоторую коммуникационную среду (высокоскоростная сеть, коммутатор и т.п.). На каждом зле работает полноценная ОС (в данном случае Windows).<

<

В частности, такой системой является локальная сеть, в которой любые два компьютера могут обмениваться данными друг с другом. На любом компьютере могут одновременно работать несколько процессов. <

<

Данная работа была выполнена в локальной сети с общей шиной. В такой сети все процессоры соединены посредством шины. Достоинством такой системы является очень малое число линий связи, однако возможны задержки (конфликт на шине) при использовании шины несколькими процессорами. Это может стать серьезной проблемой при величении числа процессоров.<

<

В состав системы FLOWer входят:<

<

      <

      DGL;<

      <

<

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

<

Создание параллельной программы в системе FLOWer состоит из следующих шагов:<

<

      <

      DGL<

      DGL<

      <

      DLL<

      DGL<

<


Г Л А В 2/h2>

<

МОДЕЛЬ ВЫЧИСЛЕНИЙ

<

Система FLOWer базируется на модели правления потоком данных. В данной модели вычислений программа представляется в виде ГПД. Вершины ГПД соответствуют отдельным процессам - последовательным часткам программы, дуги задают отношения между ними. Точка вершины, в которую входит дуга, называется входным портом (портом импорта или входом), точка, из которой она выходит, - выходным (портом экспорта или выходом). Некоторые входные порты могут быть помечены как обязательные. По дугам передаются данные из одного процесса в другой.<

<

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

<

      <

      <

<

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

<

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

<

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

<

Далее будут рассмотрены структуры данных для записи ГПД.<

<

2.1. ГПД<

<

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

<

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

<

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

<

Процесс Ч структура данных, состоящая из набора входов и выходных портов (не путать с выходами). Входы и выходные порты занумерованы. Вход может быть помечен как обязательный. Каждому процессу приписывается вес - величина, характеризующая примерный объем вычислений, выполняемых этим процессом.<

<

Выходной порт Ч массив выходов.<

<

Выход - тройка чисел <номер класса процесса, номер экземпляра процесса, номер входа>, однозначно определяющая вход, к которому подключен данный выход.<

<

Введем систему обозначений.<

<

      <

      Pi Ча процессы с номером (i, x), где x < | Pi |.<

      Pij Ча процесс с номером (i, j). <

      In Pij Ча множество входов процесса (i, j).<

      In Pij | Ча число входов процесса (i, j).<

      In sub>k Pij Ча k-й вход процесса (i, j).<

      Out Pij Ча множество выходов процесса (i, j).<

      Out sub>k Pij Ча выходы процесса (i, j) с номерами (k, x), где x < | Out sub>k Pij |<

      Out sub>kl Pij Ча выход с номером (k, l).<

      Out sub>kl Pij, тогда выход X соединен с входом h = X.in процесса с номером (s, w), где s = X.proc, w = X.copy. Т.е. существует канал c = (X, Y), где Y = In sub>h Psw.<

<

2.2. Шаблона ГПД<

<

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

<

Для записи шаблона ГПД был разработан специальный язык DGL (Dataflow Graph Language). Более подробно о DGL можно прочитать в главе Язык DGL.<

<

Шаблон ГПД - это ориентированный граф, вершинами которого являются классы процессов, дугами - каналы, и набор параметров. Каждому классу процесса сопоставлен номер.<

<

Параметры Ч вектор переменных.<

<

Канал определяет однонаправленный поток данных между процессами, он всегда направлен от входа к выходу. <

<

Класс процесса Ч структура данных, состоящая из набора входов и выходов. Входы и выходы занумерованы. Вход может быть помечен как обязательный.<

<

Введем систему обозначений.<

<

      <

      Ai - i-й параметр (целое число).<

      TPi - i-й процесс.<

      In TPi - множество входов процесса i.<

      In sub>k TPi - k-й вход процесса i.<

      Out TPi - множество выходов процесса i.<

      Out sub>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 sub>k TPi сопоставлено множество выходов Out sub>k Pij, где j < | Pi |.<

      | Out k Pij | = (Out k TPi).ncopies (j, A), где j < | Pi |.<

      (Out sub>kl Pij).proc = (Out k TPi).proc, где l < | Out k Pij |, j < | Pi |.<

      (Out sub>kl Pij).copy = (Out k TPi).copy (l, j, A), где l < | Out k Pij |, j < | Pi |.<

      (Out sub>kl Pij).in = (Out k TPi).in, где l < | Out k Pij |, j < | Pi |.<


ЗАМЕЧАНИЕ: при некоторых значениях вектора параметров операция подстановки может быть не определена.<

<

<

<

Г Л А В 3

<

ЯЗЫК DGL<

<

Язык DGL был специально разработан для описания ГПД. Для ввода програмы на языке DGL можно использовать как простой текстовый редактор, так и специальную программу Rose, которая рисует ГПД на экране компьютера.<

<

Рассмотрим как зписываются графы на языке DGL на основе элементарных примеров.<

<

1.      Out вершины V1 связан со входом In вершины V2.<

<

Скачать работу в формате MO Word.<

Г Л А В 4

<

ПРИМЕР ПАРАЛЛЕЛЬНОЙ ПРОГРАММЫ<

<

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

Ч А С Т Ь 2

<

РЕАЛИЗАЦИЯ НЕКОТОРЫХ АЛГОРИТМОВ ВЛА В<

СИСТЕМЕ FLOWer<

<

<

В данной части рассматривается реализация в системе программирования FLOWer некоторых алгоритмов ВЛА, в число которых входят множение матриц, LU-разложение, решение треугольных СЛУ, QR-разложение, итерационные методы решения СЛУ. Для каждого алгоритма приводятся теоретические оценки скорения, описание параллельного алгоритма, экспериментальные данные. Для проведения экспериментов использовалась локальная сеть FastEthernet, состоящая из 4-х компьютеров Pentium II MHz. <


Г Л А В 1

<

УМНОЖЕНИЕ МАТРИЦ

<

Рассмотрим задачу вычисления произведений Ax и AB, где А и В - матрицы, х - вектор. Отдельно будут рассмотрены ленточные и блочно-диагональные матрицы.<

<

1.1. множение матрицы на вектор

<

Пусть А - матрица m´n, х - вектор длины n.Тогда произведение можно записать двумя способами<

Результаты эксперимента/h1>

n<

t1(n), сек<

tp(n), p=2, сек<

Sp(n)<

1<

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<

1,783<

1,824<

1600<

5011,064<

2812,082<

1,782<

<


1.3.      матриц<

<

Пусть матрица А имеет блочно-диагональный вид, т.е.<

<

Результаты эксперимента

<

m<

t1(n,m), сек<

tp(n,m), p=2, сек<

Sp(n)<

1<

2131,162<

1097,971<

1,941<

1100<

2235,178

1142,729<

1,956<

1200<

3764,320

1931,411<

1,949<

1300<

4898,564

2506,942<

1,954<

<

<

1.4. Ленточные матрицы<

<

Матрица А порядка n называется ленточной, если <

<

aij = 0, i - j > b1, j - i > b2<

<

Далее будем рассматривать лишь матрицы с симметричной лентой, для которых b1 = b2 = b. Таким образом, ненулевые элементы матрицы расположены только на главной диагонали и на 2b диагоналях, прилегающих к главной сверху и снизу.<

<

Заметим, что если полуширина ленты для А равна a, для В равна b, то полуширина ленты для АВ в общем случае будет равна a+b.<

<

Пусть А - матрица размерности n´n с полушириной ленты a, В Ч матрица размерности n´n с полушириной ленты a. Причем А разбита на img src="images/picture-089-161.gif.xip" title="Скачать документ бесплатно">Скачать работу в формате MO Word.<

Г Л А В 2

<

ПРЯМЫЕ МЕТОДЫ РЕШЕНИЯ ЛИНЕЙНЫХ СИСТЕМ<

<

Рассмотрим систему линейных уравнений<

<

Ax = b<

<

с невырожденной матрицей А размера n´n.<

<

2.1. LU-разложение<

<

Постановка задачи<

<

Построим разложение мтрицы A = LU, где L - нижнетреугольная матрица с единицами на главной диагонали, U - верхнетреугольная матрица.<

<

В качестве алгоритма LU-разложения выберем kij-форму с выбором главного элемента по строке (столбцу). прощенно алгоритм можно записать следующим образом<

<

для k = 1 до n-1<

для i = k+1 до n<

lik = aik/akk<

для j = k+1 до n

aij = aij - likakj<

<

Распараллеливание и оценки производительности<

<

Предположим вначале, что система состоит из p = n процессоров. Тогда один из возможных вариантов организации LU-разложения выглядит так. Пусть i-ая строка матрицы А хранится в процессоре i. На первом шаге первая строка рассылается всем процессорам, после чего вычисления <

<

Скачать работу в формате MO Word.<

Результаты эксперимента

<

n<

t1(n), сек<

tp(n), p=2, сек<

Sp(n)<

1<

450,975<

309,948<

1,455<

1100<

600,691<

408,078<

1,472<

1200<

780,679<

554,960<

1,408<

1300<

993,420<

689,396<

1,441<

<

2.2. Решение треугольных систем<

<

Постановка задачи<

<

После выполнения LU-разложения нужно решать треугольные системы.<

<

Ly = b, Ux = y<

<

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

<

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

<

для i = 1 до n <

для j = 1 до i-1<

bi = bi Ц Lijyj<

yi = bi/Lii<


Распараллеливание<

<

Пусть вычислительная система состоит из p процессоров, размерность матрицы L равна n. Разобьем матрицу L на блоки в соответствии с рисунком<

<

<

Скачать работу в формате MO Word.<

Результаты эксперимента

<

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

<

2.3. QR-разложение<

<

Постановка задачи<

<

Рассмотрим ортогональное приведение матрицы A<

<

A = QR<

<

где Q Чортогональная, R - верхнетреугольная матрицы. В качестве алгоритма решения задачи выберем преобразование Хаусхолдера. На последовательных компьютерах преобразование Хаусхолдера выполняется примерно в два раза медленне, чем LU-разложение. Поэтому данный метод редко используется для решения СЛУ, однако он широко используется при вычислении собственных значений.<

<

Пусть A - матрица n´n. Рассмотрим запись алгоритма на псевдокоде<

<

<

для k = 1 до n-1<

Скачать работу в формате MO Word.<

Результаты эксперимента

<

n<

t1(n), сек<

tp(n), p=2, сек<

Sp(n)<

1300<

1787,780<

1406,593<

1,271<

1400<

2242,265<

1719,528<

1,304<

1500<

2762,694<

2126,785<

1,299<

1600<

4085,485<

2969,102<

1,376<


Г Л А В 3

<

ИТЕРАЦИОННЫЕ МЕТОДЫ РЕШЕНИЯ ЛИНЕЙНЫХ РАВНЕНИЙ<

<

3.1. Метод Якоби<

<

Постановка задачи<

<

Пусть А - невырожденная матрица n´n и нужно решить систему<

<

Ax = b,<

<

где диагональные элементы aii матрицы А ненулевые. Тогда метод Якоби в матричной форме имеет вид<

<

xk+1 = Hxk + d, k = 0, 1, Е, H = D-1B, d = D-1b,<


где D = diag(a11, Е, ann), B = D - A и казано начальное значение х0.<

<

Конечно, метод Якоби сходится не всегда. Приведем две стандартные теоремы сходимости.<

<

Теорема. Если матрица А имеет строгое диагональное преобладание или является неприводимой с диагональным преобладанием, то итерации метода Якоби сходятся при любом начальном приближении х0.<

<

Теорема. Если матрица A = D - B симметрична и положительно определена, то итерации метода Якоби сходятся при любом начальном приближении х0 тогда и только тогда, когда матрица D + B положительно определена.<

<

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

Результаты эксперимента

<

n<

t1(n), сек<

tp(n), p=2, сек<

Sp(n)<

1<

489,634<

,535<

1,468<

1100<

608,457

404,232<

1,505<

1200<

832,035<

514,840<

1,616<

1300<

857,569<

559,942<

1,531<

1400<

992,017<

661,823<

1,499<

<


ЗАКЛЮЧЕНИЕ/h1>

<

Результатом данной работы является программная среда FLOWer, предназначенная для конструирования параллельных программ. Основные идеи, включая язык DGL, на которых базируется система, были разработаны самостоятельно.<

<

Для испытания возможностей системы были реализованы некоторые параллельные алгоритмы ВЛА, даны теоретические оценки их эффективности иа проведены вычислительные эксперименты, которые показали состоятельность и эффективность системы.<

<

<

<