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

2.3. Определение времени выполнения параллельного алгоритма

Вычислительная схема алгоритма G совместно с расписанием Hp может рассматриваться как модель параллельного алгоритма Ap(G,Hp), исполняемого с использованием p процессоров. Время выполнения параллельного алгоритма определяется максимальным значением времени, применяемым в расписании$$T_p(G,H_p)=\max_{i \in V}(t_i + 1).$$

Для выбранной схемы вычислений желательно использование расписания, обеспечивающего минимальное время исполнения алгоритма$$T_p(G)=\min_{H_p} T_p(G,H_p).$$

Уменьшение времени выполнения может быть обеспечено и путем подбора наилучшей вычислительной схемы$$T_p = \min_{G} T_p(G).$$

Оценки Tp(G,Hp), Tp(G) и Tp могут быть применены в качестве показателей времени выполнения параллельного алгоритма. Кроме того, для анализа максимально возможного параллелизма можно определить оценку наиболее быстрого исполнения алгоритма$$T_{\infty} = \min_{p \ge 1} T_p.$$

Оценку $$T_{\infty }$$ можно рассматривать как минимально возможное время выполнения параллельного алгоритма при использовании неограниченного количества процессоров (концепция вычислительной системы с бесконечным количеством процессоров, обычно называемой паракомпьютером, широко применяется при теоретическом анализе параллельных вычислений).

Оценка T1 определяет время выполнения алгоритма при использовании одного процессора и представляет, тем самым, время выполнения последовательного варианта алгоритма решения задачи. Построение подобной оценки является важной задачей при анализе параллельных алгоритмов, поскольку она необходима для определения эффекта использования параллелизма (ускорения времени решения задачи). Очевидно, что$$T_1 (G) = |\overline{V}|,$$ где $$|\overline{V}|$$, напомним, есть количество вершин вычислительной схемы без вершин ввода. Важно отметить, что если при определении оценки ограничиться рассмотрением только одного выбранного алгоритма решения задачи и использовать величину$$T_1 = \min_{G} T_1 (G),$$ то получаемые при такой оценке показатели ускорения будут характеризовать эффективность распараллеливания выбранного алгоритма. Для оценки эффективности параллельного решения исследуемой вычислительной задачи время последовательного решения следует определять с учетом различных последовательных алгоритмов, т.е. использовать величину$$T_1^* = \min T_1,$$ где операция минимума берется по множеству всех возможных последовательных алгоритмов решения данной задачи.

Приведем без доказательства теоретические положения, характеризующие свойства оценок времени выполнения параллельного алгоритма (см. [22]).

Теорема 1. Минимально возможное время выполнения параллельного алгоритма определяется длиной максимального пути вычислительной схемы алгоритма, т.е.

Теорема 2. Пусть для некоторой вершины вывода в вычислительной схеме алгоритма существует путь из каждой вершины ввода. Кроме того, пусть входная степень вершин схемы (количество входящих дуг) не превышает 2. Тогда минимально возможное время выполнения параллельного алгоритма ограничено снизу значением

где n есть количество вершин ввода в схеме алгоритма.

Теорема 3. При уменьшении числа используемых процессоров время выполнения алгоритма увеличивается пропорционально величине уменьшения количества процессоров, т.е.

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

Теорема 5. Времени выполнения алгоритма, которое сопоставимо с минимально возможным временем $$T_{\infty }$$, можно достичь при количестве процессоров порядка $$p \sim T_{1}/T_{\infty }$$, а именно,

При меньшем количестве процессоров время выполнения алгоритма не может превышать более чем в 2 раза наилучшее время вычислений при имеющемся числе процессоров, т.е.$$p < T_1 / T_{\infty} \Rightarrow \frac{T_1}{p} \le T_p \le 2 \frac{T_1}{p}.$$

Приведенные утверждения позволяют дать следующие рекомендации по правилам формирования параллельных алгоритмов:

