臺灣博碩士論文加值系統

由於繪圖晶片的快速發展，將繪圖晶片運用於非圖形的運算已漸漸成熟，使用GPU輔助CPU處理一般運算，此技術通稱為General-purpose computing on graphics processing units (GPGPU)，而NVIDIA公司在2007年提出一個全新GPGPU的繪圖處理器架構Compute Unified Device Architecture (CUDA)，藉由CUDA技術，可程式NVIDIA硬體多執行緒的GPU，以達到平行處理大量資料的運算，而我們的系統則採用NVIDIA GTX-280，其具有240個運算核心，作為我們實作平行演算法的實驗平台。
H.264/AVC正在進行的延伸標準multiview video coding (MVC)，其編碼器中最耗費運算時間的motion estimation (ME) 以及disparity estimation (DE)，我們提出一個可平行的快速演算法multithreaded one-dimensional search (MODS)，它可使用於ME以及DE，所以我們對編碼器中整數像素的ME以及DE實做MODS於NVIDIA GTX-280平台上，可加速約CPU版本的89倍，而使用CUDA加速的MODS與標準程式中的快速演算法相比，在使用ME與DE編碼的視訊也可加速達21倍。

Due to the rapid growth of the graphics processing unit (GPU) processing capability, it gets more and more popular to use it for non-graphics computations. NVIDIA announced a powerful GPU architecture called Compute Unified Device Architecture (CUDA) in 2007, which is able to provide massive data parallelism under the SIMD architecture constraint. We use NVIDIA GTX-280 GPU system, which has 240 computing cores, as the platform to implement a very complicated video coding scheme.
The Multiview Video Coding (MVC) scheme, an extension of H.264/AVC/MPEG-4 Part 10 (AVC), is being developed by the international standard team joined by the ITU-T Video Coding Experts Group and the ISO/IEC JTC 1 Moving Pictures Experts Group (MPEG). It is an efficient video compression scheme; however, its computational compexity is very high. Two of its most time-consuming components are motion estimation (ME) and disparity estimation (DE). In this thesis, we propose a fast search algorithm, called multithreaded one-dimensional search (MODS). It can be used to do both the ME and the DE operations. We implement the integer-pel ME and DE processes with MODS on the GTX-280 platform. The speedup ratio can be 89 times faster than the CPU only configuration. Even when the fast search algorithm of the original JMVC is turned on, the MODS version on CUDA can still be 21 times faster.

Table of Contents

摘要 i
Abstract .ii
Acknowledgement iv
Table of Contents vi
List of Tables viii
List of Figures x
Chapter 1 INTRODUCTION 1
1.1 Introduction 1
1.2 Motivation 3
1.3 Overview of the Thesis 4
Chapter 2 MULTIVIEW VIDEO CODING STANDARD 5
2.1 Overview of MVC Encoder 5
2.2 Motion and Disparity Compensation 5
2.3 Prediction Structures 11
2.3.1 Hierarchical B Pictures 11
2.3.2 Prediction Structures for Multi-view Video Coding 13
2.4 Reference Software 18
Chapter 3 COMPUTER UNIFIED DEVICE ARCHITECTURE (CUDA) 20
3.1 General-Purpose Computation on GPUs 20
3.1.1 GPU versus CPU 20
3.1.2 Overview of CUDA 23
3.2 Hardware Architecture of GT200 24
3.3 SIMT Programming Model 31
3.4 Mechanism of Scheduler 32
3.5 Performance Tuning 34
Chapter 4 MVC ENCODER ACCELERATION BY CUDA 36
4.1 Full-Search Motion Estimation 36
4.2 Multithreaded One-Dimensional Search 37
4.3 MODS Parallelized Implementation on NVIDIA CUDA 38
4.4 Maximize Parallel Execution 43
4.5 Data Dependency Problem 45
4.6 Encoder Implementation 47
4.7 Simulation Result 51
Chapter 5 CONCLUSIONS 66
5.1 Conclusions 66
5.2 Future Work 66
REFERENCES 68

REFERENCES

