
\subsection{Algorithms and Systems}

We have completed a number of arithmetic designs, summarized in
Table~1. %\ref{status}.

%\BT
%\caption{SNAP Die Fab Status}	\label{status}

%\input SNAPdie	%table
%\ET

\subsubsection{Wave Pipelining} 

Ordinary pipeline systems operate at a frequency
that corresponds to the maximum logic path delay between any two stages.
Theoretically, it is possible to increase this frequency
by an amount of time equal to the minimum path delay that might occur 
in the worst-case stage.  

In SNAP research, we have shown that it is possible to use CAD tools
to automatically increase the minimum or the fast paths to a point where
the minimum path logic acts as a significant part of the storage system.
We have shown that clocking ECL circuits at 2-1/2 to 3 times the maximum
propagation delay is feasible. 
In a bipolar (ECL) experiment, Wong [P27] showed that the path of a 
multiplier that had a worst-case path delay of about 10 nanoseconds could 
be safely clocked at a 4-nanosecond rate.
In further research using a CMOS multiplier, Klass [P3] has designed
a 6-times improvement in clock rate, resulting in a 600 MHz integer
multiplication (see Figure~\ref{spice}).



\begin{figure}%[p]
\centering
\protect\addcontentsline{toc}{subsection}{Figure 1: A Wave Pipelined Multiplier}
\ \psfig{figure=spice.ps,height=5in,width=5in}

\caption{A wave pipelined $16^b$ multiplier in CMOS (0.8 cycles).
Figure shows repetition rate, latency is about 9\,ns, 
upper and lower parts show different data patterns.}
\label{spice}
\efig


\subsubsection{Addition and Floating-point Addition}

We have been able to optimize earlier work by Ling on integer adders
\cite{LIN81} to avoid excessive fanout, yet preserve the speed advantage.
We have also mapped the Ling approach over to CMOS technology [P13].

We have made basic improvements to the floating-point addition algorithm.  
Conventionally, floating-point addition consists of a subtraction of
exponents, a shifting of fractions by an amount equal to the exponent
difference, addition or subtraction of the fractions, a shifting of the
result (on subtraction) to leave it in normalized form, and a rounding of
the result.
These steps are generally sequential, and require two shifts and three
additions (the exponent subtraction, fraction addition, and rounding).
Farmwald, in earlier work \cite{Far81}, showed that one of the shifts could 
be eliminated by creating two simultaneous paths, since a long preshift
could not be accompanied by a long postshift following the fraction
addition/multiplication.
Quach has shown that it is possible to further improve the floating-point
addition by integrating the rounding step with the final fraction addition
[P14].
This is done by creating up to four different results and MUXing out the
correct result.
By careful management and integration of the paths, the overall hardware
cost is only modestly increased over the state-of-the-art approach.
A floating-point adder based upon this idea has been fabricated and is
being tested.
Using a conventional 1-micron CMOS, process, the floating-point
addition delay is about 15--16 nanoseconds 
(IEEE standard floating-point addition).


\subsubsection{Floating-point Multiplication}

In the area of floating-point multiplication, we have completed two separate
studies. 

The first concentrated on the use of regular counters, after the work of
Santori \cite{San89}.
This study developed two structures for partial-product reduction
for IEEE standard floating point multiplication,
leading to structured layouts. Such layouts are desirable because
they require shorter wires and therefore support faster operation.
The former approach uses a reduction scheme based on a 28/5 counter
followed by 55/4 counters. The latter uses a novel family of
counters, called 9/2, 6/2, and 4/2 respectively.
Both approaches use 3/2 counters as basic building blocks. 

We have developed automatic programs for synthesizing the layout of these
two structures. 
The programs are portable across different, but similar, circuit technologies.
We have implemented two sample chips, one for each style, 
in BiCMOS technology.
The 28/5 approach had delay of 10\,ns, 
while the 9/2 approach had delay of 7\,ns.

