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

ВВЕДЕНИЕ

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

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

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

1.

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

2.

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

3.

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

4.

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

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

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

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

·

DGL;

·

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

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

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

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

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

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

где T1 — времявыполнения алгоритма на одном процессоре, Тp — время выполнения алгоритма в системе из p процессоров.

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

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

где T’1 — времявыполнения алгоритма на одном процессоре, Тp — время выполнения алгоритма в системе из p процессоров.

Определение.Эффективностью параллельногоалгоритма называется величина

Очевидно, что Sp SYMBOL 163 f «Symbol» s 12Ј p, S’p SYMBOL 163 f «Symbol» s 12Ј Sp, EpSYMBOL163 f «Symbol» s 12Ј. Если алгоритм достигает максимального ускорения (Sp= p), то Ep = 1.

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

·

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

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

Рассмотрим формальную модель системы, в которой

где SYMBOL97 f «Symbol» s 12a1 — доляопераций, выполняемых только одним процессором, SYMBOL 97 f «Symbol» s 12a2 — доля операций, выполняемых со средней степенью параллелизма k < p, SYMBOL 97 f «Symbol» s 12a3 — доля операций, производимых со степенью параллелизма p, td — общее время, требуемое для подготовки данных.

Различают несколько специальных случаев этой формулы.

Случай 1.SYMBOL 97 f «Symbol» s 12a1= 0, SYMBOL97 f «Symbol» s 12a2 = 0, SYMBOL 97 f «Symbol» s 12a3= 1, td = 0.Здесь ускорение максимально.

Случай 2.SYMBOL 97 f «Symbol» s 12a1= 0, SYMBOL97 f «Symbol» s 12a2 = 1, SYMBOL 97 f «Symbol» s 12a3= 0, td = 0.Теперь Sp = k < p.

Случай 3.SYMBOL 97 f «Symbol» s 12a1= SYMBOL 97f «Symbol» s 12aSYMBOL 97 f «Symbol» s 12a2= 0, SYMBOL97 f «Symbol» s 12a3 = 1 — SYMBOL 97 f «Symbol» s 12atd = 0. Вэтом случае

Данная формула выражает законАмдаля-Уэра. Следует отметить очень быстроеубывание Sp для малыхзначений SYMBOL97 f «Symbol» s 12a

Используя последнюю формулу, можно примерно оценить долюпараллельных вычислений

Случай 4. tdвелико. Этот случай показывает, что при достаточно большом td можно получить Sp < 1. Таким образом, возможно, чтодля задач с интенсивными обменами использование нескольких процессоровоказывается менее выгодным, чем использование одного.

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

Подход к измерению ускорения, который потенциально может учесть обе названные проблемы, состоит в том,чтобы измерять скорость вычислений по мере того, как растут размер задачи ичисло процессоров. Рассмотрим, например, задачу матрично-векторного умножения Ax. Если A- n*n-матрица, то потребуется 2n2 — n операций. Предположим, что при исходном порядке n вычисления на единственном процессореидут со скоростью 1 MFLOP. Затем мы удваиваем n, и число операций при большом n увеличиваетсяпримерно в 4 раза. Если задача решается на 4 процессорах со скоростью 4 MFLOP,то мы достигли максимального ускорения.

Вообще, пусть размер задачи определяется параметров n, а числоопераций есть f(n) прирастущем nи p = SYMBOL97 f «Symbol» s 12af(n). Если n1 — размер задачи, посильный для одного процессора, то соответствующий размерзадачи np длясистемы из pпроцессоров определяется равенством f(np)= pf(n1) (чтобы число операций, выполняемых p процессорами, в p разпревосходило число операций одного процессора).

Определение.Параллельныйалгоритм обладает свойством локальности,если он использует локальные данные гораздо чаще, чем удаленные. Наряду спараллелизмом и масштабируемостью это свойствоявляется основным требованием к параллельному програмномуобеспечению. Важность этого свойства определяется отношением стоимостейудаленного и локального обращения к памяти. Это отношение может варьироватьсяот 10:1 до 1000:1 и больше, что зависит от используемой аппаратуры.

