37. Кэш-память.Прямая функция отображения.
При прямом отображении адрес строки кэш-памяти, на которую может быть отображен блоку из ОП, однозначно определяется выражением: i =j mod т, где т — общее число строк в кэш-памяти. В нашем примере i =j mod 128, где i может принимать значения от 0 до 127, а адрес блока j— от 0 до 16 383. Иными словами, на строку кэша с номером i отображается каждый 128-й блок ОП, если отсчет начинать с блока, номер которого равен |i|.
При реализации такого отображения 14-разрядный адрес блока основной памяти условно разбивается на два поля. Логика кэш-памяти интерпретирует эти 14 бит как 7-разрядный
тег и 7-разрядное поле строки. Поле строки указывает на одну из 128 = 27 строк кэш-памяти, а именно на ту, куда может быть отображен блок с заданным адресом. В свою очередь, поле тега определяет, какой именно из списка блоков, закрепленных за данной строкой кэша, будет отображен. Когда блок фактически заносится в память данных кэша, в память тегов кэш-памяти необходимо записать тег этого блока, чтобы отличить его от других блоков, которые могут быть загружены в ту же строку кэша. Тегом служат семь старших разрядов адреса блока.
Прямое отображение - простой и недорогой в реализации способ отображения. Основной его недостаток — жесткое закрепление за определенными блоками ОП одной строки в кэше.
38. Кэш-память. Ассоциативная функция отображения.
При этом способе разрывается связь между блоком ОП и опред.строкой КЭШ.
Любой блок ОП может быть размещен в любой строке КЭШ.
Существуют специальные алгоритмы выбора строки КЭШ для замены.
Алгоритм поиска:
Старшие 6 бит адреса теперь рассматриваются как поле ТЭГа и сравниваются параллельно с ТЭГами всех строк КЭШ.
«+» - позволяет повысить эффективность использования КЭШ-памяти. Позволяет повысить вероятность попадания числа обращ. к ОП.
«-» - резко увелич. ????(сложность)??? логических схем. Увеличививается объем КЭШ-памяти.
39. Секционированная ассоциативная функция отображения
40. Алгоритмы замещения строк кэш.
В информатике под алгоритмами кэширования (замещения) понимают оптимизацию инструкций — алгоритмы — особая компьютерная программа или аппаратно поддерживаемая структура, способная управлять кэшем информации, хранимой в компьютере. Когда кэш заполнен, алгоритм должен выбрать, что именно нужно удалить из него, чтобы иметь возможность записи (в кэш) новой, более актуальной информации.
«Уровень попаданий» кэша означает то, насколько часто искомые данные обнаруживаются в кэше. Более эффективные политики вытеснения отслеживают обращения к наиболее используемой информации, чтобы улучшить уровень попаданий (при том же размере кэша).
«Латентность» кэша означает, насколько быстро кэш может вернуть запрошенные данные непосредственно после запроса (в случае, если происходит «попадание»). Более быстрые стратегии вытеснения обычно отслеживают наименее используемую информацию — или, в случае кэша прямого отображения (direct-mapped cache), отсутствие информации, чтобы снизить затраты времени на обновление информации.
Каждая стратегия вытеснения является компромиссом между уровнем попаданий и латентностью.
Least Recently Used (LRU): в первую очередь, вытесняется неиспользованный дольше всех. Этот алгоритм требует отслеживания того, что и когда использовалось, что может оказаться довольно накладно, особенно если нужно проводить дополнительную проверку, чтобы в этом убедиться. Общая реализация этого метода требует сохранения «бита возраста» для строк кэша и за счет этого происходит отслеживание наименее использованных строк (то есть за счет сравнения таких битов). В подобной реализации, при каждом обращении к строке кэша меняется «возраст» всех остальных строк.
Most Recently Used (MRU): в отличе от LRU, в первую очередь вытесняется последний использованный элемент. В соответствии с источником [1], «Когда файл периодически сканируется по циклической схеме, MRU — наилучший алгоритм вытеснения». В источнике [2] авторы также подчеркивают, что для схем случайного доступа и циклического сканирования больших наборов данных (иногда называемых схемами циклического доступа) алгоритмы кэширования MRU имеют больше попаданий по сравнению с LRU за счет их стремления к сохранению старых данных. Алгоритмы MRU наиболее полезны в случаях, когда чем старше элемент, тем больше обращений к нему происходит.
Least Frequently Used (LFU): LFU подсчитывает как часто используется элемент. Те элементы, обращения к которым происходят реже всего, вытесняются в первую очередь.
41. – разрази меня гром, но я помню, как марковский говорил, что он снимает вопрос о виртуальной памяти с экзамена. Выстрелите мне стрелой в колено, если это не так.