臺灣博碩士論文加值系統

軟硬體劃分的決策精確度正扮演著新興嵌入式系統SOC設計專案成敗的關鍵角色。當下，多採用萬用啟發式(metaheuristic)演算法如GA與PSO來進行這類問題的決策輔助。然而，啟發式演算法很難以單一個適配數值(fitness value)來表達決策點中各項指標(效能、成本、功率消耗、通訊延遲、與晶片面積等)的品質，故而有很大的機率會得到不好的決策。本文提出HFTG(Hot Function Task Group)特徵萃取的創新方法，改善傳統的啟發式演算法的決策效率，可有效避免啟發式方法的決策陷阱而降低其設計空間複雜度。首先探討系統函式區塊關係圖的結構，接著基於介面通訊成本考量修改適配函式來分段篩選群組，去除部份不符合通訊成本的決策點，然後將剩餘的系統函式控制資料流程圖(CDFG)與特性參數交由後續的啟發式演算法實現軟硬體劃分決策。研究案例引用前瞻視訊壓縮標準H.264 Encoder (JM Code)的設計方案來驗證HFTG特徵萃取演算的成效。實驗結果，HFTG萃取演算由H.264編碼器的163個函式中選取79個函式區塊，得到6組佔有系統一半以上執行時間的HFTG群組。這證明HFTG特徵萃取能使傳統軟硬體劃分方法確實選出擁有軟硬體介面相對單純的硬體區塊，並且極大的避免不當的軟硬體函式呼叫，這種輔助決策方法使軟硬體共同設計中有價值的硬體函式區塊較容易被正確切割與實現。

The decision accuracy of hardware/software partitioning is now playing a key role towards success for an embedded system design. Recently, meta-heuristic algorithms such as GA or PSO are often exploited for solving the decision problems. Unfortunately, the use of single fitness value for the algorithm is difficult to present the design quality that concerned the factors of performance, cost, power consumption, communication latency and chip area, etc. So that bad decisions are often obtained. In this paper, we proposed a novel Hot Function Task Group (HFTG) feature extract algorithm to improve the decision efficiency of meta-heuristic algorithms. The goal is originally to avoid the trap of decision and then reduce the complexity of design space. First, we explore the call-graph structure for the functions in a system. Next, we modify fitness function based-on the cost of interface communications to extract groups. Then delete the decision points that have high communication cost to them. Finally, the control-data-flow-graph (CDFG) of the rest functions and the features are delivered to the meta-heuristic algorithms for hardware-software partitioning. For testing the efficiency of the algorithm, a JM-code of H.264 encoder, the advanced video coding standard, is employed as the study case. While extracting 79 functions from 163 functions of H.264, it results in obtaining six groups of HTFGs which occupying more than half of the system execution time. It revealed that HTFG feature extraction method chooses the blocks with high complexity and relatively simple interfaces for accelerating and avoids un-proper hardware-software calling style. The HTFG method that can do correct partition and implementation for functions in a system is proved to be valuable in the field of hardware/software co-design.

中文摘要 iv
英文摘要 v
誌謝 vi
目錄 vii
表目錄 ix
圖目錄 x
第一章 序論 1
1 1 研究背景 1
1 2 研究動機與目的 2
1 3 論文架構 5
第二章 實驗相關工作探討 7
2 1 軟硬體共同設計(Software Hardware Co-design)簡介 7
2 2 軟硬體劃分介紹 9
2 3 目標系統規格參數的側錄 12
2 3 1 側錄工具介紹 12
2 3 2 側錄工具：GNU gprof 13
2 3 3 目標系統規格參數的側錄 14
2 4 先進的設計空間探索演算法 18
2 4 1 GA-based algorithm for hardware/software
partitioning with resource contentions 19
2 4 2 Modeling communication cost and hardware
alternatives in PSO based HW/SW partitioning 22
第三章 目標問題描述與定義 24
3 1 目標系統架構 24
3 2 目標問題描述與假設 25
3 2 1 軟硬體單元分佈之於通訊介面規劃的困難點 25
3 2 2 萬用啟發式演算法對映於軟硬體通訊介面決策上的不足 30
3 2 3 以分段篩選的方式改善啟發式方法於通訊考量上的弱點 33
3 2 4 目標問題正式定義 36
第四章 方法論 41
4 1 函式關係圖生成(Graph Generation) 41
4 2 價值估測(Value Estimation) 43
4 2 1 係數正規劃(Normalized coefficients) 43
4 2 2 價值估測(Value estimation) 44
4 2 3 HFTG擷取(HFTG Extraction) 45
第五章 實驗數據探討 49
5 1 H 264編碼器簡介與演算量分佈探討 49
5 2 H 264編碼器的HFTG特徵萃取演算 50
5 3 HFTG序列的軟硬體劃分 55
5 4 介面規劃與架構設計探討 58
第六章 結論 64
參考文獻 66
附錄 69

