Introduction

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.

Watch the Data March

The demo below shows a 3×33 \times 3 systolic array computing the product C=A×BC = A \times B. Rows of matrix AA enter from the left, columns of BB 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.

<!-- Controls: step through ticks or run automatically. -->
<div class="controls">
  <button id="btn-step" type="button">Step</button>
  <button id="btn-run" type="button">Run</button>
  <button id="btn-reset" type="button" class="ghost">Reset</button>
  <span class="tick-label">Tick: <span id="tick-display">0</span></span>
</div>
<div class="matrices-row">
  <div class="mat-block">
    <div class="mat-title">Matrix A</div>
    <div class="mat-grid" id="mat-a"></div>
  </div>
  <div class="mat-block">
    <div class="mat-title">Matrix B</div>
    <div class="mat-grid" id="mat-b"></div>
  </div>
  <div class="mat-block">
    <div class="mat-title">Result C</div>
    <div class="mat-grid" id="mat-c"></div>
  </div>
</div>
<div class="array-section">
  <div class="array-label">Systolic Array (3×3 cells)</div>
  <div class="systolic-grid" id="systolic-grid"></div>
</div>
<div class="status-bar" id="status-bar">Press Step or Run to start the systolic march.</div>

/* Systolic array demo styles. */
* { 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; }
/* Input/output matrix display. */
.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; }
/* Systolic grid cell styles. */
.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; }
/* Status bar styles. */
.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; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Input matrices A and B (3x3). C = A*B is computed systolically.
const A = [[1,2,3],[4,5,6],[7,8,9]];
const B = [[9,8,7],[6,5,4],[3,2,1]];
// Precompute the expected result for verification and display.
// C[i][j] = sum_k A[i][k]*B[k][j]
const C_expected = (() => {
  const C = [[0,0,0],[0,0,0],[0,0,0]];
  for(let i=0;i<3;i++) for(let j=0;j<3;j++) for(let k=0;k<3;k++) C[i][j]+=A[i][k]*B[k][j];
  return C;
})();

// Systolic array state: accumulator per cell, done flag per cell.
// In a 3x3 systolic array for matrix multiply:
// A rows enter left-to-right, staggered by row index.
// B columns enter top-to-bottom, staggered by col index.
// Cell (i,j) accumulates A[i][k]*B[k][j] when diagonal wave k reaches it.
// Wave k arrives at cell (i,j) at tick = k + i + j.
const N = 3;
const MAX_TICK = 3*(N-1) + N; // Total ticks needed: first data arrives at tick 0, last at tick 2*(N-1)+N-1.

let tick = 0;
let running = false;
let timer = null;

// Accumulators and completion flags for each cell.
const acc = Array.from({length:N},()=>Array(N).fill(0));
const done = Array.from({length:N},()=>Array(N).fill(false));

function getAInput(i, k) {
  // A[i][k-i] enters row i at tick k (staggered by i ticks).
  return (k >= i && k - i < N) ? A[i][k - i] : null;
}
function getBInput(j, k) {
  // B[k-j][j] enters col j at tick k (staggered by j ticks).
  return (k >= j && k - j < N) ? B[k - j][j] : null;
}

function renderMatrices(activeA, activeB) {
  // Render all three matrices, highlighting active input elements.
  ['a','b','c'].forEach(id => {
    const el = document.getElementById('mat-' + id);
    if(!el) return;
    el.innerHTML = '';
    const mat = id === 'a' ? A : id === 'b' ? B : C_expected;
    for(let i=0;i<3;i++) for(let j=0;j<3;j++){
      const d = document.createElement('div');
      d.className = 'mat-cell';
      if(id === 'a' && activeA && activeA[i] === j) d.classList.add('active');
      if(id === 'b' && activeB && activeB[j] === i) d.classList.add('active');
      if(id === 'c') { const v = acc[i][j]; d.textContent = done[i][j] ? v : (v > 0 ? v : ''); if(done[i][j]) d.classList.add('active'); }
      else d.textContent = mat[i][j];
      el.appendChild(d);
    }
  });
}

