Анализ эффективности ассоциативного кэша неблокирующего типа

Сущенко С.П.
Томский государсвенный университет, факультет информатики

Сущенко М.С.
Томский государсвенный университет информатики


Abstract:

Предложен сравнительный анализ различных моделей оранизации кэша, позволяющий судить об их эффективности. В качестве меры эффективности используется вероятность обнаружения в кэше нужного блока памяти при заданных объемах кэша и памяти, размерах блока и известном распределении приложения (кода и данных) в адресном пространстве. Найдено среднее время выборки объекта, адресуемого приложением, и пропускная способность многоуровневой памяти при различных параметрах кэша.

A comparative analysis of various models of cache is proposed, which allows to judge their effectiveness. The probability of cache hit is taken as a measure of effectiveness with cache and memory sizes given. The distribution of an application in address space and block size are given also. Average time of retrieval of an object, addressed by an application, and memory bandwidth are found at different cache parameters.

Введение. В настоящее время при разработке микропроцессорных архитектур, построении вычислительных систем и сетей, создании распределенных прикладных систем для обеспечения быстрого доступа к наиболее часто используемым данным широко применяется многоуровневая организация памяти. На верхнем уровне находится самая быстрая и, как следствие, самая дорогая и имеющая наименьший объем память в иерархии, а на нижнем - самая медленная, дешевая и емкая [2,3,4]. Память верхнего уровня принято называть кэшем. Функция кэширования (накопления и сохранения данных для быстрого доступа к ним) используется при выборе процессором адресуемых объектов из оперативной памяти (кэш памяти), при доступе к данным, записанным на магнитных дисках (кэш диска, размещенный в оперативной памяти), при получении информации, распределенной во всемирной паутине сети Internet в виде гипертекста (кэш WWW, размещенный на локальных магнитных дисках или на магнитных носителях, существенно приближенных к получателю информации по сравнению с основным источником). 1. Принципы функционирования ассоциативного кэша. Идейной основой применения кэшей различных типов является принцип пространственной и временной локальности [4]. Различают три модели организации чтения (выборки) данных из кэша: кэш прямого отображения, полностью ассоциативный кэш и множественный ассоциативный кэш [2]. В работе предложена общая модель, в параметрической форме определяющая различные типы кэша. В наиболее общем случае организации иерархической памяти кэш и основная память разбиты на блоки (строки) длины $l$. В кэше блоки объединяются в группы объема $A\ge 1$, называемого коэффициентом ассоциативности кэша. При $A=1$ имеем кэш прямого отображения. Если размер группы совпадает с общим числом блоков в кэше, то получаем полностью ассоциативный кэш. Промежуточное значение параметра $A$ приводит к множественному ассоциативному кэшу. На каждую $g$-ю группу блоков кэша ассоциативности $A, \ (g=\overline{0,G-1})$ отображается последовательность блоков памяти с номерами $g+jG, \ j=\overline{0,M-1}$, где $G=K/Al$ - количество групп кэша, $M=AP/K$ - число строк памяти, отображаемых на одну группу кэша, $K$ и $P$ - объем кэша и памяти соответственно. При выборе данных из кэша младшая часть адреса объекта в памяти (индекс) однозначно определяет номер группы, в которой может быть расположен адресуемый объект, а старшая часть, называемая признаком, используется для идентификации требуемого блока памяти, среди множества строк памяти, отображаемых на данную группу кэша. Для этого старшая часть адреса сравнивается с признаком, записанным в признаковую (теговую) память каждой строки кэша при загрузке данных. Если признак одной из строк группы совпал со старшими разрядами адреса, то необходимая информация находится в кэше, в противном случае - запрашиваемых данных в кэше нет и необходимо обращаться к памяти. При этом, если все блоки группы заполнены, то возникает "конфликт адресов" блоков памяти, отображаемых на данную группу кэша [4], и приходится вытеснять какой-либо из блоков кэша этой группы. Важнейшими операционными показателями кэша является среднее время доступа к объектам кэшируемой памяти и вероятность попадания в кэш, которые определяются прежде всего распределением приложений по основной памяти. Данное распределение задается вероятностями $p(g+Gm)$ потребности вычислителя в $m$-ом блоке памяти, отображаемом на $g$-ю группу кэша $\left(\displaystyle\sum_{g=0}^{G-1}\sum_{m=0}^{M-1}p(g+mG)=1\right)$. Среднее время выбора объекта ($m$-го блока), отображаемого на $g$-ю группу кэша, из двухуровневой памяти (кэш-память) определится следующим выражением:

