Бурова И.Г., Демьянович Ю.К. Алгоритмы параллельных вычислений и программирование

Подождите немного. Документ загружается.

все перечисленные неравенства, приходим к заключению, сформу-

лированному в доказываемой теореме.

Теорема 7.2. Пусть выбрана такая ось l, что проекции на нее

всех дуг графа положительны. Тогда эта ось определяет некото-

рую параллельную форму алгоритма: ярусами этой параллельной

формы являются множества вершин, лежащих в перпендикуляр-

ных к l гиперплоскостях, причем ярусы упорядочены в соответ-

ствии с порядком проекции вершин на ось l.

Д о к а з а т е л ь с т в о. Докажем сначала, что множества вер-

шин в гиперплоскостях — ярусы, т.е. что они не соединены дугами:

но это действительно так, ибо в противном случае проекции этих

дуг на ось не были бы положительными (они равнялись бы нулю),

что противоречит условию теоремы.

С другой стороны, если гиперплоскости перенумерованы в со-

ответствии с порядком проекций на оси l, то ввиду однонаправлен-

ности проекций дуг ясно, что если 1, 2, . . . , k — нумерация точек

пересечения гиперплоскости с осью l в соответствии с упомянутым

направлением, а V

— множества вершин в i-й гиперплоскости, то

для вершин u ∈ V

, v ∈ V

, соединенных дугой (u, v), следует, что

i < j. Теорема доказана.

Следствие 7.1. В условиях теоремы 7.2 высота алгоритма

равна числу проекций на прямой l, а ширина алгоритма — макси-

мальному числу вершин, проектирующихся в одну точку прямой

Определение 7.1. Ось l, удовлетворяющая теореме 7.1, на-

зывается направляющим вектором графа, а сам граф называется

направленным.

Если существует ось l, удовлетворяющая условиям теоремы

7.2, то граф называется строго направленным.

Теорема 7.3. Если все дуги графа имеют положительные

координаты (разность между координатами конца и начала по-

ложительна), то этот граф является строго направленным и в

качестве направляющего вектора можно взять любой вектор с

положительными компонентами.

Д о к а з а т е л ь с т в о становится очевидным, если вспомнить

определение строгой направленности.

Рис. 10. Решетчатый граф.

Следствие 7.2. Если одноименные координаты (т.е. ко-

ординаты с одним номером) дуг либо отрицательные, либо поло-

жительные, то граф является строго направленным, а в каче-

стве направления можно взять вектор с ненулевыми координа-

тами, знаки которых совпадают со знаками соответствующих

одноименных координат дуг.

Теорема 7.4. Пусть все вершины графа алгоритма нахо-

дятся в узлах прямоугольной целочисленной решетки и принад-

лежат замкнутому прямоугольному параллелепипеду с ребрами

длиной d

, d

, . . . , d

. Пусть дуги графа имеют неотрицательные

координаты. Тогда высота h алгоритма удовлетворяет неравен-

ству

h ≤

i=1

+ 1. (7.2)

Д о к а з а т е л ь с т в о. Очевидно, рассматриваемый граф явля-

ется строго направленным, и в качестве оси можно взять вектор

с единичными компонентами. Согласно следствию 7.1 высота ал-

горитма равна числу проекций на ось, а их число не превосходит

правой части неравенства (7.2). Теорема доказана.

Определение 7.2. Граф, вершины которого лежат в узлах

целочисленной решетки, называется решетчатым.

Пример. Рассмотрим задачу вычисления произведения A =

BC двух квадратных матриц B = (b

), C = (c

), i, j, k =

1, . . . , n. Пусть A = (a

) i, j, k = 1, . . . , n. Определим алгоритм

формулами a

(k)

= a

(k−1)

+ b

, где a

(0)

= 0. Операцию a + bc

будем считать базовой.

Тогда соответствующий решетчатый граф имеет вид, изобра-

женный на рис. 10.

Глава 4. ФУНКЦИОНАЛЬНЫЕ УСТРОЙСТВА

