Abstract
It is extremely difficult to parallelize DOACROSS loops with nonuniform loop-carried dependences. In this paper, we present a static scheduling scheme with an accompanying synchronization strategy that can execute such DOACROSS loops effectively and efficiently. Our approach uses one of the parallelization techniques called Dependence Uniformization, which finds a small set of uniform dependence vectors to cover all possible nonuniform dependences in a DOACROSS loop. It differs from the previous schemes in that we demonstrate a better way to select the uniform dependence vectors. When used with the Static Strip Scheduling scheme, the proposed uniform dependence vector set allows us to enforce dependences with more locality, which reduces the requirement of explicit synchronization considerably while retaining most of the parallelism. This paper describes the uniform dependence vectors selection strategy and the static strip scheduling scheme. The performance analysis and examples are also presented.
Original language | English (US) |
---|---|
Pages (from-to) | 463-476 |
Number of pages | 14 |
Journal | IEEE Transactions on Parallel and Distributed Systems |
Volume | 7 |
Issue number | 5 |
DOIs | |
State | Published - 1996 |
Bibliographical note
Funding Information:This work was supported in part by the U.S. National Science Foundation under Grant Nos. NSF MIP94-96320 a n d NSF MIP93-07910.
Keywords
- Compiler transformation
- Data dependence
- Loop parallelization
- Parallelism
- Scheduling
- Synchronization