A modified work stealing algorithm based on randomized spanning trees approach

Abstract EN

The emergence of dynamically structured computations, which run on parallel and distributed resources, motivates us to develop advanced algorithms for load balancing and distribution.

Efficient load balancing can be defined as the process of distributing the work among a set of processors, such that the processors are kept busy as much as possible (maximizing the efficiency) and, at the same time, the overhead of scheduling is lowered.

Work stealing becomes important, as a dynamic scheduling algorithm; because it can be optimal under some circumstances.

It drives bounding values for a given system parameters.

In this paper, a modified algorithm for work stealing is introduced ; this algorithm works the same way as work stealing algorithm, but it is behaves differently ; a distributed algorithm is applied for forming a partial spanning tree of idle processors as long as a random steal, or walk, is provided.

Each partial spanning-tree will form cooperative nodes ; whenever a certain node finds a workload source, it will disconnect itself from the tree, inform its neighbors about that source of workload.

The tree, then, will be eventually flushed.

The simulation results show that the modified algorithm performs better, especially when the distribution of workload is irregular.