Distributed Work Stealing at Scale via Matchmaking

Many classes of high-performance applications and combinatorial problems exhibit large degree of imbalance in terms of task execution times. One approach to achieving high machine efficiency and balanced resource use is to over-decompose the problem into fine-grained tasks that are then dynamically re-balanced across the system by approaches such as workstealing. For such irregular applications, existing work stealing or work balancing techniques exhibit high overheads due to potentially excessive communication messages, and/or delays experienced by idle nodes in finding work due to repeated failed steals. In particular, on very large scale clusters, the problem of matching work generation and work consumption is extremely challenging. At the heart of the problem is the dilemma: idle workers do not know where to look for work and the work producers do not know where to send the generated extra work. We contend that the fundamental problem of distributed work-stealing is not one of rapid dissemination of availability of work but one of rapidly bringing together work producers and consumers. In response, we develop a workstealing-based algorithm that performs timely, lightweight and highly efficient matchmaking between work producers and consumers. The matchmaker simultaneously accumulates the work availability messages from the producer nodes and rapidly redirects messages of work availability to the consumers. The matchmaker is a regular worker which works on its own work queue executing tasks when it pauses from the matchmaking work. We validate these claims via an implementation of a match-making-based scheduler for Charm++, that we evaluate using representative benchmarks running on up to 8K cores. Results show that our scheduler is able to outperform other load balancers and distributed work stealing schedulers, and to achieve scale beyond what is possible with current approaches.