Dynamic Load Balancing Method Based on PBT Tree

Zhijie Lin, Chonghui Ren, Haifeng Huang, Xiaoyong Li2018 · DOI

Abstract

With the development of computer technology and GPU technology, hardware and software technology has been greatly developed, but a single PC machine still cannot meet the real-time computing requirements of high-complexity scenes. In this paper, we propose a dynamic load balancing strategy based on PBT tree for the load balancing problem of Sort-first architecture cluster computing system. The dynamic load balancing strategy is dynamically adjusted in real time according to the change of computing scenarios, addressing imbalances that prevent system performance improvements, making full use of system resources, and improving the overall performance of the system.

Introduction

In high-complexity 3D rendering, a single machine often lacks the power to maintain real-time frame rates. "Sort-first" cluster computing solves this by dividing the screen into blocks and assigning each block to a different node in a cluster. However, a simple static division (like a grid) is inefficient. If one node is assigned a block containing a complex 3D model while another gets a block of empty background, the first node becomes a bottleneck. The entire system must wait for the slowest node to finish. The challenge is to dynamically adjust these screen boundaries so that every node in the cluster finishes its task at roughly the same time, despite the scene changing as the camera moves.

Methodology: The Prediction Binary Tree (PBT)

The authors propose a feedback-driven approach using a Prediction Binary Tree (PBT). This method leverages the temporal continuity between animation frames, assuming that the computational cost of a specific screen area in frame n will be very similar to its cost in frame n-1.

The PBT Structure

The screen space is represented as a binary tree where the root represents the whole screen, and each branch represents a split. The leaf nodes correspond to the actual sub-blocks assigned to cluster nodes. By always dividing along the "longer side" of a block, the algorithm maintains better aspect ratios for the sub-blocks, which helps in maintaining spatial continuity and reduces communication overhead.

Illustration of screen partitioning (a) and its corresponding Prediction Binary Tree structure (b).

Initialization and Dynamic Updates

During the first frame, the system performs a "rough" estimate by marking pixels as 0 (empty) or 1 (containing geometry). It then recursively splits the screen until the number of leaf nodes matches the number of cluster nodes.

The iterative process of weight estimation and adjustment over successive frames.

After a frame is rendered, the cluster management node records the actual time spent by each node. This timing data is used to "weight" the pixels for the next frame. If a node was overworked, the PBT adjusts the split lines to give that node a smaller portion of the screen in the next frame. This "lazy" evaluation is much faster than calculating exact costs upfront and is highly accurate for continuous motion.

Experimental Evaluation

The researchers evaluated their method using the Li Buddha model, a complex 3D mesh consisting of 640,000 polygons. This model provides a high-density geometric workload suitable for testing load imbalances in a cluster environment. The method was tested on a cluster of 8 computing nodes.

Key Results

  • Performance Gain: The PBT-based dynamic load balancing improved overall system performance by approximately 51% compared to a system without load balancing.
  • Stability: Frame times became significantly more stable. In the "no load balancing" scenario, frame times fluctuated wildly as the model moved across different nodes' zones. With PBT, the workload stayed balanced regardless of the model's position on screen.

Conclusion and Future Work

While the PBT method offers significant improvements, the authors acknowledge that the initial estimation (the 0/1 pixel marking) is "rough." For algorithms like ray tracing, where a single pixel might trigger complex recursive calculations, this simple binary marking may not be enough for a smooth start. Additionally, the paper does not explore how the system handles scenes with sudden "cuts" in a sequence where space-time continuity is broken. Future work could involve more sophisticated initial weight estimations or adapting the PBT to handle "Sort-last" or hybrid architectures.

Summary updated

Abstract

With the development of computer technology and GPU technology, hardware and software technology has been greatly developed, but a single PC machine still cannot meet the real-time computing requirements of high-complexity scenes. In this paper, we propose a dynamic load balancing strategy based on PBT tree for the load balancing problem of Sort-first architecture cluster computing system. The dynamic load balancing strategy is dynamically adjusted in real time according to the change of computing scenarios, Balance caused by the system performance cannot be improved, make full use of system resources and improve the overall performance of the system.
BibTeX
@misc{lin2018dynamic,
  author = {Zhijie Lin and Chonghui Ren and Haifeng Huang and Xiaoyong Li},
  title = {{Dynamic Load Balancing Method Based on PBT Tree}},
  year = {2018},
  doi = {10.2991/ecae-17.2018.63},
}
Figure