\message{ !name(main.tex)}% -*- Mode: LaTeX; -*- % File: main.tex|thesis/ % Author: Mike Bolotski (misha@ai.mit.edu) % Copyright (C) Artificial Intelligence Laboratory, 1996 %*------------------------------------------------------------------------- % %* PURPOSE: Top file of thesis %* %* HISTORY: %* Last edited: Sep 6 00:13 1996 (misha) %* May 29 13:44 1996 (misha): Gratefull copied from Maja's all.tex %* Created: Wed May 29 13:43:10 1996 (misha) %*------------------------------------------------------------------------- % \documentstyle[11pt,config,equationarray,mapleenv]{mitthesis} \documentstyle[11pt,thesisconfig,equationarray,mapleenv,singlespace,twoside]{mitthesis} \pagestyle{headings} \def\mypsdirectory{/fs/abacus/misha/thesis/PS/} \def\mapleplot#1{ %\vskip\AboveMaplePlot \centerline{\vbox{\psfig{figure=\mypsdirectory#1,% height=80mm,% width=120mm,% %%height=\MaplePlotHeight,% %%width=\MaplePlotWidth,% angle=\MaplePlotAngle}}} \vskip -2ex } %\def\mapleplot#1{ %\vskip\AboveMaplePlot %\centerline{\vbox{\psfig{figure=\mypsdirectory#1,% %height=\MaplePlotHeight,% %width=\MaplePlotWidth,% %angle=\MaplePlotAngle}}} %\vskip\BelowMaplePlot %} %%% Draft-oriented stuff %% \pagestyle{myheadings} %% \markright{DRAFT VERSION OF \today} %% \includeonly{rough} \begin{document} \message{ !name(analytical.tex) !offset(-54) } %* Last edited: Sep 6 00:13 1996 (misha) \chapter{Analytical Modeling \chaplabel{analytical}} \section{Optimal Bit Width Analysis} Selection of the bit slice width in a SIMD computer is not 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. The initial ideal model estimates the area, delay, and cycles-per-instruction (CPI) of a given bit width and simply multiplies to obtain a figure of merit. This metric, called \emph{quality\/} in this work, is normally expressed in bit operations per nanosecond per unit area, but for better intuition has been scaled to billions of 16-bit operations per second per standard chip. The first refinement uses Amdahl's law to account for operations which are not sped up by a wider datapath. The next refinement recognizes that off-chip memory latency is a critical bottleneck, and determines the effect of cache misses. Finally, the model incorporates the effect of the background loading mechanism on I/O performance. \begin{Table}{modelparams}{Analytical Model Parameters}{Analytical Model Parameters from the Abacus-1 Implementation.} \begin{tabular}{|l|l|l|} \hline Parameter & Value & Description \\ \hline $A_{alu}$ & 8 & ALU area, in units of SRAM cells \\ \hline $A_{ovr}$ & 10 & Overhead area, in units of SRAM cells \\ \hline $f_A$ & 0.9 & Fraction of operations affected by wider datapath \\ \hline $T_{mem}$ & 3 ns & Register file access time \\ \hline $T_{alu}$ & 0.7 ns & ALU datapath bit delay \\ \hline $T_{ovr}$ & 1.0 ns & Timing overhead \\ \hline \end{tabular} \end{Table} \subsection{Ideal Model} \paragraph{PE Area.} A processing element's area is modeled 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}(k) = N_{mem} + kA_{alu} + A_{ovr} \end{equation} where $N_{mem}$ is the number of memory bits and $k$ is the width of the datapath. 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 may provide a more efficient alternative. \paragraph{Cycle Time.} The model assumes an unpipelined design, in which the cycle time consists of four parts: register file read, ALU ripple-style execute, register file write, and miscellaneous time margin. Register file access times are assumed identical for read and write, and include precharge and equilibrate time. \begin{equation} T_{pe}(k) = 2 T_{mem} + kT_{alu} + T_{ovr} \end{equation} ALU times are also assumed linear. This holds true for both the ripple-carry adder and the Manchester-carry adder (although in that case the fixed part of the cycle will grow due to the PG and Sum cells, and $T_{alu}$ will decrease). Many more sophisticated adder structures are possible but they require more area and gain in speed only for large word sizes. \paragraph{Performance.} In the ideal model, the number of cycles required to execute an instruction decreases linearly with the datapath width. Thus, a $k$-bit ALU requires twice as many cycles to perform an operation as a $2k$-bit ALU. \begin{equation} P_{pe}(k) = k \end{equation} \paragraph{Quality Metric.} The effectiveness of a PE is expressed as the number of operations per unit area per unit time. \begin{equation} Q_{ideal}(k) = \frac{k}{A_{pe}T_{pe}} = \frac{k}{(N_{mem} + kA_{alu} + A_{ovr})(2 T_{mem} + kT_{alu} + T_{ovr})} \end{equation} This function is plotted in \fig{idealq}. Several conclusions can be reached from this plot. First, smaller memory sizes lead to higher performance. This is not surprising, since smaller PEs with identical computational throughput lead to better quality measures. Second, as memory increases, the optimal datapath width $k$ also increases. This occurs because adding a few more datapath bits to a large PE improves performance without a substantial change in area. The final conclusion is that the function has a very flat optimum, so that it does not cost much to err on the side of larger $k$. \begin{Figure}{idealq}{Foo}{Ideal Performance (GOPS/chip) as a function of datapath width. The four graphs correspond to memory sizes of 32, 64, 128, and 256, from top to bottom.} \leavevmode \mapleplot{idealq.eps} \end{Figure} The next observation comes from normalizing the performance to the bit-serial case ($k=1$). \fig{idealqn} shows that wide datapaths can be up to 4.5 times more efficient than the bit serial case. Unfortunately, the greatest relative advantage occurs at a lower absolute performance level. \begin{Figure}{idealqn}{Foo}{Normalized Ideal Performance. This shows the relative advantage of the wide datapath over the bit-serial case.} \leavevmode \mapleplot{idealqn.eps} \end{Figure} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Amdahl's Law} The next refinement to the model is the application of Amdahl's law, which essentially states that if parallelization (or any speedup) affects only a subset of the total computation, the remaining fraction will greatly reduce the effectiveness of the speedup. This is the basic equation of computer architecture. Mathematically: \begin{equation} S_a(k) = \frac{1}{\frac{f_A}{S} + (1-f_A)} \end{equation} where $f_A$ is the fraction of the computation affected by the speedup $S$, and $S_a$ is the actual obtained speedup. Thus, \begin{equation} Q_a(k) = \frac{S_a}{A_{pe}T_{pe}} \end{equation} In the context of the current design, $f_A$ represents the fraction of arithmetic oriented operations in a program. Operations that are not sped up by a wider datapath include network communication and logical flag-manipulating 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 value of $f_A$ used in the model was chosen to be 0.9. It was supported by the results of two related research works. Holman \cite{Holman89} explicitly listed $f_A$ for a variety of algorithms, as in \tab{holmanfractable}. The obtained values are slightly higher than expected for vision algorithms, as most of the listed algorithms are dominated by floating point manipulations. \begin{Table}{holmanfractable}{Fraction of Operation Costs Affected by Data Path Width}{Fraction of Operation Costs Affected by Data Path Width. From \cite{Holman89}} \begin{tabular}{|l|r|} \hline Program & $f_A$ \\ \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 \cite{Herbordt94b} evaluation of parallel architectures included a set of simulation results relating datapath width to execution time. The value of $f_A$ was extracted by fitting Amdahl's function to the published performance curves. The fitted functions agreed well with the simulation data, although half of the algorithms had unexpectedly high performance for the case $k=1$. The 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 intermediate value shown for the IU Benchmark entry occurs because the benchmark 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_A$ \\ \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} The same configurations as in the ideal case but with Amdahl's-law correction are shown in \fig{amdq}. The greatest difference occurs in the high-performance low-memory case. Here, the additional dead weight of the wide datapath is a relatively large penalty compared to the small overall PE size. The maxima are much sharper than in the ideal case, but level off quickly as memory size is increased. \begin{Figure}{amdq}{Amdahl-corrected quality values}{Amdahl-corrected quality values.} \leavevmode \mapleplot{amdq.eps} \end{Figure} The normalized equations behave similarly to the ideal case, except that maxima now become apparent. \fig{amdqn} also shows that the relative overall advantage of wider paths decreases from a former peak of 4.5 to 3. \begin{Figure}{amdqn}{Normalized Amdahl-corrected quality values}{Normalized Amdahl-corrected quality values} \leavevmode \mapleplot{amdqn.eps} \end{Figure} The effect of varying $f_A$ is shown in \fig{amdqn3d}. The axis is actually labelled with $(1-f_A)$, the fraction not affected by the speedup. The expected interaction of the two parameters occurs. The best $k$ for this configuration appears to be 4-6 bits over a wide range of $f_A$, 0.8 to 0.98. Notice that in the low $f_A$ case, the multibit configurations perform worse than the bit-serial ones. \begin{Figure}{amdqn3d}{Normalized quality vs $k$ and $f_A$}{Normalized quality vs $k$ and $f_A$} \leavevmode \mapleplot{amdqn3d.eps} \end{Figure} %\begin{Figure}{amdqn3d2}{Foo}{Long Foo} % \leavevmode \mapleplot{amdqn3d2.eps} % \end{Figure} \clearpage \subsection{Off-Chip Data} The preceding analysis applies to algorithms that execute from the on-chip registers. As soon as a data item must be brought in from off-chip, a significant delay occurs. This section analyzes the impact of this delay. An implicit assumption being made here is that commercially available memory chips are at least one technology jump from that available to a university or a low-volume commercial design. If the SIMD chip was implemented in a comparably dense technology, other design points would become feasible, and the model will have to be expanded. A recent example of research in this direction is the Execube chip, which integrates several 32Kx8 DRAM memories with 16-bit PEs. Once off-chip memories are part of the design, the model must determine two parameters: the available bandwidth per pin, and the number of pins allowed on the PE chip. The former is limited by the capabilities of commercial memory devices and the latter by packaging constraints. A comparison of contemporary high-bandwidth memory alternaties are shown in \tab{memories}. \begin{Table}{memories}{Contemporary Memories}{Contemporary Memories} \begin{tabular}{|l | r| r | r |r|r|} \hline Name & Width & Cycle & Initial & Data Rate & Address \\ & (max) & Frequency & Latency & & Line \\ & & (MHz) & (ns) & bits/pin/ns & Overhead \\ \hline %% 0.6 GB/sec -> 0.6 bits/ns Rambus & 9 & 600 & 50 & 0.6 & 4 \\ Synchronous SRAM & 32 & 100 & 5 & 0.1 & 18 \\ Synchronous DRAM & 32 & 100 & 50 & 0.1 & 22 \\ Extended DRAM & 8 & 66 & 30 & 0.066 & 22 \\ \hline \end{tabular} \end{Table} The parameter that controls how long PEs must stall waiting for the data is latency: the time from the data request until the data arrives. Different memory organizations have varying latencies, from the 4~ns of high-speed SRAM \cite{Chappell91} to the 35~ns of a fast DRAM. SIMD architectures encounter another cause of latency: bandwidth limitation. Since all PEs must wait until data is received, the latency is increased by this wait period. Because of this phenomenon, memory organizations with high latency but with a high burst bandwidth may well exhibit lower latency, especially since SIMD-oriented transfers occur in units of hundreds (or thousands) of bits. The initial latency is amortized over all elements in the burst. The Rambus part falls into this category. Unfortunately, even though products are beginning to incorporate this interface, the technology is still difficult to use in a design. A comparison of these latencies is shown in \tab{latencies}. \begin{Table}{latencies}{Latencies of Memories}{Latencies of Memories} \begin{tabular}{|l | r| r | r | r |r|r|} \hline Configuration & Pins & Pins & BW & \mcol{3}{|c|}{Latency}\\ & Total & Signal & bits/ns & initial & data & total \\ \hline Rambus, 1 port & 13 & 9 & 5.4 & 50 & 190 & 240 \\ Rambus, 2 ports & 26 & 18 & 10.8 & 50 & 95 & 145 \\ SSRAM, 32 bits & 50 & 32 & 3.2 & 0 & 320 & 320 \\ SSRAM, 64 bits & 82 & 64 & 6.4 & 0 & 160 & 160 \\ \hline \end{tabular} \end{Table} The more conservative design described here assumes a conventional SRAM operating at a 16~ns cycle time through a 64-bit port. The aggregate bandwidth is therefore 4 bits/ns. An important realization incorporated in the model is that for a fixed chip size, bandwidth (and therefore latency, as discussed earlier), is also fixed, and may therefore be expressed as bits per nanosecond per unit area. This somewhat odd normalization is useful because PE area fluctuates as a function of datapath width, and the available bandwidth changes with it. Based on the Abacus design, the total PE area consisted of approximately 100,000 SRAM cell equivalents. Thus the bandwidth per unit area, $B$, is 0.00004. The time to provide a data word to all PEs in the array from an off-chip chip memory is: \begin{equation} T_l = \frac{w}{\mbox{PE bandwidth}} = \frac{w}{A_{pe}B} \end{equation} where $w$ is the data word width. It will eventually cancel out, so its exact value is not important. The next parameter to be determined is $T_s$, the amount of time that passes between load operations. Given these two quantities, the performance degradation $D_{io}$ is given by: \begin{equation} D_{io} = \frac{T_s}{T_s+ T_l} \end{equation} We use a very simple model of load events, namely a fixed frequency. Conventional caches often use Poisson (or other) distributions but control flow is much more predictable in SIMD systems, and loops are likely to access variables in a repetitive stride. A load event occurs with a period of $f_{miss}^{-1}$ instructions. Another important realization of the model is that the duration of a cache hit sequence is a function of the average instruction duration. Thus, $T_s$ is the number of instructions between misses, times the average number of cycles per instruction, times the length of each cycle. \begin{equation} T_s = \left(\frac{1}{f_{miss}}\right) T_{pe} \frac{w}{kS_a} \end{equation} \begin{Figure}{tltc}{Load Time Compared to Load Period.}{Load Time Compared to Load Period. The upper monotonic curve is $T_l$, while the lower one is $T_s$. Their ratio, scaled up, is also shown} \leavevmode \mapleplot{tltc.eps} \end{Figure} An interesting effect is shown in \fig{tltc}. The ratio of $T_l$ to $T_s$ exhibits a maximum at about $k=6$. This occurs because $T_s$ decreases very quickly at first, far faster than $T_l$ drops due to higher bandwidth per PE. The shape of the ratio curve should appear familiar, as can be seen from the following derivation. \begin{eqnarray} D_{io} & = & \left( 1+\frac{T_l}{T_s} \right)^{-1}\\ & = & \left( 1+\frac{\frac{w}{A_{pe}B}}{\frac{T_{pe}w}{f_{miss}}kS_a} \right)^{-1}\\ & = & \left( 1+\frac{fkS_a}{A_{pe}BT_{pe}} \right)^{-1}\\ & = & \left( 1+\frac{fQ_a}{B} \right)^{-1} \end{eqnarray} The performance degradation due to off-chip accesses therefore has a simple form: \begin{equation} D_{io} = \frac{1}{1+\rho Q_a} \end{equation} where $\rho = f/B$. Thus, \begin{equation} Q_{io} = Q_{a} D_{io} = \frac{Q_a}{1+\rho Q_a} \end{equation} This equation says that as the quality factor increases, the impact of off-chip accesses grows. The method of achieving high performance is irrelevant. For a fixed algorithm ($f_{miss}$) and a fixed memory bandwidth ($B$), higher performance will throttle itself back at the memory level. %\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}{IO-derated Quality Metrics}{IO-derated Quality Metrics} \leavevmode \mapleplot{qio5.eps} \end{Figure} This effect can be seen in \fig{qio5}. At high $Q_a$ values, $Q_{io}$ begins to approach $\frac{1}{\rho}$. \begin{Figure}{qio3d}{IO-derated Quality Metrics (m=64,256))}{IO-derated Quality Metrics (m=64,256))} \leavevmode \mapleplot{qio3d.eps} \end{Figure} \clearpage \subsection{Background Loading} Performance of computer systems with predictable memory access patterns can be improved with the technique of prefetching or background loading. The Abacus-1 design allows a memory access to be initiated before the data is actually required, and relies on the compiler to perform this scheduling rather than analyzing access patterns at runtime. The net effect of background loading is to reduce the loading time penalty. The effective loading time is: \begin{equation} T_{\mbox{eff}} = max(0,T_l - T_s) \end{equation} and the derating factor becomes \begin{equation} D_{back} = \frac{T_s}{T_s + T_{\mbox{eff}}} \end{equation} % The ratio maximum again appears at around $k=6$. %\begin{Figure}{tleftc}{Foo}{Effective loading time and sequence time} % \leavevmode \mapleplot{tleftc.eps} % \end{Figure} \begin{Figure}{didb3dk}{Performance improvement due to background loading.}{Performance improvement due to background loading.} \leavevmode \mapleplot{didb3dk.eps} \end{Figure} The derating reduction improvement due to prefetching is shown in \fig{didb3dk}. There are several interesting aspects of this graph. First, at high miss rates ($f_m = 0.1$), prefetching only helps by about 10\%. The improvement is very rapid as hit rates increase, reaching the 50\% ``sweet spot'' at $f_m = 0.02$. Second, the relative improvement begins to worsen again at very low miss rates, when prefetching completely eliminates the load penalty and therefore cannot improve performance further, while the non-prefetched design is still reaping the benefits of less frequent accesses. \begin{Figure}{qback5}{Absolute performance, background loading.}{Absolute performance, background loading.} \leavevmode \mapleplot{qback5.eps} \end{Figure} Interesting effects can also be seen in the absolute performance curves in \fig{qback5}. \begin{Figure}{qb3d}{Prefetching-derated quality metrics}{Prefetching-derated quality metrics} \leavevmode \mapleplot{qb3d.eps} \end{Figure} Prefetching is so effective that performance saturates at the memory bottleneck. A two-dimensional version of this plot is shown in \fig{qb3d}. Repeating the mathematical analysis of the previous section leads to very interesting results. First, we need only look in the case where $T_{eff} > 0$, since otherwise the load penalty is zero, and $D_{back} = 1$. \begin{equation} D_{back} = \frac{T_s}{T_s+(T_l-T_s)} = \frac{T_s}{T_l} = \frac{1}{\rho S_a}\\ \end{equation} This equation says that prefetching makes performance independent bit-slice width! When this computation is made explicit, the intuitive explanation becomes apparent: a long as a sequence of computations takes less time that the load delay, there is no benefit to improving the datapath efficiency. There are several observations: \begin{itemize} \item Prefetching makes the IO system behave in two qualitatively different modes. If the load penalty is smaller than the sequence delay, the external memory seems to disappear, since the PEs operate as if all data was in local registers. If the load penalty is greater than the sequence delay, the external memory becomes the only factor controlling performance. \item For a memory-limited design, increases in computational efficiency are invisible. Even if a clever data representation halves the computing time at no area penalty, the overall performance will be completely unaffected. \end{itemize} The advantage of reconfigurable systems now becomes clear. Whenever an algorithm enters a bandwidth-saturated phase, a reconfigurable system can configure itself as a wider datapath with more local memory to reduce the miss frequency and therefore improve performance. For purposes of illustration assume miss frequency is linear in memory size. Using the data of \fig{qb3d}, a \{k=4,m=64\} system operating at $f_{miss} = 0.04$ can become \{k=16,m=256\} system at $f_{miss}=0.02$ and gain 30\% improvement. \subsubsection{Less Predictable Access Patterns} We would like to determine the benefit of background loading 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 more pessimistic 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 $T$ given a string of $k$ available cycles is $L-k$, the expected value of $T$ 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}{leff}{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.} \leavevmode % \mapleplot{Leff_vs_f1.ps} \mapleplot{Leff_vs_f2.ps} \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} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Conclusions} 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. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{What's Missing} What this section really needs is to 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 assumptions. %\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} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %\section{WARNING: NOT READY: 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{Effect of Virtualization} %This analysis assumes a neighbor organization, where a rectangle of %adjacent pixels is mapped onto one PS. 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 PS would transfer T1 and T2 to itself, for a PS requirement of 48 %bits (assuming each word is 16 bits). Peak memory requirement for 16 of %these units is 768 bits. The VR16 PS 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 PSs, which would %be 1 with 1-bit PSs. 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. %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 PSs. In the extreme case of a very simple %computation such as logical AND, the highly concated PS will be twice as %slow, as the active restore overhead takes as much time as the computation. %A large working set size gives the wide PS 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. %\section{Unfinished} %\paragraph{Pin Bandwidth} The good news is that the IO rates of memories %have been rapidly increasing in recent years, driven by wide variety of %device architectures. This explosion of new RAM types requires careful %analysis of the operating trade-offs among the various alternatives. %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. %\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} %\paragraph{Number of Pins} %\begin{Table}{padringcalc}{Pad Ring Organizations}{Pad Ring Organizations} %\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 & 26 & 74 & 4.5 & 11.7 & 52.7 & 43.3\\ %\hline %208 & 26 & 24 & 4.5 & 4.2 & 24.5 & 14.0\\ %208 & 13 & 37 & 2.5 & 6.2 & 21.3 & 10.8\\ %\hline %336 & 84 & 80 & 13.2 & 12.6 & 166.3& 151.2\\ %336 & 48 & 116 & 7.8 & 18.0 & 140.4& 125.3\\ %\hline %336 & 42 & 40 & 6.9 & 6.6 & 54.0 & 37.8 \\ %336 & 24 & 58 & 4.2 & 9.3 & 47.5 & 31.3 \\ %\hline %448 & 112 & 108 & 17.4 & 16.8 & 292.3& 272.2\\ %448 & 84 & 136 & 13.2 & 21.0 & 277.2& 257.0\\ %\hline %448 & 56 & 54 & 9.0 & 8.7 & 89.3 & 68.0 \\ %448 & 42 & 68 & 6.9 & 10.8 & 85.5 & 64.3 \\ %\hline %\end{tabular} %\end{Table} %The pin availability analysis assumes the common perimeter-based IO %structure (a pad ring). Although area-based interconnect technologies such %as C4 are available, they are still a premier, higher-cost technology. %One of the problems with a perimeter-based organization is that it can %become \emph{pad-limited}, where the rectangle formed by the pads is larger %than the computing function of the chip. This problem can be ameliorated %by the use of double-ring structure, as used in the Abacus-1 chip. Finally, %the analysis assumes that low-parasitic structures like the ball-grid array %(or BGA) will become standard. %%% Local Variables: %%% TeX-master: "main" %%% comment-start: "%%% " %%% End: *** \message{ !name(main.tex) !offset(-989) } \end{document}