Overview

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.

Full Product Details

Author:   Jaime Moreno ,  Tomás Lang
Publisher:   Springer-Verlag New York Inc.
Imprint:   Springer-Verlag New York Inc.
Edition:   Softcover reprint of the original 1st ed. 1992
Volume:   174
Dimensions:   Width: 15.50cm , Height: 1.70cm , Length: 23.50cm
Weight:   0.480kg
ISBN:  

9781461366041

ISBN 10:   1461366046
Pages:   280
Publication Date:   30 September 2012
Audience:   Professional and scholarly ,  Professional & Vocational
Format:   Paperback
Publisher's Status:   Active
Availability:   Manufactured on demand  
We will order this item for you from a manufactured on demand supplier.

Table of Contents

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.

Reviews

Author Information

Tab Content 6

Author Website:  

Customer Reviews

Recent Reviews

No review item found!

Add your own review!

Countries Available

All regions