Data Organization in Parallel Computers

The organization of data is clearly of great importance in the design of high performance algorithms and architectures. Although there are several landmark papers on this subject, no comprehensive treatment has appeared. This monograph is intended to fill that gap. We introduce a model of computation for parallel computer architec­ tures, by which we are able to express the intrinsic complexity of data or­ ganization for specific architectures. We apply this model of computation to several existing parallel computer architectures, e.g., the CDC 205 and CRAY vector-computers, and the MPP binary array processor. The study of data organization in parallel computations was introduced as early as 1970. During the development of the ILLIAC IV system there was a need for a theory of possible data arrangements in interleaved mem­ ory systems. The resulting theory dealt primarily with storage schemes also called skewing schemes for 2-dimensional matrices, i.e., mappings from a- dimensional array to a number of memory banks. By means of the model of computation we are able to apply the theory of skewing schemes to var­ ious kinds of parallel computer architectures. This results in a number of consequences for both the design of parallel computer architectures and for applications of parallel processing.

Contenu

1 Data Communication and Data Organization in Parallel Computations: Classification and Overview.- 1.1 Introduction.- 1.2 Some Classification Schemes for Parallel Computer Architectures.- 1.3 Data Communication in Parallel Computer Architectures: a New Computational Viewpoint of Parallel Computations.- 1.3.1 A Model of Computation for Regularly Structured Computations.- 1.3.2 Classification of Some Existing Parallel Computer Architectures.- 1.3.2.1 Vector/Pipeline Processors.- 1.3.2.2 Array Processors.- 1.3.2.3 Bit-Slice Array Processors.- 1.3.2.4 Other Parallel Computer Architectures.- 1.4 Data Organization in Parallel Computer Architectures: the Theory of Skewing Schemes.- 1.4.1 Historical Notes.- 1.4.2 Skewing Schemes.- 1.4.3 The Interaction of Data Communication and Data Organization.- 2 Arbitrary Skewing Schemes for d-Dimensional Arrays.- 2.1 The General Case.- 2.2 The Validity of Skewing Schemes for Block Templates.- 2.3 The Validity of Skewing Scheines for [x1, x2,..., xd]-Lines.- 2.3.1 Latin Squares.- 2.3.2 Composition of Double Diagonal (dd) Latin Squares.- 2.4 The Validity of Skewing Schemes for Polyominoes (Rookwise Connected Templates).- 2.4.1 Definitions and Preliminary Results.- 2.4.2 Tessellations of the Plane by Polyominoes.- 2.4.3 Conditions for Periodic Tessellations by Polyominoes.- 2.4.4 Obtaining Periodic Tessellations from Arbitrary Tessellations; a Proof of Shapiro's Conjecture.- 2.4.5 Final Comments.- 3 Compactly Representable Skewing Schemes for d-Dimensional Arrays.- 3.1 Linear Skewing Schemes.- 3.1.1 The Equivalency of Linear Skewing Schemes.- 3.1.2 d-Ordered Vectors.- 3.1.3 The Validity of Linear Skewing Schemes for Rows, Columns and (Anti-)Diagonals.- 3.1.4 Conflict-Free Access through Multiple Fetches.- 3.2 Periodic Skewing Schemes.- 3.2.1 Periodic Skewing Schemes for 2-Dimensional Arrays.- 3.2.1.1 Periodic Skewing Schemes Redefined.- 3.2.1.2 Fundamental Templates and Their Use.- 3.2.1.3 The Validity of Periodic Skewing Schemes.- 3.2.2 Towards the Structure of Periodic Skewing Schemes.- 3.2.2.1 A Representation of Periodic Skewing Schemes.- 3.2.2.2 Applications to the Theory of (Periodic) Skewing Schemes.- 3.2.3 The Finite Abelian Group Approach.- 3.2.3.1 Skewing Schemes and Conflict-Free Access.- 3.2.3.2 The Classification of Periodic Skewing Schemes.- 3.2.3.3 A Normal Form for (General) Periodic Skewing Schemes.- 3.2.3.4 The Number of Non-Equivalent Linear Skewing Schemes.- 3.3 Multi-Periodic Skewing Schemes.- 3.3.1 Multi-Periodic Skewing Schemes and Their Relationship with Other Compact Skewing Schemes.- 3.3.2 The L-Validity of Multi-Periodic Skewing Schemes.- 3.3.3 A Representation of Multi-Periodic Skewing Schemes.- 4 Arbitrary Skewing Schemes for Trees.- 4.1 The Validity of Skewing Schemes for Trees.- 4.2 Skewing Schemes for Strips.- 4.3 An Exact Characterization of the Number µT({P1, P2,..., Pt}).- 4.4 Some Applications and Simplifications of Theorem 4.6.- 4.5 Applications of Theorem 4.6 (Theorem 4.7) to Certain Collections of Templates.- 4.6 Some Specific Results.- 5 Compactly Representable Skewing Schemes for Trees.- 5.1 Preliminaries.- 5.2 Semi-Regular Skewing Schemes.- 5.3 The Insufficiency of Semi-Regular Skewing Schemes.- 5.4 Regular Skewing Schemes.- 5.5 The Validity of Regular Skewing Schemes.- 5.6 Linear Skewing Schemes for Trees.