In the second multiplication study, we have developed a scheme based
upon a redundant 3-bit Booth encoding of the multiplier.
This redundant encoding reduces the number of partial products to be summed
by one-third over a full (53 bit) tree partial product summation, 
but it avoids the requirement of forming plus or minus three multiples 
of the multiplicand.
Coupled to the multiplier encoding, we have developed techniques that allow
us to handle irregular counter implementations of the partial product tree.
State-of-the-art implementations of partial product trees have focused on
4--2 and similar approaches that provide a regularity in wiring of the
partial product tree.
We have shown with this work that it is possible to use irregular
implementations based upon 3--2 counters with the assistance of CAD
tools, which automatically optimize the routing and path length through the
partial product tree. 
Using the combined techniques of the redundant multiplier encoding, and the
CAD-assisted layout of the partial product tree, we have implemented a full
IEEE floating-point multiplier.
This is being implemented now in ECL with the sponsorship of SUN Microsystems.
The full multiplier is expected to have an overall delay of 
five nanoseconds (see Figure~\ref{multcp}).

\bfig
\protect\addcontentsline{toc}{subsection}{Figure 2: An ECL Multiply}
%\ \psfig{figure=multcp.ps,height=3.75in,width=3in}
\vspace{4.5in}
\special{psfile=multcp.ps vscale=.6 hscale=.6 voffset=-80}

\footnotesize
\begin{picture}(240,45)
\put(1,25){1 -- input ($t=0$)}
\put(1,05){2 -- output of tree ($t=4.3$ns)}
\put(141,25){3 -- final produce ($t=5.2$ns)}
\put(141,05){4 -- multiples ready ($3x$, $1x$) $t=0.6$ns}
\end{picture}

\caption{An ECL $53 \times 53^b$ (IEEE standard) multiply in 5.2\,ns 
(latency). The $106^b$ addition at the multiply end takes 850\,ps.}
\label{multcp}
\efig


\subsubsection{Division and Higher Level Functions}	\label{ems}

SNAP has advanced both SRT and functional iteration approaches to division 
[P12].
In SRT, we have developed techniques for extending the SRT approach to 
radix 64 division [P15,P30].
We have also shown that improved methods of division by functional iteration
are also possible. 

Higher-level functions such as square root, logarithm, exponent, and various
trig functions are normally performed in software at commensurately much
slower speeds.
Even if only an approximation to one of these functions is required, a
significant amount of time is consumed in producing the result. 
Occasionally tables are stored in memory to expedite the process of
developing either an approximation to, or a starting point for, an algorithm
to produce a high-level function or result.
These schemes necessarily are limited, as they require growing amounts of
table space and still provide limited performance in developing even an
approximate result.

Schwarz [P19] has shown that since these functions 
can generally be represented as a power series 
(a series of terms involving the powers of the argument of the function), 
they can be approximated by making special use of the partial product 
tree of a multiplier.
The partial product tree of a multiplier is that portion of a multiplier
that sums up 53 multiples of the multiplicand.
Each multiple is shifted by a power of two 
with respect to the other multiples.
Thus, the partial product tree represents a sum of 53 terms in a series with
the multiplicand being the argument. 
Schwarz noted that it is possible to enter an argument and,
instead of simply replicating it (originally the multiplicand)
53 times by providing modified versions of the argument
(ANDed or exclusive-ORed with various constants), we could make
approximations to the power series for these high-level functions.
The basic manipulations are determined
by backsolving an equation that approximates the function to be determined.
Using these techniques, it is possible to get an
approximation to all of the trig functions as well as the transcendental
functions generally accurate to between 11 and 20 bits.
This is all accomplished with only a slight increase in multiplier hardware,
and it is accomplished in the same time as that to compute a product.



\subsection{MCM Technology}

Considerable progress has been made in the area of 
high-performance packaging.  In particular, a 
technology for attaching and connecting chips onto a silicon 
membrane multichip module (MCM) has been demonstrated [P2]. 
This technology utilizes conventional IC processing 
techniques and offers a high density (over 500 per chip) of 
small (as small as $10\times10\;\mu m^2$), low resistance (less than 
0.024 $\Omega$/contact) and low parasitic interconnections between a 
chip and the substrate (see Figure~\ref{abc}).  
In addition, controlled impedance 
striplines have been fabricated on the MCM substrate.


\begin{figure}[p]
\centering
\protect\addcontentsline{toc}{subsection}{Figure 3: Membrane MCMs}

