%* Last edited: Oct  6 10:33 1997 (josie)
\documentstyle[psfig]{article}
\setlength{\oddsidemargin}{.8in}
\setlength{\evensidemargin}{.8in}
\setlength{\textwidth}{4.9in}

\setlength{\topmargin}{-0.2in}
\setlength{\textheight}{8.5in}
\setlength{\parindent}{0.0in}

\begin{document}
\begin{center}

{\large Massachvsetts Institvte of Technology}

{\large Department of Electrical Engineering and Computer Science}

\vskip .1in

{\large 6.313 Contemporary Computer Design}
\vskip .1in

{\large Problem Set \#3 Fall, 1998, Due Wed 21 October}
\end{center}

\vskip .3in

% trilevel gate
 
1.  The Flexible Fnordian Finger Fabrication allows each digit of their hand
to fold both backwards and forwards.  Xenologists speculate that this
resulted in the Fnordian's symmetric ternary (radix 3) number system, with
each twit having a value of -1, 0, or +1.  The Fnords named these digits M,
Z, and P respectively.  

\vskip .1in

a) Convert the number MPZPZ into decimal notation.  Is the Fnordian
representation for this number unique?

\vskip .1in

b) Construct the Fnordian addition table.

\vskip .1in

The emergence of the twit as basic Fnordian information unit naturally led to
the development of ternary logic hardware.

\vskip .1in

In binary, we know that we can construct a universal set of logic
primitives by including at least one inverting function and at least one
monotonic function.  By monotonic, we mean a function $f(a,b,c,\ldots)$
where, as inputs are successively changed from a zero to a one (in any
order), the output changes from a logic 0 to a logic 1 and subsequently
makes no further transitions.  The XOR or Parity functions, for example are
not monotonic, while the AND and OR operations are.  OR can be thought of
as performing the MAX operation on its inputs, while AND performs the MIN
operation.  In binary, both the inversion and monotonic function can be
performed in a single logical gate, such as the NAND or NOR gate.

\vskip .1in

c) Apply these principles to construct a set of one or more universal
Fnordian ternary logic gates, and show by construction that your set is
universal.  Don't belabor the point by writing them out -- just show that
you have the ability to construct any gate.

\vskip .1in

Hints (not to be answered, but to guide your thinking): construct the truth
table for a two input Fnordian gate and think particularly about what value
must occupy the central (ZZ input) slot.  What does logic expressed in
minimum sum of products form look like?  How would you build a decoder?

\vskip .1in

d) Using your newly defined Fnordian logic (not just the minimal set
defined above, if this is inconvenient) draw a Fnordian combinational
ripple adder circuit.

\vskip .1in

e) Draw the ideal $V_{in}$ vs. $V_{out}$ characteristics for a Fnordian
inverter, using logic levels of -2, 0, and 2 volts.

\vskip .1in

f) You are given a collection of resistors and PMOS and NMOS transistors
with threshold voltages of -2.7 and +2.7 volts respectively.  Available
power supply voltages are -2, 0, and +2 volts.  Design a (simple!) inverter
which implements the Fnordian truth table:

\vskip .3in

\begin{center}
\leavevmode
\begin{tabular}{c|c}
IN & OUT \\
\hline
M & P\\
Z & Z\\
P & M
\end{tabular}
\end{center}

\vskip .1in

g) We wish to extend our logic family by including the two input logic
function below, but encounter real difficulties in doing a simple
implementation.  Explain the source of the difficulties.

\vskip .2in

\begin{center}
\leavevmode
\begin {tabular}{cc|ccc}
\hspace{0.2in} & \hspace{0.2in}& \hspace{0.2in}& B & \hspace{0.2in} \\
&&M&Z&P\\
\hline
&M&P&P&P\\[.1in]
A&Z&P&P&Z\\[.1in]
&P&P&Z&M
\end{tabular}
\end{center}

\vskip .1in

Bonus: Suggest how the addition of silicon diodes (forward voltage drop .7
volts) or PMOS devices with a different threshold voltage (which one) would
help.

\vskip .1in

Bonus: Unless you were very clever and motivated, the gates you have
constructed dissipate static DC power with some combinations of inputs.  How
would you design a gate which had no static dissipation?

\vskip .3in

2. The transition energy for a gate is $1/2C( \Delta V)^2$ where
$\Delta V$ is the change in voltage for that transition.  For binary
gates, a logic zero represented by 0 volts and a logic one is
represented by 2.5 volts.  In order to maintain the same noise
margins, when using ternary gates, a logic zero is represented as 0
volts, a logic one as 2.5 volts, and a logic two as 5 volts.

