Systolic Arrays

Picture a factory floor where parts flow on a conveyor belt, and each worker along the belt performs one small operation before passing the piece to the next. Nobody waits. Nobody repeats work. Everything moves in lockstep to a single beat.

That is the essence of a systolic array: a grid of tiny, identical processor cells connected to their neighbors, through which data streams rhythmically — like blood pulsed through a heart. Each cell does one simple operation (typically a multiply-and-add) every clock tick, and the results accumulate as data flows.

The idea was invented by H. T. Kung and Charles Leiserson in 1978 at Carnegie Mellon. Their original goal was matrix multiplication, the one operation that sits at the center of nearly all numerical computing, graphics, and — decades later — deep learning. Today, Google's Tensor Processing Unit (TPU) is essentially a massive systolic array, and so are the inference engines inside almost every AI accelerator on the market.

The demo below shows a $3 \times 3$ systolic array computing the product $C = A \times B$. Rows of matrix $A$ enter from the left, columns of $B$ enter from the top — each staggered by one clock tick so they meet at exactly the right cell at the right moment. Press Step to advance one tick, or Run to let it play automatically.

<!-- {{c_html_intro}} -->
<div class="controls">
  <button id="btn-step" type="button">{{btn_step}}</button>
  <button id="btn-run" type="button">{{btn_run}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
  <span class="tick-label">{{lbl_tick}} <span id="tick-display">0</span></span>
</div>
<div class="matrices-row">
  <div class="mat-block">
    <div class="mat-title">{{lbl_matrix_a}}</div>
    <div class="mat-grid" id="mat-a"></div>
  </div>
  <div class="mat-block">
    <div class="mat-title">{{lbl_matrix_b}}</div>
    <div class="mat-grid" id="mat-b"></div>
  </div>
  <div class="mat-block">
    <div class="mat-title">{{lbl_matrix_c}}</div>
    <div class="mat-grid" id="mat-c"></div>
  </div>
</div>
<div class="array-section">
  <div class="array-label">{{lbl_array}}</div>
  <div class="systolic-grid" id="systolic-grid"></div>
</div>
<div class="status-bar" id="status-bar">{{msg_ready}}</div>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #1a2535; background: #f4f7fa; }
.controls { display: flex; align-items: center; gap: .5rem; flex-wrap: wrap; padding: .6rem .8rem; background: #fff; border-bottom: 1px solid #dde3ea; }
button { font: 600 13px system-ui; padding: .35rem .8rem; border: 1px solid #2c5282; background: #2c5282; color: #fff; border-radius: 6px; cursor: pointer; }
button.ghost { background: #fff; color: #2c5282; }
button:disabled { opacity: .4; cursor: default; }
.tick-label { font-size: .85rem; color: #555; margin-left: auto; }
/* {{c_matrices_css}} */
.matrices-row { display: flex; gap: .8rem; padding: .7rem .8rem .4rem; flex-wrap: wrap; }
.mat-block { display: flex; flex-direction: column; align-items: center; gap: .3rem; }
.mat-title { font-size: .75rem; font-weight: 700; letter-spacing: .04em; color: #2c5282; text-transform: uppercase; }
.mat-grid { display: grid; grid-template-columns: repeat(3, 36px); gap: 3px; }
.mat-cell { width: 36px; height: 36px; display: flex; align-items: center; justify-content: center; font: 600 13px ui-monospace, monospace; border-radius: 5px; background: #e8eef6; border: 1px solid #c5d2e0; color: #1a2535; transition: background .25s; }
.mat-cell.active { background: #bee3f8; border-color: #4299e1; }
/* {{c_systolic_css}} */
.array-section { padding: .4rem .8rem .6rem; }
.array-label { font-size: .75rem; font-weight: 700; letter-spacing: .04em; color: #2c5282; text-transform: uppercase; margin-bottom: .5rem; }
.systolic-grid { display: grid; grid-template-columns: repeat(3, 72px); gap: 6px; }
.s-cell { width: 72px; height: 72px; display: flex; flex-direction: column; align-items: center; justify-content: center; border-radius: 8px; background: #fff; border: 2px solid #c5d2e0; transition: all .2s; position: relative; }
.s-cell.active { border-color: #4299e1; background: #ebf8ff; }
.s-cell.done { border-color: #48bb78; background: #f0fff4; }
.s-cell-acc { font: 700 15px ui-monospace, monospace; color: #2c5282; }
.s-cell-inputs { font: 500 10px ui-monospace, monospace; color: #718096; margin-top: 2px; }
.s-cell-label { position: absolute; top: 3px; left: 5px; font: 600 9px system-ui; color: #a0aec0; }
/* {{c_status_css}} */
.status-bar { padding: .5rem .8rem; font-size: .88rem; font-weight: 600; color: #2c5282; min-height: 1.8em; background: #fff; border-top: 1px solid #dde3ea; }
.status-bar.done { color: #276749; }

// Code not found

Notice that no cell ever fetches data from far away: each only talks to its immediate neighbors. This locality is the key to why systolic arrays scale so well in hardware — wires stay short, power stays low, and thousands of cells can run in parallel without a traffic jam.

Matrix multiplication of two $n \times n$ matrices requires $n^3$ multiply-add operations — a solved problem algorithmically, but one whose constants matter enormously at scale.

The systolic insight is about data reuse, not algorithmic novelty:

• Naive implementation: to compute entry $C_{ij} = \sum_{k=1}^{n} A_{ik} \cdot B_{kj}$, you read a full row of $A$ and a full column of $B$ from memory for every output element. Memory bandwidth becomes the bottleneck.
• Systolic schedule: each element of $A$ enters a row of cells once and flows rightward; each element of $B$ enters a column once and flows downward. Every cell accumulates a running partial sum. Total memory reads: $O(n^2)$ instead of $O(n^3)$.
• Time complexity: on an $n \times n$ grid, the full product appears in $O(n)$ clock ticks — optimal, since you cannot do better than one tick per diagonal wave.
• The tradeoff: the design is inflexible. The wiring is hardcoded for one computation pattern. Changing the algorithm means redesigning the chip — which is exactly why TPUs are fast at neural network training but not at arbitrary code.

This is a recurring theme in computer architecture: specialization buys speed, but costs generality. A systolic array is the extreme point of that tradeoff: maximally parallel, maximally specialized.

Any computation that fits the rhythm of a systolic array runs dramatically faster than on a general-purpose CPU:

• Deep learning inference and training: every layer of a neural network is a matrix multiply (or a convolution, which is also a matrix multiply in disguise). This is why Google built the TPU, and why every competitor has followed with custom matrix-multiply hardware.
• Image and signal processing: convolution filters, FFTs, and FIR filters all map cleanly onto systolic schedules — the same sliding-window structure that makes convolutions fast on a GPU.
• Sequence alignment in genomics: the Smith-Waterman dynamic-programming algorithm fills a 2-D table cell by cell with a dependency pattern that maps exactly onto a systolic array. Early DNA sequencing accelerators used this directly.
• Cryptography: modular exponentiation for RSA and elliptic-curve arithmetic involve repeated multiply-and-reduce steps that can be pipelined systolically.

The common thread is a regular, repetitive arithmetic pattern with local data dependencies. Wherever that appears, a systolic array can replace a general processor and gain orders of magnitude in throughput. Learn more about why some problems fit hardware so well in P vs NP, or see how neural networks exploit this in neural network training.

A systolic array is deceptively simple: a grid of cells, each doing one multiply-add per tick, each passing data to its neighbor. Yet that simplicity, applied at the scale of billions of transistors, produces the fastest matrix-multiply engines ever built.

The next time you ask an AI model a question, the answer flows back through a systolic array somewhere in the data center — data marching in lockstep, cell by cell, tick by tick, exactly as Kung and Leiserson imagined in 1978. Not every idea in computer science needs to be complicated to be profound.