Fundamental to the SNAP objectives is the development of very high speed
clocking techniques, which we call ``wave pipelining.'' These latchless
pipelines allow functional units to be clocked at significantly higher
repetition rates (2-3 times) than could be done with conventional designs.

In the area of algorithm improvement, SNAP work covers all of the
basic operations. We briefly report on some of the highlights of this
work in this paper.  In floating point addition, our work improves worst-case
latency by reducing the delay associated with rounding, and it improves average
latency by exploiting the distribution of operands in typical 
scientific applications. In floating point
multiply delay reduction is achieved by using redundant encoding of
a higher order Booth algorithm. This reduces the height of the partial
product tree without incurring delay due to the generation of ``hard
multiples'' of the multiplicand (eg. $\pm~3M$.) We have also studied the
area and performance tradeoffs of different partial product trees as
well as the effects of wires and a fixed number of routing channels.

With the realization that performance of arithmetic processors
is not simply dependent upon the most advanced 
circuit design techniques and algorithms,
SNAP has advanced packaging and interconnection technology.
By using MCM packaging technology, we are able to separate the
data processing and communication functions in a subnanosecond
processor and then optimize the technology for each.
Figure \ref{fig:snap} is a block diagram of the SNAP processor.
It consists of a MCM substrate with multiple 
functional unit die and high-speed interconnection.
 
\begin{figure}[htb]
\centerline{\psfig{figure=snap2.idraw,width=3in}}
\begin{center}
\begin{minipage}{3in}
\caption{SNAP Processor.\label{fig:snap}}
\end{minipage}
\end{center}
\end{figure}

In most of our work we validated our techniques by realizing implementations.
Table 1 is a summary of our chip fabrication activities.

\section{Algorithms and Systems}

In the remainder of this paper we summarize some of the techniques and 
algorithms which have been developed.

\subsection{Wave Pipelining} 

In an effort to improve the operating frequency of arithmetic processors
using conventional
technologies, we have employed wave pipelined
design techniques for standard bipolar and CMOS fabrication technology.

% THEORY

Wave pipelining, or maximum rate pipelining, is a circuit design technique
which allows digital
synchronous systems to be clocked at rates higher than can be achieved
with conventional pipelining techniques by relying on the predictable finite
delay through combinational logic for virtual data storage.
Conventional pipelined systems allow data to propagate from a register
through the combinational network to another register prior to initiating
the subsequent data transfer.  Thus, the maximum operating frequency is
determined by the maximum propagation delay through the longest pipeline stage.
Figure \ref{fig:wave} contrasts the timing of a conventional pipeline and a 
wave pipeline.  In the wave pipeline, data 2 is output from the source
register to the combinational logic prior to data 1's arrival at the
sink register.

\begin{figure}[hbt]
\centerline{\psfig{figure=wave.idraw,width=3in}}
\begin{center}
\begin{minipage}{3in}
\caption{Conventional and Wave Pipeline Timing.\label{fig:wave}}
\end{minipage}
\end{center}
\end{figure}

The clock period $T_{clk}$ of a conventional pipelined circuit is limited by
the maximum propagation delay through a logic network $P_{max}$, the
uncontrollable clock skew $\Delta C$, and register overhead $T_{reg}$ by:

\begin{displaymath}
T_{clk}>P_{max}+\Delta C+T_{reg}
\end{displaymath}

Wave pipelined systems apply the subsequent data to the network as
soon as it can be guaranteed that it will not interfere with the current
data wave.  The maximum operating frequency of a wave pipeline is therefore
determined by the difference between the maximum propagation delay and the
minimum propagation delay in the combinational logic.

