臺灣博碩士論文加值系統

近年來，一些指令的壓縮技術被提出，主要是減少在嵌入式系統中電能的消耗，取代了以往針對減少應用程式於記憶體空間上需求的研究。這些節能技術主要的構想在於挑選最常被執行的指令作壓縮，以減少記憶體存取的次數，因而節省電能的消耗。雖然每個壓縮的指令將被取代成一個長度較短的壓縮碼(codword)，然而這樣的節能的方法有些使得程式碼的大小增加，而較好的方法則只能使得程式碼大小沒有任何的改變。
有鑑於此，我們提出一個較有效的指令壓縮技術，同時能減少電能的消耗以及減少程式碼在記憶體空間上的使用需求。我們的方法主要是以一個壓縮碼表示了在基本區塊(basic block)中所有連續的指令，這些連續的指令必須存在同一個基本區塊內，然後這個表示基本區塊的壓縮碼將被編入一道虛擬指令(pseudo instruction)中，當這道虛擬指令從記憶體被取得時，其中的壓縮碼將被解壓縮，接著從解壓縮表格中獲得基本區塊所對應的原始指令。當基本區塊的大小越大以及存取的次數越高，所能節省的記憶體存取次數將會越多。
除此之外我們提出了四種架構以節省記憶體存取的次數，第一種架構在虛擬指令中編入一個壓縮碼，每次從記憶體取得虛擬指令後，便能從解壓縮表格取得基本區塊中的所有指令；第二種架構在虛擬指令中編入多個壓縮碼，目的是將執行路徑上數個連續的基本區編入其中，每次取得虛擬指令後，將取得這些基本區塊，如此一來將更加的節省記憶體的存取次數；第三種架構也是基於第二種架構的構想，不同的是在解壓縮引擎的控制上，判斷迴圈式的基本區塊，若虛擬指令中的壓縮碼為迴圈式的基本區塊，將不斷地存取這個基本區塊直至迴圈結束，如此將能節省從記憶體取得相同的虛擬指令；最後第四種架構中，加入了一個路徑查詢表，藉由這個路徑表格，從解壓縮表格獲得路徑上的基本區塊，直至路徑上的基本區塊不存在於解壓縮表格。根據實驗模擬的結果比較先前的研究，我們最佳的方法將更能節省電能的消耗，平均高出了26.01%，而在程式碼方面，記憶體空間平均大約節省了19.68%。

Several code compression techniques have been proposed for embedded systems to minimize the power consumption instead of the memory occupation of the application software as most techniques did. Their idea is to reduce the instruction memory access frequency by compressing the most frequently executed instructions. However, because every compressed instruction needs to be replaced by a shorter codeword, the static code size is increased or left unchanged. Therefore, we propose a code compression technique to reduce both the power consumption and the code size. We use a single codeword to represent all the continuous instructions belonging to the same basic block and the codeword is encoded in a pseudo instruction. Whenever a pseudo instruction is fetched, the codeword is decoded and the corresponding uncompressed instructions are obtained from the decompression table. The larger the basic block and the higher the access frequency, the more the memory accesses can be saved. According to the simulation results compared with the previous work, our method can further reduce the power consumption by about 26.01% and the code size by about 19.68% on average.

目錄
中文摘要....................................I
英文摘要....................................II
致謝.......................................III
目錄.......................................IV
圖目錄......................................VI
表目錄.....................................VII
第一章 緒論..................................1
1.1 研究背景與動機...........................1
1.2 論文架構................................4
第二章 相關的研究............................5
2.1 著重於程式碼大小減少之指令壓縮相關技術......5
2.1.1 Lefurgy提出針對程式碼減少的方法.........5
2.1.2 Nam提出針對程式碼減少的方法.............7
2.2 著重於耗能的減少之指令壓縮相關技術.........8
2.2.1 Yoshida提出針對耗能節省的方法...........9
2.2.2 Benini針對耗能節省提出的方法............10
2.2.3 Netto提出針對耗能節省的方法.............11
2.2.4 Chen提出針對耗能節省的方法..............13
第三章 新的省電指令壓縮技術....................15
3.1 在ARM處理器中基本區塊的特色................16
3.2 提出的架構...............................17
3.2.1 第一種架構.............................17
3.2.2 第二種架構.............................20
3.2.3 第三種架構.............................24
3.2.4 第四種架構.............................26
3.3 挑選基本區塊的方針........................29
3.4 解壓縮引擎使用資源........................33
第四章 實驗結果..............................35
4.1 模擬環境的架構...........................35
4.2 實驗結果及分析...........................37
4.2.1 基本區塊的觀察及分析....................37
4.2.2 第一種架構中挑選方針與IDT大小的分析......39
4.2.3 第一種架構的實驗結果與先前的研究之比較....41
4.2.4 四種架構的比較及分析....................44
4.2.5 比較挑選方針在第四種架構的情況...........50
4.2.6 第二種、第三種及第四種架構的分析.........52
4.2.7 系統整體的效能比較.....................54
4.2.8 程式碼經壓縮後的結果...................56
第五章 結論與未來研究........................57
5.1 結論...................................57
5.2 未來研究................................59
參考文獻...................................60

