4.3. Способы организация кэш-памяти

43.1. Общие сведения

В функциональном отношении кэш-память рассматривается как буфер­ное ЗУ, размещённое между основной (оперативной) памятью и процессо­ром. Основное назначение кэш-памяти — кратковременное хранение и выда­ча активной информации процессору, что сокращает число обращений к ос­новной памяти, скорость работы которой меньше, чем кэш-памяти.

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

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

Типовая структура кэш-памяти

Рассмотрим типовую структуру кэш-памяти (рис. 4.4), включающую ос­новные блоки, которые обеспечивают её взаимодействие с ОП и централь­ным процессором.

Строки, составленные из информационных слов, и связанные с ними ад­ресные теги хранятся в накопителе, который является основой кэш-памяти. Адрес требуемого слова, поступающий от центрального процессора (ЦП), вводится в блок обработки адресов, в котором реализуются принятые в дан­ной кэш-памяти принципы использования адресов при организации их срав­нения с адресными тегами. Само сравнение производится в блоке сравнения адресов (БСА), который конструктивно совмещается с накопителем, если кэш-память строится по схеме ассоциативной памяти. Назначение БСА со­стоит в выявлении попадания или промаха при обработке запросов от цен­трального процессора. Если имеет место кэш-попадание (т.е. искомое слово хранится в кэш-памяти, о чём свидетельствует совпадение кодов адреса, по­ступающего от центрального процессора, и одного из адресов некоторого ад­ресного тега), то соответствующая строка из кэш-памяти переписывается в регистр строк. С помощью селектора-демультиплексора из неё выделяется искомое слово, которое и направляется в центральный процессор. В случае промаха с помощью блока формирования запросов осуществляется инициа­лизация выборки из ОП необходимой строки. Адресация ОП при этом произ­водится в соответствии с информацией, поступившей от центрального про­цессора. Выбираемая из памяти строка вместе со своим адресным тегом по­мещается в накопитель и регистр строк, а затем искомое слово передается в центральный процессор.

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

4.3.2. Способы размещения данных в кэш-памяти

Существует четыре способа размещения данных в кэш-памяти: прямое распределение, полностью ассоциативное распределение, частично ассоциа­тивное распределение и распределение секторов. Ниже подробно описан ка­ждый способ размещения и его механизм преобразования адресов. Для того, чтобы конкретизировать описание, положим, что кэш-память может содер­жать 128 строк, размер строки - 16 слов, а основная память может содержать 16384 строк. Для адресации основной памяти используется 18 бит.

Из них старшие 14 показывают адрес строки, а младшие 4 бит — адрес слова внутри этой строки. При одном обращении к памяти выбирается одна строка. 128 строк кэш-памяти указываются 7-разрядными адресами.

Прямое распределение

При прямом распределении место хранения строк в кэш-памяти одно­значно определяется по адресу строки.

Структура кэш-памяти показана на рис. 4.5.

Рис.4.5. Структура кэш-памяти с прямым распределением

Адрес основной памяти состоит из 14-разрядного адреса строки и 4-разрядного адреса слова внутри этой строки. Адрес строки подразделяется на тег (старшие 7 бит) и индекс (младшие 7 бит).

Для того, чтобы поместить в кэш-память строку из основной памяти с адресом bn, выбирается область внутри кэш-памяти с адресом be, который равен 7 младшим битам адреса строки bn. Преобразование из bn в Ьс сводит­ся только к выборке младших 7 бит адреса строки. По адресу be в кэш-памяти может быть помещена любая из 128 строк основной памяти, имеющих адрес, 7 младших битов которого равны адресу be. Для того чтобы определить, ка­кая именно строка хранится в данное время в кэш-памяти, используется па­мять ёмкостью 7 бит х 128 слов, в которую помещается по соответствующему адресу в качестве тега 7 старших битов адреса строки, хранящейся в дан­ное время по адресу be кэш-памяти. Это специальная память, называемая те­говой памятью. Память, в которой хранятся строки, помещенные в кэш, на­зываются памятью данных. В качестве адреса теговой памяти используются младшие 7 битов адреса строки.