Для вывода рекомендаций по формированию расписания по параллельному выполнению алгоритма приведем доказательство теоремы 4.

Доказательство теоремы 4. Пусть $$H_{\infty }$$ есть расписание для достижения минимально возможного времени выполнения $$T_{\infty }$$. Для каждой итерации $$\tau ,\ 0<\tau <T_{\infty }$$, выполнения расписания $$H_{\infty }$$ обозначим через $$n_{\tau }$$ количество операций, выполняемых в ходе итерации $$\tau.$$ Расписание выполнения алгоритма с использованием p процессоров может быть построено следующим образом. Выполнение алгоритма разделим на $$T_{\infty }$$ шагов; на каждом шаге $$\tau$$ следует выполнить все $$n_{\tau }$$ операций, которые выполнялись на итерации $$\tau$$ расписания $$H_{\infty }$$. Эти операции могут быть выполнены не более чем за $$\lceil n_{\tau }/p\rceil$$ итераций при использовании p процессоров. Как результат, время выполнения алгоритма Tp может быть оценено следующим образом$$T_p = \sum_{\tau=1}^{T_{\infty}} \left{\lceil} \frac{n_{tau}}{p} \right{\rceil} < \sum_{\tau=1}^{T_{\infty}} \left( \frac{n_{tau}}{p} + 1 \right) = \frac{T_1}{p} + T_{\infty} .$$

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

2.4. Показатели эффективности параллельного алгоритма

