臺灣博碩士論文加值系統

由於嵌入式系統的開發深深受到製造成本、電力消耗、執行效能等因素的限制；因此，如何設計一個成本、效能、與省電兼顧的嵌入式系統是目前重要的研究議題。在本篇文章，我們將利用壓縮與解壓縮混合程式碼的快取設計，讓小的快取，具有高快取命中率，以達到省電的功能，因為快取是昂貴，而且耗電的，所以我們採用不影響效能下，讓快取儘量小。在有快取的嵌入式系統的環境之下，為了維持快取的高命率，快取必須保持一定的大小才可以，但是如果因為成本與耗電的考量希望將快取縮小時，則命中率又會降低。於是乎，我們必須評估，至少快取內應該放置多少的程式碼，快取才會具有一定的命中率。當然，快取如果存放壓縮過的程式碼將可以讓快取不需要太大就可以維持高命中率，但是快取內放置的是壓縮過的程式碼，快取要將資料送到處理器之前，都要先經過解壓縮的動作，這時候，解壓縮的過程將明顯的影響效能。所以我們提出了一個具混合壓縮指令與解壓縮指令的快取，並且當快取的內容要抓到處理器前如果要做解壓縮的動作，將不會存取記憶體的方式來兼顧效能與成本。由於程式執行時具有區域性的關係，壓縮時不應該一視同仁的看待所有的程式碼，而應該考慮到下列幾個觀點：（1）由於程式執行時有『時間的區域性』，因此在壓縮時應該在常執行的與不常執行的指令中作一個區隔，用不同的壓縮方法壓縮兩種不同類型的指令，來達到不同的效果。（2）如果要求執行的效率與電量消耗，常常被執行的程式碼，應該用較容易或較省電的解壓縮方法來壓縮。（3）在不常執行的指令部分，由於這些指令執行的次數少且佔據的大部分的記憶體空間，在壓縮時應該可以用複雜的壓縮法，如此一來，大部分的程式碼因為不常被執行，所以可以達到不錯的壓縮率。
而當系統有快取存在時，為了達到較好的命中率，所以我們建議在快取內常用指令是以壓縮的方式存在，那麼快取內存放的常用指令個數便可增加，以提升快取命中率。另外，我們為了讓解壓縮引擎減少對效能的損耗，在我們設計中，一次解壓縮可得到多道指令，減少解壓縮對系統的負擔。
從實驗模擬中得知，我們使用256常用道指令可以比使用pre-cache的節省電量33.08%，並且我們的壓縮率並沒有明顯的增加，另外，我們使用512常用指令亦可降低耗電量39.58%，由此可見，我們的方法的確能夠在小快取的情況下達到兼顧電量與效能的設計。

In designing an embedded system, three issues -- hardware cost, system performance, and power consumption -- have to be taken carefully into consideration. We present an embedded system with cache design which considers performance and power consumption based on the frequency with which instructions are executed. We use the locality of running programs to optimize the use of memory space, system performance, and power consumption; that is, we compress infrequently executed codes to save the use of memory space but compress (encode) frequently executed codes to power consumption and maximize performance. According to the locality of executed programs, 90% execution time is used by 10% of the static object codes. As a result, we compress 90% of the static object codes to obtain our main data compression ratio to reduce the use of memory space. However, performance and power consumption are relevant to execution process, so we compress 10% of the frequently executed object codes to improve both performance and power consumption by reducing the number of memory access times. We encode the frequently executed instructions as shorter code words and then we pack continuous code words into a pseudo instruction. Once the decompression engine fetches one pseudo instruction, it can extract multiple instructions. Therefore, memory access can be efficiently reduced because of space locality.
From our simulation results, our method with one 256-instruction reference table does not increase the compression ratio, and the ratio of the power consumption can be reduced by about 33.08% than pre-cache with compressing all instructions. However, when one 512-instruction reference table is used, the ratio of the power consumption is reduced by 39.58% . According to the simulation results, our proposed methods based on the frequencies of executed instructions result in low power consumption, performance improvement and reduced memory.

