%%% * Last edited: Sep  5 19:32 1996 (misha)

\chapter{Abacus Chip \chaplabel{chip}}

This chapter describes the design, implementation, and testing of the
Abacus-1 chip in considerable detail. After reading this section, the
reader should understand the issues involved in the design of a high-speed
SIMD computer. The discussion focuses on the implementation, assuming that
the broad architectural issues were previously decided.  Of course in
reality the design did not proceed unidirectionally from architecture to
implementation; low level issues significantly affected the architecture.

The design goals of the Abacus-1 chip were not simply to obtain the highest
possible performance, but more importantly  to investigate issues
of high-speed SIMD computers. Therefore,  performance improvements at the cost
of higher complexity and lower clock rate are not desirable.\footnote{Hard
  to justify --Carlin}  Further, the
high speed must transfer over to the system level, so the chip design must
handle inter-chip synchronization effectively.  Proceeding up the
hierarchy, the lessons learned from the design must apply to practical
systems.  A critical requirement of real systems is the capability of
expanding the memory allocated to each processing element.  Finally, the
system must support high speed (at least real-time) I/O of image data.

A large collection of on-chip subsystems is required to satisfy these
goals. The subsystems can be divided into three broad categories: the
processing element core that performs the computation; the off-chip
interface that delivers network, instruction, and data streams to the core;
and the control logic that binds the two together. This chapter addresses
each of these categories in turn.

%This partition is somewhat
%misleading since many of the the design issues are tightly coupled, but the
%text highlights key interactions. Packaging of the chip plays a key role in
%high-speed performance, but it is more naturally described in Chapter 4.


\section{Processing Element Core}

%The discussion proceeds from the bottom up.  First, we describe the basic
%processing element. We then discuss the network connecting the PEs and the
%network support circuitry within the PE. We then worry about delivering
%data to the array and describe the Data and IO planes. We then worry about
%delivering instructions to the array and describe the instruction
%distribution system.  Each PE consists of some memory, an ALU, and an
%interconnection network.  Unlike conventional microprocessors, there is no
%instruction memory, since identical instructions are delivered to all PEs.


\subsection{Memory }

\paragraph{Design}
Processor memory size is a critical design parameter as it is the main
determinant of the overall processor size and therefore the number of PEs
per chip.  Too little on-chip memory, and machine performance becomes limited
by off-chip memory bandwidth; too much memory and the amount of processing
power on a chip drops. Thus, the memory size should be carefully chosen
based on extensive simulations.

In the case of the Abacus-1 chip, the choice was mostly guided by
intuition. There are only a few feasible sizes, ranging between 32 and
1024 bits. The low end of the range is inefficient as much of the memory
is consumed by configuration and temporary bits.  The 32-bit configuration,
in vertical mode, cannot perform any g algorithm that requires more than
two 16-bit data items. The 1024-bit configuration, in horizontal mode,
allocates 1 Kword per pixel site, which is far more memory than needed.
Two other disadvantages of larger memories are a longer access time, and
more address bits, which translates directly into higher instruction
bandwidth, already one of the more challenging board-level design tasks.
The Abacus-1 design has 64 bits of memory per PE.

\paragraph{Implementation}
The 64-bit register file is arranged as two banks of eight rows and four
columns. Each cell is a standard six-transistor SRAM cell. The bit and
\z{bit} lines are used single-ended to provide two read ports, allowing
four bits to be read and two written in each cycle.

The bitlines are precharged to $V_{dd}-V_T$ to speed pulldown time and
reduce power dissipation. Precharging is done through the column select
transistors, further reducing power by charging only those bitlines that
are about to be read.


The SRAM cell is susceptible to false writes, especially because the
bitlines are typically not charged to opposite values. Thus, the
high-capacitance bitlines, charged to opposing values during the read
phase, can act as a line driver, overwriting cells not selected by the
column selects. This problem is avoided by shorting the bit and \z{bit}
lines during the precharge interval, even if those lines are charged. In
other words, all bitline pairs are shorted, but only the ones to be read
are charged.

One of the key space-saving ideas was the integration of the five control
registers and the network interface into the SRAM array.  The initial
design included fully static master-slave flip-flops, multiplexers to
connect them to read busses, and separate control wires.  This auxiliary
circuitry substantially increased the non-ALU PE area.  In the current
implementation, edge cells in the SRAM array, together with buffers that
isolate the internal data storage node, are used as control registers.
  In the case
of the network and data plane registers, the multiplexing occurs inside the
SRAM cell.





\subsection{ALU}

\paragraph{Design}

The main design issue of the ALU is its range of computations.  The initial
ALU design was a 4:1 multiplexer that could compute all 16 two-input
one-output functions.  Computation of a full binary one-bit addition
therefore required five cycles, emulating all five 2-input gates.


The limited complexity is due to available data sources and sinks. A
single-ported memory bank can produce only two bits for reading, and can
absorb only a one bit result. If operations such as addition are required,
the extra input bit must come from another source such as an auxiliary
register or the communication network.

Previous bit-serial computers incorporated dedicated adders and carry
registers.  Abacus does not follow this approach because of the additional
area and because the circuitry is only useful in vertical mode.  A
dedicated full adder circuit would be useful in horizontal mode, assuming
its outputs could be steered appropriately, but it requires three input
bits while the memory only produces two per cycle.  The Abacus design's solution was based
on the realization that the memory required much more area than the ALU.
Splitting the memory into two banks doubles the memory bandwidth and adding
another ALU doubles the peak computing power.  If the ALU requires one
tenth of the memory area, the twin-bank, twin-ALU (TBTA) design occupies
1.1 times the area, but has 2.0 times the performance, for an overall
advantage of 1.8 over the single ALU. 


\begin{Table}{tbta}{Single vs Double Bank Design}{
    Silicon area requirements of the single-banked, single-ALU 
  and the twin-banked, twin-ALU designs.  As expected, silicon area
  increases by only 15\%.}