圖目錄
圖 1. 以LEFURGY方法壓縮程式碼的例子..........6
圖 2. LEFURGY提出的架構....................6
圖 3. 使用一個字典檔對VLIW指令作壓縮.........7
圖 4. 使用兩個字典檔對VLIW指令作壓縮.........8
圖 5. NAM提出的架構........................8
圖 6. YOSHIDA提出的架構....................9
圖 7. BENINI提出的架構.....................11
圖 8. 一個BRANCH目標位址所對應壓縮指令的問題..11
圖 9. 不同格式的壓縮指令....................12
圖 10. 一個簡單的例子使用NETTO提出的方法壓縮..13
圖 11. ARM 虛擬指令........................14
圖 12. ARM 虛擬指令 WITH MULTI-IDT.........14
圖 13. CACHE-FREE之嵌入式系統架構...........15
圖 14. 基本區塊............................17
圖 15. 將基本區塊以一道虛擬指令取代...........18
圖 16. 第一種架構.........................19
圖 17. NOT-TAKEN及TAKEN路徑的基本區塊......21
圖 18. 第二種架構.........................22
圖 19. 第二種架構執行過程中的存取情況.......23
圖 20. 第三種架構.........................25
圖 21. 第三種架構執行過程中的存取情況.......26
圖 22. 第四種架構........................27
圖 23. 第四種架構執行過程中的存取情況一....28
圖 24. 第四種架構執行過程中的存取情況二....29
圖 25. 基本區塊大小的分布.................38
圖 26. 在第一種架構中平均記憶體存取減少百分比..41
圖 27. 比較256-ENTRY IDT中第一種架構與CHEN的記憶體存取次數節省百分比.....42
圖 28. 比較256-ENTRYIDT中第一種架構與CHEN的耗能節省百分比..42
圖 29. 在不同大小的IDT比較第一種架構與CHEN的節能百分比..43
圖 30. 比較不同大小的IDT與各種架構上平均記憶體減少百分比....48
圖 31. 比較不同大小的IDT與各種架構上平均耗能節省百分比....48
圖 32. 在256-ENTRY IDT及挑選方針E中比較各個BENCHMARK及架構的差異...50
圖 33. 在不同大小的IDT中程式碼所節省的百分比........56

表目錄
表格 1. 基本區塊路徑表............................27
表格 2. 基本區塊的例子............................31
表格 3. 挑選方針對於BASIC BLCOK的挑選結果..........31
表格 4. 解壓縮引擎使用資源列表.....................34
表格 5. 每個BENCHMARK程式的程式碼大小以及指令數.....36
表格 6. 不同大小的IDT存取一次所需的耗能.............36
表格 7. 不同大小的PATH TABLE存取一次所需耗能.......36
表格 8. 在第一種架構中比較記憶體存取減少的百分比...................................................40
表格 9. 比較各種架構中的記憶體存取節省的百分比.......................................................45
表格 10. 各種架構所使用的耗能.........................................................................................46
表格 11. 比較各種架構中的耗能節省的百分比.................................................................47
表格 12. 比較第四種架構中記憶體存取次數的節省百分比.............................................51
表格 13. 被挑選的基本區塊細節.........................................................................................53
表格 14. 各個架構存取虛擬指令的次數.............................................................................54
表格 15. 各種架構即CHEN架構中減少的週期數..............................................................55

