Evaluation of Work Stealing Algorithms

摘要: Work stealing is a common model in parallel computing used to schedule the execution of tasks. In this model, tasks are assigned dynamically to different processors as they are generated by a computation. However, to improve execution time, idle processors can steal tasks from other processors. Different underlying techniques have been proposed for work stealing, with FIFO and LIFO among the most used techniques. In this work we propose an alternative to these techniques, based on task priority, as a means to avoid fairness problems in the way that tasks are stolen across processors. To evaluate our technique we use a benchmark of different computation topologies variating the amount of tasks, the dependance between tasks, and the number of processors used. Our results show different performances for the three evaluated techniques. In cases managing smaller computations with fewer processors, both …