При создании модели этого тракта необходимо рассмотреть две модели: модель работы БП и модель работы рабочей нагрузки.
Во время выполнения программы происходит обращение за командами или за данными. В связи с этим можно говорить, что существует поток команд и данных или говорят, что существует рабочая нагрузка. Нас интересует адресная трасса - номера ячеек, к которым происходит обращение, следовательно, существует проблема задания адресной трассы при моделировании тракта ОП - БП - ЦП. Адресную трассу можно задать, используя структурированный подход. Все операторы можно разбить на следующие классы:
- операторы следования;
- операторы перехода;
- операторы цикла.
Существует доказательство, что все операторы могут быть сведены к выше перечисленным операторам. В результате получим, что адресная трасса примет вид:
(i,i+1), если i-ый оператор является оператором следования;
(i,i+k), если i-ый оператор - безусловный переход вперед;
(i,..,i+l,i,...,i+l,...,i,...,i+l) (r раз), если i-ый оператор - оператор цикла.
Получившаяся рабочая нагрузка обусловлена только наличием команд. Реальная программа состоит из комбинации этих объектов.
Будем выяснять вероятность «промаха» в зависимости от параметров кэш-памяти.
Пусть способ отображения БП - группо-ассоциативный. Введем параметр ассоциативности S, который показывает сколько областей в БП. V-объем БП (в блоках), n-число ячеек в блоке.
1) Пусть рабочая нагрузка состоит из операторов следования. Пусть К- объем программы в блоках.
Вероятность «промаха»:
При обращении к кэш-памяти за очередной командой происходит «промах» только для первой команды, принадлежащей данному блоку, т.к. в блок БП переписывается не только эта команда, но и остальные, следовательно происходит процесс опережающего ввода.
Вывод: чем больше ячеек в блоке - тем меньше вероятность «промаха».
2) Пусть программа состоит из команд следования и перехода вперед.
Пусть qi - вероятность того, что после выполнения текущей команды должна выполняться команда, отстоящая от текущей на i адресов вперед.
Пусть выполнилась первая команда, принадлежащая данному блоку, тогда вероятность того, что этот блок обеспечит выполнения только одной команды равна:
две команды:
ДЗ. Найти U3 и вывести рекуррентное соотношение.
Найдем среднее число команд, которые дает блок:
ДЗ. Найти m, если qi=1/n (если n®¥, то можно убедится, что m=e=2,47...)
Вероятность «промаха»:
Вывод: команды ветвления вперед увеличивают вероятность «промаха».
3) Программа состоит из всех трех операторов. Пусть длина цикла составляет l блоков и число повторений - r. При определении вероятности «промаха» рассмотрим три случая:
1. l £ V
2. V+V/S £ l
3. V £ l £ V+V/S
Рассмотрим первый случай (l £ V).
Этот случай характерен тем, что на первом цикле (шаге) (всего r) в БП нет ни одного блока программы, следовательно, при обращении к каждому блоку программы будет, происходит один «промах». На остальных циклах промахов нет. Для простоты будем считать, что программа начинается с начала области.
Рассмотрим второй случай (V+V/S £ l)
Пусть будет алгоритм замещения LRU.
На первом цикле при обращении к первым V блокам программы будет происходить один «промах», а V+1 блок вытесняет первый блок БП и т.д. На втором цикле тоже происходят вытеснения. Действительно первый блок программы отсутствует в БП (вместо него V+1 блок) следовательно, произойдет вытеснение V/S+1 блока и т.д.
Рассмотрим третий случай (V £ l £ V+V/S).
На первом цикле при обращении к первым V блокам программы будет происходить один «промах», а хвост программы (l-V блоков) вытесняет первые блоки из БП. На остальных циклах вытеснения происходят только с первыми l-V блоками каждой области БП.
На рис. приведена зависимость вероятности «промаха» от длины программы, состоящей из операторов следования, ветвления и цикла.
Пусть нам зафиксировали объем КЭШа и наша задача - найти параметр ассоциативности S (1£ S £.V). Если S=V, то мы имеем чисто ассоциативное отображение. Если S=1, то второй участок зависимости наиболее пологий, следовательно, мы имеем оптимальное значение параметра ассоциативности, принимая во внимание только «промах» при обращении к БП типа кэш (вероятность «промаха»).