Метод оценкипроизводительности

Задачейпрограммиста является проектирование и реализация программ, которыеудовлетворяют требованиям пользователя в смысле производительности и корректнойработы. Производительность является достаточно сложным и многостороннимпонятием. Кроме времени выполнения программы и масштабируемости следует такжеанализировать механизмы, отвечающие за генерацию, хранение и передачу данных посети, оценивать затраты, связанные с проектированием, реализацией,эксплуатацией и сопровождением программного обеспечения. Существуют весьмаразнообразные критерии, с помощью которых оценивается производительность. Срединих могут присутствовать: время выполнения программы, ускорение иэффективность, требования по памяти, производительность сети, время задержкипри передаче данных (latency time),переносимость, масштабируемость, затраты напроектирование, реализацию, отладку, требование к аппаратному обеспечению ит.д.

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

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

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

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

где Tstart— время запуска, а Tsend— время, необходимое для пересылки одного числа.

Подобным образомоценивается время перемножения и сложения n пар чисел. Будемсчитать, что n пар чисел перемножаются за время nTmul, а складываются завремя nTadd. При этом не будемразличать операции сложения и вычитания, и операции умножения и деления. Экспериментальнобыло установлено, что время Tmul на порядок превосходит время Tadd(конкретное значение зависит от типа процессора и отношение Tmul/Taddварьируется примерно от 10 до 100). Поэтому часто при оценкевремени выполнения алгоритма операции сложения не учитываются.

Ч А С Т Ь 1

СИСТЕМА

FLOWer

В данной частиописывается система программирования FLOWer — набор инструментов, взначительной степени облегчающих создание и отладку параллельных программ. Этасистема написана на языке Delphi и предназначенадля работы в локальных сетях ЭВМ под управлением ОС Windows.

Г Л А В А 1КРАТКИЙ ОБЗОР

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

·

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

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

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

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

·

DGL;

·

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

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

·

DGL

·

DGL

·

DLL

·

DGL
ГЛ А В А 2

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

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

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

·

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

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

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

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

2.1. ГПД

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

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

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

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

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

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

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

·

·

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).

·

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

2.2. Шаблон ГПД

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

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

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

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

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

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

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

·

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 = OutkTPi. Тогда

·

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).

·

InPij = In TPi, гдеj < | Pi |.

·

Out kTPi сопоставлено множество выходов Out k Pij, где j < | Pi |.

·

| Out kPij | = (OutkTPi).ncopies (j, A), гдеj < | Pi |.

·

(Out klPij).proc = (Out kTPi).proc, гдеl < | Out kPij |, j< | Pi |.

·

(Out klPij).copy = (Out kTPi).copy (l, j,A), гдеl < | Out kPij |, j < | Pi |.

·

(Out klPij).in = (Out kTPi).in, гдеl < | Out kPij |, j< | Pi |.

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

Г Л А В А 3

ЯЗЫК

DGL

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

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

1.

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]

3. Имеется N вершин V0, …, VN-1.Выход Outвершины k соединенсо входом In вершины W, k = 0, …,(N-1).

process W { import: In; }

process V[N] { export: Out

4. Имеется Nвершин V0,…, VN-1и N вершин W0, …, WN-1.Выход Out вершины Vk связан совходом Inвершины Wk, k = 0, …, (N-1).

process V[N] { export: Out

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]

6. Имеется Nвершин V0,…, VN-1.Выход Out вершины Vk связан совходом Inвершины V(k+1) modN, k = 0, …, (N-1).

process V[N] { export: Out

Значение N может быть объявлено каквнешний параметр. В этом случае Nопределяется во время запуска программы.

В дальнейшемпланируется ввести в язык многомерные массивы процессов, а так же добавитьусловные операторы if

…then…elseи case…of. Это позволит описывать более сложные ГПД, вчастности, многомерные решетки.

Синтаксис

DGL ::=

«DATAFLOW»«PROGRAM» name «;»

{«EXTERN» name [«=» integer] «;»}

{«CONST»name «=» expression «;»}