视频应用中运动估计算法的并行与访存优化研究

High-definition video develops fast, and it is a key problem to improve the processing speed of video applications. Motion estimation (ME) is a kernel of video applications. It usually takes most of the execution time and becomes the performance bottleneck for video applications. We plan to improve the performance of ME through inter-frame and intra-frame data reuse, collective optimization of parallelization and memory access, and auto-tuning. (1) To reduce the demand of off-chip memory access, we study the high efficiency data reuse method. The off-chip memory traffic of full search ME is reduced through inter-frame data reuse. The overhead of irregular memory access for fast search ME is reduced through intra-frame data reuse. (2)To relieve the competition for shared memory and off-chip memory bandwidth, we study the collective optimization for parallelization and memory access. The on-chip data sharing among different computing units is exploited to reduce the competition for on-chip memory. The off-chip memory bandwidth is effectively utilized through achieving the best match between parallelism degree and memory bandwidth. (3) To reduce the overhead of human optimization, we study the auto-tuning of ME. The best performance is achieved by the automatic search of algorithm or hardware parameters. We will implement the above optimization methods on GPU and FPGA. The performance of ME is supposed to be improved greatly for real-time high-definition video applications.

人们对高清视频的需求日益增长，提高视频处理速度成为视频应用发展的关键问题。运动估计是视频应用的核心算法，但其时间耗费大，成为性能瓶颈。本项目拟从帧间与帧内数据重用、并行与访存协同优化、自动调优等方面开展运动估计的性能优化研究：（1）针对片外访存需求过大的问题，研究更高效的数据重用方法，通过帧间数据重用减少全搜索运动估计的片外访存，通过帧内数据重用减少快速搜索运动估计的非规则访存开销。（2）针对多计算单元对共享存储空间和片外访存带宽的竞争问题，研究运动估计算法并行与访存的协同优化，通过计算单元之间的片上数据共享减少对片上存储的竞争，通过提升并行度与访存带宽之间的匹配度有效利用访存带宽。（3）针对手动调优时间耗费大的问题，研究运动估计算法的自动调优，通过自动选择算法或硬件参数，达到最优性能。在GPU和FPGA平台上实现上述优化方法，将大幅提升运动估计算法的性能，满足高清、实时的视频处理需求。

随着视频应用的快速发展，实时视频处理成为一个重要问题。运动估计是视频应用的核心算法，其时间耗费大，成为视频应用的性能瓶颈。因此，对运动算法进行优化能够极大地提高视频处理速度。本项目从参考帧之间的数据重用、快速搜索运动估计访存优化、运动估计算法的循环优化等方面进行了研究，具体如下：.（1）帧频提升作为运动估计的一个应用场景，现有方法中每一帧图像都要从片外存储中读取两次，第一次作为当前帧，第二次作为前一帧。如果每帧图像只被读取一次，则片外访存将会大大减少。本项目分析了运动估计算法数据访问的时间局部性，利用参考帧之间的可重用数据降低全搜索运动估计的片外访存开销，提出了Inter-E、Inter-D、Inter-C等参考帧之间的数据重用方法。.（2）在以往的研究中，较少考虑到在快速搜索运动估计中采用数据重用。快速搜索算法虽然比全搜索算法搜索速度更快，但仍然要花费较多的时间，其主要原因在于快速搜索算法的访存不规则性，增加了存储器访问的次数。本项目提出了快速搜索运动估计搜索区之间的数据重用方法，充分利用了参考帧内部的可重用数据，进而提高快速运动估计算法的性能。快速搜索运动估计算法的第一步搜索是固定的，所以相邻搜索区之间存在确定的重用数据区。在第二步搜索时，需要依靠第一步的结果确定搜索中心，而第一步的结果是不确定的，从而导致第二步的搜索结果也无法确定，因此存在不确定的数据重用区。根据这一特性，本项目将快速搜索运动估计算法的搜索区域划分为可能的和确定的重用数据区。.（3）本项目提出了针对块匹配运动估计的两种循优化方法，循环展开和循环分割，提高了运动估计算法的速度。通过循环展开，以增加程序尺寸的代价，减少了循环分支开销，加快了程序执行速度。通过循环分割，将一次迭代分割成两个或更多的部分，通过提高指令级的并行性来提高运动估计性能。