Степень ассоциативности

Алгоритм перезаписи.

Интеллектуальная предварительная загрузка

Некоторые современные контроллеры входящие в состав современных процессоров (и более тесно с ним взаимодействующие) работают несколько иначе, немного не так, как то было описано выше, в разделе 1.4.

А именно: они реализуют более сложный, более интеллектуальный механизм предварительной загрузки (предварительной загрузки строк), так называемый "интеллектуальную предварительную загрузку строк данных" (интеллектуальная предзагрузка, интеллектуальный префётч). Такие контроллеры постоянно отслеживают выполнение программ, следят за наличием в программе циклов, переходов, за тем как именно выполнились команды условного перехода, ведут статистику работу программы, и подгружают новые строки учитывая эти дополнительные данные, учитывая эту статистику. То есть такие контроллеры могут загружать в кэш память не только те строки к которым уже произошло обращение, но и какие другие фрагменты кода (строки), если алгоритм загрузки посчитает обращение к ним в ближайшее время повышенно вероятным. Использование интеллектуального префётча направленно на повышение процента попадания, а эффективность реализации этого алгоритма влияет на эффективность работу кэш памяти, и соответственно на производительность и реактивность ЭВМ.

При наличии свободного места в кэш новая строка подгружаемая в кэш, записывается на ранее незанятое место. Сложнее, когда записать на незанятое место уже невозможно. Тогда контроллеру кэш приходится удалять одну из старых строк. И желательно, если уж так, то чтобы та строка оказалась из числа менее востребованных (тех, к каким вероятность обращения ниже). Алгоритм, определяющий, какая имена из строк что могут быть удалены будет удалена (вытеснены из кэш новой записываемой в кэш строкой), называется "алгоритм перезаписи кэш". Две наиболее популярных реализации:

1. "Алгоритм самой старой" – удаляется строка та, которая была размещена в кэш раньше других строк.

2. "Алгоритм самой редкой" – удаляется строка та, к которой было наименьшее число обращений за некоторый предшествующий промежуток времени (за какой, тут возможны и варианты этого алгоритма).

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

На самом деле обычно всё не так просто, как было изложено в разделе 1.6. Дело в том, что из-за требований простоты и скорости реализации, большинство контроллеров кэш накладывает дополнительные ограничения на место размещения новой строки. Контроллеры, размещая в кэш новую строку, не могут разместить её на любом (произвольном) адресе кэш памяти. И ограничения эти могут быть очень жёсткими, вплоть до полного отсутствия выбора.

Степень ограничений которые накладывает реализация контроллера описываются параметром кэш памяти называемом "степенью ассоциативности кэш памяти". По степени ассоциативности кэш память делится:

1. "Не ассоциативная кэш память" (или "память прямого отображения", "одновходовая память").

При такой реализации ограничения максимальны, каждая отдельно взятая строка ОЗУ может быть размещена на единственно возможном, предопределённом месте в памяти. Даже если это место в кэш уже занято другой, ранее размещённой строкой, и если есть в кэш другое, свободное место, всё равно контроллер "памяти прямого отображения" разместит строку на этом месте. Естественно, вытеснив при этом из кэш памяти ранее размещённую на этом месте строку. Выбора нет, и описанные ранее, в разделе 1.6, алгоритмы перезаписи в данном случае не используются. Естественно это приводит к частому удалению нужных строк, тех к которым велика вероятность обращения, и снижению процента попаданий. Зато при этой реализации контроллера, во первых не требуется обеспечивать работу алгоритма перезаписи (проще и операции выполняемые контроллером при размещении в памяти новой строки будут выполнены быстрее, без каких дополнительных задержек), во вторых не потребуется хранить в кэш памяти признаков (КПП) адрес размещения строки в кэш памяти. В данном случае "адрес размещения строки в кэш" не извлекается из КПП, а очень просто определяется из запрошенного процессором "адреса ОЗУ" путём отбрасывания части разрядов "адреса ОЗУ" (так называемая операция "маскирования" адреса). Пусть мы имеем две строки, со следующими адресами ОЗУ:

а) 00011111

б) 10011111

Пусть адрес кэш получается из адреса ОЗУ простым отбрасыванием старших трёх разрядов. Тогда обе эти строки, при размещении в кэш будут размещаться на одном и том же адресе, и никогда не смогут быть размещены одновременно. Если одна из этих строк размещена в кэш, другая при своём размещении будет её вытеснять.

2. "Частично ассоциативный кэш со степенью ассоциативности два" (или "двухвходовая память").

При такой реализации у контроллера кэш уже появляется возможность выбора, пусть и ограниченного. Любая из строк ОЗУ что размещается в кэш может быть размещена, на выбор - на одном из двух возможных адресов кэш. На каком из двух возможных контроллер осуществит размещение, тут это уже будет определяться упомянутым в разделе 1.6 алгоритмом перезаписи. И, кроме того, размещая в кэш новую строку, контроллер кэш занесёт в кэш память признаков информацию о том, по какому именно из двух возможных адресов он осуществил размещение. Естественно и операции размещения новой строки, и операции выборки данных в этом случае будут выполняться несколько медленнее, зато возможно что не потребуется удалять из памяти ранее размещённую, и возможно ещё востребованную строку.

3. "Частично ассоциативный кэш со степенью ассоциативности 4" (и так далее, возможны варианты и со степенью ассоциативности 8, 16, 32.)

Степень ассоциативности (число входов) определяет число вариантов имеющихся у контроллера при размещении новой строки. Чем больше степень ассоциативности, тем сложнее реализация контроллера, тем больше дополнительных операций придётся выполнять, и при размещении новых строк, и при выборке данных по запросу процессора, и тем больший потребуется размер кэш памяти признаков, но тем меньше вероятность того, что при размещении новой строки придётся удалять из кэш памяти одну из старых, ещё востребованных строк.

4. "Полностью ассоциативный кэш"

Отсутствие ограничений на размещение новой строки. Только тут новая строка может быть размещена на любом свободном месте в кэш памяти, и никогда не потребуется удаление старых строк даже ещё и при наличии свободного места в кэш памяти.

1.8 Раздёлённый кэш

В системах кэш памяти низкой ассоциативности нередка ситуация когда, при выполнении программ, два или более фрагментов кода что конкурируют за одни и те же адреса в кэш памяти, постоянно вытесняют из кэш памяти друг друга. Особенно опасна ситуация что получила название "ситуация жестокой конкуренции", это когда ситуация с размещением в ОЗУ программного кода и кода данных складывается таким образом, что за одно и то же место в кэш начинают конкурировать строка содержащая программный код, и строка содержащая данные обрабатываемые этим кодом. Потери производительности ЭВМ в этом случае могут быть огромными. Для того, что бы полностью исключить вероятность проявления при выполнении программ "жестокой конкуренции", кэш память низкой степени ассоциативности обычно реализуется "разделённой" (разделённый кэш"). В этом случае кэш память выполняется в виде двух отдельных запоминающих устройств:

а) "кэш памяти команд" – в ней контроллер размещает только строки содержащие программный код;

б) "кэш памяти данных" - в ней контроллер размещает только строки содержащие код данных;