Dynamic Processor Self-Scheduling for General Parallel Nested Loops

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) [14] and shortest-delay self-scheduling (SDSS) [16] can be incorporated in this scheme. The performance and its possible overhead using this scheme are also analyzed in the paper.