Data Organization in Parallel Computers

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 uT({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.