Организация кэш-памяти современных процессоров

«Курсировать» между  оперативной памятью и кэшем, и пользы от кэша в этом случае будет мало.

3. АССОЦИАТИВНАЯ  ФУНКЦИЯ ОТОБРАЖЕНИЯ

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

На рисунке №6 схематически представлено соответствие между содержимым строк кэша и блоков оперативной памяти при реализации ассоциативной функции отображения. Код адреса в оперативной памяти рассматривается как состоящий из двух полей: 22-разрядного поля тэга и 2-разрядного поля номера байта. Таким образом, в каждой строке кэша нужно хранить помимо блока данных длиной в 4 байт (32 бит) еще и 22-разрядный код тэга этого блока. Так 24-разрядному адресу 16339С будет соответствовать 22-разрядный код тэга 058СЕ7 (коды представляются в шестнадцатеричной нотации). Как формируется такой код, легко проследить, если воспользоваться двоичной нотацией:

Применение ассоциативной  функции отображения обеспечивает известную гибкость при распределении  данных между строками кэша, поскольку позволяет применять более сложные алгоритмы при выборе строк, в которые считывается очередной блок из оперативной памяти. Эти алгоритмы, о которых речь пойдет в одном из последующих разделов, позволяют так организовать обновление строк, что вероятность обнаружения нужного слова данных в кэше (кэш-попадания – hit in cache) значительно возрастает, а это значит, что значительно реже нужно обращаться за новыми данными к оперативной памяти. Но все имеет свою цену – как мы убедились на рассмотренном простом примере, блок кэш памяти должен располагать ресурсами хранения информации, более чем в полтора раза превышающими объем полезной информации. Логические схемы анализа и сравнения тэгов при такой схеме также значительно сложнее, чем при использовании простой функции отображения.

4. СЕКЦИОНИРОВАННАЯ  АССОЦИАТИВНАЯ ФУНКЦИЯ ОТОБРАЖЕНИЯ

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

m=v*k, i = j mod v, где

i – номер секции кэша;

j – номер блока в оперативной памяти;

m – общее количество строк в кэше.

В каждой секции используется ассоциативная функция отображения, и блок B_j может быть передан в любую строку секции i. Схемы управления блока кэш-памяти анализируют три поля в составе кода адреса, поступившего от процессора: тэг, номер секции, и номер слова (байта). Поле номера секции имеет длину d разрядов, и задает одну из v=2^d секций. Поле тэга длиной s разрядов совместно с полем номера секции определяют один из 2^s блоков в оперативной памяти, который может быть помещен в любую строку этой секции. На рисунке №5 приведена схема управления блоком кэш-памяти, в котором использована секционированная ассоциативная функция отображения. При использовании чисто ассоциативной функции поле тэга в строке кэша имело довольно большую длину и значение тэга из кода адреса, полученного от процессора, нужно было сравнить со значениями в полях тэга всех строк кэша. При использовании секционированной ассоциативной функции поле тэга в коде адреса имеет несколько меньшую длину, и при анализе адреса это поле нужно сравнивать только с полями тэгов строк одной секции (обычно их бывает 2, 4 или 8).

На рисунке №5 схематически представлено соответствие между содержимым строк кэша и блоков оперативной памяти при реализации секционированной ассоциативной функции отображения. Каждая секция включает две строки кэша и, следовательно, номер секции задается 13-разрядным двоичным числом. Блоки в оперативной памяти, номера которых, взятые по модулю 2¹³, совпадают с номером секции, будут отображаться на строки этой секции кэша. Так блоки 000000, 00A000, ..., FF4000 будут отображаться на строки секции 0. Каждый из этих блоков может быть помещен в любую из двух строк секции 0. Важно, что ни один из двух блоков, которые отображаются на одну и ту же секцию, не имеют одинаковых кодов тэга. При выполнении операции чтения 13-разрядный номер секции определяет, какую из двухстрочных секций кэша следует анализировать на предмет того, не содержится ли в ней искомый блок. При этом анализируются поля тэгов обеих строк секции.

