Реклама:

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

UMA-мультипроцессоры в симметричных мультипроцессорных архитектурах

Рис. 8.21. Три варианта мультипроцессора на одной шине: без кэш-памяти (а); с кэш-памятью (б); с кэш-памятью и отдельными модулями локальной памяти (б)

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

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

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

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

Согласованность кэшей

Предположим, что память секвенциально состоятельна. Что происходит, когда процессор 1 содержит в своем кэше некую строку, а процессор 2 пытается считать слово, соответствующее той же строке кэша? При отсутствии специальных правил процессор 2 получит копию этой строки в свой кэш. В принципе двойное кэширование одной и той же строки вполне приемлемо. А теперь предположим, что процессор 1 изменяет строку, и сразу после этого процессор 2 считывает копию этой строки из своей кэш-памяти. В результате он получает устаревшие данные, нарушая контракт между программным обеспечением и памятью. Ни к чему хорошему для программы, выполняемой процессором 2, это не приведет.

Данная проблема, которая носит название проблемы согласованности кэшей, очень важна. Если ее не разрешить, нельзя будет использовать кэш-память, и число мультипроцессоров, подсоединенных к одной шине, придется сократить до двух-трех. Специалистами было предложено множество различных решений (см., например, [77, 159]). Хотя все эти алгоритмы, называемые протоколами согласования кэшей, в некоторых деталях различаются, все они не допускают одновременного появления разных версий одной и той же строки в двух или более кэшах.

Во всех решениях контроллер кэш-памяти разрабатывается так, чтобы кэш мог обеспечивать мониторинг запросов, идущих по шине от других процессоров и других кэшей, в каждом конкретном случае предпринимая те или иные действия. Указанное устройство получило название следящего кэша (snooping cache), поскольку кэш как бы "следит" за шиной. Набор правил, которым следуют кэш, процессоры и основная память, чтобы предотвратить появление различных версий данных в нескольких кэшах, и называют протоколом согласования кэшей. Единицей передачи и хранения для кэша является строка кэша. Обычно длина строки кэша составляет 32 или 64 байт.

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

Таблица 8.5. Сквозная запись (пустые графы означают, что никакого действия не происходит)

Действие

Локальный запрос

Удаленный запрос

Кэш-промах чтения

Вызов данных из памяти

 

Кэш-попадание чтения

Использование данных из локального кэша

 

Кэш-промах записи

Обновление данных в памяти

 

Кэш-попадание записи

Обновление кэша и памяти

Объявление элемента в кэше недействительным

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

Рассмотрим все эти действия снова, но теперь с позиции следящего кэша (крайняя правая колонка в табл. 8.5). Назовем кэш, который выполняет действия, кэшем 1, а следящий кэш - кэшем 2. Если происходит кэш-промах чтения кэша 1, кэш 1 обращается к шине, чтобы получить нужную строку из основной памяти. Кэш 2 видит это, но ничего не делает. Если же происходит кэш-попадание чтения кэша 1 (то есть нужная строка уже содержится в кэше 1), обращение к шине не выполняется, поэтому кэш 2 ничего не знает о кэш-попаданиях чтения кэша 1.

Процесс записи более интересен. Если процессор 1 записывает слово, кэш 1 обращается к шине как в случае кэш-промаха, так и в случае кэш-попадания. При любой записи кэш 2 проверяет наличие записываемого слова у себя. Если слово отсутствует, кэш 2 рассматривает это как кэш-промах удаленной памяти и ничего не делает. (Отметим, что, согласно табл. 8.5, кэш-промах удаленной памяти означает, что слово отсутствует в следящем кэше, а есть оно в кэше-инициаторе или нет, значения не имеет. Таким образом, один и тот же запрос может дать локальное кэш-попадание и кэш-промах для следящего кэша, и наоборот.)

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

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

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

Еще один вариант - загрузка следящего кэша при кэш-промахах записи. Такая загрузка никак не сказывается на правильности алгоритма; она влияет только на производительность. Возникает вопрос: какова вероятность, что только что записанное слово вскоре опять будет записано? Когда вероятность высока, можно говорить в пользу загрузки кэша при кэш-промахах записи (политика заполнения по записи). Когда вероятность мала, то в случае кэш-промаха записи лучше не обновлять кэш-память. Если данное слово вскоре должно быть считано, после кэш-промаха чтения оно все равно окажется загруженным, поэтому нет смысла загружать его при кэш-промахе записи.

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

