Математическая модель характеристик производительности распределённых вычислительных систем

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

В последнее время также активно развиваются технологии распределённых вычислений [2], в частности, — Грид-технологии [3]. Распределенная система представляет собой инфраструктуру, объединяющую совокупность географически распределённых неоднородных вычислительных ресурсов. Ресурсы, входящие в распределенную систему, будем называть узлами этой системы. Узлы могут быть как обычными рабочими станциями с одним процессором, так и многопроцессорными вычислительными комплексами (МВК).

Параллельные системы применяются достаточно давно, поэтому для них разработано большое число различных методов и моделей, и, в

Сравнение параллельных частности, моделей производительности [4]. Такие понятия, как ускорение, эффективность, загрузка, пиковая производительность, широко используются при оценке качества параллельных систем и приложений. Распределённые системы стали применяться в вычислительных целях относительно недавно. Видимо, по этой причине аналогичных параметров для распределённых систем к настоящему моменту не разработано.

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

Т аблица 1

и распределённых систем

Характеристика	Параллельная система	Распределенная система
Степень связности	Высокая степень связности: высокопроизводительная сеть (интерконнект) либо общая память.	Слабая связность: каналы с относительно низкими показателями пропускной способности и задержки.
Узлы	Как правило, однородные по производительности и архитектуре процессорные устройства.	Неоднородные по производительности и архитектуре вычислительные машины.
Готовность выполнять вычисления	Выделенные процессоры доступны в течение всего времени вычислений.	Узлы могут выходить из состава распределенной системы или, наоборот, добавляться к ней в процессе вычислений.

II.    Модель параллельной системы

Рассмотрим традиционную модель производительности параллельной системы, предложенную в [4]. Под параллельной системой будем понимать вычислительную систему, состоящую из n одинаковых функциональных устройств, объединённых вычислительной сетью [5].

Рассмотрим решение одной вычислительной задачи A на параллельной системе. Пусть время решения задачи на этой системе составляет T .Зафиксируем некоторый эталонный последовательный алгоритм решения задачи A . Пусть время решения задачи A с помощью этого алгоритма одним устройством составляет Т о . Ускорение S определяется как отношение S = Т о /Т . Таким образом, ускорение показывает, во сколько раз можно уменьшить время решения задачи с помощью применения параллельной системы. Заметим, что в качестве эталонного алгоритма обычно выбирают наиболее быстрый известный последовательный алгоритм.

Принято определять эффективность E параллельной системы как E = S/n (см. также [4]). Эффективность можно переписать как

E =

S n

Т о nT ^.

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

III.    Модель системы с расписанием

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

Рассмотрим вычислительную систему с расписанием, состоящую из n функциональных устройств. Пусть дана задача A из некоторого класса задач A . Предположим, что функциональные устройства рассматриваемой системы могут решать задачи этого класса, при этом время решения задачи Ai -м устройством составляет

T i ( A ) >  0. Также для каждого устройства задано расписание, которое мы опишем функцией времени h i ( t ) : R + ^ { 0 , 1 } . При этом h i ( t ) = 1, если устройство в момент времени t выделено для решения, и h i ( t ) = 0 в противном случае. Рассматривать будем только расписания, задаваемые функцией h ( t ) = ( h i ( t )), имеющей не более конечного числа точек разрыва на любом ограниченном интервале времени.

Определение. Под доступностью p i ( t ) устройства будем понимать долю временного интервала [0 ,t ], в течение которого устройство было выделено для решения задачи A . При этом значение доступности i -го устройства определяется формулой

T

Pi(Т) = Т J hi(t) dT.

о

Построенная модель позволяет описывать вычислительные системы с расписанием. Обозначим вычислительную систему с расписанием через R . Формальное определение дадим позже.

Для параллельной системы, согласно выражению (1), эффективность определяется как E = То / (пТ). Данное выражение можно перепи- сать в виде

T /n

E =   ^ , где выражение То/п соответствует некоторому ’эталонному’ времени решения задачи A системой из n устройств. Для системы с расписанием определим эффективность аналогичным образом.