§ 1. Некоторые определения

Предположим, что вычислительная система состоит из функ-

циональных устройств и работает по тактам, т. е. каждая операция

начинается или заканчивается только в фиксированные равноот-

стоящие моменты времени. Для простоты полагаем, что все рас-

сматриваемые функциональные устройства синхронизированы, т.е.

могут включаться лишь в упомянутые моменты времени.

Временн´ой интервал между соседними моментами времени

будем считать единичным и называть его тактом.

Определение 1.1. Функциональное устройство называется

простым, если время выполнения операции на нем (число тактов)

определено априори и никакая следующая операция не может на-

чаться раньше окончания предыдущей.

Простое функциональное устройство будем обозначать F

Определение 1.2. Функциональное устройство называется

конвейерным, если время выполнения на нем любой операции зара-

нее определено, но следующая операция может начать выполне-

ние через один такт после начала выполнения предыдущей.

Предполагается, что выполнение любой операции происходит

за целое число тактов.

Замечание. Основное отличие между простым и конвейерным

функциональным устройством состоит в том, что простое функци-

ональное устройство использует все свое оборудование для выпол-

нения одной операции, а конвейерное — распределяет свое обору-

дование между несколькими операциями, к выполнению каждой

из которых оно приступает последовательно, обычно не закончив

выполнение предыдущих. В некоторых случаях конвейерное функ-

циональное устройство можно рассматривать как особое устрой-

ство распараллеливания, точнее — "диагонального" распаралле-

ливания.

Конвейерное устройство можно также рассматривать как сово-

купность s простых устройств. Число последних называется числом

ступеней или длиной конвейера.

Очевидно, что длина конвейерного устройства совпадает с чис-

лом тактов обработки самой длинной операции. Конвейерное функ-

циональное устройство длины s будем обозначать F

Будем предполагать, что

1) функциональное устройство не имеет собственной памяти (в

случае необходимости присоединяется внешняя память);

2) функциональное устройство работает по индивидуальным

командам;

3) в момент подачи команды сначала уничтожаются результа-

ты предыдущего срабатывания данного функционального устрой-

ства (если они не нужны), и затем передаются результаты срабаты-

вания соседних функциональных устройств, необходимые для вы-

полнения команды;

4) если функциональное устройство может реализовывать опе-

рации разных типов, то будем считать, что функциональное устрой-

ство может выдавать их результаты даже в том случае, когда неко-

торые (или все) операции завершились в один и тот же момент вре-

мени.

Замечание. Время выполнения одной операции на конвейер-

ном функциональном устройстве совпадает с числом ступеней кон-

вейера; часто конвейерное функциональное устройство реализует-

ся, как цепочка простых функциональных устройств со временем

срабатывания 1 такт (например, при выполнении операций с пла-

вающей точкой простые функциональные устройства выполняют

сравнение порядков, сдвиг мантиссы, сложение мантисс и т.п.).

Определение 1.3. Стоимостью операции называется вре-

мя ее реализации, а стоимостью работы — сумма стоимостей

всех выполненных операций (т.е. время их выполнения на одно-

процессорной системе).

Будем обозначать R

— стоимость работ, проведенных на на-

шей вычислительной системе за время T , а P

— максимально воз-

можная стоимость работ за время T .

Определение 1.4. Загруженностью Z

устройства или

системы на данном отрезке времени T называется отношение

стоимости реально выполненных операций к стоимости опера-

ций, которые можно выполнить при максимальном использова-

Здесь и далее под T подразумевается промежуток времени [t

, t

+ T ]. В

результате достигается краткость в ущерб строгости (ибо рассматриваемые да-

лее величины чаще всего зависят не только от T , но и от t

). Заинтересованный

читатель при желании легко это исправит.

нии ресурсов за то же время:

Асимптотической загруженностью Z

∞

при выполнении дан-

ного класса работ называется предел загруженности Z

при неогра-

ниченном увеличении рассматриваемого отрезка времени T .

∞

= lim

T →+∞

Замечание. Очевидно, что 0 ≤ Z

