Stream Processors 2
Stream processing aims to create hardware that matches the strengths of VLSI, by having parallel execution units and taking advantage of parallelism and locality inherent in data parallel programs. Minimal hardware resources are dedicated to control and scheduling and much of the responsibility of taking advantage of parallelism, locality and scheduling are pushed up to the software.
Figure 1: Software pipelining allows bulk loads and store to proceed in parallel with computation.
Bulk operations allows us to design hardware that seeks to tolerate rather than reduce latencies. In the figure above, software pipelining of computation and I/O operations allows I/O and compute to proceed in parallel, hiding latencies. The stream model is characterized by bulk operations of medium granularity, predictable sequence of bulk operations to allow latency hiding, hierarchical control, locality within kernels and producer-consumer reuse between kernels. Multiple kernels may be allowed to execute in parallel, in order to take advantage of all available hardware resources.
Figure 2: Architecture of a merrimac node.
The Merrimac architecture decouples the unpredictable I/O latencies of the DRAM by providing SRF (stream register file). The SRF can be likened to a (reasonably) fast scratchpad memory. Data is brought into the SRF through bulk loads and the execution units access their data only from the SRFs. Thus it affords (almost) fixed latencies for the PEs. This in turn allows for more efficient scheduling of instructions, simplifying the hardware and also making the job easier for the compiler. Accessing SRF of a remote cluster requires the use of an inter-cluster switch, resulting in longer latencies than accessing the local SRF.
Compute Cluster of Merrimac
The compute cluster of the Merrimac architecture tries to take advantage of DLP, ILP and TLP. Each PE in Merrimac consists of multiple FPUs (DLP) organized in VLIW fashion (ILP). The FPUs are connected to each other using a crossbar. The crossbar is organized in a hierarchical fashion in order to save on area – the area cost of allowing complete communication between all FPUs to all other FPUs will be prohibitively large. The instruction sequencer is responsible for sending instructions to multiple PEs. Multiple PEs are grouped bound to a single instruction sequencer, and having multiple such sequencer groups allows for each to run different kernels (TLP). This hardware is optimized for static scheduling by decoupling memory and instructions and the compiler tries to optimize VLIW kernel scheduling in order to overlap memory and compute operations.
Figure3: Multiple clusters of FPUs. Each cluster shares a common instruction sequencer for SIMD and multiple clusters are organized as MIMD. This allows the programmer to take advantage of DLP and TLP. Note the hierarchical cluster crossbar connecting FPUs.
The Merrimac is designed for throughput oriented applications, with weak scaling, for both regular and irregular applications and almost static data sets. It tries to exploit DLP via SIMD (instead of short vectors like SSE), VLIW instead of OoO, MIMD instead of SMT.
Figure4: Heat Map illustrating the optimal configuration of FPUs per cluster and number of clusters.
The heatmap in figure 4 shows the tradeoffs involved between having large number of FPUs per cluster to take advantage of ILP, versus having more clusters to leverage DLP. Having a large number of clusters and FPUs per cluster is not a good idea as it results in large area overhead of the switch. The white region shows the optimal organization for the architecture. Accordingly, Merrimac is designed to have 16 clusters with 4 FPUs per cluster.
Figure 5: Normalized runtimes of benchmarks for various compute node configurations.
Figure 5 plots relative runtime of applications for various configurations. The values in parentheses denote the number of Merrimac nodes, number of clusters and number of FPUs per cluster respectively. The graphs are normalized to a baseline configuration of a single Merrimac node. It is observed that for most of the benchmarks, the baseline configuration is the best or very close to the best case, validating the above observation.
Shared Register File (SRF)
The SRF is organized as a single ported memory to allow efficient wide access of 4 contiguous words. It is implemented using sub-arrays to reduce access time and power. The SRF is decoupled from the execution units through the use of stream buffers, which time-multiplex the SRF port. The Merrimac architecture has 16 stream buffers to match SRF bandwidth to compute requirements. The SRF is indexed with 8:1 mux in sub-arrays and a row-decoder per sub-array. Instead of shared decoders, this allows for independent access of sub-arrays. This structure affords better read and write bandwidths for irregular, short accesses or unaligned accesses. This is illustrated in figure 6.
Figure 6: SRF organized with independent sub-array access. Address FIFOs are used to time-multiplex independent accesses.
The SRF is organized as multiple SRAM sub-arrays. Each SRAM cell consists of two inverters in a positive feedback loop, plus a transistor each for read and write (6T per cell for a single read, single write port cell). Multiple cells share common bit-lines (column select) which in turn are connected to sense-amps. To read, the bit-lines are precharged and the word-line connects the cross-coupled inverters to the bit-line. A zero on the inverter would cause the bit-line to discharge quicker than if it were 1, and this is captured by the sense amps.
Streaming Memory Systems
DRAMs are sensitive to memory access patterns. In general, contiguous memory reads or writes are much faster than random access. The reasons for these will be elaborated upon in a future lecture on DRAM memories, but suffice to say that this results from DRAM manufacturers’ need to maximize DRAM cell density, due to which a number of resources like the row decoder are heavily shared.
Figure 7: Effect of access patterns on bandwidth utilization.
In figure 7, a X b implies a contiguous accesses separated by a stride of b. Inorder implies sequential access, row implies all accesses are optimized to be in the same row as far as possible while row+col tries to optimize both row and column access sequences. The graph clearly indicates that for non-contiguous accesses, bandwidth utilization is pretty poor. This improves as we optimize for row and row+column accesses. The following figure shows the improvement in peak bandwidth for a few streaming friendly applications achieved through the use of row and row+col level optimizations.
Figure8: Effect of access patterns on peak memory bandwidth for a set of streaming workloads.