Определение. Эффективностью E системы с расписанием будем называть величину

E =

—

Т (A) Т (A), где Т(A) — эталонное время решения задачи A, а Т (A) — реальное время решения задачи A.

Для определения эталонного времени решения задачи нам понадобится величина, называемая эталонной производительностью п(A,t) системы R. Зафиксируем некоторый эталонный последовательный алгоритм решения задачи A. Обозначим через Т (A) > 0 время решения задачи Ai-м устройством с помощью данного алгоритма. Заметим, что в качестве эталонного алгоритма обычно выбирается наиболее быстрый известный последовательный алгоритм. Будем называть эталонной производительностью ni (A) устройства i при решении задачи A величину п (A) =

L ( A ) Т i ( A ) ’

здесь L(A) — функция трудоёмкости задачи (см. также [4]). Функция трудоёмкости L (A) : A ^ R+ определена на некотором множестве задач A ивы-ражает наше априорное знание о сложности решения задачи — вычислительных ресурсах, которые необходимо затратить на её решение. Примером такой функции может служить оценка числа элементарных операций, выполняемых алгоритмом. Заметим, что функцию L(A) можно в некоторых случаях принять тождественно равной единице L (A) = 1.

Эффективность параллельной системы можно представить как

E

n • 1 /То

L (A)/Т n • по (A) ’

где п о ( A ) — эталонная производительность одного устройства. L ( A ) /Т можно рассматривать как реальную производительность параллельной системы, n • п о ( A ) — как эталонную.

Введём эталонную производительность п ( A,t ) системы с расписанием R как сумму эталонных производительностей устройств с учётом расписания. Эталонная производительность п ( A,t ) запишется в виде

n

п (A,t) = h Пi (A) hi (t).

i =1

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

Определение. Ускорением S системы с расписанием R 1 относительно системы R ₂ будем называть отношение времён решения задачи A этими системами:

S (Ri, R2) = ^.

Т 2

Определим коэффициент ускорения S i как отношение эталонного времени решения задачи на устройстве i ко времени решения задачи на всей

системе:

—

Si = Ту

.

При полной доступности устройств h i ( t ) = 1 ( i = 1 ...n ) в процессе решения задачи и при одинаковой эталонной производительности п _i ( A ) = п о эталонная производительность системы будет совпадать с n • п о , то есть с эталонной производительностью параллельной системы.

Дадим формальное определение вычислительной системы с расписанием.

Определение. Вычислительной системой с расписанием R для решения задач из множества A будем называть совокупность

R = < п(A),h(t) > ,

Под относительным ускорением системы с расписанием R будем понимать вектор

S = (Si, ..., Sn).

Утверждение 1. Для распределенной системы с расписанием R справедливо следующее со-

отношение:

E=

(h S)

- 1

где ? ( A ) : A ^ R + — вектор эталонных производительностей устройств, h ( t ) : R + ^ { 0 , 1 }ⁿ — функция расписания, при этом n соответствует числу устройств в системе.

Определение. Эталонным временем решения T ( A ) задачи A системой с расписанием R будем называть решение задачи оптимизации

Доказательство. Действительно, по определению эффективность системы с расписанием составляет E = Т/Т , из определения эталонного времени решения (2) следует:

^ i n

h п hi (t) dT = L (A).

_о i =1

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

min t,

Итак,

t

| п(A,t)dT = L(A), т=0

0 < t < ж.

эффективность вычислительной систе-

мы с расписанием определяется как

E=

-

T (A)

T (A)’

где T ( A ) — время решения, определяемое экспериментально, а эталонное время Т ( A ) рассчитывается по формуле (2). Доступность i -го устройства при эталонном решении задачи будем обозначать через р i = p i ( Т ).

T

T

n                n 1

J h пihi(t)dT = h пуТТ J

о

о

n

hi(t)dT = h пу^Гpi, i=1

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

—

Т=

L (A)

E n _ - . i =1 ^п У ^р У

Отсюда следует, что, так как п _у = L ( A ) /T i , эффективность можно представить в виде

L (A)

E m v^ n   _

