Оптимальное управление вычислениями в распределенных вычислительных системах на основе графа потоков данных - (диплом)

Дата добавления: март 2006г.

    Ульяновский Государственный Университет
    Факультет механико-математический
    Кафедра математической кибернетики и информатики
    Работа допущена к защите
    Зав. кафедрой Семушин И. В.
    (Ф. И. О. )
    (подпись)
    (дата)
    Д И П Л О М Н А Я Р А Б О Т А

Оптимальное управление вычислениями в распределенных ____ ___вычислительных системах на основе графа потоков данных_____ (название темы)

    Прикладная математика. 01. 02.
    (наименование и номер специальности)
    Проект выполнил студент ПМ-52 Никифоров Ю. В.
    группа подпись Ф. И. О.
    Руководитель ассистент Дулов Е. В.
    должность подпись Ф. И. О.
    Рецензент Шиняев С. А.
    подпись Ф. И. О.
    У Л Ь Я Н О В С К
    2000
    Введение

Параллельный компьютер – это набор процессоров, которые могут работать совместно для решения вычислительных задач. Это определение достаточно общее, чтобы охватить и параллельные суперкомпьютеры с сотнями или тысячами процессоров, сети персональных ЭВМ, многопроцессорные рабочие станции, и другие параллельные системы. Параллельные компьютеры интересны тем, что они позволяют концентрировать большие вычислительные ресурсы для решения важных вычислительных задач. Параллелизм совсем недавно был экзотической областью компьютерной науки, интересной, но очень далёкой для рядового программиста. Сегодняшнее направление развития приложений, архитектуры компьютеров и сетей показывает, что теперь это не так. Паралеллизм становится вездесущим, и параллельное программирование становится центральным звеном при разработке программ. Традиционно, достижения в области высокопроизводительных вычислений мотивировалось задачами численного моделирования сложных систем, таких как погода, климат, маханические устройства, электронные схемы, производственные процессы и химические реакции. Однако, наиболее влиятельной движущей силой разработки более быстрых компьютеров на сегодняшний день является потребность в коммерческих приложениях, которые требуют от компьютера возможности обработки больших объёмов данных изощрёнными способами. В число таких приложений входят видео конференции, совместная среда разработки, компьютерное диагностирование в медицине, параллельные базы данных со средствами поддержки принятия решений, продвинутая графика и виртуальная реальность, особенно в индустрии развлечений. Но несмотря на то, коммерческие приложения может определять архитектуру большинства будущих параллельных компьютеров, традиционные научные приложения останутся важными потребителями технологии параллельных вычислений. Производительность наиболее быстрых компьютеров растёт экспоненциально с 1945 до наших дней, в среднем в 10 раз каждые пять лет. Нет сомнений, что этот рост будет продолжаться. Однако, для обеспечения этого роста архитектура компьютеров радикально меняется – от последовательной к параллельной. Важной тенденцией, меняющей лицо компьютеров, является огромное возрастание возможностей компьютерных сетей. Лишь недавно, высокоскоростные сети работали на скорости 10 Mbit в секунду; в конце 90-х пропускная способность в 100 и 1000 Mbit в секунду стала обычным делом. Значительно возрасла и их надёжность. Эти достижения позволяют разрабатывать приложения, использующие процессоры на множестве удалённых компьютеров. Эта область параллельных вычислений называется распределённые вычисления. Основной задачей разработки программ, которые могут работать на множестве компьютеров одновременно, всё таки является задача параллельных вычислений. В этом отношении, два разных слова, параллельный и распределённый, сходятся. Данный короткий обзор тенденций развития приложений, архитектуры и сетей наводит на мысль, что параллелизм охватывает не только суперкомпьютеры, но и рабочие станции, персональные компьютеры и сети. Поставщики традиционных коммерческих суперкомпьютеров (SMP, MPP, параллельных векторных) достаточно быстро улучшают производительность, надежность и простоту использования своих продуктов. Однако у этих компьютеров есть один большой недостаток - цена, подчас недоступная для многих образовательных и научно-исследовательских организаций. Однако потребность в вычислительных ресурсах у этих организаций велика. Следует иметь в виду, что производительность персональных компьютеров на базе процессоров Intel в последние годы также значительно выросла. Такие компьютеры стали создавать серьезную конкуренцию рабочим станциям на базе RISC, особенно по показателю цена/производительность. Одновременно стала приобретать все большую популярность многозадачнаые ОС Windows 95, NT. Возникла идея создавать параллельные вычислительные системы (кластеры) из общедоступных компьютеров на базе Intel и недорогих Ethernet-сетей. Оказалось, что на многих классах задач и при достаточном числе узлов такие системы дают производительность, сравнимую с суперкомпьютерной. Целью данной работы является создание системы поддержки выполнения параллельных алгоритмов для локальной сети персональных компьютеров. Реализация данной системы может применяться для решения специфических задач, характеризующихся высокой степенью регулярности. Класс таких задач довольно широк, он включает в себя такие задачи, как, например, обработка изображений, решение дифференциальных уравнений, моделирование длительных во времени процессов, в том числе и в реальном времени, многие другие научные и инженерные задачи, а также другие виды потоковой обработки данных. Модель параллельного компьютера состоит из некоторого числа вычислительных машин фон Ньюмана. Модель машины фон Ньюмана включает в себя центральный процессор (Central Processing Unit), соединённый с блоком памяти. Процессор выполняет программу, которая представляет собой последовательность операций чтения/записи над

