Управление потоками данных в параллельных алгоритмах вычислительной линейной алгебры - (диплом)
p>где aa1 - доля операций, выполняемых только одним процессором, aa2 - доля операций, выполняемых со средней степенью параллелизма k < p, aa3 - доля операций, производимых со степенью параллелизма p, td - общее время, требуемое для подготовки данных.Различают несколько специальных случаев этой формулы.
Случай 1. aa1 = 0, aa2 = 0, aa3 = 1, td = 0. Здесь ускорение максимально.
Случай 2. aa1 = 0, aa2 = 1, aa3 = 0, td = 0. Теперь Sp = k < p.
Случай 3. aa1 = aa, aa2 = 0, aa3 = 1 - aa, td = 0. В этом случае
Данная формула выражает закон Амдаля-Уэра. Следует отметить очень быстрое убывание Sp для малых значений aa.
Используя последнюю формулу, можно примерно оценить долю параллельных вычислений
Случай 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 = aaf(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
КРАТКИЙ ОБЗОР
Программный комплекс FLOWer спроектирован для работы в массивно-параллельной системе (MPP), которая состоит из однородных вычислительных узлов, включающих в себя:
один или несколько центральных процессоров;
локальную память (прямой доступ к памяти других узлов невозможен); коммуникационный процессор или сетевой адаптер.
Узлы связаны через некоторую коммуникационную среду (высокоскоростная сеть, коммутатор и т. п. ). На каждом зле работает полноценная ОС (в данном случае Windows).
В частности, такой системой является локальная сеть, в которой любые два компьютера могут обмениваться данными друг с другом. На любом компьютере могут одновременно работать несколько процессов.
Данная работа была выполнена в локальной сети с общей шиной. В такой сети все процессоры соединены посредством шины. Достоинством такой системы является очень малое число линий связи, однако возможны задержки (конфликт на шине) при использовании шины несколькими процессорами. Это может стать серьезной проблемой при увеличении числа процессоров.
В состав системы FLOWer входят:
программа визуального построения ГПД;
транслятор с языка DGL;
эмулятор сети для отладки программы.
Запуск параллельной программы осуществляется под управлением диспетчера, который распределяет процессы по компьютерам и устанавливает связи между процессами. Для нормальной работы диспетчера на всех компьютерах должна быть запущена специальная программа - монитор.
Создание параллельной программы в системе FLOWer состоит из следующих шагов:
конструирование графа потока данных программы
запись графа потока данных на языке графов данных DGL
обработка записи на языке DGL
написание прикладных программ для узловых процессов
компиляция узловых процессов в формат DLL
запуск узловых процессов диспетчером на основе DGL
Г Л А В А 2
МОДЕЛЬ ВЫЧИСЛЕНИЙ
Система FLOWer базируется на модели управления потоком данных. В данной модели вычислений программа представляется в виде ГПД. Вершины ГПД соответствуют отдельным процессам — последовательным участкам программы, а дуги задают отношения между ними. Точка вершины, в которую входит дуга, называется входным портом (портом импорта или входом), а точка, из которой она выходит, - выходным (портом экспорта или выходом). Некоторые входные порты могут быть помечены как обязательные. По дугам передаются данные из одного процесса в другой.
Основная идея модели управления потоком данных заключается в том, что процесс планируется для исполнения тогда и только тогда, когда во все его обязательные входные порты поступят данные. Т. е. процесс может быть запущен на выполнение, если выполняется одно из следующих условий:
процесс не имеет обязательных входов;
во все обязательные входы процесса поступили данные и процесс либо запускается в первый раз, либо завершено его предыдущее выполнение.
