Материал: Tannenbaum

Вопросы разработки компьютеров параллельного действия 573

ней, не будет пользоваться особым спросом. В этом разделе мы рассмотрим неко-
торые вопросы производительности, связанные с созданием архитектур параллель-
ных компьютеров.

Метрика аппаратного обеспечения

В аппаратном обеспечении наибольший интерес представляет скорость работы про-

цессоров, устройств ввода-вывода и сети. Скорость работы процессоров и устройств
ввода-вывода такая же, как и в однопроцессорной машине, поэтому ключевыми
параметрами в параллельной системе являются те, которые связаны с межсоеди-
нением. Здесь есть два ключевых момента: время ожидания и пропускная способ-
ность. Мы рассмотрим их по очереди.

Полное время ожидания — это время, которое требуется на то, чтобы процес-

сор отправил пакет и получил ответ. Если пакет посылается в память, то время
ожидания — это время, которое требуется на чтение и запись слова или блока слов.

Если пакет посылается другому процессору, то время ожидания — это время, ко-

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

Время ожидания строится из нескольких факторов. Для сетей с коммутацией

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

s

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

собность b битов в секунду, то время ожидания в одну сторону составит T

s

+p/b.

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

ответа размером в р битов составляет T

s

+2p/b секунд.

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

ния заранее, но все равно требуется некоторое время установки, Т

а

, на компоновку

пакета. Здесь время передачи в одну сторону составляет Т

а

+р/Ь, но за этот период

пакет доходит только до первого коммутатора. При прохождении через сам комму-
татор получается некоторая задержка, Т<ъ а затем происходит переход к следующе-
му коммутатору и т. д. Время T

d

 состоит из времени обработки и задержки в очереди

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

таторов, то общее время ожидания в одну сторону составляет T

a

+n(p/b+T

d

)+p/b,

где последнее слагаемое отражает копирование пакета из последнего коммутатора
в пункт назначения.

Время ожидания в одну сторону для коммутации без буферизации пакетов и

«червоточины» в лучшем случае будет приближаться к Т

а

+р/Ь, поскольку здесь

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

ку на распространение сигнала, но она обычно незначительна.

5 7 4 Глава 8. Архитектуры компьютеров параллельного действия

Следующая характеристика аппаратного обеспечения — пропускная способ-

ность. Многие программы параллельной обработки, особенно в естественных на-

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

изводительности. Существует несколько показателей пропускной способности.
Один из них — пропускная способность между двумя секциями — мы уже рас-
смотрели. Другой показатель —

 суммарная пропускная способность

 — вычисля-

ется путем суммирования пропускной способности всех каналов связи. Это число
показывает максимальное число битов, которое можно передать сразу. Еще один
важный показатель — средняя пропускная способность каждого процессора. Если
каждый процессор способен выдавать только 1 Мбайт/с, то от сети с пропускной
способностью между секциями в 100 Гбайт/с не будет толку. Скорость взаимодей-
ствия будет ограничена тем, сколько данных может выдавать каждый процессор.

На практике приблизиться к теоретически возможной пропускной способнос-

ти очень трудно. Пропускная способность сокращается по многим причинам. На-
пример, каждый пакет всегда содержит какие-то служебные сигналы и данные: это
компоновка, построение заголовка, отправка. При отправке 1024 пакетов по 4 бай-
та каждый мы никогда не достигнем той же пропускной способности, что и при
отправке 1 пакета на 4096 байтов. К сожалению, для достижения маленького вре-
мени ожидания лучше использовать маленькие пакеты, поскольку большие надолго
блокируют линии и коммутаторы. В результате возникает конфликт между дости-
жением низкого времени ожидания и высокой пропускной способности. Для од-
них прикладных задач первое важнее, чем второе, для других — наоборот. Важно
знать, что всегда можно купить более высокую пропускную способность (добавив
больше проводов или поставив более широкие провода), но нельзя купить низкое
время ожидания. Поэтому лучше сначала сделать время ожидания как можно мень-
ше, а уже потом заботиться о пропускной способности.

Метрика программного обеспечения

Метрика аппаратного обеспечения показывает, на что способно аппаратное обес-
печение. Но пользователей интересует совсем другое. Они хотят знать, насколько
быстрее будут работать их программы на компьютере параллельного действия по
сравнению с однопроцессорным компьютером. Для них ключевым показателем

является коэффициент ускорения: насколько быстрее работает программа в п-про-
цессорной системе по сравнению с 1-процессорной системой. Результаты обычно
иллюстрируются графиком (рис. 8.8.). Здесь мы видим несколько разных парал-
лельных программ, которые работают на мультикомпьютере, состоящем из 64 про-

цессоров Pentium Pro. Каждая кривая показывает повышение скорости работы
одной программы с к процессорами как функцию от к. Идеальное повышение ско-
рости показано пунктирной линией, где использование

 к

 процессоров заставляет

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