Из теговой памяти считывается тег. Параллельно этому осуществляется доступ к памяти данных с помощью 11 младших битов адреса основной па­мяти (используется 7 разрядов индекса и 4 разряда адреса слова внутри стро­ки). Если считанный из теговой памяти тег и старшие 7 бит адреса основной памяти совпадают, то это означает, что данная строка существует в памяти данных, т.е. осуществляется кэш-попадание.

Если тег отличается от старших 7 бит (кэш-промах), то из основной па­мяти считывается соответствующая строка, а из кэш-памяти удаляется стро­ка, определяемая 7 младшими разрядами адреса строки, и на его место поме­щается строка, считанная из основной памяти. Осуществляется также обнов­ление соответствующего тега в теговой памяти.

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

Полностью ассоциативное распределение

При полностью ассоциативном распределении допускается размещение каждой строки основной памяти на месте любой строки кэш-памяти. Струк­тура кэш-памяти с полностью ассоциативным распределением представлена на рис. 4.6.

Адрес основной памяти состоит из 14-разрядного адреса строки (тега) и 4-разрядного адреса внутри строки.

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

При совпадении ключа с одним из тегов теговой памяти (кэш-попадание) происходит выборка соответствующего данному тегу адреса и обращение к памяти данных. Входной информацией для памяти данных является 11-разрядное слово (7 бит адреса строки и 4 бит адреса слова в данной.

При несовпадении ключа ни с одним из тегов теговой памяти (кэш-Промах) осуществляется обращение к основной памяти и чтение необходи­мой строки.                                                   По этому способу при замене строк кандидатом на удаление могут быть

все строки в кэш-памяти.

Рис.4.6. Структура кэш-памяти с полностью ассоциативным распределением

Частично ассоциативное распределение

При данном способе несколько соседних строк (фиксированное число, не менее двух) из 128 строк кэш-памяти образуют структуру, называемую

Структура кэш-памяти, основанная на использовании частично ассоциа­тивного распределения, показана на рис. 4.7. В данном случае в одну группу входят 4 строки.

Рис.4.7. Структура кэш-памяти с частично ассоциативным распределением

Адрес строки основной памяти (14 бит) разделяется на две части: b - тег (старшие 9 бит) и е - адрес группы (младшие 5 бит). Адрес строки внутри кэш-памяти, состоящий из 7 бит, разделяется на адрес группы (5 бит) и адрес строки внутри группы (2 бит).

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

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

Когда центральный процессор запрашивает доступ по i-му адресу, то осуществляется обращение к массиву тегов по адресу е, выбирается группа из четырёх тегов (а, b, с, d), каждый из которых сравнивается со старшими 9 битами (b) адреса строки. На выходе четырех схем сравнения формируется унитарный код совпадения (0100), который на шифраторе преобразуется в двухразрядный позиционный код, служащий адресом для выбора банка дан­ных^!).

Одновременно осуществляется обращение к массиву данных по адресу

e.f(9 бит) и считывание из банка V;, требуемой строки иди слова.

При пересылке новой строки в кэш-память удаляемая из нее строка вы­бирается из четырех строк соответствующего набора (группы).

Распределение секторов

По данному методу основная память разбивается на секторы, состоящие из фиксированного числа строк, кэш-память также разбивается на секторы, состоящие из такого же числа строк. Рассмотрим случай, когда длина строки равна 16 словам, а сектор состоит из 16 строк. Структура кэш-памяти с рас­пределением секторов представлена на рис. 4.8. В адресе основной памяти старшие 10 бит показывают номер сектора, следующие 4 бит — номер строки внутри сектора, а младшие 4 бит — адрес слова в строке.

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

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

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

43.3. Методы обновления строк основной памяти

В табл. 4.1 приведены условия сохранения и обновления информации в ячейках кэш-памяти и основной памяти.

Таблица 4.1

Условия сохранения и обновления информации

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

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

