Everything about Systolic array
Type of parallel computing architecture of tightly coupled nodes
In parallel computer architectures, a systolic array is a homogeneous network of tightly coupled data processing units (DPUs) called cells or nodes. Each node or DPU independently computes a partial result as a function of the data received from its upstream neighbours, stores the result within itself and passes it downstream. The principles of systolic-like data flow were first seen in Colossus, which was an early computer used to break German Lorenz ciphers during World War II. Due to the classified nature of Colossus, they were independently invented by H. T. Kung and Charles Leiserson who described arrays for many dense linear algebra computations for banded matrices. Early applications include computing greatest common divisors of integers and polynomials. Today, they can be found in NPUs and hardware accelerators based on spatial designs. They are sometimes classified as multiple-instruction single-data (MISD) architectures under Flynn's taxonomy, but this classification is questionable because a strong argument can be made to distinguish systolic arrays from any of Flynn's four categories: single instruction, single data (SISD); single instruction, multiple data (SIMD); multiple instruction, single data (MISD); and multiple instruction, multiple data (MIMD). Wikipedia →
🧭 Start here: a 6-step reading path
- Read the overview: Systolic arrayA 5-minute orientation
- Skim a recent paper: A Survey of Design and Optimization for Systolic Array-based DNN AcceleratorsInfluential work since 2022
- Pick up a classic book: An introduction to systolic algorithm designThe most-reprinted book on the subject
- Read the landmark paper: On supercomputing with systolic/wavefront array processorsCited 211 times
- Go sideways: Multiple instruction, single dataA closely related topic
- Go sideways: Topological sortingA closely related topic
📖 Definitions
Noun In parallel computer architectures, a homogeneous network of tightly coupled data processing units (DPUs), each of which independently computes a partial result as a function of the data received from its upstream neighbors, stores the result within itself, and passes it downstream.
🏆 Landmark papers (most cited)
On supercomputing with systolic/wavefront array processors
Optical implementation of systolic array processing
QCA Systolic Array Design
Systolic array processor for MVDR beamforming
Systolic array processing of the Viterbi algorithm
A novel systolic array structure for DCT
A Systolic Array for SVD Updating
Generating Systolic Array Accelerators With Reusable Blocks
🆕 Influential since 2022
A Survey of Design and Optimization for Systolic Array-based DNN Accelerators
Accelerating Attention Mechanism on FPGAs based on Efficient Reconfigurable Systolic Array
Hybrid Accumulator Factored Systolic Array for Machine Learning Acceleration
Power-Intent Systolic Array Using Modified Parallel Multiplier for Machine Learning Acceleration
Algorithm Level Error Detection in Low Voltage Systolic Array
📚 Books worth reading
- 📕An introduction to systolic algorithm designG. M. Megson · 1992
- 📕Systolic array processorsEarl E. Swartzlander · 1989
Specification and Verification of Systolic ArraysNam Ling, Magdy A. Bayoumi · 1999- 📕Bidiagonalization and symmetric tridiagonalization by systolic arraysRobert Schreiber · 1988
- 📕Decision problems in systolic circuit verificationParosh Aziz Abdulla · 1990
- 📕Sistolicheskie strukturyInternational Workshop on Systolic Arrays (1st 1986 Oxford, England) · 1993
- 📕A Survey of the state of the art and focused research in range systems · 1986
Matrix computations on systolic-type arraysJaime H. Moreno · 1992
Ranked by number of editions on Open Library, a rough measure of how lasting a book is.
🔗 Related topics
- Multiple instruction, single data In computing, multiple instruction, single data (MISD) is a type of parallel computing architecture where many functional units perform different operations…
- Topological sorting In computer science, a topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge…
- Cannon's algorithm In computer science, Cannon's algorithm is a distributed algorithm for matrix multiplication for two-dimensional meshes first described in 1969 by Lynn…
- Mivar-based approach The Mivar-based approach is a mathematical tool for designing artificial intelligence (AI) systems. Mivar (Multidimensional Informational Variable Adaptive…
- Parallel all-pairs shortest path algorithm A central problem in algorithmic graph theory is the shortest path problem. Hereby, the problem of finding the shortest path between every pair of nodes…
- Adaptive heap sort In computer science, adaptive heap sort is a comparison-based sorting algorithm of the adaptive sort family. It is a variant of heap sort that performs…
- Bisection bandwidth In computer networking, a network may be bisected into two equal-sized partitions. The bisection bandwidth of a network topology is the minimum bandwidth…
- Neural network Gaussian process A Neural Network Gaussian Process (NNGP) is a Gaussian process (GP) obtained as the limit of a certain type of sequence of neural networks. Specifically…