Overview

""Matrix Computations on Systolic-Type Arrays"" provides a framework which should permit an understanding of the features and limitations of processor arrays for matrix algorithms. The book 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/mapoping process and the capabilities required at each stage. The text provides a 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 degredation, and that permit tradeoffs between performance/cost measures selected by the designer.

Full Product Details

Author:   Jaime Moreno ,  Tomás Lang
Publisher:   Springer
Imprint:   Springer
Edition:   1992 ed.
Volume:   174
Dimensions:   Width: 15.50cm , Height: 1.90cm , Length: 23.50cm
Weight:   1.360kg
ISBN:  

9780792392378

ISBN 10:   079239237
Pages:   280
Publication Date:   31 October 1992
Audience:   College/higher education ,  Professional and scholarly ,  Postgraduate, Research & Scholarly ,  Professional & Vocational
Format:   Hardback
Publisher's Status:   Active
Availability:   In Print  
This item will be ordered in for you from one of our suppliers. Upon receipt, we will promptly dispatch it out to you. For in store availability, please contact us.

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