Ускорение ( 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. При практическом применении данных показателей для оценки эффективности параллельных вычислений следует учитывать два важных момента:

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

Cp=pTp.

В связи с этим можно определить понятие стоимостно-оптимального (cost-optimal) параллельного алгоритма как метода, стоимость которого является пропорциональной времени выполнения наилучшего последовательного алгоритма.

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

2.5. Учебный пример. Вычисление частных сумм последовательности числовых значений

Рассмотрим для демонстрации ряда проблем, возникающих при разработке параллельных методов вычислений, сравнительно простую задачу нахождения частных сумм последовательности числовых значений$$S_k = \sum_{i=1}^k x_i, \quad 1 \le k \le n,$$ где n есть количество суммируемых значений (данная задача известна также под названием prefix sum problem ).

Изучение возможных параллельных методов решения данной задачи начнем с еще более простого варианта ее постановки – с задачи вычисления общей суммы имеющегося набора значений (в таком виде задача суммирования является частным случаем общей задачи редукции )$$S = \sum_{i=1}^n x_i.$$

2.5.1. Последовательный алгоритм суммирования

Традиционный алгоритм для решения этой задачи состоит в последовательном суммировании элементов числового набора

S=0,
S=S+x1,...

Вычислительная схема данного алгоритма может быть представлена следующим образом (см. рис. 2.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.5.2. Каскадная схема суммирования

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

Данная вычислительная схема может быть определена как граф (пусть n=2k )

G2(V2,R2),

где 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. Однако при этом эффективность использования процессоров уменьшается при увеличении количества суммируемых значений$$\lim E_p \rightarrow 0 \; \text{при } n \rightarrow \infty .$$

2.5.3. Модифицированная каскадная схема

Получение асимптотически ненулевой эффективности может быть обеспечено, например, при использовании модифицированной каскадной схемы (см. [22]). Для упрощения построения оценок можно предположить n=2k, k=2s. Тогда в новом варианте каскадной схемы все вычисления производятся в два последовательно выполняемых этапа суммирования (см. рис. 2.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 раза, однако для эффективности нового метода суммирования можно получить асимптотически ненулевую оценку снизу$$E_p = (n–1) / 2n \ge 0,25, \; \lim E_p \rightarrow 0,5 \; \text{при } n \rightarrow \infty .$$

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

Cp=pTp=(n/log2n)(2log2n)

является пропорциональной времени выполнения последовательного алгоритма.

2.5.4. Вычисление всех частных сумм

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

T1=n.

При параллельном исполнении применение каскадной схемы в явном виде не приводит к желаемым результатам; достижение эффективного распараллеливания требует привлечения новых подходов (может быть, даже не имеющих аналогов при последовательном программировании) для разработки новых параллельно-ориентированных алгоритмов решения задач. Так, для рассматриваемой задачи нахождения всех частных сумм алгоритм, обеспечивающий получение результатов за log2n параллельных операций (как и в случае вычисления общей суммы), может состоять в следующем (см. рис. 2.5, а также [22]):

(величины Si-j означают суммы значений от i до j элементов числовой последовательности)

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

Kпар=nlog2n

(параллельный алгоритм содержит большее (!) количество операций по сравнению с последовательным способом суммирования). Необходимое количество процессоров определяется количеством суммируемых значений ( p=n ).

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

Sp=T1/Tp=n/log2n,
Ep=T1/pTp=n/(plog2n)=n/(nlog2n)=1/log2n.

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

2.6. Оценка максимально достижимого параллелизма

Оценка качества параллельных вычислений предполагает знание наилучших (максимально достижимых) значений показателей ускорения и эффективности, однако получение идеальных величин Sp=p для ускорения и Ep=1 для эффективности может быть обеспечено не для всех вычислительно трудоемких задач. Так, для рассматриваемого учебного примера в предыдущем пункте минимально достижимое время параллельного вычисления суммы числовых значений составляет log2n. Определенное содействие в решении этой проблемы могут оказать теоретические утверждения, приведенные в начале данной лекции. В дополнение к ним рассмотрим еще ряд закономерностей, которые могут быть чрезвычайно полезны при построении оценок максимально достижимого параллелизмаКак и ранее, при выводе закономерностей не будут учитываться издержки, связанные с организацией передачи сообщений - анализу коммуникационной сложности параллельных алгоритмов посвящена лекция 3. .

1. Закон Амдаля. Достижению максимального ускорения может препятствовать существование в выполняемых вычислениях последовательных расчетов, которые не могут быть распараллелены. Пусть f есть доля последовательных вычислений в применяемом алгоритме обработки данных, тогда в соответствии с законом Амдаля ( Amdahl ) ускорение процесса вычислений при использовании p процессоров ограничивается величиной$$S_p \le \frac{1}{f + (1-f)/p} \le S^* = \frac{1}{f}.$$

Так, например, при наличии всего 10% последовательных команд в выполняемых вычислениях эффект использования параллелизма не может превышать 10-кратного ускорения обработки данных. В рассмотренном учебном примере вычисления суммы значений для каскадной схемы доля последовательных расчетов составляет f=log2n/n и, как результат, величина возможного ускорения ограничена оценкой S*=n/log2n.

Закон Амдаля характеризует одну из самых серьезных проблем в области параллельного программирования (алгоритмов без определенной доли последовательных команд практически не существует). Однако часто доля последовательных действий характеризует не возможность параллельного решения задач, а последовательные свойства применяемых алгоритмов. Поэтому доля последовательных вычислений может быть существенно снижена при выборе более подходящих для распараллеливания методов.

Следует отметить также, что рассмотрение закона Амдаля происходит в предположении, что доля последовательных расчетов f является постоянной величиной и не зависит от параметра n, определяющего вычислительную сложность решаемой задачи. Однако для большого ряда задач доля f=f(n) является убывающей функцией от n, и в этом случае ускорение для фиксированного числа процессоров может быть увеличено за счет увеличения вычислительной сложности решаемой задачи. Данное замечание может быть сформулировано как утверждение, что ускорение Sp=Sp(n) является возрастающей функцией от параметра n (данное утверждение часто именуется эффект Амдаля ). Так, например, для учебного примера вычисления суммы значений при использовании фиксированного числа процессоров p суммируемый набор данных может быть разделен на блоки размера n/p, для которых сначала параллельно могут быть вычислены частные суммы, а далее эти суммы можно сложить при помощи каскадной схемы. Длительность последовательной части выполняемых операций (минимально возможное время параллельного исполнения) в этом случае составляет

Tp=(n/p)+log2p,

что приводит к оценке доли последовательных расчетов как величины

f=(1/p)+log2p/n.

Как следует из полученного выражения, доля последовательных расчетов f убывает с ростом n и в предельном случае мы получаемом идеальную оценку максимально возможного ускорения S*=p.

2. Закон Густавсона – Барсиса. Оценим максимально достижимое ускорение исходя из имеющейся доли последовательных расчетов в выполняемых параллельных вычислениях:$$g= \frac{\tau(n)}{\tau(n) + \pi(n)/p},$$ где $$\tau (n)$$ и $$\pi (n)$$ есть времена последовательной и параллельной частей выполняемых вычислений соответственно, т.е.

С учетом введенной величины g можно получить

что позволяет построить оценку для ускорения$$S_p = \frac{T_1}{T_p} = \frac{\tau (n) + \pi (n)}{\tau (n) + \pi (n) / p} = \frac{(\tau (n) + \pi (n) / p)(g + (1-g)p)}{\tau (n) + \pi (n) / p} ,$$ которая после упрощения приводится к виду закона Густавсона – Барсиса ( Gustafson – Barsis's law ) (см. [63]):

Sp = g+(1–g)p = p+(1–p)g.

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

Tp = (n/p)+log2p,

что соответствует последовательной доле$$g = \frac{\log_2 p}{(n/p) + \log_2 p} .$$

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

При рассмотрении закона Густавсона – Барсиса следует учитывать еще один важный момент. С увеличением числа используемых процессоров темп уменьшения времени параллельного решения задач может падать (после превышения определенного порога). Однако за счет уменьшения времени вычислений сложность решаемых задач может быть увеличена (так, например, для учебной задачи суммирования может быть увеличен размер складываемого набора значений). Оценку получаемого при этом ускорения можно определить при помощи сформулированных закономерностей. Такая аналитическая оценка тем более полезна, поскольку решение таких более сложных вариантов задач на одном процессоре может оказаться достаточно трудоемким и даже невозможным, например, в силу нехватки оперативной памяти. С учетом указанных обстоятельств оценку ускорения, получаемую в соответствии с законом Густавсона – Барсиса, еще называют ускорением масштабирования ( scaled speedup ), поскольку данная характеристика может показать, насколько эффективно могут быть организованы параллельные вычисления при увеличении сложности решаемых задач.

2.7. Анализ масштабируемости параллельных вычислений

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

Оценим накладные расходы ( total overhead ), которые имеют место при выполнении параллельного алгоритма

T0=pTp–T1.

Накладные расходы появляются за счет необходимости организации взаимодействия процессоров, выполнения некоторых дополнительных действий, синхронизации параллельных вычислений и т.п. Используя введенное обозначение, можно получить новые выражения для времени параллельного решения задачи и соответствующего ускорения:$$T_p = \frac{T_1 + T_0}{p}, \quad S_p = \frac{T_1}{T_p} = \frac{pT_1}{T_1 + T_0} .$$

Применяя полученные соотношения, эффективность использования процессоров можно выразить как$$E_p = \frac{S_p}{p} = \frac{T_1}{T_1 + T_0} = \frac{1}{1+T_0 / T_1}.$$

Последнее выражение показывает, что если сложность решаемой задачи является фиксированной ( T1=const ), то при росте числа процессоров эффективность, как правило, будет убывать за счет роста накладных расходов T0. При фиксации числа процессоров эффективность их использования можно улучшить путем повышения сложности решаемой задачи T1 (предполагается, что при росте параметра сложности n накладные расходы T0 увеличиваются медленнее, чем объем вычислений T1 ). Как результат, при увеличении числа процессоров в большинстве случаев можно обеспечить определенный уровень эффективности при помощи соответствующего повышения сложности решаемых задач. Поэтому важной характеристикой параллельных вычислений становится соотношение необходимых темпов роста сложности расчетов и числа используемых процессоров.

Пусть E=const есть желаемый уровень эффективности выполняемых вычислений. Из выражения для эффективности можно получить$$\frac{T_0}{T_1} = \frac{1-E}{E} \; \text{или } T_1 = KT_0, K=E/(1-E).$$

Порождаемую последним соотношением зависимость n=F(p) между сложностью решаемой задачи и числом процессоров обычно называют функцией изоэффективности ( isoefficiency function ) (см. [51]).

Покажем в качестве иллюстрации вывод функции изоэффективности для учебного примера суммирования числовых значений. В этом случае$$T_0 = pT_p - T_1 = p((n/p) + \log_2 p) - n =p \log_2 p$$ и функция изоэффективности принимает вид$$n = Kp \log_2 p .$$

Как результат, например, при числе процессоров p=16 для обеспечения уровня эффективности E=0,5 (т.е. K=1 ) количество суммируемых значений должно быть не менее n=64. Или же, при увеличении числа процессоров с p до q (q>p) для обеспечения пропорционального роста ускорения (Sq/Sp)=(q/p) необходимо увеличить число суммируемых значений n в (qlog2q)/(plog2p) раз.

2.8. Краткий обзор лекции

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

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

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

Для оценки оптимальности разрабатываемых методов параллельных вычислений в лекции приводятся широко используемые в теории и практике параллельного программирования основные показатели качества - ускорение ( speedup ), показывающее, во сколько раз быстрее осуществляется решение задач при использовании нескольких процессоров, и эффективность ( efficiency ), которая характеризует долю времени реального использования процессоров вычислительной системы. Важной характеристикой разрабатываемых алгоритмов является стоимость ( cost ) вычислений, определяемая как произведение времени параллельного решения задачи и числа используемых процессоров.

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

В завершение лекции рассматривается вопрос построения оценок максимально достижимых значений показателей эффективности. Для получения таких оценок может быть использован закон Амдаля ( Amdahl ), позволяющий учесть существование последовательных (нераспараллеливаемых) вычислений в методах решения задач. Закон Густавсона – Барсиса ( Gustafson – Barsis's law ) обеспечивает построение оценок ускорения масштабирования ( scaled speedup ), применяемое для характеристики того, насколько эффективно могут быть организованы параллельные вычисления при увеличении сложности решаемых задач. Для определения зависимости между сложностью решаемой задачи и числом процессоров, при соблюдении которой обеспечивается необходимый уровень эффективности параллельных вычислений, вводится понятие функции изоэффективности ( isoefficiency function ).

2.9. Обзор литературы

Дополнительная информация по моделированию и анализу параллельных вычислений может быть получена, например, в [2, 22]), полезная информация содержится также в [51, 63].

Рассмотрение учебной задачи суммирования последовательности числовых значений было выполнено в [22].

Впервые закон Амдаля был изложен в работе [18]. Закон Густавсона – Барсиса был опубликован в работе [43]. Понятие функции изоэффективности было предложено в работе [39].

Систематическое изложение (на момент издания работы) вопросов моделирования и анализа параллельных вычислений приводится в [77].

2.10. Контрольные вопросы

2.11. Задачи и упражнения

1. Разработайте модель и выполните оценку показателей ускорения и эффективности параллельных вычислений:

2. Выполните в соответствии с законом Амдаля оценку максимально достижимого ускорения для задач п. 1.

3. Выполните оценку ускорения масштабирования для задач п.1.

4. Выполните построение функций изоэффективности для задач п.1.

5. Разработайте модель и выполните полный анализ эффективности параллельных вычислений ( ускорение, эффективность, максимально достижимое ускорение, ускорение масштабирования, функция изоэффективности ) для задачи умножения матрицы на вектор.