臺灣博碩士論文加值系統

在計算機系統的組成元件中，記憶體一直是消耗功率最多的部分。有別以往

的程式碼壓縮研究只重視壓縮比的作法，我們提出了一套以選擇性壓縮演算

法（SCC）作為核心演算法，並加上LZW（Lempel-Ziv-Welch）的壓縮演算法

做實際的資料壓縮。 我們在SCC的演算法之中增加了解壓縮功率消耗的事先

預測機制策略，而且搭配的解壓縮硬體有著成本小、功耗少的特色。我們的

解壓縮引擎為了評估出更為準確的功率消耗，我們將使用靜態時序分析的技

術去計算出各項硬體內的功率消耗成本。在編譯器方面，我們針對 VLIW 處

理器許多在指令層平行 （ILP）技巧的特性和指令間的排程技術去引進可變

動程式區塊大小的分支區塊(Branch Block)概念去做程式碼的壓縮。 解壓

縮引擎的硬體實現是使用 Cell-based 設計流程，採用TSMC.18μm-2p6m 半

導體製程技術元件庫去做實體硬體設計。我們將解壓縮硬體，進行 IP 化、

與全客製化 IC 設計；解壓縮硬體的加入並不會大幅度的更改到處理器原本

的硬體設計；因此，我們的程式碼壓縮方法並不限定於 VLIW 的架構上，也

可以應用在其他的 RISC 計算機結構上。

We studied the architecture of embedded computing systems from the

memory power consumption point-of-view and used selective-code-

compression (SCC) approach to realize our design. Based on the LZW

(Lempel-Ziv-Welch) compression algorithm, we proposed a novel cost

effective compression and decompression method. The goal of our

study is to develop a new SCC approach with the extended decision

policy based on the prediction of power consumption. Our

decompression method has to be easily implemented in hardware and

should collaborate with the processor at the same time. The

decompression engine hardware was implemented using TSMC.18μm-

2p6m model with cell-based libraries. In order to calculate more

accurate power consumption of the decompression engine, we used

static analysis method to estimate the power overhead. We also

used variable sized branch blocks and considered several

characteristics of VLIW processors for our compression; the

characteristics included the instruction level parallelism (ILP)

technique, and instruction scheduling. Our code-compression

methods are not limited to VLIW machines, but can be applied to

other kinds of RISC architecture.

Abstract---------------------------------------------i
摘 要----------------------------------------------ii
目 次----------------------------------------------iii
表目錄----------------------------------------------v
圖目錄----------------------------------------------vi
第一章 緒論----------------------------------------------1
1.1 研究動機----------------------------------------------1
1.2 相關研究----------------------------------------------2
1.3 各章節概要--------------------------------------------4
第二章 程式碼壓縮方法與VLIW架構概述-----------------------5
2.1 前言----------------------------------------------5
2.2 程式碼壓縮方法----------------------------------------6
2.3 VLIW架構概述------------------------------------------8
第三章 程式碼結構分析------------------------------------11
3.1 程式開發環境介紹-------------------------------------11
3.2 程式碼控制流程圖分析---------------------------------14
3.3 分支控制流程圖演算法開發-----------------------------19
第四章 低功率程式碼壓縮設計概述--------------------------23
4.1 前言----------------------------------------------23
4.2 嵌入式開發平台工具種類-------------------------------24
4.3 嵌入式Linux系統--------------------------------------25
4.4 低功率可預測選擇性壓縮演算法改良---------------------26
第五章 即時性解壓縮硬體電路架構設計----------------------32
5.1 前言----------------------------------------------32
5.2 Verilog硬體描述語言介紹------------------------------33
5.3 FPGA編程元件-----------------------------------------34
5.4 LZW動態解壓縮演算法----------------------------------40
5.5 數位電路設計-----------------------------------------42
第六章 解壓縮電路晶片實現與效能驗證----------------------44
6.1 前言----------------------------------------------44
6.2 Cell-based 設計流程與概述----------------------------44
6.3 晶片佈局與繞線探討-----------------------------------48
6.4 電路實體合成與驗證-----------------------------------55
6.4.1 DFM----------------------------------------------55
6.4.2 Physical-Layout------------------------------------56
6.5 效能分析---------------------------------------------58
第七章 結論----------------------------------------------61
參考文獻----------------------------------------------62