Сквозная запись

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

Обратная запись

По методу обратной записи, если адрес объектов, по которым есть за­прос обновления, существует в кэш-памяти, то обновляется только кэш­память, а основная память не обновляется. Если адреса объекта обновления нет в кэш-памяти, то в неё из основной памяти пересылается строка, содер­жащая этот адрес, после чего обновляется только кэш-память. По методу об­ратной записи в случае замены строк удаляемую строку необходимо также пересылать в основную память. У этого метода существуют две разновидно­сти: метод SWB (простая обратная запись), по которому удаляемая строка возвращается в основную память, и метод FWB (флатовая обратная запись), по которому в основную память записывается только обновлённая строка кэш-памяти. В последнем случае каждая область строки в кэш-памяти снаб­жается однобитовым флагом, который показывает, было или нет обновление строки, хранящейся в кэш-памяти.

Метод FWB обладает достаточной эффективностью, однако более эф­фективным считается метод FPWB (флатовая регистровая обратная запись), в котором благодаря размещению буфера между кэш-памятью и основной па­мятью предотвращается конфликт между удалением и выборкой строк.

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

4.3.4. Методы замещения строк кэш-памяти

Способ определения строки, удаляемой из кэш-памяти, называется стратегией замещения. Для замещения строк кэш-памяти существует не­сколько методов: метод замещения наиболее давнего по использованию объ­екта — строки, метод LRU (замещение наименее используемой информации);

метод FIFO (первым пришёл — первым вышел) и метод произвольного за­мещения.. В первом случае среди строк, являющихся объектами замещения, выбирается строка, к которой наиболее длительное время не было обраще­ний. По методу FIFO среди всех строк, являющихся объектами замещения, выбирается та, которая самой первой была переслана в кэш-память. И нако­нец, по последнему методу строка выбирается произвольно. Реализация этих методов упрощается в указанной последовательности, но наибольшим эф­фектом обладает метод замещения наиболее давнего по использованию объ­екта (строки).

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

по мере увеличения числа строк.

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

43.1. Общие сведения

В функциональном отношении кэш-память рассматривается как буфер­ное ЗУ, размещённое между основной (оперативной) памятью и процессо­ром. Основное назначение кэш-памяти — кратковременное хранение и выда­ча активной информации процессору, что сокращает число обращений к ос­новной памяти, скорость работы которой меньше, чем кэш-памяти.

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

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

Типовая структура кэш-памяти

Рассмотрим типовую структуру кэш-памяти (рис. 4.4), включающую ос­новные блоки, которые обеспечивают её взаимодействие с ОП и централь­ным процессором.

Строки, составленные из информационных слов, и связанные с ними ад­ресные теги хранятся в накопителе, который является основой кэш-памяти. Адрес требуемого слова, поступающий от центрального процессора (ЦП), вводится в блок обработки адресов, в котором реализуются принятые в дан­ной кэш-памяти принципы использования адресов при организации их срав­нения с адресными тегами. Само сравнение производится в блоке сравнения адресов (БСА), который конструктивно совмещается с накопителем, если кэш-память строится по схеме ассоциативной памяти. Назначение БСА со­стоит в выявлении попадания или промаха при обработке запросов от цен­трального процессора. Если имеет место кэш-попадание (т.е. искомое слово хранится в кэш-памяти, о чём свидетельствует совпадение кодов адреса, по­ступающего от центрального процессора, и одного из адресов некоторого ад­ресного тега), то соответствующая строка из кэш-памяти переписывается в регистр строк. С помощью селектора-демультиплексора из неё выделяется искомое слово, которое и направляется в центральный процессор. В случае промаха с помощью блока формирования запросов осуществляется инициа­лизация выборки из ОП необходимой строки. Адресация ОП при этом произ­водится в соответствии с информацией, поступившей от центрального про­цессора. Выбираемая из памяти строка вместе со своим адресным тегом по­мещается в накопитель и регистр строк, а затем искомое слово передается в центральный процессор.

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

