臺灣博碩士論文加值系統

在高階合成中，運算元排序是非常重要的一環，而常見的運算排序都是在控制步驟與運算元資源兩者中做出權衡。我們希望先找到最佳的運算時間後，再利用運算元延遲與功率管理的特性來降低整體電路的平均功率。日益複雜的電路設計中，低功率是一個重要的設計，是因為人們對電子產品高度的依賴，自然而然對於使用時間的要求也更加嚴苛，想要延長使用時間，必須降低產品的功率消耗，導致低功率成為電路設計中不可或缺的目標。
在本篇中，我們對運算時間與整體平均功率提出了整數線性規劃的式子來描述同最小化運算時間下優化平均功率之高階合成問題研究所探討的問題，我們所提出的整數線性規劃式子呈現了運算元排序與運算元延遲選擇與功率管理之間的關係、整體的運算時間與平均功率的限制，藉由這些整數線性規劃式子所設計的限制，經由LINGO軟體的運算，我們可以得到最佳解答。最後實驗結果，我們可以在最短的運算時間，減少平均功率的使用。

In the high-level Synthesis, operation scheduling is a very important part, and most conventional operation scheduling algorithms make trade-off between control steps and resources. We propose a method that utilizes the characteristics of operation delay to decrease average power under the minimum execution time. In the increasingly complex circuit design, low power is also an important design objective, because people rely heavily on portable electronic products in modern life.
In this thesis, we propose an ILP (integer linear programming) formulation to model the problem of minimizing the average power under the minimum execution time in high-level synthesis. We use the integer linear programming (ILP) formulas to express the relationship between operation scheduling and operation delay selection in order to reduce the average power. By those formulations, we simultaneously maintain the minimum cycle time and decrease average power efficiently to obtain the best solution.

摘要.................................................I

ABSTRACT..............................................III

誌謝....................................................V

目錄...................................................VI

圖目錄...............................................VIII

表目錄..................................................X


第一章 緒論............................................1
1.1 高階合成之介紹...................................1
1.2 全文架構.........................................3
第二章 文獻回顧.........................................4
2.1 運算元排序論......................................4
2.2 降低平均功率的方法...............................10
2.3 最佳化運算時間的方法..............................12
2.4 考慮運算元延遲與控制訊號的方法....................14
第三章 問題描述與定義..................................18
3.1 基本定義.........................................18
3.2 運算元延遲選擇介紹...............................22
3.3 功率管理.........................................23
3.4 問題描述.........................................24
第四章 線性規劃方程式..................................29

第五章 實驗結果與分析..................................51
5.1 作業平台與程式語言................................51
5.2 實驗結果與分析....................................51
第六章 結論...........................................55

參考文獻................................................56
 
圖目錄
圖一:假設電路使用ASAP排序方法............................5
圖二:假設電路使用ALAP排序方法.............................6
圖三:假設電路執行List Scheduling的結果....................7
圖四: 運算元所可以執行的範圍..............................8
圖五:HAL電路在ILP的計算下，排序後出來的最佳解..........9
圖六:未加control-domination的流程圖.....................11
圖七:加入control-domination後的流程圖...................12
圖八:不同電壓所需的運算時間..............................13
圖九:考慮輸入電壓的運算元................................14
圖十:峰值範例...........................................15
圖十一:考慮延遲選擇的範例................................16
圖十二:考慮延遲選擇與control-dominate的範例..............17
圖十三:相依關係示意圖....................................20
圖十四:控制步驟數目限制在3...............................21
圖十五:資源限制下的排序..................................22
圖十六:運算元延遲.......................................23
圖十七:運算元無延遲.....................................26
圖十八:運算元有延遲.....................................26
圖十九: 運算元同時考慮延遲與功率管理.....................27
圖二十:機率示意圖.......................................36
圖二十一:延遲為零的範例電路..............................37
圖二十二:ALAP示意圖.....................................38
圖二十三:最佳化的結果示意圖..............................49


表目錄
表一:ILP式子所使用的參數.................................23
表二：每個運算元的二元變數值.............................37
表三：控制元的二元變數值.................................37
表四: 測試電路的特性....................................49
表五:實驗結果...........................................50
表六:加入功率管理.......................................51
表七:加入[29]做比對.....................................51

[1] M.C. McFarland, A.C. Parker and R. Camposano, “Tutorial on High-Level Synthesis”, Proc. of IEEE/ACM Design Automation Conference, pp. 330—336, 1988.
[2] R. Walker and R. Camposano, “A Survey on High-Level Synthesis Systems”, Kluwer Academic Publishers, 1991.
[3] D.D. Gsjski, N.D. Datt, A.C.H. Wu and S.Y.L. Lin, “High-Level Synthesis: Introduction to Chip and System Design”, Kluwer Academic Publishers, 1992.
[4] D.D. Gsjski and L. Ramachandran, “Introduction to High-Level Synthesis”, IEEE Design and Test of Computers, pp. 44—54, 1994.
[5] G. De Micheli, “Synthesis and Optimization of Digital Circuits”, McGraw-Hill Academic Publishers, 1994.
[6] R. Jain, A. Mujumdar, A. Sharma and H.M. Wang, “Empirical Evaluation of Some High-Level Synthesis Scheduling Heuristics”, Proc. of IEEE/ACM Design Automation Conference, pp. 686—689, 1991.
[7] R.A. Walker and S. Chaudhuri, “Introduction to the Scheduling Problem”, IEEE Design and Test of Computers, pp. 60—69, 1995.
[8] P. Faraboschi, J.A. Fisher and C. Young, “Instruction Scheduling for Instruction Level Parallel Processors”, Proc. of the IEEE, vol. 89, no. 11,
pp. 1638—1659, 2001.
[9] S. Davidson, D. Landslov, B.D. Shriver and P.W. Mallett, “Some Experiments in Local Microcode Compaction for Horizontal Machines”, IEEE Trans. on Computers, pp 460—477, 1981.

[10] P. G.. Paulin and J. P. Knight, “Force-Directed Scheduling for the Behavioral Synthesis of ASICs”, IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, pp. 661—679, 1989.
[11] R. Camposano, “Path-Based Scheduling for Synthesis”, IEEE Trans on Computer-Aided Design of Integrated Circuits and Systems, pp. 85—93, 1991.
[12] S. H. Huang, C.T. Hwang, Y.C. Hsu, and Y. J. Oyang, “A New Approach to Schedule Operations across Nested-ifs and Nested-loops”, Proc. of IEEE/ACM International Symposium on Micro-architecture, pp.
268—271, 1992.
[13] S.H. Huang, C.T. Hwang, Y.C. Hsu and Y.J. Oyang, “A New Approach to Schedule Operations across Nested-ifs and Nested-loops”, EuroMicro Journal: Microprocessing and Microprogramming, vol. 41, pp. 37—52, 1995.
[14] C. T. Hwang, J. H. Lee and Y. C. Hsu, “A Formal Approach to the Scheduling Problem in High Level Synthesis”, IEEE Trans. On Computer-Aided Design of Integrated Circuits and Systems, pp. 464—475, 1991.
[15] M. Rim and R. Jain, “Estimating Lower-Bound Performance of Schedules Using a Relaxation Technique”, Proc. of IEEE International Conference on Computer Design, pp. 290—294, 1992.
[16] R. Jain, A. Mujumdar, A. Sharma and H.M. Wang, “Empirical Evaluation of Some High-Level Synthesis Scheduling Heuristics”, Proc. of IEEE/ACM Design Automation Conference, pp. 686—689, 1991.
[17] R.A. Walker and S. Chaudhuri, “Introduction to the Scheduling Problem”, IEEE Design and Test of Computers, pp. 60—69, 1995.

[18] P. Faraboschi, J.A. Fisher and C. Young, “Instruction Scheduling for Instruction Level Parallel Processors”, Proc. of the IEEE, vol. 89, no. 11, pp. 1638—1659, 2001.
[19] C. Tseng and D.P. Siweorek, “Automated Synthesis of Data Path in a Digital System”, IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 5, pp. 379—395, 1986.
[20] J. A. Fisher, “Trace Scheduling: A Technique for Global Microcode Compaction”. IEEE Trans. on Computers, pp 478—490, 1981.
[21] R. Gupta and M. L. Soffa, “Region Scheduling”, Proc. of IEEE International Conference on Supercomputing, pp. 141—148, 1987.
[22] C. J. Tseng, “Bridge: A Versatile Behavioral Synthesis System”, Proc. of IEEE/ACM Design Automation Conference, pp. 415—420, 1988.
[23] T. Kim, J. Liu and C. L. Liu, “A Scheduling Algorithm for Conditional Resource Sharing”, Proc. of IEEE International Conference Computer Aided Design, pp. 84—87, 1991.
[24] F.F. Hsu, E.M. Rudnick, and J.H Patel, “Testability Insertion in Behavioral Descriptions”, Proc. of IEEE International Symposium on System Synthesis, pp. 139—144, 1996.
[25] J. Li, R.K. Gupta “An Algorithm to Determine Mutually Exclusive Operations in Behavioral Descriptions”, Proc. of IEEE/ACM Design Automation and Test in Europe, pp. 457—465, 1998.
[26] K. Wakabayashi and H. Tanaka, “Global Scheduling Independent of Control Dependencies Based on Condition Vectors”, Proc. of IEEE/ACM Design Automation Conference, pp. 112—115, 1992.
[27]C.J. Tseng, R.S. Wei, S.G. Rothweiler, M.M. Tong, and A.K. Bose, “Bridge: A Versatile Behavioral Synthesis System”, Proc. of IEEE/ACM Design Automation Conference, pp. 415—420, 1988.
[28] T Kim, J.W.S Liu, C.L. Liu, “A scheduling algorithm for conditional resource sharing”, Proc. of ICCAD, pp.84-87, 1991.
[29] S.H. Huang, Chun-Hua Cheng, Chung-Hsin Chiang, and Chia-Ming Chang, “An ILP Approach to the Simultaneous Application of Operation Scheduling and Power Management”, Proc. of IEEE/APCCAS Circuits and Systems, pp.868－871, 2006.
[30]V. Raghunathan, S. Ravi, G.Lakshminarayana “High-level synthesis with variable-latency components”, Proc. of VLSI Design 2000. Thirteenth International Conference on, pp. 220-227, 2000.
[31] 顏瑋廷，”同時進行功率管理運算元排序及運算元延遲選擇之高階合成系統”,中原大學電子工程學系碩士論文(指導教授:黃世旭), 95年。