OPTIMIZATION OF ARRAY REDISTRIBUTION FOR DISTRIBUTED-MEMORY MULTICOMPUTERS

Languages such as High Performance Fortran implement parallel algorith ms by distributing large data structures across a multicomputer system . To enhance parallelism and reduce communication, it is sometimes ben eficial 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 redistributi on. Redistribution using the spiral mapping exploits communication loc ality and reduces global communication conflicts. We implemented redis tribution using the standard linear mapping and the spiral mapping for two dimensional arrays; for 1024 x 1024 arrays, redistribution using the spiral mapping is 36% faster than using the linear mapping on a 16 node Intel iPSC/860.