()

Stream Processors - Introduction

Due to the advancements in technology large number of devices can be placed on a single chip. For example, over 200 FPUs can be placed in a die of size 12mm X 12mm. In spite of having cheap computation power, this potential could not be exploited to the full extent because of bandwidth limitations. Sustaining operand and instruction throughput for a large number of FPUs is challenging since the BW is inversely proportional to the distance that the information has to traverse. The main idea behind stream processors is to use locality, parallelism, and a throughput-oriented design to maximize efficiency in terms of power and bandwidth usage. The goal is to design an architecture that can exploit the software characteristics and match them with the strengths of modern VLSI standards.

How to achieve both programmability and efficiency in a stream processor?

  1. Parallelism - Due to recent trends in the advancements in VLSI, we can have lots of FPs in a single die as discussed in the previous section
  2. Locality - Partitioning and hierarchical control to improve bandwidth
  3. Bandwidth management - Exposed communication and we make a throughput-oriented design
  4. Support stream execution model (bulk kernels and stream loads/stores) - Can overlap bulk operations to hide latency.

Parallelism and Locality

A stream program consists of a set of computation kernels with streams of data between them. A stream program exposes both parallelism and locality.

  • DLP - each element of the input stream can be processed independently thus exposing large amount of data level parallelism.
  • ILP - ILP can be exploited within kernels by executing many independent in parallel. VLIW is one way of exploiting ILP with the help of software and pipelining is another way.
  • TLP - each kernel can execute in parallel, operating on the streams in a pipelined fashion.

A stream program exposes two kinds of locality

  • Kernel Locality - While executing a kernel, all references are to variables within a kernel except for the accesses to the input streams
  • Producer-Consumer Locality - Since streams flow between kernels, the values are consumed immediately after they are produced. Therefore the elements of intermediate streams can be kept locally thus improving bandwidth.

Stream Execution Model

Given below are some of the characteristics of the stream execution model

  • Predetermined sequence of data access - Data access is determined well in advance. This “well in advance” knowledge of data sequences can be used in
- Hiding latencies (amortize the latency of accessing a global or local cache)
- Blocking (can exploit locality by making a data stay in the cache for a long time)
- SWP things in order to hide dependencies
  • Bulk operations - Bulk operations are good for hardware. There is a potential to exploit memory level parallelism (independent memory accesses to improve parallelism). Block phases into bulk operations instead of operating on single data - here we take advantage of the software. We seek the help of software to group things to these bulk operations and reformulate into gather-compute-scatter operations. There is also a potential scope of overlapping the three operations thus reducing latency. By the time a gather operation gets over and a compute starts, a gather for the next iteration starts.
  • Hierarchical control - We have a hierarchical control over the block of data. This greatly simplifies control and is also efficient. An analogy can be drawn from blocks and warps in a GPU. So the thread scheduler at the top only has to deal with blocks instead of individual threads.
  • Locality - The kernel cannot make arbitrary loads. Only data that has been explicitly gathered can be used. We are explicitly defining locality here.
  • A stream program is positively constrained - blocks should be independent of each other. For example, there should be no loop-carried dependencies between blocks (but dependencies are allowed between kernels).

Summary of stream execution model

  1. We code so that we have medium grained bulk operations
  2. We operate on data where we have a predictable sequence of bulk opedrations
  3. Hierarchical control - inter/intra block
  4. Throughput oriented design
  5. Locality and parallelism is expressed in terms of kernel locality, producer-consumer reuse and parallelism within kernels

Implications of the stream execution model on software

Software is given more explicit control over the execution of the program by the following operations

  • explicit hierarchical scheduling and latency hiding
  • explicit parallelism
  • explicit locality management

Stream Processor - Architecture

The above figure shows the architecture of the merrimac stream processor. The FPUs require data at the rate of 3840 GB/s. The available DRAM bandwidth is less than 64 GB/s. Merrimac bridges this gap by having a bandwidth hierarchy (hierarchical storage structure).

  • LRF (local register file) provides the necessary BW since we have them located very close to the FPUs so that minimum energy is spent by traversing short wires, thus providing producer-consumer locality. Comparing with the GPUs, in a G80, each SP has its own set of registers.
  • Clustering exploits kernel locality and enables efficient instruction supply. VLIW can be exploited within
  • SRF (stream register file) reduces off-chip BW requirements thus enabling latency tolerance. The SRF can be compared to the shared memory of the G80. Unlike the G80 there are no explicit banks in the SRF.
  • Intercluster switch helps in transferring data from one cluster to another and thus breaks strict SIMD allowing more flexibility when programming. FPUs from one cluster can communicate with the FPUs of another cluster directly. Data can be exchanged to handle irregular rate streaming for example without need to utilize the memory system.
  • The cache banks are mainly used in improving bandwidth. The cache banks can be bypassed if not needed. The cache banks are not tied to a particular cluster. The intercluster switch helps clusters to access different cache banks.
  • DRAM - The DRAM latencies are highly dependent on the type of access patterns. So bulk accesses can be rearranged to reduce DRAM access latencies.

Impact on software model

  1. A gather-compute-scatter programming model enables decoupling of the unpredictable and the static latencies part of the architecture. This enables having separate address spaces and an efficient static architecture. Now code can be written so that it will load it from the SRF, LRF or memory explicitly. Before the FPUs start the compute, it is made sure that the data is resident in the SRF. Since the latency of a SRF access can be easily predicted, the software can statically schedule instructions and also control over the cluster-switch.
  2. The two parts of the decoupled architecture can be thought of as a staging area for bulk operations (bulk ld/st, bulk computations). The GPP core can dispatch bulk operations to the stream processor and continue with its scalar operations. These bulk operations include both kernels in the compute clusters and stream loads and stores handled by the memory system. This helps software hide the latency of memory operations through coarse-grained software pipelining of bulk operations.

Note: This is similar to the thread scheduler in the GPU which just dispatches blocks to SMs thus making the process very simple. Instead of giving every instruction, the GPP gives one bulk instruction to the stream processor thus simplifying the scheduling process further.

Conclusion

Stream Processors are flexible, energy-efficient and provide high performance. The next lecture throws more light into the architecture of compute cluster, SRF, and the stream memory model.

References

  1. Dally, WL , Kapasi, UL , Khailany, B. , Ahn, JH and Das, A. (2004) Stream processors- Programmability with efficiency. Queue, 2(1):52–62.
  2. Erez, M. (2007) MERRIMAC—HIGH-PERFORMANCE AND HIGHLY-EFFICIENT SCIENTIFIC COMPUTING WITH STREAMS. PhD thesis, STANFORD UNIVERSITY