\documentstyle[11pt]{article}
% frob with the margins
\addtolength{\topmargin}{-1in}
\addtolength{\footskip}{-1in}
\addtolength{\textheight}{2in}
\addtolength{\oddsidemargin}{-.5in}
\addtolength{\evensidemargin}{-.5in}
\addtolength{\textwidth}{1in}
% no page numbers
\pagestyle{empty}
% counter for page numbers
\newcounter{pg}
\setcounter{pg}{2}

% DEFINE THE PROBLEM SET NUMBER
\def\psnum{8}

% title command
\newcommand{\mytitle}[1]{\begin{center} {\Large Computation Structures -- 
6.004 Problem Set \psnum \\ Juliet Bourne -- #1} \\ \vspace{-.1in} 
\rule{6in}{.5mm} \end{center}}
% problem command
\newcommand{\prob}[1]{\vspace{.15in}\noindent{\fbox{\large\bf Problem #1}}}
% subproblem command
\newcommand{\subprob}[1]{\vspace{.15in} \noindent{\large\bf #1.}}
% equations commands
\newcommand{\beq}{\vspace*{-.3in}\begin{eqnarray*}}
\newcommand{\eeq}{\end{eqnarray*}}
% newpage setup command 
\newcommand{\mynewpage}{\newpage\noindent
\begin{center}
{\Large 6.004 Problem Set \psnum -- Juliet Bourne -- {\bf Page \thepg}}
\rule{6in}{.5mm}
\end{center}
\addtocounter{pg}{1}}
% see-page command
\newcommand{\seepage}{\noindent See page \rule{.2in}{.1mm} for the
computer output.}

\begin{document}

\mytitle{11/21/90}

\prob{1: {\em Top of Stack Cache}}

\subprob{A}

\begin{verbatim}
                            Types of Access    Number of Accesses
fib:         slaa(0)      | 1 read, 1 push             2
             sl4          | 1 pop, 1 read, 1 push      3
             sc4(2)       | 1 push                     1
             scmp4        | 2 pops, 1 push             3
             sc4(smalln)  | 1 push                     1
             sjlt         | 2 pops                     2
                                                     -----
                                                      11
      
             slaa(0)      | 1 read, 1 push             2
             sl4          | 1 pop, 1 read, 1 push      3
             sc4(1)       | 1 push                     1
             ssub4        | 2 pops, 1 push             3
             sc4(fib)     | 1 push                     1
             scall(4)     | 1 pop, 4 pushes            5
             slaa(0)      | 1 read, 1 push             2
             sl4          | 1 pop, 1 read, 1 push      3
             sc4(2)       | 1 push                     1
             ssub4        | 2 pops, 1 push             3
             sc4(fib)     | 1 push                     1
             scall(4)     | 1 pop, 4 pushes            5
             sadd4        | 2 pops, 1 push             3
             srtn4        | 1 pop, 1 push              2
                                                     -----
                                                      35

smalln:      slaa(0)      | 1 read, 1 push             2
             sl4          | 1 pop, 1 read, 1 push      3
             srtn4        | 1 pop, 1 push              2
                                                     -----
                                                       7
\end{verbatim}

\noindent So, \verb+fib(3)+ makes $11 + 35$ accesses plus the number of
accesses that \verb+fib(2)+ and \verb+fib(1)+ makes. Thus, \verb+fib(3)+
makes $11 + 35 + 11 + 7 + 11 + 7 = 82$ accesses to the main memory. With
each access taking $10T$ time units, the total time is: $820T$ time
units. 

\subprob{B} Start with the TOS register empty. \verb+Pop, Push+ indicate
pops or pushes using the TOS register. \verb+Read, Write+ indicates that
a read/write from main memory and a cache access have occurred. For
\verb+Read+, it is likely that the TOS register is empty and a pop is
needed; so the cache must read the top-of-stack value from main memory
and put it in the register. I'm basing my idea about what happens on
Figure 16.6, which is C code for the behavior of pop and push when using
a Top of Stack Cache.

\mynewpage

\begin{verbatim}
                            Types                     MM  Cache
fib:         slaa(0)      | 1 read, 1 Push             1    1
             sl4          | 1 Pop, 1 read, 1 Push      1    2     
             sc4(2)       | 1 Write, 1 Push            1    2
             scmp4        | 1 Pop, 1 Read, 1 Push      1    3
             sc4(smalln)  | 1 Write, 1 Push            1    2
             sjlt         | 1 Pop, 1 Read              1    2
                                                     ----------
                                                       6   12
      
             slaa(0)      | 1 read, 1 Push             1    1
             sl4          | 1 Pop, 1 read, 1 Push      1    2
             sc4(1)       | 1 Write, 1 Push            1    2
             ssub4        | 1 Pop, 1 Read, 1 Push      1    3
             sc4(fib)     | 1 Write, 1 Push            1    2
             scall(4)     | 1 Pop, 4 Pushes, 3 Writes  3    8
             slaa(0)      | 1 read, 1 Write, 1 Push    2    2
             sl4          | 1 Pop, 1 read, 1 Push      1    2
             sc4(2)       | 1 Write, 1 Push            1    2
             ssub4        | 1 Pop, 1 Read, 1 Push      1    3
             sc4(fib)     | 1 Write, 1 Push            1    2
             scall(4)     | 1 Pop, 4 Pushes, 3 Writes  3    8
             sadd4        | 1 Pop, 1 Read, 1 Push      1    3
             srtn4        | 1 Pop, 1 Push              0    2
                                                     ----------
                                                      18   42

smalln:      slaa(0)      | 1 read, 1 Push             1    1
             sl4          | 1 Pop, 1 read, 1 Push      1    2
             srtn4        | 1 Pop, 1 Push              0    2
                                                     ----------
                                                       2    5
\end{verbatim}

\noindent Main memory access time: $(6 + 18 + 8 + 8)(10T) = 400T$ time
units. Cache access time: $(12 + 42 + 17 + 17)(T) = 88T$ time units. So
the total time is: $488T$ time units. The increase in performance is
about 40\%.

\subprob{C} Instruction fetch times dramatically increase the amount of
time since each instruction must be fetched from main memory; also,
additional instructions for the cache algorithm are needed.

\subprob{D} Probably, since most instructions tend to pop multiple
values off the stack. Some instructions, like \verb+scall+, push
multiple values onto the stack. However, a cache will not improve
performance in proportion with its size; there is an optimal size for
such caches.

\mynewpage

\subprob{E} If the cache is empty and a pop is requested, read and
return the top of the stack from main memory and cache nothing. If a
push is requested, just cache the push argument as the first element. If
the cache is full and a push is requested, write the last element in the
cache to main memory, shift the remaining elements down one register,
and cache the push argument as the first element. If a pop is requested,
return the first element of the cache and shift the remaining elements
up one register, so that the last element is empty. If the cache is
neither full nor empty and a push is requested, shift the elements down
one register and cache the push argument as the first element. If a pop
is requested, return the first element and shift the remaining elements
up by one register.

\prob{2: {\em Cache Design}}

\subprob{A} Since this is fully associative, the tags need to be 32 bits
to hold the 32-bit addresses. 
\vspace{1in}

\subprob{B} A compare must be done on each line before a cache miss is
signalled; $2^{15}$ compares. The average number of compares for a cache
hit is $2^{15}/2 = 2^{14}$.

\subprob{C} $t_{h,av} = 20 \cdot 2^{14} = 10 \cdot 2^{15}$ ns.  $t_m =
20 \cdot 2^{15} + 300$ ns.

\beq
t_a & = & \alpha t_h + (1 - \alpha) t_m \\
\mbox{} & = & 0.95 (10 \cdot 2^{15}) + 0.05 (20 \cdot 2^{15} + 300) \\
\mbox{} & = & 10.5 \cdot 2^{15} + 15
\eeq

\subprob{D} This scheme entails a lot of serial compares. The average
access time is very high. 

\subprob{E} This scheme doesn't take advantage of temporal or spatial
locality. 

\subprob{F} The tags are 17 bits. The data portion of the line is 32
bits. Therefore, the cache system requires $49\cdot 2^{15}$ bits.

\subprob{G} Take two physical addresses: $tk$ and $sk$. $tk$ is the
physical address where $t$ represents the high 17 bits and $k$
represents the low 15 bits. In the fully-associated cache scheme, once
these physical addresses are cached, there is no need to go to the main
memory again if they are referenced again. However, in the single-set
associative cache scheme, since these addresses share the same low 15
bits, interleaved references to $tk$ and $sk$ will cause repeated
accesses to main memory because $sk$ will replace $tk$ and then $tk$
will replace $sk$, et cetera.

\subprob{H} All that needs to be done is to access the $k$th line and
compare the tag with the high 17 bits. Therefore it only takes one
access, or 20ns, to determine if the data is in the cache.

\subprob{I} Again, spatial and temporal locality is ignored.

\mynewpage

\subprob{J} This sets the $k$ parameter, which should be 2 bits. The
compiler should start its complex pairs at $k=00$ so that a complex
number fits onto one line of the cache.

\subprob{K} Since more than two arrays are rarely referenced at once,
$m$, the number of sets, should be 2. Since arrays start on 15-bit
boundaries, the number of lines in a set should be 15.

\subprob{L} Tags in the cache are 15 bits and they come from the high 15
bits of a 32-bit address. The cache takes the second 15 bits of the
address and accesses the line that that 15 bits refers to in each set.
Then the cache compares the tag of the first selected line to the high
15 bits of the address. If a match occurs, the cache signals a hit and a
multiplexer gives the data based on the low 2 bits of the address, which
is the offset into the block. If a match doesn't occur, the cache looks
at the second set's selected line and repeats the procedure.

\vspace{2in}

\subprob{M} If a cache miss occurs, random, or LRU strategy if feasible,
choice between which of the two sets to replace the required line in. 

\prob{3: {\em Distributed Caches}}

\subprob{A} A processor needs to signal that it has read or written its
own cache since it might be reading out-dated data or it might be
writing data which would make other caches' data out-dated. If the
processor accessed a line in its cache, and if another processor also
had a line referring to the same data but it had changed the data
previously, then the first processor will be reading out-dated data. 

\subprob{B} When Processor A gets a cache miss on a location that
Processor B's cache has tagged dirty, then Processor B's cache should
push the value for that location onto the bus so that Processor A's
cache can cache it.

\subprob{C} Main memory writes should occur when a dirty line in some
processor's cache is about to be replaced. That way, the correct value
will be in main memory for other processors to access.

\subprob{D} When a processor accesses its caches, it signal the other
caches over the bus when it access line with ``clean, shared'' or
``dirty, shared'' tags.

\subprob{E} If Cache A notices that another processor is trying to read
a location that it (Cache A) has tagged as unshared clean, it must
change the tag for that location to shared clean.

\prob{4: {\em Paged Virtual Memory}}

\subprob{A} $\frac{2^M}{2^P} = 2^{M-P}$

\subprob{B} $\frac{2^V}{2^P} = 2^{V-p}$

\subprob{C} $M - P = 21 - 10 = 11 \; \; \; 11 + 2 = 13$ bits.

\subprob{D} $2^{V-P}$ times the size of an entry. An entry is 13 bits,
so $13 \cdot 2^{14}$ bits or $13 \cdot 2^{14 - 3 - 10} = 26$ pages.

\prob{5: {\em Quiz Two Revisited}}

\end{document}
