All-pairs paradigm, Householder reduction, Precedence matrices, Pipelined computers
An all-pairs problem is a computation on every possible subset consisting of two elements chosen from a set of n elements. N-body simulation and Householder reduction are all-pairs problems. The paper defines the all-pairs problem concisely by means of precedence matrices and derives a parallel algorithm. The algorithm is presented in both coarse-grain and medium-grain form. The all-pairs paradigm is illustrated by a pipeline for Householder reduction of a matrix to triangular form.
Hansen, Per Brinch, "THE ALL-PAIRS PIPELINE" (1990). Electrical Engineering and Computer Science Technical Reports. 77.