памяти. Эта простая модель обосновалась довольно прочно в течение последних 45 лет. Все вычислительные машины соединены сетью.

Каждая машина выполняет свою собственную программу, которая может обращаться к локальной памяти, посылать и принимать данные по межмашинной сети. Понятие локальности – третье фундаментальное требование к параллельной программе, в дополнение к параллелизму и масштабируемости. Его важность зависит от отношения цены удалённого доступа к цене локального даступа к данным. Это отношение варьируется от 10: 1 до 1000: 1 в зависимости от относительной производительности локального компьютера, сети, и механизма, используемого для передачи и приёма данных через сеть. Эта идеализированная модель достаточно хорошо согласуется с реальной архитектурой параллельного компьютера, в качестве которой выбрана локальная сеть компьютеров. Локальная сеть характеризуется высокой ценой удалённого доступа. Ethernet и ATM являются наиболее распространёнными сетевыми технологиями на сегодняшний день. Для сети Fast Ethernet 100Mbits отношение времён удалённого и локального доступа в некоторых случаях приближается к 10: 1, что почти не сказывается на эффективности параллельных алгоритмов. Что касается ЭВМ с многозадачной операционной системой, то она также подходит под модель фон Ньюмана, т. к. центральный процессор просто работает в режиме разделения времени. В работе приводится соответствующая математическая интерпретация данного факта. Основу математической модели параллельного алгоритма составляет граф потоков данных (ГПД). В потоковой модели параллельная программа представляется набором вычислительных узлов-подзадач (далее задач), которые имеют фиксированное количество информационных входов и выходов. Узлы выполняют одни и те же операции с разной поступающей на входы информацией, и выдают результаты на свои выходы, также в виде числовой информации. Эти входы и выходы называются, соответственно, входными и выходными портами. Таким образом, вычислительные узлы строго периодичны. Узлы соединены между собой каналами передачи информации, выходные порты со входными. В реальной системе узлы представляются программами, а каналы – потоками байтов данных.

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