a) What is the average transition energy for a binary gate assuming all
transitions are equally likely?

\vskip .1in

b) What is the average transition energy for a ternary gate assuming
all transitions are equally likely?

\vskip .1in

c) Compare binary logic to ternary logic by giving a short list of
benerits and drawbacks for both.  Which one would you use if you were
crunched for space? Which one would you use if you wanted to save
power?  What about speed? Why?

\vskip .3in
% Driving wires
3. As you saw in problem set 2, driving long wires requires intermediate
repeaters.  Even in an on-chip environment, RC wire delays are an important
problem.  In this problem, we investigate the optimal number of repeaters
to place on a wire run.  Model the wire delay as a lumped RC delay, with a
delay as a function of length given by
\begin{equation}
\tau = {\cal RC}l^2.
\end{equation}

\vskip .1in

Consider now a wire of length $L$.  Driven from one end, this wire will
have an approximate delay of ${\cal RC}L^2$.  Instead, we will improve the
wire delay by adding $n$ inverters along the length of the wire, spaced
evenly every $L/n$.  The inverters have a gate delay of $T$ each.

\vskip .1in

a) Write an expression for the total delay of wire plus gates as a function
of $n$.

\vskip .1in

We can analyze this situation by thinking of $n$ as a continuous variable,
rather than as a discrete variable.

\vskip .1in

b) Minimize the total delay by setting the first derivative with respect to
$n$ of the expression from (a) equal to zero, and solving for $n$ and the
total minimum delay.

\vskip .1in

c) For the minimal delay case, what is the relationship between the total
length of time taken in interconnect and the total length of time taken in
wire?

\vskip .1in

d) How will $n$ and the total delay scale for these buffered lines as we
apply our scaling factor $k$?

\vskip .1in

e) Calculate an expression for the speed of propagation of a signal down a
buffered wire.  Note that, unlike in an unbuffered wire, the concept of
speed makes sense, since the delay is linear in the length of the buffered
wire.

\vskip .1in

f) In our modern integrated circuit process, a wire has a sheet resistance of
0.1 ohms/square.  The wire is separated from the conductive substrate by
0.5 microns of silicon dioxide, K = 4.0.  The gate delay of our inverters
is 100 ps.  Estimate the speed of propagation of a signal down an optimally
buffered wire.  How does this speed compare to the speed of light?

\vskip .1in

g) IBM's new process uses copper instead of aluminum interconnection
technology.  How much faster is a signal on a copper chip than an aluminum
chip, assuming that the geometry, dielectric materials,  and gate speeds
are otherwise unchanged from section (f).


\vskip .3in
% optical transistor
4. John Smallberries from Yoyodyne Propulsion proclaims on comp.arch that
he has invented an optical inverter, which will revolutionize computing as
we know it.   His proposal looks like this:

\vskip .1in

\begin{center}
\leavevmode
\psfig{file=fig95-3.ps}
\end{center}

On the bottom is a constant laser light input beam.  It is mixed at the
half-silvered mirror with an
input beam (of the same intensity as the constant beam when on) from a
previous stage, ultimately derived from the same laser.  The mixture
produces interference.  The path lengths are chosen carefully such
that when no input light is present, the constant laser beam falls onto the
output slit.  When light is present in the input beam, the light
destructively interferes with the constant beam in the region of the slit,
and hence no light appears in the output beam.  

\vskip .1in

Manifestly, John asserts, he has made an all optical inverter, allowing the
construction of much faster and lower power computers than ever before.
After all, if light comes in, no light comes out, and vice-versa.

\vskip .1in

a) Sketch a graph of the input intensity vs. output intensity curve for
John's ``inverter.''  Include input intensity points above the nominal
constant beam intensity.

\vskip .1in

b) Criticize the proposed inverter given what you know of logic gates and
their necessary functions.

\vskip .1in

c) Propose an experiment that John can do which involves only a few devices
and little other equipment to convince himself that there is a serious
problem in his plan to revolutionize computing.

\vskip .1in

Questions to think about (no answer required): What is really required to
build all-optical logic gates?  How soon might we really get it?  Will it
make any difference when we do?  If you were a research manager at IBM in
charge of future computing technology research, what fraction of your money
would you spend on optical computing?

\end{document}


