Beyond loop partitioning
David E. Hudak, Santosh G. Abraham · 1991
Iterative parallel algorithms account for many important supercomputer applications.on such algorithms, the communication of partial results stresses the memory system performance.In an earlier paper, we developed loop partitioning strategies that minimize the number of data points exchanged between processors.In this paper, we develop data placement schemes that minimize communication time.Under a given loop $bal da~a into four classes for artition our compile-time algorlthm partitions each processor.Eac rocessor may move its ezclu- !V sive read-write set (ER ), into the highest level of its hierarchy.The processor must maintain consistency on the shared read-excluszve write set (SREW) and shared read-no wlit e set (SRN W).A processor does not access the no read-wrate set (NRW).Assignment of SRNW sets to the local memory of each processor and caching of the ERW sets leads to a factor of five improvement over the default data assignment in the BBN TC2000.Features in current generation pipelined processors with multiple functional units permit the overlap of memory accesses with computation.Our experiments on the BBN TC2000 show that the degree of overlap is limited by architectural parameters, such as the number of CPU registers.We show that software redundancy in data assignments achieves 1? rester overla thus reducing communication over-: ead even furt er.