[1] Advance RISC Machines Ltd., An Introduction to Thumb, 1995.
[2] Advance RISC Machines Ltd., ARM SDT 2.50 : Reference Manual, http://infocenter.arm.com/help/topic/com.arm.doc.dui0041c/DUI0041C.pdf.
[3] R. Benes, S.M. Nowick, and A. Wolfe, “A fast asynchronous Huffman decoder for compressed-code embedded processors,” 1998 Fourth International Symposium on Advanced Research in Asynchronous Circuits and Systems. (1998) 43–56.
[4] L. Benini, A. Macii, E. Macii, and M. Poncino, “Minimizing memory access energy in embedded systems by selective instruction compression,” IEEE Trans. Very Large Scale Integr. (VLSI) Syst., 10(5), (2002) 521–531
[5] L. Benini, A. Macii, E. Macii, and M. Poncino, “Selective instruction compression for memory energy reduction in embedded systems,” IEEE/ACM Proceedings of International Symposium on Low Power Electronics and Design (ISLPED’99). (1999) 206–211.
[6] T. Bonny and J. Henkel, “Instruction splitting for efficient code compression design automation conference,” 2007. DAC '07. 44th ACM/IEEE 4-8, (2007) 646 – 651
[7] T. Bonny and J. Henkel, “Using Lin-Kernighan algorithm for look-up table compression to improve code density,” GLSVLSI’06, (2006) 259 – 265.
[8] C.-W. Chen, C.-H. Chang, and C.J. Ku, “A low power-consuming embedded system design by reducing memory access frequencies,” IEICT Trans. Inf. & Syst., E88-D(12), (2005) 2748-2756.
[9] A. Eichenberger, W. Meleis, and S. Maradani, “An integrated approach to accelerate data and predicate computations in hyperblocks,” Proceedings of MICRO-33, (2000) 101 – 111.
[10] Steve Furber, ARM system-on-chip architecture, 2nd Edition, Addison-Wesley Professional, 2000.
[11] IBM, CodePack PowerPC Code Compression Utility User’s Manual Version 3.0, IBM, 1998.
[12] N. Inshiura, AND M. Yamaguchi, “Instruction code compression for application specific VLIW processors based on automatic field partitioning.” Proceedings of the Workshop on Synthesis and System Integration of Mixed Technologies., (1997) 105–109.
[13] K. Kissell, “MIPS16: High-density MIPS for the embedded market,” 42 Technical Report, Silicon Graphics, 1997.
[14] M. Kozuch and A. Wolfe, “Compression of embedded system programs,” IEEE International Conference on Computer Design: VLSI in Computers and Processors, (1994) 270–277.
[15] Rajeev Kumar and Dipankar Das, “Code compression for performance enhancement of variable-length embedded processors,” ACM Transactions on Embedded Computing Systems, 7(3), (2008) 35:1–35:36.
[16] T. M. Kemp, R. K. Montoye, J.D. Haper, J. D. Palmer, AND D. J. Auerbach, “A decompression core for PowerPC.” IBM J. Res. Develop. 42, 6, (1998) 807–812.
[17] Chunho Lee, M. Potkonjak and W. H. Mangione-Smith, “MediaBench: A tool for evaluating and synthesizing multimedia and communications systems,” 1997. Proceedings of thirtieth Annual IEEE/ACM International Symposium on Microarchitecture, (1997) 330 – 335.
[18] C. Lefurgy, P. Bird, I.C. Chen, and T. Mudge, “Improving code density using compression technique,” Proceedings of 30th Annual International Symposium on Microarchitecture, (1997) 194–203.
[19] H. Lekatsas and W. Wolf. “SAMC: A code compression algorithm for embedded processors.” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 18(12), (1999) 1689–1701.
[20] S. Liao, S. Devadas, and K. Keutzer, “Code density optimization for embedded DSP processors using data compression techniques,” Proceedings of 15th Conference on Advanced Research in VLSI. (1995)272.
[21] C. Lin, Y. Xie, and W. Wolf. “LZW-based code compression for VLIW embedded systems.” DATE, (2004)76-81.
[22] S. Nam, I. Park, and C. Kyung. “Improving dictionary-based code compression in VLIW architectures.” IEICE Trans. Fundamentals, A(11), (1999)2318-2324.
[23] E.W. Netto, R. Azevedo, P. Centoducatte, and G. Araujo, “Multi-profile based code compression,” Annual ACM/IEEE Design Automation Conference archive Proc. 41st Annual Conference on Design Automation, (2004)244-249.
[24] J. Prakash, C. Sandeep, P. Shankar and Y. Srikant. “A simple and fast scheme for code compression for VLIW processors.” DCC 2003.
[25] M. Ros and P. Sutton. “A hamming distance based VLIW/EPIC code compression technique.” CASES 2004.
[26] Seok-Won Seong and Prabhat Mishra, “A Bitmask-based Code Compression Technique for Embedded Systems,” Proceedings of ICCAD, (2006)251–254.
[27] Seok-Won Seong and Prabhat Mishra, “An efficient code compression technique using application-aware bitmask and dictionary selection methods,” DATE07, (2007)582-587.
[28] P. Shivakumar and N. Jouppi, “CACTI 3.0: An integrated cache timing, power, and area model,” Technical report 2001/2, Compaq Western Research Lab. 2001.
[29] A. Wolfe and A. Chanin, “Executing compressed programs on an embedded RISC architecture,” Proceedings of 25th Annual International Symposium on Microarchitecture. (1992)81–91.
[30] Y. Xie, W. Wolf, AND H. Lekatsas, “Code compression for VLIW processors using variable-to-fixed coding.” IEEE Trans. VLSI Syst. 14, 5, (2006) 525–536.
[31] Y. Yoshida, B.-Y. Song, H. Okuhata, T. Onoye, and I. Shirakawa, “An object code compression approach to embedded processors,” ACM/IEEE International Symposium Low Power Electronics and Design, Monterey, CA, (1997) 265–268.