Kung and Leiserson's systolic arrays
In April 1978 H. T. Kung and Charles E. Leiserson of Carnegie-Mellon described systolic arrays: a network of identical processors through which data flow rhythmically, as blood through the heart, each processor doing one inner product step per beat. A hexagonal grid of w1w2 processors multiplies two n x n band matrices in 3n+min(w1, w2) units of time.
Why it matters
The work showed how to build cheaply on a chip a device that multiplies matrices without reading memory for every operation: data enter once and pass through the whole grid. It is the work Google's 2017 paper cites when it explains why the TPU's matrix unit is systolic.
According to report CMU-CS-79-103, a linear array of w processors computes a band matrix-vector product in 2n+w time units against O(wn) on a single processor, and the LU-decomposition of a dense n x n matrix takes 4n units on n^2 processors, input and output included. The arrays are linear, orthogonal or hexagonal, and the size of each depends only on the band width, not on the length of the matrix. The report concludes that a systolic device connected to a standard von Neumann computer provides inexpensive but massive computation power. In the 1982 article Why Systolic Architectures? Kung illustrates the principle: one processing element at 100 ns gives at most 5 million operations a second, six in an array on the same memory 30 million. The TPU's matrix unit, by the 2017 paper, holds 256 x 256 multiply-accumulators. What the record does not claim: in which volume and on which pages of the 1979 SIAM proceedings the paper appeared; the volume itself was not found.