Если v=m, k=1, то секционированная ассоциативная функция сводится к прямой функции отображения, а при v=1, k=m секционированная ассоциативная функция сводится к чистой ассоциативной. Разделение кэша на 2-строчные секции (v=m/2, k=2) – самый распространенный вариант использования секционированной ассоциативной функции, который дает наибольший прирост эффективности по сравнению с прямой функцией отображения. Если еще более увеличить размер секции – включить в нее 4 строки (v = m/4, k = 4), – то повышение эффективности кэша будет довольно скромным. Дальнейшее увеличение размера секции оказывает очень незначительное влияние на повышение эффективности.

5. Алгоритм замены строк кэша

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

Возможно, наиболее эффективным  является алгоритм LRU (least recently used), предполагающий выбор той из строк – кандидатов на замену, к которой дольше всего не обращался процессор. Вполне резонно предположить, что процессору скорее понадобится информация из той строки, к которой он недавно обращался, и, следовательно, этот алгоритм обеспечит более эффективное в вероятностном смысле использование кэша. Алгоритм LRU реализуется довольно просто, если в кэше использована 2-строчная секционированная ассоциативная функция отображения. В состав строки включается специальный бит USE. При каждом обращении к строке в ее бите USE устанавливается 1, а в бите USE второй строки той же секции устанавливается 0. Когда возникает необходимость записать в эту секцию новый блок, выбирается строка, бит USE которой равен 0.

Другой вариант – алгоритм FIFO (first in, first out), который реализует принцип «первым вошел – первым вышел». При этом новый блок записывается в ту из строк секции, в которую текущая информация была записана раньше, чем в другие. Алгоритм FIFO несложно реализовать, используя принцип циклического буфера.

Алгоритм LFU (least frequently used) предполагает выбор той из строк – кандидатов на замену, к которой процессор обращался реже всего. Для реализации этого алгоритма необходимо включить в состав строки поле счетчика обращений и анализировать счетчики всех строк секции, когда возникает необходимость записи в эту секцию нового блока из оперативной памяти.

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

6. Целостность информации в кэше и оперативной памяти

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

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

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

Возможны различные  варианты решения этой задачи – варианты политики поддержания информационной целостности, – которые отличаются эффективностью и накладными расходами. Самый простой вариант получил наименование сквозной записи (write through). Предлагается все операции записи сразу же дублировать в оперативной памяти, не дожидаясь момента, когда нужно будет заменить содержимое соответствующей строки кэша. В результате, можно всегда быть уверенным в том, что в оперативной памяти хранится самая свежая, а значит, в любой момент времени достоверная, информация. В мультипроцессорной компьютерной системе все остальные процессоры должны следить за обновлением информации в оперативной памяти и соответственно обновлять содержимое своих блоков кэш-памяти. Думаю, читателю совершенно ясно, в чем недостаток такой политики, – создается очень интенсивный поток обмена информацией между оперативной памятью и процессорами, который может свести на нет все преимущества мультипроцессорной системы.

Альтернативный вариант – обратная запись (write back) – минимизирует количество обращений к оперативной памяти. В этом варианте процессор вносит изменения только в содержимое своего кэша. При изменении содержимого определенной строки в специальном бите UPDATE этой строки устанавливается 1. Когда возникает необходимость очистить эту строку для приема нового блока из оперативной памяти, анализируется бит UPDATE. Если этот бит установлен, содержимое строки переписывается в оперативную память. Очевидно, что при та кой политике блок оперативной памяти некоторое время содержит неверную, устаревшую информацию и, следовательно, если к нему в это время обратится модуль ввода-вывода, обращение нужно будет каким-то образом переадресовать кэшу. Реализация такого алгоритма серьезно усложняет компоненты системы, и процедура проверки достоверности данных может стать ее узким местом. Эксперименты показали, что на долю операций записи приходится примерно 15% всех обращений к памяти.

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

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

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