[1]A. Smolic and P. Kauff, “Interactive 3-D video representation and coding technologies,” in Proc. IEEE, vol. 93, no. 1, pp. 98–110, Jan. 2005.
[2]T. Fuji and M. Tanimoto, “Free-Viewpoint TV Systems Based on Ray-Space Representation,” in Proc. of SPIE, vol. 4864, pp. 175-189, Nov. 2002.
[3]Draft ITU-T Recommendation and Final Draft International Standard of Joint Video Specification, ITU-T Recommendation H.264 and ISO/IEC 14496-10 Std., 2003.
[4]Y. -S. H, and K. -J. O, "Overview of Multi-view Video Coding", IEEE International Conference on Signals and Image Processing, Multimedia Communications and Services, pp. 5-12, 2007
[5]A. Smolic, P. Merkle, K. M‥uller, C. Fehn, P. Kauff, and T. Wiegard, “Compression of multi-view video and associated data,” in Three Dimensional Television:Capture, Transmission, and Display, eds. H. Ozaktas and L. Onural, Springer, New York, 2007.
[6]E. Martinian, A. Behrens, J. Xin, A. Vetro, and H. Sun, “Extensions of H.264/AVC for multiview video compression,” in IEEE Int. Conf. on Image Processing, Atlanta, USA, Oct. 2006.
[7]L. Ding, P. Tsung, S. Chien, W. Chen, and L. Chen, "Content-Aware Prediction Algorithm With Inter-View Mode Decision for Multiview Video Coding", in IEEE Transactions on Circuits and Multimedia, vol. 10, no. 8, pp. 1553-1564, 2008.
[8]CUDA GPUs, http://www.nvidia.com/object/cuda_gpus.html
[9]W. -N. Chen, H. -M. Hang, “H.264/AVC motion estimation implementation on Compute Unified Device Architecture (CUDA)”, IEEE International Conference on Multimedia and Exposition, pp. 697-700, 2008.
[10]L. Chan, J. Lee, A. Rothberg, and P. Weaver, “Parallelizing H.264 Motion Estimation Algorithm using CUDA”, MIT IAP, 2009.
[11]B. Pietersa, C. F. Hollemeersch, P. Lambert, and Rik Van de Walle, “Motion Estimation for H.264/AVC on Multiple GPUs Using NVIDIA CUDA”, SPIE, vol. 7443, 2009.
[12]Y.-L. Huang, Y.-C. Shen and J.-L. Wu, “Scalable computation for spatially scalable video coding using NVIDIA CUDA and multi-core CPU”, Proceedings of the seventeen ACM international conference on Multimedia, pp. 61-370, 2009.
[13]P. Merkle, K. Muller, A. Smolic, and T. Wiegand, Efficient Compression of Multi-view Video Exploiting Inter-view Dependencies Based on H.264/MPEG4-AVC, IEEE International Conference on Multimedia and Exposition, Toronto, Ontario, Canada, July 2006.
[14]P. Merkle, A. Smolic, K. Muller, T. Wiegand, “Efficient Prediction Structures for Multiview Video Coding,” IEEE trans. on circuits and systems for video technology, vol. 17, no. 11, , pp. 1461-1473, Nov. 2007.
[15]H. Schwarz, D. Marpe, and T. Wiegand, “Analysis of hierarchical B pictures and MCTF”, IEEE International Conference on Multimedia and Exposition, Toronto, Ontario, Canada, July 2006.
[16]H. Pan and F. pan, “Development of multi-view video coding using hierarchical B pictures,” IEEE Congress on Image and Signal Processing, pp. 497-502, June 2008.
[17]Y. Chen, P. Pandit, and S. Yea, “WD 4 reference software for MVC,” ISO/IEC JTC/ISC29/WG11 and ITU-T Q6/SG16, Doc. JVT-AD207, Jan. 2009 (JMVC)
[18]http://thenextwavefutures.wordpress.com/2009/08/02/the-end-of-moores-law/
[19]http://en.wikipedia.org/wiki/Moore''s_law
[20]NVIDIA CUDA Programming Guide Version 2.2 4/2/2009
[21]http://www.xcpus.com/reviews/87-Unleash-the-Beast-Core-i7-and-X58-Page-1.aspx
[22]http://www.realworldtech.com/page.cfm?ArticleID=RWT090808195242
[23]NVIDIA CUDA, http://www.nvidia.com/object/cuda_home_new.html
[24]http://en.wikipedia.org/wiki/GPGPU
[25]NVIDIA The CUDA Compiler Driver NVCC Version 2.2 3/26/2009
[26]http://www.realworldtech.com/page.cfm?ArticleID=RWT090808195242&p=7
[27]W.-M. Hwu, and D. Kirk, ECE 498 AL1 Programming Massively Parallel Processors Lecture, University of Illinois at Urbana-Champaign, 2007. http://courses.ece.uiuc.edu/ece498/al1/
[28]NVIDIA CUDA C Programming Best Practices Guide Version July 2009.
[29]L.-G. Chen, W.-T. Chen, Y.-S. Jehng, and C.-T. Church, “An efficient parallel motion estimation algorithm for digital image processing,” IEEE Trans. Circuits and Systems for Video Tech, vol. 1, pp. 378–385, Dec. 1991.
[30]M. Harris, “Optimizing Parallel Reduction in CUDA,” NVIDIA Developer Technology, 2007.
[31]I.E.G. Richardson, H.264 and MPEG-4 Video Compression, John Wiley & Sons, 2003.
[32]T. Wiegand, G. J. Sullivan, G. Biontegaard, and A. Luthra, “Overview of the H.264/AVC Video Coding Standard,” IEEE Transactions on Circuit and System for Video Technology, vol. 13, Issue 7, pp. 560-576, Jul. 2003.
[33]Tourapis, H.-Y. Cheong; Tourapis, A.Michael, “Fast motion estimation within the H.264 codec”, IEEE International Conference on Multimedia and Exposition, July 2003.
[34]J. Vieron, M. Wien, and H. Schwarz, “JSVM 9 Software”, Dec. 2008.