Array Partitioning and Load-Balancing Algorithms with Applications to Video Compression

In the array partitioning problem, the goal is to split an array into a tile grid of given dimensions so that the maximum tile weight, computed as the aggregation of array cell weights, is minimized. Although the problem has attracted much research interest (for instance, in image processing), it has only recently become relevant to video compression after the introduction of tiles in high-efficiency video coding (HEVC). In this context, the basic problem statement is not agile enough, since it assumes grid dimensions are known, while the optimization target lends itself to the case in which the number of available processors equals the number of tiles. In this paper, we study the problem of array partitioning with unknown grid dimensions. The goal is to create a grid that contains bounded number of tiles T, and its scheduling on P processors results on minimizing makespan. We tackle the problem from the standpoint of proposing fast and easily implementable algorithms that offer good speedup and can be easily ported to existing video codecs without incurring prohibitive time overhead. The latter is particularly important, since the algorithms are meant to run upon every frame and adapt tile sizes according to weight estimates. Experiments with the reference software of HEVC illustrate the merits of our approach.