Cache conflict equations
authorlekernel <sebastien.bourdeauducq@lekernel.net>
Sat, 5 Sep 2009 19:22:33 +0000 (21:22 +0200)
committerlekernel <sebastien.bourdeauducq@lekernel.net>
Sat, 5 Sep 2009 19:22:33 +0000 (21:22 +0200)
milkymist-core/cores/tmu/doc/dist_12lines.dia
milkymist-core/cores/tmu/doc/dist_12lines.eps
milkymist-core/cores/tmu/doc/tmu.tex

index adc668a..a1c9f85 100644 (file)
Binary files a/milkymist-core/cores/tmu/doc/dist_12lines.dia and b/milkymist-core/cores/tmu/doc/dist_12lines.dia differ
index 76e5b9e..ec5d86c 100644 (file)
@@ -1,7 +1,7 @@
 %!PS-Adobe-2.0 EPSF-2.0
 %%Title: /home/lekernel/Milkymist/milkymist/milkymist-core/cores/tmu/doc/dist_12lines.dia
 %%Creator: Dia v0.97
-%%CreationDate: Sat Sep  5 20:00:05 2009
+%%CreationDate: Sat Sep  5 21:21:32 2009
 %%For: lekernel
 %%Orientation: Portrait
 %%Magnification: 1.0000
@@ -286,4 +286,104 @@ start_ol
 384 2044 lineto
 2655 5440 lineto
 end_ol grestore 
+1.000000 1.000000 1.000000 srgb
+n 32.620000 9.409344 m 32.620000 10.561844 l 33.380000 10.561844 l 33.380000 9.409344 l f
+0.000000 0.000000 0.000000 srgb
+gsave 32.620000 10.326844 translate 0.035278 -0.035278 scale
+start_ol
+1472 4864 moveto
+1472 576 lineto
+2364 576 lineto
+3494 576 4019 1093 conicto
+4544 1610 4544 2726 conicto
+4544 3834 4019 4349 conicto
+3494 4864 2364 4864 conicto
+1472 4864 lineto
+704 5440 moveto
+2251 5440 lineto
+3833 5440 4572 4782 conicto
+5312 4125 5312 2725 conicto
+5312 1319 4568 659 conicto
+3825 0 2251 0 conicto
+704 0 lineto
+704 5440 lineto
+end_ol grestore 
+1.000000 1.000000 1.000000 srgb
+n 32.661250 7.409344 m 32.661250 8.561844 l 33.338750 8.561844 l 33.338750 7.409344 l f
+0.000000 0.000000 0.000000 srgb
+gsave 32.661250 8.326844 translate 0.035278 -0.035278 scale
+start_ol
+1472 2624 moveto
+1472 576 lineto
+2628 576 lineto
+3245 576 3542 828 conicto
+3840 1081 3840 1602 conicto
+3840 2126 3542 2375 conicto
+3245 2624 2628 2624 conicto
+1472 2624 lineto
+1472 4864 moveto
+1472 3200 lineto
+2539 3200 lineto
+3067 3200 3325 3405 conicto
+3584 3610 3584 4032 conicto
+3584 4450 3325 4657 conicto
+3067 4864 2539 4864 conicto
+1472 4864 lineto
+704 5440 moveto
+2592 5440 lineto
+3437 5440 3894 5092 conicto
+4352 4744 4352 4103 conicto
+4352 3606 4112 3312 conicto
+3873 3019 3409 2947 conicto
+3978 2830 4293 2458 conicto
+4608 2087 4608 1530 conicto
+4608 798 4102 399 conicto
+3597 0 2664 0 conicto
+704 0 lineto
+704 5440 lineto
+end_ol grestore 
+1.000000 1.000000 1.000000 srgb
+n 22.662500 7.409344 m 22.662500 8.561844 l 23.337500 8.561844 l 23.337500 7.409344 l f
+0.000000 0.000000 0.000000 srgb
+gsave 22.662500 8.326844 translate 0.035278 -0.035278 scale
+start_ol
+2560 4710 moveto
+1560 1984 lineto
+3564 1984 lineto
+2560 4710 lineto
+2144 5440 moveto
+2980 5440 lineto
+5056 0 lineto
+4290 0 lineto
+3793 1408 lineto
+1338 1408 lineto
+841 0 lineto
+64 0 lineto
+2144 5440 lineto
+end_ol grestore 
+1.000000 1.000000 1.000000 srgb
+n 22.655000 9.409344 m 22.655000 10.561844 l 23.345000 10.561844 l 23.345000 9.409344 l f
+0.000000 0.000000 0.000000 srgb
+gsave 22.655000 10.326844 translate 0.035278 -0.035278 scale
+start_ol
+4864 5056 moveto
+4864 4288 lineto
+4489 4642 4063 4817 conicto
+3638 4992 3160 4992 conicto
+2217 4992 1716 4407 conicto
+1216 3823 1216 2718 conicto
+1216 1617 1716 1032 conicto
+2217 448 3160 448 conicto
+3638 448 4063 623 conicto
+4489 798 4864 1152 conicto
+4864 384 lineto
+4475 128 4040 0 conicto
+3606 -128 3122 -128 conicto
+1878 -128 1163 635 conicto
+448 1398 448 2718 conicto
+448 4042 1163 4805 conicto
+1878 5568 3122 5568 conicto
+3613 5568 4048 5440 conicto
+4483 5312 4864 5056 conicto
+end_ol grestore 
 showpage
