An efficient Markov chain-based data prefetching for motion estimation of HEVC on multi-core DSPs

As one of the most time-consuming parts of video coding, Motion Estimation (ME) has always been the major issue in the embedded coding system due to its memory-intensive nature. This is even truer now as the gap between processor and memory speed continues to grow in the embedded coding system on multi-core processors. In this paper, a data prefetching algorithm based on a Markov Chain Model (MCMDP) is presented to improve the data access efficiency for the ME of High Efficiency Video Coding (HEVC) on multi-core DSPs. First, by analyzing the process and features of ME, a new method of calculating Motion Vector Predictions (MVPs) is given, in which the coding block’s MVP is estimated from the MVPs of the reference picture instead of the motion vectors of the neighboring blocks. This is critical to improve the efficiency of data prefetching for ME because it eliminates the data dependencies that cause the latency of data prefetching. Second, the experimental results show that the probability distribution of the search windows in ME has continuity and locality in successive pictures, and these statistical properties are consistent with the characteristics of Markov chains. Therefore, a new model based on Markov chains is designed for predicting the prefetch window that covers the search window to improve the coverage of data prefetching. Finally, the experiments on TMS320C6678 demonstrate that the prefetching efficiency is significantly improved for the ME of HEVC on multi-core DSPs.