Архитектура компьютера - Таненбаум Э

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

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 байта, а общее адресное пространство составляет 232 байтов. Размер кэш-памяти в каждом узле — 1 Мбайт. Сколько байтов нужно иметь

вкаждом кэш-каталоге?

29.Машина NUMA-Q 2000 содержит 63 узла. Предложите ввести 64 узла вместо 63. Почему компания Sequent в качестве максимума выбрала именно 63,

ане 64?

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

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

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

Глава 9

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

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

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

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

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

1. Hamacheretal., ComputerOrganization, 4thed.

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

2.Hayes,ComputerArchitectureandOrganization,3rded.

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

3. Pattersonand Hennessy, ComputerOrganizationandDesign.

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

4. Price, A History ofCalculatingMachines.

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

648Глава 9. Библиография

5.Slater, Portraitsin Silicon.

Почему Деннис Ритчи защитил докторскую диссертацию в Гарварде? Почему Стив Джобе стал вегетарианцем? Ответы на эти и другие вопросы вы можете найти в этой увлекательной книге. Книга содержит 34 короткие биографии людей, которые сформировали компьютерную промышленность (от Чарльза Бэббиджа до Дональда Кнута).

6.Stallings,ComputerOrganizationandArchirecture,4thed.

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

7. Wilkes, Computers Then andNow.

Автор книги Морис Уилкс, один из первых компьютерных разработчиков и изобретатель микропрограммирования, излагает историю компьютеров с 1946 по 1968 год. Он рассказывает о войне между приверженцами автоматического программирования («space cadets») и традиционалистами, которые предпочитали программировать в восьмеричной системе.

Организация компьютерных систем

1.Ng,AdvancesinDiskTechnology:PerformanceIssues.

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

2.Messmer,TheIndispensablePCHardwareBook,3rded.

Толстая книга на 1384 страницы (36 глав и 13 приложений). Здесь очень подробно описываются процессоры 80x86, память, шины, вспомогательные микросхемы и периферийные устройства. Если вы уже прочитали книгу Нортона и Гудмэна (см. ниже) и хотите получить более подробную информацию, обратитесь к этой работе.

3. Norton and Goodman, Inside the PC, 7th ed.

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

4. Pilgrim, Build Your Own Pentium IIPC.

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

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

649

Цифровой логический уровень

1. Floyd,DigitalFundamentals, 6thed.

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

2. Katayama, TrendsinSemiconductorMemory.

Хотя память работает гораздо медленнее процессоров, полупроводниковая память все же развивается. В этой статье рассказывается о некоторых тенденциях развития динамического ОЗУ.

3. ManoandKime,LogicandComputerDesignFundamentals.

Эта книга не обладает такой проработанностью и ясностью, как книга Флойда (Floyd), но тоже является неплохим пособием по цифровому логическому уровню. В ней содержится информация о комбинационных и последовательных схемах, регистрах, памяти, процессорах и устройствах ввода-вывода.

4. Mazidi and Mazidi, The 80x86 IBMPCand Compatible Computers, 2nd ed.

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

5. McKee et al., SmarterMemory:ImprovingBandwidthforStreamedReferences.

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

6. Nelson et al., DigitalLogicandCircuitAnalysisandDesign.

Еще одна всеобъемлющая книга по цифровой логике. В ней подробно рассказывается о последовательных и комбинационных схемах.

7. Triebel,The80386,80486andPentiumProcessor.

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

Микроархитектурный уровень

1. Handy, TheCacheMemoryBook,2nded.

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

650 Глава 9. Библиография

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

2.Johnson,SuperscalarMicroprocessorDesign.

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

3. Normoyleetal. UltraSPARCHi:ExpendingtheBoundariesofaSystemona Chip.

UltraSPARC Iii — это версия UltraSPARC II с шиной PCI. В этом труде разработчики рассказывают о том, как работает эта система.

4. McChan and О' Connor, picojava: A Direct Execution Engine for Java ByteCode.

Эта статья представляет собой краткое введение в микроархитектуру picojava (и следовательно, микросхемы microjava 701). В ней дана блок-схема, обсуждаются вопросы конвейеризации и рассказывается о различных способах оптимизации.

