\documentstyle[11pt]{article}
\oddsidemargin=-0.005in
\evensidemargin=-0.005in
\topmargin=-0.7in
%\columnsep=0.25in
\textwidth=6.50in
\textheight=9.0in
\newenvironment{tempspacing}[1]{\begin{trivlist}
\baselineskip=#1
\normalbaselineskip=\baselineskip\item[]}{\end{trivlist}}
\renewcommand{\baselinestretch} {1.2}
\pagenumbering{empty}
\pagestyle{empty}
\thispagestyle{empty}
\begin{document}
%\begin{center}
%{\huge\bf CIS 655 Computer Architecture\\
%     Fall 1994}
%\end{center}
\title{\Large\bf \vspace*{-0.5in}Comprehensive Examination\\
Computer Architecture and Operating Systems\\January 21, 1995}
\author{}
\date{}
\maketitle
\vspace*{-0.8in}
\underline{\bf Note:} \begin{itemize}
            \item Answer the Operating Systems and the Architecture parts 
                  on separate answer books. Start each answer on a fresh
		  sheet of paper.
            \item You must write your Social Security Number on each
                  answer book. {\bf Do not} write your name.
            \end{itemize}
\begin{enumerate}
\item
The Multics system, as originally designed, provided for two page
sizes.  What are the potential advantages/disadvantages of having more
than one page size?  How does a storage organization scheme that
supports multiple page sizes differ from one that supports a single
page size?  Suppose a system were designed to support $n$ page sizes.
How would it differ from the Multics approach?  Is a system that
supports a large number of page sizes essentially equivalent to a
segmentation system?  Explain. (10 points)

\item
The Cigarette-Smokers Problem.  Consider a system with three smoker
processes and one agent process.  Each smoker continuously rolls a
cigarette and then smokes it.  But to roll and smoke a cigarette, the
smoker needs three ingredients: tobacco, paper, and matches.  One of
the smoker processes has paper, another has tobacco, and the third has
matches.  The agent has an infinite supply of all three materials.
The agent places two of the ingredients on the table.  The smoker who
has the remaining ingredient then makes and smokes a cigarette,
signaling the agent on completion.  The agent then puts out another
two of the three ingredients, and the cycle repeats.  Write a program
to synchronize the agent and the smokers using monitors. (10 points)

\item
The ISIS protocol for causal ordering of messages assumes that the
processes communicate through broadcast messages. Give an algorithm
for causal ordering of messages which does not require processes to
use broadcasts. Prove the correctness of your algorithm. (10 points)

\item
In a word-addressable computer system, all instructions are one word
long. The computer has separate instruction and data TLBs and a unified
cache. The following informations is given (CC stands for clock cycles):
\begin{itemize}
\item Miss rate of instruction TLB = $0.1\%$; Miss penalty = $25$ CC.
\item Miss rate of data TLB = $0.2\%$; Miss penalty = $25$ CC.
\item $256$ Kword, $2$-way set associative cache; Miss rate = $2\%$; 
      Miss penalty = $10$ CC;  hit time = $1$ CC; Cache access time includes
      TLB hit time; Block size = $32$ words.
\item Main memory size = $1$ GWords.
\item $1.5$ memory references per instruction (including instruction fetch).
\end{itemize} 
\begin{enumerate}
\item Show the various fields and the number of bits in each field in
      the interpretation of the physical address by the cache. (3 points)
\item Find the average memory access time. (5 points)
\item If CPI for execution is 2.0, what is the overall CPI? (2 points)
\end{enumerate}

\item
Consider a three stage instruction pipeline with the following stages: 
Instruction fetch, Operand decode and Execution (including memory access,
write back and branch resolution). Let $T$ be the clock cycle time of this 
pipelined machine and let the ideal CPI be $1$. The only possible data 
hazards are between register write of instruction $i$ and register read 
of instruction $i+1$. The frequency of occurrence of such a data dependency 
is $10\%$.

We are considering changing this pipeline into a four stage pipeline by
splitting the third stage into two stages. In the new pipeline, the
write back and the branch resolutions are done in the fourth stage. Let
$T^\prime$ be the clock cycle time of the new pipeline.
\begin{enumerate}
\item For the new pipeline, in addition to the $10\%$ data hazard frequency 
      between instruction $i$ and $i+1$, there is a data hazard
      frequency of $1\%$ between instruction $i$ and $i+2$ (and not on
      $i+1$). Assuming only data hazards and no data forwarding, 
      what should $T^\prime$ be as a function of $T$ in order for the
      new pipeline to be faster? (5 points)
\item Assuming that forwarding is used whenever possible, consider the 
      impact of control hazards and the remaining data hazards. Assume that 
      only the first stage of the pipeline can be safely executed before 
      the branch outcome is known and that all the branches are conditional. 
      $60\%$ of the branches are taken. What is the maximum possible 
      percentage of branch instructions in a program as a function of 
      $T$ and $T^\prime$ such that the new pipeline is faster? (5 points)
\end{enumerate}

\item
The following information is given about a computer system:
\begin{itemize}
\item Write-back cache with $5\%$ miss ratio, $4$ word blocks and $30\%$
      dirty blocks at any time.
\item The bus reads or writes at the rate of $1$ word/clock cycle.
\item The processor sends references to its cache at the rate of $0.8$
      words/clock cycle.
\end{itemize}
\begin{enumerate}
\item What percentage of the bus bandwidth is used for the cache? (4 points)
\item Assume that only $80\%$ of the maximum possible bus bandwidth
      can be used to avoid performance loss due to conflicts. Each I/O
      operation consists of 1000 clock cycles of CPU time to initiate,
      100,000 clock cycles to find data on the disk and another 1000
      clock cycles to transfer the data. How many I/O operations can be
      performed per one million clock cycles? What is the minimum number 
      of disks needed to achieve this rate assuming that disk accesses
      are ideally distributed? (6 points)
\end{enumerate}
\end{enumerate}
\end{document}
