рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

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

Работа сделанна в 2000 году

Модель вычислений - раздел Математика, - 2000 год - Управление потоками данных в параллельных алгоритмах вычислительной линейной алгебры Модель Вычислений. Система Flower Базируется На Модели Управления Потоком Дан...

Модель вычислений. Система FLOWer базируется на модели управления потоком данных.

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

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

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

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

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

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

Вход может быть помечен как обязательный. Каждому процессу приписывается вес величина, характеризующая примерный объем вычислений, выполняемых этим процессом. Выходной порт массив выходов. Выход тройка чисел номер класса процесса, номер экземпляра процесса, номер входа, однозначно определяющая вход, к которому подключен данный выход. Введем систему обозначений. ГПД обозначим через G P, C, где P множество процессов, C множество каналов. 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. Пусть X Out kl Pij, тогда выход X соединен с входом h X.in процесса с номером s, w, где s X.proc, w X.copy. Т.е. существует канал c X, Y, где Y In h Psw. 2.2. Шаблон ГПД Шаблоны ГПД имеют сходные черты с шаблонами в языке С. Каждый шаблон ГПД обладает набором параметров, после определения которых из шаблона получается конкретный экземпляр ГПД. От параметров может зависеть число процессов ГПД, число выходов процесса.

Параметры шаблона вводятся на этапе запуска программы.

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

Каждому классу процесса сопоставлен номер. Параметры вектор переменных. Канал определяет однонаправленный поток данных между процессами, он всегда направлен от входа к выходу. Класс процесса структура данных, состоящая из набора входов и выходов. Входы и выходы занумерованы. Вход может быть помечен как обязательный. Введем систему обозначений. TG TP, TC, A шаблон ГПД, где TP множество шаблонов процесса, TC множество шаблонов канала, A вектор параметров.

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 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 k TPi сопоставлено множество выходов Out k Pij, где j Pi. Out k Pij Out k TPi.ncopies j, A, где j Pi. Out kl Pij.proc Out k TPi.proc, где l Out k Pij, j Pi. Out kl Pij.copy Out k TPi.copy l, j, A, где l Out k Pij, j Pi. Out kl Pij.in Out k TPi.in, где l Out k Pij, j Pi. ЗАМЕЧАНИЕ при некоторых значениях вектора параметров операция подстановки может быть не определена.

Г Л А В А 3 ЯЗЫК DGL Язык DGL был специально разработан для описания ГПД. Для ввода програмы на языке DGL можно использовать как простой текстовый редактор, так и специальную программу Rose, которая рисует ГПД на экране компьютера. Рассмотрим как зписываются графы на языке DGL на основе элементарных примеров. 1. Выход Out вершины V1 связан со входом In вершины V2. process V1 export Out V2In process V2 import In 2. Имеется N вершин V0 VN-1. Вершина W содержит N выходов Out0 OutN-1. Выход Outk соединен со входом In вершины Vk, k 0, ,N-1. process VN import In process W export Out N VcIn 3. Имеется N вершин V0 VN-1. Выход Out вершины k соединен со входом In вершины W, k 0, ,N-1. process W import In process VN export Out WIn 4. Имеется N вершин V0 VN-1 и N вершин W0 WN-1. Выход Out вершины Vk связан со входом In вершины Wk, k 0 N-1. process VN export Out WpIn process WN import In 5. Имеется N вершин V0 VN-1 и M вершин W0 WM-1. Каждая вершина типа V содержит M выходов Out0 OutM-1, причем выход Outk связан со входом In вершины Wk, k 0 M-1. process WM import In process VN export Out M WcIn 6. Имеется N вершин V0 VN-1. Выход Out вершины Vk связан со входом In вершины Vk1 mod N, k 0 N-1. process VN export Out Vp1 mod NIn import In Значение N может быть объявлено как внешний параметр.

В этом случае N определяется во время запуска программы.

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

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

