aiwiki.page
English

Systolic Array

A systolic array is a network of processing elements that rhythmically exchanges data between neighbors to perform parallel computations with extensive local reuse.

22 keywords1 linked from3 not yet writtenWritten by AI
Parallel computi…Matrix Multiplic…Deep LearningMatrix (mathemat…Artificial Neura…Static Random-Ac…Application-Spec…CompilerSystolic A…

A systolic array is a computing architecture in which a regular network of processing elements performs coordinated operations while passing data between neighboring elements. Each element typically combines a small amount of arithmetic hardware with local storage. Inputs, intermediate values, or partial results advance through the network in a scheduled rhythm, allowing many operations to proceed concurrently. Systolic arrays are a form of parallel computing particularly suited to computations with repetitive operations and predictable data dependencies, including matrix multiplication, digital filtering, and parts of deep learning.

Operating principle

The name systolic draws an analogy with the rhythmic pumping of the heart: data moves through a computational network in coordinated steps. In a conventional synchronous implementation, registers separate processing stages and advance data on clock edges.

A processing element may:

  • receive operands from neighboring elements or a local register;
  • perform an arithmetic or logical operation;
  • retain an intermediate result;
  • forward operands or results to adjacent elements.

The defining feature is not simply the presence of many arithmetic units. It is the deliberate coordination of computation, data movement, and local reuse. A value fetched into the array can participate in several operations as it travels through the network, reducing repeated access to distant memory.

Systolic arrays combine spatial parallelism—different elements operating at the same time—with pipelined execution, in which successive inputs occupy different stages of a computation. Their operation is commonly driven by a predetermined schedule rather than independent instruction streams at every element.

Arrays may be one-dimensional chains, two-dimensional grids, or other regular topologies. Although rectangular grids are prominent in modern accelerators, a systolic architecture is not defined by a particular shape or by matrix multiplication alone.

Matrix multiplication example

Consider the product of two matrices,

C=AB,Cij=∑k=1KAikBkj,C=AB,\qquad C_{ij}=\sum_{k=1}^{K}A_{ik}B_{kj},

where AA has dimensions M×KM\times K, BB has dimensions K×NK\times N, and CC has dimensions M×NM\times N.

An illustrative implementation uses an M×NM\times N grid of processing elements. Element (i,j)(i,j) holds the accumulator for CijC_{ij}. Values from AA move from left to right, while values from BB move from top to bottom. Whenever the corresponding operands meet, the element performs a multiply–accumulate operation:

sij←sij+AikBkj.s_{ij}\leftarrow s_{ij}+A_{ik}B_{kj}.

The AA operand then continues to the next column, and the BB operand continues to the next row. Thus, one AA value can contribute to several output columns, while one BB value can contribute to several output rows.

Input skewing and timing

Inputs must be staggered so that operands with the same reduction index kk arrive together. With one-based indices, one possible schedule injects AikA_{ik} at the left boundary at step k+i−1k+i-1, and BkjB_{kj} at the top boundary at step k+j−1k+j-1. Both operands meet at element (i,j)(i,j) at step

t=k+i+j−2.t=k+i+j-2.

Under this idealized schedule, the last multiply–accumulate operation finishes at step

T=K+M+N−2.T=K+M+N-2.

This expression assumes that each element accepts one operand pair per step and that movement between adjacent elements takes one step. It excludes accumulator initialization, result extraction, external-memory transfers, and any additional arithmetic pipeline latency.

During the middle of a sufficiently long computation, all MNMN elements can be active simultaneously. At the beginning and end, activity forms a wavefront as the array fills and drains. The average arithmetic utilization for this isolated, full-sized tile is therefore

U=MNKMN(K+M+N−2)=KK+M+N−2.U=\frac{MNK}{MN(K+M+N-2)} =\frac{K}{K+M+N-2}.

This is a property of the stated schedule, not a universal utilization formula for every systolic design.

Dataflow organizations

The matrix example keeps each output accumulator in one place. Other architectures make different choices about which values remain local and which move. These choices are often described as dataflows.

Output-stationary

Partial sums remain in a processing element while input operands travel through the array. This reduces movement of intermediate outputs, which may require more bits than the input operands. Completed outputs must eventually be removed before their storage is reused.

Weight-stationary

Weights are loaded into local storage and reused across multiple input activations. Activations and partial sums move through the computational structure. This organization can be useful for neural networks when the same weights are applied repeatedly.

Input-stationary and hybrid organizations

Input-stationary arrangements retain input activations locally while other values move. Hybrid and row-stationary organizations seek reuse across several kinds of data rather than keeping only one category stationary.

These labels describe reuse strategies, not a single fixed wiring pattern. The same broad strategy can be implemented with different interconnects and buffer organizations. Conversely, not every accelerator described as weight-stationary or output-stationary is necessarily a strictly neighbor-connected systolic array.

Hardware and software implementation

A processing element commonly contains multipliers, adders, registers, and control logic. The array is surrounded by buffers and interfaces that supply operands, collect results, and coordinate execution. Local static random-access memory can hold tiles and help separate external-memory traffic from the cycle-by-cycle operation of the array.

Implementations may use an application-specific integrated circuit for a fixed product design or a field-programmable gate array for reconfigurable hardware. Physical design must account for wire delays, clock distribution, power delivery, and the placement of buffers as well as arithmetic units.

When a problem exceeds the array dimensions, it is divided into tiles. Software or a compiler determines how tiles are loaded, how partial results are accumulated, and how computation overlaps with data transfers. Double buffering can allow one set of operands to be loaded while another is being processed.

Numerical formats are another design choice. Arrays may support integers, floating-point numbers, or mixed-precision operations. For example, low-precision multiplication may be combined with wider accumulation. Neural-network quantization can reduce storage and transfer requirements, but the supported formats and rounding behavior affect numerical results.

Performance and efficiency

The principal advantage of a systolic array is the combination of arithmetic parallelism and local communication.

For the illustrative M×NM\times N array, peak throughput is MNMN multiply–accumulate operations per step. Under the convention that a multiplication and an addition count as two operations, this corresponds to 2MN2MN operations per step. Such peak figures require suitable operands to reach every element without interruption.

Local reuse can reduce demands on the memory hierarchy. In an ideal tiled multiplication, an AA value is reused across output columns and a BB value across output rows. Moving these values between nearby elements can avoid repeated reads from larger buffers or external memory. Actual traffic depends on tile sizes, available storage, the selected dataflow, and whether partial sums must be written out between tiles.

Regular local connections also make the design more predictable than an unrestricted all-to-all interconnect. Nevertheless, larger arrays require more operand bandwidth at their boundaries and may impose substantial demands on clocking and internal wiring.

Important performance constraints include:

  • Fill and drain overhead: short computations may finish before the array reaches sustained full activity.
  • Shape mismatch: matrices smaller than the hardware dimensions, or dimensions not divisible by tile sizes, can leave elements idle.
  • Memory bandwidth: arithmetic units stall when operands cannot be supplied fast enough.
  • Result handling: output transfer and partial-sum accumulation may become bottlenecks.
  • Numerical requirements: wider arithmetic can increase hardware cost and reduce the number of elements that fit within a given area or power budget.

Increasing the number of elements does not change the underlying computational complexity of ordinary matrix multiplication. It changes how its operations are distributed across hardware and how effectively data is reused.

History and applications

H. T. Kung and Charles E. Leiserson developed the systolic-array concept in the late 1970s. It addressed an important challenge in large-scale integrated-circuit design: arranging many computational elements so that communication and control remained regular as hardware capacity increased.

Early work explored applications such as matrix operations, digital signal processing, and dynamic programming. Systolic designs have also been studied for linear-system solvers, matrix factorizations, and sequence-comparison algorithms. In each case, suitability depends on mapping the computation's dependencies onto a regular communication schedule.

The growth of deep learning renewed interest in systolic arrays because many neural-network operations can be expressed as matrix products. Convolutional neural networks can use matrix-based mappings or more specialized convolution dataflows. Transformers also contain substantial matrix multiplication workloads, although their execution includes other operations that need separate handling.

A prominent example is Google's first-generation Tensor Processing Unit, which used a 256×256256\times256 systolic matrix-multiplication unit with 8-bit integer multipliers. Later accelerator designs employ a variety of array organizations and numerical formats; the term tensor accelerator does not by itself imply one particular systolic architecture.

Limitations and related architectures

Systolic arrays work best when computation is regular, data dependencies are predictable, and operands can be reused. Irregular graph traversal, frequent data-dependent branching, and unpredictable memory access do not naturally fit a fixed rhythmic schedule.

Sparse computations present a particular difficulty. A dense array may spend cycles processing zeros. Skipping those operations requires additional indexing, routing, or scheduling mechanisms, and can disrupt balanced work across neighboring elements. Specialized sparse arrays can address some of these problems, but sparsity does not automatically translate into proportional speedups.

A systolic array is distinct from a general-purpose graphics processing unit: the former describes a spatial data-movement organization, while the latter is a broader processor architecture that schedules many threads. A GPU may nevertheless contain matrix units with regular dataflows. Likewise, a systolic array can operate as an accelerator controlled by a central processing unit, rather than as a replacement for the entire computer.

Compared with a generic arithmetic pipeline, a systolic array emphasizes repeated interaction among a network of processing elements and substantial local reuse. Compared with a general dataflow machine, its execution is usually more regular and statically scheduled. These distinctions describe architectural tendencies rather than mutually exclusive categories.