\begin{displaymath} \bar{T}_{gm}=П_{gm}t+(1-П_{gm})T. \end{displaymath} (1)

Здесь $П_{gm}$ - вероятность обнаружения объекта в кэше, $t$ - время выборки объекта из кэша, $T$ - время выборки объекта из памяти. При последовательной реализации этапов доступа к адресуемому объекту соотношение (1) можно переписать в виде

\begin{displaymath} \bar{T}_{gm}=П_{gm}(t_a+t_c\bar{A}+lt_b)+(1-П_{gm})(t_a+t_cA+l\tau+T_a+lT_b)= \end{displaymath}


\begin{displaymath} =t_a+t_c\bar{A}+lt_bП_{gm}+[t_c(A-\bar{A})+T_a+l(\tau+T_b)](1-П_{gm}), \ m=\overline{1,M}, \ g=\overline{1,G}, \end{displaymath}

где $t_a$ - время адресации объекта в кэше, $t_c$ - время сравнения признакового поля кэша со старшей частью адреса, $\bar{A}$ - среднее количество сравнений при условии обнаружения блока в кэше, $l$ - длина блока, $t_b$ - время выборки байта из кэша, $\tau$ - время вытеснения блока данных из кэша, $T_a$ - время адресации объекта в памяти, $T_b$ - время выборки байта из памяти и записи в кэш. Очевидно, что среднее время доступа к объектам кэшируемой памяти определится соотношением
\begin{displaymath} \bar{T}=\sum_{g=0}^{G-1}\sum_{m=0}^{M-1}\bar{T}_{gm}p(g+Gm), \end{displaymath} (2)

а вероятность попадания в кэш - зависимостью
\begin{displaymath} П=\sum_{g=0}^{G-1}\sum_{m=0}^{M-1}П_{gm}p(g+Gm). \end{displaymath} (3)

2. Урновая модель кэша. Будем считать, что для группы $g$ известны условные вероятности потребности вычислителя в $m$-ом блоке памяти

\begin{displaymath} f_g(m)=\frac{p(g+Gm)}{\displaystyle\sum_{i=0}^{M-1}p(g+Gi)}, \ \sum_{m=0}^{M-1}f_{g}(m)=1, \ \end{displaymath}

отображаемом на эту группу кэша. При наличии априорных сведений только о вероятностях $f_{g}(m)$ процесс поиска нужного блока памяти описывается урновой моделью выбора без возвращения [5]. Основной вопрос состоит в определении вероятности выбора необходимого объекта $m$ за $A$ попыток. В случае кэша произвольной ассоциативности $A$ вероятность попадания в $g$-ю группу $m$-го блока памяти определится вероятностью обнаружения его в одной из строк группы:

\begin{displaymath} П_{gm}=f_g(m)+\sum_{k_1=0,k_1\ne m}^{M-1}f_g(m\vert k_1)+\s... ...1} \sum_{k_2=0,k_2\ne m,k_1}^{M-1}f_g(m\vert k_1,k_2)+\ldots \end{displaymath}


\begin{displaymath} +\sum_{k_1=0,k_1\ne m}^{M-1}\ldots \sum_{k_{A-1}=0,k_{A-1}\ne m,k_1,\ldots,k_{A-2}}^{M-1} f_g(m\vert k_1,\ldots,k_{A-1}). \end{displaymath}

Условные вероятности при этом имеют вид

\begin{displaymath} f_{g}(m\vert k_1,\ldots,k_a)=f_{g}(m)\prod_{i=1}^{a}\frac{f... ...\displaystyle{\sum_{j=1}^{i}f_g(k_j)}}, \ a=\overline{1,A-1}. \end{displaymath}

Условное среднее количество сравнений до обнаружения нужного блока с номером $m$, отображаемого на $g$-ю группу кэша $\bar{A}_{gm}$, задается зависимостью

