APPLICATION OF SECRETARY ALGORITHM TO DYNAMIC LOAD BALANCING IN USER-SPACE ON MULTICORE SYSTEMS

In recent years, multicore processors have been so prevalent in many types ofsystems and are now widely used even in commodities for a wide range of applications.Although multicore processors are clearly a popular hardware solution to problems thatwere not possible with traditional single-core processors, taking advantage of them areinevitably met by software challenges. As Amdahl’s law puts it, the performance gain islimited by the percentage of the software that cannot be run in parallel on multiple cores.Even when an application is “embarrassingly” parallelized by a careful design ofalgorithm and implementation, load balancing of tasks across different cores is a veryimportant and critical aspect in utilizing a multicore system as close to its fullest potentialas possible.In this paper, we investigate how a solution to a cardinal payoff variant of thesecretary problem can be applied to a proactive, decentralized, dynamic load balancingtechnique in user-space to assist single program, multiple data (SPMD) applications inmultiprogrammed environment so that all tasks can make roughly equal progressdistributed over all cores. We examine how this method compares with the default Linuxload balancer in terms of scalability and predictability. Our experiments show promisingresults that show our technique outperforms the default Linux scheduler by an average 40%speedup in multiprogrammed environment with less time variance among multipleexecutions