\iffalse INSTRUCTIONS: (if this is not ps1, use the right file name) Clip out the ********* INSERT HERE ********* bits below and insert appropriate TeX code. Once you are done with your file, run ``latex template.tex'' from the Athena shell. If your TeX code is clean, the latex will exit back to a prompt. Once this is done, run ``dvips template.dvi -o template.ps'' which should print your file to the nearest printer. There will be residual files called ps1.log, ps1.aux, and ps1.dvi. All these can be deleted, but do not delete ps1.tex. \fi \documentclass[11pt]{article} \usepackage{amsfonts} \usepackage{latexsym} \setlength{\oddsidemargin}{.25in} \setlength{\evensidemargin}{.25in} \setlength{\textwidth}{6in} \setlength{\topmargin}{-0.4in} \setlength{\textheight}{8.5in} \newcommand{\handout}[5]{ \renewcommand{\thepage}{#1-\arabic{page}} \noindent \begin{center} \framebox{ \vbox{ \hbox to 5.78in { {\bf 6.823 Computer Architecture} \hfill #2 } \vspace{4mm} \hbox to 5.78in { {\Large \hfill #5 \hfill} } \vspace{2mm} \hbox to 5.78in { {\it #3 \hfill #4} } } } \end{center} \vspace*{4mm} } \newcommand{\ho}[5]{\handout{#1}{#2}{Instructor: #3}{Teaching Assistant: #4}{Handout #1: #5}} \newcommand{\al}{\alpha} \newcommand{\Z}{\mathbb Z} \begin{document} \handout{PS3-1}{DUE: 3/13/2002}{Problem Set 3} {Instructors: Krste Asanovic, Srinivas Devadas} {Timothy Danford, Kilian Pohl, Bryan Russell} \section{Problem 1} {\bf a} \bigskip Loop A incurs a cache miss approximately $\frac{1}{4}$ of its memory accesses. Loop B never hits the contents of the cache. This translates into 256 cache misses in Loop A and 1024 cache misses in Loop B. The reason is the combination of the row-major ordering of the matrix $A$ and the direct-mapped nature of the cache. Each row of the matrix contains $4$ cache lines worth of data ($4$ consecutive lines). When loop B sums the matrix, it sums down the columns. Therefore, as each entry in the matrix is touched, cache lines are loaded at positions in the cache that are multiples of $4$. After every $16$ rows of the matrix, loop B starts loading new cache lines in the place of the ones currently in place. In other words, loop B uses only $\frac{1}{4}$ of the lines available in the cache. Loop A, on the other hand, loads the cache lines sequentially and accesses all four words within a line before accessing the next line. Only $1$ in $4$ memory accesses are misses when the length of a cache line is exceeded. {\bf b} \bigskip \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|} \hline & \multicolumn{10}{|c|}{1B Table 1-1: Matrix Multiply Without Blocking} \\ \cline{2-11} & \multicolumn{2}{|l}{Line 0} & \multicolumn{2}{|l}{Line 1} & \multicolumn{2}{|l}{Line 2} & \multicolumn{2}{|l}{Line 3} & \multicolumn{2}{|l|}{Line 4} \\ \hline 0 & Invalid & Invalid & Invalid & Invalid & Invalid & Invalid & Invalid & Invalid & Invalid & Invalid \\ \hline 1 & $Y[0][0]$ & $Y[0][1]$ &&&&&&&& \\ \hline 2 & && $Z[0][0]$ & $Z[0][1]$ &&&&&& \\ \hline 3 & & HIT & &&&&&&& \\ \hline 4 & &&&& $Z[1][0]$ & $Z[1][1]$ &&&& \\ \hline 5 & &&&&&& $Y[0][2]$ & $Y[0][3]$ && \\ \hline 6 & &&&&&&&& $Z[2][0]$ & $Z[2][1]$ \\ \hline 7 & &&&&&&& HIT && \\ \hline 8 & && $Z[3][0]$ & $Z[3][1]$ &&&&&& \\ \hline 9 & $X[0][0]$ & $X[0][1]$ &&&&&&&& \\ \hline 10 & &&&& $Y[0][0]$ & $Y[0][1]$ &&&& \\ \hline 11 & &&&&&&&& $Z[0][0]$ & $Z[0][1]$ \\ \hline 12 & &&&&& HIT &&&& \\ \hline 13 & &&&&&& $Z[1][0]$ & $Z[1][1]$ && \\ \hline 14 & && $Y[0][2]$ & $Y[0][3]$ &&&&&& \\ \hline 15 & $Z[2][0]$ & $Z[2][1]$ &&&&&&&& \\ \hline 16 & &&& HIT &&&&&& \\ \hline 17 & &&&&&&&& $Z[3][0]$ & $Z[3][1]$ \\ \hline 18 & &&&& $X[0][0]$ & $X[0][1]$ &&&& \\ \hline \end{tabular} $14$ misses from $18$ memory accesses means that the matrix multiply without blocking suffers from a $\frac{14}{18} = 77.78\%$ miss rate. \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|} \hline & \multicolumn{10}{|c|}{1B Table 1-2: Matrix Multiply With Blocking} \\ \cline{2-11} & \multicolumn{2}{|l}{Line 0} & \multicolumn{2}{|l}{Line 1} & \multicolumn{2}{|l}{Line 2} & \multicolumn{2}{|l}{Line 3} & \multicolumn{2}{|l|}{Line 4} \\ \hline 0 & Invalid & Invalid & Invalid & Invalid & Invalid & Invalid & Invalid & Invalid & Invalid & Invalid \\ \hline 1 & $Y[0][0]$ & $Y[0][1]$ &&&&&&&& \\ \hline 2 & && $Z[0][0]$ & $Z[0][1]$ &&&&&& \\ \hline 3 & & HIT &&&&&&&& \\ \hline 4 & &&&& $Z[1][0]$ & $Z[1][1]$ &&&& \\ \hline 5 & &&&&&& $X[0][0]$ & $X[0][1]$ && \\ \hline 6 & HIT &&&&&&&&& \\ \hline 7 & &&& HIT &&&&&& \\ \hline 8 & & HIT &&&&&&&& \\ \hline 9 & &&&&& HIT &&&& \\ \hline 10 & &&&&&&& HIT && \\ \hline 11 & &&&&&&&& $Y[1][0]$ & $Y[1][1]$ \\ \hline 12 & && HIT &&&&&&& \\ \hline 13 & &&&&&&&&& HIT \\ \hline 14 & &&&& HIT &&&&& \\ \hline 15 & $X[1][0]$ & $X[1][1]$ &&&&&&&& \\ \hline 16 & &&&&&&&& HIT & \\ \hline 17 & &&& HIT &&&&&& \\ \hline 18 & &&&&&&&&& HIT \\ \hline 19 & &&&&& HIT &&&& \\ \hline 20 & & HIT &&&&&&&& \\ \hline \end{tabular} Although the table extends to length $20$, we will calculate the miss rate with respect to the first $18$ accesses to memory. There are $6$ of the first $18$ accesses that are misses, for a miss ratio of $\frac{6}{18} = 33.33\%$ miss rate. {\bf c} \bigskip If we want the inner two loops of our matrix multiply code to run without cache misses (except for compulsory misses), we need to make sure there is enough space to hold the complete $BxB$ block in $Z$, and the $B$-length rows in $X$ and $Y$. In other words, the data cache must be large enough to hold $B^2 + 2B$ matrix elements simultaneously to avoid (capacity) cache misses. Assuming Ben Bitdiddle has a 16 kB data cache and that matrix elements are 1 word each, Ben's maximum blocking factor is $63$. When Ben notices the poor performance of his code on the UltraSPARC-I with a TLB, his matrices are stored in row-major order within his virtual address space. However, due to the size of the matrix ($3000 * 4 \textrm{bytes} = 12000 \textrm{bytes per matrix row}$, which is greater than the page size of 8 KB) each row starts on a different page. For that matter, any element of any of the matrices is on a different page from the corresponding element (same column) in the previous and subsequent rows of the same matrix. In Ben's code (and using the maximum blocking factor from above), when the innermost loop is reached and executed it touches (in the best case for Ben) 63 separate pages from the data of $Z$ and 1 page (at best) for the data from $Y$. At this point the TBL is full, containing 64 VPN-to-PPN mappings in its 64 lines. However, Ben's code then accesses and sets an entry of $X$. Since the TBL is governed by an LRU replacement policy, this causes the table entry correpsonding to $Z[kk,j]$ (the oldest $Z$ page) to be removed from the TBL. In other words, the TBL is one line too short; every time Ben's code enters the innermost loop, it must reload \textbf{all} of the VPN-to-PPN mappings corresponding to $Z$ and $X$ into the TBL from memory. Therefore the hit rate is below 50\% for the TLB. Thus the overhead connected to the TLB outweighs the benefit in this case. Consequently it leads to a slow down in performance. {\bf d} \bigskip The optimized \verb+BlockMove+ routine incorporates two main ideas: \begin{enumerate} \item The first was illustrated in the blocked code for the matrix multiplication in 1B: blocking to maximize the use of the cache in the reading of the matrix that's being copied. \item The second and more important technique is the use of \verb+dcbz+ to avoid the penalty associated with the Macintosh's write-allocate cache behavior. If we weren't using the \verb+dcbz+ instruction, then every time we wrote to a new block of the destination memory array, we would incur a cache miss and a read from memory into cache that would be both costly and pointless (since the existing data is about to be written over anyway). Normally, the only way to bring something into the cache is to read it (the appropriate line) from memory. The \verb+dcbz+ instruction allows us to specify that a line is loaded in the cache without actually going through the hassle of reading the contents from memory, when we don't care about the contents. Reading the source array requires a cache load, as will writing the modified (copied) cache contents back out to memory when the program is finished with each cache line: those are costs that cannot be avoided. However, before writing to any memory location, the memory location is ``read'' into the cache through the use of the lightweight (1 cycle) \verb+dcbz+, and {\bf only then} is written to. We could think of \verb+dcbz+ as a data prefetch operation, although it ignores the values of the (destination) array that's being read. \end{enumerate} In other words, the optimized \verb+BlockMove+ routine will access avoid spurious loads into the cache with \verb+dcbz+, and use blocking so that all work on a cache line can be completed in a single pass once that cache line is loaded into the cache -- there's no need for any flushed cache line to ever return to the cache. \end{document}