Файл: 551-668.pdf

Контрольные вопросы  6 1 1

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

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

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

толических ВС для этого требуется строгая синхронизация.

Концепцию массива процессоров волнового фронта проиллюстрируем на при-

мере матричного умножения (рис. 14.19).

Вычислительная система в примере состоит из процессорных элементов, име-

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

Операнды из других ПЭ принимаются на основе протокола связи с подтвержде-
нием.

Рисунок 14.19,

 а

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

ных буферов. Здесь ПЭ(1,1) суммирует произведение

 а

 х

 е

 с содержимым своего

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

 а и е

 своим соседям. Таким образом, пер-

вый волновой фронт вычислений (см. рис. 14.19,

6)

 перемещается в направлении

от ПЭ(1,1) к ПЭ(1,2) и ПЭ(2,1). Рисунок 14.19, в иллюстрирует продолжение распрос-
транения первого фронта и исход от ПЭ(1,1) второго фронта вычислений.

По сравнению с систолическими ВС массивы волнового фронта обладают луч-

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

высокой отказоустойчивостью.

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

1. По какому признаку вычислительную систему можно отнести к сильно связан-

ным или слабо связанным ВС?

2. Какие уровни параллелизма реализуют симметричные мультипроцессорные

системы?

3. Какими средствами поддерживается когерентность кэш-памяти в SMP-систе-

мах?

4. Оцените достоинства и недостатки различных SMP-архитектур.
5. В чем состоит принципиальное различие между матричными и симметричны-

ми мультипроцессорными вычислительными системами?

6. Какие две проблемы призвана решить кластерная организация вычислитель-

ной системы?

7. Существуют ли ограничения на число узлов в кластерной ВС? И если суще-

ствуют, то чем они обусловлены?

8. Какие задачи в кластерной вычислительной системе возлагаются на специали-

зированное (кластерное) программное обеспечение?

6 1 2 Глава 14. Вычислительные системы класса MIMD

9. Каким образом может быть организовано взаимодействие между узлами клас-

терной ВС?

10. При каком количестве процессоров ВС можно отнести к системам с массовой

параллельной обработкой?

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

даний в МРР-системах?

12. Какие топологии можно считать наиболее подходящими для МРР-систем и по-

чему?

13. Поясните назначение справочника в вычислительных системах типа CC-NUMA.
14. Какие протоколы когерентности, на ваш взгляд, наиболее подходят для ВС,

построенных на технологии CC-NUMA?

15. Какие черты транспьютера отличают его от стандартной однокристальной ВМ?

16. Какими аппаратными и программными средствами поддерживается взаимодей-

ствие соседних транспьютеров в вычислительной системе?

17. Сколько линий поддерживает канал связи транспьютера, как они используются

и в каком режиме осуществляется ввод/вывод?

18. Какие особенности транспьютеров облегчает реализовать язык Occam?

19. Опишите структуру пакета данных и пакета подтверждения, передаваемых

в транспьютерных ВС.

20. Какие из рассмотренных типов вычислительных систем могут быть построены

на базе транспьютеров и в каких случаях это наиболее целесообразно?

21. В чем состоят сходство и различие между систолическими ВС и вычислитель-

ными системами с обработкой по принципу волнового фронта?

22. Как организуется межпроцессорный обмен в массивах волнового фронта?

Глава 15

Потоковые и редукционные

вычислительные системы

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

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

с помощью программного счетчика, иногда называют

 вычислительными система-

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

 (control flow computer). Данный

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

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

- команда выполняется, после того как выполнена предшествующая ей команда

последовательности;

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

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

довательностью команд; второй механизм известен как

 управляемый данными

 (data

driven) или

 потоковый

 (dataflow); третий метод называют механизмом

 управления

по запросу

 (demand driven).

6 1 4 Глава 15. Потоковые и редукционные вычислительные системы

Общие идеи нетрадиционных подходов к организации вычислительного про-

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

Рис. 1 5 . 1 . Возможные вычислительные модели:

 а —

 фон-неймановская;

 б—

 потоковая;

в —

 макропотоковая; г—редукционная

Вычислительные системы с управлением

вычислениями от потока данных

Идеология вычислений, управляемых потоком данных (потоковой обработки),
была разработана в 60-х гадах Карпом и Миллером. В начале 70-х годов Деннис,
а позже и другие начали разрабатывать компьютерные архитектуры, основанные
на вычислительной модели с потоком данных.

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

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

 графом потоков данных

 (dataflow graph).

Этот граф состоит из

 узлов

 или

 вершин,

 отображающих операции, и

 ребер

 или

 дуг,

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

Узловые операции выполняются, когда по дугам в узел поступила вся необхо-

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

ния. По выполнении операции формируются один или два результата. Таким

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

 инициированием вершины)

 результаты передаются по ребрам к

ожидающим вершинам. Процесс повторяется, пока не будут инициированы все

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

ляется автоматически.

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

  6 1 5

Рис.

 15.2. Граф потоков данных для выражения А/B + В х С

На рис. 15.2 показан простой потоковый граф для вычисления выражения f=

А/В+

+ В x С.

 Входами служат переменные А, В и С, изображенные вверху графа. Дуги

между вершинами показывают тракты узловых операций. Направление вычисле-
ний — сверху вниз. Используются три вычислительные операции: сложение,
умножение и деление. Заметим, что В требуется в двух узлах. Вершина «Копи-
рование»- предназначена для формирования дополнительной копии перемен-

ной В.

Данные (операнды/результаты), перемещаемые вдоль дуг, содержатся в опо-

знавательных информационных кадрах, маркерах специального формата —

 «то-

кенах

» (иначе «фишках»- или маркерах доступа). Рисунок 15.3 иллюстрирует дви-

жение токенов между узлами. После поступления на граф входной информации
маркер, содержащий значение А, направляется в вершину деления; токен с пере-
менной В — в вершину копирования; токен с переменной С — в вершину умноже-
ния. Активирована может быть только вершина «Копирование», поскольку у нее

лишь один вход и на нем уже присутствует токен. Когда токены из вершины «Ко-

пирование*' будут готовы, узлы умножения и деления также получат все необхо-

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

необходимые токены.

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

стей, например при выполнении команд условного перехода. По этой причине
в потоковых графах предусмотрены вершины-примитивы нескольких типов
(рис. 15.4):