\begin{tabular}{|l|l|l|l|l|}
\cline{2-5}
\mcol{1}{c}{} & \mcol{2}{|c|}{SBSA} & \mcol{2}{|c|}{TBTA} \\ 
\hline
{\bf Circuit Element} &  \mcol{2}{|c|}{1 ALU, 1 bank} & \mcol{2}{|c|}{2
  ALU, 2 bank} \\
\cline{2-5}
  &  {\bf   Quant}&  {\bf  Area}  & {\bf Quant} & {\bf Area2} \\
\hline
Memory Array &     1 &   205 &     2 &   102 \\
Column Mux &       8 &    20 &     8 &    20\\
Read/Write Logic   &    1 &    18  &    2 &    36\\
Aux Logic &        1&     64 &     1&     64\\
ALU     &          1 &    38&      2&     76\\
Network &          1 &    52&      1&     52\\
\hline
Total   &  &           397 &  &         452\\
\hline
\end{tabular}
\end{Table}


%%% However, there are practical issues that cost more area than first
%%% expected.  The number of column select, ALU op code, and phase control wires increases as twice the number
%%% of column wires must be driven.  Although the gate load stays the
%%% same, the wiring capacitance increase is significant, and larger drivers
%%% are required.  Since the memory cell area is wire-limited, the new wires
%%% cannot run over the memory array, so the banks must be split, changing the
%%% PE aspect ratio to a long and thin cell. To maintain a square at the chip
%%% level, the PEs must be folded, adding further overhead in the network wires.

%%% The TBTA design requires twice as many row select, column
%%% select, phase control, and ALU op code wires. The wiring requirements
%%% increase from 36 to 72. Since gate loading and wire capacitance are
%%% approximately equal, eliminating one wire eliminates half a row driver.  So
%%% the second design requires 18 fewer row drivers to drive a block of 64 PEs.
%%% This is an improvement of 0.28 driver per PE. Each driver occupies 3500~\mm, or 42 length units.  The effective area is increased by 12 units to
%%% 465, for a 17\% instead of 15\% penalty.


A significant penalty occurs because the chip is pad-limited.  The inner
pad-ring is arranged in a 56 by 44 rectangle.  Without the 20 extra
instruction bits (corresponding to 10 double-cycled pads) the pad ring
could be reduced to a 51 by 44 rectangle.  Assuming a 170~micron pad pitch,
the area decrease is 6.4~\mm.  Since the entire PE array occupies 38.4~\mm,
the extra instruction bits cost an additional 17\% overhead.  As long as
the design remains pad limited, this effect will grow worse as technologies
scale down, mostly because the pad size stays constant while the PE density
improves.  Thus, any design decision that increases the number of chip pads
should be considered carefully.  This is an important example of how
architectural analysis must be done at all levels of design in order to be
accurate.

The algorithmic advantage is more difficult to quantify.  Each 3-input ALU can
perform an arbitrary 3-input operation each cycle, which could take a
2-input ALU at least 3 (and as many as 5) cycles. To see this, consider the
an arbitrary function of three boolean variables Z = f(A,B,C). Using the
Shannon expansion, Z can be expressed as 
\begin{equation}
\label{eqn:zfunc}
Z = (\overline{A} \cdot f_{A=0}(B,C)) + A \cdot * f_{A=1}(B,C))
\end{equation}
where the two subfunctions are obtained from the truth table entries
corresponding to the cases where A is 0 and 1 respectively.  Most useful
functions are actually simpler.  For example, consider the the multiplexing
operation \texttt{Z = (!A \& B) | (A \& C)}.\footnote{This function is used
  frequently when some bits must be conditionally updated.  The idiom is
  \verb|Z := mux(flag, Z, newZ)|.} For this function, $f_{A=0}(B,C)$ is
simply B, and steps 1 and 3 of \fig{threefunc} can be eliminated.

\begin{Figure}{threefunc}{Three Func}{Evaluation of an arbitrary 3-input
    function by a two-input ALU.  Two auxiliary memory locations are
    required.}
\tt
\begin{tabular}{lcl}
     T1 & = & f0(B,C)\\
     T1 & = & T1 \& !A\\
     T2 & = & f1(B,C)\\
     T2 & = &T2 \& A\\
     Z  & = &T1 + T2\\
   \end{tabular}
 \end{Figure}
 



 Converting to two 3-input ALUs improves the peak bit-manipulation
 performance by a factor of ten, but several effects limit this
 improvement.  First, the addressing is limited to sharing certain bits
 between the two banks.  Second, these five-cycle operations are relatively
 rare.  Third, data dependencies require waiting for bits to arrive from
 the network.

\tab{cyclecount}  shows the number of cycles required per arithmetic
operation, including reconfiguration overhead.  The ratio is about 1.75. Of
course, the proper instruction mix for real applications should be
evaluated for true improvements, but this analysis suffices to bound
performance improvement in the range of 1.25 to 2.1.


\begin{Table}{cyclecount}{Number of cycles in horizontal mode}{Number of cycles required for common operations in horizontal mode. The
  count includes reconfiguration cost.}
\begin{tabular}{|l|r|r|}
\hline
Operation & SBSA &  TBTA  \\
          & (cycles) & (cycles) \\
\hline
    Add  &            9  &      4 \\
Shift         &   4  &      3\\
Grid Move    &    7  &      6\\
Accumulate  &    10  &      4\\
\hline
Average    &    7.5  &    4.3\\
\hline
\end{tabular}
\end{Table}


There is another subtle effect of a more complicated ALU.  A 2-input
ALU can require up to two temporary storage locations to evaluate most
3-input functions.  When operating near the memory capacity, two memory
spills can have a substantial effect on performance.

We can now evaluate the overall advantage of the twin ALU design. The area
cost is dominated by the pad ring increase, and is a factor of 1.35. The
performance improvement is 1.75.  Thus, the overall advantage of the design
is only about 30\%. This advantage will increase slightly as compiler
technology improves and as memory accesses become more expensive.


