Dynamic screen division for load balancing the raycasting of irregular data

Parallel rendering algorithms usually suffer from high load imbalance during execution, due to the irregular nature of the datasets. In this paper, we propose a new load balancing scheme for tile-based parallel rendering that includes strategies for load estimation, tile decomposition and tile assignment. The load estimation strategy computes the rendering cost for each pixel, and uses it as a prediction for the next frame. The tile decomposition strategy adaptively divides the screen into tiles based on the computed costs, until an evenly tile partition is achieved. The tile assignment strategy distributes the tiles among rendering processors, based on a 2-optimal scheduling. Experimental results show that our scheme achieves significant performance gains by reducing the load imbalance when compared to the traditional tile subdivision and static random distribution schemes.