index 3ac905a..5c541f9 100644 (file)
@@ -233,7 +233,56 @@ Wrapping can cause pixels split across the texture. This can happen horizontally
 \caption{Wrapping in both directions.}\label{fig:casewrap3}
 \end{figure}
 
-\subsection{Chosen cache architecture}
-The case of Figure~\ref{fig:case1} is the most frequent one.
+\subsection{Cache architecture}
+\subsubsection{Design options}
+We have two options for designing the cache:
+\begin{itemize}
+\item four separate caches (one for pixel 1, one for pixel 2, etc.)
+\item a shared cache capable of looking up 4 pixels at a time
+\end{itemize}
+
+Misses between the ways for pixels 1, 2, 3 and 4 are likely to be correlated, so a shared cache architecture is chosen to minimize memory bandwidth.
+
+\subsubsection{Avoiding cache conflicts}
+There could be replacement conflicts that have, at least, a detrimental impact of performance.
+
+Such conflicts happen when:
+\begin{itemize}
+\item (Figure~\ref{fig:case1}) lines A and B collide. This happens when:
+\begin{equation*}
+\text{hres} \equiv 0 \pmod{\text{csize}}
+\end{equation*}
+\item (Figure~\ref{fig:case2}) lines A and B collide or lines C and D collide. This does not happen unless the cache only contains one line, which is not a practical case.
+\item (Figure~\ref{fig:case2}) lines A and C or lines B and D collide. This is the same case as for Figure~\ref{fig:case1}.
+\item (Figure~\ref{fig:casewrap1}) lines A and B collide. This happens when:
+\begin{equation*}
+\text{hres}\cdot(\text{vres}-1) \equiv 0 \pmod{\text{csize}}
+\end{equation*}
+\item (Figure~\ref{fig:casewrap2}) lines A and B or lines B and C collide. This happens when:
+\begin{equation*}
+\text{hres}-1 \equiv 0 \pmod{\text{csize}}
+\end{equation*}
+\end{itemize}
+
+In the equations above:
+\begin{itemize}
+\item hres is the horizontal resolution in pixels
+\item vres is the vertical resolution in pixels
+\item csize is the total number of pixels the cache can hold. It is equal to the cache size in bytes (not counting the tag memory) divided by 2.
+\end{itemize}
+
+\subsubsection{Summary}
+When using the texture mapping unit, one must make sure that:
+\begin{equation*}
+\text{hres} \not \equiv 0 \pmod{\text{csize}}
+\end{equation*}
+Additionally, if texture wrapping is enabled, one must also make sure that:
+\begin{equation*}
+\text{hres}\cdot(\text{vres}-1) \not \equiv 0 \pmod{\text{csize}}
+\end{equation*}
+\begin{equation*}
+\text{hres}-1 \not \equiv 0 \pmod{\text{csize}}
+\end{equation*}
+
 
 \end{document}