12.3.2.Асимптотическая производительность

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

Методику оценки производительности конвейеров операций рассмотрим на примере конвейера операции сложения. Положим, что имеется l-ступенчатый конвейер операции сложения и пусть все ступени конвейера операций требуют одинакового времени выполнения Δt. Пусть s Δt -фиксированное время запуска конвейера, lΔt - время "разгона" конвейера. Тогда для выполнения операции сложения векторов X=(x₁,…,x_n) и Y=(y₁,…,y_n) требуется время T_конв=(s+l+n) Δt.

После запуска конвейера и его "разгона" конвейер выдает результат через каждый такт Δt. Т.е. максимальная скорость выдачи результатов конвейером (максимальное быстродействие) равна (r_∞)_конв=1/Δt. Это принято называть асимптотическим быстродействием. Быстродействие конвейера приближается к асимптотическому быстродействию в случае, когда в формуле T_конв=(s+l+n) Δt можно пренебречь слагаемыми (s+l) Δt. Эта ситуация имеет место когда длина обрабатываемых векторов n много больше величины s+l.

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

При работе конвейера в последовательном режиме, очевидно, максимальная скорость выдачи результатов равна (r_∞)_посл=1/lΔt. Таким образом, конвейерная обработка увеличивает производительность вычислительной системы в l раз (на векторах бесконечной длины).

Рассмотрим оценку асимптотической производительности векторно-параллельных систем и MIMD-систем рассмотрим на примере операции сложения векторов сложения векторов X=(x₁,…,x_n) и Y=(y₁,…,y_n) на s-процессорной системе. Время выполнения этой операции как на векторно-параллельной системе, так на MIMD-системе можно оценить суммой времени коммуникации T_com и времени вычислений T_cal. Пусть d - диаметр коммуникационной сети системы, производительность каналов межпроцессорного обмена равна v байт/ сек, а время операции сложения двух чисел на одном процессоре – τ сек. Тогда T_com =O(dnv/s), T_cal =nτ/s.

Если пренебречь коммуникационными расходами, то получаем предельно возможное время вычислений T_cal /n. Таким образом, максимальная скорость выдачи результатов s-процессорной векторно-параллельной системой и MIMD-системой (максимальное быстродействие) равна (r_∞)_парал= 1/ T_cal =s/ τ.

Эту величину также принято называть асимптотическим быстродействием. Быстродействие векторно-параллельной системы и MIMD-системы приближается к асимптотическому быстродействию в случае, когда можно пренебречь коммуникационной составляющей и когда величина n кратна s. При сложении векторов на одном процессоре системы максимальная скорость выдачи результатов равна, очевидно, (r_∞)_парал= 1 / τ.

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

Важной характеристикой параллельных вычислительных систем является n_1/2 - длина векторов, на которых достигается половина асимптотического быстродействия системы. Эта величина называется длиной полупроизводительности. Смыслы асимптотического быстродействия и длины полупроизводительности различны. Асимптотическое быстродействие, главным образом, характеризует технологию изготовления ЭВМ, в то время как длина полупроизводительности представляет собой критерий степени параллелизма системы. Относительная производительность различных алгоритмов на данной параллельной вычислительной системе определяется длиной полупроизводительности.

Пусть n –средняя длина обрабатываемого вектора, а σ= n_1/2 /n. Чем больше эта величина, тем меньше эффект от распараллеливания.

Пример.(Из [10]).

Рассматривается операция перемножения двух матриц на параллельных вычислительных системах CYBER-205 и CRAY-1. Результаты приведены в таблице.

ЭВМ	Операция	(r∞)парал [MFLOPS]	n1/2
CYBER-205	Сложение векторов	100	102
CYBER-205	Скалярное произведение	100	116
CRAY-1	Перемножение двух матриц	153	7

Пусть средняя длина обрабатываемых векторов n равна 100. Тогда для решения рассматриваемой задачи система CRAY-1 гораздо более эффективна по сравнению с системой CYBER-205.

Также важными характеристиками производительности вычислительных систем являются параметры, учитывающие организацию топологии процессоров: связи между устройствами, отображаемыми в виде ориентированного графа, в котором вершины обозначают устройства, а дуги - связи между ними . Предположим, дуга графа системы идет из i-го устройства в j-е. Поскольку результат i-го устройства является аргументом j-го, количество операций, выполняемых j-м устройством, не может более, чем на 1, отличаться от количества операций, реализованных i-м устройством: N -1≤ N_j ≤N_t +1. Если связный граф содержит q дуг, k-е устройство за время T выполнило N_k операций, а l-е - N_l операций, то отсюда вытекает, что

