Optimization of Array Redistribution for Distributed Memory Multicomputers

Languages such as High Performance Fortran implement parallel algorithms by distributing large data structures across a multicomputer system. To enhance parallelism and reduce communication, it is sometimes beneficial for a programmer to change the distribution between phases of the algorithm. We introduce a new mapping strategy, called the spiral mapping, that reduces the communication overhead of array redistribution. Redistribution using the spiral mapping exploits communication locality and reduces global communication conflicts. We implemented redistribution using the standard linear mapping and the spiral mapping for two dimensional arrays; for 1024 \Theta 1024 arrays, redistribution using the spiral mapping is 36% faster than using the linear mapping on a 16 node Intel iPSC/860. Keywords: HPF; redistribution; distributed memory computer; processor mapping. 1 Introduction In languages like High Performance Fortran (HPF) for distributed memory multicomputers, array redistribu..