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

Ульяновский Государственный Университет Факультет механико-математический Кафедра математической кибернетики и информатики Работа допущена к защите Зав. кафедрой Семушин И.В. Ф.И.О. подпись дата Д И П Л О М Н А Я Р А Б О Т А Управление потоками данных в параллельных алгоритмах вычислительной линейной алгебры название темы Прикладная математика. 01.02. наименование и номер специальности Проект выполнил студент ПМ-52 Андреев М.В. группа подпись Ф.И.О. Руководитель Дулов Е.В. должность подпись Ф.И.О. Рецензент подпись Ф.И.О. У Л Ь Я Н О В С К 2000 ОГЛАВЛЕНИЕ Введение ЧАСТЬ 1. Система FLOWer Глава 1. Краткий обзор Глава 2. Модель вычислений 2.1. ГПД 2.2. Шаблон ГПД 3. Связь ГПД и шаблона ГПД Глава 3. Язык DGL Глава 4. Пример параллельной программы ЧАСТЬ 2. Реализация некоторых алгоритмов ВЛА в системе FLOWer Глава 1. Умножение матриц 1. Умножение матрицы на вектор 2. Матричное умножение 3. Возведение в степень блочно-диагональных матриц 1.4. Ленточные матрицы Глава 2. Прямые методы решения линейных систем 2.1. LU-разложение 2. Решение треугольных систем 2.3. QR-разложение Глава 4. Итерационные методы решения линейных систем 1. Метод Якоби Заключение Список литературы ВВЕДЕНИЕ Необходимость решения сложных фундаментльных и прикладных задач постоянно обуславливает исследования в области разработки и создания высокопроизводительных вычислительных средств.

Производительности современных ЭВМ недостаточно для обеспечения требуемого решения многих задач.

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

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

Все инструменты для разработки параллельных программ можно разделить на несколько типов 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, PVM. Библиотеки функций позволяют писать быстрые и компактные программы, но они достаточно сложны в использовании и отладке так, библиотеку MPI называют ассемблером для параллельных систем.

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

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

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

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

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

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

В идеальном случае Определение. Ускорением параллельного алгоритма по сравнению с наилучшим последовательным алгоритмом называется отношение где T 1 - время выполнения алгоритма на одном процессоре, Тp - время выполнения алгоритма в системе из p процессоров. Определение. Эффективностью параллельного алгоритма называется величина Очевидно, что Sp p, S p Sp, Ep 1. Если алгоритм достигает максимального ускорения Sp p, то Ep 1. Одной из целей при конструировании параллельных алгоритмов является достижение по возможности большего ускорения.

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

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

Балансировка нагрузки может осуществляться как статически, так и динамически. Рассмотрим формальную модель системы, в которой где a1 - доля операций, выполняемых только одним процессором, a2 - доля операций, выполняемых со средней степенью параллелизма k p, a3 - доля операций, производимых со степенью параллелизма p, td - общее время, требуемое для подготовки данных. Различают несколько специальных случаев этой формулы.

Случай 1.a1 0, a2 0, a3 1, td 0. Здесь ускорение максимально. Случай 2.a1 0, a2 1, a3 0, td 0. Теперь Sp k p. Случай 3.a1 a, a2 0, a3 1 - a, td 0. В этом случае Данная формула выражает закон Амдаля-Уэра. Следует отметить очень быстрое убывание Sp для малых значений a. Используя последнюю формулу, можно примерно оценить долю параллельных вычислений Случай 4. td велико. Этот случай показывает, что при достаточно большом td можно получить Sp 1. Таким образом, возможно, что для задач с интенсивными обменами использование нескольких процессоров оказывается менее выгодным, чем использование одного.

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

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

Вообще, пусть размер задачи определяется параметров n, а число операций есть fn при растущем n и p afn. Если n1 - размер задачи, посильный для одного процессора, то соответствующий размер задачи np для системы из p процессоров определяется равенством fnp pfn1 чтобы число операций, выполняемых p процессорами, в p раз превосходило число операций одного процессора.

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

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

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

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

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

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

Для многих систем время такого обмена можно выразить приближенной формулой где Tstart время запуска, а Tsend время, необходимое для пересылки одного числа. Подобным образом оценивается время перемножения и сложения n пар чисел. Будем считать, что n пар чисел перемножаются за время nTmul, а складываются за время nTadd. При этом не будем различать операции сложения и вычитания, и операции умножения и деления.