\paragraph{Implementation.}
Each ALU is implemented as a precharged 8-to-1 multiplexer that uses three
data bits to select one of eight instruction bits.  Initial design used
predecoded cells but this was slower and larger due to the non-regularity.
This design does have four transistors in the pulldown path, but the timing
and capacitances are designed to minimize the body effect and reduce
charge-sharing problems.

\paragraph{Immediate Constant.}
The ALU also incorporates an additional circuit that allows the
architecture to support effective constant distribution. Without this
feature, there is no clean method of distributing a run-time value
generated in the scalar unit to the array. Indeed the only way of
transferring such a value would be to send it via the image IO interface.

Instead, the output of the left ALU passes through a NAND gate controlled
by a global wire common to each column of PEs. In normal operation, these
32 global ``literal'' wires are held at 1. When a constant is to be loaded,
the instruction decoder generates a \texttt{set} ALU op code, and loads the
literal bus with the logical inverse of the constant. Thus, in every column
whose bus is at 1, the result will be forced to a 0, as desired.

%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Network}
\paragraph{Design}

The two questions in network design are where the PE obtain its network
data and how does it route data around itself.  Two alternatives of routing
data are shown in \fig{nettypes}. The first, the two-channel crossbar,
allows messages to pass in a wide variety of directions. For example, the
PE can connect the north port to the east port while simultaneously
connecting the west port to the south.  The second is far less flexible,
and can only make one connection.


The original network design used four independent switches in a \mesh\
topology. Each switch had a dedicated control register.  The independent
switch control allowed many cluster configurations. 


\mypsfigx{4in}{net_types.epsi}{nettypes}{Network Types}{Various
  network types. The Abacus type is of the single channel, but even more
  restrictive in that each PE can turn on only one switch.}

The price of this flexibility is additional registers and increased
reconfiguration time. If a register is allocated to each switch, the four
registers represent 5\% of the total addressable registers.  More
importantly, reconfiguration time doubles.  Even with dual ALUs (which were
added primarily to speed reconfiguration), two cycles are required to
change topology.  Since reconfiguration may be required after each
arithmetic operation, and since most operations require only two or three
cycles, the additional 1 cycle penalty is a performance hit of
approximately 20\%.

\mypsfigx{\textwidth}{clusters.epsi}{netconfig}{Network
  Configurations}{Various network configurations.  Arithmetic, bit
  broadcast, and \mesh\ move modes are shown.  For example, broadcast of a
  bit to all 16 cluster elements can be done with only 8 ($2\sqrt{N}$)
  switch delays if the cluster is configured as a tree with fanout of 4.}


Reconfiguration time can be reduced at a slight loss in flexibility. Since
information flow in arithmetic operations is usually along the MSB/LSB
path, configuration in a line is usually sufficient.  The design
implemented in Abacus-1 incorporates a decoder to select only one of the
four switches, and a {\em connect\/} configuration bit that controls
whether any of the switches are activated at all. The addressing
cost of the two approaches is not substantially different: three registers
instead of four.  But now, changing reconfiguration directions requires
only one cycle, and conditional bypass, another frequent operation, also
requires only one cycle instead of two.

\mypsfigy{5in}{network.ps}{netblock}{Network Block Diagram}{Network
Block Diagram. Magnified view and \mesh\ view.}


%%% Actually, this design is also capable of the tree topology discussed
%%% earlier.  The key difference between the earlier version is that a
%%% processor can decide to connect itself to as many as all four of its
%%% neighbors.

\paragraph{Implementation.}
The on-chip communication network consists of a precharged
output node and four isolating switches. The node is a simple precharged
inverter whose input is driven by the network output register.  The four
switches are NMOS transistors driven by a 2:4 precharged decoder.


Communication with signaling times longer than a cycle period is performed
by controlling network precharge via software. As long as precharge is
turned off, processors connected to a bus node continue to discharge it.

Propagation delay across a series of pass transistors is usually quadratic
in the number of devices.  This delay is greatly reduced by a local
accelerator circuit at each node which regeneratively pulls a node to
ground as soon as the node voltage drops by a transistor threshold.  The
circuit is a dynamic NORA style circuit and is well suited to the
precharged operation of the network.  We found it to be several times
faster than an implementation based on a complementary inverter.  At the
nominal process corner, simulations show that a bit propagates through 18
switches and long network wires in one 8~ns cycle.


\mypsfigy{2in}{net-accel.ps}{netaccel}{Network Accelerator}{Network
  accelerator in the NORA circuit style.}

This circuit has a noise margin of $V_T$, so careful layout was done to
reduce coupling capacitance to the pre-discharged node.  Further, the chip
is provided with on-chip bypass capacitance and over 200 power and ground pins to
reduce dI/dt noise.



%%% \begin{Figure}{netcellschem}{Network Cell Schematic}{Network Cell Schematic}
%%% \vspace{1in} Network cell schematic\vspace{1in}
%%% \end{Figure}

% Integration with SRAM array. 

\subsection{Data/IO Planes}
The architecture supports a background loading mechanism for both the
external memory data and image data.  Data is shifted through the PE array
without interfering with computation. One memory location in each PE is
dedicated as the data plane (DP) registers.  All DP registers in a column
are connected in a 32-element shift register.  This shift register is
clocked by a global signal. The PE addresses the DP register as a normal
SRAM cell, and is not aware of the alternate write path. 
%%% The modified SRAM cell is shown in figure X.

\subsection{Global OR Operation}

The global OR (GOR) mode is used to signal completion of some computation
by the entire PE array to the sequencer.  Off-chip, the GOR is computed by
dedicated logic. On-chip, the GOR can be computed with the multiple-writer
capability of the network.  In this mode, all PEs connect their network
nodes into one chip-wide node. The shortest propagation path is obtained by
connecting all PEs in a row to the left-most PE of that row, and then
connecting all left-edge PEs together vertically, as in \fig{netconfig}.
The on-chip evaluation time is five cycles in the worst case.


\subsection{Layout Summary}
The simplicity of each PE resulted in a compact, 83~micron by 453~micron
implementation in a 2.6 micron contacted metal pitch technology.


