Программа для ЭВМ это упорядоченная последовательность команд, подлежащая обработке
 Скачать 1.98 Mb.
|
22.Алгоритмы замещения информации в заполненной кэш-памяти.Когда кэш-память заполнена, занесение в нее нового блока связано с замещением содержимого одной из строк. При прямомотображении каждому блоку основной памяти соответствует только одна определенная строка в кэш-памяти, и никакой иной выбор удаляемой строки здесь невозможен. При полностьюи частичноассоциативныхспособах отображения требуется какой- либо алгоритм замещения (выбора удаляемой из кэш-памяти строки). Основная цель стратегии замещения – удерживатьв кэш-памяти строки, к которым наиболее вероятны обращения в ближайшем будущем, и заменятьстроки, доступ к которым произойдет в более отдаленном времени или вообще не случится. Оптимальным будет алгоритм, который замещает ту строку, обращение к которой в будущем произойдет позже, чем к любой другой строке кэша. Такое предсказание практически нереализуемо, поэтому используются алгоритмы, уступающие оптимальному. В любом случае для достижения высокой скорости алгоритм замещения должен быть реализован аппаратными средствами. Наиболее распространенными являются четыре алгоритма замещения, рассматриваемые в порядке уменьшения их относительной эффективности.
Наиболее известны два способа аппаратной реализации этого алгоритма. В первомиз них с каждой строкой кэш-памяти связывается счетчик. К содержимому всех счетчиков через определенные интервалы времени добавляется единица. При обращении к строке ее счетчик обнуляется. Таким образом, наибольшее число будет в счетчике той строки, к которой дольше всего не было обращений, и эта строка – первый кандидат на замещение. Второйспособ реализуется с помощью очереди, куда в порядке заполнения строк кэш-памяти заносятся ссылки на эти строки. При каждом обращении к строке ссылка на нее перемещается в конец очереди. В итоге первой в очереди каждый раз оказывается ссылка на строку, к которой дольше всего не было обращений. Именно эта строка, прежде всего и заменяется.
23.Алгоритмы согласования содержимого кэш-памяти и основной памяти.В процессе вычислений процессор может не только считывать имеющуюся информацию, но и записывать новую, обновляя тем самым содержимое кэш-памяти. С другой стороны, многие устройства ввода/вывода могут напрямую обмениваться информацией с основной памятью (прямой доступ к памяти). В обоих вариантах возникает ситуация, когда содержимое строки кэша и соответствующего блока ОП перестают совпадать. В результате на связанное с основной памятью устройство вывода может быть выдана устаревшая информация, поскольку все изменения в ней, сделанные процессором, фиксируются только в кэш-памяти, а процессор будет использовать старое содержимое кэш-памяти вместо новых данных, загруженных в ОП из устройства ввода. Для разрешения первой из рассмотренных ситуаций, когда процессор выполняет операцию записи, в системах с кэш-памятью предусмотрены методы обновления основной памяти (политики записи), которые можно разбить на две большие группы:
По методу сквозной записи, прежде всего, обновляется слово, хранящееся в основной памяти. Если в кэш-памяти существует копия этого слова, то она также обновляется. Если же в кэш-памяти отсутствует нужная копия, то возможны два варианта:
Метод достаточно прост в реализации и легко обеспечивает целостность данных за счет постоянного совпадения копий данных в кэше и основной памяти. Основное достоинство метода сквозной записи состоит в том, что когда строка в кэш-памяти назначается для хранения другого блока, то удаляемый блок можно не возвращать в основную память, поскольку его копия там уже имеется. При этом можно обойтись без признака модифицированности. Недостаток метода состоит в том, что эффект от использования кэш-памяти (сокращение времени доступа) в отношении к операциям записи отсутствует. Данный метод применен в микропроцессорах i486 фирмы Intel. Определенный выигрыш дает его модификация, известная как метод отложеннойбуферизированнойсквознойзаписи. Информация сначала записывается в кэш-память и в специальный буфер, работающий по схеме FIFO. Запись в основную память производится уже из буфера, а процессор, не дожидаясь ее окончания, может сразу же продолжать свою работу. Соответствующая логика управления должна заботиться о том, чтобы своевременно переписывать заполненный буфер в ОП (например, во время свободных тактов шины). При использовании буферизации процессор полностью освобождается от работы с ОП. Согласно методу обратнойзаписи, слово заносится только в кэш-память. Если соответствующей строки в кэш-памяти нет, то нужный блок сначала пересылается из ОП, после чего запись все равно выполняется только в кэш-память. При этом строка кэша, в которую произведена запись, помечается как грязная или модифицированная, т.е. требующая выгрузки в основную память. Только после этой выгрузки (записи в основную память) строка становится чистой, и ее можно будет использовать для кэширования других блоков без потери целостности данных. В основную память данные переписываются только целой строкой. Выгрузка (запись) в основную память откладывается до наступления крайней необходимости (например, обращение к кэшированной памяти другим устройством, замещение строки в кэше новыми данными) или выполняется в свободное время после модификации всей строки. Данный метод сложнее в реализации, но существенно эффективнее (в среднем на 10%), чем сквозная запись, так как позволяет уменьшить количество операций записи в основную память. Предотвратить несогласованность в ситуации, когда в основную память из устройства ввода, минуя процессор, заносится новая информация и неверной становится копия, хранящаяся в кэш-памяти, позволяют два приема. В первом случае ввод любой информации в ОП автоматически сопровождается соответствующими изменениями в кэш-памяти. Во втором случае ввод любой информации в ОП допускается только через кэш-память. |