Chapter 1

Analytical Modeling

1.1 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.

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 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.

Parameter Value Description
A_{alu}  8  ALU area, in units of SRAM cells
A_{ovr}  10  Overhead area, in units of SRAM cells
f_{A}  0.9  Fraction of operations affected by wider datapath
T_{mem}  3 ns Register file access time
T_{alu}  0.7 ns ALU datapath bit delay
T_{ovr}  1.0 ns Timing overhead

Table 1.1: Analytical Model Parameters from the Abacus-1 Implementation.

1.1.1 Ideal Model

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.

A_{pe}(k) = N_{mem} + kA_{alu} + A_{ovr}  (1.1)

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.

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.

T_{pe}(k) = 2T_{mem} + kT_{alu} + T_{ovr}  (1.2)

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.

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.

P_{pe}(k) = k  (1.3)

Quality Metric. The effectiveness of a PE is expressed as the number of operations per unit area per unit time.

Q_{ideal}(k) = \frac{k}{A_{pe}T_{pe}} = \frac{k}{(N_{mem} + kA_{alu} + A_{ovr})(2T_{mem} + kT_{alu} + T_{ovr})}  (1.4)

This function is plotted in Figure 1-1. 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.

Figure 1-1: 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.

The next observation comes from normalizing the performance to the bit-serial case (k = 1). Figure 1-2 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.

1.1.2 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:

S_{a}(k) = \frac{1}{\frac{f_{A}}{S} + (1 − f_{A})}  (1.5)

Figure 1-2: Normalized Ideal Performance. This shows the relative advantage of the wide datapath over the bit-serial case.

where f_{A} is the fraction of the computation affected by the speedup S, and S_{a} is the actual obtained speedup. Thus,

Q_{a}(k) = \frac{S_{a}}{A_{pe}T_{pe}}  (1.6)

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 [?] explicitly listed f_{A} for a variety of algorithms, as in Table 1.2. The obtained values are slightly higher than expected for vision algorithms, as most of the listed algorithms are dominated by floating point manipulations.

Herbordt’s [?] 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

Program  f_{A}
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

Table 1.2: Fraction of Operation Costs Affected by Data Path Width. From [?]

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 Table 1.3. 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.

Program  f_{A}
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

Table 1.3: Fraction of Operation Costs Affected by Data Path. From [?]

The same configurations as in the ideal case but with Amdahl’s-law correction are shown in Figure 1-3. 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.

The normalized equations behave similarly to the ideal case, except that maxima now become apparent. Figure 1-4 also shows that the relative overall advantage of wider paths decreases from a former peak of 4.5 to 3.

The effect of varying f_{A} is shown in Figure 1-5. 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.

6 CHAPTER 1. ANALYTICAL MODELING

Figure 1-3: Amdahl-corrected quality values. Figure 1-4: Normalized Amdahl-corrected quality values 1.1. OPTIMAL BIT WIDTH ANALYSIS 7

Figure 1-5: Normalized quality vs k and f_{A}

1.1.3 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 Table 1.4.

Name  Width  Cycle Initial Data Rate Address
(max) Frequency Latency  Line
(MHz)  (ns) bits/pin/ns Overhead
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

Table 1.4: Contemporary Memories

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 [?] 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 Table 1.5.

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

Configuration  Pins Pins  BW  Latency
Total Signal bits/ns initial data total
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

Table 1.5: Latencies of Memories

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:

T_{l} = \frac{w}{PE bandwidth} = \frac{w}{A_{pe}B}  (1.7)

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:

D_{io} = \frac{T_{s}}{T_{s} + T_{l}}  (1.8)

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.

T_{s} = (\frac{1}{f_{miss}} ) T_{pe} \frac{w}{kS_{a}}  (1.9)

An interesting effect is shown in Figure 1-6. 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.

10 CHAPTER 1. ANALYTICAL MODELING Figure 1-6: 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

D_{io} = (1 + \frac{T_{l}}{T_{s}} )^{−1}  (1.10)
= (1 + \frac{\frac{w}{A_{pe}B}}{\frac{T_{pe}w}{f_{miss}} kS_{a}} )^{−1}  (1.11)
= (1 + \frac{fkS_{a}}{A_{pe}BT_{pe}} )^{−1}  (1.12)
= (1 + \frac{fQ_{a}}{B} )^{−1}  (1.13)

The performance degradation due to off-chip accesses therefore has a simple form:

D_{io} = \frac{1}{1 + ρQ_{a}}  (1.14)

where ρ = f/B. Thus,

Q_{io} = Q_{a}D_{io} = \frac{Q_{a}}{1 + ρQ_{a}}  (1.15)

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.

Figure 1-7: IO-derated Quality Metrics

This effect can be seen in Figure 1-7. At high Q_{a} values, Q_{io} begins to approach \frac{1}{ρ}.

12 CHAPTER 1. ANALYTICAL MODELING Figure 1-8: IO-derated Quality Metrics (m=64,256))

1.1.4 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:

Teff = max(0, T_{l} − T_{s})  (1.16)

and the derating factor becomes

D_{back} = \frac{T_{s}}{T_{s} + Teff}  (1.17)

Figure 1-9: Performance improvement due to background loading.

The derating reduction improvement due to prefetching is shown in Figure 1-9. 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.

Figure 1-10: Absolute performance, background loading.

Interesting effects can also be seen in the absolute performance curves in Figure 1-10.

Prefetching is so effective that performance saturates at the memory bottleneck. A twodimensional version of this plot is shown in Figure 1-11.

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.

D_{back} = \frac{T_{s}}{T_{s} + (T_{l} − T_{s})} = \frac{T_{s}}{T_{l}} = \frac{1}{ρS_{a}}  (1.18)

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:

• 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.

• 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.

Figure 1-11: Prefetching-derated quality metrics

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 Figure 1-11, 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.

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:

P (N = k) = (1 − p)^{k−1}p  (1.19)

This distribution is shown in Figure 1-12. 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 Figure 1-12: 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.

expected value of T is:

E[T] = ∑_{k=1}^{L} q^{k−1}p(L − k) = \frac{( 1 − p)^{L} + p L − 1}{p}  (1.20)

1.1.5 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.

1.2 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 Figure 1-13: 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.

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.