≤ 1, 0 ≤ Z

∞

≤ 1.

§ 2. Свойства простых и конвейерных

функциональных устройств

Рассмотрим некоторые свойства функциональных устройств.

Теорема 2.1. Если функциональное устройство простое, то

максимальная стоимость работ, выполняемая им на отрезке вре-

мени длины T , равна T , а максимальная стоимость работ на том

же отрезке времени для конвейерного функционального устрой-

ства длины s равна T · s.

Д о к а з а т е л ь с т в о очевидно.

Обозначим P

) — максимальную стоимость работ на про-

стом функциональном устройстве, а P

) — максимальную стои-

мость работ на конвейерном функциональном устройстве с s ступе-

нями. Из теоремы 2.1 следуют формулы P

) = T , P

) = s·T .

Замечание. Максимальная стоимость работ не зависит от ти-

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

Будем говорить, что устройство F работает стабильно на рас-

сматриваемой задаче, если его производительность на этой задаче

пропорциональна времени T , а именно R

(F ) = T R

(F ).

Говорят, что устройство при максимальной загрузке работает

стабильно, если P

(F ) = T P

(F ).

Определение 2.1. Максимальная стоимость работ, выпол-

няемая устройством за единицу времени в среднем на промежут-

ке времени [t, t + T] называется пиковой производительностью на

этом промежутке. Обозначим ее Π

[t,t+T ]

Ясно, что Π

[t,t+T ]

= P

(F )/T .

Замечание. Если устройство при максимальной загрузке рабо-

тает стабильно, то пиковая производительность от t и T не зависит.

Обозначая ее через Π(F ), имеем

Π(F ) = P

(F )/T = P

(F ).

Нетрудно видеть, что

— для простого функционального устройства Π(F

) = 1,

— для s-ступенчатого конвейера Π(F

) = s.

Определение 2.2. Реальной производительностью системы

называется стоимость работ, фактически выполненных систе-

мой за единицу времени.

Замечание. Если система F работает стабильно, то реальная

производительность ее равна R

(F ), а ее загруженность Z

от T не

зависит. Действительно

T R

T P

. (2.1)

В дальнейшем будем считать, что рассматриваемые функцио-

нальные устройства работают стабильно.

Теорема 2.2. Если система состоит из k устройств с пико-

выми производительностями p

1(1)

, p

1(2)

, . . . , p

1(k)

и с загружен-

ностями z

(1)

, z

(2)

, . . . , z

(k)

, то реальная производительность си-

стемы равна

i=1

(i)

1(i)

. (2.2)

Д о к а з а т е л ь с т в о. Поскольку реальная стоимость работ,

проводимых системой за время T складывается из стоимостей ра-

бот R

1(i)

, проводимых ее устройствами за это время, то полагая

T = 1 имеем

i=1

1(1)

Напомним, что R

— стоимость работ, проведенных за время T ,

— максимально возможная стоимость работ,

— загруженность функционального устройства, Z

= R

Деля и умножая каждое слагаемое на P

1(i)

и пользуясь определе-

нием загруженности z

(i)

= R

1(i)

, получаем (2.2).

Следствие 2.1. Из формул (2.1) и (2.2) найдем

Z =

i=1

(i)

1(i)

. (2.3)

С учетом формулы

i=1

1(i)

получаем

min

i=1,...,k

(i)

≤ Z ≤ max

i=1,...,k

(i)

. (2.4)

Следствие 2.2 Если система состоит из независимых

устройств одинаковой пиковой производительности, то в усло-

виях теоремы 2.2 ее загруженность равна среднему арифметиче-

скому загруженностей ее функциональных устройств.

Следствие 2.3 В условиях теоремы 2.2 загруженность си-

стемы равна единице тогда и только тогда, когда равна единице

загруженность всех ее функциональных устройств.

Следствие 2.4 В условиях теоремы 2.2 для того чтобы обес-

печить выполнение обьема работы заданной стоимости за мини-

мальное время, нужно обеспечить максимальную загруженность