Reference
[1]A. Kalavade and E. A. Lee, "The extended partitioning problem: hardware/software mapping and implementation-bin selection," in Rapid System Prototyping, 1995. Proceedings., Sixth IEEE International Workshop on, 1995, pp. 12-18
[2]J. Axelsson, Cost Model for Electronic Architecture Trade Studies, Proc. Sixth Int. Conf. on Engineering of Complex Computer Systems, Tokyo, Japan, 2000.
[3]Shuang Dou; Shan Ding; Shi Zhang; Liucun Zhu; , "GA-based algorithm for hardware/software partitioning with resource contentions," Advanced Computer Control (ICACC), 2010 2nd International Conference on , vol.1, no., pp.68-72, 27-29 March 2010.
[4]Abdelhalim, M.B.; Habib, S.E.-D.; , "Modeling communication cost and hardware alternatives in PSO based HW/SW partitioning," Microelectronics, 2007. ICM 2007. Internatonal Conference on , vol., no., pp.111-114, 29-31 Dec. 2007.
[5]T. Wiegand, G. Sullivan, G. Bjøntegaard, and A. Luthra, “Overview of the H.264/AVC video coding standard,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 13, no. 7, pp. 560–576, July 2003.
[6]Wei Yu, Yun He, “A high performance CABAC decoding architecture”, IEEE trans. on Consumer Electronics, Vol.51, No.4, Nov. 2005
[7]W. Wolf, A Decade of Hardware/Software Codesign," Computer, Vol. 36, No. 4, pp. 38-43, April 2003.
[8]A. Kalavade and E.A. Lee. The Extended Partitioning Problem: Hardware/Software Mapping and Implementation-Bin Selection. In Proc. of Sixth International Workshop on Rapid Systems Prototyping, pages 12–18, June 1995.
[9]J. Madsen, J. Grode, P. V. Knudsen, M. E. Petersen, and A. Haxthausen, ”LYCOS: The Lyngby Co-synthesis System,” J. Design Automation for Embedded Systems, vol. 2, no. 2, pp. 195-235, Mar. 1997.
[10]R. Ernst, J. Henkel, and T. Benner, “Hardware-software cosynthesis for microcontrollers,” IEEE Design & Test of Computers, vol. 10, no. 4, pp. 64-75, Dec. 1993.
[11]M. Holzer, B. Knerr, M. Rupp, “Design Space Exploration with Evolutionary Multi-Objective Optimization,” IEEE Second International Symposium on Industrial Embedded Systems, Lisbon, Portugal; 07-04-2007 - 07-06-2007; in: "2007 Symposium on Industrial Embedded Systems Proceedings", (2007), ISBN: 1-4244-0840-7; 126 - 133.
[12]W. Wang, A. Raghunathan, and N. K. Jha, “Pro_ling driven computation reuse: An embedded software synthesis technique for energy and performance optimization,”in VLSID-04 Design, 2004, p. 267.
[13]Ji-Gang Wu, Thambipillai Srikanthan, Guang-Wei Zou, New Model and Algorithm for Hardware/Software Partitioning, Journal of Computer Science and Technology, Vol.23, No.4, 644-651, 2008.
[14]TU Dortmund. (2010, June 03). “Motivation for HW/SW Co-Design”. Available:http://ls12-www.cs.tu-dortmund.de/research/activities/codesign/motivation/index.html.
[15]Jay Fenlason. GNU gprof (version 2.21.) [Online]. http://sourceware.org/binutils/docs/gprof/index.html.
[16]Jai-Ming Lin; Yao-Wen Chang; , "TCG: A transitive closure graph-based representation for general floorplans," Very Large Scale Integration (VLSI) Systems, IEEE Transactions on , vol.13, no.2, pp. 288- 292, Feb. 2005