[1] A. Wolfe and A. Chanin, “Executing compressed programs on an embedded risc architecture," in Intl Symposium on Micro-architecture., Dec. 1992, pp. 81-91.
[2] IBM, “PowerPC Code Compression Utility Users Manual," version 3.0 ed., 1998.
[3] S. Liao, S. Devadas, and K. Keutzer, “Code density optimization for embedded dsp processors using data compression techniques," in Conf. on Advanced Research in VLSI,1995, pp. 272-285.
[4] C. Lefurgy, P. Bird, I. Chen, and T. Mudge, “Improvingcode density using compression techniques," in Intl Symposium on Micro-architecture, Aug. 1997, pp. 194-203.
[5] H. Lekatsas and W. Wolf, “Samc: A code compression algorithm for embedded processors," IEEE Trans. Computer Aided Design., vol. 18, no. 12, pp. 1689-1701, Dec. 1999.
[6] S. Segars, K. Clarke, and L. Goude, “Embedded control problems, thumb and the arm7tdmi," IEEE Micro, vol. 15,no. 5, pp. 22V30, Oct. 1995.
[7] Y. Xie, W. Wolf, and H. Lekatsas, “Code compression for vliw using variable-to-fixed coding," in Intl Symposium on System Synthesis. ACM, Oct. 2002, pp. 138-143.
[8] C. H. Lin, Y. Xie and W. Wolf, “Code Compression for VLIW Embedded Systems Using a Self-Generating Table," in IEEE Transaction VLSI., vol. 15, no. 10, pp. 1160-1171,Apr.2007.
[9] S. Seong and P. Mishra, “A bitmask-based code compression technique for embedded systems," IEEE Trans. Computers., vol. 27, no. 4, pp. 673-685, Apr. 2008.
[10] C. H. Lin, Y. Xie, and W. Wolf, “Lzw-based code compression for vliw embedded systems," in Design, Automation and Test in Europe Conference and Exposition., Feb. 2004,pp. 76-81.
[11] Y. Xie, W. Wolf, and H. Lekatsas, “Profile-driven selective code compression," in Design, Automation and Test in Europe Conference and Exposition., Mar. 2003, pp. 462-467.
[12] T. Bonny and J. Henkel, “LICT: Left-uncompressed Instructions Compression Technique to improve the decoding performance of VLIW processors," in Design Automation Conference ACM, Jul. 2009, pp. 903-906.
[13] M.S. Ali, Anjali Mahajan, N.V. Choudhari, "Compiled Code Compression for Embedded Systems Using Evolutionary Computing," pp.1173-1174, Fifth International Conference on Information Technology: New Generations, Apr.2009
[14] L. Yang, T. Zhang, D. Wang and C. Hou, “Optimal-Partition Based code compression for embedded processor, "in IEEE Conference on ASIC., Oct. 2009, pp. 87-90.
[15] E. W. Netto, R. Azevedo, P. Centoducatte, and G. Araujo,
“Multi-pro_le based code compression," in Design Automation Conference. ACM, 2004, pp. 244-249.
[16] L. Benini, F. Menichelli, and M. Olivieri, “A class of code compression schemes for reducing power consumption in embedded microprocessor systems," IEEE Trans. Computers., vol. 53, no. 4, pp. 467-482, Apr. 2004.
[17] C. W. Lin and C. H. Lin, ‘A Power-saving Code-compression Design for the VLIW Embedded Systems," in ESA’10, the international Embedded System and Applications Conference, Jul. 2010
[18] NSC, ‘A Low-power Code-compression Design on the Architecture of VILW Computers," Project no:97-2218-E-011-016.
[19] D. Patterson and D. Ditzel, “The case for the reduced instruction set computing,” ACM SIGARCH Computer Architecture News, Oct.1980, p.25-33.
[20] TI, “TMS320C64x/C64x+ DSP CPU and Instruction Set: Reference Guide, " SPRU732H, Oct.2008.
[21] TI, “Code Composer Studio v3.0 Getting Started Guide, " SPRU509E,May.2004.
[22] TI, “Code Composer Studio Development Tools v3.2 Getting Started Guide, " SPRU509G,Mar.2006.
[23] TI, “TMS320C62xx CPU and Instruction Set: Reference Guide, " SPRU731, Jul.2006.
[24] TI, “TMS320C6000 Optimizing Compiler v6.1: Users Guide, " SPRU1870,May.2008.
[25] TI, “TMS320C6000 Assembly Language Tools v 6.0 Beta: Users Guide, " SPRU186P,Jul.2005.
[26] TI, “TMS320C6000 Programmer’s Guide, " SPRU198I,Mar.2006.
[27] D. Walker, “Compiling Techniques,” Princeton University, Spring.2009
[28] R. Gansner, “Drawing graphs with Graphviz, " Graphviz Drawing Library Manual,Apr.2009.
[29]S. B. Furber, “ARM System-on-chip Architecture, ” Addison Wesley Longmain, 2000.
[30]S. B. Furber, “ARM System Architecture, ” Addison Wesley Longmain,1996.
[31]ARM, “ARM architecture reference manual, ” Ver. Jan 2000, E.
[32]ARM, “AMBA specification Rev 2.0
[33] C.H.Lin, “Advanced Computer Architecture.”, NTUST, Spring, 2009
[34] C.-H.Wu and C.H.Lin, “Embedded System and its application.”, NTUST, Spring, 2009
[35]M. Barr and A. Oram, “Programming Embedded Systems in C and C++,” O’REILLY, 1999.
[36]J. J. Labrosse, “Embedded Systems Building Blocks: Complete and Read-To-Use Modules in C, ” Second Edition, CMP books, 2000.
[37] V. Cuppu, “ Cycle Accurate Simulator for TMS320C62x, 8way VLIW DSP Processor," University of Maryland, College Park, 1999
[38]Galaxy Far East Corp., “Quartus II ADVANCED Training Manual,” Fall, 2007
[39]Altera Corp., “Quartus II data sheet and Cyclone FPGA Family data sheet,” 2003.
[40] T. Welch, "A Technique for High-Performance Data Compression", IEEE Computer, Jun. 1984、p.8-19.
[41] M.-B. Lin, “Digital System Designs and Practices : Using Verilog HDL and FPGAs, " WILEY,2008.
[42] D.Ciletti, “Advanced Digital Design with the Verilog HDL, " Prentice Hall,2003.
[43] Synopsys, “Synplicity FPGA Synthesis Synplify, Synplify Pro, Synplify Premier, and Synplify Premier with Design Planner : User Guide, ", Dec.2005.
[44] CIC, “Cell-Based IC Design Concepts Training Manual, " A101,Jul.2004.
[45] Synopsys, “Design Compiler Reference Manual: Constraints and Timing, " Version A-2007.12, Dec.2007.
[46] C.-Y. Yao, “Backend Design Flow of digital Systems”, NTUST, Fall, 2008
[47] CIC, “Cell-Based IC Physical Design and Verification with Astro, " A107,Jul.2007.
[48] M.-B. Lin, “VLSI circuit design.”, NTUST, Fall, 2008
[49] S.-K. Lu, “VLSI Testing and Testability Design.”, NTUST, Fall, 2009
[50] Synopsys, “PrimePower Manual, " Version Y-2006.06,Jun.2006
[51] D. Burger and M. Austin, “SimpleScalar User’s Guide: The SimpleScalar Tool Set, Version 2.0, ”.
[52] D. Brooks, V. Tiwari and M.Martonosi, “Wattch: a framework for architectural-level power analysis and optimizations,” ACM SIGARCH Computer Architecture News, May.2000, p.83-94.