Архитектура кэш-памяти.

Архитектура кэш-памяти.

 В зависимости от способа определения взаимного соответствия строки кэша и обла­сти основной памяти различают три архитектуры кэш-памяти: кэш с прямым отобра­жением, полностью ассоциативный кэш-память, частично- или наборно-ассоциативная кэш-память.

Кэш-память с прямым отображением.

В кэш-памяти прямого отображения адрес памяти, по которому происходит обра­щение, однозначно определяет строку кэша, в которой может находиться требуе­мый блок. Принцип работы такого кэша поясним на примере несекторированного кэша объемом 256 Кбайт с размером строки 32 байта и объемом кэшируемой основной памяти 64 Мбайт -  типичный кэш системной платы для Pentium. Структуру кэш-памяти в такой системе иллюстрирует рис. 1. Кэшируемая основная память условно разбивается на страницы (в данном случае по 256 Кбайт), размер которых совпадает с размером кэш-памяти (256 Кбайт). Кэш­-память (и, условно - страницы основной памяти) делится на строки (256 Кбайт/ 32 байт - 8 К строк). Архитектура прямого отображения подразумевает, что каж­дая строка кэша может отображать из любой страницы кэшируемой памяти толь­ко соответствующую ей строку. Поскольку объем основной памяти много больше объема кэша, на каждую строку кэша может претендовать множество блоков памяти с одинаковой младшей частью адреса, которую называют  смещением внутри страницы (0 – множество, 1-множество, 2-ьножество … N-множество 32-х байтных блоков). Одна строка в определен­ный момент может содержать копию только одного из этих блоков. Номер строки является адресом строки в кэш-памяти, а тег несет ин­формацию о том, какой именно блок занимает данную строку (тег это старшая часть адреса, выставленного процессором при обращении в память или, иначе говоря, номер страницы). Память тегов должна иметь количество ячеек, равное количеству строк кэша, а ее разрядность должна быть достаточной, чтобы вместить старшие биты адреса кэшируемой памяти, не попавшие на шину адреса кэш-памяти. Кроме адресной части тега, с каждой строкой кэша связаны биты признаков действительности и модифицированности данных. В начале каждого обращения к оперативной памяти контроллер кэш-памяти, первым делом, счи­тывает ячейку памяти тэгов с адресом строки, определяемым разрядами А17-А5, сравнивает содержимое этой строки памяти тэгов с разрядами А25-А18 адреса памяти, выставленного процессором, и анализирует признак действительности.

Рис. 1. Кэш с прямым отображением.

Этот анализ выполняется в специальном цикле слежения, который иногда называют циклом запроса. Если в результате анализа выясняется, что требуемого блока нет в кэше, генерируется (или продолжается) цикл обращения к основной памяти (кэш-промах). В случае попадания запрос обслуживается кэш­-памятью. В случае промаха после считывания из основной памяти приемником ин­формации новые данные помещаются в строку кэша (если она чистая), а в ее тег помещаются старшие биты адреса и устанавливается признак действительности данных. Независимо от объема затребованных данных в кэш из основной памя­ти строка переписывается вся целиком (поскольку признак действительности относится ко всем ее байтам). Если контроллер кэша реализует упреждающее считывание, то в последующие свободные циклы шины обновляется также следующая строка (если она была чистой). Чтение «про запас» позволяет при необходимости осуществлять пакетный цикл чтения из кэша через границу строки.  Такой кэш имеет самую простую аппаратную реализацию и применяется во вторич­ном кэше большинства системных плат. Однако ему присущ серьезный недоста­ток. Если в процессе выполнения программы процессор поочередно будет обращаться по одному и тому же адресу строки, но разными или циклически изменяющимися номерами тэгов, то постоянно будут фиксироваться кэш-промахи и кэш-память вместо ускорения будет вносить замедление в обмен с памятью. Переклю­чение страниц в многозадачных операционных системах (ОС) также снижает количество кэш-попаданий, что отражается на производительности системы. Увеличение размера кэша при сохранении архитектуры прямого отображения даст не очень существенный эф­фект, поскольку разные задачи будут претендовать на одни и те же строки кэша. Не увеличивая объема кэша, .можно повысить эффективность кэширования изме­нением его структуры, о чем пойдет речь ниже.

Иногда в описании кэша прямого отображения фигурирует понятие набор, которое применяется вместо термина строка в секторированном кэше прямого отображения, а сектор тогда называют строкой. С набо­ром (как и строкой несекторированного кэша) связана информация о теге, отно­сящаяся ко всем элементам набора (строкам или секторам). Кроме того, каждый элемент набора (строка или сектор) имеет собственный бит действительности (рис. 2).

Рис. 2. Секторированный кэш прямого отображения

Наборно-ассоциативный (частично-ассоциативный) кэш.

Наборно-ассоцативная архитектура КЭШа (рис. 3) позволяет каждому блоку кэшируемой памяти претендовать на одну из нескольких строк кэша, объединенных в набор. В этой архитектуре есть, как бы, несколько параллельно и согласованно работающих каналов прямого отображения, где контроллеру кэша приходится при­нимать решение о том, в какую из строк набора помещать очередной блок данных. Например, в простейшем случае каждый блок памяти может помещаться в одну из четырех строк набора (четырехканальный наборно-ассоциативный кэш). Номер набора, в котором может отображаться затребованный блок дан­ных, однозначно определяется средней частью адреса (как номер строки в кэше прямого отображения). Строка набора, отображающая требуемый блок, опреде­ляется сравнением тегов (как и в ассоциативном кэше), параллельно выполняе­мым для всех строк памяти тэгов данного набора (каналов кэша). Кроме того, с каждым набором должен быть связан признак, определяющий строку набора, подлежащую замещению новым блоком данных в случае кэш-промаха (на рисунке в ее сторону указывает стрелка).

Рис. 3. Четырехканальный наборно-ассоциативный кэш

 Канди­датом на замещение обычно выбирается строка, к которой дольше всего не обраща­лись (алгоритм LRU - Least Recently Used). При относительно большом количе­стве каналов (строк в наборе) прибегают к некоторому упрощению - алгоритм Pseudo-LRU для четырех строк позволяет при­нимать решения, используя всего 3 бита.

Возможно также применение алгоритма замещения FIFO (первым вошел - первым вышел) или даже случайного замещения, что проще, но менее эффективно. Наборно-ассоциативная архитектура широко применяется для первичного кэша современных процессоров.

Ассоциативный кэш.

В отличие от предыдущих у полностью ассоциативного кэша любая его строка может отображать любой блок памяти, что существенно повышает эффективность использования ограниченного объема кэша. При этом все биты

Рис. 4. Полностью ассоциативная кэш-память.

 Адреса кэшированного блока, за вычетом битов, определяющих положение (смещение) данных в строке, хранятся в памяти тегов. В такой архитектуре (рис. 4) для определения наличия затребованных данных в кэш-памяти требуется сравнение со старшей частью ад­реса тегов всех строк памяти тэгов, а не одной или нескольких, как при прямом отображении или наборно-ассоциативной архитектуре. Последовательный пере­бор ячеек памяти тегов отпадает. (на это требуется слишком много времени), поэтому остается параллельное сравнение тэгов всех ячеек, а это является сложной аппаратной за­дачей, которая приемлемо решаема только для небольших объемов первичного кэша (процессор М2 Cyrix).