Eliminating Memory Fragmentation within Partitionable SIMD/SPMD Machines

Efficient data layout is an important aspect of the compilation process. A model for the creation of “perfect” memory maps for large-scale parallel machines capable of user-controlled partitionable SIMD/SPMD operation is developed. The term “perfect” implies that no memory fragmentation occurs and ensures that the memory map size is kept to a minimum. The major constraint on solving this problem is one based on the single program nature of both the SIMD and SPMD modes of parallelism. Specifically, it is assumed all processors within the same submachine use identical addresses to access corresponding data items in each of their local memories. Necessary and sufficient conditions are derived for being able to create “perfect” memory maps and these results are applied to several partitionable interconnection networks.