5. Shriverand Smith, TheAnatomyofaHigh-PerformanceMicroprocessor.

Эта книга хорошо подходит для детального изучения современного процессора на микроархитектурном уровне. Подробно описывается микросхема AMD Кб (клон Pentium). Рассказывается о конвейерах, планировании выполнения команд и о способах повышения производительности.

6. Sima,SuperscalarInstructionIssue.

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

7.Wilson,ChallengesandTrendsinProcessorDesign.

Неужели разработка процессоров не продвигается? Шесть ведущих разработчиков процессоров из компаний Sun, Cyrix, Motorola, Mips, Intel и Digital рассказывают о перспективах развития процессоров в следующие несколько лет. В 2008 году читать это будет смешно, но в настоящее время ее стоит прочитать.

Уровень команд

1. Antonakos,ThePentiumMicroprocessor.

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

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

651

2.Paul,SPARCArchitecture,AssemblyLanguage,Programming,andС

Удивительно, но эта книга по программированию на языке ассемблера посвящена вовсе не серии Intel 80x86. Здесь рассказывается о компьютере SPARC и о том, как программировать на нем.

3.Weaver and Germond, The SPARCArchitectureManual.

Всвязи с интернационализацией компьютерной промышленности стандарты приобретают особую важность. В этой книге дается определение Version 9 SPARC, а также подробно рассказывается о том, что представляет собой стандарт. В книге содержится много информации о том, как работают 64-битные процессоры SPARC.

Уровень операционной системы

1.Hart, Win32 System Programming.

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

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

2.Jacob and Mudge, VirtualMemory:Issues ofImplementation.

Хорошая книга о современной виртуальной памяти. В ней рассказывается о таблицах страниц и TLB на примере MIPS, Power PC и процессоров Pentium.

3. Korn,Porting UNIXto WindowsNT.

На первый взгляд может показаться, что переносить программы UNIX на NT легко, поскольку система NT содержит очень много системных вызовов. Однако практика показывает, что сделать это не так-то просто. Автор статьи рассказывает, почему возникают трудности.

4.McKusick et al., Design andImplementation ofthe 4.4 BSD OperatingSystem.

Вотличие от большинства книг по UNIX, эта начинается с фотографии четырех авторов на конференции USENIX Conference. Трое из них много написали о пакете BSD версии 4.4 и высококвалифицированы в этом вопросе.

Вкниге говорится о системных вызовах, процессах, о процессе ввода-выво- да. Целый раздел посвящен сетям.

5.Ritchie and Thompson, The UNIX Time-Sharing System.

Это самая первая работа, посвященная системе UNIX. И тем не менее ее стоит прочитать. Из этого маленького зернышка выросла большая операционная система.

6. Solomon,Inside WindowsNT, 2nd ed.

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

652 Глава 9. Библиография

7.TanenbaumandWoodhull,OperatingSystems:DesignandImplementation,2nded. Большинство книг об операционных системах касаются только теоретических вопросов. В этой книге теория проиллюстрирована на примере реального программного кода операционной системы MINIX, сходной с UNIX, которая работает на IBM PC и других компьютерах. Исходный код с подробными комментариями приводится в приложении.

Уровень языка ассемблера

1.Irvine,AssemblyLanguageforIntel-BasedComputers,3rded.

Тема этой книги — программирование процессоров Intel на языке ассемблера. В ней также рассказывается о программировании ввода-вывода, макросах, файлах, связывании, прерываниях и т. д.

2. Saloman,AssemblersandLoaders.

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

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

1. AdveandGharachorloo,SharedMemoryConsistencyModels:ATutorial.

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

2.Almasiand Gottlieb,HighlyParallelComputing, 2nded.

Вэтой книге рассказывается о параллельной вычислительной обработке,

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

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

3.Hill, Multiprocessors Should Support Simple Memory-Consistency Models.

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

4. HwangandXu,ScalableParallelComputing.

Авторы рассматривают и программное, и аппаратное обеспечение, поэтому им удалось дать всестороннее, но доступное описание параллельной вы-