Task scheduling in distributed systems by work stealing and mugging - a simulation study

We model and simulate the execution of parallel jobs represented by directed acyclic graphs on a system of networked distributed heterogeneous computers. We tested two online schedulers, the Enhanced Cilk Scheduler (ECS) and the Central Manager (CM). ECS is a decentralized scheduler, which implements work stealing and processor mugging techniques. CM is a centralized greedy scheduler. Our simulation results show that ECS is a well behaved scheduler particularly suited for scheduling task execution in dynamically changing systems because it is robust, requires little communication, and almost matches the performance of the CM scheduler.