\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{4}

% 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{10/10/90}

\prob{1: {\em Pulse Synchronizer}}

The waveforms will look something like this:
                                                                              
\vspace{4in}

In this circuit, the R-S latch acts as the arbiter. Arbitration
problems occur when B sends a reset signal and P sends a set signal.
The R-S latch decides which arrives first (if either) and acts
accordingly. Keeping the P signals less than a clock pulse's width
wide and separated by at least eight clock edges will eliminate the
problem of having B and P asserting conflicting signals of reset and
set to the R-S latch. The problem still remains, however, that if a
pulse in P causes X to change too close to an active clock edge, A
will most likely be invalid for a clock period before it gets the
valid value of X and acts accordingly.

\mynewpage

\prob{2: {\em Traffic Lights and Intersections}}

\subprob{A} All traffic paths:

\beq
N \longrightarrow S \; \; &  N \longrightarrow W & \; \; N \longrightarrow E \\
E \longrightarrow W \; \; &  E \longrightarrow N & \; \; E \longrightarrow S \\
W \longrightarrow E \; \; &  W \longrightarrow S & \; \; W \longrightarrow N \\
S \longrightarrow N \; \; &  S \longrightarrow E & \; \; S \longrightarrow W \\
\eeq

\subprob{B} Some strongly conflicting traffic paths:

\beq
N \longrightarrow S \; \; & and  & \; \; W \longrightarrow E \\
W \longrightarrow N \; \; & and  & \; \; S \longrightarrow W \\
\eeq

\subprob{C} Some non-conflicting paths:

\beq
N \longrightarrow S \; \; & and  & \; \; S \longrightarrow N \\
N \longrightarrow W \; \; & and  & \; \; S \longrightarrow E \\
\eeq

\subprob{D} Some weakly conflicting paths:

\beq
N \longrightarrow W \; \; & and  & \; \; E \longrightarrow W \\
W \longrightarrow N \; \; & and  & \; \; E \longrightarrow N \\
\eeq

\subprob{E} When constrained to a two-phase pattern, the paths such as South
to West and West to North have to be eliminated since they strongly conflict
with straight-ahead paths and with each other in two out of four cases.
Although weakly conflicting paths could be eliminated from the following
two-phase pattern, eliminating them would increase the latency.

\vspace{2in}

\subprob{F} A four-phase traffic pattern can be devised which not only allows
the cross paths such as South to West and West to North but which also
eliminates the weakly conflicting ``merging'' paths which may cause delay
problems under heavy traffic. 

\mynewpage

A four-phase pattern sans weakly conflicting paths:

\vspace{2in}

\subprob{G} The information about how many cars are waiting in each lane could
be used to help determine which the best phase to change into would be.
However, it is impossible to know which way the cars want to go,
straight-ahead or a cross path. Still, it would be useful to know which paths
are the most in need of attention. Walk buttons would be rather difficult to
deal with if they were to do anything but halt all of the traffic paths all at
once. One possible alternative would be to modify the straight-ahead paths
(phases 1 and 2 above) to not allow turns. This would allow ``walks'' to occur
while traffic still flows. (Give me some time and lots of money
and I might be able to come up with the optimal solution to this traffic
problem. {\tt :-)}

\prob{3: {\em Equation Synthesis}}

\subprob{A}

\vspace{3in}

\subprob{B} The path from the C input to the second adder must be padded so
that it has the same number of registers as the other paths up to that point.

\subprob{C} The circuit can be clocked every 370 plus 40 or 410 ns. (The 370
ns is the longest combinational delay in the circuit and the 40 is the
propagation delay of the registers.)

\mynewpage

\subprob{D} Therefore the throughput of this circuit would be $\frac{1}{410
ns}$. 

\subprob{E} The clock period now becomes 540 plus 40 or 580 ns. Therefore the
throughput is $\frac{1}{580 ns}$. The latency is 4 (the number of registers
between input and output) times 580 ns (the clock period), or 2320 ns.

\subprob{F} The middle pipeline layer can be eliminated while still
preserving the pipelining rules of not having more than the clock period's
length of delay (580 ns) between two registers and of having the same number
pf registers along each data path.

\vspace{3in}

\subprob{G} Since the divider now operates in 290 ns, the slowest
combinational delay in the circuit is 300 ns (the multipliers). Therefore the
clock period is 300 plus 40 or 340 ns. So, the throughput is $\frac{1}{340
ns}$ and the latency is 3 times 340 ns or 1020 ns.

\vspace{.5in}
\prob{4: {\em Clipping Divider}}

\vspace{.25in}
This is a very heinous problem. The lead-up to the questions is two
pages long. Granted, it's probably a fascinating problem and all, but I just
don't have the time to do it and understand it fully. Doing it halfway would
probably just confuse me more. (Don't you just love rationalization? {\tt :-)} 


\end{document}


