Управление потоками данных в параллельных алгоритмах вычислительной линейной алгебры - (диплом)
Управление потоками данных в параллельных алгоритмах вычислительной линейной алгебры - (диплом)
Дата добавления: март 2006г.
Ульяновский Государственный Университет
Факультет механико-математический
Кафедра математической кибернетики и информатики
Работа допущена к защите
Зав. кафедрой Семушин И. В.
(Ф. И. О. )
(подпись)
(дата)
Д И П Л О М Н А Я Р А Б О Т А
Управление потоками данных в параллельных алгоритмах ____________ вычислительной линейной алгебры______________________ ___________ (название темы)
Прикладная математика. 01. 02.
(наименование и номер специальности)
Проект выполнил студент ПМ-52 Андреев М. В.
группа подпись Ф. И. О.
Руководитель Дулов Е. В.
должность подпись Ф. И. О.
Рецензент
подпись Ф. И. О.
У Л Ь Я Н О В С К
2000
ОГЛАВЛЕНИЕ
Введение
ЧАСТЬ 1. Система FLOWer
Глава 1. Краткий обзор
Глава 2. Модель вычислений
2. 1. ГПД
2. 2. Шаблон ГПД
2. 3. Связь ГПД и шаблона ГПД
Глава 3. Язык DGL
Глава 4. Пример параллельной программы
ЧАСТЬ 2. Реализация некоторых алгоритмов ВЛА в
системе FLOWer
Глава 1. Умножение матриц
1. 1. Умножение матрицы на вектор
1. 2. Матричное умножение
1. 3. Возведение в степень блочно-диагональных
матриц
1. 4. Ленточные матрицы
Глава 2. Прямые методы решения линейных
систем
2. 1. LU-разложение
2. 2. Решение треугольных систем
2. 3. QR-разложение
Глава 4. Итерационные методы решения линейных
систем
4. 1. Метод Якоби
Заключение
Список литературы
ВВЕДЕНИЕ
Необходимость решения сложных фундаментльных и прикладных задач постоянно обуславливает исследования в области разработки и создания высокопроизводительных вычислительных средств. Производительности современных ЭВМ недостаточно для обеспечения требуемого решения многих задач. Один из наиболее эффективных способов повышения производительности заключается в распараллеливании вычислений в многопроцессорных и параллельных структурах.
В параллельном программировании, так же как и в последовательном, существует много различных средств для создания параллельного программного обеспечения. В данном разделе мы кратко опишем лишь несколько средств непосредственного программирования (кодирования) параллельных алгоритмов.
Все инструменты для разработки параллельных программ можно разделить на несколько типов:
Специализированные языки программирования, например Concurrent C++ (CC++) и Fortran M (FM). Эти языки предоставляют собой небольшой набор расширений языков C++ и Fortran и предоставляют программисту явное управление параллелизмом, коммуникациями и распределением заданий между процессорами. Языки CC++ и FM лучше всего подходят для реализации алгоритмов, в которых присутствуют динамическое создание заданий, нерегулярные схемы коммуникаций, а также для написания библиотек параллельного программирования. Недостатком программ, созданных с помощью данных языков программирования, является их недостаточная переносимость. Кроме того, компиляторы этих языков не всегда входят в стандартный комплект программного обеспечения, поставляемый с компьютером. Стандартные средства операционных систем. Средства межпроцессных коммуникаций (interprocess communication) такие как разделяемая память (shared memory), семафоры (semaphores), очереди сообщений (message queues), сигналы (signals) удобно использовать при программировании в модели разделяемой памяти. При использовнии низкоуровневых средств межроцессных коммуникаций программисту кроме кодирования непосредственно вычислительного алгоритма, требуется самому создавать процедуры синхронизации процессов, что может быть источником дополнительных трудностей. Специализированные средства операционных систем. Некоторые параллельные компьютеры, например, суперкомпьютеры с распределенной памятью фирмы Parsytec, поставляеются со специализированной операционной системой Parix, обеспечивающей реализацию параллельных алгоритмов на программном уровне. ОС Parix предоставляет разработчику библиотеку системных функций, обеспечивающих синхронную и асинхронную передачу данных, получение информации о конфигурации вычислительного узла, на котором запущена программа и т. д. Недостатком таких библиотек является их специализированность, т. е. узкая направленность на конкретную параллельную машину и, как следствие, плохую переносимость. Универсальные библиотеки параллельного программирования передачи сообщений (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.
Одной из целей при конструировании параллельных алгоритмов является достижение по возможности большего ускорения. Но максимальное ускорение можно получить только для тривиальных задач. Главные факторы, влияющие на снижение ускорения таковы:
отсутствие максимального параллелизма в алгоритме и/или несбалансированность нагрузки процессоров;
обмены, конфликты памяти и время синхронизации.
Определение. Временем подготовки данных называется задержка, вызванная обменами, конфликтами памяти или синхронизацией и необходимая для того, чтобы разместить данные в соответствующих ячейках памяти.
Большинство алгоритмов представляют собой смесь фрагментов с тремя различными степенями параллелизма, которые мы будем называть максимальным, частичным и минимальным параллелизмом. Но даже если алгоритм обладает максимальным параллелизмом, ситуация для данной параллельной системы может осложнятся проблемой балансировки нагрузки. Под балансировкой нагрузки понимается такое распределение заданий между процессорами системы, которое позволяет занять каждый процессор полезной работой по возможности большую часть времени. Балансировка нагрузки может осуществляться как статически, так и динамически.
Рассмотрим формальную модель системы, в которой