\begin{Table}{resrouce}{PE Area Resources}{PE Area resources}
\begin{tabular}{|l|r|r|}
\hline
Subsystem & Area&  Percentage\\
          & (K\uu)&           \\
\hline
Memory      &  22.9 &    61.0\\
ALU         &   6.3  &    16.8\\
Network     &   6.2  &    16.6\\
Misc PE     &   1.2  &    3.1\\
Data Plane  &   1.0  &    2.6\\
\hline
\end{tabular}
\end{Table}


This data differs from the earlier table in that configuration registers
are now allocated to the resource they serve instead of to the memory
array. For example, there are four control registers (2 select, 1 connect,
1 data) dedicated to the network.  Similarly, two are dedicated to the I/O
and data planes.


%% PE Pictures
%%% \mypsfigx{\textwidth}{PE-bw-m2.ps}{pe-m2}{PE Layout}{PE Layout with metal-2
%%%   shown.}


\mypsfigx{\textwidth}{PE-bw-nm2.ps}{pe-nm2}{PE Layout}{PE Layout with the
  second layer of metal removed. {\bf ADD OVERLAYS}}





\section{On-Chip Signal Distribution }

A previously unanticipated design task was the challenge of distributing
control signals to the PEs.  As discussed in \sec{timing}, there are
four phases in the clock cycle, and each phase must complete before the
other can begin. For example, all word lines in the register file must be
unasserted while bitlines are being precharged, and any overlap may cause
memory cells to be overwritten. This nonoverlap is guaranteed by separating
the clock phases sufficiently to account for the worst case rise/fall
times.  Signal transitions that occur in the same phase but must follow
each other are separated by inserting an inverter or two as delay
elements.
%%\footnote{for example, the alu evaluate following the read} 

There are two problems with this approach. Given 8~ns cycle time of the PE,
each of the four phases has only 2~ns to rise, stay level, and fall. This
means that even if the level time is 1~ns long, each rise/fall time must be
500~ps or less%
%%% \footnote{The system cycle time is currently limited by
%%%   instruction wire uncertainties.  For example, the bit-precharge pulse
%%%   completes operation in 250~picoseconds, but the rise and fall times vary
%%%   by over 300~psec.}%
.  This is an aggressive RC product, given the long and narrow signal
wires and the high gate loading of the wire. The usual technique of simply
widening the signal wires cannot be used due to the wire density.  The
second problem is that even if the four phases can be safely separated,
non-overlap within the cycle by using inverters as delay elements may not
work because the variation in wire loading may dwarf inverter delays.  Both
of these problems can be addressed by local buffering of the global
signals.



\subsection{Load Equalization}

Local buffering both reduces the load on each wire and decreases the
variation between signal arrival times due to unequal loads. This section
describes the calculations used to obtain the load values, wire widths, and
row buffer sizes.

In addition to reducing the capacitive load by local buffering, the RC
product was improved by reducing wire resistance by widening the signal
traces. Although the wire capacitance increases, the lowered resistance
decreases the effect of the load capacitance, as shown in \eq{rcdelay}.
\begin{equation}
\tau = RC = \left( R_{\mbox{wire}} + R_{\mbox{driver}}\right) \left(
C_{\mbox{wire}} + C_{\mbox{driver}} \right)
\end{equation}

The equation can be made more rigorous to account for the distributed wire
loads and the lumped driver load, but those calculations do not capture the
most difficult characterization: the variation in wire capacitance due to
fringing fields and to the material underlying the wires.  Further, the
wire pitch, and therefore width and spacing, undergoes different
constraints in different parts of the circuit.  Instead of obtaining an
analytical solution for the wire width, spreadsheet models were developed
for common wiring situations and driver configurations, and used to
determine case-specific trace widths.



%%% The downside of widening the traces is the increased variability of wiring
%%% capacitance. Although process variation accounts for comparable capacitance
%%% differences (6\% to 7\% between nominal and maximum cases for both gate and
%%% wire capacitances), more of the total capacitance varies because the wire
%%% runs over different material. Also, wire separation decreases, which
%%% increases variability due to data-dependent capacitive coupling.  Both of
%%% these effects could in principle be computed by careful extraction and the
%%% use of 3-D Poisson field solvers.  
%%% until the last minute.

%%% The computations were done using a spreadsheet model shown in
%%% \fig{rcmodel}.  

%%% %Since  the  drivers  are so large, accurate  computation  of
%%% %output   capacitance  was  required.  This   is   relatively
%%% %straighforward,  but it was important  to  account  for  the
%%% %fingers-style layout of the buffers.
%%% \begin{Table}{rcmodel}{Row Driver RC delay calculation}{Row Driver RC delay calculation}
%%% \vspace{2in}
%%% \Large Table goes here
%%% \vspace{2in}
%%% \end{Table}




\subsection{Layout Issues: The Trench}
The Abacus-1 design had to deliver 76 signals across a 1 cm chip with very
little skew even though the array is tolerant of gradual signal skew across
the part since communication is purely local. Problems arise in two cases:
intra-PE signal skew and interfaces to logically synchronous zones at at
the pad ring.  The task was decomposed into two parts: delivering the
signals to the horizontal row drivers and then their outputs.  Vertical
signal delivery was not an issue due to the low resistivity of the metal 3
layer.  The design easily tolerated high uniform latency in instruction
distribution so the row buffers could be composed of several scale-up
stages. As a result, the loads presented to the vertical wires were that of
minimum sized inverters, and therefore dwarfed by wiring capacitance.  The
vertical wires were metal-3, 3.2~microns wide, and spaced by 3.3~microns.
The nominal capacitance of a 7~mm vertical wire is 2.5~pF, and the nominal
resistance is 75~ohms.  The distributed RC delay of this wire is only 184
picoseconds.
%%% which is obviously more than acceptable, especially since this
%%% means that the skew between neighboring rows is on the order of 12
%%% picoseconds.

