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.
What people are saying - Write a review
We haven't found any reviews in the usual places.
Data Communication and Data Organization in Parallel Com
Arbitrary Skewing Schemes for dDimensional Arrays
Compactly Representable Skewing Schemes for dDimensional
4 other sections not shown
Other editions - View all
access patterns access to rows base(m binary tree block templates cells collection of templates column-conflict columns conflict-free access Consider Contradiction Corollary coset d-dimensional array data locations data transfers defined definition denote diagonal Latin square double diagonal Latin equivalent exists a skewing f-cell figure follows four-node fundamental domain G Zd gridline handled analogously hence hyperbase ILLIAC IV instance integer k-ary tree Latin square lemma linear skewing scheme mapped matrix memory banks minimum number model of computation modulo multi-periodic skewing scheme node NP-complete number of memory P G C p-group parallel computer architectures perfect shuffle periodic skewing scheme periodic tessellation points polyomino prim(m primary line processing elements Proof Directly Proof Let proposition regular skewing scheme relative position result schemes for trees semi-regular skewing scheme SIMD strip templates submonoid subset surjective tessellates the plane three-node transversal templates underlying lattice