Протокол MESI

Одним из популярных протоколов отложенной записи является протокол MESI (Invalid, Shared, Exclusive, Modified - недействительный, разделяемый, эксклюзивный, модифицированный), названный так по первым буквам четырех возможных состояний элементов кэша [159]. В его основе лежит более ранний протокол однократной записи [77]. Протокол MESI используется в Pentium 4 и других процессорах для слежения за шиной. В соответствии с этим протоколом каждый элемент кэша может находиться в одном из следующих четырех состояний:

+ недействительный - элемент кэша содержит недействительные данные;

+ разделяемый - элемент может храниться в нескольких кэшах, память обновлена;

+ эксклюзивный - элемент находится только в данном кэше (ни в каких других кэшах его нет), память обновлена;

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

При загрузке процессора все элементы кэша помечаются как недействительные. При первом считывании из основной памяти нужная строка вызывается в кэш данного процессора и помечается как эксклюзивная, поскольку это - единственная кэшированная копия (рис. 8.22, а). При последующих считываниях процессор использует эту строку, не обращаясь к шине. Другой процессор может вызвать ту же строку и поместить ее в кэш. В этом случае первый держатель строки (процессор 1) благодаря слежению узнает, что он уже не единственный держатель строки, и объявляет по шине, что у него копия. Обе копии помечаются как разделяемые (рис. 8.22, б). Другими словами, состояние "разделяемая" означает, что память обновлена, и строка после чтения находится в одном или нескольких кэшах. При последующих чтениях разделяемой строки процессор не использует шину и не меняет состояние строки.

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

Далее выясним, что происходит, когда эту строку считывает процессор 3. Процессор 2, который в данный момент является держателем строки, знает, что копия в памяти недействительна, поэтому он передает на шину сигнал о том, чтобы процессор 3 ждал, пока он запишет строку обратно в память. Сразу после записи процессор 3 вызывает из памяти копию только что записанной строки, и в обоих кэшах строка помечается как разделяемая (рис. 8.22, г). Когда затем процессор 2 снова записывает эту строку (рис. 8.22, в), ее копия в кэше процессора 3 становится недействительной.

Наконец, пусть теперь слово в строке записывает процессор 1. Процессор 2 видит, что делается попытка записи, и выставляет на шину сигнал, который сообщает процессору 1, чтобы тот подождал, пока процессор 2 запишет свою строку в память. После окончания записи процессор 2 помечает собственную копию строки как недействительную, поскольку знает, что другой процессор собирается ее изменить. Возникает ситуация, в которой процессор выполняет запись в некэшированную строку. Если применяется политика заполнения по записи, строка будет загружена в кэш и помечена как модифицированная (рис. 8.22, е). Если политика заполнения по записи не применяется, запись происходит непосредственно в память, и строка вообще нигде не кэшируется.

UMA-мультипроцессоры в симметричных мультипроцессорных архитектурах

Рис. 8.22. Иллюстрация протокола МЕЭ1

иМА-мультипроцессоры с перекрестной коммутацией

Из-за наличия всего одной шины в ИМА-мультипроцессоре даже после оптимизации не может быть больше 16 или 32 процессоров. Чтобы процессоров стало больше, требуется другой тип коммуникационной сети. Самая простая схема соединения п процессоров с к блоками памяти - перекрестная коммутация

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

UMA-мультипроцессоры в симметричных мультипроцессорных архитектурах

Рис. 8.23. Перекрестная коммутация 8x8 (а); открытый узел (б); закрытый узел (б)

На каждом пересечении горизонтальной (входящей) и вертикальной (исходящей) линии находится коммутационный узел (ш^ротт.), который можно открыть или закрыть в зависимости от того, нужно соединить горизонтальную и вертикальную линии или нет. На рис. 8.23, а мы видим, что три узла закрыты, благодаря чему одновременно устанавливается связь между следующими парами процессор-память (001, ООО), (101, 101) и (110, 010). Возможны и другие комбинации. Число комбинаций равно числу вариантов расстановки восьми ладей на шахматной доске так, чтобы ни одна из них не находилась под боем другой.

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

Одним из худших свойств перекрестной коммутации является то, что число узлов растет как п2. Для средних по размеру систем перекрестная коммутация является хорошим решением, и далее в этой главе мы рассмотрим одно из таких решений - NUMA-мультипроцессор Sun Fire Е25К. Однако для 1000 процессоров и 1000 модулей памяти понадобится миллион узлов, что неприемлемо. Необходимо нечто совершенно иное.