\vspace{7.75in}\special{psfile=wheling.ps vscale=.95 hscale=.95 hoffset=-90 voffset=-120} 
\caption{
(a) Membrane multi-chip module in Si.
(b) Process steps for making membrane MCM substrate.
(c) Time domain reflectometry.}
\label{abc}
\end{figure}


The initial experimental striplines have been implemented 
in a three-layer ground-signal-ground configuration with 
aluminum conductors and polyimide dielectric.  The sandwiched 
structure ensures a constant characteristic impedance as the 
stripline crosses the boundary between the MCM substrate and 
the chip.  The stripline has been characterized with time 
domain reflectometry.  The delay is 68 psec/cm which 
corresponds to a propagation velocity of $1.5 \times 10^{10}$ cm/sec.  
A pulse rise time of 72 psec, which corresponds to a $-3$dB 
bandwidth of 3 GHz, has been measured on a 1-cm long line.  
These results are consistent with those predicted by simulations.



\subsection{Advanced Packaging}

Ultimately, SNAP depends on extremely fast interconnects 
with a large array of die to package connections.
In addition to its MCM work, SNAP has undertaken other advanced experimental
packaging approaches to support 50--100 picosecond signal rise times and 
high-density interconnects.


\subsubsection{Microcontacts}

Despite the fundamental advantages of high density packaging, the
introduction of advanced technology has been very slow. One of the
difficulties has been the unreliability of low-force pressure contacts which
has hampered exhaustive testing of chips prior to mounting and has
restricted our choice of high-density, reversible mounting technologies
(such as the original active substrate configuration). 

To attack this problem, we designed, built, and carried out preliminary
experiments with a novel instrument that is essentially a combined scanning
tunneling microscope and atomic force microscope (STAFM). 
This allowed us to measure the electrical properties of contacts 
with controllable forces down to a few $nN$, 
many orders of magnitude below those normally employed. 
In this way, we can not only study low-force contacts per se, 
but can build up a model of macroscopic contacts 
as arrays of STM's in parallel. 

In the preliminary experiments carried out under this contract, 
we were able to demonstrate electrical conduction between gold surfaces 
quite close to the value predicted by the deformation of a gold surface 
under the action of the tip.  
This apparatus was the subject of a paper presented at the Holm
conference on contacts in 1992.  
Because this work was judged to have medium-to-short term applicability, 
the project was picked up by the SRC in 1991.


\subsubsection{Superconducting Chip-to-chip Interconnects}

High density of on-chip circuitry leads to higher speed, lower power, 
and, apparently, to greatly reduced cost per function. 
Higher density at the system level should also lead to equivalent gains. 
Indeed, it is now being argued that achieving such gains 
is much more practical by increasing the density of chip-to-chip 
interconnects because we are not pushing the state of the art in 
high-resolution fabrication in such interconnects; dimensions of 
chip-to-chip interconnects are typically expressed in mils, not microns. 
However, studies both in the U.S. and abroad show that the limit 
to achieving such density in normal metallic interconnects 
is set by the the resistivity of the metal 
(see, for example, Masaki \cite{Mas89}).
In our previous work, it appeared that a signal line pitch of about 
35 microns was the practical limit for terminated, matched transmission lines 
operating at a clock frequency of 1 GHz.

Given the above limit, the possible application of (high temperature)
superconductors in such transmission lines is obvious.  
An early (paper) study treated the high temperature superconductors 
as high-temperature analogs of low-temperature, metallic superconductors 
and predicted significant advantages at clock frequencies up to several GHz. 

Under this contract, we built transmission lines using the high-temperature
superconductor YBCO, and experimentally demonstrated that the predictions 
of the paper study held good for lines down to a few microns; 
i.e., the effects of the kinetic inductance 
(due to the low density of superconducting electron-pairs) 
in this material were negligible for frequencies up to 20GHz. 
The PhD dissertation of B. W. Langley \cite{Lan93} describing this work 
is in the final stages of preparation.




\subsection{List of NSF-Supported (SNAP) Publications}	\label{snappubs}

\newcounter{bean}
\begin{list}{P\arabic{bean}.}{\usecounter{bean}} 

\input publications

\end{list}

