Description: 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.

Please Wait