Алгоритмы восстановления информации в оперативной памяти.
Существует два метода восстановления измененной информации из КЭШ в ОП:
1. Write Back – обратная запись; 2. Write Through – сквозная запись.
Обратная запись.
Восстановление информации в ОП происходит на этапе вытеснения информации из кэша. При работе ЦП и ОП инфа изменяется только в кэше.
Существует 3 реализации этого метода восстановления:
1. Простой обмен. Вне зависимости от того изменялась информация в КЭШ или нет, она восстанавливается в ОП.
2. Регистровый обмен. Измененный блок информации записывается в буферный регистр. Из ОП на освободившееся место отображается новый блок информации и только за тем измененная информация восстановленная в ОП.
3. Признаковый обмен. В этом случае только измененная информация восстанавливается в ОП. Признаком изменения является единичное значение бита изменения в строке кэша.
В процессорах Pentium при реализации кэш памяти второго уровня используется обратная запись.
Сквозная запись.
При данном методе изменяется информация как в кэше, так и в ОП почти одновременно. Т.к. каждый цикл записывается => шина загружается. Т.е. на каждую операцию изменения данных приходится 2 операции изменения данных.
Достоинства: в ОП всегда хранятся последние данные.
Для повышения эффективности функционирования кэша используют метод с двойной буферизацией. Для уменьшения загрузки шины процессор выполняет запись в нескольких буферах, работающих по алгоритму FIFO. Т.е. запись для процессора заканчивается практически мгновенно, но информация не сохраняется в ОП. Процессор далее выполняет свои функции, не заботясь о восстановлении информации в ОП. Дополнительные затраты связаны с необходимостью реализации алгоритмов освобождения буфера, определения загрузки шины. Но это эффективно, т.к. процессор полностью освобождается от работы с ОП.
|
|
|
Сравнение:
1) при обратной записи системная шина менее загружена из-за меньшего количества записей. 2) требуются аппаратные затраты, связанные с обеспечением целостности данных.
Обычно обратная запись используется в процессорах для реализации кэша 2-го уровня. Обратная запись на 10% эффективнее сквозной записи.
1) плюсом сквозной записи – в ОП постоянно находится измененная инфа. Практика показывает, что операция записи составляет небольшую долю от общего обращения к памяти. Поэтому различие между 2-мя методами невелико.
Обычно сквозная запись используется для реализации кэш 1-го уровня в современных процах.
4. Алгоритмы замещения: точные, приближенные.
Оптимальный алгоритм замещения обеспечивает удаление тех блоков, которые нескоро понадобятся, т.е. хранит историю использования блоков. При функционировании кэш-памяти используют алгоритм LRU. Существуют точные и приближенные методы реализации данного алгоритма. Они отличаются количеством используемого оборудования и методами реализации алгоритмов.
|
|
|
Точная реализация алгоритма
Регистр хронологий
| БП | Рг хрон | |||||
| 
|
Каждому блоку ОП ставится в соответствие свой Регистр хронологий, который хранит информацию об истории использования блоков. Регистры принимают значение от 0 до 7. Значение «7» - блок использовался недавно, «0» - использовался давно.
n=log2N
При вытеснении используют блок, значение регистра хронологий которого равно 0. Аппаратные затраты оцениваются по необходимому объему памяти и количеству регистров хронологии.
C = n* log2N – теоретический min для данного алгоритма.
Применение точных алгоритмов требует больших аппаратных затрат, поэтому эффективно при небольшом объеме кэш-памяти (до 4 кбайт).
|
|
|
Турнирная таблица
Создается матрица SxS, в которой фиксируется обращение к блокам. Количество элементов, используемых в матрице, определяется как k(k-1)/2, где к – количество блоков. В качестве элементов матрицы используют триггеры. В общем виде структура матрицы имеет следующий вид.
Обращение ко 2-ому блоку
Если происходит обращение к i-ому блоку, которому соответствует i-ая строка, следовательно все элементы этой строки устанавливаются в 1, а все элементы i-го столбца в 0. При вытеснении замещению подлежит блок …, члены строки которого равны 0. На данном рисунке вытеснению подлежит блок 0.
Затраты оборудования определяются по следующей формуле: a=n(n-1)/2, где n –количество триггеров. Данный алгоритм относится к точным алгоритмам и эффективен для реализации объема до 64 кбайт.
Дата добавления: 2015-12-17; просмотров: 146; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!