Моделирование и анализ параллельных вычислений

Источник: http://at.tuit.uz/rus/o_kafedre/ МОДЕЛИРОВАНИЕ И АНАЛИЗ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ Модель вычислений в виде графа «операции – операнды» Для описания существующих информационных зависимостей в выбираемых алгоритмах решения задач может быть использована модель в виде графа «операции – операнды». Для уменьшения сложности излагаемого материала при построении модели будет предполагаться, что время выполнения любых вычислительных операций является одинаковым и равняется 1 (в тех или иных единицах измерения). Кроме того, принимается, что передача данных между вычислительными устройствами выполняется мгновенно без каких-либо затрат времени (что может быть справедливо, например, при наличии общей разделяемой памяти в параллельной вычислительной системе). Анализ коммуникационной трудоемкости параллельных алгоритмов приводится в следующей лекции. Представим множество операций, выполняемых в исследуемом алгоритме решения вычислительной задачи, и существующие между операциями информационные зависимости в виде ациклического ориентированного графа G = (V, R), Рис. 1. Пример вычислительной модели алгоритма в виде графа «операции – операнды» где V = {1,...,|V|} есть множество вершин графа, представляющих выполняемые операции алгоритма, а R есть множество дуг графа (при этом дуга r = (i, j) принадлежит графу только в том случае, если операция j использует результат выполнения операции i). Для примера на рис. 1 показан граф алгоритма вычисления площади прямоугольника, заданного координатами двух противолежащих углов. Как можно заметить по приведенному примеру, для выполнения выбранного алгоритма решения задачи могут быть использованы разные схемы вычислений и построены соответственно разные вычислительные модели. Как будет показано далее, разные схемы вычислений обладают Источник: http://at.tuit.uz/rus/o_kafedre/ различными возможностями для распараллеливания и, тем самым, при построении модели вычислений может быть поставлена задача выбора наиболее подходящей для параллельного исполнения вычислительной схемы алгоритма. В рассматриваемой вычислительной модели алгоритма вершины без входных дуг могут использоваться для задания операций ввода, а вершины без выходных дуг – для операций вывода. Обозначим через V множество вершин графа без вершин ввода, а через d(G) — диаметр (длину максимального пути) графа. Показатели эффективности параллельного алгоритма Ускорение (speedup), получаемое при использовании параллельного алгоритма для p процессоров, по сравнению с последовательным вариантом выполнения вычислений определяется величиной Sp(n)=T1(n)/Tp(n), т.е. как отношение времени решения задач на скалярной ЭВМ к времени выполнения параллельного алгоритма (величина n применяется для параметризации вычислительной сложности решаемой задачи и может пониматься, например, как количество входных данных задачи). Эффективность (efficiency) использования параллельным алгоритмом процессоров при решении задачи определяется соотношением Ep(n)=T1(n)/(pTp(n))=Sp(n)/p (величина эффективности определяет среднюю долю времени выполнения алгоритма, в течение которой процессоры реально задействованы для решения задачи). Из приведенных соотношений можно показать, что в наилучшем случае Sp(n)=p и Ep(n)=1. При практическом применении данных показателей для оценки эффективности параллельных вычислений следует учитывать два важных момента:  При определенных обстоятельствах ускорение может оказаться больше числа используемых процессоров Sp(n)>p - в этом случае говорят о существовании сверхлинейного (superlinear) ускорения. Несмотря на парадоксальность таких ситуаций (ускорение превышает число процессоров), на практике сверхлинейное ускорение может иметь место. Одной из причин такого явления может быть неодинаковость условий выполнения последовательной и параллельной программ. Например, при решении задачи на одном процессоре оказывается недостаточно оперативной памяти для хранения всех обрабатываемых данных и тогда становится необходимым использование более медленной внешней памяти (в случае же использования нескольких процессоров оперативной памяти может оказаться достаточно за счет разделения данных между процессорами). Еще одной причиной сверхлинейного ускорения может быть нелинейный характер зависимости сложности решения задачи от объема обрабатываемых данных. Так, например, известный алгоритм пузырьковой сортировки характеризуется квадратичной зависимостью количества необходимых операций от числа упорядочиваемых данных. Как результат, при распределении сортируемого массива между процессорами может быть получено ускорение, превышающее число процессоров. Источником сверхлинейного ускорения может быть и различие вычислительных схем последовательного и параллельного методов,  При внимательном рассмотрении можно обратить внимание, что попытки повышения качества параллельных вычислений по одному из показателей Источник: http://at.tuit.uz/rus/o_kafedre/ (ускорению или эффективности) могут привести к ухудшению ситуации по другому показателю, ибо показатели качества параллельных вычислений являются часто противоречивыми. Так, например, повышение ускорения обычно может быть обеспечено за счет увеличения числа процессоров, что приводит, как правило, к падению эффективности. И наоборот, повышение эффективности достигается во многих случаях при уменьшении числа процессоров (в предельном случае идеальная эффективность Ep(n)=1 легко обеспечивается при использовании одного процессора). Как результат, разработка методов параллельных вычислений часто предполагает выбор некоторого компромиссного варианта с учетом желаемых показателей ускорения и эффективности. При выборе надлежащего параллельного способа решения задачи может оказаться полезной оценка стоимости (cost) вычислений, определяемой как произведение времени параллельного решения задачи и числа используемых процессоров Cp=pTp. В связи с этим можно определить понятие стоимостно-оптимального (costoptimal) параллельного алгоритма как метода, стоимость которого является пропорциональной времени выполнения наилучшего последовательного алгоритма. Далее для иллюстрации введенных понятий в следующем пункте будет рассмотрен учебный пример решения задачи вычисления частных сумм для последовательности числовых значений. Кроме того, данные показатели будут использоваться для характеристики эффективности всех рассматриваемых параллельных алгоритмов при решении ряда типовых задач вычислительной математики. Учебный пример. Вычисление частных сумм последовательности числовых значений Рассмотрим для демонстрации ряда проблем, возникающих при разработке параллельных методов вычислений, сравнительно простую задачу нахождения частных сумм последовательности числовых значений где n есть количество суммируемых значений (данная задача известна также под названием prefix sum problem). Изучение возможных параллельных методов решения данной задачи начнем с еще более простого варианта ее постановки – с задачи вычисления общей суммы имеющегося набора значений (в таком виде задача суммирования является частным случаем общей задачи редукции) Последовательный алгоритм суммирования Традиционный алгоритм для решения этой задачи последовательном суммировании элементов числового набора S=0, S=S+x1,... состоит в Источник: http://at.tuit.uz/rus/o_kafedre/ Вычислительная схема данного алгоритма может быть представлена следующим образом (см. рис. 2): G1=(V1,R1), где V1={v01,...,v0n, v11,...,v1n} есть множество операций (вершины v01,...,v0n обозначают операции ввода, каждая вершина v1i, 1 i n, соответствует прибавлению значения xi к накапливаемой сумме S), а R1={(v0i,v1i),(v1i,v1i+1), 1 i n–1} есть множество дуг, определяющих информационные зависимости операций. Рис. 2. Последовательная вычислительная схема алгоритма суммирования Как можно заметить, данный "стандартный" алгоритм суммирования допускает только строго последовательное исполнение и не может быть распараллелен. Каскадная схема суммирования Параллелизм алгоритма суммирования становится возможным только при ином способе построения процесса вычислений, основанном на использовании ассоциативности операции сложения. Получаемый новый вариант суммирования (известный в литературе как каскадная схема) состоит в следующем (см. рис. 3):  на первой итерации каскадной схемы все исходные данные разбиваются на пары, и для каждой пары вычисляется сумма их значений;  далее все полученные суммы также разбиваются на пары, и снова выполняется суммирование значений пар и т.д. Данная вычислительная схема может быть определена как граф (пусть n=2k) G2(V2,R2), Рис. 3. Каскадная схема алгоритма суммирования Источник: http://at.tuit.uz/rus/o_kafedre/ где V2={(vi1,...,vli), 0 i k, 1 li 2-1n} есть вершины графа ((v01,...v0n) - операции ввода, (v1l,...,v1n/2) - операции суммирования первой итерации и т.д.), а множество дуг графа определяется соотношениями: R2={(vi-1,2j-1vij),(vi-1,2jvij), 1 i k, 1 j 2-in}. Как нетрудно оценить, количество итераций каскадной схемы оказывается равным величине k=log2n, а общее количество операций суммирования Kпосл=n/2+n/4+...+1=n–1 совпадает с количеством операций последовательного варианта алгоритма суммирования. При параллельном исполнении отдельных итераций каскадной схемы общее количество параллельных операций суммирования является равным Kпар=log2n. Поскольку считается, что время выполнения любых вычислительных операций является одинаковым и единичным, то T1=Kпосл, Tp=Kпар, поэтому показатели ускорения и эффективности каскадной схемы алгоритма суммирования можно оценить как Sp=T1/Tp=(n–1)/log2n, Ep=T1/pTp=(n–1)/(plog2n)=(n–1)/((n/2)log2n), где p=n/2 есть необходимое для выполнения каскадной схемы количество процессоров. Анализируя полученные характеристики, можно отметить, что время параллельного выполнения каскадной схемы совпадает с оценкой для паракомпьютера в теореме 2. Однако при этом эффективность использования процессоров уменьшается при увеличении количества суммируемых значений Модифицированная каскадная схема Получение асимптотически ненулевой эффективности может быть обеспечено, например, при использовании модифицированной каскадной схемы (см. [22]). Для упрощения построения оценок можно предположить n=2k, k=2s. Тогда в новом варианте каскадной схемы все вычисления производятся в два последовательно выполняемых этапа суммирования (см. рис. 4):  на первом этапе вычислений все суммируемые значения подразделяются на (n/log2n) групп, в каждой из которых содержится log2n элементов; далее для каждой группы вычисляется сумма значений при помощи последовательного алгоритма суммирования; вычисления в каждой группе могут выполняться независимо друг от друга (т.е. параллельно – для этого необходимо наличие не менее (n/log2n) процессоров);  на втором этапе для полученных (n/log2n) сумм отдельных групп применяется обычная каскадная схема. Источник: http://at.tuit.uz/rus/o_kafedre/ Рис. 4. Модифицированная каскадная схема суммирования Тогда для выполнения первого этапа требуется log2n параллельных операций при использовании p1=(n/log2n) процессоров. Для выполнения второго этапа необходимо log2(n/log2n) log2n параллельных операций для p2=(n/log2n)/2 процессоров. Как результат, данный способ суммирования характеризуется следующими показателями: Tp=2log2n, p=(n/log2n). С учетом полученных оценок показатели ускорения и эффективности модифицированной каскадной схемы определяются соотношениями: Sp=T1/Tp=(n–1)/2log2n, Ep=T1/pTp=(n–1)/(2(n/log2n)log2n)=(n–1)/2n. Сравнивая данные оценки с показателями обычной каскадной схемы, можно отметить, что ускорение для предложенного параллельного алгоритма уменьшилось в 2 раза, однако для эффективности нового метода суммирования можно получить асимптотически ненулевую оценку снизу Можно отметить также, что данные значения показателей достигаются при количестве процессоров, определенном в теореме 5. Кроме того, необходимо подчеркнуть, что, в отличие от обычной каскадной схемы, модифицированный каскадный алгоритм является стоимостно-оптимальным, поскольку стоимость вычислений в этом случае Cp=pTp=(n/log2n)(2log2n) является пропорциональной времени выполнения последовательного алгоритма. Вычисление всех частных сумм Вернемся к исходной задаче вычисления всех частных сумм последовательности значений и проведем анализ возможных способов последовательной и параллельной организации вычислений. Вычисление всех частных сумм на скалярном компьютере может быть получено при помощи обычного последовательного алгоритма суммирования при том же количестве операций (!) T1=n. При параллельном исполнении применение каскадной схемы в явном виде не приводит к желаемым результатам; достижение эффективного распараллеливания требует привлечения новых подходов (может быть, даже не имеющих аналогов при последовательном программировании) для разработки новых параллельно-ориентированных алгоритмов решения задач. Источник: http://at.tuit.uz/rus/o_kafedre/ Так, для рассматриваемой задачи нахождения всех частных сумм алгоритм, обеспечивающий получение результатов за log2n параллельных операций (как и в случае вычисления общей суммы), может состоять в следующем (см. рис. 5):  перед началом вычислений создается копия S вектора суммируемых значений (S=x);  далее на каждой итерации суммирования i, 1 i log2n, формируется вспомогательный вектор Q путем сдвига вправо вектора S на 2i-1 позиций (освобождающиеся при сдвиге позиции слева устанавливаются в нулевые значения); итерация алгоритма завершается параллельной операцией суммирования векторов S и Q. Рис. 5. Схема параллельного алгоритма вычисления всех частных сумм (величины Si-j означают суммы значений от i до j элементов числовой последовательности) Всего параллельный алгоритм выполняется за log2n параллельных операций сложения. На каждой итерации алгоритма параллельно выполняются n скалярных операций сложения и, таким образом, общее количество скалярных операций определяется величиной Kпар=nlog2n (параллельный алгоритм содержит большее (!) количество операций по сравнению с последовательным способом суммирования). Необходимое количество процессоров определяется количеством суммируемых значений (p=n). С учетом полученных соотношений показатели ускорения и эффективности параллельного алгоритма вычисления всех частных сумм оцениваются следующим образом: Sp=T1/Tp=n/log2n, Ep=T1/pTp=n/(plog2n)=n/(nlog2n)=1/log2n. Как следует из построенных оценок, эффективность алгоритма также уменьшается при увеличении числа суммируемых значений, и при необходимости повышения величины этого показателя может оказаться полезной модификация алгоритма, как и в случае с обычной каскадной схемой.