This paper proposes a processor self-scheduling scheme for general parallel nested loops in multiprocessor systems. Parallel loops usually constitute most of the execution time in scientific application programs. In a general parallel loop structure, parallel loops, serial loops, and IF-THEN-ELSE constructs are nested in an arbitrary order, and the execution time of the loop body may vary substantially from iteration to iteration. In the proposed scheme, programs are instrumented to allow processors to schedule loop iterations among themselves dynamically at run time without the involvement of the operating system. The proposed self-scheduling scheme has two levels. At the low level, it uses simple “fetch-and-op” operations to take advantage of the regular structure in the innermost parallel loop nests. At the high level, the irregular structure of the outer loops (parallel or serial) and the IF-THEN-ELSE constructs are handled by using dynamic parallel linked lists. The larger granularity of the processes at the high level can easily justify the added overhead incurred from maintaining such dynamic data structures. Many self-scheduling techniques proposed so far, such as guided self-scheduling (GSS)  and shortest-delay self-scheduling (SDSS)  can be incorporated in this scheme. The performance and its possible overhead using this scheme are also analyzed in the paper.
Bibliographical noteFunding Information:
Manuscript received February 1, 1987; revised September 7, 1989. This work was supported in part by the National Science Foundation under Grant US NSF MIP-8410110, the U.S. Department of Energy under Grant US DOE DE-FG02-85ER25001, the U.S. Army Research Office under Grant DAA2-03-87-(3-003, and by a donation from the IBM Corporation. 2. Fang is with the Convex Computer Corporation, Richardson, TX 75083. P. Tang is with the Department of Computer Science, Australia National University, Canberra, ACT 2601, Australia. P.-C. Yew is with the Center for Supercomputing Research and Development, University of Illinois at Urbana-Champaign, Urbana, IL 61801. C.-Q. Zhu is with the Computer Center, hdan University, Shanghai, Peoples Republic of China. IEEE Log Number 9035955.
- Data synchronization
- doacross loops
- doall loops
- shared-memory multiprocessor