ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 24.12.2021
Просмотров: 6705
Скачиваний: 8
5 9 8 Глава 8. Архитектуры компьютеров параллельного действия
Совместно
используемая память
Процессор Процессор
Память
Процессор Процессор
Кэш-память
Шина
Память
Собственная память -
Процессор
И(
Процессор
Кэш-память
Совместно
:пользуемая п<
\
Память
Рис. 8.17. Три мультипроцессора на одной шине: без кэш-памяти (а); с кэш-памятью (б);
с кэш-памятью и отдельными блоками памяти (в)
Еще одна возможность — разработка, в которой каждый процессор имеет не
только кэш-память, но и свою локальную память, к которой он получает доступ
через назначенную локальную шину (рис. 8.17,
в).
Чтобы оптимально использовать
такую конфигурацию, компилятор должен поместить в локальные модули памяти
весь текст программы, цепочки, константы, другие данные, предназначенные только
для чтения, стеки и локальные переменные. Общая разделенная память использу-
ется только для общих переменных. В большинстве случаев такое разумное разме-
щение сильно сокращает количество данных, передаваемых по шине, и не требует
активного вмешательства со стороны компилятора.
Отслеживание изменений данных в кэш-памяти
Предположим, что память согласована по последовательности. Что произойдет,
если процессор 1 содержит в своей кэш-памяти строку, а процессор 2 пытается
считать слово из той же строки кэш-памяти? При отсутствии специальных правил
процессор 2 получит копию этой строки в свою кэш-память. В принципе помеще-
ние одной и той же строки в кэш-память дважды вполне приемлемо. А теперь пред-
положим, что процессор 1 изменяет строку, и сразу после этого процессор 2 счи-
тывает копию этой строки из своей кэш-памяти. Он получит
устаревшие данные,
нарушая контракт между программным обеспечением и памятью. Ни к чему хоро-
шему это не приведет.
Эта проблема, которую называют
непротиворечивостью кэшей,
очень важна.
Если ее не разрешить, нельзя будет использовать кэш-память, и число мультипро-
цессоров, подсоединенных к одной шине, придется сократить до двух-трех. Спе-
циалистами было предложено множество различных решений (например, [47,109]).
Хотя все эти алгоритмы, называемые
протоколами когерентности кэширования,
Мультипроцессоры с памятью совместного использования
599
различаются в некоторых деталях, все они не допускают одновременного появле-
ния разных вариантов одной и той же строки в разных блоках кэш-памяти.
Во всех решениях контроллер кэш-памяти разрабатывается так, чтобы кэш-па-
мять могла перехватывать запросы на шине, контролируя все запросы шины от
других процессоров и других блоков кэш-памяти и предпринимая те или иные дей-
ствия в определенных случаях. Эти устройства называются
кэш-памятью с отсле-
живанием (snooping caches
или
snoopy caches),
поскольку они отслеживают шину.
Набор правил, которые выполняются кэш-памятью, процессорами и основной па-
мятью, чтобы предотвратить появление различных вариантов данных в несколь-
ких блоках кэш-памяти, формируют протокол когерентности кэширования. Еди-
ница передачи и хранения кэш-памяти называется строкой кэш-памяти. Обычно
строка кэш-памяти равна 32 или 64 байтам.
Самый простой протокол когерентности кэширования называется
сквозным кэ-
шированием.
Чтобы лучше понять его, рассмотрим 4 случая, приведенные в табл. 8.6.
Если процессор пытается считать слово, которого нет в кэш-памяти, контроллер
кэш-памяти загружает в кэш-память строку, содержащую это слово. Строку предо-
ставляет основная память, которая в это: > протоколе всегда обновлена. В дальней-
шем информация может считываться из кэш-памяти.
Таблица 8.6.
Сквозное кэширование. Пустые графы означают, что никакого
действия не происходит
Действие Локальный запрос Удаленный запрос
Промах при чтении Вызов данных из памяти
Попадание при чтении Использование данных
из локальной кэш-памяти
Промах при записи Обновление данных в памяти
Попадание при записи Обновление кэш-памяти Объявление элемента кэш-
и основной памяти памяти недействительным
В случае промаха кэш-памяти при записи слово, которое было изменено, запи-
сывается в основную память. Строка, содержащая нужное слово, не загружается
в кэш-память. В случае результативного обращения к кэш-памяти при записи кэш
обновляется, а слово плюс ко всему записывается в основную память. Суть прото-
кола состоит в том, что в результате всех операций записи записываемое слово
обязательно проходит через основную память, чтобы информация в основной па-
мяти всегда обновлялась.
Рассмотрим все эти действия снова, но теперь с точки зрения кэш-памяти с от-
слеживанием (крайняя правая колонка в табл. 8.6). Назовем кэш-память, которая
выполняет действия, кэш-1, а кэш с отслеживанием — кэш-2. Если при считыва-
нии произошел промах кэша-1, он запрашивает шину, чтобы получить нужную
строку из основной памяти. Кэш-2 видит это, но ничего не делает. Если нужная
строка уже содержится в кэш-1, запроса шины не происходит, поэтому кэш-2 не
знает о результативных считываниях из кэша-1.
Процесс записи более интересен. Если процессор 1 записывает слово, кэш-1
запрашивает шину как в случае промаха кэша, так и в случае попадания. Всегда
при записи кэш-2 проверяет наличие у себя записываемого слова. Если данное слово
6 0 0 Глава 8. Архитектуры компьютеров параллельного действия
отсутствует, кэш-2 рассматривает это как промах отдаленной памяти и ничего не
делает. (Отметим, что в табл. 8.6 промах отдаленной памяти означает, что слово не
присутствует в кэш-памяти отслеживателя; не имеет значения, было ли это слово
в кэш-памяти инициатора или нет. Таким образом, один и тот же запрос может
быть результативным логически и промахом для отслеживателя и наоборот.)
А теперь предположим, что кэш-1 записывает слово, которое присутствует
в кэш-2. Если кэш-2 не произведет никаких действий, он будет содержать устарев-
шие данные, поэтому элемент кэш-памяти, содержащий измененное слово, поме-
чается как недействительный. Соответствующая единица просто удаляется из кэш-
памяти. Все кэши отслеживают все запросы шины, и всякий раз, когда записывается
слово, нужно обновить его в кэш-памяти инициатора запроса, обновить его в ос-
новной памяти и удалять его из всех других кэшей. Таким образом, неправильные
варианты слова исключаются.
Процессор кэш-памяти-2 вправе прочитать то же самое слово на следующем
цикле. В этом случае кэш-2 считает слово из основной памяти, которая уже обно-
вилась. В этот момент кэш-1, кэш-2 и основная память содержат идентичные ко-
пии этого слова. Если какой-нибудь процессор произведет запись, то другие кэши
будут очищены, а основная память опять обновится.
Возможны различные вариации этого основного протокола. Например, при
успешной записи отслеживающий кэш обычно объявляет недействительным
элемент, содержащий данное слово. С другой стороны, вместо того чтобы объяв-
лять слово недействительным, можно принять новое значение и обновить кэш-
память. По существу, обновить кэш-память — это то же самое, что признать слово
недействительным, а затем считать нужное слово из основной памяти. Во всех кэш-
протоколах нужно сделать выбор между
стратегией обновления
и
стратегией с
признанием данных недействительными.
Эти протоколы работают по-разному.
Сообщения об обновлении несут полезную нагрузку, и следовательно, они больше
по размеру, чем сообщения о недействительности, но зато они могут предотвра-
тить дальнейшие промахи кэш-памяти.
Другой вариант — загрузка отслеживающей кэш-памяти при промахах. Такая
загрузка никак не влияет на правильность выполнения алгоритма. Она влияет толь-
ко на производительность. Возникает вопрос: какова вероятность, что только что
записанное слово вскоре будет записано снова? Если вероятность высока, то мож-
но говорить в пользу загрузки кэш-памяти при промахах записи
(политика запол-
нения по записи).
Если вероятность мала, лучше не обновлять кэш-память в слу-
чае промаха при записи. Если данное слово скоро будет считываться, оно все равно
будет загружено после промаха при считывании, и нет смысла загружать его в слу-
чае промаха при записи.
Как и большинство простых решений, это решение не очень эффективно. Каж-
дая операция записи должна передаваться в основную память по шине, а при боль-
шом количестве процессоров это затруднительно. Поэтому были разработаны дру-
гие протоколы. Все они характеризуются одним общим свойством: не все записи
проходят непосредственно через основную память. Вместо этого при изменении
строки кэш-памяти внутри кэш-памяти устанавливается бит, который указывает,
что строка в кэш-памяти правильная, а в основной памяти — нет. В конечном ито-
ге эту строку нужно будет записать в основную память, но перед этим в память
Мультипроцессоры с памятью совместного использования 601
можно произвести много записей. Такой тип протокола называется
протоколом
с обратной записью.
Протокол MESI
Один из популярных протоколов с обратной записью называется
MESI
(по пер-
вым буквам названий четырех состояний, М, Е, S и I) [109]. В его основе лежит
протокол однократной записи
[47]. Протокол MESI используется в Pentium II и
других процессорах для отслеживания шины. Каждый элемент кэш-памяти может
находиться в одном из следующих четырех состояний:
1. Invalid — элемент кэш-памяти содержит недействительные данные.
2. Shared — несколько кэшей могут содержать данную строку; основная память
обновлена.
3. Exclusive — никакой другой кэш не содержит эту строку; основная память
обновлена.
4. Modified — элемент действителен; основная память недействительна; копий
элемента не существует.
При загрузке процессора все элементы кэш-памяти помечаются как недействи-
тельные. При первом считывании из основной памяти нужная строка вызывается
в кэш-память данного процессора и помечается как Е (Exclusive), поскольку это
единственная копия в кэш-памяти (рис. 8.18,
а).
При последующих считывани-
ях процессор использует эту строку и не использует шину. Другой процессор
может вызвать ту же строку и поместить ее в кэш-память, но при отслеживании
исходный держатель строки (процессор 1) узнает, что он уже не единственный,
и объявляет, что у него есть копия. Обе копии помечаются состоянием S (Shared)
(см. рис. 8.18,
б).
При последующих чтениях кэшированных строк в состоянии S
процессор не использует шину и не меняет состояние элемента.
Посмотрим, что произойдет, если процессор 2 произведет запись в строку кэш-
памяти, находящуюся в состоянии S. Тогда процессор помещает сигнал о недействи-
тельности на шину, который сообщает всем другим процессорам, что нужно от-
бросить свои копии. Соответствующая строка переходит в состояние М (Modified)
(см. рис. 8.18, в). Эта строка не записывается в основную память. Отметим, что если
записываемая строка находится в состоянии Е, никакого сигнала о недействитель-
ности на шину передавать не следует, поскольку известно, что других копий нет.
А теперь рассмотрим, что произойдет, если процессор 3 считывает эту строку.
Процессор 2, который в данный момент содержит строку, знает, что копия в ос-
новной памяти недействительна, поэтому он передает на шину сигнал, чтобы про-
цессор 3 подождал, пока он запишет строку обратно в память. Как только строка
записана в основную память, процессор 3 вызывает из памяти копию этой строки,
и в обоих кэшах строка помечается как S (см. рис. 8.18,
г).
Затем процессор 2 запи-
сывает эту строку снова, что делает недействительной копию в кэш-памяти про-
цессора 3 (см. рис. 8.18,
в).
Наконец, процессор 1 производит запись в слово в этой строке. Процессор 2
видит это и передает на шину сигнал, который сообщает процессору 1, что нужно
подождать, пока строка не будет записана в основную память. Когда это действие
закончится, процессор помечает собственную копию строки как недействитель-
ную, поскольку он знает, что другой процессор собирается изменить ее. Возникает
6 0 2 Глава 8. Архитектуры компьютеров параллельного действия
ситуация, в которой процессор записывает что-либо в некэшированную строку.
Если применяется политика write-allocate, строка будет загружаться в кэш-память
и помечаться как М (рис. 8.18,
е).
Если политика write-allocate не применяется,
запись будет производиться непосредственно в основную память, а строка в кэш-
памяти сохранена не будет.
Кэш-память
а
Процессор 1
I A |
Процессор 2
I I
Exclsive
Процессор 3
I I
/
Память
Шина
Процессор 1
считывает
блок А
Процессор 1
I I
Процессор 2
I A |
Shared
Процессор 3
I I
Shared
Память
Шина
Шина
Шина
Шина
Процессор 2
считывает
блок А
Процессор 1
I I
Процессор 2
I A I
Modified
Процессор 3
I I
Память
Процессор 2
записывает
блок А
Процессор 1
I
Процессор 2
I A |
Shared
Процессор 3
I A |
Shared
Память
Процессор 3
считывает
блок А
Процессор 1
I I
Процессор 2
J А I
Modified
Процессор 3
I I
Память
Процессор 2
записывает
блок А
Процессор 1
I A |
Modified
Процессор 2
I I
Процессор 3
I I
Память
е
Шина
Рис. 8.18. Протокол MESI
Процессор 1
записывает
блок А