Систолічні масиви Кунга й Лейзерсона
У квітні 1978 року Г. Т. Кунг і Чарлз Лейзерсон з Карнегі-Меллона описали систолічні масиви: мережу однакових процесорів, крізь яку дані ритмічно течуть, як кров крізь серце, і кожен процесор на кожному такті робить один крок скалярного добутку. Шестикутна решітка з w1·w2 процесорів множить дві смугові матриці n×n за 3n+min(w1, w2) тактів.
Чому це важливо
Робота показала, як дешево зібрати на кристалі пристрій, що множить матриці, не читаючи пам'ять на кожну операцію: дані заходять раз і проходять крізь усю решітку. Саме на цю роботу посилається стаття Google 2017 року, коли пояснює, чому матрична одиниця TPU систолічна.
За звітом CMU-CS-79-103, добуток смугової матриці на вектор лінійний масив із w процесорів дає за 2n+w тактів проти O(wn) на одному процесорі, а LU-розклад щільної матриці n×n на n² процесорах займає 4n тактів разом із введенням і виведенням. Масиви лінійні, прямокутні або шестикутні, і розмір кожного залежить лише від ширини смуги, а не від довжини матриці. Висновок звіту: систолічний пристрій, приєднаний до звичайної машини фон Неймана, дає недорогу, але величезну обчислювальну потужність. У статті 1982 року «Why Systolic Architectures?» Кунг ілюструє принцип так: один процесор із тактом 100 нс дає щонайбільше 5 мільйонів операцій на секунду, шість у масиві з тією самою пам'яттю — 30 мільйонів. Матрична одиниця TPU, за статтею 2017 року, має 256×256 помножувачів-суматорів. Чого запис не стверджує: у якому томі й на яких сторінках матеріалів SIAM 1979 року вийшла доповідь — самого тому не знайдено.