Scheduling user-level threads on distributed shared-memory multiprocessors

In this paper we present Dynamic Bisectioning or DBS, a simple but powerful comprehensive scheduling policy for user-level threads, which unifies the exploitation of (multidimensional) loop and nested functional (or task) parallelism. Unlike other schemes that have been proposed and used thus far, DBS is not constrained to scheduling DAGs or singly nested parallel loops. Rather, our policy encompasses the most general type of parallel program model that allows arbitrary mix of nested loops and nested DAGs (directed acyclic task-graphs) or any combination of the above. DBS employs a simple but powerful two-level dynamic policy which is adaptive and sensitive to the type and amount of parallelism at hand. On one extreme DBS approximates static scheduling, hence facilitating locality of data, while at the other extreme it resorts to dynamic thread migration in order to balance uneven loads. Even the latter is done in a controlled way so as to minimize network latency.