Tuning mechanism for the Lifeline GLB

Achieving load balance is a challenge for irregular applications. Balancing runtimes and libraries aim at relieving the programmer from this difficult task by proposing a layer of abstraction between the computation at hand and the hardware used to actually perform it. With the rise of many-core architectures, load balancers for distributed computation are now expected to handle unbalance both between and within compute nodes. We bear a particular interest in backtrack search algorithms where branches of the exploration tree can be processed in parallel. Profile-based load balancers cannot be applied to them as the computation need only be performed once. It is therefore vital to promptly detect and address load unbalances from the start.A popular solution consists in using the fork/join model. Another approach on which we focus in this article is implemented in the load balancing library of X10. Both of these schemes are sensitive to task granularity. Fined-grained tasks may incur significant overhead, especially with the increased number of parallel workers of many-core architectures, while coarse-grained tasks may cause starvation. Determining a suitable grain size for a particular application is difficult.In this article we present our Java implementation of the X10 load balancing scheme. We extend it with a tuning mechanism which dynamically adjusts the task granularity, increasing the library’s versatility and usability. We demonstrate the capabilities of our tuning mechanism to suit many-core clusters using four applications: Unbalanced Tree Search, Pentomino, the Traveling Salesman Problem, and N-Queens. We achieve near identical performance to the ideal fixed grain executions on the first three but suffer from a more significant performance gap on the N-Queens problem. We advance hypotheses as to why.

Global load balancer libraries should be easy to use and allow users to easily obtain good performance for their applications on a variety of distributed systems. In this article, we introduce a new tuning mechanism to our Java implementation of the lifeline-based global load balancer which automatically adjusts the task granularity to reach good performance based on some selected runtime metrics. We evaluate our system against four backtrack-search problems on both a many-core supercomputer environment and on a beowulf server, achieving ideal performance with our tuning mechanism on the supercomputer. We also identify the limits of our mechanism in handling situations with reduced imbalance.