%* Last edited: Sep  5 02:44 1996 (misha)

\chapter{Rough  Work}


\subsection{Foo}

\begin{quote}
  \em The reconfigurability of RBP allows it to function at the optimal
  performance points by providing a smooth tradeoff between the amount of
  local memory dedicated to a pixel.

  The assumption here is that there is more data than processors. This is
  certainly true in practical situations, where users want to process
  images larger than the physical array they can afford. It is especially
  true for situations in which the PE array is used as a coprocessor
  instead of a dedicated computer.

  A true computer must be able to process large data sets, albeit with a
  massive slowdown, and designs that ignore the requirement of processing
  multiple pixels with a single PE do so at a loss of general
  acceptability.

\end{quote}

\begin{itemize}

\item The MGAP people cheat horribly, quoting multiplication times by a
  constant for their multiply performance.  For example, they reduce the
  expected number of cycles to 14 from a worst case of 32.  


\item Finally, RBP allows low-latency operation in the case of small data
  sets.

\item Dr. Ken Batcher, the designer of the MPP, has said the most difficult
  part of that design was the data routing structure.


\end{itemize}

\subsection{Packaging}


Commercial PEMs generally weigh about half as much as ceramic packages. For
example, a fourteen-lead plastic dual in-line package (DIP) weighs about
one gram, versus two grams for a fourteen-lead ceramic DIP. Although there
is little difference in size between plastic and ceramic DIPs, smaller
configurations, such as small-outline packages (SOPs), and thinner
configurations, such as thin small-outline packages (TSOPs), are available
only in plastic. The use of SOPs and TSOPs also enables better-performing
circuit boards due to higher packing density and consequent reduced
component propagation delays. Figure 1.5 shows size-versus-lead comparisons
of various microcircuit packaging options. A smaller form factor naturally
implies higher board density and more functionality packed into the same
precious board real estate. Similarly, a lighter package results in a
smaller overall payload for the same board functionality, a concern of
critical importance for avionics equipment.  Consumer and commercial
electronics will also benefit from these advantages of plastics over
ceramics.

304-pin PQFPs are available.

Perimeter-Distrributed IO Pads vs Area-Distributed IO Pads.

\begin{table}
\begin{verbatim}
Table 1-2 summarizes key characteristics of each of these BGA packages.2

___________________________________________________________________

                        PGA             CBGA            QFP
-------------------------------------------------------------------
Size                    43.5 x 43.5 mm  21 x 21mm       26 x 26 mm
I/Os                    196             324             256
Type I/O                Pins            Pads            Leads
Pitch                   0.394mm         1.0mm           0.4mm
Signal-Signal Cap       1.43pF          0.40pF          --
Signal-GND Cap          6.76pF          1.85pF          1.78pF
Signal Inductance       8.57nH          3.26nH          20.31nH
Ground Inductance       ---             0.76nH          ---
____________________________________________________________________

        Table 1-2. BGA Package Performance Comparisons   
                        Source: IBM
\end{verbatim}
\end{table}

The VSPA semiconductor package employs a revolutionary design in which
three peripheral rows of pins replace the current standard of one row. VSPA
is being positioned as the "next generation" quad flatpack (QFP) style
packaging.  It offers 2-4 times better electrical and thermal performance,
yet is available at the same cost as a comparable QFP.

\begin{itemize}

