Matrix Computations on Systolic-Type Arrays

Matrix Computations on Systolic-Type Arrays provides a framework which permits a good understanding of the features and limitations of processor arrays for matrix algorithms. It describes the tradeoffs among the characteristics of these systems, such as internal storage and communication bandwidth, and the impact on overall performance and cost. A system which allows for the analysis of methods for the design/mapping of matrix algorithms is also presented. This method identifies stages in the design/mapping process and the capabilities required at each stage.
Matrix Computations on Systolic-Type Arrays provides a much needed description of the area of processor arrays for matrix algorithms and of the methods used to derive those arrays. The ideas developed here reduce the space of solutions in the design/mapping process by establishing clear criteria to select among possible options as well as by a-priori rejection of alternatives which are not adequate (but which are considered in other approaches). The end result is a method which is more specific than other techniques previously available (suitable for a class of matrix algorithms) but which is more systematic, better defined and more effective in reaching the desired objectives.
Matrix Computations on Systolic-Type Arrays will interest researchers and professionals who are looking for systematic mechanisms to implement matrix algorithms either as algorithm-specific structures or using specialized architectures. It provides tools that simplify the design/mapping process without introducing degradation, and that permit tradeoffs between performance/cost measures selected by the designer.

1 Introduction.- 1.1 Matrix computations, algorithms, parallel architectures.- 1.2 Summary of the book.- 2 Systolic-type arrays for matrix algorithms.- 2.1 Realization and mapping of matrix algorithms.- 2.2 Design space, performance and cost measures.- 2.3 Architectural models of systolic-type arrays.- 2.4 Models of computation in systolic-type arrays.- 2.5 Size relation among problem and array.- 2.6 Tradeoffs in an implementation.- 2.7 Further readings.- 3 Regularization of matrix algorithms.- 3.1 Stages in a design method.- 3.2 Regularized representations.- 3.3 The multimesh graph representation.- 3.4 Class of admissible algorithms in the MMG method.- 3.5 Regularization stage in the MMG method.- 3.6 Formal description of the regularizing transformations.- 3.7 Deriving the multimesh graph of the triangularization algorithm.- 3.8 Deriving the multimesh graph of the transitive closure algorithm.- 3.9 Deriving the multimesh graph of the LU-decomposition algorithm.- 3.10 Deriving the multimesh graph of the algorithm to compute BA-1.- 3.11 Summary.- 4 Realization of algorithm-specific fixed-size arrays.- 4.1 Realization procedure.- 4.2 Derivation of G-graphs: Grouping by prisms.- 4.3 Schedule of nodes in a complete prism.- 4.4 Prisms in a complete graph.- 4.5 Direction of prisms.- 4.6 Complete multimesh graph and the pseudosystolic model of computation.- 4.7 Cell architecture and control.- 4.8 Incomplete graphs and the pseudosystolic model.- 4.9 Multimesh graphs with two flows of input data.- 4.10 Example: Pseudosystolic arrays for matrix triangularization.- 4.11 Example: Systolic-type arrays for computing BA-1.- 4.12 Summary.- 5 Partitioned realizations using cut-and-pile.- 5.1 Model of partitioned execution using cut-and-pile.- 5.2 Partitioning a multimesh graph using cut-and-pile.- 5.3 Selection of G-sets.- 5.4 Schedule of G-sets.- 5.5 G-sets from a complete multimesh graph.- 5.6 Incomplete MMGs and G-sets.- 5.7 Summary of performance measures.- 5.8 Multimesh graphs with two flows of input data.- 5.9 Cut-and-pile in LU-decomposition.- 5.10 Tradeoffs among array topologies.- 5.11 A canonical linear array for partitioned problems.- 6 Partitioned realizations using coalescing.- 6.1 The model of computation.- 6.2 The model of partitioned execution.- 6.3 Partitioning the multimesh graph.- 6.4 Coalescing the multimesh graph.- 6.5 Schedule of nodes in a partition.- 6.6 Cell architecture and control.- 6.7 Coalescing incomplete MMGs.- 6.8 Example: Local-access arrays for LU-decomposition.- 7 Linear pseudosystolic array for matrix algorithms.- 7.1 Architecture of the array.- 7.2 Architecture of the cells.- 7.3 Code efficiency.- 7.4 Executing LU-decomposition.- 7.5 Summary.- 8 Mapping matrix algorithms.- 8.1 The regularization stage.- 8.2 The mapping stage and the specific target architecture.- 8.3 Example: Mapping onto a memory-linked array.- 8.4 Example: Mapping onto a digital signal processor.- 8.5 Summary.- 9 Summary and further research.- 9.1 Architectural and computational models.- 9.2 Realization of arrays.- 9.3 Linear pseudosystolic array.- 9.4 Mapping onto existing structures.- 9.5 Further research.