Файл: Tannenbaum.pdf

Вопросы и задания 643

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

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

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

MESI. Кроме того, возможны различные сети, а также машины на основе каталога

N U M A H C O M A .

Мультипроцессоры можно разделить на системы МРР и COW, хотя граница

между ними произвольна. К системам МРР относятся Cray ТЗЕ и Intel/Sandia
Option Red. В них используются запатентованные высокоскоростные сети межсо-
единений. Системы COW, напротив, строятся из таких стандартных деталей, как

Ethernet, ATM и Myrinet.

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

дачей сообщений (например, PVM или MPI). Оба пакета поддерживают библио-
течные вызовы для отправки и получения сообщений. Оба работают поверх суще-
ствующих операционных систем.

Альтернативный подход — использование памяти совместного использования

на прикладном уровне (например, система DSM со страничной организацией, про-
странство кортежей в системе Linda, объекты в системах Огса и Globe). Система
DSM моделирует совместно используемую память на уровне страниц, и в этом она
сходна с машиной NUMA. Системы Linda, Orca и Globe создают иллюзию совмест-
но используемой памяти с помощью кортежей, локальных объектов и глобальных
объектов соответственно.

Вопросы и задания

1. Утром пчелиная матка созывает рабочих пчел и сообщает им, что сегодня

им нужно собрать нектар ноготков. Рабочие пчелы вылетают из улья и ле-
тят в разных направлениях в поисках ноготков. Что это за система — SIMD
или MIMD?

2. Вычислите диаметр сети для каждой топологии, изображенной на рис. 8.4.
3. Для каждой топологии, изображенной на рис. 8.4, определите степень отказо-

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

4. Рассмотрим топологию двойной тор (см. рис. 8.4, е), расширенную до раз-

мера kxk. Каков диаметр такой сети? Подсказка: четное и нечетное к нужно
рассматривать отдельно.

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

5. Представим сеть в форме куба 8x8x8. Каждый канал связи имеет дуплекс-

ную пропускную способность 1 Гбайт/с. Какова бисекционная пропускная
способность этой сети?

6. Рассмотрим сеть в форме прямоугольной решетки размером 4 коммутатора

в ширину и 3 коммутатора в высоту. В ней пакеты, исходящие из левого
верхнего угла и направляющиеся в правый нижний угол, могут следовать
по любому из нескольких возможных путей. Пронумеруйте верхний ряд
коммутаторов с 1 по 4, следующий ряд — с 5 по 8, а нижний — с 9 по 12.
Выпишете все пути, по которым пакеты перемещаются только вправо или
вниз, начиная с коммутатора 1 и заканчивая коммутатором 12.

7. Закон Амдала ограничивает потенциальный коэффициент ускорения, до-

стижимый в компьютере параллельного действия. Вычислите как функцию
от f максимально возможный коэффициент ускорения, если число процес-
соров стремится к бесконечности. Каково значение этого предела для f=0,l?

8. На рисунке 8.10 показано, что расширение невозможно с шиной, но возможно

с решеткой. Каждая шина или канал связи имеет пропускную способность Ь.
Вычислите среднюю пропускную способность на каждый процессор для
каждого из четырех случаев. Затем расширьте каждую систему до 64 про-
цессоров и выполните те же вычисления. Чему равен предел, если число
процессоров стремится к бесконечности?

9. Компьютерная компания выпускает системы, состоящие из п компьютеров

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

1. Как это изменение повлияет на максимальное время ожидания?

2. Как это изменение повлияет на общую пропускную способность?

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

гласованности — это вид контракта между программным обеспечением и
памятью. Зачем нужен такой контракт?

11. Векторный процессор (например, Cray-1) содержит арифметические устрой-

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

12. Рассмотрим мультипроцессор с общей шиной. Что произойдет, если два

процессора попытаются получить доступ к глобальной памяти в один и тот
же момент?

13. Предположим, что по техническим причинам отслеживающий кэш может

отслеживать только адресные линии и не может отслеживать информаци-
онные. Повлияет ли это изменение на протокол сквозной записи?

14. Рассмотрим простую модель мультипроцессорной системы с шиной без

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

Вопросы и задания 645

время выполнения команды. Если шина занята, то запрашивающий про-
цессор становится в очередь «первым вошел — первым вышел». Насколько
быстрее будет работать система с 64 процессорами по сравнению с однопро-
цессорной системой?

15. Протокол MESI содержит 4 состояния. Каким из 4 состояний можно по-

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

16. Бывают ли в протоколе MESI такие ситуации, когда строка кэш-памяти при-

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

17. Предположим, что к общей шине подсоединено п процессоров. Вероятность,

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

1. Шина свободна (0 запросов).

2. Совершается ровно один запрос.
3. Совершается более одного запроса.

18. Процессоры Sun Enterprise 10000 работают с частотой 333 МГц, а отслежи-

