Proactive task scheduling and stealing in master-slave based load balancing for parallel contingency analysis

With increasing emphasis on analyzing N − k contingencies, use of parallel resources has become imperative. Parallelization imposes the requirement of load-balancing for achieving high resource usage efficiency. Conventional static allocation based scheduling techniques fail to achieve load balancing. To address this limitation, master-slave scheduling (MSS) has been used; however, in MSS, after task completion, slave processors wait for the next task to arrive leading to idle-wait. In the case of contention at master, the idle-wait could become significant and degrade the performance of the MSS algorithm.

We present a technique to combine the advantage of proactive task scheduling and stealing with the simplicity of MSS. We refer to it as PTMSS. In PTMSS, master proactively queues an extra task at the slave processor, such that on completion of a task, the next task is immediately started. Further, when master runs out of the tasks, it steals a queued task from one slave and allocates to another slave which has completed its tasks. Simulation experiments have been conducted on a large power system with 13,029 buses and thousands of contingencies have been analyzed. The results show that PTMSS performs better than conventional MSS and also offers significant computational gains over serial execution.