Дипломнаяработ а




НазваниеДипломнаяработ а
страница1/9
Дата публикации25.02.2013
Размер0.61 Mb.
ТипДиплом
litcey.ru > Информатика > Диплом
  1   2   3   4   5   6   7   8   9

Библиотека 5баллов.ru
Соглашение об использовании

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

Во всех остальных случаях полное или частичное воспроизведение, размножение или распространение материалов данного файла допускается только с письменного разрешения администрации проекта www.5ballov.ru.

РосБизнесКонсалтинг



Ульяновский Государственный Университет

Факультет механико-математический

Кафедра математической кибернетики и информатики

Работа допущена к защите

Зав. кафедрой Семушин И.В.

(Ф.И.О.)



(подпись)



(дата)

Д И П Л О М Н А Я Р А Б О Т А

Управление потоками данных в параллельных алгоритмах ____________

вычислительной линейной алгебры______________________ ___________

(название темы)

Прикладная математика. 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. Метод Якоби
Заключение

^

Список литературы



ВВЕДЕНИЕ



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


  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 входят:


  1. программа визуального построения ГПД;

  2. транслятор с языка DGL;

  3. эмулятор сети для отладки программы.


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



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


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



где T’1 - время выполнения алгоритма на одном процессоре, Тp - время выполнения алгоритма в системе из p процессоров.
Определение.Эффективностью параллельного алгоритма называется величина



Очевидно, что Sp Ј p, S’p Ј Sp, Ep Ј 1. Если алгоритм достигает максимального ускорения (Sp = p), то Ep = 1.
Одной из целей при конструировании параллельных алгоритмов является достижение по возможности большего ускорения. Но максимальное ускорение можно получить только для тривиальных задач. Главные факторы, влияющие на снижение ускорения таковы:


  1. отсутствие максимального параллелизма в алгоритме и/или несбалансированность нагрузки процессоров;




  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- n*n-матрица, то потребуется 2n2 - n операций. Предположим, что при исходном порядке n вычисления на единственном процессоре идут со скоростью 1 MFLOP. Затем мы удваиваем n, и число операций при большом n увеличивается примерно в 4 раза. Если задача решается на 4 процессорах со скоростью 4 MFLOP, то мы достигли максимального ускорения.
Вообще, пусть размер задачи определяется параметров n, а число операций есть f(n) при растущем n и p = af(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   2   3   4   5   6   7   8   9

Похожие:

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


При копировании материала укажите ссылку © 2013
контакты
litcey.ru
Главная страница