zBalancer: a Dual-Function CPU Load Balancer for NUMA Architectures

Abstract

CPU load balancing is an important function of task dispatcher, particularly in future Non-Uniform Memory Access (NUMA) architectures. Because in NUMA architectures tasks are dispatched to the same (sets of) CPUs as much as possible to avoid high cost of inter-memory access latency. Traditional load balancing mechanism faces a dilemma: it must run frequently enough to reduce the impact of imbalance between each run yet, being on the critical performance path of task dispatching, it must not impose undue overhead on the dispatcher. The general approach taken is to run the load balancing algorithm at a moderate interval, e.g., on the order of milliseconds, and to keep the algorithm very simple, e.g., using average run queue length as CPU load indicator. This causes two problems: (1) as CPUs become faster, even milliseconds are relatively long period; (2) simple CPU load indicator such as average run queue length does not always correctly reflect CPU load. We propose zBalancer, a dual-function load balancer that resolves this dilemma. zBalancer consists of a simple and fast crossover which runs whenever the dispatcher runs, and a more sophisticated and slower balancer which runs periodically on the order of seconds. The crossover allows quick response to temporary CPU spike while the balancer provides advanced balancing features for sustained CPU imbalance. We have implemented zBalancer and evaluated its performance with both trace-driven simulation and real machine test. zBalancer is shipped in the latest IBM System z10 flagship mainframe.