Экспериментально было установлено, что время Tmul на порядок превосходит время Tadd конкретное значение зависит от типа процессора и отношение TmulTadd варьируется примерно от 10 до 100. Поэтому часто при оценке времени выполнения алгоритма операции сложения не учитываются. Ч А С Т Ь 1 СИСТЕМА FLOWer В данной части описывается система программирования FLOWer набор инструментов, в значительной степени облегчающих создание и отладку параллельных программ.

Эта система написана на языке Delphi и предназначена для работы в локальных сетях ЭВМ под управлением ОС Windows. Г Л А В А 1 КРАТКИЙ ОБЗОР Программный комплекс FLOWer спроектирован для работы в массивно-параллельной системе MPP, которая состоит из однородных вычислительных узлов, включающих в себя один или несколько центральных процессоров локальную память прямой доступ к памяти других узлов невозможен коммуникационный процессор или сетевой адаптер.

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

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

Для нормальной работы диспетчера на всех компьютерах должна быть запущена специальная программа - монитор. Создание параллельной программы в системе FLOWer состоит из следующих шагов конструирование графа потока данных программы запись графа потока данных на языке графов данных DGL обработка записи на языке DGL написание прикладных программ для узловых процессов компиляция узловых процессов в формат DLL запуск узловых процессов диспетчером на основе DGL Г Л А В А 2

Модель вычислений

Процесс структура данных, состоящая из набора входов и выходных портов... Параметры вектор переменных. process VN import In process W export Out N VcIn 3. process VN export Out WpIn process WN import In 5. Следует отметить, что это процессорная программа. Она не затрагивает м...

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

Тогда произведение можно записать двумя способами или, где аi i-я стро... Предположим, что p n и xi и ai приписаны процессору i. Все произведения xiai вычисляются с максимальным параллелизмом, а зате... Еще одно существенное соображение желаемое расположение результата по ... В реальных системах n и m значительно больше числа процессоров, и кажд...

Матричное умножение

Процесс вычисления состоит из трех этапов пересылка исходных данных на... В случае параллельного алгоритма пересылка исходных данных выполняется... При достаточно больших значениях n Т.е. В этом случае Spn сначала резко возрастает до некоторого экстремальног... Значение p в данном конкретном случае несложно вычислить. Оно находитс...

Возведение в степень блочно-диагональных матриц

Пусть матрица А имеет блочно-диагональный вид, т.е. где Аii квадратная матрица. Очевидно, что Аn можно вычислить следующим... Вычислим оптимальное число процессоров p и построим график Spn, m при ... Ленточные матрицы Матрица А порядка n называется ленточной, если aij 0... Причем А разбита на блоков Число ненулевых элементов матрицы B не прев...

Прямые методы решения линейных систем

Результаты эксперимента nt1n, секtpn, p2, секSpn1000450,975309,9481,45... В этом случае получим При достаточно больших значениях n Альтернативой... Рассылка строки выполняется за время n-kn-kTsend, нормировка за время ... В ситуации, когда p n, проблема балансировки нагрузки в определенной с... .

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

Постановка задачи После выполнения LU-разложения нужно решать треуголь... Найденный вектор y1 пересылается процессорам P2 Pp 3. На одном процессоре задача размерности n решается за время Оценим врем... Вычислить s1 в процессоре 1 и переслать его всем процессорам. И пусть система состоит из p процессоров, причем npm.

ЗАКЛЮЧЕНИЕ Результатом данной работы является программная среда FLOWer, предназначенная для конструирования параллельных программ.

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

Для испытания возможностей системы были реализованы некоторые параллельные алгоритмы ВЛА, даны теоретические оценки их эффективности и проведены вычислительные эксперименты, которые показали состоятельность и эффективность системы. Литература 1. Ортега Дж. Введение в параллельные и векторные методы решения линейных систем М. Мир, 1991. 2. Водяхо А.И Горнец Н.Н Пузанков Д.В. Высокопроизводительные системы обработки данных М. Высшая школа, 1997. 3. Бэбб Р. Программирование на параллельных вычислительных системах М. Мир, 1991. 4. Белецкий В.Н. Многопроцессорные и параллельные структуры с организацией асинхронных вычислений.

Киев Наукова думка, 1988. 5. httpparallel.ru. Информационно-аналитический центр по параллельным вычислениям.