Stream Algorithms and Architecture
Volker Strumpen, Henry Hoffmann, Anant K. Agarwal · 2003
Wire delay and power consumption are primary obstacles to the continued scaling of microprocessor performance. Fundamentally, both issues are addressed by the emerging breed of singlechip, tiled microarchitectures including Raw [1], Trips [2], Scale [3], Wavescalar [4], and Synchroscalar [5], that replicate programmable processing elements with small amounts of memory and communicate via on-chip networks characterized by extremely low latencies and high bandwidth. Our goal is to show that tiled microarchitectures permit energy-efficient high-performance computations when algorithms are mapped properly. To that end, we propose a decoupled systolic architecture as a canonical tiled microarchitecture that supports the resource requirements of decoupled systolic algorithms designed specifically for this architecture. We develop an analytical framework for reasoning about the efficiency and performance of decoupled systolic algorithms. In particular, we define stream algorithms as a class of decoupled systolic algorithms that achieve computational efficiency asymptotically for large numbers of processors. We focus our attention on the class of regularly structured computations that form the foundation of scientific computing and digital signal processing. 1.