SAFE SELF-SCHEDULING - A PARALLEL LOOP SCHEDULING SCHEME FOR SHARED-MEMORY MULTIPROCESSORS

In this paper we present Safe Self-Scheduling (SSS), a new scheduling scheme that schedules parallel loops with variable length iteration ex ecution times not known at compile time. The scheme assumes a shared m emory space. SSS combines static scheduling with dynamic scheduling an d draws favorable advantages from each. First, it reduces the dynamic scheduling overhead by statically scheduling a major portion of loop i terations. Second, the workload is balanced with a simple and efficien t self-scheduling scheme by applying a new measure, the smallest criti cal chore size. Experimental results comparing SSS with other scheduli ng schemes indicate that SSS surpasses other scheduling schemes. In th e experiment on Gauss-Jordan, an application that is suitable for stat ic scheduling schemes, SSS is the only self-scheduling scheme that out performs the static scheduling scheme. This indicates that SSS achieve s a balanced workload with a very small amount of overhead.