Параллельное вычисление состоит из одного или более одновременно исполняющихся задач (процессов), число которых постоянно в течение времени выполнения программы. Задача - это последовательная программа с локальными данными. Задача имеет входные и выходные порты, которые служат интерфейсом к среде процесса. В дополнение к обычным операциям задача может выполнять следующие действия: послать сообщение через выходной порт, получить сообщение из входного порта, создать новый процесс и завершить процесс. Посылающаяся операция асинхронная - она завершается сразу, не ожидая того, когда данные будут получены. Получающаяся операция синхронная: она блокирует процесс до момента поступления сообщения. Пары из входного и выходного портов соединяются очередями сообщений, называемыми каналами. Каналы можно создавать и удалять. Ссылки на каналы (порты) можно включать в сообщения, так что связность может измениться динамически. Процессы можно распределять по физическим процессорам произвольным способами, причем используемое отображение (распределение) не воздействует на семантику программы. В частности, множество процессов можно отобразить на одиночный процессор. Рассмотрим некоторые другие свойства модели задача/канал: производительность, независимость от распределения, модульность и детерминизм. Производительность. Абстракции последовательного программирования, такие как процедуры и структуры данных, эффективны потому, что они могут просто и рационально отображаться на вычислительную машину фон Ньюмана. Задача и канал производят тот же эффект по отношению к параллельному компьютеру. Задача представляет собой кусок кода, который может выполняться последовательно, на одном процессоре. Если две задачи, обменивающиеся данными, распределены на разные процессоры, то канал связи между ними воспроизводится как межпроцессорное взаимодействие; а если на один процессор, то может использоваться более быстрый механизм. Независимость от распределения. Так как задачи взаимодействуют используя один и тот же механизм (каналы) независимо от их расположения, результат выполнения программы не зависит от того, где задачи выполняются. Следовательно, процесс проектирования и реализации алгоритмов может не касаться количества процессоров, на которых алгоритм будет выполняться; фактически, большинство реализаций алгоритмов состоят из намного большего числа задач, чем процессоров. Это прямая предпосылка к масштабируемости. Модульность. В модульном программировании, различные компоненты программы разрабатываются поотдельности, как независимые модули, затем они собъединяются для получения полной программы. Взаимодействия между модулями ограничены хорошо продуманными интерфейсами. Т. о. модульность уменьшает сложность программ и облегчает повторное использование отлаженного кода. Задача является естественным строительным блоком. Задача инкапсулирует данные и код, который работает с этими данными; порты, через которые она посылает и принимает данные, составляют её интерфейс. Более того, в качестве модуля можно использовать более сложную структуру, реализующую какой-то алгоритм, и который имеет свой интерфейс. Определённое сходство существует и с объектно-ориентированной парадигмой программирования. Детерминизм. Алгоритм или программа детерминирована, когда выполнение с определёнными входными данными всегда приводит к одним и тем же результатам. Попарные взаимодейтсвия в модели задача/канал позволяет относительно легко гарантировать детерминизм. Каждый канал соединяет только одного отправителя и одного принимающего, и принимающая задача блокируется пока не закончится операция приёма. Эти условия ослабляются тем, что в один и тот же входной порт могут передаваться данный по разным каналам, т. е. от разных посылающих задач, но при этом формат данных должен быть один и тот же. Операция посылки данных в порт также может блокироваться, если принимающая задача, на другом конце канала, не успевает принимать и обрабатывать данные. Потоковая модель не единственный подход представления параллельных вычислений. Было предложено много других, отличающихся гибкостью, маханизмами взаимодействия задач, степенью разбиения на задачи (гранулярностью), масштабируемостью, модульностью. Примеры других моделей параллельного программирования: передача сообщений, параллелизм данных, разделяемая память. Передача сообщений. В иностранной литературе её называют Message Passing Interface (MPI). Возможно, сегодня это самая популярная модель параллельного программирования. Как и в модели задача/канал, MPI программы состоят из множества задач, каждая из которых инкапсулирует локальные данные. Каждая задача имеет своё уникальное имя, и модет посылать и принимать сообщения от другой задачи путём указания её имени. В этом отношении, MPI просто вариация модели задача/канал – вместо операции "послать в канал", используется операция "послать задаче X". MPI не препядствует динамическому созданию задач, выполнению нескольких задач на одном процессоре или выполнение разных программ одними и теми же задачами. Но на практике большинство MPI систем создают фиксированное количество задач при запуске программы, и не позволяют создание и уничтожение задач во время выполнения программы. Эти системы реализуют модель типа "одна программа много данных" (Single Program Multiple Data), так как каждая задача выполняет одни и те же действия над разными поступающими данными. Это сильно перекликается с потоковой моделью параллельного программирования. Паралеллизм данных. Паралеллизм в данной модели используется тогда, когда одна операция применяется к нескольким элементам структуры данных, например, "добавить число ко всем элементам массива". Т. о. программа состоит из последовательности подобных операторов. Так как каждый элемент данных можно интерпретировать как независимую задачу, присущая гранулярность вычислений мала, и понятие "локальности" не очевидно. Следовательно, специализированные компиляторы часто требуют от программиста информацию о том, как данные распределяются между процессорами, другими словами, как данные должны разбиваться на задачи. Далее компилятор транслирует программу в SPMD формулировку, генерируя коммуникационный код автоматически. Разделяемая память. В модели разделяемой памяти задачи используют общее адресное пространство для асинхронного чтения и записи. Различные механизмы, такие как замки и семафоры, могут регулировать доступ к разделяемой памяти. Преимуществом данной модели для программиста яаляется то, что не нужно явно указывать источник и приёмник данных, эта модель может сильно упростить программирование. Однако, затрудняется понимание и управление обменом данных, а также затрудняется написание детерминированииых программ. Далее приводится несколько типичных примеров параллельных алгоритмов. Все они описываются в терминах модели потоков данных.

    Конечные разности.

