Оценка вероятности промаха БП типа кэш

Будем выяснять вероятность «промаха» в зависимости от параметров кэш-памяти.

Пусть способ отображения БП - группо-ассоциативный. Введем параметр ассоциативности S, который показывает сколько областей в БП. V-объем БП (в блоках), n-число ячеек в блоке.

 
  Оценка вероятности промаха БП типа кэш - №1 - открытая онлайн библиотека

1) Пусть рабочая нагрузка состоит из операторов следования. Пусть К- объем программы в блоках.

Вероятность «промаха»:

Оценка вероятности промаха БП типа кэш - №2 - открытая онлайн библиотека

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

Оценка вероятности промаха БП типа кэш - №3 - открытая онлайн библиотека

Вывод: чем больше ячеек в блоке - тем меньше вероятность «промаха».

2) Пусть программа состоит из команд следования и перехода вперед.

Пусть qi - вероятность того, что после выполнения текущей команды должна выполняться команда, отстоящая от текущей на i адресов вперед.

Пусть выполнилась первая команда, принадлежащая данному блоку, тогда вероятность того, что этот блок обеспечит выполнения только одной команды равна:

Оценка вероятности промаха БП типа кэш - №4 - открытая онлайн библиотека

две команды:

Оценка вероятности промаха БП типа кэш - №5 - открытая онлайн библиотека Оценка вероятности промаха БП типа кэш - №6 - открытая онлайн библиотека

ДЗ. Найти U3 и вывести рекуррентное соотношение.

Найдем среднее число команд, которые дает блок:

Оценка вероятности промаха БП типа кэш - №7 - открытая онлайн библиотека

ДЗ. Найти m, если qi=1/n (если n®¥, то можно убедится, что m=e=2,47...)

Вероятность «промаха»:

Оценка вероятности промаха БП типа кэш - №8 - открытая онлайн библиотека Оценка вероятности промаха БП типа кэш - №9 - открытая онлайн библиотека

Вывод: команды ветвления вперед увеличивают вероятность «промаха».

3) Программа состоит из всех трех операторов. Пусть длина цикла составляет l блоков и число повторений - r. При определении вероятности «промаха» рассмотрим три случая:

1. l £ V

2. V+V/S £ l

3. V £ l £ V+V/S

Рассмотрим первый случай (l £ V).

Оценка вероятности промаха БП типа кэш - №10 - открытая онлайн библиотека

Этот случай характерен тем, что на первом цикле (шаге) (всего r) в БП нет ни одного блока программы, следовательно, при обращении к каждому блоку программы будет, происходит один «промах». На остальных циклах промахов нет. Для простоты будем считать, что программа начинается с начала области.

Оценка вероятности промаха БП типа кэш - №11 - открытая онлайн библиотека

Рассмотрим второй случай (V+V/S £ l)

Пусть будет алгоритм замещения LRU.

На первом цикле при обращении к первым V блокам программы будет происходить один «промах», а V+1 блок вытесняет первый блок БП и т.д. На втором цикле тоже происходят вытеснения. Действительно первый блок программы отсутствует в БП (вместо него V+1 блок) следовательно, произойдет вытеснение V/S+1 блока и т.д.

Оценка вероятности промаха БП типа кэш - №12 - открытая онлайн библиотека

Рассмотрим третий случай (V £ l £ V+V/S).

Оценка вероятности промаха БП типа кэш - №13 - открытая онлайн библиотека

На первом цикле при обращении к первым V блокам программы будет происходить один «промах», а хвост программы (l-V блоков) вытесняет первые блоки из БП. На остальных циклах вытеснения происходят только с первыми l-V блоками каждой области БП.

Оценка вероятности промаха БП типа кэш - №14 - открытая онлайн библиотека

Оценка вероятности промаха БП типа кэш - №15 - открытая онлайн библиотека

На рис. приведена зависимость вероятности «промаха» от длины программы, состоящей из операторов следования, ветвления и цикла.

Пусть нам зафиксировали объем КЭШа и наша задача - найти параметр ассоциативности S (1£ S £.V). Если S=V, то мы имеем чисто ассоциативное отображение. Если S=1, то второй участок зависимости наиболее пологий, следовательно, мы имеем оптимальное значение параметра ассоциативности, принимая во внимание только «промах» при обращении к БП типа кэш (вероятность «промаха»).

Лекция №3