\documentstyle[12pt]{article}
\setlength{\oddsidemargin}{0in}
\setlength{\textwidth}{6.5in}
\setlength{\topmargin}{0in}
\setlength{\textheight}{22cm}
\setlength{\headheight}{0in}
\setlength{\headsep}{0in}
\setlength{\parskip}{5pt plus 2pt minus 3pt}

\def\thefootnote{\fnsymbol{footnote}}
\setcounter{footnote}{1}

\renewcommand{\baselinestretch}{1.4}
\newtheorem{definition}{Definition}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{fact}[theorem]{Fact}

% to get nice proofs ...
\newcommand{\qedsymb}{\mbox{ }~\hfill~{\rule{2mm}{2mm}}}
\newenvironment{proof}{\begin{trivlist}
\item[\hspace{\labelsep}{\bf\noindent Proof: }]
}{\qedsymb\end{trivlist}}

\parskip 0.1in
\pagenumbering{arabic}    %  Start using 1,2,... as page numbers.
\pagestyle{plain}         %  Page numbers in middle bottom of page.
\setcounter{page}{1}
\setcounter{theorem}{1}
 
\begin{document}
 
\begin{table}\centering
\begin{tabular*}{6.5in}{@{\extracolsep{\fill}}|llr|} \hline
\multicolumn{2}{|l}{Comprehensive Examination in Architecture} & Spring 1995 \\
 & & \\
\multicolumn{3}{|c|}{
{Solutions}} \\
 & & \\ 
Instructor: Srinivas Aluru &  &\\ \hline
\end{tabular*}
\end{table}

\begin{enumerate}
\item[4] \begin{enumerate}
         \item Size of main memory $= 2^{30}$ words.\\
	       Number of bits in physical address $= 30$.\\
	       Size of cache $= 2^{18}$ words.\\
	       Block size $= 2^5$ words.\\
	       Number of blocks in cache $= 2^{18}/2^5 = 2^{13}$.\\
	       Number of sets in cache $= 2^{13}/2 = 2^{12}$.\\
	       The physical address is interpreted by cache as follows:\\\
	       \begin{tabular}{ccc}
	       Tag & Set Number & Offset\\
	       $13$ bits & $12$ bits & $5$ bits\\
	       \end{tabular}
         \item Average memory access time is the ratio of the total
     	       time for memory accesses to the total number of memory
	       accesses. Since the number of memory references per
	       instruction is $1.5$ of which the instruction access is
	       $1$, $\frac{2}{3}rd$ of memory accesses are to
	       instructions and $\frac{1}{3}rd$ are to data.

	       Average memory access time\\
	       $= \frac{2}{3} *$ average instruction access time $+
	          \frac{1}{3} *$ average data access time\\
               $= \frac{2}{3}\left[1+0.001*25+0.02*10\right]
		  + \frac{1}{3}\left[1+0.002*25+0.02*10\right]$\\
               $= 1 + \frac{1}{3}\left[0.7\right]$\\
	       $= 1.233$.
         \item $CPI = CPI_{exec} +$ mem. access. per instr. $*$ avg. miss
	       penalty\\
	       $= 2 + 1.5 * \frac{0.7}{3}$\\
	       $= 2.35$
         \end{enumerate}
\item[5] Let $IC$, $CPI$ and $CCT$ refer to the instruction count,
         Cycles per Instructions and clock cycle time of the old
	 pipeline. Let $IC^\prime$, $CPI^\prime$ and $CCT^\prime$ refer
	 to the same quantities in the new pipeline.
         \begin{enumerate}
	 \item $IC = IC^\prime$.\\
	       $CPI = 1 + 0.1 * 1 = 1.1$\\
	       $CPI^\prime = 1 + 0.1 * 2 + 0.01 * 1 = 1.21$\\
	       For the new pipeline to be better,\\
	       $IC^\prime * CPI^\prime * CCT^\prime < IC * CPI * CCT$\\
	       $1.21 * T^\prime < 1.1 * T$\\
	       $T^\prime < \frac{1.1}{1.21}T = \frac{T}{1.1}$.
	 \item All the data hazards in both the pipelines can be
	       eliminated by forwarding. This leaves only control hazards.
	       Since $60\%$ of the branches are taken, it is best to
	       adopt the {\em predict taken} strategy. Let $b$ be the
	       fraction of instructions that are branch instructions.\\
               $IC = IC^\prime$.\\
               $CPI = 1 + b*\left[0.6 * 1 + 0.4 * 2\right] = 1 +
	       1.4b$\\
	       $CPI^\prime = 1 + b*\left[0.6 * 2 + 0.4 * 3\right] = 1 +
	       2.4b$\\
	       For the new pipeline to be better,\\
	       $IC^\prime * CPI^\prime * CCT^\prime < IC * CPI * CCT$\\
	       $(1+2.4b)*T^\prime < (1+1.4b)*T$\\
	       $b < \frac{T-T^\prime}{2.4T^\prime-1.4T}$
	 \end{enumerate}
\item[6] \begin{enumerate}
	 \item Number of words transferred over the bus per clock cycle
               for cache\\
	       $= 0.8 * 0.05 * 4 * (1 + 0.3)$\\
	       $= 0.208$\\
	       Therefore, $20.8\%$ of the bus bandwidth is used.
         \item Number of words that can be transferred over the bus per
                clock cycle after satisfying the cache
		$= 0.8 * 1 - 0.208 = 0.592$.\\
		In one million clock cycles,\\
                Maximum IOPS CPU can handle $= 1000$.\\
		Maximum IOPS Bus can handle $= 0.592 * 1,000,000 / 1000
		= 592$.\\
		Therefore, $592$ I/O operations can be performed in one
		million clock cycles.\\
		Maximum IOPS a disk can handle $= \lfloor\frac
		{1,000,000}{101,000}\rfloor = 9$.\\
		Minimum number of disks required
		$=\lceil\frac{592}{9}\rceil = 66$.
          \end{enumerate}
\end{enumerate}
\end{document}