The problem arises after the signals have been delivered on the vertical
wires. The row buffers are rather large, and there are 152 of them packed
into one PE height, 76 for each side.  This occupies a significant area,
and spans 1.1~mm!  Fully one-sixth of the core area is dedicated to these
buffers. To connect a row buffer at the extreme edge of the trench to the
vertical wire requires a horizontal wire of 500~microns. This horizontal
load almost doubles the signal capacitance, and therefore skew. Also, a
little bit of horizontal skew is introduced, as the row buffer output wires
end up differing in length, depending on the buffer position.
\footnote{Notice that the routing channel alone is 500~microns. This means that row
buffers had better drive only one row of signals. Otherwise, distribution
of signals to other rows will require another such routing channel on each
half of the array, boosting the trench width to 1500~microns!}
\footnote{Need A Diagram!}

\subsection{Timing \seclabel{timing}}

\mypsfigx{\textwidth}{write_path2.ps}{writepath}{Memory read and write path
  (one of the banks)}{Memory read and write path (one of the banks). No
  reference in text --Carlin.}

The processor timing is driven by the basic design choice of double-cycling
the register file to perform a read and a write operation in one cycle.
The cycle starts with the instruction clock, which clocks out the decoded
instruction bits.  At the same time, the word lines are gated off to avoid
overwriting memory cell contents in the upcoming precharge interval.
After the word lines are safely off, , the bitline precharge signal is
asserted. This signal enables precharge transistors onto the A and B
busses, charging them, and the bitlines that are about to be read. The
column selects must therefore be stable at their read phase values during
this phase. A circuit diagram of the memory system is shown in
\fig{writepath}.


After the bitline is unasserted, the read phase executes. The word lines
are enabled, allowing the selected SRAM cells to pull down their respective
bitlines, and through the column selects, to pull down the A and B lines.
When the read cycle is over, the contents of the A and B busses are latched
on a simple NMOS dynamic latch. The ALU evaluate cycle begins next (the ALU
evaluate is the read signal delayed by one inverter). All inputs to the ALU
were guaranteed high for long enough during its precharge phase (since the
A and B busses were precharged).  The ALU outputs are stable until the next
read cycle. During the ALU evaluate the bitlines are equilibrated and
precharged. As in the read precharge phase, the word lines must be gated
off. During this off interval, they may safely transition to the write
addreses.


When the ALU cycle completes, the write cycle begins.  The write is a
double-sided write and occurs through the write enables, the column
selects, and the SRAM pass transistor, so it is fairly slow. In fact, once
the coupled inverters are flipped to their future state, the write
completes slightly into the next cycle. This delay is safe because the
written state is not examined until after the precharge phase of the next
cycle.


The write signal also controls the network precharge/evaluate timing. As
soon as the write is over, the network evaluates. The dynamic decoder
evaluates and selects one of the four switches. Simultaneously, the X node
is pulled down (or not, based on the NetData register). Thus, for neighbor
to neighbor communication, the just written bit has the combined time of
the bit precharge period and the read period to propagate to the neighbor
and pull down the bitline.




%The first signal is the instruction clock, which clocks out the decoded
%instruction bits.  Next comes BitPre, the bitline precharge, which stayes
%flat for about 750~psec.  Safely surrounding the precharge is the ClearRow
%signal, which turns off all word lines. After the precharge is done, the
%read signal is asserted and lasts for 1.5~nsec. The alu uses the read clock
%as the precharge/evaluate clock. As soon as read is unasserted, the ALU
%evalutes. Simultaneously, BitPre is asserted again, equilibrating the bit
%and bit lines.  Then the write occurs. The write starts as the precharge is
%finishing, but the write drivers do not activate until the precharge is
%almost off.  The wite actually continues slightly into the next cycle. The
%write signal also serves as the network precharge/evaluate signal.


%%% As long as everything completes by a global clock, the skew doesn't
%%% matter. Unfortunately, the RC increase removes that time from the cycle.


\mypsfigy{4in}{timing_wave.ps}{petiming}{Abacus PE Timing}{PE Timing.}

%% What is the critical path?




\section{External Interfaces}

\subsection{System Synchronization}
Careful synchronization is essential to a high-speed SIMD architecture.  On
the Abacus PE board the system clock is distributed in differential ECL to
each PE chip. Propagation delays are matched by snaking traces so that
trace lengths are equalized.  To compensate for skew introduced by process
variations in the on-chip clock distribution, each chip phase locks its
internal clock to the received clock.  Phase locking is performed by a
delay locked loop (DLL) based on a mostly--digital delay line with a
fine-tuning analog section. The DLL uses the simple and accurate arbiter
circuit shown in \fig{arbit}. The arbiter has a  symmetric 30~ps
uncertainty window at nominal process.

\mypsfigy{2in}{arbit.ps}{arbit}{DLL Arbiter}{Arbiter used in the
  delay-locked loop}


The next design issue is the choice of which of the several signals should
be synchronized across chips.  There are several internal clocks:
instruction register, PE register read, network precharge, etc. Abacus
synchronizes to the clock that drives the \mesh\ output pads. As a result,
off- chip communication is synchronized system-wide.
%%% \footnote{ What is the
%%%   locking range?  Describe the fine analog delay at the end of the digital
%%%   chain. Provice a block diagram of DLL and theory of operation.}

\subsection{Instruction Distribution}
A spatially distributed SIMD system must ensure not only that all clocks
are synchronized, but also that all chips are executing the same
instruction at the same time. Several effects complicate this requirement.

First, signal propagation time across a large circuit board is significant
at high frequencies.  Propagation time is approximately 2 nanoseconds per
foot. Thus for a 60 cm board, chips near the distribution point receive
their signals four nanoseconds before chips on the far edge.  Even wires
connecting to the same chip can deliver signals at slightly different times
due to routing differences. For example, wires routed on outside PCB layers
experience a different effective $\epsilon_r$ and therefore different propagation
velocities.  Finally, PCB thickness variations can cause impedance
variations that affect signal velocity.  Two common techniques to overcome
this problem are snaking traces to equalize propagation delay, or by using
specialized clock distribution parts with programmable delays such as the
ClockWorks family \cite{Synergy95}. Neither technique is feasible for a board with four
30-bit instruction busses running at 250~MHz.