^T Z_^i =i ^p i ^п У

L (A)

T • L(A) £n=i T

£ n  РЦ^.

2^ i =1 Si

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

Интересно заметить, что если в распределенной системе с расписанием положить, что все устройства доступны в течение всего времени расчёта, то выражение для эффективности приобре-

тает вид

Е = (v — ^

E hetero I / _v s ^.

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

Рассмотрим выражение для закона Амдала для параллельных систем [4]. Пусть β выражает долю последовательных вычислений. Обычно, закон Амдала записывают для ускорения параллельной системы в виде

S <

Если же дополнительно положить, что все устройства решают задачу A за одинаковое время, то распределенная система будет эквивалентна однородной параллельной системе, и выражение для эффективности для неё будет иметь вид

в + (1 - в)/n

E parallel

(5 S)

- 1

S n

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

Обобщим последнее неравенство на случай неоднородных систем. Для неоднородных вычислительных систем относительное ускорение есть вектор из S i . Доля времени, затраченная системой на выполнение последовательной части алгоритма на j -м устройстве, составляет βT j . Параллельная часть алгоритма выполняется всеми устройствами системы за время (1 —в ) Т . Поэтому, согласно определению относительного ускорения, максимальное относительное ускорение S _i ^∗ _j для i -го устройства при выполнении последовательной части алгоритма полностью на j -м функциональном устройстве:

S* =      Ti

ij вТ + (1 — в) T.

hi (t) = 1,

ni (A) = по.

С учётом указанных соотношений эффективность системы с расписанием можно представить как

При этом для однородной параллельной системы выражение для максимального ускорения будет совпадать с правой частью неравенства в законе Амдала (5):

S∗

в + (1 — в)/n

_ T(A) _ L(A)/(n • по) _ TO parallel   t ( a )        t ( a )        nT,

Для однородной параллельной системы максимальная эффективность, согласно определению, составляет

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

* ₌ S * ₌       1

p = n = вп + (1 — в).

IV.    Закон Амдала для неоднородных систем

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

Под неоднородной вычислительной системой будем понимать такую систему с расписанием, для которой каждое устройство доступно в течение всего времени расчёта, то есть для любого i расписание h i ( t ) = 1. В дальнейшем под последовательной частью алгоритма будем понимать тот его участок, который может быть выполнен только на одном устройстве, при этом никакие другие

Для неоднородной системы из соотношений (3) и (6) можно получить выражение для максимальной эффективности при выполнении последовательной части алгоритма только на j-м устрой- стве:

E * = fe¹ /S * ,)

E j ^∗

= ( a ^V T i ^{+ (} 1 ^{— в} ))   .

Учитывая, что ^ i 1 /T i = 1 /T , получим

^_

E* =

• j   вТj + (1 — в) T

Подставив выражения для эталонной производительности устройства j и системы в целом, полу- чим

E * = ------1------.

j   в nj + 1 — в’ здесь п = ^2i ni — производительность системы.

Поскольку различные значения j описывают различные варианты распределения нагрузки, то очевидно, что

Е ^ max Е*. jj

Покажем, что в неоднородной системе с помощью выбора устройства для выполнения последовательной части можно добиться большей эффективности, чем в параллельных системах, состоящих из такого же числа устройств. Примем трудоёмкость задачи за единицу: L ( A ) = 1. Перепишем выражение для максимальной эффективности E j , учитывая, что n i = 1 /T i :

Е*=в E..+(1 -3), ji

E E* = пз E ni + (1 - 3) £ nj, ij             i                         j

£ nj ( E* E*) = 0.        (8)

Полученные соотношения можно интерпретировать следующим образом. Без ограничения общности можно считать, что п 1 3 п 2 ... 3 n n . Тогда значения максимальных эффективностей E _j ^∗ будут удовлетворять неравенствам

Е * 3 Е * 3 ... 3 Е П .

Кроме того, из равенства (8) следует соотношение, связывающее оценки эффективности в неоднородной и однородной системах:

Е * 3 Е* _р 3 Е П .