вающие шины — с частотой 83,3 МГц. Если имеется 64 процессора, ясно, что
шины не справятся с такой нагрузкой. Тем не менее машина работает. Объяс-
ните, почему.

19. В этой книге мы вычислили, что производительности координатного ком-

мутатора было достаточно для обработки 167 млн отслеживаний/с, когда
к нему подсоединено 16 плат, причем мы даже принимаем во внимание тот
факт, что из-за конфликтных ситуаций на практике пропускная способность
составляет 60% от теоретической. Небольшая машина Enterprise 10000 может
содержать всего 4 платы (16 процессоров). Будет ли такая машина работать
с полной скоростью?

20. Предположим, что провод между коммутатором 2 А и коммутатором ЗВ в сети

Omega поврежден. Какие именно элементы будут отрезаны друг от друга?

21. Области памяти, к которым часто происходят обращения, представляют

большую проблему в многоступенчатых сетях. А являются ли они пробле-
мой в системах с шинной организацией?

22. Сеть Omega соединяет 4096 процессоров RISC, время цикла каждого из ко-

торых составляет 60 не, с 4096 бесконечно быстрыми модулями памяти. Каж-
дый переключательный элемент дает задержку 5 не. Сколько пустых цик-
лов требуется для команды LOAD?

23. Рассмотрим машину с сетью Omega (см. рис. 8.22). Предположим, что про-

грамма и стек i хранятся в модуле памяти i. Какое незначительное измене-
ние топологии может сильно повлиять на производительность? (IBM RP3 и
BBN Butterfly используют эту измененную топологию.) Какой недостаток
имеет новая топология по сравнению со старой?

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

24. В мультипроцессоре NUM А обращение к локальной памяти занимает 20 не,

а к памяти другого процессора — 120 не. Программа во время выполнения
совершает N обращений к памяти, 1% из которых — обращения к странице Р.
Изначально эта страница находится в удаленной памяти, а на копирование
ее из локальной памяти требуется С не. При каких обстоятельствах эту страни-
цу следует копировать локально, если ее не используют другие процессоры?

25. Система DASH содержит b байтов памяти, которые распределены между

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

26. Рассмотрим мультипроцессор CC-NUMA (см. рис. 8.24), содержащий

512 узлов по 8 Мбайт каждый. Если длина строки кэш-памяти составляет
64 байта, каков процент непроизводительных затрат для каталогов? Как
повлияет увеличение числа узлов на непроизводительные затраты (они уве-

личатся, уменьшатся или останутся без изменений)?

27. На какую операцию в SCI требуется больше всего времени?
28. Мультипроцессор на базе SCI содержит 63 узла. Длина строки кэш-памяти

составляет 32 байта, а общее адресное пространство составляет 2

32

 байтов.

Размер кэш-памяти в каждом узле — 1 Мбайт. Сколько байтов нужно иметь
в каждом кэш-каталоге?

29. Машина NUMA-Q 2000 содержит 63 узла. Предложите ввести 64 узла вме-

сто 63. Почему компания Sequent в качестве максимума выбрала именно 63,
а не 64?

30. В этой книге мы обсуждали 3 варианта примитива send — синхронный, бло-

кирующий и неблокирующий. Предложите четвертый метод, который схож
с блокирующей операцией send, но немного отличается по свойствам. Какое
преимущество и какой недостаток имеет новый метод по сравнению с обыч-
ной блокирующей операцией send?

31. Рассмотрим компьютер, который работает в сети с аппаратным широкове-

щанием (например, Ethernet). Почему важно соотношение операций чте-
ния (которые не изменяют внутреннее состояние переменных) и операций
записи (которые изменяют внутреннее состояние переменных)?

32. Многие вопросы, возникающие при разработке мультипроцессоров, возни-

кают также при разработке совместно используемой памяти на прикладном
уровне. Один из таких вопросов — выбор одной из двух политик: обновле-
ние или объявление недействительным. Какая политика используется в си-
стеме Огса?

Глава 9

Библиография

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

Литература для дальнейшего чтения

Вводная и неспециальная литература

1. Hamacher et al.,

 Computer Organization,

 4th ed.

Традиционный учебник об организации компьютеров (процессоры, память,
ввод-вывод, арифметика, периферийные устройства). Основные примеры —
68000 и Power PC.

2. Hayes,

 Computer Architecture and Organization,

 3rd ed.

Еще одна традиционная книга о компьютерной организации с уклоном к ап-

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

3. Patterson and Hennessy,

 Computer Organization and Design.

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

4. Price,

 A History of Calculating Machines.

Современные компьютеры восходят к машине Бэббиджа, созданной в XIX веке,

но люди производили различные вычисления с самого начала цивилизации.
В этой иллюстрированной статье прослеживается вся история счета, мате-
матики, календарей и вычислений с 3000 г. до н. э. до начала XX века.