The clock period $T_{clk}$ of a wave pipelined circuit is limited by
the variation in propagation delay through a logic network
($P_{max}-P_{min}$), uncontrollable clock skew $\Delta C$,
and register overhead $T_{reg}^{'}$ by:

\begin{displaymath}
T_{clk}>P_{max}-P_{min}+2\Delta C+T_{reg}^{'}
\end{displaymath}

The primary
causes of data wave interference are the variation in the propagation delay
due to differences the delay along separate
paths, differences in the rate of propagation due
to the state of the network inputs and intermediate nodes, and
difference in fabrication and environmental conditions.

% TOOLS
\subsubsection{Wave Pipelining Tools and Techniques}

To maximize the performance of wave pipelined arithmetic circuits, the
variations in delay through the combinational logic must be minimized.
Automated delay balancing tools have been developed as part of the SNAP
research effort.  These tools balance the propagation delay of all
paths by inserting delay buffers and by modifying the individual bipolar
[P28] and CMOS gates to increase the delays along the paths which are faster
than the critical paths.

Run-to-run process variation can have a significant impact on propagation
delay.  Maximum to minimum delay along the same path for seven different 
runs of a one-micron feature size CMOS fabrication process
was found to be 1.35x [P9].  Unless this variation is
controlled, all wave pipelined logic will be limited to speedups of
two to three to ensure that devices from any of these runs will operate over
a specified clock interval.
To counteract the effects of process variation, we have developed an adaptive
supply
voltage method. An on-chip detector circuit determines if the propagation
delays are faster than the nominal delays and the power supply is lowered
until the delay approaches the anticipated delay.   In this manner, ICs
fabricated with fast processes are run at a lower supply voltage to
ensure correct operation over the frequency range for which they were designed.

% VLSI CHIPS
\subsubsection{Wave Pipelined VLSI designs}

Wave pipelining has been used in the development of ECL and CMOS
arithmetic VLSI designs.  A wave pipelined ECL
population counter which can be clocked at 2.5 to 3-times the rate
that the circuit could be operated without wave pipelining was developed [P29].
The worst-case delay of this circuit is 10~ns and the minimum
clock period for wave pipelined operation is 4~ns.

Wave pipelining was used in the development of a CMOS 16-bit multiplier which
operates at 300-350~MHz [P8].  This VLSI chip is clocked at a
rate 3.7-times a nonpipelined design could achieve.

To demonstrate that this technology can be applied to arithmetic
system design, we have developed a CMOS wave pipelined vector unit.  Extensive
use of wave pipelining was employed to achieve high clock rates in the 
functional units.  The VLSI processor consists of a wave pipelined
vector register file, a wave pipelined adder, a wave pipelined
multiplier, load and store units, an instruction buffer, and a scoreboard
and control logic.  The register file, adder, and multiplier were designed
to operate with less than a 2~ns variation in propagation delay.  

The adder takes 16-bit unsigned
operands and produces a 16-bit result with a maximum delay of 5.5~ns. 
Register add operations have a 3 cycle latency.

The multiplier takes 8-bit unsigned operands and produces a 16-bit
result in a maximum of 10.8~ns. The multiplier is
constructed with (4,2) counters and employs an additional parallel adder.
Booth encoding is not used.
Register multiply operations have a 5 cycle latency.

The vector register file consists of 5 vector registers.
Each vector register has sixteen 16-bit elements.  The registers have separate
read and write ports and local address generation to optimize for cycle time.
Read access time is less than 3.4~ns and minimum cycle time is 2~ns for the
register file.

The VLSI vector unit contains approximately 47000 transistors and
occupies an area of 43~sq~mm.  It has been fabricated in a 1~micron
CMOS technology.  Correct operation at 300~MHz has been verified.
Figure \ref{fig:wpphoto} is a die photo of the wave pipelined vector unit.
Figure \ref{fig:vslam} details the vector register-to-register wave pipelined
multiply operation at 300~MHz.

\begin{figure}[htb]
\centerline{\psfig{figure=wpphoto.ps,width=2.8in}}
\begin{center}
\begin{minipage}{3in}
\caption{WP Vector Unit Die Photo.\label{fig:wpphoto}}
\centering{\footnotesize\sf 300MHz, 43 sq mm, 1 micron CMOS}
\end{minipage}
\end{center}
\end{figure}

\begin{figure}[htb]
\centerline{\psfig{figure=vslam.epsi,width=3in,angle=90}}
\begin{center}
\begin{minipage}{3in}
\caption{WP Vector Unit Multiply.\label{fig:vslam}}
\end{minipage}
\end{center}
\end{figure}

We have developed bipolar and CMOS circuit design techniques and tools which
enable VLSI system design using wave pipelining.  We have demonstrated the
benefits of wave pipelining for arithmetic processors via an ECL population
counter, a CMOS multiplier, and a CMOS arithmetic vector unit designs.  Using
standard device fabrication technology these VLSI units achieve operating
frequencies of 250 to 350~MHz through the use of wave pipelining.

\subsection{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 [P20].

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.

We have shown that it is possible to
minimize the worst-case latency of floating-point addition by 
integrating the rounding
step with the final fraction addition [P21].
The traditional, two path, and SNAP algorithms are shown in
figure \ref{fig:add}.
The improvements are the result of creating up to four different results
and selecting the correct result.

\begin{figure}[htb]
\centerline{\psfig{figure=add.idraw,width=3in}}
\begin{center}
\begin{minipage}{3in}
\caption{Floating Point Addition Algorithms.\label{fig:add}}
\end{minipage}
\end{center}
\end{figure}

Existing addition algorithms perform rounding by first computing the
guard bit, round bit, and sticky bit. These bits then determine
if the result has to be rounded and if so, the result is incremented.
The SNAP algorithm sought to merge the increment step with the mantissa
addition step by having the mantissa adder computing multiple results 
in advance and then selecting the final rounded result.

\begin{table*}[hbt]
\begin{center}
\begin{tabular} {|l|l|l|} \hline

{\bf Operation} & {\bf Exponent} & {\bf Rounding need to consider}\\
\hline\hline

Effective add & don't care & - mantissa computes $Ma+Mb$ and $Ma+Mb+2$\\
 & & - rounding needs to account for a potential right shift. \\

Effective subtract & a. $Ea>Eb$ & - mantissa inverts $Mb$ and computes $Ma+Mb$ and $Ma+Mb+1$.\\
 & & - rounding needs to account for a potential left shift. \\

 &b. $Ea=Eb$ & - mantissa inverts $Mb$ and computes $Ma+Mb$ and $Ma+Mb+1$\\
 & &- mantissa inverts the results if the result is negative.\\
 &c. $Ea<Eb$ &- same as case (a) with $Ea$ and $Eb$ swapped.\\ \hline
\end{tabular}
\caption{SNAP Addition Rounding Operations.}
\end{center}
\end{table*}

Table 2 shows the possible events that can happen in an addition and
the events that the rounding algorithm has to consider. In the table, 
$Ex$ and $Mx$ stand for the exponent and mantissa of operand $x$. When the 
effective operation is addition, the mantissa adder computes
$Ma+Mb$ and $Ma+Mb+2$
and select the proper result. To compute $Ma+Mb+2$, there is a row
of half adder before the mantissa adder. The result $Ma+Mb+2$ is needed
when a right shift and a round is needed at the same time. The result
$Ma+Mb+1$ is needed when there is no right shift and a round is needed.
$Ma+Mb+1$ is computed by inverting the $lsb$ of the result $Ma+Mb+2$ or
the result $Ma+Mb$. In either case, a simply inversion of the $lsb$
suffices and no carry propagation is needed.

For effective subtraction, two cases need to be considered: $Ea>Eb$ and $Ea=Eb$.
The $Ea>Eb$ case is quite straightforward because computing $Ma-Mb$ and $Ma-Mb+1$ 
is enough to cover all the cases. A complication arises in the $Ea=Eb$
case and the result is negative because IEEE standard calls for a positive 
mantissa. This case can be handled as follows. $Mb$ is first inverted and added
to $Ma$. If the result is negative, the result itself is bit-inverted to obtain
a possible mantissa. Again, no carry propagation is needed.

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.
Using a conventional 1-micron CMOS process, the floating-point
addition delay is about 15--16 nanoseconds 
(IEEE standard floating-point addition).

As another part of the SNAP effort, we have demonstrated that it
is possible to reduce the average latency of floating-point addition
below that of the worst-case [P14]. It has been shown that additional 
performance can be achieved in dynamic instruction scheduling processors 
by exploiting the distribution of operands that use the {\em CLOSE} path
where $|Ea-Eb| \leq 1$. 

Rather than letting the {\em CLOSE} path hardware sit idle during
the first cycle, it is
possible to take advantage of duplicated hardware and initiate 
{\em CLOSE} path computation one cycle earlier. The operation of the proposed
algorithm is as follows. Both paths begin
speculative execution in the first cycle. At the end of the first cycle,
the true exponent difference is known from the {\em FAR} path where
$|Ea-Eb|>1$.
If the exponent difference dictates that the {\em FAR} path is the
correct path, then computation continues in that path for two more
cycles, for a total latency of three cycles. However, if the {\em CLOSE} 
path is chosen, then computation continues for one more cycle, with
the result available after a total of two cycles. 
While the maximum latency of the adder remains
three cycles, the average latency is reduced due to the faster {\em CLOSE} 
path.

Further reductions in the latency of the {\em CLOSE} path can be made
after certain observations. First, it can be seen that the normalizing 
left shift in the second cycle is not required for all operations.
A normalizing left shift can only be required if the
effective operation is subtraction. Since additions never need a left shift, 
addition operations in the {\em CLOSE} path can complete in
the first cycle.
Second, in the case of effective subtractions, small normalizing shifts, 
such as $d \leq 2$, can be separated from longer shifts. While longer
shifts still require the second cycle to pass through the full-length
shifter, short shifts can be completed in the first cycle through the
addition of a separate small multiplexor. Both of these cases
have a latency of only one cycle, with little or no impact on
cycle time. If these cases occur frequently, the average latency is 
reduced. A block diagram of the adder is shown in figure~\ref{fig:varadd}.
\begin{figure}[h]
\centerline{\psfig{figure=varadd.ps,width=3in}}
\begin{center}
\begin{minipage}{3in}
\caption{Variable latency adder.\label{fig:varadd}}
\end{minipage}
\end{center}
\end{figure}

It has been determined that 43\% of the operands in
the SPECfp92 applications use 
the {\em CLOSE} path, resulting in a speedup of 1.17 for the
base variable latency algorithm. By allowing effective additions in the
{\em CLOSE} path to complete in the first cycle, a speedup of 1.27 is
achieved. For even higher performance, an implementation of the 
{\em One Cycle} algorithm achieves a speedup of 1.33
by allowing both effective additions and effective subtractions 
requiring very small normalizing shifts to complete in the first cycle. 

\subsection{Floating-point Multiplication}

In a multiplication study, we developed a scheme based
upon a redundant 3-bit Booth encoding of the multiplier [P2].
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 times 
the multiplicand ($\pm~3M$) using a wide carry propagate adder.

The conventional Booth 3 algorithm assumes that the $3M$ multiple is
available in non-redundant form.  Before the partial products can be
summed, a time
consuming carry propagate addition is needed to produce this multiple.
The Booth 3 algorithm with fully
redundant partial products avoids the carry propagate addition,
but has the equivalent of twice the number of partial products
to sum.  The new scheme tries to combine the small number of partial products from
the conventional Booth 3 algorithm, with the ease of the hard multiple
generation of the fully redundant Booth 3 algorithm.
 
The idea is to form the $3M$ multiple in a {\it partially redundant}
form by using a series of small
length adders, with no carry propagation between the adders (figure~\ref{partially_red_pp}).
If the adders are of sufficient length, the number of bits per partial
product can approach the number in the
non-redundant representation.  This reduces the number of bits needing
summation.  If the adders are small enough, carries will not be
propagated across large distances, and the small adders will be much faster
than a full
carry propagate adder.  Also, less hardware is required due to
the elimination of the logic which propagates carries between the
small adders. The new algorithm can achieve performance parity while reducing
the total area of the multiplier by 15-20\%.

\begin{figure}[hbtp]
\centerline{\psfig{figure=partially_red_pp.ai,width=3in}}
\begin{center}
\begin{minipage}{3in}
\caption{Computing 3M in a partially redundant form. \label{partially_red_pp}}
\end{minipage}
\end{center}
\end{figure}

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 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 has been implemented in ECL with the sponsorship of SUN Microsystems.
Figure \ref{fig:mulphoto} is a die photo of the multiplier.
The delay of the multiplier is shown in figure \ref{multcp}.

\begin{figure}[htb]
\centerline{\psfig{figure=mulphoto.ps,width=2.25in}}
\begin{center}
\begin{minipage}{3in}
\caption{SNAP Multiplier Die Photo.\label{fig:mulphoto}}
\centering{\footnotesize\sf 5~mm~x~3~mm, 0.6~micron BiCMOS}
\end{minipage}
\end{center}
\end{figure}


%The full multiplier is expected to have an overall delay of 
%five nanoseconds (see Figure~\ref{multcp}).

\begin{figure}[htb]
%\centerline{\psfig{figure=multcp.ps,width=2.5in}}
\centerline{\psfig{figure=multcp.ps,width=2.5in}}
\footnotesize
\begin{picture}(240,45)
\put(1,25){input ($t=0$)}
\put(1,05){tree output ($t=4.3$ns)}
\put(100,25){final product ($t=5.2$ns)}
\put(100,05){$3x$, $1x$ multiples ready ($t=0.6$ns)}
\end{picture}
\begin{center}
\begin{minipage}{3in}
\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}
\end{minipage}
\end{center}
\end{figure}

In another study [P1], we have investigated the effects of the different
methods of connecting the counters on the possible circuit realizations 
when constrained with a fixed number of routing channels.
Further, the effects of wires have been quantified 
as the technology scales for different partial product trees
used in the design of multioperand adders and the different partial
product encoding schemes.

\begin{figure}[hbtp]
\centerline{\psfig{figure=wires.ps,width=3in}}
\begin{center}
\begin{minipage}{3in}
\caption{Effects of wires on multiplier delay.
\label{fig:wires}}
\end{minipage}
\end{center}
\end{figure}

Figure~\ref{fig:wires} shows the effects of wires on the total delay for
Booth 2 encoding when using a binary partial product tree composed of
4-2 counters. It is apparent that the effects of the wire capacitance
are greater at smaller feature sizes. This is due to the wire
capacitance providing a greater portion of the total capacitance for the
circuit at smaller feature sizes. For extremely small feature sizes, the
wire capacitance is dominated by fringing capacitance, which is
proportional to the wire lengths and scales linearly with a reduction
in feature size. This is in contrast to the transistor
capacitance which is proportional to the transistor area and scales
quadratically with a reduction in feature size. This behavior is
observed across all partial product encoding schemes. 

\vspace{1mm}
\subsection{Division and Higher Level Functions}     \label{ems}

Advances in the performance and correctness of division and higher level
functions have been made in the SNAP research effort.

\vspace{-2mm}
\subsubsection{Approximation Theory}

Significant accomplishments have been made in SNAP
in the field of approximation
theory and its application to starting approximations.
Traditionally look-up tables have been used to
accelerate division and other high-order arithmetic operations.
In our study [P23], a non-traditional approach of
back-solving logic equations is used.  We further prior research
in this area \cite{stef, mand},
by creating a generic method for
describing approximations and suggesting a unique implementation
of reusing the hardware of a multiplier.  In this manner,
division and other high level functions can be accelerated
with high-precision approximations at little cost.

These approximations are described in terms of a
general Partial Product Array (PPA).  A binary multiplication's
PPA consists of the bits of the multiplier logically
ANDed with the bits of the multiplicand.  Each element
in the array is a 2 input logical AND of a multiplier
bit and a multiplicand bit.  These elements are summed by
a large counter tree and a carry propagate adder to form the product.
Our work focused on creating the optimal PPA which describes
an approximation to a function such as the reciprocal function.  Instead of
using array elements that are 2 way ANDs they were replaced
with any type of Boolean logic gate.  By using a similar array
to the multiplier's PPA, the counter tree and adder could be reused.
The use of a PPA to describe an approximation of a function
and reusing an existing multiplier was founded by the SNAP project.

An example of deriving a PPA approximation for the reciprocal function
is shown.  First, the PPA of a multiplication
($B * Q = 0.111\cdots$) is back-solved in terms of the multiplier ($Q$).

\[
%\footnotesize
\arraycolsep=0.1pc
\begin{array}{r|r|r|r|r|r|rrrrr||l}
\multicolumn{1}{r}{ }&\multicolumn{1}{r}{ }&\multicolumn{1}{r}{ }&
\multicolumn{1}{r}{ }&\multicolumn{1}{r}{0{\bf .} }&\multicolumn{1}{r}{1 }&
   b_{2}  &   b_{3} &  b_{4}  & b_{5}    & \cdots & = B\\
\multicolumn{1}{r}{ }&\multicolumn{1}{r}{ }&\multicolumn{1}{r}{ }&
\multicolumn{1}{r}{X}&\multicolumn{1}{r}{q_{0}{\bf .} }&
\multicolumn{1}{r}{q_1 }&   q_{2}  &   q_{3}&  q_{4}  & \cdots & & = Q\\
\hline
&          &          &          &
&         & \vdots   & \vdots   &\vdots & \vdots &\cdots\\
&          &          &          &
&     q_{4}&b_{2}q_{4}&b_{3}q_{4}&b_{4}q_{4}&b_5q_4&\cdots\\
&          &          &
&     q_{3}&b_{2}q_{3}&b_{3}q_{3}&b_{4}q_{3}&b_5q_3 &\cdots &\\
&          &          &     q_{2}&b_{2}q_{2}&b_{3}q_{2}&b_{4}q_{2}&b_5q_2
&\cdots & &\\
&          &     q_{1}&b_{2}q_{1}&b_{3}q_{1}&b_{4}q_{1}&b_5q_1&\cdots & & &\\
&     q_{0}&b_{2}q_{0}&b_{3}q_{0}&b_{4}q_{0}&b_5q_0&\cdots & & & &\\
\hline
0.& 1 &   1  &   1  &   1 & 1 &\cdots &  &  &  &  & \approx 1.0
\end{array}
\]


By choosing the quotient digits appropriately in a redundant notation,
each column of the PPA forms an independent equation.
\begin{eqnarray*}
q_0 &= & 1\\
q_1 + b_2q_0& = & 1  \\
q_2 + b_2q_1 + b_3q_0 & = & 1 \\
q_3 + b_2q_2 + b_3q_1 + b_4q_0 & = & 1 \\
q_4 + b_2q_3 + b_3q_2 + b_4q_1 + b_5q_0& = & 1 .
\end{eqnarray*}

These equations are solved to yield the
following formulations for five digits of the quotient:
\begin{eqnarray*}
q_0 &= & 1\\
q_1 & = & 1 - b_2 \\
q_2 & = & 1 - b_3 \\
q_3 & = & 1 - b_2 + 2b_2b_3 - b_3 - b_4 \\
q_4 & = & 1 - b_2b_3 - b_4 + 2b_2b_4 - b_5 .
\end{eqnarray*}

These equations are used to form the PPA of the approximation.
\[
\begin{array}{rrrrrrrrr}
q_0 & & q_1& & q_2& & q_3       & &q_4\\\hline
\hspace{0.2in}&\hspace{0.2in}&
\hspace{0.2in}&\hspace{0.2in}&
\hspace{0.2in}&\hspace{0.2in}&
\hspace{0.2in}&\hspace{0.2in}&
\hspace{0.2in}\\
    & &    & &    & &-b_4   & &-b_5\\
    & &    & &    & &-b_3   & &2b_2b_4\\
    & &    & &    & &2b_2b_3& &-b_4\\
    & &-b_2& &-b_3& &-b_2   & &-b_2b_3 \\
1   & & 1  & & 1  & & 1     & & 1
\end{array}
\]

Reduction of the Boolean elements is performed, such
as applying the equivalency
$1 - b_i = \overline{b_i}$ or representing $2b_j$
by $b_j$ in the next more significant column.
If a large multiplier is available such as one having 53 rows,
a PPA can be developed which has a minimum of 12 bits correct
for the reciprocal function.  This high-precision approximation
can be used as a starting approximation to accelerate a
multiplicative division algorithm.

This technique has been developed for many operations such
as the square root, logarithm, exponential, and several trigonometric
functions.  For the square root operation, a PPA with a minimum of 16 bits
was determined.  This enables a square root algorithm to require one
less iteration than the typical 8 bit ROM implementations.
Thus, several cycles can be saved by using the PPA approximation technique.

Further research is aimed at overcoming the irregularity of the
PPAs in physical design.  Also other techniques for deriving
PPAs have been suggested such as using other approximation
techniques expressed in PPA form.
The optimal PPA for a function has yet to be determined, though
PPAs which provide a minimum of 8 to 16 bits correct have been shown.
PPA implementations create high precision approximations
at very low cost with the latency of a multiplication.

\subsubsection{Correctness of Division Algorithms}

One currently hot topic in computer arithmetic
is how to insure the correctness of high order
arithmetic functions such as division.
Rather than addressing one
of simpliest algorithms for division such
as non-restoring radix-4 division, we have focused
our research on one the most difficult algorithms,
the Goldschmidt algorithm.  Non-restoring division
algorithms and even the Newton-Raphson algorithm
are self-correcting algorithms and can be proven correct
by analyzing a generic iteration.  The Goldschmidt
algorithm accumulates errors each iteration and thus
needs to be analyzed for all iterations.
This algorithm is very attractive due to its quadratic
convergence.  The Newton-Raphson algorithm also is
quadratically converging
but the Goldschmidt algorithm has the advantage that
some of the operations can be computed in parallel.
Thus, our task has been to prove the correctness of
implementations of the Goldschmidt algorithm.

We intend our research in this area to provide guidelines
for designers that will insure the correctness of their
implementations.  We have tried to generalize the
derivation for any length operands and any multiplier
type.  Currently we have finished the derivation for
a rectangular multiplier of $N$ by $N+G$ bits where
$N$ is the number of bits desired and $G$ is the necessary
guard bits.  The relationship of $G$ to table size and
$N$ has been determined.
The proof of the algorithm has paralleled the development
of a S/390 CMOS microprocessor which will hopefully
serve as an example application of this research.
This research will provide guidelines for
the correctness of any implementation of the Goldschmidt
algorithm.

\subsection{System Performance}

We have investigated in detail the relationship between division 
latency and system performance [P15]. 
System performance was evaluated using 11 applications from the SPECfp92
benchmark suite.
The applications were each compiled on a DECstation 5000 using the MIPS
C and Fortran compilers at each of three levels of optimization.
The excess CPI due to division is determined by summing all of the
stalls due to division interlocks, which is the total penalty, and
dividing this quantity by the total number of instructions executed.
The performance degradation due to division latency is
displayed in figure~\ref{fig:cpiarea}. 

\begin{figure}[hbtp]
\centerline{\psfig{figure=cpiarea.ps,width=3in}}
\begin{center}
\begin{minipage}{3in}
\caption{CPI and area vs division latency.
\label{fig:cpiarea}}
\end{minipage}
\end{center}
\end{figure}

This graph shows how the excess
CPI due to the division interlocks varies with division unit latency
between 1 and 20 cycles when compiled with high optimization.
Figure~\ref{fig:cpiarea} also shows the effect of increasing the
number of instructions issued per cycle on excess CPI due to division, 
and it also shows how area increases as the functional unit latency decreases. 
The data shows that to achieve reasonable system
performance, some form of hardware division is required. 
However, at very low divider latencies, two problems arise.
The area required increases exponentially or cycle time becomes
impractical. 
This study shows a knee in the area/performance curve near 10 cycles.
Dividers with lower latencies do not provide significant system
performance benefits, and their areas are too large to be justified.  

In a separate study [P6], we developed a cost-performance metric for
evaluating floating-point
unit implementations. The metric, {\bf F}loating Point {\bf U}nit Cost 
{\bf P}erformance {\bf A}nalysis Metric (FUPA), 
incorporates five key aspects of VLSI
systems design: latency, die area, power, minimum feature size
and profile of applications.
FUPA utilizes technology projections based on scalable device models
to identify the design/technology compatibility, and allows
designers to make high level tradeoffs in optimizing
FPU designs.

We summarize the five steps of computing FUPA as:
\begin{enumerate}
\item   {\bf Profile the applications} to obtain dynamic floating point
operation (add/sub, multiply, and divide) distribution in the application,
\item   {\bf Compute Effective Latency (EL)} from the clock rate, FPU 
latencies, and the dynamic FP operation distribution obtained in 
step 1,
\item   {\bf Measure the die area (Area)} of the FPU not including the
register file,
\item   {\bf Compute Normalized Effective Latency (NEL) and Normalized
Area (NArea)}, removing the feature size dependency, and
\item   {\bf Compute FUPA} where \\ $FUPA=\frac{(NEL)(NArea)}{100}$.
\end{enumerate}

Example applications of FUPA to recently announced processors is shown
in table 3.
\begin{table*}[htbp]
\centering {{\small Table 3: FUPA components and results of recently announced processors}}
\bt{|lllll|}
\hline
Processor&  Effective & Normalized & Normalized Effective& FUPA\\
         &  Latency (ns) & Area ($mm^{2}$)& Latency (ns)& ($cm^{2}ns$)\\
\hline
\hline
DEC21164      & 12.38   & 77.51  & 35.36     &27.41  \\
\hline
MIPS R10000   & 14.25  & 70.08  & 40.71 &   28.53\\
\hline
PA8000        & 24.44      & 81.16 & 48.89     &39.68  \\
\hline
Intel P6      & 28.25  & 51.56  & 80.71 &  41.61 \\
\hline
SUN UltraSparc& 23.65  & 133.43 &  50.32 &  67.15\\
\hline
AMD K5        & 66.00     & 48.42  & 188.57    &91.32  \\
\hline
\et

\end{table*}


\subsection{MCM Technology [P5]}

Considerable progress has been made in the area of 
high-performance packaging for SNAP.  In particular, a 
technology for attaching and connecting chips onto a silicon 
membrane multichip module (MCM) has been demonstrated by S. Wong
and his colleagues [P5]. 
This package 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.


%\vspace{-1in}
\begin{figure}[htb]
\centerline{\psfig{figure=wheling.ps,width=3in}}
\begin{center}
\begin{minipage}{3in}
%\vspace{-1in}
\caption{Membrane multi-chip module in Si. [P5]\label{abc}}
\end{minipage}
\end{center}
\end{figure}
%\vspace{-0.5in}

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 delay has been measured at 68~psec/cm which 
corresponds to a propagation velocity of $1.5 \times 10^{10}$ cm/sec.  
A pulse rise time of 72~psec has been measured on a 1-cm long line.  

\section{Summary} 
By employing a unified, multidisciplinary approach to high-performance
arithmetic research, SNAP has made significant progress toward the
development of a gigaflop computing element.  Improvements in clocking
methods, algorithms, tools, and packaging technology have been demonstrated
in implementations of high-performance VLSI adders, multipliers, and
a vector unit.

\subsection*{Acknowledgments}
This work was supported by NSF under contract MIP93-13701.
Support for K. Nowka was provided by an ARPA Fellowship in High Performance
Computing administered by the Institute for Advanced Computer Studies,
University of Maryland. Support for E. Schwarz was provided by the IBM
Resident Study Program.


\subsection*{Partial List of SNAP Publications}  \label{snappubs}

The following is a partial list of publications related to the SNAP
project.  Recent publications and information on the SNAP project and
researchers may be obtained through the World Wide Web using the URL
http://umunhum.stanford.edu.

\newcounter{bean}
\begin{list}{[P\arabic{bean}]}{\usecounter{bean}} 

\input publications

\end{list}

\begin{thebibliography}{10}

\bibitem{stef} R. Stefanelli.  ``A suggestion for a high-speed parallel
binary divider,''
{\em IEEE Transactions on Computing,} Jan. 1972, pp. 42-55.


%\end{thebibliography}

%\end{document}