UMA-мультипроцессоры с многоступенчатой коммутацией

В основе этого "совершенно иного" лежит небольшой коммутатор 2x2 (рис. 8.24, а) с двумя входами и двумя выходами. Сообщения, приходящие на любую из входных линий, могут переключаться на любую выходную линию. В нашем примере сообщения будут содержать до четырех частей (рис. 8.24, б). Поле модуля показывает, какой модуль памяти запрашивается. Поле адреса определяет адрес в этом модуле памяти. В поле кода операции указывается одна из доступных операций, например, READ или WRITE. Наконец, дополнительное поле значения может содержать операнд, например, 32-разрядное слово, которое нужно записать при выполнении операции WRITE. Коммутатор проверяет поле модуля и с его помощью определяет, через какую выходную линию нужно отправить сообщение: через X или через Y.

UMA-мультипроцессоры в симметричных мультипроцессорных архитектурах

Рис. 8.24. Коммутатор 2x2 (а); формат сообщения (б)

Наши коммутаторы 2x2 можно компоновать различными способами и получать сети с многоступенчатой коммутацией. Один из возможных вариантов - сеть omega (рис. 8.25). Здесь 8 процессоров соединены с 8 модулями памяти через 12 коммутаторов. Для п процессоров и п модулей памяти понадобится log2n ступеней и п/2 коммутаторов на каждую ступень, то есть, всего (n/2)log2n коммутаторов, что намного меньше, чем п2 коммутационных узлов при перекрестной коммутации, особенно для больших значений п.

Схему разводки проводов сети omega часто называют полной перетасовкой (perfect shuffle), поскольку смешение сигналов на каждой ступени напоминает тасование колоды карт. Чтобы понять, как работает сеть omega, предположим, что процессору 011 нужно считать слово из модуля памяти 110. Процессор посылает сообщение READ, чтобы переключить коммутатор 1D, который содержит 110 в поле модуля. Коммутатор берет первый (то есть крайний левый) бит от 110 и по нему узнает направление (0 указывает на верхний выход, 1 - на нижний). Поскольку в данном случае этот бит равен 1, сообщение отправляется через нижний выход к коммутатору 2D.

Все коммутаторы второй ступени, включая 2D, для определения направления используют второй бит. В данном случае он равен 1, поэтому сообщение отправляется через нижний выход к коммутатору 3D, который проверяет третий бит. Он равен 0, следовательно, сообщение проходит через верхний выход и прибывает в модуль памяти 110, чего мы и добивались. Путь, пройденный сообщением, обозначен на рис. 8.25 буквой а.

UMA-мультипроцессоры в симметричных мультипроцессорных архитектурах

По мере прохождения через сеть сообщение поочередно перестает нуждаться во всех битах номера модуля, начиная с самого левого. Их можно использовать для записи номеров входных линий, чтобы было известно, по какому пути посылать ответ. Для пути а входные линии - это 0 (верхний вход в ID), 1 (нижний вход в 2D) и 1 (нижний вход в 3D) соответственно. Таким образом, при отправке ответа тоже используется последовательность 011, только прочтенная справа налево.

Пусть в то время как все это происходит, процессор 001 тоже решает записать слово в модуль памяти 001. Здесь происходит аналогичный процесс. Сообщение отправляется через верхний, верхний и нижний выходы соответственно. На рис. 8.25 этот путь отмечен буквой Ъ. Когда сообщение прибывает в пункт назначения, в его поле модуля содержится последовательность 001, показывая путь, который прошло сообщение. Поскольку эти два запроса проходят через разные коммутаторы, линии и модули памяти, они могут выполняться параллельно.

А теперь посмотрим, что произошло бы, если бы процессору 000 понадобился доступ к модулю памяти 000. Его запрос вступил бы в конфликт с запросом процессора 001 на коммутаторе ЗА, и одному из них пришлось бы ждать. То есть, в отличие от сети с перекрестной коммутацией, сеть omega - это блокирующая сеть. Одновременно может передаваться не всякий набор запросов. Конфликты могут возникать как между запросами (при использовании одной и той же линии или одного и того же коммутатора), так и между запросами (к памяти) и ответами (из памяти).

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

Семантика памяти8 || Оглавление || NUMA-мультипроцессоры