A partial multi stealing scheduling model for divide and Conquer Problems

摘要

Work-Stealing technique has proven itself to be one of the successful multithreaded scheduling techniques that are designed to balance work-load in multicore environments. As the number of cores in multicore-based products increases, new developments have to be made for this technique to cope with this continuous challenge in the hardware side. In this paper, we present a multicore model that is designed to deal with Divide and Conquer Problems. The model is based on designing two types of schedulers: The High-Level Scheduler (HLS) and Low-Level Scheduler (LLS). The HLS has the duty of balancing threads distribution among the modelled cores. In this scheduler, we present a new policy, Partial Multi Stealing Policy that extends the principle of work stealing in managing threads distribution. The policy is scalable and general for dealing with any kind of Divide and Conquer Problems. For the LLS, we introduce a new method for threads creation and management for the Matrix Multiplication problem. The model has been designed using Coloured Petri Nets (CPN) as the modelling language, and simulated by CPN-Tool as the modelling tool. The results of the simulation show a high level of concurrency between the elements of the model which reduces the execution time as the number of cores increases in the model.