3.2.3. Частично ассоциативная кэш память

(Множественно ассоциативная КЭШ память)

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

Сравнение тегов КЭШа с тегом адреса происходит только для строк, входящих в выбранный набор. При совпадении тега адреса с одним из тегов набора происходит чтение байта из КЭШа (КЭШ попадание). Если такого совпадения нет (КЭШ промах), то происходит обращение к ОЗУ.

Подобную архитектуру имеет подавляющее число процессоров Intel, начиная с 80486 DX (предшественник Pentium). По количеству строк КЭШа, входящих в набор, КЭШ-память может называться двухвходовой (две строки КЭШа в одном наборе), четырех-входовой, восьми –входовой – и так далее.

Такая архитектура еще называется множественно-ассоциативной.

Некоторые процессоры имеют раздельные КЭШ для команд и данных. Раздельный КЭШ позволяет производить выборку команд и данных одновременно, что ведет к повышению производительности процессора. Однако, такая организация КЭШа имеет недостаток. Например, в программе требуется больше памяти для команд и меньше для данных. В этом случае КЭШ данных будет недогружен, но использовать его свободные строки для записи команд нельзя в силу разделенности двух типов КЭШа.

Раздельные КЭШ для команд и данных имеет, например, процессор фирмы Intel Pentium. (два КЭШа с двухвходовой частично-ассоциативной архитектурой ).

Смешанную архитектуру (один КЭШ как для команд, так и для данных) имеет процессор Alpha фирмы DEC.

3.3 Алгоритм замещения строк в кэш памяти

Среднее время доступа к КЭШ памяти можно определить следующим образом:

t_ср = t_обр + Р_пр * t_пр,

где:

t_обр - время обращения при попадании;

Р_пр - потери времени при промахе;

t_пр – вероятность промаха.

Из приведенной формулы видно, что для уменьшения среднего времени доступа t_ср к КЭШ необходимо уменьшить потери времени при промахе, время обращения при попадании и вероятность промахов. При увеличении объема КЭШ памяти вероятность промахов как правило уменьшается. Кроме объема КЭШ памяти на вероятность промахов влияет так же и алгоритм замещения строк КЭШа. Наиболее простой алгоритм замещения используется в КЭШ памяти с прямым отображением, когда замещается та строка, к которой было неудачное обращение (КЭШ промах). Этот алгоритм имеет простое аппаратное решение и существенный недостаток, который ведет к увеличению вероятности промахов, если две строки ОЗУ, претендующих на одну и ту же строку КЭШа, используются одинаково часто.

В полностью ассоциативной и множественно ассоциативной КЭШ памяти имеется возможность использовать более сложные алгоритмы замещения, которые позволяют устранить недостаток организации КЭШа с прямым отражением. На практике наиболее часто используются случайные и LRU алгоритмы замещения строк памяти.

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

В алгоритме LRU удаляется из КЭШ памяти та строка, которая дольше всех не использовалась. Least – Recently Used (LRU) – это алгоритм, имеющий более сложную аппаратную реализацию, поскольку необходимо фиксировать все обращения к строкам для определения той строки, к которой дольше всех не было обращения.

Ассоциативность	2-ух канальная		4-ех канальная		8-ми канальная
Размер КЭШ-памяти	LRU	Random	LRU	Random	LRU	Random
16 Кбайт	5.18%	5.69%	4.67%	5.29%	4.39%	4.96%
64 Кбайт	1.88%	2.01%	1.54%	1.66%	1.39%	1.53%
256 Кбайт	1.15%	1.17%	1.13%	1.13%	1.12%	1.12%

В таблице приведены вероятности промахов для LRU и случайного (Random) алгоритмов при нескольких размеров КЭШа и разной канальности множественно-ассоциативной КЭШ - памяти. Размер строки КЭШа при этом брался равным 16 байт.

При увеличении объема КЭШ - памяти алгоритм LRU становится все более сложным и дорогим, а главное, не позволяет существенно снизить вероятность промахов по сравнению со случайным алгоритмом. Уже при объеме КЭШ памяти 256 кБ, алгоритм LRU практически не имеет преимуществ по сравнению со случайным алгоритмом, и поэтому при больших размерах КЭШа не используется, а используется случайный алгоритм.