4.3.2. Способы размещения данных в кэш-памяти

Существует четыре способа размещения данных в кэш-памяти: прямое распределение, полностью ассоциативное распределение, частично ассоциа­тивное распределение и распределение секторов. Ниже подробно описан ка­ждый способ размещения и его механизм преобразования адресов. Для того, чтобы конкретизировать описание, положим, что кэш-память может содер­жать 128 строк, размер строки - 16 слов, а основная память может содержать 16384 строк. Для адресации основной памяти используется 18 бит.

Из них старшие 14 показывают адрес строки, а младшие 4 бит — адрес слова внутри этой строки. При одном обращении к памяти выбирается одна строка. 128 строк кэш-памяти указываются 7-разрядными адресами.

Прямое распределение

При прямом распределении место хранения строк в кэш-памяти одно­значно определяется по адресу строки.

Структура кэш-памяти показана на рис. 4.5.

Рис.4.5. Структура кэш-памяти с прямым распределением

Адрес основной памяти состоит из 14-разрядного адреса строки и 4-разрядного адреса слова внутри этой строки. Адрес строки подразделяется на тег (старшие 7 бит) и индекс (младшие 7 бит).

Для того, чтобы поместить в кэш-память строку из основной памяти с адресом bn, выбирается область внутри кэш-памяти с адресом be, который равен 7 младшим битам адреса строки bn. Преобразование из bn в Ьс сводит­ся только к выборке младших 7 бит адреса строки. По адресу be в кэш-памяти может быть помещена любая из 128 строк основной памяти, имеющих адрес, 7 младших битов которого равны адресу be. Для того чтобы определить, ка­кая именно строка хранится в данное время в кэш-памяти, используется па­мять ёмкостью 7 бит х 128 слов, в которую помещается по соответствующему адресу в качестве тега 7 старших битов адреса строки, хранящейся в дан­ное время по адресу be кэш-памяти. Это специальная память, называемая те­говой памятью. Память, в которой хранятся строки, помещенные в кэш, на­зываются памятью данных. В качестве адреса теговой памяти используются младшие 7 битов адреса строки.

Из теговой памяти считывается тег. Параллельно этому осуществляется доступ к памяти данных с помощью 11 младших битов адреса основной па­мяти (используется 7 разрядов индекса и 4 разряда адреса слова внутри стро­ки). Если считанный из теговой памяти тег и старшие 7 бит адреса основной памяти совпадают, то это означает, что данная строка существует в памяти данных, т.е. осуществляется кэш-попадание.

Если тег отличается от старших 7 бит (кэш-промах), то из основной па­мяти считывается соответствующая строка, а из кэш-памяти удаляется стро­ка, определяемая 7 младшими разрядами адреса строки, и на его место поме­щается строка, считанная из основной памяти. Осуществляется также обнов­ление соответствующего тега в теговой памяти.

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

Полностью ассоциативное распределение

При полностью ассоциативном распределении допускается размещение каждой строки основной памяти на месте любой строки кэш-памяти. Струк­тура кэш-памяти с полностью ассоциативным распределением представлена на рис. 4.6.

Адрес основной памяти состоит из 14-разрядного адреса строки (тега) и 4-разрядного адреса внутри строки.

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