Another source of instruction skew is the variability of discrete parts in
the distribution path.  For example, the clock to output delay on a
high-performance ECL shift register has an uncertainty of 0.4 ns.  A signal
traversing two parts can be skewed by a much as 0.8 ns.  The combined
effect of these skews is that some chips receive an instruction a cycle
later than others, even though all chips are supposed to be executing the
same instruction at once.  Worse yet, bits of an instruction can be mixed
with bits of the next instruction due to component variability.

Thus, the instruction distribution scheme must solve three problems.
First, it must sample safely within the 4~nanosecond data window. Second,
it must align all bits of an instruction to arrive at the same time.
Third, it must align instructions across all chips in the system.  The
Abacus-1 instruction pads incorporate retiming logic, shown in \fig{instpad}
that solves each of these problems in turn.  Retiming occurs as
part of the system startup process and proceeds in three stages.


\mypsfigx{\textwidth}{instpad.epsi}{instpad}{Instruction Pad}{Instruction Pad Block Diagram.}



The sampling alignment stage first finely adjusts the delay of each bit
until the sampling clock transitions safely after the data is stable.  The
variable delay is performed by an all-digital delay line consisting of
inverter chains and multiplexers. A binary value generated by a
free-running counter selects the delay. The counter runs until the sampling
clock transitions after a delayed version $D'$ of that data. That
event disables the counter, freezing the delay. Ideally $D'$ is one quarter
of the cycle time, so that the sampling occurs in the middle of the data
valid period, but the quarter-delay line is limited to approximately 30
inverter delays.  Notice that the instruction generator must ensure that
the data transitions on every cycle during this phase.

Once this phase is complete, the bit alignment stage lines up all
instruction bits. This technique proceeds by passing the received data bits
through a shift register.  The shift register outputs are ORred together to
generate a \verb|got_one| bit.  As soon as all instruction pads assert this
bit, the shift register is disabled.  The position of the leading one
selects the delay to be applied to the data of that particular pad by
selecting the tap location from another tapped delay line.

Finally, the instruction sequencer performs the system-wide alignment phase
by broadcasting instructions and using the global OR feedback to determine
the delay to each chip.  Once this delay is known, the sequencer uses the
boundary-scan interface to set a register in each chip that determines
another delay to be applied to all pads in the chip.  To eliminate the need
for yet another delay line, the control register value is added (in unary)
to the delay computed in the previous phase, and the sum is actually used
to select the tap location.

The development history of this design is somewhat interesting. When it
became apparent that instruction distribution time was comparable than
cycle time, a proposed design used the PE chips as pipeline registers,
receiving and sending instructions point to point.  To synchronize
instruction execution, successive chips in a column would have to execute
out of different stages in an internal instruction buffer.  A natural next
step is unpipeline the process, and have the chips load the internal delay
buffer direction from the bus. Once the idea of cycle-level delay is
accepted, it leads to using nanosecond-level delays at the pin level.


\subsection{Inter-Chip Mesh Communication}
The next system level challenge is to provide synchronous high-bandwidth,
low-latency \mesh\ communication between PE chips.   Due to pin limitations,
the edges of the 32 by 32 PE array  on each chip are time multiplexed onto
16-bit ports.  The required clock rate is therefore 250 MHz, which presents
a number of design problems. 

Chips are separated by significantly varying transmission times. For
example, chips on board edges communicate over wires as long as 2 feet,
while neighboring on-board chips are separated by less than two inches.
Also,  different signal paths have different propagation speeds. For
example, the ribbon cables used between board have a characteristic
impedance of 90 ohms, compared to 50 ohms for PCB traces, and are therefore
almost twice as slow.

Process skews between chips introduce more differences. Although the chips
are synchronized at the start of a cycle, subsequent edges diverge in time.
Therefore, the faster chips can sample the second transmitted bit too early,
getting a copy of the first bit.



Unlike the instruction pads, the \mesh\  port design assumes that all wires
in a port are bundled and experience similar delays.
Each of the four \mesh\ ports sends out an escort clock along with the data.
Since the off-chip drivers and propagation time are identical for data and
clock, the receiving chip can safely use the escort clock (delayed by the
setup time of the receiving registers) to sample the data.  Metastability
problems do not arise as we ensure that data is sampled well before the
receiving data needs to use it.

The communication pads are driven with custom 1V, on-chip series terminated
drivers and matching receivers in order to minimize power dissipation and
transmission line reflections \cite{DeHon93}.  Impedance calibration for
the series termination is performed at system initialization.  Each of the
four ports on a chip is calibrated independently, since on-board and
board-to-board impedances may differ.

In addition to the pipelined, high bandwidth mode of operation, the \mesh\ 
pads can operate in a flow-through mode that bypasses the on-chip pulldown
network with a single wire, allowing fast multi-chip broadcast algorithms.
Propagation through a chip is reduced from three clock cycles to half a
cycle. However, the time multiplexing is disabled, reducing the effective
bandwidth. This was added to investigate the practicality of algorithms
designed under the architectural model of meshes with reconfigurable
busses.

Crossing a chip boundary costs an extra cycle for move operations. That
occurs because on-chip nearest neighbor is on the edge of making it to the
adjacent processor, never mind across a board. (Note that with aggressive
cycle times, worst-case travel in a real system is at least a cycle time).

The edge interface does not present a uniform \mesh\ model to the programmer.
\footnote{And...? --Carlin}

\subsection{External Memory Interface}

Any SIMD architecture that does not support relatively efficient access to
off-chip memory is simply unable to process to data sets that do not fit in
the small on-chip memory. This type of hard limit does not fit the common
expectation that a computer should be able to process larger than optimal
data sets, albeit at a performance degradation. Any such architecture is
limited to algorithms with little memory requirements such as systolic
processing.

