本文呈現了一個創新的電子系統層級演算法暨架構共同探索設計方法論，這個設計方法論可以應用於同時探索日益複雜的視訊運算系統中演算法跟架構的開發。演算法複雜度分析 協同多重精細度資料流模型在同時最佳化演算法及架構中扮演著相當重要的角色。為了在系統設計的初期階段就將必要的架構資訊展現出來，複雜度的度量必須具備有效特徵化演算法本質上複雜度的特性，也就是說，這些複雜度量測必須不受實現時細節或者是設計限制所影響，當然也不可以偏頗於軟體或硬體實現。本論文基於演算法資料流模型的特徵值分解，有系統地探討及量化了重要的演算法本質複雜度，其中包含運算量、平行度、資料流量以及儲存組態和使用量等，並將其應用於電子系統層級設計。這些被萃取出來的複雜度可以有效地呈現出架構上潛在特性進而幫助修改或最佳化演算法。此外，本文也探討了演算法複雜度之間的交互作用，進而擴大架構的設計空間。基於本設計方法論，本文亦呈現了一些個案研究的成果，實驗結果顯示出本文提議之方法論除了可以精準地特徵化演算法本質複雜度進而揭露高抽象層級的架構資訊外，還可以有效率地幫助視訊運算系統在不同平台上設計空間的探索，而這些平台包含了特殊應用積體電路、可規劃邏輯閘陣列、可重組態架構、單晶片系統、以及多核心平台等。受惠於演算法暨架構共同探索，本文針對高畫質即時視訊運算的應用，提出了較佳的離散小波轉換在單指令多資料機器上的實現、高品質低成本的移動估計器積體電路實現、高效能幀率提升技術在可規劃邏輯閘陣列上的實現以及高解析度解交錯器在低成本消費電子多核心平台上的實現。這些較佳的系統實現佐證了本文提出之設計方法的優點以及貢獻。

This thesis presents a novel Algorithm/Architecture Co-exploration (AAC) design methodology that can concurrently explore both algorithms and architectures for the increasingly complex visual computing systems required for high-quality applications. Algorithmic complexity analysis and dataflow modeling at various granularities play significant roles in the presented concurrent optimization of both algorithms and architectures. To extract essential architectural information in early design stages and thus optimize the targeted architectures or platforms, the complexity measurements must be intrinsic. That is, they should be transparent to implementation details or design constraints and of course unbiased with regard to either hardware or software. This thesis introduces important intrinsic complexity measurements, including the number of operations, degree of parallelism, data transfer rate, and storage configuration. To accurately quantify the intrinsic algorithmic complexity, this thesis presents a systematic complexity analysis framework based on the eigen-decomposition of dataflow graphs at multiple granularities. The extracted complexity can reveal sufficient architectural information, enabling early back-annotation for modifying algorithms. In addition, this thesis also discusses the interplay among four complexity metrics, which significantly enlarges the architectural space. Several case studies based on the novel AAC methodology for electronic system level (ESL) design are also presented. Experimental results reveal that the introduced methodology can not only accurately characterize the algorithmic complexity but also facilitate the design space exploration of visual computing systems for generic platforms or architectures such as application-specific integrated circuits (ASICs), field-programmable gate arrays (FPGAs), reconfigurable architectures, and system-on-a-chip (SoC), single-processor, single instruction multiple data (SIMD), and multicore systems. Using the innovative AAC methodology, this thesis presents a better porting of the discrete wavelet transform onto SIMD; a high-quality, low-cost motion estimation ASIC; an efficient frame rate up-convertor on an FPGA; and a high-resolution de-interlacer on a low-cost consumer multicore platform for real-time visual computing applications. The significantly enhanced mapping of algorithms onto various platforms reveals the advantages and contributions of the presented design methodology.