Рассматривается одномерная конечноразностная задача, в которой имеем вектор X(0) размерности N и должны вычислить вектор X(T), где Т. о. мы должны периодически обновлять каждый элемент X, так чтобы на t+1 шаге обновление происходило только после того, как над соседними элементами выполнится шаг t. ГПД данного алгоритма состоит из N задач, по одной на каждый элемент X. i -тая задача получает значение Xi(0) и вычисляет, за T шагов, значения Xi(1) , Xi(2), … Xi(T). Значит, на шаге t, она должна получить значения Xi-1(t) и Xi+1(t) от задач i-1 и i+1. Каждая задача i, за исключением 0-й и N-1-й, имеет по паре разнонаправленных левых (left) и правых (right) портов, как показано на рисунке, и на каждой итерации t выполняет следующие действия: посылает данные Xi(t) в свои левый и правые выходные порты; принимает от своих Xi-1(t) и Xi+1(t) левого и правого соседа; использует полученные значения для вычисления Xi(t+1).

Заметим, что N задач могут выполняться независимо, с одним лишь ограничением на порядок выполнения, определяемом синхронизацией посредством операций приёма. Следовательно, выполнение детерминировано.

    Попарные взаимодействия.

В данном примере используется похожая структура ГПД как в примере с конечными разностями, но требуется более сложный алгоритм обмена данных. Многие задачи требуют вычисление всех N(N-1) попарных взаимодействий I (Xi, Xj) между N векторами Xo, X1, …XN-1. В случае, когда взаимодействия симметричны, I (Xi, Xj) = ± I (Xi, Xj), и требуется вычислить только N(N-1) / 2 взаимодействий. Например, в молекулярной динамике требуется вычислить суммарный вектор сил воздействующих на атом Xi, определённый как:

F(Xi, Xj) означает взаимное притяжение или отталкивание между атомами Xi и Xj; в данном случае, F (Xi, Xj) = - F (Xi, Xj), взаимодействия симметричны. Простой параллельный алгоритм для общей задачи попарных взаимодействий состоит из N задач. Задача i получает значение Xi и вычисляет набор i № j . Сначала можно подумать, так как задача требует информацию от каждой другой задачи, для этого должно быть создано N(N-1) каналов. Однако, более экономичная структура ГПД использует только N каналов. Они соединяют все задачи в однонаправленное кольцо, так что каждая задача имеет по одному входному и выходному порту. Каждая задача сначала инициализирует буфер (для хранения локальной переменной) и аккуммулятор, в котором будет содержаться результат вычислений. Затем задача периодически: посылает значение из буфера в свой выходной порт;

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

Этот цикл посылки-приёма-вычисления повторяется N-1 раз, осуществляя перемещение по кольцу всех N значений Xi. Каждая задача видит их всех и способна вычислить все N-1 взаимодействия. Алгоритм выполняет N-1 операцию на каждую задачу. Если взаимодействия симметричны, то можно уменьшить в два раза количество вычислений и обменов данных путём улучшения структуры ГПД. Предположим для простоты, что N четно. Добавляется дополнительные N каналов, соединяющих каждую задачу с задачей, расположенной через [N / 2] по кольцу. Каждый раз, когда вычисляется I (Xi, Xj) между локальным Xi и принятым Xj, вычисленное значение не только суммируется в аккумуляторе для Xi, но и в другом аккумуляторе, который является противоположным с Xj. После [N / 2] итераций аккумуляторы, ассоциированные со своими противоположными значениями, возвратятся в свои начальные задачи через новые каналы и обхединятся с локальными аккумуляторами. Следовательно, каждое симметричное взаимодействие вычислится только раз: либо как I (Xi, Xj) на вершине содержащей Xi, либо I (Xj, Xi) на вершине содержащей Xj.

    Параметрическое исследование

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

Страницы: 1, 2