Each Abacus PE chip is backed by two 1M x 32 specialized DRAM modules.  The
data interface is 64~bits wide and operates at 16~ns, which matches the
32-bit, 8~ns PE array.  The 16~ns cycle time is made possible by the
Ramtron extended DRAM part, which contains an SRAM cache integrated in the
DRAM. When an address not in the cache is referenced, a relatively slow
(35~ns) DRAM read cycle is initiated, and in each memory chip, 512 bits are
loaded into the SRAM cache.  The long DRAM read latency is encountered only
once, after which all reads operate at SRAM speeds. This mode of operation
is ideal for the block transfer requirements of Abacus, in which 1024 PEs
request a bit stored in the same address.

Control signals for the memory chips are synchronized to the PE chips by
sending them as part of the instruction stream.  Fine control over DRAM
timing is made possible by the small instruction cycle time, which is
comparable to that of a dedicated DRAM controller.  A useful side-effect of
this approach is the elimination of memory glue logic, and the ability to
use different memory components by changing only the control software.  A
counter in each PE chip generates the external memory addresses.  This
counter can be loaded from the top row of the PE array, allowing indirect
addressing.



%%% Considered other technologies such as Rambus and Synchronous DRAM.

%%% More banks can be added with extra S0, S1 enable signals.

%%% It would be nicer to use very wide, shallow chips instead of the
%%% current narrow deep ones.



\subsection{Image I/O  Interface}

%%% The next external interface requires getting image data (or any other data
%%% set) into the array. Fortunately, computer speeds have increased far faster
%%% than the bandwidth demands of images. 

% Data IO has always been a weak spot of academic designs. We were pleasantly
% surprised when IO of images became extraordinarily simple.

While early SIMD designs were concerned with limited image I/O bandwidth,
it is not an issue today's high-speed designs.  Since I/O is distributed
among 256 chips, a single pin on each component results in a very wide bus.


The Abacus PE chip has a one-bit single-ended ECL input and a one-bit
differential ECL output for external data I/O.  The aggregate bandwidth of
a 32-byte, 125 MHz bus is 4 GB/sec, which is almost three orders of
magnitude than the 7.7 MB/sec required by 512 by 512 images at 30 Hz.  The
I/O bottleneck, if anywhere, is clearly going to occur upstream of the PE
array.  This very high I/O bandwidth makes the architecture well-suited to
applications requiring real-time processing of large amounts of data such
as video and synthetic aperture radar.

The I/O bandwidth can be scaled down to reduce the interface logic and
wiring cost. For example, if only the 16 chips comprising the top row of
the 256-chip array were connected, the 4 GB/sec bandwidth would be reduced
to 250 MB/sec, which is more than an order of magnitude higher than frame
rate.

A single PE instruction initiates a burst transfer of 32 bits from the edge
of the PE array to the output pin (or from input pin to the PE array).
This background transfer frees the array to perform computation, or in the
case of the lower cost interface, to use the \mesh\ connections to shift
data towards the connected chips.

% A single chip has 1.5 MB/sec bandwidth. Of course, it must store this data
% somewhere, which it can do, if it does no further processing. Transfer path
% to memory is 40 cycles for a 1Kbit write, which is 3.2 bytes/cycle,
% which is  4GB/sec. So the memory bandwidth can easily keep up with IO
% bandwidth.  

%%% We could have used the DRAM path for I?O but this would have kept the need
%%% for format conversion and would have made the cycle times long due to the
%%% long risetime of 2-feet long traces. Alternatively, bus isolators would
%%% have to be used. Chips would have to be sequenced to only enable one at a
%%% time onto a row bus. This would have to be done in software or with external
%%% logic. More board area, less integration.  Ideally we would like a custom
%%% IC to handle the high-speed serial line.



\section{Chip Floorplan and Control Logic}
The chip is organized into three major parts: the PE array, split into two
halves; the control signal drivers in the middle; and control logic at the
left, as shown in \fig{chip}. The control logic includes address decoders,
instruction decode, external memory control, and a scan path controller.
The PE core is organized as 16 strips of 64 PEs each.  Each strip also
contains two sets of 76 buffers that drive control signals outward from the
center.  Skew is reduced by distributing signals vertically in a
lightly-loaded metal-3 bus, buffering horizontally with identical drivers,
and equalizing the load on each horizontal control wire.

The Abacus PE chip contains several mechanisms required for high-speed
system-level operation: skew-tolerant instruction distribution pads,
high-bandwidth local DRAM interface, low voltage swing impedance-matched
\mesh\ pads, and low pin-count I/O interface.

\mypsfig{chip_photo_bw.ps}{chip}{Chip Photograph}{Chip photograph.}


\begin{Table}{chiparea}{Chip Area by Subsystem}{Chip Area by Subsystem}
    \begin{tabular}{|l|r|r|}
      \hline
      \hdr{System} & \hdr{Area} & \hdr{Fraction} \\
      & \hdr{\mm} & \hdr{\%} \\
      \hline
      Pad Ring       & 24.23 & 25.4\\
      Control Logic  &  9.43 &  9.9\\
      PEs            & 38.30 & 40.1\\
      Row buffers    &  7.95 &  8.3\\
      Busses         & 13.09 & 13.7\\
      Edge Interfaces & 2.57 &  2.7\\
      \hline
      \textbf{Total} & \textbf{ 95.57} & \\
      \hline
    \end{tabular}
  \end{Table}
  
The PE array formed approximately 40\% of the chip area and 56\% of the
chip core area.

\subsection{Timing Generator}
The timing generator is a straightforward design, based on tapping a delay
line composed of inverters.  Clocks are generated by ANDing a tapped signal
and a delayed version.  This method provides an accurate method of
generating pulses quantized in terms of inverter delays, and therefore
tracking process variation. Another useful property of this timing method
is that all clocks are generated from the leading edge of the delay line
input, so the chip can operate at a variable clock rate.

