Повышение производительности вычислительных систем непосредственно связано с увеличением быстродействия и емкости памяти. Емкость памяти наиболее крупных вычислительных систем возросла от 1000 байт до десятков терабайт, а время цикла уменьшилось с 20 мкс до 10 нс. Однако даже с учетом прогресса в технологии быстродействующие запоминающие устройства остаются более дорогими, чем медленные. Следовательно, с целью уменьшения стоимости ВС при той же производительности эффективнее иметь иерархию памяти с небольшим по емкости запоминающим устройством, расположенным рядом с процессором и имеющим минимальное время доступа. Такая иерархия позволяет согласовать характеристики памяти и центрального процессора.
С ростом сложности а также размерности технических и научных задач возрастает требование к объему памяти. Рост объема памяти в свою очередь приводит к большим физическим размерам устройства, увеличению длины проводников и задержки распространения сигналов, т.е. уменьшается время доступа к такой памяти. Хотя быстродействие и емкость отдельных устройств памяти возросли, этого было не достаточно для того, чтобы они соответствовали характеристикам процессора. Конечно, можно реализовать память больших объемов, которая несколько быстрее имеющейся на данный момент при помощи совершеннейших технологий, существующих на данный момент. Однако стоимость такой памяти по отношению к увеличению ее производительности будет очень велика и использование такой памяти экономически невыгодно.
Компромиссом между производительностью и объемами памяти является решения использовать иерархию запоминающих устройств, т.е. применять в ВС так называемую иерархическую модель памяти. При хорошо построенной иерархической системе памяти среднее время доступа ко всей памяти лишь незначительно превышает время доступа к небольшому быстродействующему запоминающему устройству, а количество хранящейся информации равно емкости большой памяти. Идея иерархии запоминающих устройств в том или ином виде с самого начала была одной из важных концепций при разработке вычислительных систем.
Иерархическая память-это система памяти, состоящая как минимум из двух запоминающих устройств, отличающихся быстродействием и емкостью [1]. Обычно первое устройство памяти, расположенное в непосредственной близости от процессора, имеет малое время доступа и более высокую стоимость на бит. В связи с этим емкость более быстродействующей памяти в иерархии делается небольшой для того, чтобы оптимизировать стоимость всей системы. Технология памяти второго уровня иерархии выбирается исходя из низкой стоимости на один бит; такая память имеет большие значения времени цикла и времени доступа.
Иерархическая память управляется пользовательскими программами, аппаратным путем или системным программным обеспечением так, чтобы система памяти по времени доступа приближалась к быстродействующей памяти, а по стоимости - к медленной памяти. Примером иерархии, управляемой системным программным обеспечением, является организация виртуальной памяти со страничной организацией применяемая в данное время всеми современными операционными системами: недостаток емкости оперативной памяти возмещается внешней дисковой памятью.
Применение иерархических систем памяти оправдывает себя в следствие двух важных факторов - принципа локальности обращений и низкого (экономически выгодного) соотношения стоимость/производительность [1]. Принцип локальности обращений говорит о том, что большинство программ к счастью не выполняют обращений ко всем своим командам и данным равновероятно, а оказывают предпочтение некоторой части своего адресного пространства.
Иерархия памяти существует главным образом для того, чтобы повысить экономическую эффективность системы путем оптимального сочетания временных и стоимостных характеристик различных запоминающих устройств. Для того чтобы иерархия памяти была экономически эффективной, память должна иметь высокие эксплуатационные характеристики. Это означает, что технические параметры запоминающих устройств на разных уровнях иерархии должны существенно различаться. Невозможно достигнуть больших различий по эксплуатационным характеристикам и стоимости малой и большой памяти, если и та и другая выполнены по одной технологии и имеют близкие по значению времена доступа.
В системах с кэш-памятью быстрая и небольшая память, известная как буфер, или кэш, имеющая почти такое же быстродействие, как и регистры, расположена между процессором и основной памятью. Такой кэш согласует скорости процессора и основной памяти. Этот буфер совершенно незаметен, недоступен пользователям и не может быть непосредственно адресован. Однако использование кэша создает иллюзию, что большая основная память работает со скоростью процессора.
Иерархия памяти обычно состоит из многих уровней, но в каждый момент времени мы имеем дело только с двумя близлежащими уровнями. Минимальная единица информации, которая может либо присутствовать, либо отсутствовать в двухуровневой иерархии, называется блоком или строкой. Размер блока обычно фиксированный, а объем памяти является кратным размеру блока.
Успешное или неуспешное обращение к более высокому уровню называются соответственно попаданием (hit) или промахом (miss). Попадание - есть обращение к объекту в памяти, который найден на более высоком уровне, в то время как промах означает, что он не найден на этом уровне. Доля попаданий (hit rate) есть доля обращений, найденных на более высоком уровне. Доля промахов (miss rate) есть доля обращений, которые не найдены на более высоком уровне. Частота попаданий и промахов является важной характеристикой. Время обращения при попадании (hit time) есть время обращения к более высокому уровню иерархии, которое включает в себя, в частности, и время, необходимое для определения того, является ли обращение попаданием или промахом. Потери на промах (miss penalty) есть время для замещения блока в более высоком уровне на блок из более низкого уровня плюс время для пересылки этого блока в требуемое устройство (обычно в процессор). Потери на промах далее включают в себя две компоненты: время доступа (access time) - время обращения к первому слову блока при промахе, и время пересылки (transfer time) - дополнительное время для пересылки оставшихся слов блока. Время доступа связано с задержкой памяти более низкого уровня, в то время как время пересылки связано с полосой пропускания канала между устройствами памяти двух смежных уровней.
Основные характеристики современных моделей кэш памяти сведены в таблицу 1.1 [2]
Таблица 1.1 Основные характеристики современных моделей кэш памяти| Характеристика | Типичное значение |
| Размер блока (строки) | 4-128 байт |
| Время попадания (hit time) | 1-4 такта синхронизации (обычно 1 такт) |
| Потери при промахе (miss penalty) | 8-32 такта синхронизации |
| Время доступа (access time) | 6-10 тактов синхронизации |
| Время пересылки (transfer time) | 2-22 такта синхронизации |
| Доля промахов (miss rate) | 1%-20% |
| Размер кэш-памяти | 4 Кбайт - 16 Мбайт |
Для реализации системы кэш-памяти необходимо наличие таких элементов [1]
При построении систем с иерархической памятью ставится цель получения максимальной производительности подсистемы памяти при ее минимальной стоимости. Эффективность той или иной системы кэш-памяти зависит от стратегии управлений памятью. Стратегия управления памятью подразумевает ответ на такие вопросы: выбор метода отображения основной памяти в кэше; алгоритм взаимодействия между медленной основной и быстрой кэш-памятью; выбор стратегии замещения информации в кэше.
Существует три основных способа размещения блоков(строк) в кэш-памяти. По способу размещения блоков основной памяти в кэше различают кэш-память с прямым отображением (direct-mapped cache), частично ассоциативную кэш-память (или множественно ассоциативную кэш-память, set-associative cache) и полностью ассоциативную кэш-память (fully associative cache).
Кэш-память называется с прямым отображением, если каждый блок основной памяти имеет только одно фиксированное место, на котором он может появиться в кэш-памяти. Это наиболее простая организация кэш-памяти. Все блоки основной памяти, имеющие одинаковые младшие разряды в своем адресе, попадают в один блок кэш-памяти. При таком подходе справедливо соотношение:
(адрес блока кэш-памяти) = (адрес блока основной памяти) mod (число блоков в кэш-памяти)
Кэш-память называется полностью ассоциативной, если некоторый блок основной памяти может располагаться на любом месте кэш-памяти. Кэш-память называется частично ассоциативной, если некоторый блок основной памяти может располагаться на ограниченном множестве мест.
В современных процессорах как правило используется либо кэш-память с прямым отображением, либо двух- (четырех-) канальная множественно-ассоциативная кэш-память.
Алгоритмы взаимодействия (обмена, свопинга) между медленной основной и быстрой кэш-памятью приведены в главе 2.
Стратегии замещения информации в кэше определяет блок подлежащий замещению при возникновении промаха. Простота при использовании кэша с прямым отображением заключается в том, что аппаратные решения здесь наиболее простые: легко реализуется сама аппаратура, легко происходит замещение данных. При замещении просто нечего выбирать - на попадание проверяется только один блок и только этот блок может быть замещен. При полностью ассоциативной или множественно-ассоциативной организации кэш-памяти имеются несколько блоков, из которых надо выбрать кандидата в случае промаха. Как правило для замещения блоков применяются две основных стратегии: случайная и LRU-стратегия.
В первом случае, чтобы иметь равномерное распределение, блоки-кандидаты выбираются случайно. В некоторых системах, чтобы получить воспроизводимое поведение, которое особенно полезно во время отладки аппаратуры, используют псевдослучайный алгоритм замещения.
Во втором случае, чтобы уменьшить вероятность выбрасывания информации, которая скоро может потребоваться, все обращения к блокам фиксируются. Заменяется тот блок, который не использовался дольше всех (LRU - Least-Recently Used).
Достоинство случайного способа заключается в том, что его проще реализовать в аппаратуре. Когда количество блоков увеличивается, алгоритм LRU становится все более дорогим и часто только приближенным [2]. В таблице 1.2 показаны различия в долях промахов при использовании алгоритма замещения LRU и случайного алгоритма [2].
Таблица 1.2 Влияние стратегии замещения на долю промаха при разных размерах кэш-памяти и ассоциативности.| Ассоциативность Размер кэш-памяти |
2-канальная стратегия | 4-канальная стратегия | 8-канальная стратегия | |||
| LRU | Random | LRU | Random | LRU | Random | |
| 16 KB | 5.18 | 5.69 | 4.67 | 5.29 | 4.39 | 4.96 |
| 64 KB | 1.88 | 2.01 | 1.54 | 1.66 | 1.39 | 1.53 |
| 256 KB | 1.15 | 1.17 | 1.13 | 1.13 | 1.12 | 1.12 |
Из таблицы видно, что при большом размере кэш памяти стратегии замещения не имеет существенного различия в эффективности памяти.
При использовании иерархической памяти для каждого элемента данных должна быть обеспечена когерентность (согласованность, одинаковость) его копий, в разных уровнях иерархии. Для многопроцессорной ЭВМ, дело осложняется и тем, что одни и те де данные могут требоваться различными процессорами.
Как уже было замечено ранее, механизмы реализации когерентности могут быть как явными, так и неявными для прикладного программиста. Современные микропроцессоры имеют один или несколько уровней внутрикристальной кэш-памяти. Поэтому интерфейс микропроцессоров с необходимостью включает механизм организации когерентности внутрикристальной кэш-памяти и внекристальной памяти. Внекристальная память может также быть многоуровневой: состоять из кэш-памяти и основной памяти.
Реализация механизма когерентности в ВС с разделяемой памятью требует аппаратурно-временных затрат. Причем уменьшить временную составляющую затрат можно за счет увеличения аппаратурной составляющей и наоборот. Уменьшение временной составляющей требует создания специализированной аппаратуры реализации когерентности. Уменьшение аппаратурной составляющей предусматривает некоторый минимум аппаратных средств, на которых осуществляется программная реализация механизма когерентности.
Характеристики иерархической системы памяти, можно разделить на две группы: внутренние и внешние. Эффективное быстродействие буфера и эффективная стоимость представляют собой внутренние характеристики. Внешними характеристиками, являются: вероятность удачного обращения, размещение буфера, емкость буфера, размер блока, алгоритмы управления, отображение адресов, отношение значений времени обращения для чтения и записи, алгоритмы записи, число модулей основной памяти и последовательность обращения к ним, эффективная задержка или время ожидания для одного модуля, эффективная средняя задержка или время ожидания для нескольких модулей.
Внешние характеристики устанавливаются опытным путем или моделированием и используются при проектировании в качестве исходных данных.