Большой разброс длительности фазы ЕХ для различных машинных команд
11. Иерархическая схема организации памяти компьютеров и её обоснование. Основные характеристики уровней памяти: объём, время доступа (быстродействие), удельная стоимость хранения.
Иерархический подход к организации памяти компьютера означает, что память представляет собой совокупность запоминающих устройств, отличающихся как своими основными характеристиками, так и принципами действия. В простейшем случае иерархичная структура памяти рассматривает состояние из четырех уровней (уровни нумеруются по степени и близости к ЦП):
1. Регистровая память ЦП(CPU).
2. Кэш-память.
3. Основная память.
4. Внешняя память на жестких магнитных дисках.
Дополнение к упрощенной схеме уровней:
1. Кэш-память сама является многоуровневой (три, и даже четыре уровня).
2. Ниже уровня четвертого может использоваться дополнительно архивная память на сменных носителях.
3. Промежуточный уровень между третьим и четвертым в виде дискового кэша.
Иерархичный подход к организации памяти можно рассмотреть как разумный компромисс к обеспечению противоречивых требований со стороны пользователей к основным характеристикам памяти.
Основные характеристики основной памяти:
1. Объем или емкость.
В последнее время к единицам измерения емкости памяти применяется модифицированное наименование в виде добавки к основным приставкам: Kilo, Mega, Giga, Tera, Peta, Exa слова Binary.
Предлагается также использовать новые единицы измерения Kib, Mib и т.п., именующиеся Кибибайт, Мебибайт, для того чтобы отличать кило, мега от степени 2.
2. Время доступа.
3. Удельная стоимость.
Определяется стоимостью хранения 1-го бита. Удельная стоимость памяти определяется как отношение общей стоимости к объему
4. Длина слова памяти или ширина выборки.
Совпадает с разрядностью шины данных.
12. Организация кэш-памяти: стратегии отображения, стратегии удаления, стратегии поддержания актуальности копий блоков в ОП при их модификации в кэш-памяти.
Стратегии отображения
Двумя основными стратегиями отображения блоков основной памяти на блоки кэш-памяти являются:
- прямое отображение;
- полностью ассоциативное отображение.
При использовании первого принципа любой блок ОП может отображаться только на один конкретный блок кэш-памяти. При использовании второго принципа любой блок ОП может быть отображен на любой блок кэш-памяти.
1) Кэш-память с прямым отображением
Упрощенная структура кэш-памяти с прямым отображением представлена на рис. 3а.
Кэш-память разделяется на две части: память тегов и память данных. Память данных состоит из 128 блоков (по разрядности поля b в адресе основной памяти), каждый блок содержит 16 слов (по разрядности поля c). В частном случае, слово может соответствовать байту. Емкость кэш-памяти составляет 211 слов = 2 Кслов.
Емкость основной памяти равна 218 слов = 256 Кслов, что в 128 раз больше емкости кэш-памяти. Основная память состоит из 214 = 16384 блоков. Адрес блока (14 разрядов) разделяется на два поля: 7 старших разрядов образуют тег (идентификатор блока), а 7 младших – индекс блока. В соответствии со значениями тега и индекса, основную память можно представить в виде матрицы блоков, в которой номер столбца определяет значение тега, а номер строки – значение индекса блока (рис. 3 б). На один блок кэш-памяти может отображаться любой из 128 блоков ОП с одинаковым значением индекса, то есть блоки одной строки матрицы.
Рис. 3. Кэш-память с прямым отображением.
а) – структура кэш-памяти, б) – карта отображения блоков
При обращении к ОП осуществляется выборка тега из памяти тегов по адресу, представляющему собой индекс блока (поле b). Выбранный тег блока поступает на один из входов схемы сравнения (компаратора – CMP), на другой вход которого поступает тег запроса, то есть тег блока, к которому осуществляется текущее обращение (поле a из регистра адреса).
При совпадении тегов (кэш-попадание) на выходе компаратора формируется сигнал, по которому разрешается запись слова из памяти данных в регистр данных при операции чтения, или запись слова из регистра данных в память данных при операции записи. При несовпадении тегов формируется сигнал кэш-промаха. При обращении по чтению реакцией на этот сигнал будет пересылка блока из ОП в кэш-память с последующим чтением из кэш-памяти. При обращении по записи могут иметь место два подхода:
- запись слова только в ОП;
- пересылка блока из ОП в кэш-память с последующей записью слова в кэш-память.
2) Кэш-память с полностью ассоциативным отображением
Кэш-память с полностью ассоциативным отображением представлена на рис. 4.
Рис. 4. Кэш-память с полностью ассоциативным отображением
а – структура кэш-памяти, б – карта отображения блоков
При использовании принципа полностью ассоциативного отображения любой блок ОП может быть помещен на место любого блока кэш-памяти. По аналогии с кэш-памятью с прямым отображением в кэш-памяти с полностью ассоциативным отображением можно выделить память тегов и память данных.
Память тегов реализуется как ассоциативная, то есть обращение к ней производится не по адресу, а по некоторому ключу (признаку, тегу). Ключом поиска в памяти тегов является 14-разрядный адрес блока.
В ассоциативной памяти выделяются два регистровых блока:
- регистры тегов (TR1, …, TRn);
- регистры данных (DR1, …, DRn).
Так же существуют ещё 2 типа отображения кэш памяти, кратко о них:
3) Кэш-память с множественно-ассоциативным отображением
В кэш-памяти с множественно-ассоциативным отображением осуществляется разделение блоков кэш-памяти и, соответственно, основной памяти на ряд множеств (групп). Для блоков ОП, принадлежащих одному множеству, реализуется принцип прямого отображения, то есть все блоки ОП из одного множества должны отображаться на определенное число блоков кэш-памяти соответствующего множества гораздо меньшей мощности. В свою очередь принцип отображения блоков ОП на блоки кэш-памяти внутри выбранного множества является ассоциативным: любой блок ОП, принадлежащий выбранному множеству, может помещаться на место любого блока кэш-памяти, принадлежащего соответствующему множеству.
4) Кэш-память с распределением секторов
Кэш-память состоит из 8-ми секторов по 16 блоков в каждом, а ОП – из 1024 секторов, также, по 16 блоков в каждом. В отношении секторов реализован принцип полностью ассоциативного отображения, в то время как для блоков внутри каждого из секторов используется принцип прямого отображения. Дополнительным элементом кэш-памяти является память битов достоверности. Каждый бит этой памяти отмечает наличие копии блока из соответствующего сектора ОП в кэш-памяти. Память битов достоверности представляет собой битовую матрицу размером 16х8, число строк которой соответствует числу блоков в секторе, а число столбцов – количеству секторов.
При обращении к кэш-памяти, прежде всего, проверяется наличие сектора в кэш-памяти (по ассоциативному принципу). В случае кэш-попадания определяется наличие блока путем проверки соответствующего бита достоверности. При отсутствии затребованного сектора в кэш-памяти (кэш-промах по сектору), осуществляется выделение места под сектор кэш-памяти путем выбора сектора – кандидата на удаление. Все биты достоверности данного сектора сбрасываются. Далее осуществляется пересылка затребованного блока из ОП в кэш-память с установкой бита достоверности этого блока, после чего обращение к этому блоку становится возможным.
Стратегии замещения:
При загрузке компьютера все блоки кэш-памяти являются свободными. По мере работы происходит заполнение кэш-памяти, в результате чего наступает момент, когда свободные блоки отсутствуют. В этом случае при очередном кэш-промахе возникает проблема выбора блока – кандидата на удаление из кэш-памяти – с целью освобождения места для блока, пересылаемого из ОП. Эта проблема полностью отсутствует в кэш-памяти с прямым отображением, поскольку при таком способе организации существует единственная строка кэша, в которую может быть помещен новый блок.
В зависимости от используемого принципа отображения выбор блока – кандидата на удаление из кэш-памяти – осуществляется:
a) на всем множестве блоков для полностью ассоциативной кэш-памяти;
b) среди блоков, принадлежащих одному множеству для ассоциативной по множеству кэш-памяти;
c) среди множества секторов для кэш-памяти с распределением секторов.
К основным видам стратегии замещения блоков принято относить:
1) случайный выбор (RAND);
2) FIFO – First In First Out;
3) LFU – Least Frequency Used;
4) LRU – Least Recently Used.
При использовании принципа случайного выбора не предполагается выполнения анализа предыстории блоков, находящихся в кэш-памяти. Согласно стратегии RAND блок – кандидат на удаление – выбирается случайным образом (т.е. удален может быть любой из допустимого множества блоков кэш-памяти). Реализация принципа случайного выбора может быть осуществлена с помощью счетчика, содержимое которого инкрементируется с каким-либо периодом. Частным случаем такого счетчика может быть системный таймер. Значение в счетчике, в принципе, является случайным по отношению к процессу замещения блоков в кэш-памяти и может использоваться как номер блока – кандидата на удаление.
При реализации принципа FIFO удалению подлежит тот блок из допустимого множества блоков кэш-памяти, который раньше других был помещен в кэш. Физическая реализация этой стратегии может быть осуществлена с использованием принципа циклического буфера, в котором блоки выстраиваются в порядке их поступления в кэш. Блок – кандидат на удаление выбирается из вершины буфера.
Принцип LFU предполагает, что удалению из допустимого множества блоков кэш-памяти подлежит блок с наименьшей частотой обращений. Для реализации этого принципа необходимо каждый блок кэш-памяти снабдить счетчиком обращений, значение которого инкрементируется при обращении к блоку. Тогда при необходимости записать новый блок из ОП на место одного из блоков кэш-памяти анализируются значения счетчиков всех блоков из допустимого множества. Удалению подлежит блок с наименьшим значением счетчика обращений. Процесс выбора блока – кандидата на удаление завершается обнулением (сбросом) счетчиков обращений всех блоков кэш-памяти.
Наиболее употребительной при реализации кэш-памяти является стратегия LRU или её упрощенная модификация в виде Pseudo LRU. Данная стратегия предполагает, что удалению подлежит тот блок из допустимого множества блоков кэш-памяти, к которому наиболее долго не было обращения.