A practical scheduling scheme for non-uniform parallel loops on distributed memory parallel machines

Loops without dependences among iterations are a rich source of parallelism in many applications. Among these types of loops, non-uniform loops with variable execution times need efficient scheduling schemes to take advantages of the capabilities of parallel machines. We present a global distributed control scheme (GDC) to schedule nonuniform loops on distributed memory parallel machines. GDC decentralizes scheduling controls among all processors with an attempt to keep heavily loaded processors being in charge of scheduling tasks. For comparative evaluation, GDC and other well-known scheduling schemes are implemented on a 512 processor Intel Delta parallel machine. Our experimental results show that GDC performs well on many applications with different characteristics