%* Last edited: May 29 17:23 1996 (misha) \MaplePlotWidth=\textwidth \MaplePlotHeight=60ex \section{Optimal Bit Width Analysis} Selection of the bit slice width in a SIMD computer is yet a solved problem. Early PEs were bit-serial due to VLSI area constraints. Some designs have upgraded to a conventional 32-bit datapath, while others moved to only 8 bits, even in a contemporary technology. This section develops a simple model that examines various slice widths in terms of silicon area efficiency. Development proceeds in four steps. First, we estimate the area, delay, and cycles-per-instruction (CPI) of a given bit width and simply multiply to obtain the figure of merit. This metric, called \emph{quality} in this work, is normally expressed in bit operations per nanosecond per unit area, but for easier intuition has been scaled to billions of 16-bit operations per second per standard chip. Second, we use Amdahl's law to account for operations which are not sped up by a wider datapath. Third, recognizing that off-chip memory latency is a critical bottleneck, we determine the effect of cache misses. Finally, we evaluate the performance gain of the background loading mechanism on the Abacus architecture. We begin by describing the assumptions and limitations of the model. \begin{Table}{modelparams}{Analytical Model Parameters}{Analytical Model Parameters} \begin{tabular}{|l|l|l} \hline Parameter & Value & Description \\ \hline $A_{ALU}$ & 8 & ALU area, in units of SRAM cells \\ \hline $f_A$ & 0.9 & Fraction of operations affected by wider datapath \\ \hline \end{tabular} \end{Table} \subsection{Model Assumptions and Limitations} \subsubsection{PE Area} A processing element's area is modelled as consisting of three parts: the memory cells, the ALU, and the other overhead circuitry, including the network and the data plane registers. The basic unit of area is the SRAM cell. \begin{equation} A_{PE} = m + kA_{ALU} + A_{ovr} \end{equation} where $k$ is the width of the datapath and $m$ is the number of memory bits. Thus, area growth is linear in the datapath. There will be slight area growth in overhead components, such as in the size of the buffers controlling the datapath, but that can be folded into the ALU area. An important immediate assumption is that $AT^2$ circuits such as multipliers and barrel shifters are not present. These elements have important applications and should be analyzed in later work, but their inclusion in a massively parallel system must be evaluated carefully, since their area grows quadratically with decreased cycle time, and parallelism provides a more efficient alternative. \subsubsection{Cycle Time} \subsubsection{Off-Chip Memory Accesses} The analysis of the effect of off-chip bandwidth implicitly assumes that commercially available memory technology will be at least one technology jump from that available to a university or even a low-volume commercial design. If this situation changes, this model will have to be reevaluated. \paragraph{Pin Bandwidth} \paragraph{Number of Pins} \paragraph{Power Issues} In the sense of raw performance, the design is optimal when the off-chip memory pathway is constantly busy with a minimal number of PE stalls. At that design point, the internal PE area has been pared down to provide as much on-chip processing power as possible. However, this mode of operation is probably not optimal under the power consumption metric, since large off-chip buffers are constantly active. This multivalued optimization problem is an interesting avenue of future research. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Amdahl's Law} \begin{Table}{holmanfractable}{Fraction of Operation Costs Affected by Data Path Width}{Fraction of Operation Costs Affected by Data Path Width. From \cite{Holman90}} \begin{tabular}{|l|r|} \hline Program & f \\ \hline Bitonic Sort & 0.75 \\ Matrix Product & 0.94 \\ LU Decomposition & 0.76 \\ Cholesky Decomposition & 0.25 \\ Jacobi Method & 0.91 \\ SOR Method & 0.91 \\ SIMPLE & 0.71 \\ \hline \end{tabular} \end{Table} Herbordt's evaluation of parallel architectures included a set of simulation results relating datapath width to execution time. Amdahl's function was fitted to the data points and generated good agreement with data (although half of the algorithms had unexpectedly high performance for the case $k=1$). The fitted data is tabulated in \tab{herbordtfractable}. The algorithms clearly fall into two classes: mostly bit oriented, with only $f_A=0.2$ and mostly word oriented, with $f_A=0.9$. The IU Benchmark entry is a composite of several algorithms. \begin{Table}{herbordtfractable}{Fraction of Operation Costs Affected by Data Path}{Fraction of Operation Costs Affected by Data Path. From \cite{Herbordt94}} \begin{tabular}{|l|r|} \hline Program & f \\ \hline Region-based Line Finder & 0.15 \\ Curve-Fitting Filter & 0.92 \\ Correspondence Problem & 0.21 \\ Fast Line Finder & 0.07 \\ IU Benchmark & 0.41 \\ Depth From Motion & 0.80 \\ \hline \end{tabular} \end{Table} An important source of non-accelerable operations is network operations. In a multi-chip system, every communication must cross a chip boundary, and the number of pins does not grow with data path width. Simple filter-style algorithms such as convolutions require one mesh move operation for each multiply and add. If the multiplication is by a known constant, an average eight-bit multiplication requires four shifts and five adds. Thus, approximately 90\% of the operations benefit from a wider datapath. The remainder of the chapter uses $f_A=0.9$. \subsection{IO} \subsection{Background Loading} \subsection{Background Loading} A memory access on the Abacus machine has a latency of 40 cycles, but can be initiated before the data is actually required. Only one outstanding memory reference can be pending. We would like to determine the benefit of this feature compared to the worst-case penalty of 40 cycles. The key parameters are the latency of a reference, and a distribution probability on consecutive non-memory references Our first order model assumes a uniform probability $p$ of an off-chip memory reference. Thus, the probability of a sequence of $k$ on-chip references before an off-chip reference is: \begin{equation} P(N=k) = (1-p)^{k-1}p \end{equation} \begin{figure}[ hbtp] \begin{center} \leavevmode \mapleplot{Pk_vs_k.ps} \end{center} \caption{Probability of an on-chip hit sequence of length $k$ for different values of $p$, the miss probability. Note that for high $p$ almost all the area under the curve is near small values of $k$, and therefore long load times. } \label{fig:seqprob} \end{figure} This distribution is shown in \fig{seqprob}. Notice that the probability of long sequences is small if $p$ is high. Therefore, we expect background loading to help only in the case of low $p$ or low latency. Since the loading time given a string of $k$ available cycles is $L-k$, the expected loading time is: \begin{equation} E[T] = \sum_{k=1}^L{q^{k-1}p(L-k)} = \frac {(\,1 - {p}\,)^{{L}} + {p}\,{L} - 1}{{p}}\\ \end{equation} \begin{figure}[ hbtp] \begin{center} \leavevmode %% \mapleplot{Leff_vs_f1.ps} \mapleplot{Leff_vs_f2.ps} \end{center} \caption[Effective latency vs latency due to background loading as a function of $L$ and $p$]{Effective latency vs latency due to background loading as a function of $L$ and $p$. The advantage of background loading occurs in a relatively narrow zone: where the frequency of loads is very low to begin with, and where latency is low. For low values of $L$, the ratio may not be really important, since it approaches internal access time.} \label{fig:leff} \end{figure} Still, even for relatively large of $L$ and $p$\footnote{40 and 0.1, respectively}, we can get a 3X speedup. %\begin{figure}[ hbtp] % \begin{center} % \leavevmode %\mapleplot{Leff_vs_m.ps} % \end{center} % \caption{Effective Latency as a function of $m$. This } % \label{fig:leff} %\end{figure} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{Figure}{idealq}{Foo}{Long Foo} \leavevmode \mapleplot{idealq.eps} \end{Figure} \begin{Figure}{idealqn}{Foo}{Long Foo} \leavevmode \mapleplot{idealqn.eps} \end{Figure} \begin{Figure}{amdqn}{Foo}{Long Foo} \leavevmode \mapleplot{amdqn.eps} \end{Figure} \begin{Figure}{amdqn3d}{Foo}{Long Foo} \leavevmode \mapleplot{amdqn3d.eps} \end{Figure} \begin{Figure}{amdqn3d2}{Foo}{Long Foo} \leavevmode \mapleplot{amdqn3d2.eps} \end{Figure} \begin{Figure}{tltc}{Foo}{Long Foo} \leavevmode \mapleplot{tltc.eps} \end{Figure} \begin{Figure}{dio3d}{Foo}{Long Foo} \leavevmode \mapleplot{dio3d.eps} \end{Figure} \begin{Figure}{tltc3d}{Foo}{Long Foo} \leavevmode \mapleplot{tltc3d.eps} \end{Figure} \begin{Figure}{qio5}{Foo}{Long Foo} \leavevmode \mapleplot{qio5.eps} \end{Figure} \begin{Figure}{tleftc}{Foo}{Long Foo} \leavevmode \mapleplot{tleftc.eps} \end{Figure} \begin{Figure}{didb3dk}{Foo}{Long Foo} \leavevmode \mapleplot{didb3dk.eps} \end{Figure} \begin{Figure}{qback5}{Foo}{Long Foo} \leavevmode \mapleplot{qback5.eps} \end{Figure} \begin{Figure}{qio3d}{Foo}{Long Foo} \leavevmode \mapleplot{qio3d.eps} \end{Figure} \begin{Figure}{qb3d}{Foo}{Long Foo} \leavevmode \mapleplot{qb3d.eps} \end{Figure} \section{Architectural Tradeoffs} In this section we begin to develop a performance model for the Abacus computer. \subsection{Representative Algorithms} Low level vision applications can be divided into four broad categories based on the required communication. \paragraph{Point}. No communication occurs, as each pixel is updated based only on its value. Examples of this algorithm class are thresholding, pixel quantization, and image differencing. \paragraph{Neighborhood.} Communication occurs only over a small region surrounding a pixel, typically a 3 by 3 or a 5 by 5 neighborhood. The basic instance of this algorithm class is spatial convolution with a mask to perform linear filtering operations such as low pass filtering. Edge detection can be performed by thresholding the result of a high-pass filter operation. Non-linear operations such as median filtering, anisotropic diffusion, and morphological operations also fall into this class. Several non-local algorithms have been converted into a systolic form, and can therefore be performed with purely local communication. The Hough transform falls into this class. \paragraph{Data Reduction.} Communication is global but non-overlapping. Initially dense image-wide information is condensed to a few numbers. Responder count is an example of such an operation. \paragraph{Dense Transform.} Communication is global and overlapping. Fast Fourier transforms and sorting operations are an example of this class. \subsection{Slice Optimization} In addition to the usual architectural and algorithmic parameters, the RBP organization allows a compile-time selection of the concatenation factor $m$. This is the number of PEs grouped into a single PS. We would like to determine the optimal number of bit-slices operating for a particular algorithm. Assume the following constants: \begin{table}[ hbtp] \begin{center} \leavevmode \begin{tabular}{|c|l|} \hline Name & Description\\ \hline \multicolumn{2}{|c|}{Architectural} \\ \hline D & Number of registers in slice \\ k & Slice width\\ B & Bandwidth into each slice (per bit)\\ \hline \multicolumn{2}{|c|}{Algorithmic}\\ \hline R & Number of variables in algorithm\\ W & Bits in data word \\ N & Number of ops in sequence\\ Z & Number of answers and initial data items\\ \hline \multicolumn{2}{|c|}{Derived}\\ \hline f & Fraction of register misses (function of R,E)\\ E & Effective registers per pixel\\ \hline \multicolumn{2}{|c|}{Compiler Decision}\\ \hline m & Number of slices / pixel\\ \hline \end{tabular} \end{center} \caption{Architectural and Algorithmic Parameters} \label{tab:param} \end{table} Thus, a processing site consists of $m$ slices of $D$ registers each of $k$ bits. There are $W$ bits in each data word. The number of effective registers per pixel is the total number of bits in a processing site divided by the word length: \begin{equation} E = \frac{mkD}{W} \end{equation} %We have some constraints. First, there is at least 1 slice allocated per %pixel. Second, we have no more than $\frac{W}{k}$ slices per pixel (full %bit-parallelism): $W/k \geq m \geq 1$. \footnote{As a (not very useful) % consequence, $W/mk > 1$, so that $D \geq E$.} The time to load a word/operate on a word is equal to the number of bits to be loaded divided by the cumulative bandwidth/ALU width of the slices doing the loading: \begin{equation} T_{load} = \frac{W}{mBk} \ \ , \ \ \ T_{alu} = \frac{W}{mk}\\ \end{equation} So we model an operation sequence on a single pixel as loading some initial number $Z_{in}$ of words from off-chip memory, performing $N$ arithmetic operations, and writing $Z_{out}$ result words out, for a total of $Z$ loads and stores. Equation \ref{eq:proctime} gives the time required for processing a single pixel, assuming that for every memory fault the processor has to write the previous value to memory and load the requested value. This memory fault is going to occur on some fraction $f$ of the memory accesses. \begin{equation} \label{eq:proctime} T_{seq} = Z T_{load} + 2Nf(R,E)T_{load} + NT_{alu} \end{equation} Assume that there are $P$ pixels to be processed and $M$ slices to process them. If $m$ slices are allocated to a pixel, $M/m$ pixels are processed in a time step of $T_{seq}$, so that $Pm/M$ iterations are required. It is convenient to define the quantity $l=Z/N$, the ratio of initialization operations (forced cache misses) to iterative operations (possible cache hits). \begin{eqnarray*} T_{tot} & = & \frac{P}{M}m T_{seq}\\ & = & \frac{P}{M}m \left[ \left( Z+2Nf(R,E) \right) \frac{W}{mBk} + N\frac{W}{mk} \right] \\ %% & = & \frac{PW}{Mk}\left[ \frac{Z+2Nf}{B} + N \right] \\ %% & = & \frac{PWN}{Mk}\left[ \frac{Z/N+2f}{B} + 1 \right] \\ & = & \frac{PWN}{Mk}\left[ \frac{(l+2f)}{B} + 1 \right] \\ & \propto & \frac{(l+2f)}{B} + 1 \\ \end{eqnarray*} %% Of course, if $m>k$ , then $T_{alu}$ saturates at 1. The simplified model presented in this chapter does not consider the disadvantages of RBP, such as the overhead of PEs whose ALUs are unused, or the distribution of conditional information to each PE. Therefore, the obtain optimal concatenation factor $w$ will always be too high. Nevertheless, the performance improvement is an upper bound on the advantage of RBP. However, the analysis applies only to single-phase algorithms. The flexibility advantage has not been incorporated. So, we would like to choose $m$ to minimize $T_{tot}$, given the algorithmic constraints of $W$, $N$, $Z$, $f$; the architectural constraints of $B$ and $D$. We could evaluate this exactly, except that we do not know the behavior of the miss function $f(R,E)$. So we'll explore some plausible functions. \begin{enumerate} \item {\em Case 1: No Cache Misses}. If $R < E$, we have enough local storage and $f = 0$. $Q$ then becomes independent of $m$. This indicates a bad initial design point: both in the nibble-serial mode and in the nibble-parallel mode, all data fits in memory. Therefore, the memory is too big. \item {\em Case 2: All Cache Misses}. If the algorithms steps repeatedly through all the registers, the miss rate is effectively 100\%. Again, the number of nibbles allocated is irrelevant. \item {\em Case 3: Random Register Usage}. If the register used during each step is selected at random from the logical registers, there is a $E/R$ probability that it is already in the cache. $f$ is therefore \begin{equation} f(E,R) = 1-\frac{E}{R} = 1 - \frac{mkD}{WR} = \frac{WR - mkD}{WR} \end{equation} So, to maximize performance we want to lower $f$ and therefore increase $m$. \end{enumerate} In conclusion, $m$ should always be maximized. \subsection{Conclusion} The following plots are for parameter settings of: \begin{center} \small \begin{tabular}{|c|l|r|} \hline \hdr{Variable} & \hdr{Meaning} & \hdr{Value} \\ \hline Dr & number of registers in slice & 50 \\ k & slice width & 1 \\ Bw & bandwidth into each slice (per bit)& 0.05 \\ R & registers in algorithm & 30 \\ Wb & bits per word & 16 \\ Z & initial loads/saves & 10 \\ N & number of operations in a sequence& 30 \\ \hline \end{tabular} \end{center} \begin{figure}[ hbtp] \begin{center} \leavevmode \mapleplot{perf_func_m.ps} \end{center} \caption{Execution time as function of $m$. The dip in the middle is the effect of background loading. Without it, the graph would have continued in a straight line. Notice that the dip occurs at a non-useful $m$ value, as it is difficult to evenly partition a 16-bit value.} \label{fig:execfuncm} \end{figure} The algorithm requires 480 bits. At 9.6 slices per pixel, there are no external references and time is constant. Background loading makes a difference only in a narrow zone. Until about $m=7.8$, The linear performance improvement is due to the linearly decreasing hit frequency in our simplified model. \begin{figure}[ hbtp] \begin{center} \leavevmode \mapleplot{cycles_vs_m_bw.ps} \end{center} \caption{Execution time as function of m and bandwidth} \label{fig:execfuncm2} \end{figure} The main conclusion is that external memory references are catastrophic, and that the number of bit-slices should be chosen to minimize the number of external loads. The model can be made more accurate in a number of ways. \begin{enumerate} \item Accounting for the circuit density improvement of higher-width bit slices. \item Speed decreases due to larger ALU widths. Of course, this may not matter if the cycle time is dominated by memory access. \item Slower memory accesses with increasing memory size. \item Better estimates of cache miss behavior as a function of available registers. \end{enumerate} As illustrated by the graphs in this section, the last modification is probably the most significant, since the initial three factors are not likely to be more than a factor of 2 each, while cache misses can result in order of magnitude performance changes. \section{Misc} There are a number of methods to compare design tradeoffs; holdings some parameters constant while varying others. For reconfiguration analysis, the hardware is fixed, and only the number of slices operating on a data word is varied. In this design example, we return to a design-time analysis, and compare a bit-serial system with a bit-parallel one. The BP system may or may not be reconfigurable. Consider a PE with 2 cycles/bit bandwidth to external memory. This is typical of a chip containing 1000 PEs, operating at Consider an algorithm that requires 1000 ops, and has 10\% misses. The bit-serial system needs 16K ALU cycles, and encounters 100 misses. These misses are spaced 9 ops apart, which is 144 cycles. Assuming a load and a store, each miss costs 2 x 16 x 2 = 64 cycles. is plenty of time to do loads between misses. Total time is 16K. The bit-parallel system with the same memory contents encounters the same number of misses. BUT its misses are 36 cycles apart, so each miss now has to wait for 28 cycles. So the 100 misses cost 2.8K cycles. Now, since computation took 4K cycles, the total time is 6.8K. The fourfold advantage has now dropped to 2.5. The same thing without background loading. The 100 misses cost the same in both cases, 6.4K cycles. The ratio is now (16+6.4)/(4+6.4) = 2.15. This is somewhat surprising. The background loading helps the bit-parallel case more than the bit-serial case. Why? Because the IO time is a larger share of the total compute time. In the first case, total time time dropped from 22.4 to 16.4. A factor of 0.73. In the second case, total time dropped from 10.4 to 6.8, a factor of 0.65. \section{Local Memory vs External Bandwidth} In this section we determine how performance on an algorithm varies as a function of the size on-chip register file, and the off-chip memory latency. The limiting cases are obvious. When the entire computation fits into the register file, the off-chip latency becomes irrelevant. When latency is very low, there is no need for a register file at all. If we plot performance as a function of register file size $s$ and off-chip memory latency $l$, we get a slope falling off to the northwest, where both latency is high and on-chip capacity is low. So, for an given acceptable level of performance, we can travel the curve, trading off capacity for latency. To convert this expected graph into a design optimization tool, we need to assign resource costs and physical limitations, based on current technology. This cost assignment is a challenging task, since it incorporates a good number of technology assumputions. \begin{verbatim} Latency | L L L M High | L L M H | L M H H | M H H H Low | H H H H ------------ Low High RF Size \end{verbatim} \subsection{Assumptions} The approach will be be to list assumptions and upcoming technology trends that will affect them, as well as the direction of change. \begin{itemize} \item Perimeter-based IO structure. Although area-based interconnect technologies are coming, they are not dominant. [references. expand]. \item Double-ring structure. Bonding to a double-ring structure is not difficult. \item 100 micron pitch pads. Lower pitch will decrease the cost of off-chip bandwidth. \item Low inductance area-based packages. BGAs are coming. \end{itemize} There are a number of limitations on off-chip access times, based on both existing technologies, and other design constraints. For example, assume a 10~ns PE cycle time. Off-chip memory latency consists of two parts. First, the basic access time of the memory, which can be negligible for a modern fast SRAM, or significant for a DRAM-based memory such Rambus. By negligible, I mean times as low as 4~ns for a fast SRAM [ref Chappel]). By significant, I mean several cycles. The second component is the bandwidth-limitation imposed latency of getting the 1000 bits of data or so onto the PE chip through a relatively narrow bus. For example, with a 32-bit bus, a 2:1 external/internal cycle time (16~ns SRAM cycle time, 8~ns internal), 64 cycles are required to load each of 1024 PEs with a data bit. This second component dominates the overall latency for any reasonable technologies. The following table assumes that one memory access is required for every arithmetic operation. Therefore, total bandwidth in bits/nanosecond is the GOPS rating multiplied by 16. This model assumes an accumulation based operation, in which an internal register is updated by an external value. If each arithmetic operation used two new operands and wrote one new result, such as in an elementwise vector multiply, the bandwidth requirements would go up by a factor of three. \begin{table} \begin{center} \begin{tabular}{|l|r| r |r | r | r | r|r|} \hline Name & PEs & Width & Clock & Cyc/op & GOPS & Bus & bit rate \\ & & & (MHz) & & & & bits/pin/ns \\ \hline Abacus-1, BS & 1024 & 1 & 125 & 1 & 7.5 & 64 & 1.88 \\ Abacus-1, BP & 1024 & 1 & 125 & 3 & 2.5 & 64 & 0.63 \\ Abacus-2/4 & 256 & 4 & 100 & 1 & 6.4 & 64 & 1.60 \\ Abacus-2/8LC & 64 & 8 & 62 & 1 & 2.0 & 8 & 4.00 \\ \hline \end{tabular} \end{center} \end{table} %%The Abacus-8/LC part is designed to fit into a plastic package with a small %%number of pins. It therefore sacrifices performance density for substantially %% lower cost. \subsection{Cost Analysis} The cost issue is difficult to establish, because of multiple interacting factors. For example, a low cost design point uses cheap packages with relatively high package parasitics. But reducing the supply voltage to deal with the low thermal tolerance of plastic packages also reduces the peak current draw, and therefore the ground bounce. Finally, pricing is a delicate matter of balancing chip carrier cost, PCB cost, defect probability, ease of assembly, and a host of other factors. Any analytical equations are therefore misleading in their apparent exactness. At best, they will serve as guidelines. Even if this was possible, it would be difficult to assign a cost to integration. In the extreme case, the best performance per area would be obtained by a small number of processors with a large pad ring. External memory accesses would have very low latency in this configuration, so that very little silicon area need be devoted to the register file. The apparent performance per area would increase, but at the cost of integration. This effect will be ignored (instead of say, weighing the number of chips in a design as part of the cost), but the number of chips required to process an image will be noted for qualitative evaluation. \paragraph{Pads} The equation for the number of pads consts of three parts: \begin{enumerate} \item A fixed component due to the instruction, boundary scan, and IO wires. This is estimated at 40 pads for a 40-bit instruction word, assuming instructions are sent using both clock edges. \item A slowly varying component of mesh communication wires. Once a particular mesh move latency is accepted (say four cycles for a 16-bit number, requiring four bits per edge element per cycle), the pad count grows as the square root of the total datapath width. Of course, the dimensions of the PE array will most likely be powers of two. For example, the 1024-bit Abacus-1 data path organized as 16-bit clusters is effectively an 8 x 8 array of 16-bit PUs. To transfer a 16-bit number between chips with a latency of four requires 4 bits/cycle/edge PU, or 32 bits/cycle/edge. Assuming sending on both clock edges, each edge must have 16 pins. Including three control wires per port, the total pin cost was 76. In vertical slice mode, $t_{ALU} = 16$, so it can take up to 64 cycles to transfer the 16 bits. This is 0.25 bits/cycle/edge PU, or 8 bits/cycle/edge. Total pin cost is only 44. Consider the 8 x 8 array of 8-bit PUs. Transfer of a 16-bit number with a latency of eight cycles (four times $t_{ALU}$) requires 2 bits/cycle/edge PU or 16 bits/cycle/edge. Each edge must only have 8 data pins, or 11 pins in total. \begin{displaymath} N_{mesh} = 4 \times (\sqrt{\frac{N_{datapath}}{\mbox{PE Width}}} + 3) \end{displaymath} \item A quickly varying component of memory subsystem wires. \end{enumerate} \begin{table} \begin{center} \begin{tabular}{% |l |l |l |l |l |l |l |} \hline Pads& w1 & h1 & W & H & Area & Core\\ \hline 208 & 52 & 48 & 8.4 & 7.8 & 65.5 & 56.2\\ 208 & 39 & 61 & 6.5 & 9.8 & 62.9 & 53.5\\ 208 & 26 & 74 & 4.5 & 11.7 & 52.7 & 43.3\\ \hline 336 & 84 & 80 & 13.2 & 12.6 & 166.3& 151.2\\ 336 & 63 & 101 & 10.1 & 15.8 & 158.3& 143.2\\ 336 & 48 & 116 & 7.8 & 18.0 & 140.4& 125.3\\ \hline 448 & 112 & 108 & 17.4 & 16.8 & 292.3& 272.2\\ 448 & 84 & 136 & 13.2 & 21.0 & 277.2& 257.0\\ 448 & 96 & 124 & 15.0 & 19.2 & 288.0& 267.8\\ \hline \end{tabular} \end{center} \end{table} \begin{table} \begin{center} \begin{tabular}{% |l |l |l |l |l |l |l |} \hline Pads& w2 & h2 & W & H & A2 & Core\\ \hline 208 & 26 & 24 & 4.5 & 4.2 & 24.5 & 14.0\\ 208 & 20 & 31 & 3.5 & 5.2 & 23.8 & 13.4\\ 208 & 13 & 37 & 2.5 & 6.2 & 21.3 & 10.8\\ \hline 336 & 42 & 40 & 6.9 & 6.6 & 54.0 & 37.8 \\ 336 & 32 & 51 & 5.3 & 8.2 & 52.0 & 35.8 \\ 336 & 24 & 58 & 4.2 & 9.3 & 47.5 & 31.3 \\ \hline 448 & 56 & 54 & 9.0 & 8.7 & 89.3 & 68.0 \\ 448 & 42 & 68 & 6.9 & 10.8 & 85.5 & 64.3 \\ 448 & 48 & 62 & 7.8 & 9.9 & 88.2 & 67.0 \\ \hline \end{tabular} \end{center} \end{table} \begin{displaymath} Area_1 = p^2wh + 2lp(h+w) + 4l^2 \\ Area_2 = p^2wh + 4lp(h+w) + 16l^2 \end{displaymath} \subsection{External Memory Alternatives} The emergence of multimedia and video-intensive applications, as well as the ever increasing clock speeds in systems, has outpaced the abilities of standard random access memory. RAM manufacturers have improved technologies and developed new architectures in response to this demand for higher memory speeds. This explosion of new RAM types will require careful analysis of the operating trade-offs among the various alternatives to make best use of capabilities of the new generation of memories. \begin{table} \begin{center} \begin{tabular}{|l | r| r | r |r|r|} \hline Name & Width & Cycle & Initial Latency & Data Rate & Addr Line \\ & (max) & (MHz) & (ns) & bits/pin/ns & Overhead \\ \hline %% 0.6 GB/sec -> 0.6 bits/ns Rambus & 9 & 600 & 50 & 0.6 & 4 \\ SSRAM & 32 & 100 & 5 & 0.1 & 18 \\ SDRAM & 32 & 100 & 50 & 0.1 & 22 \\ EDRAM & 8 & 66 & 30 & 0.066 & 22 \\ \hline \end{tabular} \end{center} \end{table} Note: incorporates about 17 ns of controller pipelining. \begin{table} \begin{center} \begin{tabular}{|l | r| r | r | r |r|r|} \hline Configuration & Pins & Pins & BW & Lat & Lat & Lat\\ & Total & Signal & bits/ns & init& data & Tot \\ \hline Rambus, 1 port & 13 & 9 & 5.4 & 50 & 190 & 240 \\ Rambus, 2 ports & 26 & 18 & 10.8 & 50 & 95 & 145 \\ Rambus, 3 ports & 39 & 27 & 16.2 & 50 & 63 & 113 \\ SSRAM, 32 bits & 50 & 32 & 3.2 & 0 & 320 & 320 \\ SSRAM, 64 bits & 82 & 64 & 6.4 & 0 & 160 & 160 \\ \hline \end{tabular} \end{center} \end{table} \section{Virtualization} This analysis assumes a neighbor organization, where a rectangle of adjacent pixels is mapped onto one WU. If all virtual pixels fit into memory, only perimeter data moves require actual communication between chips. Thus, if each pixel holds a 3 by 3 neighborhood, only 3 grid operations are required for a move of all 9 pixels. The rest are internal memory transfers, or even better, just different local references, which are free. \begin{figure} \begin{center} \sl \Large VP Perimeter picture \begin{verbatim} A2 = FromWest(B3); A0 = FromWest(B1); A1 = B0; A3 = B2; \end{verbatim} \end{center} \end{figure} High VP ratio also reduce the peak memory requirements of algorithms. Consider a VR of 16, and the following code segment (implementing a triangle filter). \begin{figure} \begin{center} \sl \Large VP Perimeter picture \begin{verbatim} T1 = FromWest(A); T2 = FromEast(A); T2 = (T1 + T2)/2 + A; \end{verbatim} \end{center} \end{figure} A VR1 WU would transfer T1 and T2 to itself, for a WU requirement of 48 bits (assuming each word is 16 bits). Peak memory requirement for 16 of these units is 768 bits. The VR16 WU need only use one scratch location for computing T1, reducing memory needs to $2 \times 16 + 1 = 33$ words of 16 words each, or 528 bits. Actually, the VR1 ALUs can also perform this reduction if they can compute with each bit as it comes in, and then discard it. For fast update code, where little computations occurs for every grid move, high VP ratios are preferred As edge-crossing latencies increase, high VRs will be more favorable. Consider a VP ratio of 16 when implemented with a 16-bit WUs, which would be 1 with 1-bit WUs. A single move operation requires 4 grid moves in the first case, and 16 in the second. But a grid move of a 4x4 cluster requires 4 cycles, while a grid move of a unit cluster requires only one. In each case, the move of 16 pixels requiers 16 cycles. Adding a one cycle penalty on each transfer due to pipelining leads to 4 * 5 = 20 cycles for the first, and 16 * 2 = 32 cycles for the second. Extra latency on pin crossings favors high VP ratios, since its cost is amortized on a move of several bits in the high VP case. \paragraph{Foo} It is clear that concatenation implies virtual processors. Obviously, each word unit now must iterate over $m$ PEs. The model in Audet's paper ignores issues such as context swaps at synchronizations. For example, the associated \emph{active} bit must be restored for each VP. While it is true that simple image filtering operations do not use the active bit, many other algorithms do. Every algorithm that contains a \emph{where} clause will be more expensive for wide WUs. In the extreme case of a very simple computation such as logical AND, the highly concated WU will be twice as slow, as the active restore overhead takes as much time as the computation. \paragraph{Bar} A large working set size gives the wide WU an advantage. Consider an algorithm with a working set size of 4 16-bit words, (such as a temporal filter), 10 iterations per update, and bit slices with a physical size of 32 bits, a. A VR1 implementation will require 2 loads per iteration, while a VR16 iteration requires none. Between VPs, the VR16 implementation has to load up the context half of the time, but this is amortized over all iterations. \paragraph{Pithy} Issue is primarily how to allocate fast bits to the pixel. %%% Local Variables: %%% TeX-master: "main" %%% comment-start: "%%% " %%% End: ***