N_l - q ≤ N_k ≤ N_l + q для любых k, l, 1 < k, l < s.

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

_{(N1 -q)s + q ≤< tNt ≤ (N1 +q)s -q.}

Разделив все части неравенств на T получим ₁s-(s-1)q/T≤r≤₁s+(s-1)q/T.

Слагаемые q(s -1)/T при увеличении T стремятся к нулю. Это означает, что для системы из s устройств с пиковыми производительностями ₁≤₂≤…≤_s описываемой связным графом, максимальная производительность определяется как r_max=s₁. Тогда максимальная загруженность системы p_max= r_max / , а максимальное ускорение R_max= r_max /_s .

Мы вновь получили подтверждение вышеприведенным выводам. Иногла эти выводы называются законами Амдала.

1-й закон Амдала. Производительность вычислительной системы, со­стоящей из связанных между собой устройств, определяется самым непроизво­дительным устройством.

2-й закон Амдала:

Пусть система состоит из s одинаковых устройств, а n операций из общего числа операций алгоритма N могут выполняться только последовательно, тогда максимально возможное ускорение равно s/(ns/N + 1- n/N).

Эта формула используется для прогноза возможного ускорения. На­пример, в случае, когда половина операций не поддаются распараллеливанию, максимально достижимое ускорение в случае использования 2 процессоров составит около 1,33, для 10 процессоров - менее 1,82, а для 100 процессоров - около 1,98. В данном примере наиболее «узким» местом является сам алгоритм решения задачи, а основные усилия должны быть на­правлены на поиск другой формулировки задачи, допускающей более высокую степень параллелизма.

Оценку максимально достижимого ускорения параллельного алгоритма можно построить также исходя из имеющейся доли последовательных расче­тов, задаваемой в виде: g = τ_n/(τ_n+τ_N-n/s), τ_n и τ_N-n - время, необходимое для выполнения последовательной и па­раллельной частей соответственно.

С учетом введенных обозначений время решения задачи на одном и s процессорах соответственно T₁ = τ_{n +} τ_N-n, T_s = τ_n+τ_N-n/s. С другой стороны, для величины g можно записать: τ_n = g(τ_n+τ_N-n/s); τ_N-n=(1-g)s(τ_n+τ_N-n/s).

Отсюда следует, так называемый, закон Густавсона – Барсиса:

T₁/T_s=g+(1-g)s=s+(1-s)g.

Если процессоры - ФУ конвейерного типа, то операция разбивается на последователь­ность микроопераций. Каждую микрооперацию выделяют в отдельную часть устройства и располагают их в порядке выполнения так, чтобы входные аргу­менты прошли через все ступени конвейера.

Предположим, что конвейерное устройство состоит из l ступеней, срабаты­вающих за один такт. Тогда, например, для сложения двух векторов из n эле­ментов потребуется l + n -1 тактов. Если при этом используются также вектор­ные команды, то потребуется (возможно, несколько) дополнительных тактов для их инициализации. Эта величина учитывает также возможные пропуски тактов выдачи результатов на выходе конвейера, вследствие необходимости выполнения вспомогательных операций, связанных с организацией конвейера.

С использованием введенных обозначений запишем соотношение для оценки производительности конвейера: E=n/t=1/[τ+(σ+l-1)τ/n].

где τ- время такта работы компьютера.

Обычно вычислительные системы строятся с использованием одновременно всех типов устройств: скалярных, векторных конвейерных. В частности, первый векторно-конвейерный компьютер Cray-1 (пиковая производительность 160 Mflops) имел 12 конвейерных функциональных устройств, причем все функциональные устройства могли работать одновременно и независимо друг от друга.

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

T_s<T_∞+T₁/s.

Действительно, пусть H_∞ есть расписание для достижения минимально воз­можного времени выполнения T_∞. Для каждой итерации τ: 0<τ< T_∞ выполнения расписания H_∞ обозначим через п_т количество операций, выполняемых в ходе итерации τ. Расписание выполнения алгоритма с использованием s процессоров может быть построено следующим образом. Выполнение алгоритма разделим на T_∞ шагов; на каждом шаге т следует выполнить все п_т операций, которые вы­полнялись на итерации т расписания H_∞. Эти операции могут быть выполнены не более чем за ]n_τ/s[ итераций при использовании s процессоров. Как резуль­тат, время выполнения алгоритма T_s может быть оценено следующим образом:

T_s = ]n_τ/s[ < ]1+n_τ/s[ = T₁/s+ T_∞.

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