Parallel Sorting with Dynamic Load-Balancing in Stochastic Environments

Abstract: Parallel algorithms and specifically parallelism in sorting algorithms as a symbolic application have been in-tensively studied. Some algorithms are available for parallel sorting by dedicated or homogenous processors. Dedicated processors for sorting are rarely a practice of real world. This paper introduces an algorithm for parallel sorting on proces-sors that are not only utilized for sorting but also may run a multitasking OS and perform other tasks concurrently. This multitasking leads to stochastic behaviors and virtual speeds of the processors felt by the processes including the sorter pro-cesses. An agent framework is used to simulate a multiprocessor environment. The results show that the proposed algorithm performs better load balancing between processors than previous algorithms in stochastic speed-variant environments. Key-words: Parallel sorting, Dynamic load-balancing, Overpartitioning, Stochastic environments