Шинная организация микропроцессорных систем- с одной шиной, с дв. Программа для эвм это упорядоченная последовательность команд, подлежащая обработке
 Скачать 1.97 Mb.
|
22.Алгоритмы замещения информации в заполненной кэш-памяти.Когда кэш-память заполнена, занесение в нее нового блока связано с замещением содержимого одной из строк. При прямомотображении каждому блоку основной памяти соответствует только одна определенная строка в кэш-памяти, и никакой иной выбор удаляемой строки здесь невозможен. При полностьюи частичноассоциативныхспособах отображения требуется какой- либо алгоритм замещения (выбора удаляемой из кэш-памяти строки). Основная цель стратегии замещения – удерживатьв кэш-памяти строки, к которым наиболее вероятны обращения в ближайшем будущем, и заменятьстроки, доступ к которым произойдет в более отдаленном времени или вообще не случится. Оптимальным будет алгоритм, который замещает ту строку, обращение к которой в будущем произойдет позже, чем к любой другой строке кэша. Такое предсказание практически нереализуемо, поэтому используются алгоритмы, уступающие оптимальному. В любом случае для достижения высокой скорости алгоритм замещения должен быть реализован аппаратными средствами. Наиболее распространенными являются четыре алгоритма замещения, рассматриваемые в порядке уменьшения их относительной эффективности. Алгоритмзамещениянаосновенаиболеедавнегоиспользования(LRU – Least Recently Used). Является наиболее эффективным алгоритм замещения. В соответствии с этим алгоритмом замещается та строка кэш-памяти, к которой дольше всего не было обращения. Проводившиеся исследования показали, что алгоритм LRU работает достаточно хорошо в сравнении с оптимальным алгоритмом. Наиболее известны два способа аппаратной реализации этого алгоритма. В первомиз них с каждой строкой кэш-памяти связывается счетчик. К содержимому всех счетчиков через определенные интервалы времени добавляется единица. При обращении к строке ее счетчик обнуляется. Таким образом, наибольшее число будет в счетчике той строки, к которой дольше всего не было обращений, и эта строка – первый кандидат на замещение. Второйспособ реализуется с помощью очереди, куда в порядке заполнения строк кэш-памяти заносятся ссылки на эти строки. При каждом обращении к строке ссылка на нее перемещается в конец очереди. В итоге первой в очереди каждый раз оказывается ссылка на строку, к которой дольше всего не было обращений. Именно эта строка, прежде всего и заменяется. Алгоритм,работающийпо принципуFIFO(первый вошел, первый вышел – First In First Out). В соответствии с этим алгоритмом заменяется строка, дольше всего находившаяся в кэш-памяти. Алгоритм легко реализуется с помощью рассмотренной очереди, с той лишь разницей, что после обращения к строке положение соответствующей ссылки в очереди не меняется. Алгоритмзаменынаименеечастоиспользовавшейсястроки(LFU – Least Frequently Used). В соответствии с этим алгоритмом заменяется та строка в кэш-памяти, к которой было меньше всего обращений. Аппаратная реализация алгоритма: каждая строка связывается со счетчиком обращений, к содержимому которого после каждого обращения добавляется единица. Главным претендентом на замещение является строка, счетчик которой содержит наименьшее число. Произвольныйвыборстрокидлязамены. Простейший алгоритм, в соответствие с которым замещаемая строка выбирается случайным образом. Реализовано это может быть, например, с помощью счетчика, содержимое которого увеличивается на единицу с каждым тактовым импульсом, вне зависимости от того, имело место попадание или промах. Значение в счетчике определяет заменяемую строку. Данный алгоритм используется крайне редко. |