Algorithms

These topics apply the main sequence to four kinds of program that recur in applications: a product of matrices across a grid, a sort along a row, physics on a grid with its boundary conditions, and a column of PEs driven by a stream of commands.

Each topic is a complete program, and each opens with the lessons and topics it needs. Read a topic once you have read everything on its Needs line.

Topic	What it teaches
Matrix multiplication across PEs	An output-stationary systolic array on an M×N grid, compared with three other layouts of the same product
Sorting networks along a row	Odd-even transposition and merge-split sorts, phases without barriers, an exchange that cannot deadlock
Physics on a grid of points: boundary conditions	Fixed, zero-flux and periodic boundaries made by the moat, colors that alternate so a grid can wrap, two fields per exchange
Command streams: Tetris on a column	Fixed-size command packets forwarded and applied by every PE, a field rewritten in flight, a run that ends by count