A Concurrent Multi-Stealing Scheduler Model For Divide And Conquer Problems

Abstract

Multicore architecture has dramatically changed the general direction of software development dedicated for personal computers. As such, it is important for software designers to keep pace with the evolving challenges that happen in the hardware side, for example in this context of multicore architecture, so that they can leverage on the advantages of multicore technology as much as possible while developing software. As one of the well-known techniques, Divide and Conquer has a natural adaptation with the multicore technology. The technique needs to be further developed to fit into this new environment. In this paper, we present a new concurrent multithreaded Colored Petri Nets model that provides a new approach for scheduling Divide and Conquer problems on a multicore environment. Two new schedulers have been developed to control the actions of the model. The Multi Stealing Scheduler (MSS) has been designed to redistribute threads among the modelled cores. The MSS is general, scalable and it can be used for any Divide and Conquer problem. The second scheduler is the Local Threads Scheduler (LTS) that has the duty of threads creation and division inside each modelled core. In addition, the LTS introduces a new recursive method to provide the necessary information to multiply two matrices. Two main things have been achieved: First, workload among the modelled cores becomes well balanced; second, the technique produces a high level of concurrency between the elements of the model, which greatly minimise the execution time.