совместно используют общую основную память, и мультикомпьютеры, которы не используют общую основную память. Системы обоих типов состоят из процес соров и модулей памяти, связанных друг с другом различными высокоскоростны ми сетями, по которым между процессорами и модулями памяти передаются паке ты запросов и ответов. Применяются различные топологии, в том числе решетки торы, кольца и гиперкубы.
Для всех мультипроцессоров ключевым вопросом является модель согласо ванности памяти. Из наиболее распространенных моделей можно назвать согла сованность по последовательности, процессорную согласованность, слабую со гласованность и свободную согласованность. Мультипроцессоры можно строить с использованием отслеживающей шины, например, в соответствии с протоколом 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, определите степень отказо устойчивости. Отказоустойчивость — максимальное число каналов связи
6 4 4 Глава 8. Архитектуры компьютеров параллельного действия
5.Представим сеть в форме куба 8x8x8. Каждый канал связи имеет д ную пропускную способность 1 Гбайт/с. Какова бисекционная про способность этой сети?
6.Рассмотрим сеть в форме прямоугольной решетки размером 4 комм в ширину и 3 коммутатора в высоту. В ней пакеты, исходящие из верхнего угла и направляющиеся в правый нижний угол, могут сл по любому из нескольких возможных путей. Пронумеруйте верхн коммутаторов с 1 по 4, следующий ряд — с 5 по 8, а нижний — с Выпишете все пути, по которым пакеты перемещаются только впр вниз, начиная с коммутатора 1 и заканчивая коммутатором 12.
7.Закон Амдала ограничивает потенциальный коэффициент ускорен стижимый в компьютере параллельного действия. Вычислите как ф от f максимально возможный коэффициент ускорения, если число соров стремится к бесконечности. Каково значение этого предела дл
8.Нарисунке 8.10 показано,чторасширениеневозможносшиной, но во
срешеткой. Каждая шина или канал связи имеет пропускную способ Вычислите среднюю пропускную способность на каждый процес каждого из четырех случаев. Затем расширьте каждую систему до цессоров и выполните те же вычисления. Чему равен предел, есл процессоров стремится к бесконечности?
9.Компьютерная компания выпускает системы, состоящие из п комп
ссовместно используемой памятью, организованных в квадратную ку. Однажды вице-президенту компании приходит в голову идея вы новый продукт: трехмерную решетку, в которой п компьютеров орга ны в правильный куб (это возможно, например, для п=4096).
1. Как это изменение повлияет на максимальное время ожидания?
2. Как это изменение повлияет на общую пропускную способность
10.Когда мы говорили о согласованности памяти, мы сказали, что мо гласованности — это вид контракта между программным обеспече памятью. Зачем нужен такой контракт?
11.Векторный процессор (например, Cray-1) содержит арифметические ства с конвейерами из четырех стадий. Прохождение каждой стади мает 1 не. Сколько времени понадобится для сложения двух векторов элементов?
12.Рассмотрим мультипроцессор с общей шиной. Что произойдет, е процессора попытаются получить доступ к глобальной памяти в оди же момент?
13.Предположим, что по техническим причинам отслеживающий кэш отслеживать только адресные линии и не может отслеживать инфо
Вопросы и задания
64
время выполнения команды. Если шина занята, то запрашивающий про цессор становится в очередь «первым вошел — первым вышел». Наскольк быстрее будет работать система с 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?
6 4 6 Глава 8. Архитектуры компьютеров параллельного действия
24.В мультипроцессореNUMА обращение к локальной памяти занимае
ак памяти другого процессора — 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 в качестве максимума выбрала име
ане 64?
30.В этой книге мы обсуждали 3 варианта примитива send — синхронны кирующий и неблокирующий. Предложите четвертый метод, которы с блокирующей операцией send, но немного отличается по свойствам. преимущество и какой недостаток имеет новый метод по сравнению с ной блокирующей операцией send?
31.Рассмотрим компьютер, который работает в сети с аппаратным шир щанием (например, Ethernet). Почему важно соотношение операц ния (которые не изменяют внутреннее состояние переменных) и оп записи (которые изменяют внутреннее состояние переменных)?
32.Многие вопросы, возникающие при разработке мультипроцессоров, кают также при разработке совместно используемой памяти на прик уровне. Один из таких вопросов — выбор одной из двух политик: об ние или объявление недействительным. Какая политика используетс стеме Огса?
Глава 9
Библиография
Впредыдущих главах мы с разной степенью подробности обсуждали достаточн широкий ряд вопросов. Эта глава предназначена для читателей, которые заин тересованы в более глубоком изучении строения компьютеров. В разделе «Лите ратура для дальнейшего чтения» содержится список литературы к каждой главе
Вразделе «Алфавитный список литературы» приводится алфавитный список все книг и статей, на которые мы ссылались в этой книге.
Литература для дальнейшего чтения
Вводная и неспециальная литература
1. Hamacheretal., ComputerOrganization, 4thed.
Традиционный учебник об организации компьютеров (процессоры, память ввод-вывод, арифметика, периферийные устройства). Основные примеры — 68000 и Power PC.
Еще одна традиционная книга о компьютерной организации с уклоном к аппаратному обеспечению. В книге рассматриваются процессоры, тракт данных, микропрограммирование, конвейеры, организация памяти и процесс ввода-вывода.
Эта книга почти на 1000 страниц содержит обширный материал о компью терной архитектуре, в частности о разработке процессоров RISC. Упор делается на то, как достичь высокой производительности с помощью конвейе-
ризации и других технологий.
648Глава 9. Библиография
5.Slater, Portraitsin Silicon.
Почему Деннис Ритчи защитил докторскую диссертацию в Гарвард чему Стив Джобе стал вегетарианцем? Ответы на эти и другие вопр можете найти в этой увлекательной книге. Книга содержит 34 коротк графии людей, которые сформировали компьютерную промышленн Чарльза Бэббиджа до Дональда Кнута).
Книга по компьютерной архитектуре. В ней рассматриваются и те во которые мы обсуждали в нашей книге.
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.
Если вы умеете обращаться с отверткой и паяльником и хотите ско
Литература для дальнейшего чтения
64
Цифровой логический уровень
1. Floyd,DigitalFundamentals, 6thed.
Эта огромная иллюстрированная книга вполне подойдет для тех, кто хоч более подробно изучить цифровой логический уровень. В ней рассказыв ется о комбинационных логических схемах, программируемых логически устройствах, триггерах, сдвиговых регистрах, о памяти, интерфейсах и мн гом другом.
2. Katayama, TrendsinSemiconductorMemory.
Хотя память работает гораздо медленнее процессоров, полупроводников память все же развивается. В этой статье рассказывается о некоторых те денциях развития динамического ОЗУ.
Эта книга не обладает такой проработанностью и ясностью, как книга Флой (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.
Эта книга имеет отношение и к аппаратному, и к программному обеспеч нию, а также к интерфейсам. В ней рассказывается все о процессорах, пам ти, устройствах ввода-вывода и о сопряжении микросхем компьютера 80x8 а также о том, как их программировать на языке ассемблера. В ней всего 9 страниц, но она содержит столько же материала, как и книга Мессмера, п скольку страницы здесь больше по размеру.
Микроархитектурный уровень
650 Глава 9. Библиография
объединенная и разделенная кэш-память, а также некоторые вопро граммного обеспечения. Целая глава посвящена когерентности кэш в мультипроцессоре.
2.Johnson,SuperscalarMicroprocessorDesign.
Если вы интересуетесь подробностями разработки суперскалярн цессоров, вам нужно начать именно с этой книги. В ней рассказы вызове и декодировании команд, о выдаче команд с изменением пос тельности, переименованиирегистров, резервациях, прогнозирован ходов и о многом другом.
UltraSPARC Iii — это версия UltraSPARC II с шиной PCI. В этом тр работчики рассказывают о том, как работает эта система.
4. McChan and О' Connor, picojava: A Direct Execution Engine for Java B
Эта статья представляет собой краткое введение в микроархитектуру (и следовательно, микросхемы microjava 701). В ней дана блок-сх суждаются вопросы конвейеризации и рассказывается о различны бах оптимизации.
Эта книга хорошо подходит для детального изучения современного сора на микроархитектурном уровне. Подробно описывается мик AMD Кб (клон Pentium). Рассказывается о конвейерах, планирова полнения команд и о способах повышения производительности.
6. Sima,SuperscalarInstructionIssue.
Суперскалярная подача команд чрезвычайно важна в современн цессорах. В этой книге мы затронули некоторые вопросы, связанны (в частности, переименование и спекулятивное выполнение). В ста сматриваются эти и многие другие вопросы.
7.Wilson,ChallengesandTrendsinProcessorDesign.
Неужели разработка процессоров не продвигается? Шесть ведущи ботчиков процессоров из компаний Sun, Cyrix, Motorola, Mips, Intel рассказывают о перспективах развития процессоров в следующие н ко лет. В 2008 году читать это будет смешно, но в настоящее время прочитать.
Удивительно, но эта книга по программированию на языке ассемблера посвящена вовсе не серии 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. И тем не менее ее стоит прочитать. Из этого маленького зернышка выросла большая операци онная система.
Большинство книг об операционных системах касаются только теор ких вопросов. В этой книге теория проиллюстрирована на примере ре программного кода операционной системы MINIX, сходной с UNI рая работает на IBM PC и других компьютерах. Исходный код с под ми комментариями приводится в приложении.
Тема этой книги — программирование процессоров Intel на языке ас ра. В ней также рассказывается о программировании ввода-вывода, сах, файлах, связывании, прерываниях и т. д.
2. Saloman,AssemblersandLoaders.
Все, что вы хотели знать об однопроходных и двупроходных ассемб также о том, как работают компоновщики и загрузчики, макросы и у компоновкапрограммы.
Во многих современных компьютерах, особенно мультипроцессор держивается более слабая модель памяти, чем согласованность по п вательности. В этом учебном пособии обсуждаются различные м объясняется, как они работают. Здесь также приводятся и опрове многочисленные мифы о слабо согласованной памяти.
Вэтой книге рассказывается о параллельной вычислительной обр
втом числе о сетях, архитектуре, компиляторах, моделях и прило
Вней представлены проблемы аппаратного и программного обесп а также прикладные вопросы.
3.Hill, Multiprocessors Should Support Simple Memory-Consistency Mo
Слабые модели памяти — важная и спорная проблема в разработке мультипроцессора. Слабые модели допускают определенные опт ции аппаратного обеспечения (например, совершение обращений к в другом порядке), но усложняют программирование. В этой стать обсуждает различные вопросы, связанные с согласованностью памяти