Dependence driven execution for multiprogrammed multiprocessor
Suvas Vajracharya, Dirk C. Grunwald · 1998
Abstract Barrier synchronizations can be very expensive on multiprogramming environment because no process can go past a barrier until all the processes have arrived. If a process participating at a barrier is swapped out by the operating system, the rest of participating processes end up waiting for the swapped-out process. This paper presents a compile-time/run-time system that uses a dependence-driven execution to overlap the execution of computations separated by barriers so that the processes do not spend most of the time idling at the synchronization point. Keywords: Run-time systems, multiprogramming, loop scheduling, dependence-driven execution, barrier synchronization, coarse-grain dataflow. The parallel execution of a sequence of loop nests is typically broken into phases, each phase consisting of a simple loop separated by a barrier synchronization to ensure that the execution respects