\begin{displaymath} \bar{A}_{gm}=\frac{1}{П_{gm}}\left(f_g(m)+ \sum_{a=2}^{A}af_{g}(m\vert k_1,\ldots,k_{a-1})\right). \end{displaymath}

В случае равномерного распределения приложений по пространству адресов памяти $(f_{g}(m)=1/M=K/AP)$ вероятность попадания в кэш блока памяти $m$ определится зависимостью

\begin{displaymath} П_{gm}=\frac{1}{M}\sum_{a=1}^{A}\left(\frac{1}{M}\right)^{a... ...\prod_{i=1}^{a-1} \frac{M-i}{1-i/M}=\frac{A}{M}=\frac{K}{P}. \end{displaymath}

Отсюда видно, что при равномерном распределении приложений в памяти вероятность попадания в кэш инвариантна к коэффициенту ассоциативности кэша. Среднее число сравнений при этом равно $\bar{A}=(A+1)/2$. Из чего следует, что для приложений с равномерной загрузкой поля памяти (частотой обращения) наилучшим является кэш прямого отображения. Однако, как правило, реальные приложения имеют существенно неоднородное по частоте обращения расположение адресуемых объектов в оперативной памяти. 3. Модель кэша с идеальным вытеснением блоков. Важнейшим фактором, определяющим частоту попадания в кэш ассоциативности $A>1$, является стратегия вытеснения блоков из группы кэша при возникновении конфликта адресов. Очевидно, что наиболее предпочтительной является стратегия вытеснения самого неиспользуемого блока в группе, т.е. имеющего наименьшую вероятность $f_{g}(m)$ быть востребованным. Определим влияние оптимальной стратегии вытеснения самого неиспользуемого блока в группе на общую производительность кэша (частоту попадания в кэш). Для простоты будем анализировать отдельную группу кэша и при рассмотрении опустим индекс принадлежности к различным группам кэша $g$. Предположим, что вероятности $f(m)$ упорядочены по убыванию значений и априори известны механизму вытеснения блоков кэша. Функционирование группы кэша можно описать случайным Марковским процессом в $A$-мерном пространстве $\{m_1,m_2,\ldots,m_A\}$, где $m_a$ - номер блока памяти, находящегося в $a$-м блоке группы кэша. Переходные вероятности цепи Маркова, описывающей динамику процесса замещения блоков данных в кэше имеют вид перемещений вдоль координатной оси с максимальным значением координаты:

\begin{displaymath} \pi_{IJ}=f(m), \ I=\{i_1,i_2,\ldots,i_A\}, \ i_a=\overline{0,M-1}, \ a=\overline{1,A}; \end{displaymath}


\begin{displaymath} J=\{j_1,j_2,\ldots,j_A\}, \ j_k=m, \ k=arg\{\max_{a=\overline{1,A}}m_a\}, \ j_a=i_a, \ a=\overline{1,A}, \ a\ne k. \end{displaymath}

Здесь $I$ и $J$ - координаты исходного и измененного состояний соответственно. Рассмотрим кэш ассоциативности, равной двум. В стационарных условиях уравнения равновесия для вероятностей состояния $P_{ij}$ полностью заполненной группы кэша принимают вид

\begin{displaymath} P_{ij}\sum_{l=0,l\ne i,j}^{M-1}f(l)= f(i)\sum_{l=j+1,l\ne ... ...l=i+1,l\ne j}^{M-1}P_{il}, \ i,j=\overline{0,M-1}, \ i\ne j. \end{displaymath}

С учетом условия нормировки

\begin{displaymath} \sum_{i=0}^{M-1}\sum_{j=0}^{M-1}P_{ij}=1 \end{displaymath}

отсюда находим, что вероятные состояния симметричны и расположены вдоль координатных осей:

\begin{displaymath} P_{00}=P_{ij}=0, \ P_{0i}=P_{i0}=\frac{f(i)}{2(1-f(0))}, \ i,j=\overline{1,M-1}. \end{displaymath}

Вероятность попадания в кэш буфера с номером $m=\overline{0,M-1}$ определится соотношением:

\begin{displaymath} П_{m}=\sum_{i=0}^{M-1}(P_{im}+P_{mi}). \end{displaymath}

С учетом вида вероятностей состояний $P_{ij}$ отсюда получаем:

\begin{displaymath} П_{0}=1, \ П_{m}=\frac{f(m)}{1-f(0)}, \ m=\overline{1,M-1}. \end{displaymath}

То есть самый используемый блок (с номером $m=0$) в стационарном режиме всегда находится в кэше. Пусть $A=3$. Тогда уравнения равновесия записываются следующим образом:

\begin{displaymath} P_{ijk}\sum_{l=0,l\ne i,j,k}^{M-1}f(l)= f(i)\sum_{l=\max\{... ...M-1}P_{ljk}+ f(j)\sum_{l=\max\{i,k\}+1,l\ne j}^{M-1}P_{ilk}+ \end{displaymath}


\begin{displaymath} +f(k)\sum_{l=\max\{i,j\}+1,l\ne k}^{M-1}P_{ijl}, \ i,j,k=\overline{0,M-1} \ i\ne j,k, \ j\ne k. \end{displaymath}

Для вероятностей состояния справедливо:

\begin{displaymath} P_{000}=P_{111}=P_{ijk}=0, \ i,j,k=\overline{2,M-1}; \ \end{displaymath}


\begin{displaymath} P_{01i}=P_{10i}=P_{0i1}=P_{1i0}=P_{i01}=P_{i10}=\frac{f(i)}{6(1-f(0)-f(1))}, \ i=\overline{2,M-1}. \ \end{displaymath}

Вероятности обнаружения необходимых блоков памяти в кэше определяются из выражения

\begin{displaymath} П_{m}=\sum_{i=0}^{M-1}\sum_{j=i+1}^{M-1} (P_{ijm}+P_{jim}+P_{imj}+P_{jmi}+P_{mij}+P_{mji}). \end{displaymath}

Из данного соотношения окончательно получаем:

\begin{displaymath} П_{0}=П_{1}=1, \ П_{m}=\frac{f(m)}{1-f(0)-f(1)}, \ m=\overline{2,M-1}. \end{displaymath}

Отсюда следует, что при ассоциативности $A=3$ два самых используемых блока памяти, отображаемых на данную группу, гарантированно находятся в кэше. Для кэша произвольной ассоциативности $A$ система уравнений равновесия принимает следующий вид:

\begin{displaymath} P_{m_1\ldots m_A}\sum_{l=0,l\ne m_1,\ldots,m_A}^{M-1}f(l)= ... ...,l\ne m_a} ^{M-1}P_{m_1\ldots m_{a-1}lm_{a+1}\ldots m_A}, \ \end{displaymath}


\begin{displaymath} m_a=\overline{0,M-1}, \ a=\overline{1,A}, \ m_i\ne m_j, \ i,j=\overline{1,A}, \end{displaymath}

а вероятные состояния симметричны и находятся на отрезках прямых, параллельных различным координатным осям, общее количество которых равно числу перестановок $A$ координат:

\begin{displaymath} P_{m_1\ldots m_A}=0, \ m_a=\overline{A-1,M-1}, \ a=\overline{1,A}; \ \end{displaymath}


\begin{displaymath} P_{k_1\ldots k_{a-1}mk_{a+1}\ldots k_{A}}=\frac{f(m)}{A!\left(1- \displaystyle\sum_{l=0}^{A-2}f(l)\right)}, \ \end{displaymath}


\begin{displaymath} k_a=\overline{0,A-2}, \ k_i\ne k_j, \ i,j=\overline{1,A-1}, \ m=\overline{A-1,M-1}. \end{displaymath}

Таким образом, цепь Маркова, описывающая динамику вытеснения блоков кэша, распадается на совокупность замкнутых множеств состояний, образующих $A!$ неприводимых подцепей Маркова [1]. Для вероятностей обнаружения блоков памяти в кэше в силу симметричности вероятностей состояний цепи Маркова справедливо:

\begin{displaymath} П_{m}=\sum_{m_1=0}^{M-1}\sum_{m_2=m_1+1}^{M-1}\cdots \sum_{m_{A-1}=m_{A-2}+1}^{M-1}A!P_{mm_1\ldots m_{A-1}}. \end{displaymath}

При этом
\begin{displaymath} П_{a}=1, \ a=\overline{0,A-2}; \ П_{m}=\frac{f(m)} {1-\displaystyle{\sum_{k=0}^{A-2}f(k)}}, \ m=\overline{A-1,M-1}. \end{displaymath} (4)

Отсюда следует, что $G(A-1)$ строк кэша достоверно содержат самые необходимые блоки памяти, а $G$ строк (по одной в каждой группе) используются для попеременной подкачки недостающих вычислителю блоков памяти. Из чего можно заключить, что вероятность попадания в кэш (3) принимает максимальное значение при полностью ассоциативном кэше, в котором только одна строка используется для замещения блоков памяти в то время как в других находится самая востребованная процессором информация. В силу симметричности вероятностей состояний условное среднее число сравнений признакового поля кэша с признаком, выделенным из адреса объекта, для любого $m$ составляет

\begin{displaymath} \bar{A}_m=\frac{1}{П_m}\sum_{a=1}^{A}\sum_{k_1=0}^{M-1}\sum... ...{k_{a-1}=k_{a-2}+1}^{M-1}\sum_{k_{a+1}=k_{a-1}+1}^{M-1}\ldots \end{displaymath}


\begin{displaymath}\ldots \sum_{k_A=k_{A-1}+1}^{M-1}a(A-1)!P_{k_1\ldots k_{a-1}mk_{a+1}\ldots k_{A}}= (A+1)/2. \end{displaymath}

Рассмотренная схема вытеснения основана на априорном знании вероятностей $f(m)$. В реальной ситуации эти показатели заранее неизвестны, а оцениваются по количеству обращений программ к различным блокам группы кэша. 4. Динамические свойства идеального кэша. Поскольку при выполнении вычислительых процессов из-за динамики вычислений и перемещения страниц виртуальной памяти в общем случае распределение приложений в памяти изменяется, то важными параметрами кэша являются вероятностно-временные характеристики движения Марковского процесса замещения блоков кэша к стационарному состоянию. Найдем функцию вероятностей $F_A(k), \ k\ge A-1$, распределение времени движения к стационарному состоянию

\begin{displaymath}P_A(n)=\sum_{k=A-1}^{n}F_A(k), \ n\ge A-1\end{displaymath}

и среднее время

\begin{displaymath}\bar{S}_A=\sum_{k=A-1}^{\infty}kF_A(k),\end{displaymath}

в течение которого из любого нестационарного состояния можно попасть в одну из неприводимых подцепей Маркова. Время движения к стационарному состоянию - это время попадания $A-1$ координат цепи Маркова в область значений пространства состояний $m=\overline{0,A-2}$. При $A=2$ время движения распределено по геометрическому закону с параметром $f(0)$ и среднее время определяется соотношением $\bar{S}_2=1/f(0)$. С ростом ассоциативности геометрический характер функции вероятностей сохраняется, но по мере достижения координат стационарного состояния меняется параметр распределения. Для кэша ассоциативности $A=3$ вероятность $F_3(k), \ k\ge 2$ достижения стационарного состояния ровно за $k$ шагов сначала имеет геометрический вид с вероятностью неуспеха, равной $1-f(0)-f(1)$, и вероятностями успеха $f(0)$ и $f(1)$ событий $m=0$ и $m=1$ соответственно. После попадания в состояние $m=0$ или $m=1$ параметр распределения принимает значение $f(1)$ или $f(0)$ соответственно. Определение функции вероятностей имеет вид:

\begin{displaymath} F_3(k)=f(0)f(1)\sum_{i=0}^{k-2} [1-f(0)-f(1)]^i\{[1-f(0)]^{k-i-2}+[1-f(1)]^{k-i-2}\}= \end{displaymath}


\begin{displaymath} =f(0)[1-f(0)]^{k-1}+f(1)[1-f(1)]^{k-1}-[f(0)+f(1)][1-f(0)-f(1)]^{k-1}. \end{displaymath}

Вероятность достижения стационарного состояния за время $n\ge 2$ задается зависимостью

\begin{displaymath} P_3(n)=1-(1-f(0))^n-(1-f(1))^n+(1-f(0)-f(1))^n, \end{displaymath}

а среднее время движения к стационарному состоянию составит:

\begin{displaymath} \bar{S}_3=\frac{f^3(0)+f^3(1)+2f(0)f^2(1)+2f^2(0)f(1)}{f(0)f(1)[f(0)+f(1)]^2}. \end{displaymath}

В случае $f(0)=f(1)=f$ отсюда получаем $\bar{S}_3=3/2f$. Для произвольного $A$ функция вероятностей определится следующим соотношением:

\begin{displaymath} F_A(k)=\prod_{a=0}^{A-2}f(a)\sum_{i_1=0}^{k+1-A} \left(1-\... ...-2} \left(1-\sum_{j=0,j\ne a_1}^{A-2}f(j)\right)^{i_2}\times \end{displaymath}


\begin{displaymath} \times\sum_{i_3=0}^{k+1-A-i_1-i_2}\sum_{a_2=0,a_2\ne a_1}^{... ...\left(1-\sum_{j=0,j\ne a_1,a_2}^{A-2}f(j)\right)^{i_3}\ldots \end{displaymath}


\begin{displaymath} \ldots\sum_{i_{A-2}=0}^{k+1-A-\sum_{l=1}^{A-3}i_l} \sum_{a... ...m_{j=0,j\ne a_1,...,a_{A-3}}^{A-2}f(j)\right)^{i_{A-2}}\times \end{displaymath}


\begin{displaymath} \times \sum_{j=0,j\ne a_1,...,a_{A-3}}^{A-2}(1-f(j))^{k+1-A-\sum_{l=1}^{A-2}i_l}. \end{displaymath}

При $f(a)=f, \ a=\overline{0,A-1}, \ (A-1)f\le 1$ вероятностно-временные характеристики переходных процессов функционирования кэша принимают вид:

\begin{displaymath} F_A(k)=(A-1)f\sum_{a=0}^{A-2}(-1)^a \left(\begin{array}{c}A-2 \\ a\end{array}\right) (1-(a+1)f)^{k-1}, \end{displaymath}


\begin{displaymath} P_A(n)=1+\sum_{a=1}^{A-1}(-1)^a \left(\begin{array}{c}A-1 \\ a\end{array}\right) (1-af)^n, \end{displaymath}


\begin{displaymath} \bar{S}_A=\frac{1}{f}\sum_{a=1}^{A-1}(-1)^{a+1}\frac{1}{a} ... ... \frac{1}{f}\sum_{a=1}^{A-1}\frac{1}{a}, \ f\le\frac{1}{A-1}. \end{displaymath}

Анализ среднего времени движения к стационарному состоянию показывает, что минимальное значение $\bar{S}_A$ при ограничении $\displaystyle\sum_{a=0}^{A-2}f(a)=const$ достигается для однородных вероятностей потребности $f(a)=f, \ a=\overline{0,A-2}$. 5. Анализ времени доступа. В силу предположения об упорядоченности вероятностей $f_g(m)$, а следовательно и $p(g+Gm)$, внутри групп кэша по убыванию, для среднего времени выбора адресуемых объектов (2) при идеальном вытеснении с учетом (4) справедливо
\begin{displaymath} \bar{T}=tP_A+T(1-P_A)-(T-t)\sum_{g=0}^{G-1}\sum_{m=A-1}^{M... ...-1}p(g+Gi)}, \ P_A=\sum_{g=0}^{G-1}\sum_{m=0}^{A-2}p(g+Gm). \end{displaymath} (5)

Здесь $P_A$ имеет смысл доли распределения востребованных данных, расположенных в $(A-1)G$ блоках всех групп кэша, и характеризует степень локализации кода программ и данных в кэше. Нетрудно видеть, что с ростом емкости и ассоциативности кэша доля $P_A$ растет. Рост вероятностной массы $P_A$ имеет место и в случае увеличения вероятностей $p(g+Gm)$ для $m=\overline{0,A-1}$. Среднее время доступа принимает максимальное значение для равномерного распределения $p(g+Gm)=1/GM=l/P$:

\begin{displaymath} \bar{T}_{\max}=\frac{Kt+(P-K)T}{P}. \end{displaymath}

Величина $P_A$ при этом имеет минимальное значение

\begin{displaymath} P_A=\frac{A-1}{M}=\frac{K}{P}\left(1-\frac{1}{A}\right). \end{displaymath}

Минимальное время доступа $\bar{T}_{\min}=t$ достигается тогда, когда все востребованные данные размещаются в кэше, то есть либо $P_A=1$, либо $P_A<1$, но $p(g+G(A-1))>0, \ p(g+Gm)=0, \ g=\overline{0,G-1}, \ m=\overline{A,M-1}$. В том случае, если равномерно распределен "хвост" распределения

\begin{displaymath}p(g+Gm)=\displaystyle\frac{1-P_A}{M+1-A}, \ g=\overline{0,G-1}, \ m=\overline{A-1,M-1}, \end{displaymath}

среднее время выборки адресуемого объекта линейно падает с ростом локализации приложения в кэще $P_A$:

\begin{displaymath} \bar{T}=tP_A+T(1-P_A)-(T-t)\frac{1-P_A}{M+1-A}. \end{displaymath}

Для распределения "хвоста" в отдельных группах кэша в виде однородных треугольников (арифметических прогрессий) при

\begin{displaymath} p(g+Gm)=\frac{2(1-P_A)}{G(M+2-A)}\left(1-\frac{m+1-A}{M+1-A}\right), \ m=\overline{A-1,M-1} \end{displaymath}

среднеее время доступа (5) составит

\begin{displaymath} \bar{T}=tP_A+T(1-P_A)-2(T-t)(1-P_A)\times \end{displaymath}


\begin{displaymath} \times\frac{M(M-1)(2M-1)-(A-1)(A-2)(2A-3)-6(A-2)M(M+1-A)} {3(M+1-A)^2(M+2-A)^2}. \end{displaymath}

Область допустимых значений степени локализации при этом имеет вид: $\displaystyle\frac{2(A-1)}{M+A}\le P_A\le 1$. Численные исследования показывают, что среднее время доступа к адресуемым объектам (5) слабо зависит от вида "хвоста" распределения $p(g+Gm), \ g=\overline{0,G-1}, \ m=\overline{A-1,M-1}$. 6. Модель кэша неблокирующего типа. Процесс функционирования многоуровневой памяти с кэшем неблокирующего типа может быть описан работой двухстадийного конвейера. На первой фазе конвейера выполняется обращение к кэш-памяти. Длительность этой фазы равна времени доступа к кэшу t. При попадании адресуемого объекта в кэш выполняется следующий запрос к иерархической памяти. В случае промаха одновременно происходит обработка текущего запроса на второй фазе - фазе доступа к оперативной памяти и следующей транзакции - на первой фазе. Таким образом, факт обработки транзакции доступа к иерархической памяти на второй фазе является случайным событием. Время обработки транзакции на второй фазе $T$ в $K\ge 2$ раз превышает время обращения к кэш-памяти $t$. При глубине неблокируемости $N>1$ подсистема многоуровневой памяти имеет буфер емкости $N$ для хранения запросов к оперативной памяти, которые последовательно обрабатываются элементами управления памятью на второй фазе конвейера. Если количество таранзакций, обрабатываемых в фазе обращения к оперативной памяти, совпадает с $N$, то кэш-память оказывается заблокированной. В заблокированном состоянии первая стадия конвейера не работает. Разблокирование первой фазы наступает при завершении обработки одной транзакции на второй фазе конвейера. Для описания процесса обработки запросов к двухуровневой памяти с глубиной блокировки, равной $N$, будем моделировать стадию доступа к оперативной памяти Марковской системой масового обслуживания (СМО) с дискретным временем и $K$-этапным обслуживающим прибором [1]. Длительность цикла дискретной СМО составляет время $t$. Время между поступлениями заявок (транзакций обращения к оперативной памяти) кратно $t$ и имеет геометрическое распределение с параметром, равным вероятности промаха $R$. Считаем, что доступ к многоуровневой памяти выполняется только на чтение или только на запись. Будем полагать, что в каждом такте выполняется обращение к кэш-памяти (при незаблокированной первой фазе конвейера) и с вероятностью промаха $R$ в СМО поcтупает заявка с временем обработки $T$, равным трудоемкости выполнения $K$ этапов СМО длительности $t$. Поскольку обработка различных запросов к оперативной и кэш-памяти выполняется параллельно, то цепь Маркова, описывающая динамику количества этапов обработки совокупности заявок на доступ к оперативной памяти будет содержать $KN$ состояний. Заблокированным соответствует множество состояний $i=\overline{K(N-1)+1,KN-1}$. Переходные вероятности цепи Маркова имеют вид:

\begin{displaymath} \Pi_{ij}=\left\{\begin{array}{l} R, \ i=0, \ j=K; \\ R... ...1, \ i=\overline{K(N-1)+1,KN-1}, \ j=i-1. \end{array}\right. \end{displaymath}

Система уравнений равновесия для стационарного режима функционирования дискретной СМО, описывающей процесс доступа к иерархической памяти, для произвольной глубины неблокируемости $N\ge 2$ и целочисленного отношения времен обращения к оперативной памяти и кэш-памяти $K\ge 2$ записывается следующим образом:

\begin{displaymath} \left\{\begin{array}{l} P_0R=P_1(1-R); \\ P_i=P_{i+1}(1... ...-1)K,NK-2}; \\ P_{NK-1}=P_{(N-1)K+1}R. \end{array}\right. \end{displaymath}

Важнейшими операционными характеристиками иерархической памяти являются вероятность блокировки кэш-памяти, среднее время доступа и пропускная способность. Вероятность блокировки определяется суммой вероятностей состояний, в которых на фазе доступа к оперативной памяти (в СМО) выполняется обработка $N$ транзакций:
\begin{displaymath} Q(N,K)=\sum_{i=(N-1)K+1}^{NK-1}P_i. \end{displaymath} (6)

Среднее время доступа к адресуемым объектам складывается из времени разблокирования кэш-памяти, времени обращения к кэшу и времени обращения к оперативной памяти (при промахе в кэш):
\begin{displaymath} \bar{T}(N,K)=t\left\{ \sum_{i=(N-1)K+1}^{NK-1}(i-(N-1)K)P_{i}+1+R\sum_{i=1}^{NK-1}iP_i\right\}. \end{displaymath} (7)

Пропускная способность определяется количеством транзакций доступа к многоуровневой памяти, обработанных за время $\bar{T}(N,K)$:

\begin{displaymath} C(N,K)=\frac{1}{\bar{T}(N,K)}\left\{\frac{1}{K} \sum_{i=(N... ...-(N-1)K)P_{i}+1-R+ \frac{R}{K}\sum_{i=1}^{NK-1}iP_i\right\}. \end{displaymath}

С учетом (7) данное определение можно переписать в виде:
\begin{displaymath} C(N,K)=\frac{1}{Kt}+\frac{1}{\bar{T}(N,K)}\left\{1-R-\frac{1}{K}\right\}. \end{displaymath} (8)

Анализ показывает, что при заданной вероятности промаха в кэш-памяти $R$ пропущенный по системной шине поток транзакций доступа к адресуемым объектам оперативной памяти (8) растет с увеличением глубины неблокируемости, а среднее время выборки операндов и команд из иерархической памяти (7) и вероятность блокировки (6) - падают.

Bibliography

1
Клейнрок Л. Теория массового обслуживания. Машиностроение, Москва, 1979.

2
Корнеев В.В., Киселев А.В. Современные микропроцессоры. Нолидж, Москва, 1998.

3
Корнеев В.В. Параллельные вычислительные системы. Нолидж, Москва, 1999.

4
Озерецковский С. Кэш // Hard and Soft, 5, 1995, 31-34.

5
Феллер В. Введение в теорию вероятностей и ее приложения. Мир, Москва, 1984.

Ваши комментарии
[SBRAS]
[Головная страница]
[Конференции]
[СО РАН]

© 2001, Сибирское отделение Российской академии наук, Новосибирск
© 2001, Объединенный институт информатики СО РАН, Новосибирск
© 2001, Институт вычислительных технологий СО РАН, Новосибирск
© 2001, Институт систем информатики СО РАН, Новосибирск
© 2001, Институт математики СО РАН, Новосибирск
© 2001, Институт цитологии и генетики СО РАН, Новосибирск
© 2001, Институт вычислительной математики и математической геофизики СО РАН, Новосибирск
© 2001, Новосибирский государственный университет
Дата последней модификации Saturday, 06-Oct-2001 18:59:32 NOVST