Rate-distortion (RD)-based mode selections are important techniques in video coding. In these methods, an encoder may compute the RD costs for all the possible coding modes, and select the one which achieves the best trade-off between encoding rate and compression distortion. Previous papers have demonstrated that RD-based mode selections can lead to significant improvements in coding efficiency. RD-based mode selections, however, would incur considerable increases in encoding complexity, since these methods require computing the RD costs for numerous candidate coding modes. In this paper, we consider the scenario where software-based video encoding is performed on personal computers or game consoles, and investigate how multi-core graphics processing units (GPUs) may be efficiently utilized to undertake the task of RD optimized intra-prediction mode selections in audio and video coding standards and H. 264 video encoding. Achieving efficient GPU-based intra-mode decisions, however, could be nontrivial for two reasons. First, intra-mode decision tends to be sequential. Specifically, the mode decision of the current block would depend on the reconstructed data of the neighboring blocks. Therefore, the coding modes of neighboring blocks would need to be computed first before that of the current block can be determined. This dependency poses challenges to GPU-based computation, which relies heavily on parallel data processing to achieve superior speedups. Second, RD-based intra-mode decision may require conditional branchings to determine the encoding bit-rate, and these branching operations may incur substantial performance penalties when being executed on GPUs due to pipeline architectural designs. To address these issues, we analyze the data dependency in intra-mode decision, and propose novel greedy-based encoding orders to achieve highly parallel processing of data blocks. We also prove that the proposed greedy-based orders are optimal in our problem, i.e., they require the minimum number of iterations to process a video frame given the dependency constraints. In addition, we propose a method to estimate the coding rate suitable for GPU implementation. Experimental results suggest our proposed solution can be more than 50 times faster than the previously proposed parallel intra-prediction, since our work can efficiently exploit the massive parallel opportunity in GPUs.
