К. Хамахер, З. Вранешич, С. Заки - Организация ЭВМ - 5-е издание (2003) (1114649), страница 83
Текст из файла (страница 83)
Поле тега адреса ассоциативным путем сравнивается с тегами двух блоков найденного множества, и если оно совпадет с одним из тегов, значит, соответствующий блок уже находится в каше. Реализовать такой поиск очень просто. Количество блоков во множестве задается в соответствии с требованиями конкретного компьютера.
В случае основной памяти и каша, показанных на рис. 5.17, для четырех блоков в множестве потребуется 5-разрядное поле множества, длл восьми блоков — 4-разрядное и т. д. Граничное значение 128 блоков в множестве не требует поля множества и соответствует полностью ассоциативному кэшу с 12 теговыми битами. Другое граничное значение — один блок в множестве — соответствует методу прямого отображения. Кэш с я блоками во множестве называется в-канальным множественно-ассоциативным кэшем.
Для каждого блока в каше должен храниться еще один управляющий бит, называемый битом достоверности. Он указывает, содержит ли блок достоверные данные. Его не следует путать с упоминавшимся ранее битом изменения, указывающим, был ли блок модифицирован за то время, пока он находится в каше.
Бит модификации нужен только в тех системах, в которых не используется сквозная запись. При включении питания системы и при загрузке с диска в основную память новой программы и данных все биты достоверности устанавливаются в О. Пересылка данных между диском и основной памятью управляется механизмом прямого доступа к памяти (1)МА). Обычно эти данные минуют кэш, что вызвано соображениями стоимости и производительности. Когда блок каша в первый раз загружается из основной памяти, его бит достоверности устанавливается в 1.
Если блок основной памяти обновляется из другого источника, минуя кзш, система проверяет, находится ли загружаемый блок в каше. Если да, его бит достоверности устанавливается в О, чтобы в каше не оказалось устаревших данных. Подобная проблема возникает прн ПДП-пересылке данных из основной памяти на диск, если используется кзш с обратной записью.
Данные, находящиеся в памяти, могут не отражать изменений, внесенных в кзшируемую копию. Поэтому перед их копированием на диск можно записать измененные данные из каша в основную память. Операционная система легко справляется с этой задачей, и это не отражается на ее производительности, поскольку пересылка данных между диском и основной памятью происходит нечасто, Обязательное использование двумя б.б. Кэш-памнть 355 разными элементами (в данном случае процессором и подсистемой ЩП) одинаковых копий данных называется согласованностью кеша.
Основная память Множество 1 Множество 2 Множество 63 Тег Множество Олово Адрес основной памяти Рис. 5.17. Множественно-ассоциативный кзш с двумя блоками в множестве 5.5.2. Алгоритмы замещения В каше с прямым отображением позиция каждого блока определена раз и навсегда, поэтому никакая особая стратегия замены блоков ему не требуется.
Л вот в ассоциативном или множественно-ассоциативном каше замена блоков может выполняться по-разному. Когда в кэш нужно будет поместить новый блок, но свободной позиции для него там не окажется, контроллер каша должен выбрать один вз старых блоков для перезаписи. От того, как он будет решать эту задачу, зависит производительность системы.
Главная идея, которой следует руководствоваться, 356 Глава 5. Система памяти принимая такое решение, состоит в следующем: в памяти должны оставаться блоки, для которых вероятность того, что они понадобятся в ближайшем будущем, максимальна. Но как их определить? Здесь можно опереться на принцип локализации ссылок. Так как повторяющиеся команды, лежащие в пределах некоторой области, выполняются в течение определенного времени, существует большая вероятность того, что блоки, обращение к которым производилось недавно, очень скоро потребуются снова. Поэтому, когда требуется освободить место для нового блока, имеет смысл удалить из кэша тот блок, к которому дольше всего не было обращений. Алгоритм работы этого блока называется алгоритмом удаления наиболее давно использовавшихся элементов (Ееазс Кесепс1у Пзеб, ЕК '). Для использования алгоритма ЕКП контроллер каша должен отслеживать обращения ко всем блокам кэша.
Предположим, что ему нужно следить за обращениями к блоку ЕКП из четырехблочного множества множественно-ассоциативного каша. Для каждого блока может использоваться 2-разрядный счетчик. При попадании в кэш счетчик соответствующего блока устанавливается в О. Счетчики, значения которых были больше значения данного счетчика, увеличиваются на 1. Когда в каше не оказывается нужного блока, а в множестве еще есть место, счетчик нового блока устанавливается в 0, а значения других счетчиков увеличиваются на 1.
Если же множество заполнено, блок, счетчик которого равен 3, удаляется, а на его место помещается новый блок. Значения остальных трех счетчиков увеличиваются на 1. Нетрудно убедиться, что при использовании такого алгоритма значения счетчиков четырех блоков всегда будут разными. Алгоритм ЕК ' очень популярен. В большинстве случаев он работает прекрасно, но иногда его применение может привести к снижению производительности, например, при обращении к последовательным элементам массива, который слишком велик и не помещается в каше целиком (см, раздел 5.5,3 и упражнение 5.12). Для того чтобы повысить производительность алгоритма, можно внести в него некоторую долю случайного выбора.
На практике используются и некоторые другие алгоритмы замещения. Правило замены самого «старого» блока кажется наиболее логичным, но оно не принимает в расчет частоту обращений к хранящимся в каше блокам. Поэтому оно не так эффективно, как алгоритм ЕКП. Самым простым решением является случайный выбор перезаписываемого блока, и, что интересно, практика показывает его эффективность.
5.5.3. Примеры технологий отображения Ниже будет рассмотрен пример, демонстрирующий различия между разными технологиями отображения памяти на кэш. Предположим, что у процессора имеются отдельные каши команд и данных. Для упрощения примера будем считать, что в кэше данных помещается только восемь блоков. Блок состоит из одного 10-разрядного слова, а память адресуется пословно посредством 16-разрядньп адресов. (Это не реалистичные параметры, но они удобны для нашего примера.) Для замены блоков в каше используется алгоритм ЕКП. Давайте проанализируем изменения в кэше данных, вызванные выполнением следующей задачи.
Массив чисел А размером 4 х 14, в котором каждое число 5.5. Кэш-память 357 занимает одно слово, хранится в основной памяти по шестнадцатеричным адресам от 7АОО до 7А27. Элементы этого массива хранятся в порядке следования столбцов. На рис. 5.18 показано, как выделяются тети из адресов памяти при разных технологиях отображения. Обратите внимание, что в нашем примере нет специальных битов, используемых для идентификации слова внутри блока, как на рис. 5.15 — 5.17, поскольку мы предполагаем, что каждый блок содержит только одно слово. Приложение нормализует значения элементов первой строки массива А относительно среднего значения элементов этой строки.
Таким образом, нам нужно вычислить среднее значение элементов строки и разделить на него значение каждого из элементов. Эту задачу можно выразить так: Код, выполняющий указанную задачу, приведен на рис. 5.19. В программе на машинном языке для ссылки на элементы массива будут использоваться адреса памяти. Для хранения суммы и среднего значения предназначены переменные 8ПМ и АЧЕ. Эти переменные, равно как и индексные переменные 1 и)', при вычислениях хранятся в регистрах процессора. Содержимое (7А24) (7А25) (7А26) (7А27) Тег для прямого отображения Тег для множественноцнативного отображен Тег для ассоциативного отображения (7АОО) (7А01) (7А02) (7АОЗ) (7А04') А(0,() +- для 1 - О, 1, ..., 9 А(0, 1) ,,> А(О,Я 10 т=а 0 1 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 0 0 0 0 0 0 0 0 1 0 1 1 1 1 0 1 0 0 0 0 0 0 0 1 0 0 1 1 1 1 0 1 0 0 0 0 0 0 0 1 1 0 1 1 1 1 0 1 0 0 0 0 0 0 1 0 0 0 1 1 1 1 0 1 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 1 0 0 0 1 0 0 1 0 1 0 1 1 1 1 0 1 0 0 0 1 0 0 1 1 0 0 1 1 1 1 0 1 0 0 0 1 0 0~1 1 1~ Рис.
5.18. Массив, хранящийся в основной памяти 358 Глава 5. Система памяти 5ПМ:- О Еог):-О Го 9 до ЯЛМ:- ЯБМ + А(0,1) епб Ат'Е:- ЯЮМ / 10 1ог 1:- 9 с1оч псо О с1о А(0,1):- А(О,!) / АУЕ епд Рис. 6.19. Код дяя примера из раздела 5.5.3 Каш с прямым отображением На рис. 5.20 показано, как изменяется содержимое каша с прямым отображением. В столбцах таблицы приведено содержимое каша после проходов по двум циклам программы, представленной на рис.
5.19. Например, после второго прохода по первому циклу (у - 1) в каше содержатся элементы А(0,0) и А(0,1). Они хранятся в блоках 0 и 4 с учетом значений трех младших разрядов нх адресов. На следующем проходе элемент А(0,0) заменяется элементом А(0,2), имеющим тот же адрес блока. Обратите внимание, что элементы массива соответствуют только двум блокам кэша, а остальные блоки остаются неизменными — в конце процесса нормализации они содержат те же данные, что до его начала.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
