Попов И.И., Матвеев А.А., Максимов Н.В. Архитектура электронно-вычислительных машин и систем (2004) (1186255), страница 34
Текст из файла (страница 34)
Стратегияуправления памятью подразумевает ответ на такие вопросы: выборметода отображения основной памяти в кэше; алгоритм взаимодействиямежду медленной основной и быстрой кэш-памятью; выбор стратегиизамещения информации в кэше.Существует три основных способа размещения блоков(строк) вкэш-памяти. По способу размещения блоков основной памяти в кэшеразличают кэш-память с прямым отображением (direct-mapped cache),частично ассоциативную кэш-память (или множественно ассоциативнуюкэш-память, set-associative cache) и полностью ассоциативную кэшпамять (fully associative cache).Кэш-память называется с прямым отображением, если каждыйблок основной памяти имеет только одно фиксированное место, накотором он может появиться в кэш-памяти. Это наиболее простаяорганизация кэш-памяти.
Все блоки основной памяти, имеющиеодинаковые младшие разряды в своем адресе, попадают в один блоккэш-памяти. При таком подходе справедливо соотношение:(адрес блока кэш-памяти) = (адрес блока основной памяти) mod (числоблоков в кэш-памяти).Кэш-память называется полностью ассоциативной, еслинекоторый блок основной памяти может располагаться на любом местекэш-памяти.
Кэш-память называется частично ассоциативной, еслинекоторый блок основной памяти может располагаться на ограниченноммножестве мест.В современных процессорах как правило используется либо кэшпамять с прямым отображением, либо двух- (четырех-) канальнаямножественно-ассоциативная кэш-память.Стратегии замещения информации в кэше определяет блокподлежащий замещению при возникновении промаха. Простота прииспользовании кэша с прямым отображением заключается в том, чтоаппаратные решения здесь наиболее простые: легко реализуется самааппаратура, легко происходит замещение данных. При замещении190просто нечего выбирать - на попадание проверяется только один блок итолько этот блок может быть замещен. При полностью ассоциативнойили множественно-ассоциативной организации кэш-памяти имеютсянесколько блоков, из которых надо выбрать кандидата в случае промаха.Как правило для замещения блоков применяются две основныхстратегии: случайная и LRU-стратегия.В первом случае, чтобы иметь равномерное распределение, блокикандидаты выбираются случайно.
В некоторых системах, чтобыполучить воспроизводимое поведение, которое особенно полезно вовремя отладки аппаратуры, используют псевдослучайный алгоритмзамещения.Во втором случае, чтобы уменьшить вероятность выбрасыванияинформации, которая скоро может потребоваться, все обращения кблокам фиксируются. Заменяется тот блок, который не использовалсядольше всех (LRU - Least-Recently Used).Достоинство случайного способа заключается в том, что егопроще реализовать в аппаратуре. Когда количество блоковувеличивается, алгоритм LRU становится все более дорогим и частотолько приближенным. В табл. 2 показаны различия в долях промаховпри использовании алгоритма замещения LRU и случайного алгоритма.Таблица 2Влияние стратегии замещения на долю промаха при разныхразмерах кэш-памяти и ассоциативностиАссоциативностьРазмер кэшпамяти16 KB64 KB256 KB2-канальнаястратегияLRU5.181.881.154-канальнаястратегияRandom5.692.011.17LRU4.671.541.13Random5.291.661.138-канальнаястратегияLRU4.391.391.12Random4.961.531.12Из таблицы видно, что при большом размере кэш памятистратегии замещения не имеет существенного различия вэффективности памяти.Проблема когерентности кэш-памятиПри использовании иерархической памяти для каждого элементаданных должна быть обеспечена когерентность (согласованность,одинаковость) его копий, в разных уровнях иерархии.
Длямногопроцессорной ЭВМ, дело осложняется и тем, что одни и те деданные могут требоваться различными процессорами.191Как уже было замечено ранее, механизмы реализациикогерентности могут быть как явными, так и неявными для прикладногопрограммиста. Современные микропроцессоры имеют один илинесколько уровней внутрикристальной кэш-памяти. Поэтому интерфейсмикропроцессоров с необходимостью включает механизм организациикогерентности внутрикристальной кэш-памяти и внекристальнойпамяти. Внекристальная память может также быть многоуровневой:состоять из кэш-памяти и основной памяти.Реализация механизма когерентности в ВС с разделяемой памятьютребует аппаратурно-временных затрат.
Причем уменьшить временнуюсоставляющую затрат можно за счет увеличения аппаратурнойсоставляющей и наоборот. Уменьшение временной составляющейтребует создания специализированной аппаратуры реализациикогерентности.Уменьшениеаппаратурнойсоставляющейпредусматривает некоторый минимум аппаратных средств, на которыхосуществляется программная реализация механизма когерентности.Характеристики систем иерархической памятиХарактеристики иерархической системы памяти, можно разделитьна две группы: внутренние и внешние.
Эффективное быстродействиебуфера и эффективная стоимость представляют собой внутренниехарактеристики. Внешними характеристиками, являются: вероятностьудачного обращения, размещение буфера, емкость буфера, размер блока,алгоритмы управления, отображение адресов, отношение значенийвремени обращения для чтения и записи, алгоритмы записи, числомодулей основной памяти и последовательность обращения к ним,эффективная задержка или время ожидания для одного модуля,эффективная средняя задержка или время ожидания для несколькихмодулей.Внешние характеристики устанавливаются опытным путем илимоделированием и используются при проектировании в качествеисходных данных.Организация памяти в однопроцессорных ВСОднопроцессорные ВС являются первыми вычислительнымисистемами в которых была реализована иерархическая структурапамяти.
Как правило, однопроцессорные ВС представляют собойсовокупность процессора, памяти и внешних устройств (ВНУ)соединенных при помощи общей шины (рис. 20). Т.е. применяетсяшинная архитектура.192Рис. 20. Однопроцессорные ВС с иерархической системой памятиПрименение кэша в таких системах обусловлено толькоэкономической эффективностью функционирования систем с кэшпамятью.— алгоритм сквозной записи (Write Through) или сквозного накопления(Store Through);— алгоритм простого свопинга (Simple Swapping) или обратной записи(Write Back);— алгоритм свопинга с флагами (Flag Swapping) или обратной записи вконфликтных ситуациях с флагами (CUX);— алгоритм регистрового свопинга с флагами (FRS).Алгоритм сквозной записиЭто самый простой алгоритм свопинга.
Каждый раз при появлениизапроса на запись по некоторому адресу обновляется содержимоеобласти по этому адресу как в быстрой, так и в основной памяти, дажеесли копия содержимого по этому адресу находится в быстром буфере.Такое постоянное обновление содержимого основной памяти, как ибуфера, при каждом запросе на запись позволяет постоянноподдерживать информацию, находящуюся в основной памяти, вобновленном состоянии.193Рис.
21. Блок-схема алгоритма сквозной записиПоэтому, когда возникает запрос на запись по адресу,относящемуся к области, содержимое которой не находится в данныймомент в быстром буфере, новая информация записывается просто наместо блока, которое предполагается переслать в основную память (безнеобходимости пересылки этого слова в основную память), так как восновной памяти уже находится его достоверная копия.Данный алгоритм несложен для реализации и понимания, поэтомуон был широко распространен в системах с кэш-памятью.
Данныйалгоритм также просто позволяет реализовать когерентность данных длямультипроцессорных систем с раздельными кэшами и общей памятью.Обратной стороной простоты алгоритма является его малаяэффективность: в нем не заложена тенденция к минимизации долиобращений к основной памяти. При увеличении объема кэш-памятидоля обращений к основной памяти асимптоматически приближается кдоле обращений для записи в основную память (а не к нулю). На рис. 21приведена блок-схема алгоритма сквозной записи.Алгоритм простого свопингаДанный алгоритм не сложнее алгоритма сквозной записи.Обращения к основной памяти имеют место в тех случаях, когда в194быстром буфере не обнаруживается нужное слово.
Эта схема свопингаповышает производительность системы памяти, так как в ней обращенияк основной памяти не происходят при каждом запросе на запись, чтоимеет место при использовании алгоритма сквозной записи. Однако всвязи с тем, что содержимое основной памяти не поддерживается впостоянно обновленном состоянии, если необходимого слова в быстромбуфере не обнаруживается, из буфера в основную память надовозвратить какое-либо устаревшее слово, чтобы освободить место длянового необходимого слова. Поэтому из буфера в основную памятьсначала пересылается какое-то слово, место которого занимает в буференужное слово. Таким образом, происходят две пересылки междубыстрым буфером и основной памятью.Алгоритм свопинга с флагамиДанный алгоритм является улучшением алгоритма простогосвопинга.
В алгоритме простого свопинга когда в кэш-памяти необнаруживается нужное слово происходит два обращения к основнойпамяти - запись удаляемого значения из кэша и чтение нового значенияв кэш. Если слово с того момента, как оно попало в буфер из основнойпамяти, не подвергалось изменениям, т. е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
