Танненбаум Е. Архітектура компютера [pdf]
.pdf
Мультипроцессоры с памятью совместного использования |
6 |
1 М строк, в каталоге содержится 1 М элементов, по одному элементу на кажд строку. Каждый элемент содержит битовое отображение по одному биту на класт Этот бит показывает, имеется ли в данный момент строка данного кластера в кэ памяти. Кроме того, элементсодержит 2-битное поле, которое сообщаето состоян строки.
1 М элементов по 18 битов каждый означает, что общий размер каждого ка лога превышает 2 Мбайт. При наличии 16 кластеров вся память каталога буд немного превышать 36 Мбайт, что составляет около 14% от 256 Мбайт. Если чи ло процессоров на кластер возрастает, объем памяти каталога не меняется. Бол шое число процессоров на каждый кластер позволяет погашать стоимость памя каталога, а также контроллера шины при наличии большого числа процессоро сокращая стоимость на каждый процессор. Именно поэтому каждый кластер им ет несколько процессоров.
Каждый кластер в DASH связан с интерфейсом, который дает возможнос кластеру обмениваться информацией с другими кластерами. Интерфейсы связан через межкластерные каналы в прямоугольную решетку, как показано нарис. 8.25 Чем больше добавляется кластеров в систему, тем больше нужно добавлять ме кластерных каналов, поэтому пропускная способность системы возрастает. В си теме используется маршрутизация «червоточина», поэтому первая часть паке может быть направлена дальше еще до того, как получен весь пакет, что сокраща задержку в каждом транзитном участке. Существует два набора межкластерн каналов: один — для запрашивающих пакетов, а другой — для ответных пакет (на рисунке это не показано). Межкластерные каналы нельзя отслеживать.
Каждая строка кэш-памяти может находиться в одном из трех следующих с стояний:
1.UNCACHED (некэшированная) — строка находится только в памяти.
2.SHARED (совместно используемая) — память содержит новейшие данны строка может находиться в нескольких блоках кэш-памяти.
3.MODIFIED(измененная) —строка,содержащаясявпамяти,неправильна данная строка находится только в одной кэш-памяти.
Состояние каждой строки кэш-памяти содержится в поле Состояние в соотве ствующем элементе каталога, как показано на рис. 8.25, б.
Протоколы DASH основаны на обладании и признании недействительност В каждый момент у каждой строки имеется уникальный владелец. Для строк в с стоянии UNCHANGED или SHARED владельцем является собственный класт данной строки. Для строк в состоянии MODIFIED владельцем является тот кла тер, в котором содержится единственная копия этой строки. Прежде чем записа что-либо в строку в состоянии SHARED, нужно найти и объявить недействител ными все существующие копии.
Чтобы понять, как работает этот механизм, рассмотрим, как процессор счит
6 1 4 Глава 8. Архитектуры компьютеров параллельного действия
дится в состоянии MODIFIED, нужно проинформировать исходный ката строка теперь SHARED. В любом случае слово берется из какой-то кэшно это не влияет на битовое отображение каталогов (поскольку каталог со 1 бит на кластер, а не 1 бит на каждый процессор).
Если нужная строка не присутствует ни в одной кэш-памяти данного к то пакет с запросом отправляется в исходный кластер, содержащий данну ку. Этот кластер определяется по 4 старшим битам адреса памяти, и им может оказаться кластер запрашивающей стороны. В этом случае соо физически не посылается. Аппаратное обеспечение в исходном класте веряет свои таблицы и выясняет, в каком состоянии находится строка. Е UNCACHED или SHARED, аппаратное обеспечение, которое управляет гом, вызывает эту строку из глобальной памяти и посылает ее обратно в за вающий кластер. Затем аппаратное обеспечение обновляет свой каталог, данную строку как сохраненную в кэш-памяти кластера запрашивающей с
Если нужная строка находится в состоянии MODIFIED, аппаратное об ние находит кластер, который содержит эту строку, и посылает запрос туд кластер, который содержит данную строку, посылает ее в запрашивающий и помечает ее копию как SHARED, поскольку теперь эта строка находит чем в одной кэш-памяти. Он также посылает копию обратно в исходный чтобы обновить память и изменить состояние строки на SHARED.
Запись происходит по-другому. Перед тем как осуществить запись, пр должен убедиться, что он является единственным обладателем данной стро памяти в системе. Если в кэш-памяти данного процессора уже есть эта с она находится в состоянии MODIFIED, то запись можно осуществить с Если строка в кэш-памяти есть, но она находится в состоянии SHARED, т ла в исходный кластер посылается пакет, чтобы объявить все остальны недействительными.
Если нужной строки нет в кэш-памяти данного процессора, этот проце сылает запрос на локальную шину, чтобы узнать, нет ли этой строки в с процессорах. Если данная строка там есть, то она передается из одной кэш в другую. Если эта строка SHARED, то все остальные копии должны быт лены недействительными.
Если строка находится где-либо еще, пакет посылается в исходный Здесь может быть три варианта. Если строка находится в состоянии UNCA она помечается как MODIFIED и отправляется к запрашивающему про Если строка находится в состоянии SHARED, все копии объявляются нед тельными, и после этого над строкой совершается та же процедура, чт UNCASHED строкой. Если строка находится в состоянии MODIFIED ( на), то запрос направляется в тот кластер, в котором строка содержится в момент. Этот кластер удовлетворяет запрос, а затем объявляет недействи свою собственную копию.
6 1 6 Глава 8. Архитектуры компьютеров параллельного действия
плата IQ-Link, соединяет все платы quad board в один мультипроцессор. ная задача — реализовать протокол SCI. Каждая плата IQ-Link содержит 32 кэш-памяти, каталог, который следит за тем, что находится в кэш-памяти фейс с локальной шиной платы quad board и микросхему, называемую и ционным ядром, соединяющую плату IQ-Link с другими платами IQ-Li микросхема подкачивает данные от входа к выходу, сохраняя те данные, направляются в данный узел, и передавая все прочие данные далее без изм
Все платы IQ-Link в совокупности формируют кольцо, как показано на р В данной разработке присутствует два уровня протокола когерентности к вания. Протокол SCI поддерживает непротиворечивость всех кэшей платы I используя это кольцо. Протокол MESI используется для сохранения непро чивости между четырьмя процессорами и кэш-памятью на 32 Мбайт в кажд
В качестве связи между платами quad board используется интерфейс S интерфейс был разработан для того, чтобы заменить шину в больших мул цессорах и мультикомпьютерах (например, NUMA-Q). SCI поддерживает н воречивость кэшей, которая необходима в мультипроцессорах, а также по быстро передавать блоки, что необходимо в мультикомпьютерах. SCI выд ет нагрузку до 64 К узлов, адресное пространство каждого из которых мож до 248 байтов. Самая большая система NUMA-Q состоит из 63 плат quad bo торые содержат 252 процессора и почти 238 байтов физической памяти. Как возможности SCI гораздо выше.
Кольцо, которое соединяет платы IQ-Link, соответствует протоколу SCI ствительности это вообще не кольцо, а отдельные двухточечные кабели. кабеля составляет 18 битов: 1 бит синхронизации, 1 флаговый бит и 1 данных. Все они передаются параллельно. Каналы синхронизируются с т частотой 500 МГц, при этом скорость передачи данных составляет 1 Г По каналам передаются пакеты. Каждый пакет содержит заголовок из 14 ба 16, 64 или 256 байтов данных и контрольную сумму на 2 байта. Трафик из запросов и ответов.
Физическая память в машине NUMA-Q 2000 распределена по узлам, каждая страница памяти имеет свою собственную машину. Каждая плата qu может вмещать до 4 Гбайт ОЗУ. Размер строки кэш-памяти равен 64 байт этому каждая плата quad board содержит 226 строк кэш-памяти. Когда ст используется, она находится только в одном месте — в собственной памят
Однако строки могут находиться в нескольких разных кэшах, поэтому д дого узла должна существовать таблица локальной памяти из 226 элемен которой можно находить местоположение строк. Один из возможных вариа иметь на каждый элемент таблицы битовое отображение, которое показыв кие платы IQ-Link содержат эту строку. Но в SCI не используется такое отображение, поскольку оно плохо расширяется. (Напомним, что SCI мо держивать нагрузку до 64 К узлов, и иметь 226 элементов по 64 К битов было бы слишком накладно.)
Мультипроцессоры с памятью совместного использования
для больших систем гораздо лучше, чем битовое отображение. Именно это ство делает SCI более расширяемой по сравнению с системой DASH.
Кроме таблицы локальной памяти, каждая плата IQ-Link содержит ка с одним элементом для каждой строки кэш-памяти, которую плата в да момент содержит. Поскольку размер кэш-памяти составляет 32 Мбайт, а ст кэш-памяти включает 64 байта, каждая плата IQ-Link может содержать до 219 с кэш-памяти. Поэтому каждый каталог содержит 21Э элементов, по одному эле ту на каждую строку кэш-памяти.
Если строка находится только в одной кэш-памяти, то тот узел, в котором дится строка, указывается в таблице локальной памяти исходного узла. Если этого данная строка появится в кэш-памяти другого узла, то в соответствии с н протоколом исходный каталог будет указывать на новый элемент, который, в очередь, указывает на старый элемент. Таким образом формируется двухэле ный список. Все новые узлы, содержащие ту же строку, прибавляются к н списка. Следовательно, все узлы, которые содержат эту строку, связываются в с угодно длинный список. На рис. 8.27 проиллюстрирован этот процесс (в да случае строка кэш-памяти содержится в узлах 4, 9 и 22).
Таблица локальной памяти в узле
Каталог кэш-памяти узла 4 Каталог кэш-памяти узла 9 Каталог кэш-памяти уз
Рис. 8.27. Протокол SCI соединяет всехдержателей данной строки в дважды связанн список. Вданном примерестроканаходитсяодновременновтрехузлах
6 1 8 Глава 8. Архитектуры компьютеров параллельного действия
Последние 13 битов — это тег (нужен для идентификации строки). Нап что самая большая система NUMA-Q2000 содержит 63х232=238 байтов О этому имеется почти 232 строк кэш-памяти. Все кэши прямого отображен этому 232 строк отображаются на 219 элементов кэш-памяти, существует 21 которые отображаются на каждый элемент. Следовательно, 13-битный те для того, чтобы показывать, какая именно строка находится там в данный
Каждая строка имеет фиксированную позицию только в одном блоке (исходном). Эти строки могут находиться в одном из трех состояний: UNCA (некэшированном), SHARED (совместногоиспользования) и MODIFIED ненном). В протоколе SCI эти состояния называются HOME, FRESH и соответственно, но мы во избежание путаницы будем использовать прежн минологию. Состояние UNCACHED означает, что строка не содержится ном из кэшей на плате IQ-Link, хотя она может находиться в локальной кэш ти на той же самой плате quad board. Состояние SHARED означает, что находится по крайней мере в одной кэш-памяти платы IQ-Link, а память жит обновленные данные. Состояние MODIFIED означает, что строка на в кэш-памяти на какой-то плате IQ-Link, но, возможно, эта строка была из поэтому память может содержать устаревшие данные.
Блоки кэш-памяти могут находиться в одном из 29 устойчивых состоян
водном из переходных состояний (их более 29). Для записи состояния строки необходимо 7 битов (рис. 8.27). Каждое устойчивое состояние пока ся двумя полями. Первое поле указывает, где находится строка — в начале
вконце, в середине или вообще является единственным элементом списка. поле содержит информацию о том, изменялась ли строка, находится ли она
вэтой кэш-памяти и т. п.
Впротоколе SCI определены 3 операции со списком: добавление узла к удаление узла из списка и очистка всех узлов кроме одного. Последняя оп нужна в том случае, если разделяемая строка изменена и становится единст
Протокол SCI имеет три варианта сложности. Протокол минимальной ни сложности разрешает иметь только одну копию каждой строки в кэш- (см. рис. 8.24). В соответствии с протоколом средней степени сложности строка может кэшироваться в неограниченном количестве узлов. Полный пр включает различные особенности для увеличения производительности. В NUMA-Q используется протокол средней степени сложности, поэтому н рассмотрим именно его.
Разберемся, как обрабатывается команда READ. Если процессор, выполн эту команду, не может найти нужную строку на своей плате, то плата IQ-L сылает пакет исходной плате IQ-Link, которая затем смотрит на состоян строки. Еслисостояние UNCACHED,онопревращаетсявSHARED,инужн ка берется из основной памяти. Затем таблица локальной памяти в исходн обновляется. После этого таблица содержит одноэлементный список, ука
щий на узел, в кэш-памяти которого в данный момент находится строка.
Мультипроцессоры с памятью совместного использования |
6 |
Представим теперь, что требуемая строка находится в состоянии MODIFIE Исходный каталог не может вызвать эту строку из памяти, поскольку в памя содержится недействительная копия. Вместо этого исходный каталог сообща запрашивающей плате IQ-Link, в какой кэш-памяти находится нужная строка, отдает приказ вызвать строку оттуда. Каталог также изменяет элемент таблиц локальной памяти, поскольку теперь он должен указывать на новое местополож ние строки.
Обработка команды WRITE происходит немного по-другому. Если запрашива щий узел уже находится в списке, он должен удалять все остальные элементы, чт бы остаться в списке единственным. Если его нет в списке, он должен удалить в элементы, а затем войти в список в качестве единственного элемента. В люб случае в конце концов этот элемент остается единственным в списке, а исходн каталог указывает на этот узел. В действительности обработка команд READ и WR довольно сложна, поскольку протокол должен работать правильно, даже если н сколько машин одновременно выполняют несовместимые операции на одной л нии. Все переходные состояния были введены именно для того, чтобы проток работал правильно даже во время одновременно выполняемых операций. В эт книге мы не можем изложить полное описание протокола. Если вам это необход мо, обратитесь к стандарту IEEE 1596.
Мультипроцессоры СОМА
Машины NUMA и CC-NUMA имеют один большой недостаток: обращения к уд ленной памяти происходят гораздо медленнее, чем обращения к локальной пам ти. В машине CC-NUMA эта разница в производительности в какой-то степе нейтрализуется благодаря использованию кэш-памяти. Однако если количест требуемых удаленных данных сильно превышает вместимость кэш-памяти, пр махи будут происходить постоянно и производительность станет очень низкой
Мы видим, что машины UMA, например Sun Enterprise 10000, имеют оче высокую производительность, но ограничены в размерах и довольно дорого сто Машины NUMA могут расширяться до больших размеров, но в них требуется ру ное или полуавтоматическое размещение страниц, а оно не всегда проходит удачн Дело в том, что очень трудно предсказать, где какие страницы могут понадобит ся, и кроме того, страницы трудно перемещать из-за большого размера. Маши CC-NUMA, например Sequent NUMA-Q, могут работать с очень низкой произв дительностью, если большому числу процессоров требуется много удаленных да ных. Так или иначе, каждая из этих разработок имеет существенные недостатк
Однако существует процессор, в котором все эти проблемы разрешаются за сч того, что основная память каждого процессора используется как кэш-память. Так разработка называется СОМА (Cache Only Memory Access). В ней страницы имеют собственных фиксированных машин, как в системах NUMA и CC-NUM
Вместо этого физическое адресное пространство делится на строки, котор
6 2 0 Глава 8. Архитектуры компьютеров параллельного действия
К сожалению, ничего идеального не бывает. В системе СОМА появляе новых проблемы:
1.Как размещаются строки кэш-памяти?
2.Если строка удаляется из памяти, что произойдет, если это последняя
Первая проблема связана со следующим фактом. Если блок управлени тью транслировал виртуальный адрес в физический и если строки нет в а ной кэш-памяти, то очень трудно определить, есть ли вообще эта строка в ной памяти. Аппаратное обеспечение здесь не поможет, поскольку каждая ст состоит из большого количества отдельных строк кэш-памяти, которые пер ются в системе независимо друг от друга. Даже если известно, что строка ствует в основной памяти, как определить, где она находится? В данном нельзя спросить об этом собственную машину, поскольку таковой машины теме нет.
Было предложено несколько решений этой проблемы. Можно ввести аппаратное обеспечение, которое будет следить за тегом каждой строки кэш ти. Тогда блок управления памятью может сравнивать тег нужной строки с всех строк кэш-памяти, пока не обнаружит совпадение.
Другое решение — отображать страницы полностью, но при этом не тр присутствия всех строк кэш-памяти. В этом случае аппаратному обеспечен надобится битовое отображение для каждой страницы, где один бит для строки указывает на присутствие или отсутствие этой строки. Если стро сутствует, она должна находиться в правильной позиции на этой страниц она отсутствует, то любая попытка использовать ее вызовет прерывание, зволит программному обеспечению найти нужную строку и ввести ее.
Таким образом, система будет искать только те строки, которые действи находятся в удаленной памяти. Одно из решений — предоставить каждой с це собственную машину (ту, которая содержит элемент каталога данной стр а не ту, в которой находятся данные). Затем можно отправить сообщение ственную машину, чтобы найти местоположениеданной строки. Другое реш организовать память в виде дерева и осуществлять поиск по направлению пока не будет обнаружена требующаяся строка.
Вторая проблема связана с удалением последней копии. Как и в маши NUMA, строка кэш-памяти может находиться одновременно в нескольки Если происходит промах кэша, строку нужно откуда-то вызвать, а это знач ее нужно отбросить. А что произойдет, если выбранная строка окажется ней копией? В этом случае ее нельзя отбрасывать.
Одно из возможных решений — вернуться к каталогу и проверить, суще ли другие копии. Если да, то строку можно смело выбрасывать. Если не нужно переместить куда-либо еще. Другое решение — пометить одну из коп дой строки кэш-памяти как главную копию и никогда ее не выбрасывать. Пр
Мультикомпьютеры с передачей сообщений
Мультикомпьютеры с передачей сообщен
Как видно из схемы на рис. 8.12, существует два типа параллельных процессо MIMD: мультипроцессоры и мультикомпьютеры. В предыдущем разделе мы сматривали мультипроцессоры. Мы увидели, что мультипроцессоры могут и разделенную память, доступ к которой можно получить с помощью обычных манд LOAD и STORE. Такая память реализуется разными способами, включая от живающие шины, многоступенчатые сети, а также различные схемы на осн каталога. Программы, написанные для мультипроцессора, могут получать до к любому месту в памяти, не имея никакой информации о внутренней тополо или схеме реализации. Именно благодаря такой иллюзии мультипроцессоры вес популярны.
Однако мультипроцессоры имеют и некоторые недостатки, поэтому мул компьютеры тоже очень важны. Во-первых, мультипроцессоры нельзя расшир до больших размеров. Чтобы расширить машину Interprise 10000 до 64 проце ров, пришлось добавить огромное количество аппаратного обеспечения.
В Sequent NUMA-Q дошли до 256 процессоров, но ценой неодинако времени доступа к памяти. Ниже мы рассмотрим два мультикомпьютера, кото содержат 2048 и 9152 процессора соответственно. Через много лет кто-нибудь ск струирует мультипроцессор, содержащий 9000 узлов, но к тому времени мул компьютеры будут содержать уже 100 000 узлов.
Кроме того, конфликтная ситуация при обращении к памяти в мультипро соре может сильно повлиять на производительность. Если 100 процессоров по янно пытаются считывать и записывать одни и те же переменные, конфликт ситуация для различных модулей памяти, шин и каталогов может сильно удар по производительности.
Вследствие этих и других факторов разработчики проявляют огромный и рес к параллельным компьютерам, в которых каждый процессор имеет свою ственную память, к которой другие процессоры не могут получить прямой дос Это мультикомпьютеры. Программы на разных процессорах в мультикомпью взаимодействуют друг с другом с помощью примитивов send и receive, кото используются для передачи сообщений (поскольку они не могут получить дос к памятидругих процессоров с помощью команд LOADи STORE). Эторазличие пол стью меняет модель программирования.
Каждый узел в мультикомпьютере состоит из одного или нескольких про соров, ОЗУ (общее для процессоров только данного узла), диска и(или) дру устройств ввода-вывода, а также процессора передачи данных. Процессоры п дачи данных связаны между собой по высокоскоростной коммуникационной с
(см. раздел «Сети межсоединений»). Используется множество различных топо
6 2 2 Глава 8. Архитектуры компьютеров параллельного действия
Процессор |
Память |
Узел |
|
|
|
|
|
|
|||
|
Р |
|
Диск |
Р-РР |
Диск |
Локальная |
—| и устройства |
Локальная |
—| и устрой |
||
коммуникация |
коммуникация |
||||
|
|
|
ввода-вывода |
|
ввода-вы |
Процессор
передачиданных
Высокоскоростная коммуникационная сеть
Рис. 8.28. Схемамультикомпьютера
Мультикомпьютеры бывают разных типов и размеров, поэтому очень привести хорошую классификацию. Тем не менее можно назвать два общи МРР и COW. Ниже мы рассмотрим каждый из этих типов.
МРР — процессоры с массовым параллелизм
МРР (Massively Parallel Processors — процессоры с массовым параллелиз это огромные суперкомпьютеры стоимостью несколько миллионов долларо используются в различных науках и промышленности для выполнения сл вычислений, для обработки большого числа транзакций в секунду или для ния больших баз данных и управления ими.
В большинстве таких машин используются стандартные процессоры. Э гут быть процессоры Intel Pentium, Sun UltraSPARC, IBM RS/6000 и DEC Отличает мультикомпьютеры то, что в них используется сеть, по которой передавать сообщения, с низким временем ожидания и высокой пропускн собностью. Обе характеристики очень важны, поскольку большинство сооб малы по размеру (менее 256 байтов), но при этом суммарная нагрузка в б степени зависит от длинных сообщений (более 8 Кбайт).
Еще одна характеристика МРР — огромная производительность процес да-вывода. Часто приходится обрабатывать огромные массивы данных, ин рабайты. Эти данные должны быть распределены по дискам, и их нужно п щать в машине с большой скоростью.
Следующая специфическая черта МРР — отказоустойчивость. При нали одной тысячи процессоров несколько неисправностей в неделю неизбежн кращать работу системы из-за неполадок в одном из процессоров было бы
