This paper deals with general nestedloops and proposes a novel scheduling methodology for reducing the communication cost of parallel programs. General loops contain complex loop bodies (consisting of arbitrary progr...
详细信息
ISBN:
(纸本)0769523269
This paper deals with general nestedloops and proposes a novel scheduling methodology for reducing the communication cost of parallel programs. General loops contain complex loop bodies (consisting of arbitrary program statements, such as assignments, conditions and repetitions) that exhibit uniform loop-carried dependencies. Therefore it is now possible to achieve efficient parallelization for a vast class of loops, mostly found in DSP PDEs, signal and video coding. We use computational geometry methods, that exploit efficiently the regularity of nestedloops index spaces, in order to significantly reduce the communication cost, which in most cases is the main drawback of parallel programs' performance. Through extensive testing, we show that the proposed method outperforms in all cases the classic cyclic mapping, succeeding to reduce the communication by 15%-35%. This significant reduction of the communication volume makes our method a promising candidate to be incorporated into existing automatic parallel code generation tools.
This paper attempts to uniformly parallelize cyclic and acyclic code, and schedule nestedloops directly. A program is parallelized by one-pass scanning from its first to its last operation. This contrasts sharply wit...
详细信息
暂无评论