\item Ball grid arrays will become more popular.  The notion of a cheap
  package will expand.  More pins will become available, reducing
  bandwidth-caused latency. But by then, the number of PEs on a chip will
  grow to match the increased pins.

  The ball grid array is still an expensive package. At leadcounts in the
  225 to 313 range it is approximately twice as expensive as the equivalent
  quad flat pack (plastic BGAs are currently selling for 1.9 to 2.2 per pin
  - PQFPs are typically 0.9 per pin).

  Simply put, a leading edge technology printed circuit board or a cofired
  header is more expensive than a stamped leadframe until the leadcount and
  electrical performance takes the package into a domain where the PQFP
  cannot easily follow.

  Today, BGAs are a more expensive package than the alternative. Tomorrow,
  there is really no alternative, and relative price differences between
  BGAs and alternatives will continue to decline. As we have seen so often
  in the past, "You can never beat an old technology on price but an old
  technology can never grow to create new headroom."

  {\tt http://www.ieec.binghamton.edu/prismark/tm9601.htm}



\item 
ECL is especially bad for standby mode alpplications, if power is critical.
Of course, one possibility is to drive all zeros on the output when in
standby, to eliminate ECL power consumption.


\end{itemize}

However, a cost comparison must include the entire system. Number of I/O's,
size and area comparison, thermal and electrical comparison, assembly yield
and rework costs must all be considered. One must also consider that BGA
processing requires only conventional SMT assembly equipment; highly
accurate placement capability is not required. Plastic BGAs (PBGAs) are
approaching cost parity with QFPs, while ceramic BGAs remain higher priced
than QFPs. As general BGA usage increases, we will see price reductions to
very competitive levels versus QFPs.

\paragraph{Price/IO}

\begin{table}
\begin{tabular}{|l|r|r|}
\hline
Package & Cost/IO &  Package Cost \\
        & (cents)  &  300 pins\\
\hline
PGA & 4-16 & 12-48 \\
QFP & 1-5 & 3-15 \\
BGA & 2-8 & 6-24 \\
\hline
\end{tabular}
\end{table}

For comparison, MOSIS quotes an identical price of \$12 per package for up
to 208-pin PQFP, \$15 thereafter.

Area is \$370 per micron.

\subsection{Modern Previous Work}


A 7.68GIPS 3.84GB/s 1W Parallel Image-Processing RAM Integrating
a 16Mb DRAM and 128 Processors, Yoshiharu Aimoto, etal. NEC 

A parallel image processing RAM integrates a 16Mb DRAM and 128 processor
elements(PEs) on a single chip in 64Mb DRAM process technology.

\begin{verbatim}
 Technology                       0.38mu p-sub triple-well 2-metal layers
 Cell size                       1.69x0.85um2/sup
 Die size                       18.8x16.7mm2/sup
 DRAM size                       10mmx10mm, 16Mb
 DRAM organization                       128DEs, 8MUs/DE, 16kb/MU
 Number of PEs                       128
 GP registers                       24x8b/PE (3-port SRAM)
 DAta input/output                       PE-DE: 8b serial I/O:8bx2
 clock                       30MHz
 cycle time                       33ns, 66ns(segment miss)
 memory bandwidth                       3.84Gb/s
 Performace                       7.68GI/s
 Power dissipation                       992mW
 Supply Voltage                       DE: 2.5V; PE: 2V
\end{verbatim}




The Mpact chip delivers the feature set of a collection of add-in cards or
chips that would cost hundreds of dollars. But according to Purcell, a
complete subsystem that includes Mpact, a 16-Mbit RDRAM, and support chips
will cost just \$150 and can be placed on the motherboard. 

Not surprisingly, Rambus cofounder Farmwald, now Chromatic's chief
technologist, chose a Rambus memory interface to get the biggest bang for
the area and (eventually, if you believe Rambus) buck. A single 16-Mbit
RDRAM provides 2M of memory, the standard system size. The Rambus transfers
one byte every 2 ns, or one 72-bit word every 16 ns, giving rise to Mpact's
62.5-MHz core clock rate. Two RDRAMs are needed for MPEG-1 encoding or
MPEG-2 decoding.

Chromatic calls Mpact a VLIW (very long instruction word) and SIMD (single
instruction, multiple data) vector processor. While it is all of these
things, it is not a general-purpose CPU but rather a sophisticated,
special-purpose multimedia controller. The internal architecture, shown in
Figure 1, is more akin to a DSP than a microprocessor. It includes an SRAM
(which Chromatic calls a cache) that houses both instructions and data, an
instruction unit, five function units called ALU groups, the Rambus
controller, and the I/O port controllers.

There is no virtual memory-management hardware, since all programs run in
real memory out of the RDRAM.  Even the SRAM is controlled completely by
software, with little hardware support. Programs set up data and
instruction areas of the SRAM and can overlay themselves, taking care not
to oversubscribe the SRAM, for there is no hardware protection.

The 4K SRAM is organized into 512 words of 72 bits each. Software
partitions this memory into instruction and data areas, with the
instruction area configurable to 256, 512, or 1K bytes. The instruction
side is a direct-mapped cache with a whopping 128-byte line size. The data
side is self-managed, looking more like scratch-pad memory with no real
line size. Data is moved in 72-bit words; all "bytes" are 9 bits long for
extra precision and to take advantage of the extra bit in the RDRAM for
data instead of parity.

Prefetching is done only by explicit instruction direction, and it is done
in address order. Chromatic's programs are written carefully to avoid any
prefetching delays. The SRAM has four general-purpose read ports and four
write ports, all of which can be accessed simultaneously in a single cycle.
One write port is typically dedicated to the RDRAM interface and one to a
DMA channel; the other two are general-purpose.

Mpact has a straightforward instruction model with a few advanced features.
The very long instruction word is an eight-byte instruction pair. The
instructions may be three, four, or five bytes in length, with pairing done
by hand or using Chromatic's compiler. Resource conflicts may cause the
instructions to be executed sequentially, but even so, packing two
instructions together helps with code density.

An instruction typically consists of one byte of opcode, two source bytes,
and one destination byte. These 9-bit source and destination addresses can
access any 72-bit word in the on-chip SRAM. Other instruction forms include
a three-byte format for two-operand instructions and a five-byte format
that allows four-operand calculations such as multiply-add.

An instruction count register creates a repeated vector that can improve
code density and speed inner loops. The vector operations are coded only in
eight-byte instruction pairs and have a maximum iteration count of 127.
Vector loads transfer data from the RDRAM to the SRAM at 500 Mbytes/s. A
vector operation can move as many as 256 bytes.

Branches are simple two-byte immediates, allowing a maximum code size of 1M
in the Mpact RDRAM. Two forms of each conditional-branch
instruction--branch likely and branch unlikely--allow static prediction set
by the programmer or compiler. Conditionals are only on the sign of a
result; there are no other condition codes.

Figure 2 shows the five function units that Purcell calls ALU groups. Each
group consists of essentially an eight-byte (72-bit) arithmetic unit that
can operate on one, two, four, or eight bytes at a time. Thus, they can be
configured to do eight 9-bit ALU operations in one cycle, giving very good
performance at the lower precision required by many multimedia algorithms.
The 9-bit bytes lend themselves nicely to 16-bit audio applications,
providing two bits of extra precision for intermediate results. This
structure avoids the need to go to 24 bit data, which would use more space
and time.

Generally, only one ALU group is active per instruction (two for an
instruction pair). Multiplies and special "inner loop" instructions can
activate more than one group. To achieve the rated 2.0 BOPS, all four
standard ALU groups must be processing eight bytes per cycle at the
62.5-MHz clock speed.

Each group has a specialization. Group 1 is a shift/align unit, while Group
2 is a standard ALU. Multiplication uses Groups 3 and 4: Group 4 produces
partial products using Wallace trees, then Group 3 completes the
multiplication and adds a third operand. The multipliers can be configured
to produce eight 9 x 9 ® 18-bit multiplies, four 18 x 18 ® 36-bit
multiplies, or two 24 x 24 ® 36-bit multiplies. Alternatively, Group 3 can
be used as a dual three-input adder.

Finally, Group 5 is a specialized motion-estimation unit with some 400
ALUs, most consisting of a few bits.  Purcell would not disclose additional
details on Group 5 but indicated that it can achieve 20 BOPS, ten times the
performance of the other function units combined.

All these units are connected by a crossbar bus that can place any result
into any input for the next cycle. This requires a massive 792-bit
unidirectional bus with a single source (11 results of 72 bits each) and 19
taps.

The pipeline has just four stages: fetch, decode, execute, and writeback.
The leisurely clock rate allows SRAM data to be read and used in the same
cycle (no load-use penalty). Splitting multiplication between two ALU
groups allows it to be fully pipelined with one-cycle throughput and
two-cycle latency. Correctly predicted branches have no penalties, whereas
an incorrect prediction costs two cycles. The loop instructions repeat the
execute and writeback stages up to 127 times before moving on.

Chromatic and its semiconductor partners designed the custom chip using an
increasingly common cell-based approach. Data paths, along with the SRAM
and the Rambus interface (designed by Rambus), were custom designed, while
the rest of the chip is standard cell, as Figure 3 shows. A large part of
the data path swizzles the 72-bit result buses to their respective
destinations, leaving a quite small set of highly customized circuits.  The
Rambus interface produces the core 62.5-MHz clock, and the other interfaces
accept their own asynchronous clocks (33 MHz for the PCI bus, 135 MHz for
the display, etc). FIFOs are used for frequency matching.

                            
Chromatic designed and laid out the circuits for each manufacturer
separately, tuning the layout to the design rules of each. This technique
is far superior to the least-common-denominator design-rule method used for
the R4000, for example. Chromatic's method allows straightforward
compaction and die shrinks, as justified by volume. These shrinks may
require multiple rows of bond pads or possibly area bonding, as the first
layout is nearly pad limited.
                            
The 100-mm2 processor is implemented in 0.5-micron three-layer-metal CMOS
and consumes 1.5 million transistors. This first design is expected to be
in production in 2Q96. The design is currently going through a shrink to
Toshiba's 0.35-micron three-layer-metal process to yield a chip less than
65 mm2 with appropriate I/O-pad technology. That tapeout is supposed to
occur before year-end, and Chromatic expects full production of the shrink
version to begin in early 3Q96, though this sounds aggressive. The MDR Cost
Model places the manufacturing cost of the 0.5-micron version at \$30,
shrinking to \$25 for the smaller part.

The 62.5-MHz Mpact operates at 3.3 V but tolerates 5-V inputs. Chromatic
has not released power numbers.  The package is a 240-pin heat-slugged
PQFP.

\begin{itemize}


\item A diversion here. Although commercial cost issues are frowned upon in
academic designs, cost is a reasonable measure of resource cost, and in an
engineering design, there must be a resource consumption criterion.
Otherwise many designs would be overly simplistic.

\item Relevant Patent: Patent 5,467,455 (Motorola).  A data-processing
  system and a method for performing dynamic bus-signal termination uses a
  dynamic bus-termination circuitry with a device. The circuitry is enabled
  when data is incoming to the device and is disabled when data is outgoing
  from the device to selectively reduce unwanted signal reflection at the
  signal end of a bidirectional bus. The disabling allows the circuitry to
  be removed or tristated from any connection with the bus when not needed
  (i.e., data outgoing) to reduce loading. The disabling of the termination
  circuitry also aids in reducing the power consumption of the part when
  either the bus is sitting idle or the part is in a low-power mode of
  operation.

\item Cost notes. Moto 16K x 16 SRAM chips cost  approximately \$30.

\item {\em Rambus}. Another possibility is to use Rambus interfaces. A
  single 8-bit Rambus port delivers 500 MB/sec, or 5 bytes/cycle. Four such
  ports will lower memory access time to 10 for the initial access and then
  10 for the bandwidth-limited access. Not a substantial difference from
  the 8 ns SRAM, when latency is considered.


\item {\em Processor in Memory}.
A common avenue of speculation is Computing in RAM. It seems straighforward
to add a bit-serial processing element to each set of bitlines in a dense
DRAM. There are a number of problems with this approach. DRAM cycle time is
on the order of 50 nanoseconds. The topology is that of a line.  Unless
fast static registers are added, an operation requires two reads and a
write, leading to a cycle time of 150 ns. Further, off-chip communication
is terribly limited unless larger pad frames are used.  SRAM integration
seems more promising, as performance could increase to a 10-ns cycle time,
for a PE cycle time of 30 ns.  The other problems of interconnection and
off-chip communication are still present, of course.


\item GF11 used compiler controlled SRAM cache.

\item Data point: ITT processor. 150 \mm area in a 0.8 process, 2
  metal. 125 MHz, 8W, heavily pipelined (7 stages). 4 GOPS
  (multiply-accumulate).  Resembles PADDI, data driven. Pseudo
  MIMD. 16 registers, each of 12 bits. Total chip bit capacity is 16 x 16 x
  12 = 256 * 1.5 = 378 bytes.

\item Data point: Field-Programmable Operator Array (FPOA) \cite{Quenot94}.
  1 micron CMOS, 9mm by 9.6 mm, 25 MHz, 2 PEs, 10 IO ports. 16-bit ALU, 8x8
  multiplier, 256 by 9 RAM. 64 instruction memory.

\item   Abacus can function in either high throughput or low latency
  mode. In other words, resources can be allocated to getting a single
  result quickly, or many results with a low average computation time.

\item Radix-4 math on abacus. Appears to require 11 cycles (maybe reducable
  to 9. Requires 5 bits to redundantly store a 2 bit (almost a 3-bit
  number: -3..+3).  This compares to 2 bits to store a 1-bit number in
  radix-2. Why bother?
  \begin{enumerate}
    
  \item Sign extend (1) C0 = C1 = x2
  \item Binary addition (4): S0 = halfsum(y0, x0); t = halfcarry(y0,x0)
    \newline S1 = sum(t, y1, x1); t = carry (t,y1,x1); \newline S2 = sum(t,
    y2, x2); t = carry (t,y2,x2); \newline

\item Sign correct (1).  S1 := fix(s0,s1,s2);

\item Carry correct/shift (2). 

\item Add (3)
      \end{enumerate}

    \item Throwing bits on the floor. With a four-to-one column
      multiplexor, three fourths of the read bits are unused. The 8-bitline
      implementation wastes no energy in charging and discharging bitlines
      unnecessarily.
\end{itemize}


\subsection{Scan and Reduce Primitives}


{\em Need intro here about scans}.

Scans on a \mesh\ with bypass are logarithmic time under the  unit time
assumption. In practice, the assumption is false, and the network operates
as a sub-linear \mesh.


Assume a 4 by 4 square organization of PEs. Let's look at a reduction
operation, say summing the pixel values.  Even though this number can
overflow, for now we'll do the arithmetic in 16-bit integers. This reflects
the real life case of crossing chip boundaries.  \footnote{Describe model:
  ie, 2 cycles to cross chip plus one for chip boundary}.  \footnote{Note
  about changing orientation}.



\subsubsection{Unpipelined loop}

An unpipelined loop algorithm is:

\begin{verbatim}
for i = 0 to L {
   set_bypass_reg(i)
   configure_horizontal()
   net_out := x   
   for j = 1 to n {
      wait( WaitTime(i))
      net_out := net_in            // on the 4th iteration, do Y := in
   }
   do_arithmetic()
}
\end{verbatim}

On the $i$th cycle, $2^i$ pixels are bypassed (the first iteration, with no
bypassing, is not shown).  Waiting time as a function of number of PEs,
$p$, bypassed is $p/16$ if $p \leq 32$ and $1.5 p/16$ otherwise (chip
crossing penalty of 1 cycle). Since $p = 4 \times 2^i = 2^{i+2}$, this can
be expressed as $2^{i-2}$ if $i \leq 3$, and $1.5 \times 2^{i-2}$
otherwise.

Let $A$ be the time for the arithmetic operation and other overhead.
Say we want to send $n$ bits.
%Assume 4 cycles for the arithmetic operation, and another 5 for the other
%overhead.  
Then iteration $i$ requires:

\begin{equationarray*}{lll}
T_i  =  A + n & (1 +  2^{i-2})           & \mbox{if}\  i \leq 3 \\
              & (1 +  1.5 \times 2^{i-2}) & \mbox{otherwise} \\
\end{equationarray*}
                 
The total time $T = \sum_{i=0}^L T_i$ is
\begin{eqnarray}
T   & = & L(A+n) + n(1+1+1+2) + 1.5n \sum_{i=3}^L 2^{i-2} \\
    & = & L(A+n) + 5n + 1.5n  \sum_{j=1}^{L-2}  2^j \\
    & = & AL + n(L+3.5) + 1.5n  2^{L-1} \\
\end{eqnarray}

For $L=6$, $n=4$, $A=9$,  in this case, $T_i = 54 + 38 + 192 = 284$.


\subsubsection{Pipelined Loop}

As an aside, given an ideal (transmission line) wire and ideal flip flops
with no setup or hold times, how many FFs should be used to pipeline the
transmission of $n$ bits?  The answer is infinity, if clocking rates can be
arbitrarily high.

This requires more iterations but smaller waiting time between iterations.

\begin{verbatim}
for i = 0 to 6 {
   set_bypass_reg(i)
   configure_horizontal()
   net_out := x
   for j = 1 to NumIter(i) {
      wait(WaitTime(i))
      net_out := net_in            // on the 4th iteration, do Y := in
   }
   do_arithmetic()
}
\end{verbatim}

WaitTime(i) is easy: if messages have to cross chip boundaries, it is $n-1$,
otherwise it is $\lceil p/16 \rceil$, which is effectively 1. 
The tricky part now is determining NumIter($i$).  The number of iterations
is the number of bits plus the pipeline length minus 1. If we set up each
chip as a pipeline stage, {\tt NumIter(i)} is $N_{\mbox{chips}} + 3$.
The time equation decomposes nicely into two parts: within chip and intra
chip.

\begin{equation}
T_i  =  A + \left\{ 
\begin{array}{llll}
   n            & \times & (1+1)     & \mbox{if}\  i < 3 \\
   n-1+2^{i-3}  & \times & (1+3)     & \mbox{otherwise} \\
 \end{array}
 \right.
\end{equation}


Making the substitutions: 
\begin{equation}
T_i  =  A + \left\{ \begin{array}{ll}
                     2n               &   \mbox{if}\  i < 3 \\
                     4n-4+2^{i-1}     & \mbox{otherwise} \\
                    \end{array}
                  \right.
\end{equation}
                
  
\begin{equation}              
\begin{array}{lllll}
T  &  = & L(A+1) + 6n + (L-2)(4n-4) & +  \sum_{i=3}^L 2^{i-1} \\
   &    & L(A+4n-3) - 2n +8      &  +  \sum_{i=3}^L 2^{i-1} \\
   &    & L(A+4n-3) - 2n +8       & +   2^L - 4\\
   &    & L(A+4n-3) - 2n + 4     & +   2^L\\
  \end{array}
\end{equation}

For $L=6$, $A=9$, $n=4$, $T= 6(22) - 8 + 4 + 64 = 192$.
 or about 30\% faster.

Compare with    $T =  L(A+n)  + 3.5n - 4 + \frac{3n}{4} 2^L$.
The difference is $(\frac{3n}{4}-1)2^L + 5.5n - 4 + L(3n-3)$, or $2(64) +
22 - 6(9) - 4 = 92$.


\subsubsection{Conclusions}

Notice that we get only 30\% gain. Why? We would naively expect a factor of
3.



\subsection{Starting Computing During Background Loading}

\paragraph{Start Work Early?}

A minor modification is to allow computation to start on a nibble as soon
as it's read in, and not wait for the entire word.  Assuming that it takes
longer to load than to compute, the time for a combined load and operate is
just the load time plus the time to compute the final slice. As a result, the
arithmetic time drops by the number of external loads.

If we assume that the time to process a single slice is 1, then:

\begin{eqnarray*}
  T_{tot} & = & Qm \left[ (Z+2Nf) T_{load} + N(1-f)T_{alu} + Nf \right] \\
          & = & Qm \left[ \left( Z+2Nf \right) \frac{W}{mB} +   N(1-f)\frac{W}{mk}  + Nf \right] \\
%%          & = & QW\left[ \frac{Z+2Nf}{B} + \frac{N(1-f)}{k} + \frac{Nf}{W} \right] \\
          & = & QWN\left[ \frac{l+f}{B} + \frac{1-f}{k} + \frac{f}{W} \right] \\
          & = & \frac{QWN}{Bk}\left[ (l+f) + B \left( 1 - f +
          \frac{fk}{W} \right) \right] \\
\end{eqnarray*}

Recall that we defined $l=Z/N$.
This is faster than the non-overlapped case, but not by much. If we define
$X$ as $(l + 2f)$ and $Y$ as $k/W$ then:

\begin{eqnarray*}
  R & = & \frac{X+B}{X+B(1-f + fY)} \\
  & = & 1 + \frac{f(1-Y)}{\frac{X}{B} + (1-f(1-Y))} \\
\end{eqnarray*}
  
The increase is at most 20\%, even for very high values of $f$ and $B$, so
we'll ignore this effect. Let's assume $Y$ is 1/16, for 1 bit PEs and
16-bit data. Let's say 20 cycles are required to load the chip, so $V$ is
20. Since $X$ ranges between 0.2 and 1.2, the term $X/B$ dominates the
denominator, about 4 at the least. So $R$ is approximately $1 +
\frac{fB}{X}$, or 1.1 at most.  This is a minor effect, so we'll ignore it.



%\subsection{MIMD Flexibility Hurts Performance}

The MIMD model incurs enormous overhead for every functional unit that
actually manipulates data. This overhead consists of silicon area required
to store the program (a 10K word program of 32 bits each corresponds to 1.8
million transistors!), instruction decoding, addressing, and control
circuitry. The overhead can easily be a factor of ten larger than
the functional unit actually processing the data.

A more subtle disadvantage is the loss of integration due to pin
limitations.  Today's chip carriers can support very few 32-bit wide
instruction ports.  Reduced integration leads to pressure on improving the
performance on a single chip. Regardless of diminishing returns, valuable
silicon resources are allocated to squeezing the last available performance
from a single instruction stream.  Thus, only a small fraction of the
circuitry on a chip is devoted to actually manipulating the data. The rest
is allocated to branch prediction, instruction caching, instruction
scheduling and reordering, etc.  Other baggage inherited from the
workstation background of RISC chips is support for operating systems, such
as interrupts and fast context switches.


Many important applications are characterized by irregular data and
instruction flow, complex interactions between data sets, and highly
conditional execution.  For this wide variety of important computing tasks,
high performance uniprocessors and MIMD parallel machines have emerged as
the best architectural choices.  

 A general purpose MIMD machine capable of performing the
required massive data manipulations would be prohibitively costly.
Especially in constrained environments where power and size requirements
dictate efficient solutions, the uniprocessor/MIMD approaches are a poor
application of resources.



On a philosophical note, the microprocessor approach locks architecture and
programmers into a rigid way of thinking, as the cycle count does not
reflect the true silicon cost of operations. When logical shift and
multiplication take nearly the same amount of time, programmers (and
compilers) start to use multiplication more. Algorithms get slanted towards
using multiplications, and what's worse, profiling programs for instruction
frequency shows that multiplications are used frequently and should be
accelerated by allocating more area.


\subsection{Hybrid Reductions}

Reductions are not very efficient at the higher levels. It is probably
faster to compute a reduced value at each chip and send it up to the scalar
processor.

For example, each chip can count its own pixels in about 100 cycles
(without crossing any chip boundaries).  If each chip then sent up its
value through an FPGA and into the IO memory, the FPGA could compute the
sum and only 16 values would be stored into the scalar unit's memory.

Or, each neighborhood of four chips could perform another nearest-neighbor
reduction.


\subsection{Motivation Junk}
There are two questions that must be answered, with the second leading from
a successful answer to the first.  Imprimis, what is the point of this
work?  This one is easy: to demonstrate that a reconfigurable architecture
is better than a fixed architecture.  A number of sub-questions arise when
we try to pick apart this somewhat facile answer.  What does \emph{better}
mean?  Specifically, we interpret better to mean more efficient in terms of
performance per resource used.  Is this the only interpretation of
\emph{better?} Clearly not.  On occasion, we may not be interested in
resource cost at all. This occurs when the overall cost is so low, that the
ratio of performance to cost is irrelevant.  Other times, the resource cost
is important, but only as long as some performance goal is met. For
example, if some algorithm must be executed at frame rate, any hardware
resources resulting in faster execution is wasted.  But for now, we will
assume that the performance threshold is met, and we are optimizing for
price/performance.


Further, the work should allow designers to determine what configuration
parameters are best for the task at hand. What parameters of a VLSI-based
parallel machine can be varied?
\begin{itemize}
\item ALU width
\item ALU functionality
\item Register file size
\item Off-chip memory latency and bandwidth
\item Communication network
\item Controller/array communication latency
\end{itemize}

Why not make every processor 64 bits wide, with gargantuan register files,
and low latency memory? Because this costs resources:
\begin{itemize}
\item Silicon area
\item Pins
\item Off-chip DRAM
\item Off-chip network chips.
\end{itemize}

Total cost is hard to quantify, so we'll assume a base case (such as the
one-bit processor Abacus-1).

\textbf{What will you have when you're done?}  A way to determine the best
configuration for a particular compute task.

Level 1: Given a reconfigurable system, with particular slice
characteristics, determine $m$, the number of slices to be concatenated.

Level 2: What should that slice look like?

\textbf{How will you do it?}

\begin{itemize}

\item DCA implies virtualization. If processors are grouped 

\end{itemize}



% Local Variables: 
% TeX-master: "main"
% TeX-master: "main"
% End: 
