Э. Таненбаум - Архитектура компьютера (1127755), страница 166
Текст из файла (страница 166)
Возникает вопрос: какова вероятность, что только что записанное слово вскоре опять будет записано? Когда вероятность высока, можно говорить в пользу загрузки каша при кэш-промахах записи (политика заполнения по записи). Когда вероятность мала, то в случае кэш-промаха записи лучше не обновлять кэш-память. Если данное слово вскоре должно быть считано, после кэш-промаха чтения оно все равно окажется загруженным, поэтому нет смысла загружать его при кэш-промахе записи. Как и большинство простых решений, это решение не слишком эффективно.
Каждая операция записи требует передачи данных в основную память по шине, и при большом количестве процессоров шина становится узким местом. Поэтому были разработаны другие протоколы. Все они имеют одно общее свойство: не каждая операция записи ведет к записи непосредственно в основную память. Вместо этого при изменении строки каша внутри каша устанавливается особый бит, который указывает, что строка в каше правильная, а в памяти — нет. Хотя в конечном итоге данную строку все равно придется записать в память, вполне вероятно, что это произойдет после выполнения еще нескольких операций записи.
Такой тип протокола называется протоколом отложенной записи. Протокол МЕЗ! Одним из популярных протоколов отложенной записи является протокол МЕ$1 (1пуа11о, 911агед, Ехс1изгуе, Мог]1йео — недействительный, разделяемый, эксклюзивный, модифицированный), названный так по первым буквам четырех возможных состояний элементов каша [159]. В его основе лежит более ранний протокол однократной записи 177]. Протокол МЕЯ1 используется в Репг1нш 4 и других процессорах для слежения за шиной. В соответствии с этим протоколом каждый элемент каша может находиться в одном из следующих четырех состояний: Мультипроцессоры 651 + недействительный — элемент каша содержит недействительные данные; + разделяемый — элемент может храниться в нескольких кашах, память обновлена; + эксклюзивный — элемент находится только в данном кэше (ни в каких других кашах его нет),память обновлена; + модифицированный — элемент действителен, основная память недействительна, копий элемента не существует.
При загрузке процессора все элементы каша помечаются кэк недействительные. При первом считывании из основной памяти нужная строка вызывается в кэш данного процессора и помечается как эксклюзивная, поскольку это — единственная кэшированная копия (рис. 8.22, а). При последующих считываниях процессор использует эту строку, не обращаясь к шине. Другой процессор может вызвать ту же строку и поместить ее в кэш. В этом случае первый держатель строки (процессор 1) благодаря слежению узнает, что он уже не единственный держатель строки, н объявляет по шине, что у него копия. Обе копии помечаются как разделяемые (рис. 8.22, 6). Другими словами, состояние «разделяемая» означает, что память обновлена, и строка после чтения находится в одном или нескольких кэшах.
При последующих чтениях разделяемой строки процессор не использует шину и не меняет состояние строки. Посмотрим теперь, что происходит, когда процессор 2 выполняет запись в разделяемую строку каша. В этом случае процессор помещает на шину специальный сигнал, сообщая всем другим процессорам о том, что их копии более недействительны, при этом копия в каше самого процессора 2 переходит в состояние «модифицирована» (рис. 8.22, в). В память эта строка не записывается. Отметьте, что если указанная строка является эксклюзивной, никакого сигнала о недействительности на шину передавать не нужно, поскольку других копий этой строки не существует. Далее выясним, что происходит, когда эту строку считывает процессор 3.
Процессор 2, который в данный момент является держателем строки, знает, что копия в памяти недействительна, поэтому он передает на шину сигнал о том, чтобы процессор 3 ждал, пока он запишет строку обратно в память. Сразу после записи процессор 3 вызывает из памяти копию только что записанной строки, и в обоих кашах строка помечается как разделяемая (рис. 8.22, г). Когда затем процессор 2 снова записывает зту строку (рис.
8.22, в), ее копия в кэше процессора 3 становится недействительной. Наконец, пусть теперь слово в строке записывает процессор 1. Процессор 2 видит, что делается попытка записи, и выставляет на шину сигнал, который сообщает процессору 1, чтобы тот подождал, пока процессор 2 запишет свою строку в память. После окончания записи процессор 2 помечает собственную копию строки как недействительную, поскольку знает, что другой процессор собирается ее изменить. Возникает ситуация, в которой процессор выполняет запись в некэшированную строку.
Если применяется политика заполнения по записи, строка будет загружена в кэш и помечена как модифицированная (рис. 8.22, е). Если политика заполнения по записи не применяется, запись происходит непосредственно в память, и строка вообще нигде не кэшируется. 652 Глава 8. Параллельные компьютерные архитектуры Процессор 1 считывает блокА Кзш Шина Процессор 2 считывает блок А Шина Процессор 2 записывает блок А Шина Процессор 3 считывает блок А Шина Процессор 2 записывает блок А Шина Процессор 1 записывает блок А Шина Рис. 8.22. Иллюстрация протокола МЕ81 ЦМА-мультипроцессоры с перекрестной коммутацией Из-за наличия всего одной шины в ИМА-мультипроцессоре даже после оптимизации не может быть больше 16 или 32 процессоров.
Чтобы процессоров стало больше, требуется другой тип коммуникационной сети. Самая простая схема соединения и процессоров с и блоками памяти — перекрестная коммутация Мультнлроцессоры 653 1рис. 8.23). Перекрестная коммутация на протяжении многих десятилетий ис- пользуется в телефонных коммутаторах, позволяющих произвольным образом связывать группы входящих и исходящих линий.
Модули памяти рытый ационный узел л о о о о Ф о СЬ крытый утационный узел Открытый коммутационный узел Закрытый коммутационный узел Рис. 8.23. Перекрестная коммутация 8 х 8 (в); открытый узел (б); закрытый узел (в) На каждом пересечении горизонтальной 1входящей) и вертикальной 1исходящей) линии находится коммутационный узел (сгоззро(пг), который можно открыть или закрыть в зависимости от того, нужно соединить горизонтальную и вертикальную линии или нет. На рис.
8.23, а мы видим, что три узла закрыты, благодаря чему одновременно устанавливается связь между следующими парами процессор-память 1001, 000), (101, 101) и 1110, 010). Возможны и другие комбинации. Число комбинаций равно числу вариантов расстановки восьми ладей на шахматной доске так, чтобы ни одна из них не находилась под боем другой. Одним из самых симпатичных свойств сети с перекрестной коммутацией является то, что она неблокирующая.
Это означает, что процессор всегда сможет соединиться с нужным модулем памяти, даже если некоторые линии или узлы уже заняты гпредполагается, что сам модуль памяти доступен). Более того, никакого предварительного планирования не требуется. Даже если уже установлено семь произвольных соединений, всегда можно соединить оставшийся процессор с оставшимся модулем памяти. Далее мы рассмотрим схемы взаимного соединения, которые не обладают такой возможностью. Одним из худших свойств перекрестной коммутации является то, что число узлов растет как и".
Для средних по размеру систем перекрестная коммутация 654 Глава 8. Параллельные компьютерные архитектуры является хорошим решением, и далее в этой главе мы рассмотрим одно из таких решений — )ч)()МА-мультипроцессор Зип Е(ге Е25К. Однако для 1000 процессоров и 1000 модулей памяти понадобится миллион узлов, что неприемлемо. Необходимо нечто совершенно иное.
0МА-мультипроцессоры с многоступенчатой коммутацией В основе этого «совершенно иногое лежит небольшой коммутатор 2 х 2 (рис. 8.24, а) с двумя входами и двумя выходами. Сообщения, приходящие на любую из входных линий, могут переключаться на любую выходную линию. В нашем примере сообщения будут содержать до четырех частей (рис.
8.24, 6). Поле модуля показывает, какой модуль памяти запрашивается. Поле адреса определяет адрес в этом модуле памяти. В поле кода операции указывается одна из доступных операций, например, йЕАО или Ий1ТЕ. Наконец, дополнительное поле значения может содержать операнд, например, 32-разрядное слово, которое нужно записать при выполнении операции Ий1ТЕ. Коммутатор проверяет поле модуля и с его помощью определяет, через какую выходную линию нужно отправить сообщение: через Х или через К Значение Рис. 8.24.
Коммутатор 2 х 2 (а); формат сообщения (б) Наши коммутаторы 2 х 2 можно компоновать различными способами и получать сети с многоступенчатой коммутацией. Один из возможных вариантов— сеть ощейа (рис. 8.25). Здесь 8 процессоров соединены с 8 модулями памяти через 12 коммутаторов. Для л процессоров и л модулей памяти понадобится 1ойтл ступеней и л/2 коммутаторов на каждую ступень, то есть, всего (л/2)1ойтл коммутаторов, что намного меньше, чем л' коммутационных узлов при перекрестной коммутации, особенно для больших значений л.
Схему разводки проводов сети ошейа часто называют полной перетасовкой (рег(ест зЬпЯе), поскольку смешение сигналов на каждой ступени напоминает тасование колоды карт. Чтобы понять, как работает сеть ошейа, предположим, что процессору 011 нужно считать слово из модуля памяти 110. Процессор посылает сообщение йЕАО, чтобы переключить коммутатор 11), который содержит 110 в поле модуля. Коммутатор берет первый (то есть крайний левый) бит от 110 и по нему узнает направление (О указывает на верхний выход, 1 — на нижний).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