Синтаксис DGL DATAFLOW PROGRAM name EXTERN name integer CONST name expression process process PROCESS name numberofinstances directive processattr EXPORT export IMPORT import directive LOCAL START TERMINATION processattr weight integer import name importattr importattr export name numberofinstances processname processindex importname exportattr exportattr numberofinstances expression processindex expression importattr ARGUMENT exportattr DATASIZE integer Г Л А В А 4 ПРИМЕР ПАРАЛЛЕЛЬНОЙ ПРОГРАММЫ В качестве примера рассмотрим задачу приближенного вычисления числа Пи с использованием правила прямоугольников для вычисления определенного интеграла где Согласно правилу прямоугольников, где, а. Следует отметить, что это процессорная программа.

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

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

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

Каждой вершине ГПД соответствует процесс DGL с тем же именем. Теперь нарисуем ГПД с помощью программы Rose и запишем его на диск в формате DGL. DATAFLOW PROGRAM PI EXTERN NProcs 5 CONST nw MAX 1, NProcs - 2 PROCESS Summer 1 LOCAL IMPORT NumIter PartSum PROCESS Worker nw EXPORT PartSum 1 Summator 0 PartSum DATASIZE 0 Demand 1 Manager 0 DemandList DATASIZE 0 IMPORT Arg PROCESS Manager 1 LOCAL START TERMINATION EXPORT Done 1 Summator 0 DoneSignal DATASIZE 0 Worker nw Worker c Arg DATASIZE 0 IMPORT DemandList 4.3. Компиляция процессов После того, как ГПД записан на языке DGL, его нужно обработать транслятором dglc. В результате работы транслятора на диске должны появиться следующие файлы PI.dpr, Manager.pas, ManagerBody.pas, Worker.pas, WorkerBody.pas, Summator.pas, SummatorBody.pas. Далее, программист записывает код каждого процесса в файлах SummatorBody.pas, WorkerBody.pas, ManagerBody.pas, а затем компилирует проектный файл PI.dpr. Ч А С Т Ь 2 РЕАЛИЗАЦИЯ НЕКОТОРЫХ АЛГОРИТМОВ ВЛА В СИСТЕМЕ FLOWer В данной части рассматривается реализация в системе программирования FLOWer некоторых алгоритмов ВЛА, в число которых входят умножение матриц, LU-разложение, решение треугольных СЛУ, QR-разложение, итерационные методы решения СЛУ. Для каждого алгоритма приводятся теоретические оценки ускорения, описание параллельного алгоритма, экспериментальные данные.

Для проведения экспериментов использовалась локальная сеть FastEthernet, состоящая из 4-х компьютеров Pentium II 333MHz. Г Л А В А 1 УМНОЖЕНИЕ МАТРИЦ Рассмотрим задачу вычисления произведений Ax и AB, где А и В матрицы, а х вектор.

Отдельно будут рассмотрены ленточные и блочно-диагональные матрицы. 1.1.

– Конец работы –

Эта тема принадлежит разделу:

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

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

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Модель вычислений

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Умножение матрицы на вектор
Умножение матрицы на вектор. Пусть А матрица mn, а х вектор длины n. Тогда произведение можно записать двумя способами или, где аi i-я строка матрицы А, аi i-й столбец матрицы А, а x, y скалярное п

Матричное умножение
Матричное умножение. Аналогично рассматриваются алгоритмы умножения матриц А и В. Пусть матрицы разбиты на блоки Пусть число процессоров р равно числу st блоков матрицы С. Тогда все блоки можно выч

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

Прямые методы решения линейных систем
Прямые методы решения линейных систем. Рассмотрим систему линейных уравнений Ax b с невырожденной матрицей А размера nn . 2.1. LU-разложение Постановка задачи Построим разложение мтрицы A LU, где L

Решение треугольных систем
Решение треугольных систем. Постановка задачи После выполнения LU-разложения нужно решать треугольные системы. Ly b, Ux y Процесс их решения назывантся прямой и обратной подстановками. Рассм

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги