臺灣博碩士論文加值系統

在base processor上加入延伸指令集(ISE)與超長指令集架構是其中兩種在嵌入式系統中，廣泛被用來滿足運算需求的方法。

針對multiple-issue架構，藉由在關鍵路徑(critical path)上挑選operations成為延伸指令集與指令排序平行化，可以在有效率使用硬體資源的情況下達到更好的效能增進。

然而，手動探索延伸指令集是非成複雜與耗時間的，本篇論文提供了一針對超長指令集架構，藉由使用力導向排序(Force-Directed Scheduling)演算法探索延伸指令集的自動化的設計流程，並提出一heuristic探索適合multi-issue架構的ISE。該流程首先將C源碼轉成部分順序資料流圖(Data Flow Graph)的表示式，並且對VLIW架構結合指令排續探索有效率的延伸指令集，最後設計一Estimation的model，評估使用延伸指令集的應用源碼，在效能上的增進。 實驗結果顯示，即使一應用程式的最大指令平行度已被基本處理器架構滿足，本篇論文提出的方法依然可以有12%的效能增進。

Both Instruction Set Extension(ISE) on base processor and VLIW architectures are two of the most popular methodology to achieve the required computing power in embedded system design.

Selecting operations on critical path as ISE as well as scheduling parallel operations on a multiple-issue architecture can obtain the better performance with efficient hardware utilization.

However, manually explore ISE may be very complex and time cost. This thesis presents an automatic design flow for ISE exploration on VLIW architectures using a Force-Directed Scheduling Algorithm and a proposed heuristic. Firstly the C source code will be translated into partial order data flow graph representation, and then to explore efficient ISE by proposed heuristic and cooperating with instruction scheduling for VLIW. Finally, the application code with ISE will be estimated by proposed Estimation Model to estimate the performance improvement. Results indicates that our approach gives average 12% improvement even the maximum ILP is been satisfied by base architecture.

誌謝.........i
摘要.........ii
Abstract.........iii
目錄.........iv
圖目錄.........vi
表目錄.........viii
第一章 導論.........1
第二章 相關文獻.........4
第三章 Instruction Set Extension for VLIW architectures.........7
3.1 Introduction to VLIW.........7
3.2 The Limitation of ILP on VLIW.........8
3.3 Instruction Set Extension Exploration.........8
3.3.1 Application-Specific Instruction: An Technique to Improve the Bottleneck of VLIW.........8
3.3.2 The Importance of Operation Scheduling.........11
3.4 Problem Definition.........11
3.5 The Proposed Methodology.........13
第四章 設計流程.........15
4.1 整合Trimaran Infrastructure.........15
4.2 CDFG Generation.........17
4.3 Scheduling.........18
4.3.1 Architecture Model.........19
4.3.2 Force-Directed Scheduling Methodology.........19
4.4 ASI Generation.........24
4.4.1 Heuristic.........25
4.4.2 Template Generation.........26
4.4.3 Candidate Generation.........30
4.4.4 ASI Selection.........31
4.4 ASI Replacement.........33
第五章 實驗數據與分析.........36
5.1 Estimation Model.........37
5.2 Reduce Execution Latency.........40
5.3 More Analysis.........43
第六章 結論與未來展望.........45
參考文獻.........46

[01]Khawam, S. Nousias, I. Milward, M. Ying Yi Muir, M. Arslan, T., “The Reconfigurable Instruction Cell Array,” EEE Transactions on Very Large Scale Integration (VLSI) Systems, Volume: 16, Issue: 1, Jan. 2008.
[02]Diviya Jain1, Anshul Kumar1, Laura Pozzi2, and Paolo Ienne2, “Automatically Customising VLIW Architectures with Coarse Grained Application-Specific Functional Units,” Proceedings of the 8th International Workshop on Software and Compilers for Embedded Systems, 2004.
[03]Vundela Srinivas Reddy, “Exploring VLIW ASIP Design Space using Trimaran Based Framework,” May. 2006.
[04]I-Wei Wu; Zhi-Yuan Chen; Jyh-Jiun Shann; Chung-Ping Chung, “Instruction Set Extension Exploration in Multiple-Issue Architecture,” IEEE Design, Automation and Test in Europe, 2008. DATE ''08.
[05]P.G. Paulin and J.P. Kight. “Force-directed scheduling in automatic data path synthesis”. Proc. 25th Design Automat. Conf.. 1988. 330-336.
[06]Zhixiong Zhou; Hu He; Yanjun Zhang; Yihe Sun; Chen, A, “A 2-Dimension Force-Directed Scheduling Algorithm for Register-File-Connectivity Clustered VLIW Architecture,” IEEE Conference on Application -specific Systems, Architectures and Processors. ASAP, Volume , Issue , 9-11, July 2007 Page(s):371 - 376.
[07]Trimaran Infrastructure URL:
http://www.trimaran.org.
[08]Chijie Lin, Jiying Wu, Jerung Shiu, Desheng Chen, Yiwen Wang. Department of Information Engineering and Computer Science, Feng Chia University Taichung, Taiwan.