Trapezoid Self-Scheduling: A Practical Scheduling Scheme for Parallel Compilers

In this paper, we present a new practical processor self-scheduling scheme, Trapezoid Self-Scheduling, for arbitrary parallel nested loops in shared-memory multiprocessors. Generally, loops are the richest source of parallelism in parallel programs. To dynamically allocate loop iterations to processors, one may achieve load balancing among processors at the expense of run-time scheduling overhead. By linearly decreasing the chunk size at run time, the best tradeoff between the scheduling overhead and balanced workload can be obtained in the proposed trapezoid self-scheduling approach. Due to its simplicity and flexibility, this approach can be efficiently implemented in any parallel compilers. The small and predictable number of chores also allow efficient management of memory in a static fashion. Our experiments conducted in a 96-node Butterfly GP1000 clearly show the advantage of the trapezoid self-scheduling over other well-known self-scheduling approaches. Keywords: Chunk size, Cr..