Algebraic foundation for FORTRAN 90 communication intrinsics

摘要

This paper proposes linear algebra and multilinear algebra as a foundation for the implementation and the understanding of several fundamental parallel communication operations. We will analyze three representative operations: the FORTRAN 90 intrinsic SPREAD, the FORTRAN 90 intrinsic SUM and the parallel prefix operator SCAN. By formulating the operations as linear transformations, we hope to be able to apply linear algebraic techniques to reorder and to factor both these transformations and higher level user functions that call these primitives. Several applications of this technique will be discussed. Perhaps the most surprising was simple code that sped up the SPREAD intrinsic on the CM-200 by a factor of up to 6 and the SUM intrinsic by a factor of up to 20. This speedup had immediate and dramatic impact on many parallel programs. The SUM intrinsic was also sped up on the CM-5.