A work-stealing based dynamic load balancing algorithm for conservative parallel discrete event simulation

In the past few years, we have witnessed an increased interest in using multithreading PDES on multicore platforms. The work-stealing scheme, which towards to general multithread computing, can be utilized in PDES to achieve load balance straightly. However, to the best of our knowledge, the work-stealing scheme has only served as a competitor, instead of a cooperator, to other load balancing algorithm. In this paper, we propose a work-stealing based dynamic load balancing algorithm (WS-DLB) with the aim of combining their advantages. It adaptively rebalances the LPs distribution based on a priori estimation, and uses a greedy lock-free work-stealing scheme to eliminate bias at runtime. In addition, these two schemes are well adapted to enhance each other. We analyze the performance characteristics of the proposed algorithm by means of a synthetic benchmark. Experiments demonstrate that our WS-DLB algorithm achieves better performance.