При совпадении ключа с одним из тегов теговой памяти (кэш-попадание) происходит выборка соответствующего данному тегу адреса и обращение к памяти данных. Входной информацией для памяти данных является 11-разрядное слово (7 бит адреса строки и 4 бит адреса слова в данной.

При несовпадении ключа ни с одним из тегов теговой памяти (кэш-Промах) осуществляется обращение к основной памяти и чтение необходи­мой строки.                                                   По этому способу при замене строк кандидатом на удаление могут быть

все строки в кэш-памяти.

Рис.4.6. Структура кэш-памяти с полностью ассоциативным распределением

Частично ассоциативное распределение

При данном способе несколько соседних строк (фиксированное число, не менее двух) из 128 строк кэш-памяти образуют структуру, называемую

Структура кэш-памяти, основанная на использовании частично ассоциа­тивного распределения, показана на рис. 4.7. В данном случае в одну группу входят 4 строки.

Рис.4.7. Структура кэш-памяти с частично ассоциативным распределением

Адрес строки основной памяти (14 бит) разделяется на две части: b - тег (старшие 9 бит) и е - адрес группы (младшие 5 бит). Адрес строки внутри кэш-памяти, состоящий из 7 бит, разделяется на адрес группы (5 бит) и адрес строки внутри группы (2 бит).

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

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

Когда центральный процессор запрашивает доступ по i-му адресу, то осуществляется обращение к массиву тегов по адресу е, выбирается группа из четырёх тегов (а, b, с, d), каждый из которых сравнивается со старшими 9 битами (b) адреса строки. На выходе четырех схем сравнения формируется унитарный код совпадения (0100), который на шифраторе преобразуется в двухразрядный позиционный код, служащий адресом для выбора банка дан­ных^!).

Одновременно осуществляется обращение к массиву данных по адресу

e.f(9 бит) и считывание из банка V;, требуемой строки иди слова.

При пересылке новой строки в кэш-память удаляемая из нее строка вы­бирается из четырех строк соответствующего набора (группы).

Распределение секторов

По данному методу основная память разбивается на секторы, состоящие из фиксированного числа строк, кэш-память также разбивается на секторы, состоящие из такого же числа строк. Рассмотрим случай, когда длина строки равна 16 словам, а сектор состоит из 16 строк. Структура кэш-памяти с рас­пределением секторов представлена на рис. 4.8. В адресе основной памяти старшие 10 бит показывают номер сектора, следующие 4 бит — номер строки внутри сектора, а младшие 4 бит — адрес слова в строке.

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

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

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

43.3. Методы обновления строк основной памяти

В табл. 4.1 приведены условия сохранения и обновления информации в ячейках кэш-памяти и основной памяти.

Таблица 4.1

Условия сохранения и обновления информации

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

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

Сквозная запись

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

Обратная запись

По методу обратной записи, если адрес объектов, по которым есть за­прос обновления, существует в кэш-памяти, то обновляется только кэш­память, а основная память не обновляется. Если адреса объекта обновления нет в кэш-памяти, то в неё из основной памяти пересылается строка, содер­жащая этот адрес, после чего обновляется только кэш-память. По методу об­ратной записи в случае замены строк удаляемую строку необходимо также пересылать в основную память. У этого метода существуют две разновидно­сти: метод SWB (простая обратная запись), по которому удаляемая строка возвращается в основную память, и метод FWB (флатовая обратная запись), по которому в основную память записывается только обновлённая строка кэш-памяти. В последнем случае каждая область строки в кэш-памяти снаб­жается однобитовым флагом, который показывает, было или нет обновление строки, хранящейся в кэш-памяти.

Метод FWB обладает достаточной эффективностью, однако более эф­фективным считается метод FPWB (флатовая регистровая обратная запись), в котором благодаря размещению буфера между кэш-памятью и основной па­мятью предотвращается конфликт между удалением и выборкой строк.

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

4.3.4. Методы замещения строк кэш-памяти

Способ определения строки, удаляемой из кэш-памяти, называется стратегией замещения. Для замещения строк кэш-памяти существует не­сколько методов: метод замещения наиболее давнего по использованию объ­екта — строки, метод LRU (замещение наименее используемой информации);

метод FIFO (первым пришёл — первым вышел) и метод произвольного за­мещения.. В первом случае среди строк, являющихся объектами замещения, выбирается строка, к которой наиболее длительное время не было обраще­ний. По методу FIFO среди всех строк, являющихся объектами замещения, выбирается та, которая самой первой была переслана в кэш-память. И нако­нец, по последнему методу строка выбирается произвольно. Реализация этих методов упрощается в указанной последовательности, но наибольшим эф­фектом обладает метод замещения наиболее давнего по использованию объ­екта (строки).

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

по мере увеличения числа строк.

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