устройств наибольшей пиковой производительности.

Теорема 2.3. Пусть s простых независимых функциональ-

ных устройств за время T в общей сложности выполняют N

операций длительностью τ

, i = 1, . . . , r. Пусть z

— загружен-

ность j-го функционального устройства. Тогда

j=1

i=1

. (2.5)

Д о к а з а т е л ь с т в о почти очевидно. Пусть N

— число опе-

раций с номером i на j-м устройстве. Ясно, что

j=1

С другой стороны, z

i=1

, откуда

j=1

i=1

j=1

что совпадает с доказываемой формулой (2.5).

Теорема 2.4 Пусть s конвейерных функциональных

устройств за время T в общей сложности выполняют N опера-

ций, и каждое из этих функциональных устройств может вы-

полнять лишь операции одной длительности. Пусть z

— загру-

женность j-го устройства. Тогда

j=1

. (2.6)

Д о к а з а т е л ь с т в о. Обозначим τ

длительность операций на

j-м устройстве, а N

— их количество.

Стоимость реально выполненной работы на j-м устройстве рав-

на τ

, а максимально возможная стоимость работы, которую

можно осуществить на j-м устройстве, по теореме 2.2 равна τ

T .

Поэтому загруженность j-го устройства равна z

= (τ

)/(τ

T ) =

)/T .

Поскольку

j=1

= N, то теперь легко получить формулу

(2.6). Теорема доказана.

§ 3. О времени реализации алгоритма

Теорема 3.1. Время реализации алгоритма не меньше, чем

время выполнения операций, находящихся на каждом произвольно

выбранном пути графа алгоритма.

Д о к а з а т е л ь с т в о вытекает из того факта, что операции,

находящиеся на одном пути алгоритма не могут выполняться од-

новременно.

Теорема 3.2. Любой алгоритм при подходящем составе и

количестве функциональных устройств может быть реализован

за время, равное максимальному из времен последовательного вы-

полнения операций, находящихся на отдельных путях графа алго-

ритма.

Д о к а з а т е л ь с т в о. Используя сведения об имеющихся

функциональных устройствах, укажем в вершинах графа время

выполнения соответствующих операций. Далее заменим все вер-

шины графа линейными цепочками новых вершин, число которых

совпадает со временем выполнения упомянутых операций и постро-

им для полученного графа его каноническую максимальную парал-

лельную форму

. Очевидно, что высота этой формы равна макси-

мальному из врем¨ен последовательного выполнения всех операций,

находящихся на различных путях исходного графа (т.е. высота на

единицу больше длины критического пути графа). На месте каждо-

го яруса поставим соответствующее конвейерное функциональное

устройство. Ясно, что в результате получится набор функциональ-

ных устройств, позволяющий реализовывать алгоритм за указанное

в утверждении время. Теорема доказана.

Замечание. На каждом ярусе вместо конвейерных функцио-

нальных устройств можно использовать простые функциональные

устройства, но в значительно большем количестве (примерно во

столько раз больше, во сколько больше длительность выполнения

операций). Нетрудно видеть, что хотя общее время решения задачи

может уменьшаться при использовании б´ольшего количества функ-

циональных устройств, но тем не менее при заданном наборе типов

функциональных устройств оно ограничено снизу, так что начиная

с некоторого момента дальнейшее увеличение количества функци-

ональных устройств бесполезно; при этом, как правило, не реали-

зуется полная загруженность системы ни при каком наборе функ-

циональных устройств.

Постоянно возникают следующие кардинальные вопросы:

– нужно ли создавать специализированные параллельные си-

стемы для решения тех или иных классов задач (для некоторых

таких классов ответ оказывается отрицательным),

– что следует делать для увеличения загруженности системы,

– как заранее распознавать трудные для распараллеливания

ситуации.

Ответы на подобные вопросы можно получить лишь при рас-

смотрении конкретных ситуаций.

Параллельная форма называется канонической, если она — результат то-

пологической сортировки графа; в этом случае все пути начинаются на первом

ярусе.