function renderGrid(waveK) {
  // Render the systolic grid, marking active and completed cells.
  const grid = document.getElementById('systolic-grid');
  grid.innerHTML = '';
  for(let i=0;i<N;i++) for(let j=0;j<N;j++){
    const cell = document.createElement('div');
    cell.className = 's-cell';
    const lbl = document.createElement('div');
    lbl.className = 's-cell-label';
    lbl.textContent = 'C' + (i+1) + (j+1);
    cell.appendChild(lbl);

    const aVal = getAInput(i, waveK - j);
    const bVal = getBInput(j, waveK - i);
    const contributing = (aVal !== null && bVal !== null);

    const accDiv = document.createElement('div');
    accDiv.className = 's-cell-acc';
    accDiv.textContent = acc[i][j];

    const inpDiv = document.createElement('div');
    inpDiv.className = 's-cell-inputs';

    if(contributing){
      cell.classList.add('active');
      inpDiv.textContent = 'a=' + aVal + ' b=' + bVal;
    } else if(done[i][j]){
      cell.classList.add('done');
      inpDiv.textContent = '= ' + C_expected[i][j];
    }

    cell.appendChild(accDiv);
    cell.appendChild(inpDiv);
    grid.appendChild(cell);
  }
}

function step() {
  if(tick >= MAX_TICK) return;
  // Advance one tick: apply diagonal wave, update accumulators.
  // diagonal wave index = tick; wave k hits cell (i,j) when i+j+k == tick => k = tick-i-j
  const waveK = tick;
  const activeA = {};
  const activeB = {};
  for(let i=0;i<N;i++) for(let j=0;j<N;j++){
    const k = waveK - i - j;
    if(k >= 0 && k < N){
      const aVal = A[i][k];
      const bVal = B[k][j];
      acc[i][j] += aVal * bVal;
      activeA[i] = k;
      activeB[j] = k;
    }
    // Mark cell done when its accumulator has reached the expected value.
    if(acc[i][j] === C_expected[i][j] && tick >= i + j + N - 1) done[i][j] = true;
  }
  tick++;
  document.getElementById('tick-display').textContent = tick;
  renderMatrices(activeA, activeB);
  renderGrid(waveK);
  updateStatus(waveK);
  if(tick >= MAX_TICK){
    stopRun();
    document.getElementById('status-bar').textContent = 'Done! Every cell has computed its share of C = A × B.';
    document.getElementById('status-bar').className = 'status-bar done';
  }
}

function updateStatus(waveK) {
  const bar = document.getElementById('status-bar');
  bar.className = 'status-bar';
  bar.textContent = i18nFmt('Tick %tick% — diagonal wave %wave% passing through the array.', { tick: tick, wave: waveK });
}

function startRun() {
  if(running) return;
  running = true;
  document.getElementById('btn-run').textContent = 'Pause';
  document.getElementById('btn-step').disabled = true;
  timer = setInterval(()=>{ step(); if(tick >= MAX_TICK) stopRun(); }, 600);
}
function stopRun() {
  running = false;
  clearInterval(timer);
  timer = null;
  document.getElementById('btn-run').textContent = 'Run';
  document.getElementById('btn-step').disabled = false;
}
function reset() {
  stopRun();
  tick = 0;
  for(let i=0;i<N;i++) for(let j=0;j<N;j++){ acc[i][j]=0; done[i][j]=false; }
  document.getElementById('tick-display').textContent = 0;
  renderMatrices(null, null);
  renderGrid(-1);
  const bar = document.getElementById('status-bar');
  bar.className = 'status-bar';
  bar.textContent = 'Press Step or Run to start the systolic march.';
}

document.getElementById('btn-step').addEventListener('click', step);
document.getElementById('btn-run').addEventListener('click', ()=>{ running ? stopRun() : startRun(); });
document.getElementById('btn-reset').addEventListener('click', reset);

// Initialize display on load.
renderMatrices(null, null);
renderGrid(-1);
Result
Console

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.

The Real Complexity

Matrix multiplication of two n×nn \times n matrices requires n3n^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 Cij=∑k=1nAik⋅BkjC_{ij} = \sum_{k=1}^{n} A_{ik} \cdot B_{kj}, you read a full row of AA and a full column of BB from memory for every output element. Memory bandwidth becomes the bottleneck.
  • Systolic schedule: each element of AA enters a row of cells once and flows rightward; each element of BB enters a column once and flows downward. Every cell accumulates a running partial sum. Total memory reads: O(n2)O(n^2) instead of O(n3)O(n^3).
  • Time complexity: on an n×nn \times n grid, the full product appears in O(n)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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/systolic-arrays/Content licensed under CC BY-NC 4.0.