достигают совершенного повышения скорости, но есть достаточное число программ,
которые приближаются к идеалу. Скорость работы N-объектной задачи с добавле-

Вопросы разработки компьютеров параллельного действия

575

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

60

50

-о

N-объектная задача

- Авари

-«— Горизонтальное

инвертирование матрицы

10

20

30

40

50

60

Количество процессоров

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

Идеальный коэффициент ускорения показан пунктирной линией

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

повышения скорости: все программы содержат последовательную часть, они часто
имеют фазу инициализации, они обычно должны считывать данные и собирать
результаты. Большое количество процессоров здесь не поможет. Предположим, что
на однопроцессорном компьютере программа работает Т секунд, причем доля (f)
от этого времени является последовательным кодом, а доля (1-f) потенциально
параллелизуется, как показано на рис. 8.9, а. Если второй код можно запустить на п
процессорах без издержек, то время выполнения программы в лучшем случае
сократится с (l-f)T до (1-f )Т/п, как показано на рис. 8.9, б. В результате общее
время выполнения программы (и последовательной и параллельной частей) будет
f T+( I -f )Т/п. Коэффициент ускорения — это время выполнения изначальной про-
граммы (Т), разделенное на это новое время выполнения:

Speedup» n /d+(n-l)f)

Для f=0 мы можем получить линейное повышение скорости, но для f>0 иде-

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

 закона Амдала.

576 Глава 8. Архитектуры компьютеров параллельного действия

Последовательная

часть программы

1

f

Потенциально

параллелизируемая

часть программы

\

1-t i

а

Действует

1 процессор

\

I f

-»-fT-«-

Действуют

п процессоров

I

1-f

-

—(1 -f )T/n—

*-

б

Рис. 8.9. Программа содержит последовательную часть и параллелизуемую часть (а);

результат параллельной обработки части программы (б)

Закон Амдала — это только одна причина, по которой невозможно идеальное

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

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

Как достичь высокой производительности

Самый простой способ — включить в систему дополнительные процессоры. Одна-
ко добавлять процессоры нужно таким образом, чтобы при этом не ограничивать
повышение производительности системы. Система, к которой можно добавлять
процессоры и получать соответственно этому большую производительность, на-

зывается

 расширяемой.

Рассмотрим 4 процессора, которые соединены шиной (рис. 8.10, а). А теперь пред-

ставим, что мы расширили систему до 16 процессоров, добавив еще 12 (рис. 8.10,

 б).

Если пропускная способность шины составляет b Мбайт/с, то увеличив в 4 раза

число процессоров, мы сократим имеющуюся пропускную способность каждого
процессора с Ь/4 Мбайт/с до Ь/16 Мбайт/с. Такая система не является расши-
ряемой.

А теперь проделаем то же действие с сеткой (решеткой) межсоединений

(рис. 8.10,

 в, г).

 В такой топологии при добавлении новых процессоров мы добав-

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

Отношение числа каналов к числу процессоров увеличивается от 1,0 при нали-

чии 4 процессоров (4 процессора, 4 канала) до 1,5 при наличии 16 процессоров

Вопросы разработки компьютеров параллельного действия 577

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

Процессор

р

? ? ? у

t

 ШШ

Ш

t

Шина

а 6 в г

Рис. 8.10. Система из 4 процессоров, соединенных шиной (а); система из 16 процессоров,

соединенных шиной (б); сетка межсоединений из 4 процессоров (в); сетка межсоединений

из 16 процессоров (г)

Естественно, пропускная способность — это не единственный параметр. Добав-

ление процессоров к шине не увеличивает диаметр сети или время ожидания при
отсутствии трафика, а добавление процессоров к решетке, напротив, увеличивает.
Диаметр решетки пхп равен 2(п—1), поэтому в худшем случае время ожидания
растет примерно как квадратный корень от числа процессоров. Для 400 процессо-
ров диаметр равен 38, а для 1600 процессоров — 78, поэтому если увеличить число
процессоров в 4 раза, то диаметр, а следовательно, и среднее время ожидания
вырастут приблизительно вдвое.

В идеале расширяемая система при добавлении новых процессоров должна со-

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

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

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

Системные разработчики применяют несколько различных технологий, кото-

рые позволяют сократить или, по крайней мере, скрыть время ожидания. Первая
технология — это копирование данных. Если копии блока данных можно хранить
в нескольких местах, то можно увеличить скорость доступа к этим данным. Один
из возможных вариантов — использование кэш-памяти, когда одна или несколько
копий блоков данных хранятся близко к тому месту, где они могут понадобиться.
Другой вариант — сохранять несколько равноправных копий — копий с равным
статусом (в противоположность асимметричным отношениям первичности/вто-
ричности, которые наблюдаются при использовании кэш-памяти). Когда сохраня-

ется несколько копий, главные вопросы — это кем, когда и куда они помещены.