The timing generator includes a debugging feature that doubles the delay of
each inverter stage by opening a pass gate to a capacitor. This technique
stretches out the clock waveforms uniformly, affecting both pulse widths
and pulse start times.  The feature was intended to allow testing of the
chip in case the original pulse widths were too narrow.  The original
design was based on an analog-controlled delay line \cite{johnson-pll},
in which the voltage controlled the gate voltage on the switch. This
flexibility was unnecessary and routing an analog line to each chip in a
system was judged to be impractical.

\mypsfigy{2in}{time_unit.ps}{time_unit}{Time Ring Unit}{Time Unit.}

\subsection{Pad Ring Summary}

\begin{Table}{padring}{Pin Requirements}{Pin Requirements}
  \begin{tabular}{|l|r|l|l|r|}
      \hline
\hdr{Pins} & \hdr{Number} & \hdr{Direction} & \hdr{Voltage} & \hdr{Freq} \\ 
\hline
% Grid related
Grid clock in    &   4 &  I & 1V & 250   \\
Grid clock out   &   4 &  O & 1V & 250  \\
Grid data        &  64 & IO & 1V & 250  \\
\hline
ECL Vref         &   1 & I  & ECL   & DC  \\
Clock            &   2 & I  & ECL & 125   \\
Data In          &   1 & I  & ECL & 125   \\
Data Out         &   2 & O  & ECL & 125   \\
Global OR        &   2 & O  & ECL  & 125 \\
\hline
Instruction      &  30 & I  & ECL & 250  \\
\hline
DRAM address     &  11 & O  & CMOS & 62.5 \\
DRAM control     &  10 & O  & CMOS & 62.5 \\
DRAM data        &  64 & IO & CMOS & 62.5 \\
\hline
TAP in           &   4 & I & CMOS & 125  \\
TAP out          &   1 & O & CMOS & 125  \\
Debug            &   4 & O & CMOS & 125   \\
 \hline
Total signal     & 204 & \multicolumn{3}{c|}{} \\
Power (5V)       & 74  &  \multicolumn{3}{c|}{} \\
Power (1V)       & 32  & \multicolumn{3}{c|}{} \\
Ground           & 114 &\multicolumn{3}{c|}{} \\
  \hline
Total           & 424 & \multicolumn{3}{c|}{} \\
\end{tabular}
\end{Table}



%% \subsection{Configuration and Control Registers}

%%% \subsection{Power Distribution}
%%% \begin{itemize}
  
%%% \item Electromigration calculation.
  
%%% \item Peak current requirement estimation.

%%% \item Bypass capacitance calculation.
%%% \end{itemize}


\subsection{Instruction Decode}

Instruction decode is very simple, primarily because the instruction word
is effectively horizontal microcode.  The decoder logic is equivalent to
approximately forty two-input gates. A sizeable fraction of those gates
detect when a special instruction is specified. Once that occurs, further
decoding of special instructions requires at most two more gate delays.
Ordinary instructions are not decoded at all; addresses are sent directly
to the address decoders and ALU op codes directly to the pipeline
registers.  Including the address decoders, the logic depth of the decode
stage is approximately eight gates.

%%% Decode is remarkably simple since it has an entire cycle to operate.

\subsection{TAP Control}

The Abacus chip incorporates a standard IEEE Test Access Port (TAP)
interface.  This interface is used not only for testing the chip, but is a
necessary part of system initialization and configuration. It is used to
initiate clock synchronization and instruction pad retiming, to program
impedance settings on the \mesh\ communication ports, and to inform each chip
about its location on the circuit board.

The test interface provides access to the decoded instruction pipeline
registers. These registers can be scanned out to evaluate instruction pad
functionality or scanned in to override the instruction decoder and allow
testing of the PE array in case of a design fault.

The current design has a fault in that the initial value of the pipeline
registers upon powering up is unknown. As a result, all decoded address
lines could be activated and cycling at the full clock rate. Thus, until a
correct bit pattern is scanned in, power consumption could be higher than
in normal operation.


%%% The boundary scan mechanism consists of:
%%% \begin{enumerate}
%%% \item A finite state machine controlling the TAP interface.

%%% \item Instruction registers. These specify the current mode, and are
%%%   decoded to enable certain groups of scan registers. There are four modes:
%%%   {\tt Bypass}, {\tt Configure}, {\tt SampleInst}, {\tt SetInst}.  The
%%%   Configure mode may be broken down into separate configuration modes if
%%%   routing the serial connections becomes too difficult.

%%% \item Bypass register. Allows bypassing of the scan path of a particular
%%%   chip. The feature is not enormously useful for Abacus, but it's required
%%%   by the standard.

%%% \item Configuration register. One of the two on-chip application-specific
%%%   registers. It contains:
%%%   \begin{itemize}
%%%   \item Impedance control registers for the four grid directions (5 each).
%%%   \item Near/Far configuration bits for each grid direction.
%%%   \item Reset register for retiming circuitry in input pads.
%%%   \end{itemize}

%%% \item Pipeline Scan Register. Contains sample/set registers wrapped around
%%%   the 60-odd control bits.

%%% \end{enumerate}

%%% \paragraph{Scan Registers}
%%% The {\tt Mode} bit controls whether the pipeline register outputs come from
%%% the pipeline registers or from the scanned registers.  

%%% This bit could be set through two different mechanisms: a configuration
%%% bit, or as a separate instruction (testing state).  In the case of decoder
%%% failure, we want to be able to protect the PE array by setting the Mode to
%%% select only the scan registers, even during bypass or configuration instructions. 

%%% {\em There is a problem, however. After power-up, the scan registers will
%%%   come up in an unknown state. Likewise the configuration register that
%%% holds the Mode bit...\/}



%% \subsection{Package}
\input{howfast.tex}

\input{testing.tex}
              
              
%% \clearpage              



%%% Local Variables: 
%%% TeX-master: "main"
%%% comment-start: "%%% "  
%%% TeX-master: "main"
%%% TeX-master: "main"
%%% End: ***