摘要 I
Abstract III
誌謝 V
目錄 VI
圖目錄 VIII
表目錄 X
第1章 簡介 1
1.1 研究背景 1
1.2 研究動機 1
1.3 研究目標與研究方法 3
1.4 論文架構 4
第2章 相關研究 5
2.1 節省系統的記憶體空間的設計與改善執行效能的設計 5
2.2 省電的嵌入式系統設計 10
2.2.1 減少快取的電量消耗 10
第3章 階層式快取 15
3.1 壓縮方法 16
3.2 混合式快取 20
3.3 連結式快取 25
第4章 實驗與模擬 30
4.1 模擬環境 30
4.2 電量消耗 32
4.3 快取失誤率 34
4.4 壓縮率 35
4.5 連結式快取 36
第5章 結論 38
參考文獻 40
Publication List of Chang-Jung Ku 45

[1].C. Lefurgy, P. Bird, I. C. Chen and T. Mudge, “Improving Code Density Using Compression Technique,” Proceedings of the 30th Annual International Symposium on Microarchitecture, December 1997.
[2].A. Wolfe and A. Chanin, “Executing Compressed Programs on an Embedded RISC Architecture,” Proceedings of the 25th Annual International Symposium on Microarchitecture, December 1992.
[3].H. Lekatsas and W. Wolf, “SAMC: A Code Compression Algorithm for Embedded Processors,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 18, No. 12, December 1999.
[4].S.Liao, S. Devadas, K. Keutzer, ”Code Density Optimization for Embedded DSP Processors Using Data Compression Techniques”, Proceedings of the 15th Conference on Advanced Research in VLSI, March 1995.
[5].S.J. NAM, I.C. PARK and C.M. KYUNG, “Improving Dictionary-Based Code Compression in VLIW Architecture,” IEICE TRANS. Fundamentals, Vol. E82- A, No. 11 November 1999.
[6].C. Lefurgy, E. Piccininni and T. Mudge, “Analysis of a High Performance Code Compression Method”, Proceedings of the 32nd Annual International Symposium on Microarchitecture, November 1999.
[7].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), pp. 206-211, 1999.
[8].Y.Yoshida, B.-Y. Song, H. Okuhata, T. Onoye, and I. Shirakawa, “An objectcode compression approach to embedded processors,” In ACM/IEEE Int. Symp. Low Power Electronics and Design, Monterey, CA, Aug. 1997, pp. 265–268.
[9].H. Lekatsas and W. Wolf, “Code compression for Embedded Systems”, Proceedings of the 35th Design Automation Conference, June 1998.
[10].G. Araujo, P. Centoducatte, M. Cortes and R. Pannain, “Code compression based on operand factorization,” In Proceedings MICRO-31 Int. Symposium Microarchitecture, pp. 194-201, Dec.1998.
[11].G. Araujo, P. Centoducatte and R. Pannain, “Compressed code execution on DSP architecture,” System Synthesis, 1999 Proceedings 12th International Symposium on, Nov 1999.
[12].G. Araujo, P. Centoducatte, R. Azevedo and R. Pannain, “Expression tree based algorithms for code compression on embedded RISC architecture,” IEEE Transactions on VLSI Systems, VOL. 8, No. 5, October 2000.
[13].K. Lin, J.J. Shann and C.P. Chung, “Code Compression by Register Operand Dependency,” Interaction between Compilers and Computer Architectures, 2002. Proceedings 6th Annual Workshop on, 2002.
[14].B. Jacob, “Cache Design for Embedded Real-Time System”, Proceedings of the Embedded Systems Conference, Summer 1999.
[15].S.Y. Larin, T.M. Conte, “Compiler-Driven Cached Code Compression Schemes for Embedded ILP Processors,” Microarchitecture, 1999. MICRO-32. Proceedings 32nd Annual International Symposium On, 1999.
[16].C. Lefurgy, E. Piccininni and T. Mudge, “Reducing Code Size with Run-time Decompression,” High-Performance Computer Architecture, 2000. HPCA-6. Proceedings 6th International Symposium on, pp. 218-228, 2000..
[17].Y. Xie, H. Lekatsas and W. Wolf, “Compression Ratio and Decompression overhead Tradeoffs in Code compression for VLSI Architectures,” Proceedings of International Conference on ASIC (ASION) October, 2001.
[18].Y. Xie, H. Lekatsas and W. Wolf, “A Code Decompression Architecture for VLSI Processors,” Proceedings of the 34th Annual ACM/IEEE International Symposium on Microarchitecture December 2001.
[19].J. Henkel, H. Lekatsas and W. Wolf, “Design and SimuLAT ion of a Pipelined Decompression Architecture for Embedded Systems,” System Synthesis, 2001. Proceedings the 14th International Symposium on, 2001.
[20].C.D. Benveniste, P.A. Franaszek, J. Robinson, “Cache-memory interfaces in compressed memory systems,” IEEE Transactions on Computers, Vol. 50, No. 11, November 2001.
[21].J. Henkel, H. Lekatsas and V. Jakkula, “Design of an One-cycle Decompression Hardware for Performance increase in Embedded Systems,” Proceedings of the 39th conference on Design Automation June 2002.
[22].Y. Yoshida, B.Y. Song, H. Okuhata, T. Onoye and I. Shirakawa, “An Object Code Compression Approach to Embedded Processors,” Low Power Electronics and Design, 1997. Proceedings International Symposium on, 18-20 Aug 1997.
[23].J. Henkel, H. Lekatsas and W. Wolf, “Code Compression for Low Power Embedded System Design,” Data Compression Conference, 2000. Proceedings DCC 2000.
[24].J. Henkel, H. Lekatsas and W. Wolf, “Arithmetic Coding for Low Power Embedded System Design,” Design Automation Conference, 2000. Proceedings 2000. 37th 2000.
[25].L. Benini, A. Macii and A. Nannarelli, “Cached-Code Compression for Energy Minimization in Embedded Processors”, ACM Proceedings of International Symposium on Low Power Electronics and Design (ISLPED’01), August6-7, 2001.
[26].L. Benini, A. Macii and A. Nannarelli, “Code Compression Architecture for Cache Energy Minimization in Embedded Systems”, IEE Proceedings-Comput. Digit. Tech., Vol.149, No. 4, July 2002.
[27].Advanced RISC Machines Ltd., “An Introduction to Thumb”, March 1995.
[28].IBM, CodePack PowerPC Code Compression Utility User‘s Manual Version 3.0, IBM, 1998.
[29].K. Kissell, MIPS16: High-density MIPS for the Embedded Market, Technical report, Silicon Graphics MIPS Group, 1997.
[30].Yen-Jen Chang, Shanq-Jang Ruan, Feipei Lai, “Design and analysis of low-power cache using two-level filter scheme,” IEEE Transactions on Very Large Scale Integration (VLSI) Systems, pp. 568-580, August 2003.
[31].N. Hajj, Univ. of Illinois at Urbana-Champaign, “Architectural and Compiler Support for Energy Reduction in the memory Hierarchy of High Performance Microprocessors,” 1998 International Symposium on Low Power Electronics and Design.
[32].J. Kin, M. Gupta and W. H. Mangione-Smith, “The Filter Cache: An Energy Efficient Memory Structure, ” In Proc. of 30th International Symposium on Microarchitecture, pp. 184-193, Dec. 1997.
[33].Jun Yang and Rajiv Gupta, “Frequent Value Locality and its Applications, ” ACM Transactions on Embedded Computing Systems, 1(1):79-105, November 2002.
[34].Jun Yang and Rajiv Gupta, “Energy Efficient Frequent Value Data Cache Design, ” ACM/IEEE 35th International Symposium on Micro architecture, pages 197-207, Istanbul, Turkey, November 2002.
[35].Jang-Soo Lee, Won-Kee Hong, and Shin-Dug Kim, “An On-chip Cache Compression Technique to Reduce Decompression Overhead and Design Complexity, ” Journal of Systems Architecture: the EUROMICRO Journal, 46(15):1365-1382, December 2000.
[36].Alaa R. Alameldeen and David A. Wood, “Frequent Pattern Compression: A Significance-Based Compression Scheme for L2 Caches, ” Dept. of Computer Sciences Technical Report CS-TR-2004-1500, April 2004.
[37].Morten Kjelso, Mark Gooch, and Simon Jones, “Design and Performance of a Main Memory Hardware Data Compressor, ” In Proceedings of the 22nd EUROMICRO Conference, 1996.
[38].Jun Yang, Youtao Zhang, and Rajiv Gupta, “Frequent Value Compression in Data Caches, ” In Proceedings of the 33rd Annual IEEE/ACM International Symposium on Microarchitecture, pages 258-265, December 2000.
[39].Yuan Xie, Wayne Wolf and Haris Lekatsas, Profile-driven Selective Code Compression, Proceedings of the Design,Automation and Test in Europe Conference and Exhibition (DATE’03), 2003, pp. 10462-10467
[40].P. Shivakumar and N. Jouppi, "CACTI 3.0: An integrated cache timing, power, and area model," Compaq, Palo Alto, CA, WRL Res. Rep. 2001/2