Заметим, что максимальная эффективность достигается в случае, когда последовательная часть алгоритма выполняется на вычислительном узле с наибольшей производительностью, что согласуется с интуитивным представлением об оптимальном размещении последовательной части. Поскольку п = ^i n i 3 п 1 , то из выражения для максимальной эффективности (7) следует, что Е * <  1, при этом lim _п 1 /_п^ 1 Е * = 1. Содержательно полученные соотношения означают, что эффективность неоднородной системы при решении задач с последовательной частью не превосходит единицы и будет близка к ней, если наиболее быстрое устройство системы сильно превосходит остальные устройства по производительности.

Приведённые рассуждения позволяют сформулировать закон Амдала для неоднородной системы в виде

Е < max Е* = ----—1———.

j 3   Зп + (1 — 3) п 1

Из соотношения (8) также следует, что обратная величина эффективности однородной системы равна обратному значению эффективности

ТРУДЫ МФТИ. — 2010. — Том 2, № 1(5) неоднородной системы, усреднённому по j с весами, равными относительным эталонным производительностям.

Е

j

п* 1 π Ej∗

∗ ^{, p}

Ep∗

^π _π ^j E j ^∗

)

- 1

Приведём также выражение для относительного ускорения, подставив выражения для эталонных производительностей устройств:

S * =         ^п * ^п

ij   3Пi п + (1 — 3) п* Пi.

Итак, справедливо следующее утверждение, выражающее закон Амдала для неоднородных вычислительных систем.

Утверждение 2. Пусть устройства неоднородной вычислительной системы R упорядочены по убыванию эталонной производительности п 1 3 п 2 3 ... 3 п _п , тогда справедливы соотноше-

ния:

Е <

S i <

π 1

3п + (1 — 3) п 1,

π1 π

3пiП + (1 — 3)п 1 Пi,

где β — доля последовательных вычислений.

Покажем, что для систем с расписанием закон Амдала в виде утверждения 2 неприменим. Рассмотрим частный случай однородной параллельной системы с расписанием. Пусть параметр 3 = 1 / 2, система состоит из двух устройств одинаковой производительности п _i = п о с расписанием:

h 1( t) = |

0,t Е [0,1 /2), 1 ,t Е [1 /2,1],

h *( t) = 1.

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

S

1         4

1 / 2 + 1 / 4 = 3,

E∗

S∗

.

Согласно определению эффективности и относительного ускорения для систем с расписанием, получим:

Т=1 / 2+1 / 4=4,

Е=

S 1

S2 =

—

T

T

—

T 1

T

—

T 2

T

= 1,

3 ^,

з.

Видно, что закон Амдала выполняется для ускорения, но не для эффективности. Для неоднородных систем максимальное относительное ускорение, определяемое формулой

S * =_______ ^п 1 ^п _______

i впп + (1 - в)пini ’

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

стем

S∗

π

вп + (1 — в) ’

так как n i ^ п 1 ( г = 1 ...n ). Рассмотрим теперь другой пример.

Рассмотрим распределенную систему с расписанием, состоящую из трёх устройств. Пусть эталонные производительности устройств равны п 1 =2, п 2 = 3 / 2, п з = 3 / 2 и расписание задается соотношениями

, . Г 0,t € [0,1 /2),

h 1(t)    |1 ,t Е [1 /2,1],  h2(t) - 1 ,h3(t) - 1.

Пусть в = 1 / 2. Если принять трудоёмкость задачи за единицу L ( A ) = 1, то эталонное время решения задачи A данной системой составляет T = 1 / 3. Относительные ускорения устройств:

S1 =

1 /

1 / 3

2’

S 2 = S3 =

2 / 3 1/3

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

- * -          2 • 5          _ 10

1 = 1 / 2 • 2 • 5 + 1 / 2 • 2 • 2 = 7

S2∗

1 / 2 • 3 / 2 • 5 + 1 / 2 • 2 • 3 / /2

40 <9

21

S * = 21 < S 3.

Таким образом, соотношение Si ^ Si, выражающее закон Амдала для неоднородных систем,

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

писанием.

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

V. Заключение

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

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