[1] M.H. Chan, Y.B. Yu, A.G. Constantinides, “Variable size block matching motion compensation with applications to video coding”, IEE Proceedings, vol 137, Pt. 1, No. 4, pp. 205-212, August 1990.
[2] T. Wiegand, X. Zhang, and B. Girod, “Long-term memory motion-compensated prediction,” IEEE Trans. Circuits and Systems for Video Technology, vol. 9, pp. 70–84, Feb. 1999.
[3] J. M. Boyce, “Weighted prediction in the H.264/MPEG AVC video coding standard,” in Proc. ISCAS2004, vol. 3, pp. 789–792, May 2004.
[4] D. Wang, “Improvement of H26L Intra Block Prediction,” ITU-T Q.6/SG16 VCEG-L09, Germany January, 2001.
[5] G. G. Lee, H.-Y. Lin and M.-J. Wang, “Rate control algorithm based on intra-picture complexity for H.264/AVC,” IET Image processing, vol.3 no.1, pp. 26-39, Feb. 2009.
[6] P. Chenn, Y. Ye, and M. Karczewicz, “Video coding using extended block sizes”, ITU-T Q.6/SG16 VCEG, COM16-C123, Geneva, CH, January 2009.
[7] A. Tanizawa, T. Chujoh, “Adaptive Quantization Matrix Selection”, ITU-T Q.6/SG16 VCEG, D.266, April 2006.
[8] G. G. Lee, H.-Y. Lin and M.-J. Wang, “Textural Complexity-Based Rate Control Algorithm,” in Proc. IEEE ICME 2008, pp. 1109-1112, April, 2008.
[9] H.-Y. Lin, G. G. Lee, M.-J. Wang, D. W.-C. Su and B.-Y. Lin, “Model-Based Optimal Rate Control Algorithm for Real-Time Hybrid Video Encoder,” in Proc. IEEE ISCAS 2006, pp. 4455-4458, May 2006.
[10] G. G. Lee, H.-Y. Lin, D. W.-C. Su and M.-J. Wang, “Multiresolution-based texture adaptive algorithm for high-quality deinterlacing,” IEICE Trans. Information and System, vol. E 90-D, no. 11, pp. 1821-1830, Nov. 2007.
[11] G. G. Lee, H.-Y. Lin, M.-J. Wang, R.-L. Lai, C. W. Jhuo and B.-H. Chen, “Spatial-temporal content-adaptive deinterlacing algorithm,” IET Image processing, vol. 2, no. 6, pp. 323-336, December 2008.
[12] M. Biswas, S. Kumar, and T. Q. Nguyen, “Performance analysis of motion compensated de-interlacing system,” IEEE Trans. Image Processing, vol. 15, no. 9, pp. 2596-2609, Sept. 2006.
[13] K. Hilman, H. W. Part, Y. Kim, “Using motion-compensated frame-rate conversion for the correction of 3:2 pulldown artifacts in video sequences,” IEEE Trans. Circuits and Systems for Video Technology, vol. 10, no. 6, pp. 869–877, Sept. 2000.
[14] B.-D. Choi, J.-W. Han, C.-S. Kim, and S.-J. Ko, “Motion-compensated frame interpolation using bilateral motion estimation and adaptive overlapped block motion compensation,” IEEE Trans. Circuits and Systems for Video Technology, vol. 17, no. 4, pp. 407–416, Apr. 2007.
[15] Y.-W. Huang, B.-Y. Hsieh, S.-Y. Chien, S.-Y. Ma, and L.-G. Chen, “Analysis and Complexity Reduction of Multiple Reference Frames Motion Estimation in H.264/AVC,” IEEE Trans. Circuits and Systems for Video Technology, vol. 16, no. 4, pp. 507-522, April 2006.
[16] J. Ostermann, J. Bormans, P. List, D. Marpe, M. Narroschke, F. Pereira, T. Stockhammer, and T. Wedi, “Video coding with H.264/AVC: tools, performance, and complexity,” IEEE Circuits and Systems Magazine, vol. 4, issue 1, pp. 7-28, 2004.
[17] K. P. Lim and G. Sullivan, “Text Description of Joint Model Reference Encoding Methods and Decoding Concealment Methods,” ISO/IEC JTC1/SC29/WG11and ITU-T Q.6/SG16, JVT-K049, Germany, 2004.
[18] J. Ostermann and M. Narroschke, “Motion compensated prediction with 1/8-pel displacement vector resolution,” ITU-T Q.6/SG16, VCEG-AD09, Hangzhou, China, October 2006.
[19] Y. Vatis and J. Ostermann, “Prediction of P- and B-frames using a two-dimensional non-separable adaptive Wiener interpolation filter for H.264/AVC,” ITU-T Q.6/SG16, VCEG-AD08, Hangzhou, China, October 2006.
[20] S. Wittmann and T. Wedi, “Separable adaptive interpolation filter”, ITU-T Q.6/SG16 VCEG, COM16-C219, Geneva, CH, June 2007
[21] D. Rusanovskyy, K. Ugur and J. Lainema, “Adaptive interpolation with directional filter,” ITU-T Q.6/SG16, VCEG-AG21, Shenzhen, China, October 2007.
[22] T. Chujoh N. Wada and G. Yasuda, “Quadtree-based adaptive loop filter”, ITU-T Q.6/SG16 VCEG, COM16-C181, Geneva, CH, January 2009.
[23] C. K. Koc, G. Chen, and C. K. Chui, “Complexity analysis of wavelet signal decomposition and reconstruction,” IEEE Trans. Aerospace and Electronic System, vol. 30, no. 3, pp. 910–918, July 1994.
[24] S. Bouguezel, M. O. Ahmad and M.N.S. Swamy, “Arithmetic complexity of the split-radix FFT algorithms,” IEEE ICASSP2005, vol. 5, pp. v-137-v-140, 2005.
[25] Y. Ye and M. Karczewicz, “Improved Intra Coding,” ITU-T Q.6/SG16, VCEG-AG11, Shenzhen, China, October 2007.
[26] Y. Ye and M, Karczewicz, “Improved h.264 intra coding based on bi-directional intra prediction, directional transform, and adaptive coefficient scanning,” in Proc. IEEE ICIP 2008, pp. 2116-2119, Oct. 2008.
[27] A. Materka and M. Strzelecki, “Texture analysis methods - a review,” in COST B11 report, Institute of Electronics, Technical University of Lodz. 1998.
[28] MPEG, “Vision and Requirements for High-Performance Video Coding (HVC) Codec,” ISO/IEC JTC1/SC29/WG11/N10361, Lausanne, Suisse, February 2009.
[29] MPEG, “Call for test materials for future high-performance video coding standardization,” ISO/IEC JTC1/SC29/WG11/N10362, Lausanne, Switzerland, February 2009.
[30] MPEG, “Draft Call for Proposals on High-Performance Video Coding (HVC),” ISO/IEC JTC1/SC29/WG11/N10722, London, UK, July 2009.
[31] G. Sullivan, “Report of San Diego VCEG meeting,” ITU-T Q.6/SG16, VCEG-AJ01_d2, San Diego, October 2008.
[32] G. G. Lee, Y.-K. Chen, M. Mattavelli, and E. S. Jang, “Algorithm/architecture co-exploration of visual computing: overview and future perspectives,” IEEE Trans. Circuits and Systems for Video Technology, vol. 19, no. 11, pp. 1576-1587, Nov. 2009.
[33] G. G. Lee, M.-J. Wang, H.-Y. Lin and R.-L. Lai, “On the efficient algorithm/architecture co-exploration for complex video processing,” in Proc. IEEE ICME 2008, pp. 1057-1060, June 2008.
[34] G. G. Lee, M.-J. Wang, H.-Y. Lin, Drew W. C. Su and B.-Y. Lin, “Algorithm/architecture co-design of 3D spatio-temporal motion estimation for video coding.” IEEE Tran. on Multimedia, vol. 9, iss. 3, pp. 455-465, April 2007.
[35] G. G. Lee, H.-Y. Lin, M.-J. Wang, B.-H. Chen and Y.-L. Cheng, “On the verification of multi-standard SoC’s for reconfigurable video coding based on algorithm/architecture co-exploration,” in Proc. IEEE SiPS 2008, pp. 170-175, Oct. 2008.
[36] R. W. Schaefer and A. V. Oppenheim, Discrete-Time Signal Processing. Englewood Chliffs, NJ: Prentice-Hall, 1989.
[37] S. Edeards, L. Lavagno, E. A. Lee, and A. Sangiovanni-Vincentelli. Design of embedded systems: Formal models, validation and synthesis. Proceedings of the IEEE, 85(3): 366-390, March 1997.
[38] G. G. Lee, E. S. Jang, M. Mattavelli, M. Raulet, C. Lucarz, H. Kim, S. Lee, H.-Y. Lin, J. Janneck, D. Ding, and C-J. Tsai, “Text of ISO/IEC FDIS 23001-4: Codec Configuration Representation,” Information technology — MPEG systems technologies — Part 4: Codec configuration representation, 2009.
[39] H. S. Shin, Y.-S. Tung, C. Lucarz, K. Sugimoto, M. Raulet, Y. Yamada, H.-Y. Lin, Y.-L. Cheng, and M. Mattavelli, “Text of ISO/IEC FDIS 23002-4: Video Tool Library,” Information technology — MPEG video technologies — Part 4: Video tool library, 2010.
[40] G. G. Lee, C. Lucarz, H.-Y. Lin, “Study of ISO/IEC 23002-4/FPDAM1 Video Tool Library Conformance and Reference Software,” ISO/IEC JTC1/SC29/WG11 MPEG w10921, Xian, China, Oct. 2009. (will be an ISO/IEC international standard in Oct. 2010)
[41] V. Mathur and V. Prasanna, “A hierarchical simulation framework for application development on system-on-chip architectures,” in Proc. IEEE Int. ASIC/SOC Conf., 2001, pp. 428–434, Sept. 2001.
[42] L. Benini, D. Bertozzi, D. Bruni, N. Drago, F. Fummi, and M. Poncino,“SystemC cosimulation and emulation of multiprocessor SoC designs,” Computer, vol. 36, no. 4, pp. 53–59, Apr. 2003.
[43] L. Thiele, S. Chakraborty, M. Gries, and S. Künzli, “A framework for evaluating design tradeoffs in packet processing architectures,” in Proc. ACM IEEE DAC 2002, pp. 880–885, June 2002.
[44] G. Kahn, “The semantics of simple language for parallel programming,” in Proc. IFIP Congress, Vol. 74, pp. 471–475, 1974.
[45] E. A. de Kock, W. J. M. Smits, P. van der Wolf, J.-Y. Brunel, W. M. Kruijtzer, P. Lieverse, K. A. Vissers, and G. Essink, “YAPI: application modeling for signal processing systems,” in Proc. IEEE DAC 2000, pp. 402-405, June 2000.
[46] M. Chiodo, P. Giusto, H. Hsieh, A. Jurecska, L. Lavagno, and A. Sangiovanni-Vincentelli. “A formal methodology for hardware/software codesign of embedded systems,” IEEE Micro, vol. 14, no. 4, pp. 26-36, Aug. 1994.
[47] G. M. Amdahl, “Validity of single-processor approach to achieving large-scale computing capability,” in Proc. AFIPS Conference, pp.483-485, Apr. 1967.
[48] V. Escuder, R. Duran, R. Rico, “Quantifying ILP by means of graph theory,” Proceedings of the 2nd international conference on performance evaluation methodologies and tools, 2007.
[49] A. Prihozhy, M. Mattavelli and D. Mlynek, “Evaluation of the parallelization potential for efficient multimedia implementations: dynamic evaluation of algorithm critical path,” IEEE Trans. Circuits and Systems for Video Technology, vol. 15, no. 5, pp. 593–608, May 2005.
[50] S. Y. Kung, VLSI Array Processor. Prentice Hall, 1988.
[51] J. W. Janneck, D. Miller and D. B. Parlour, “Profiling dataflow programs,” in Proc. IEEE ICME 2008, pp. 16065-1068, June 2008.
[52] K. K. Parhi., VLSI digital signal processing systems: design and implementation, New York: Wiley, 1999.
[53] B. Hendrickson and T. G. Kolda, “Graph partitioning models for parallel computing,” Parallel Computing, 26, pp. 1519–1534, 2000.
[54] B. L. Chamberlain, “Graph partitioning algorithms for distributing workloads of parallel computations,” Technical report UW-CSE-98-10-03, University of Washington, Oct 1998.
[55] H. D. Simon, “Partitioning of unstructured problems for parallel processing”, Proc. Conference on Parallel Methods on Large Scale Structural Analysis and Physics Applications,1991
[56] B. Hendrickson and R. Leland, “An improved spectral graph partitioning algorithm for mapping parallel computations,” Technical report SAND92-1460, Sandia National Laboratories, Albuquerque, NM, 1992.
[57] B. Mohar, “The Laplacian spectrum of graphs,” Graph Theory, Combinatorics, and Applications, vol. 2, pp. 871-898, 1991.
[58] A. Pothen, H.D. Simon, and K.P. Liou, “Partitioning sparse matrices with eigenvectors of graphs,” SIAM J. Matrix Analytical Applications, vol. 11, pp. 430-452, 1990.
[59] M. Ravasi and M. Mattavelli, “High-abstraction level complexity analysis and memory architecture simulations of multimedia algorithms,” IEEE Trans. Circuits and Systems for Video Technology, vol. 15, no. 5, pp. 673–684, May 2005.
[60] M. C. McFarland, A. C. Parker, and R. Camposano, “The high level synthesis of digital system,” Proc. IEEE, vol. 78, no. 2, p.p. 301-318, Feb. 1990.
[61] F. Balasa, F. Catthoor, and H. De. Man, “Background memory area estimation for multidimensional signal processing systems,” IEEE Trans. VLSI Systems, vol. 3, no. 2, pp. 157-172, June 1995.
[62] P. G. Kjeldsberg, F. Catthoor, E. J. Aas, “Storage requirement estimation for data intensive applications with partially fixed execution ordering,” Proceedings of 8th International Workshop on Hardware/Software Codesign, San Diego, pp56-60, May 3-5, 2000.
[63] Danckaert, K., F. Catthoor, and H. De Man, “A preprocessing step for global loop transformations for data transfer and storage optimization,” in Proc. ACM CASES 2000, pp. 34–40. Nov. 2000.
[64] F. R. K. Chung, Spectral Graph Theory, Regional Conferences Series in Mathematics, No. 92, 1997.
[65] M. Fiedler, “Algebraic connectivity of graphs,” Czech. Math. J., vol. 23, No.2, pp. 298-305, 1973.
[66] D.B. West, Introduction to Graph Theory, second ed., Prentice Hall, Upper Saddle River, NJ, 2001.
[67] W. Sweldens, “The lifting scheme: A custom-design construction of biorthogonal wavelets,” J. Appl. Comput. Harmonic Analysis, vol.3, no.2, pp. 186–200, 1996.
[68] http://software.intel.com/en-us/intel-compilers/
[69] W. A. Chen, C. Harrison, and S. C. Fralick, “A Fast computational Algorithm for the Discrete Cosine Transform,” IEEE Tran. Communications, vol. COM-25, No. 9, pp. 1004-1011, 1977.
[70] C. Chrysafis and A. Ortega, “Line-based, reduced memory, wavelet image compression,” IEEE Trans. Image Processing, vol. 9, no. 3, pp. 378–389, Mar. 2000.
[71] W. Jiang and A. Ortega, “Lifting factorization-based discrete wavelet transform architecture design,” IEEE Trans. Circuits and Systems for Video Technology, vol. 11, no. 5, pp. 651–657, 2001.
[72] H. Yamauchi et al., “Image processor capable of block-noise-free JPEG2000 compression with 30 frames/s for digital camera applications,” in Proc. IEEE ISSCC 2003, pp. 46–47, Feb. 2003.
[73] C.-T. Huang, P.-C. Tseng, and L.-G. Chen, “Analysis and VLSI architecture for 1-D and 2-D discrete wavelet transform,” IEEE Trans. Signal Processing, vol. 53, no. 4, pp. 1575–1586, April 2005.
[74] Target http://www.retarget.com/
[75] Y. Nie and K. Ma, “Adaptive irregular pattern search with matching prejudgment for fast block-matching motion Estimation,” IEEE Trans. Circuits and Systems for Video Technology, vol. 15, no. 6, pp. 789–794, Jun. 2005.
[76] C. Zhu, X. Lin, L. Chau, and L. Po, “Enhanced hexagonal search for fast block motion estimation,” IEEE Trans. Circuits and Systems for Video Technology, vol. 14, no. 10, pp. 1210–1214, Oct. 2004.
[77] Y. Murachi, K. Hamano, T. Matsuno, J. Miyakoshi, M. Miyama, and M. Yoshimoto, “A 95 mW MPEG2 MP@HL motion estimation processor core for portable high-resolution video application,” IEICE Trans. Fund. Electron. Commun. Comput. Sci., vol. E88-A, pp. 3492–3499, Dec. 2005.
[78] Zhu, X Lin, and L.P. Chau, “Hexagon-based search pattern for fast block motion estimation,” IEEE Trans. Circuits and Systems for Video Technology, vol.12, pp. 349-355, May 2002.
[79] K. R. Namuduri, “Motion estimation using spatio-temporal contextual information,” IEEE Trans. Circuits and Systems for Video Technology, vol. 14, pp. 1111-1115, Aug. 2004.
[80] V. Bhaskaran, K. Konstantinides, Image and video compression standards algorithms and architectures, Second Edition, Kluwer Academic Publishers, 1997.
[81] A. Segall, J. Zhao, “Entropy slices for parallel entropy decoding”, ITU-T Q.6/SG16 VCEG, COM16-C405, Geneva, CH, Apr. 2008.
[82] G. de haan, and E. B. Bellers, “Deinterlacing – an overview,” Proceedings of the IEEE, vol. 86, iss. 9, pp. 1839–1857, Sept. 1998.
[83] G. G. Lee, H.-Y. Lin, M.-J. Wang, R.-L. Lai and C. W. Jhuo, “A High-Quality Spatial-Temporal Content-Adaptive Deinterlacing Algorithm,” in Proc. IEEE ISCAS 2008, pp. 2594-2597, May 2008.
[84] H. Y. Lee, J. W. Park, T. M. Bae, S. U. Choi, and Y. H. Ha, “Adaptive scan rate up-conversion system based on human visual characteristics,” IEEE Trans. Consumer Electronics, vol. 46, iss. 4, pp. 999–1006, Nov. 2000.
[85] S.-F. Lin, Y.-L. Chang, and L.-G. Chen, “Motion adaptive interpolation with horizontal motion detection for deinterlacing,” IEEE Trans. Consumer Electronics, vol. 49, no. 4, pp. 1256–1265, Nov. 2003.
[86] L. Yu, J. Li, Y. Zhang and Y. Shen, “Motion adaptive deinterlacing with accurate motion detection and anti-aliasing interpolation filter,” IEEE Trans. Consumer Electronics, vol. 52, no. 2, pp. 712-717, May 2006.
[87] G. De Haan, “De-interlacing image signals,” US-patent 6,618,094 B1, Sep. 2003.
[88] M. Weston, “Interpolating lines of video signals,” US-patent 4,789,893, Dec. 1988.
[89] Y.-L. Chang, S.-F. Lin, and L.-G. Chen, “Extended intelligent edge-based line average with implementation and test method,” in Proc. international symposium on consumer electronics 2004, pp. 3341-344, May 2004.
[90] Y. Shen, D. Zhang, Y. Zhang, and J. Li, “Motion adaptive deinterlacing of video data with texture detection,” IEEE Trans. Consumer Electronics, vol. 52, no. 4, pp.1403-1408, Nov. 2006.