工程師在設計數位系統時，必須同時考慮到成本、效能與功耗等問題；而嵌入式系統更是被這三項因素嚴苛的限制住。記憶體是一個同時影響這三項因素的關鍵之一，在嵌入式系統中，指令壓縮技術是一個用來降低記憶體使用需求的方法，BitMask壓縮方法是一種Dictionary壓縮方法的修改版本。BitMask壓縮方法是透過記錄指令之間的差異值以及差異值的位置(即漢明距離)進而降低指令原本未壓縮指令的編碼長度，解壓縮時只要透過移位與互斥或運算即可還原原始未壓縮的指令。本篇論文結合可變Mask個數以及一個小的分離字典的方法至BitMask壓縮演算法中，把最常被執行的指令編碼成長度更短的codeword，我們也提出新的建立字典演算法來達到更高的指令覆蓋率並提出完全分離式字典架構來改善指令解壓縮單元的效能，根據我們的實驗結果，我們提出的方法在較小的評測程式可以改善平均5~6%的壓縮比，但是在較大的評測程式可以改進超過7%的壓縮比，而且不需提升太多的解壓縮硬體需求。

Engineers must consider performance, power consumption and cost when they design digital systems. Embedded systems are more constrained in all these considerations. Memory is one of the key factors that affect all of them. Code compression is a technique for embedded systems to reduce the memory usage. BitMask based code compression is a modified version of dictionary based code compression. The basic of BitMask is to record mismatch values and their positions to compress more instructions and use exclusive or operation with the reference instruction to decode the codeword. In this article, we applied a small separated dictionary and variable mask numbers to the BitMask algorithm to reduce the codeword length of high frequency instructions. A novel dictionary selection algorithm is also proposed to increase the instruction match rates. The fully separated dictionary method is used to improve the performance of decompression engine without affecting the compression ratio. According to our experimental results, our method can improve in average 5~6% compression ratio for smaller benchmarks, and over 7% improvement for bigger benchmarks with nearly no hardware overhead.

[1] Wolfe, A. and Chanin, A. 1992. Executing Compressed Programs on an Embedded RISC Architecture. Proc. of the Intl. Symposium on Microarchitecture (Dec. 1992), 81-91.
[2] Lefurgy, C., Bird, P., Chen, I., and Mudge, T. 1997. Improving code density using compression techniques. in Proc. Int. Symp. MICRO, 194-203.
[3] Seong, S. and Mishra, P. 2006. A bitmask-based code compression technique for embedded systems. in Proc. ICCAD, 251–254.
[4] Seong, S. and Mishra, P. 2007. An efficient code compression technique using application-aware bitmask and dictionary selection methods. in Proc DATE, 1-6.
[5] Texas Instruments. 2006. Literature Number: SPRU731 TMS320C62x DSP CPU and instruction set reference guide (July 2006).
[6] IBM. 1998 .PowerPC Code Compression Utility User’s Manual, Version 3.0.
[7] Lekatsas, H. and Wolf, W. 1999. SAMC: A code compression algorithm for embedded processors. IEEE Trans. Comput.-Aided Design Integr. Circuits Syst., 18, 12 (Dec. 1999), 1689–1701.
[8] Larin, S. and Conte, T. 1999 Compiler-Driven Cached Code Compression Schemes for Embedded ILP Proceesors. Proc. of the Annual Int. Symposium on Microarchitecture (Nov. 1999), 82-91.
[9] Xie, Y., Wolf, W., and Lekatsas, H. 2002. Code Compression for VLIW using Variable-to-fixed coding. Proc. of ISSS.
[10] Lin, C., Xie, Y., and Wolf, W. 2007. Code compression for VLIW embedded systems using a Self-Generating Table. IEEE Trans on Very Large Scale Integration (VLSI) Systems, 15, 10, 1160 - 1171.
[11] Lin, C.W. and Lin, C.H. 2010. A Power-saving Code-compression Design for the VLIW Embedded Systems. in Proc. 2010 World Congress in Computer Science, Computer Engineering, and Applied Computing (July 2010).
[12] Bonny, T., and Henkel, J. 2008. FBT: Filled Buffer Technique to reduce code size for VLIW processors. Proceedings of international conference on CAD (ICCAD), 549-554.
[13] Yang, L., Zhang, T., Wang, D., and Hou, C. 2009. Optimal-partition based code compression for embedded processor. IEEE 8th International Conference on ASIC.
[14] Qin, X., and Mishra, P. 2009. Efficient Placement of Compressed Code for Parallel Decompression. VLSI Design, 2009 22nd International Conference (Jan. 2009), 335-340.
[15] Bonny, T., and Henkel, J. 2009. LICT: Left-uncompressed instructions compression technique to improve the decoding performance of VLIW processors. Design Automation Conference.
[16] Nam, S., Park, I., and Kyung, C. 1999. Improving Dictionary-Based Code Compression in VLIW Architectures. IEICE Trans. Fundamentals (Nov. 1999), 2318-2324.
[17] Gorjiara, B. Reshadi, M., and Gajski, D. 2008. Merged. Dictionary Code Compression for Fpga Implementation of Custom Microcoded Pes. ACM Trans. Reconfigurable Technol. Syst, Volume 1 Issue 2 (June 2008), 1-21.
[18] Prakash, J, Sandeep, C., Shankar, P., and Srikant, Y. 2003. A simple and fast scheme for code compression for VLIW processors. in Proc. DCC, 444.
[19] Ros, M. and Sutton, P. 2004. A hamming distance based VLIW/EPIC code compression technique. in Proc. CASES, 132–139.
[20] Murthy, C. and Mishra, P. 2009. Lossless Compression Using Efficient Encoding of Bitmasks, IEEE Symposium on VLSI, 2009. ISVLSI '09 (May 2009), 163-168.
[21] Qin, X., Muthry, C., and Mishra, P. 2011. Decoding-Aware Compression of FPGA Bitstreams,　IEEE Trans. Very Large Scale Integration (VLSI) Syst. (Mar. 2011), 411-419.
[22] Murthy, C. and Mishra, P. 2009. Bitmask-based control word compression for nisc architecture. in Proc. ACM Great Lakes Symposium on VLSI, 321–326.
[23] Bonny, T. and Henkel, J. 2008. Efficient code compression for embedded processors. IEEE Trans. Very Large Scale Integr. (VLSI) Syst., 16, 12 (Dec. 2008), 1696-1707.
[24] Ranjith, J., Muniraj, N.J.R and Renganayahi, G. 2010. VLSI implementation of single bit control system processor with efficient code density, Communication Control and Computing Technologies (ICCCCT), 2010 IEEE International Conference on, (Oct. 2010), 103-108.
[25] Sayood, K., 吳俊霖譯, 2008. Introduction to data compression, Morgan Kaufmann, 3rd, (May. 2008).
[26] Li, L., Chakrabarty, K., and Touba, N. 2003. Test data compression using dictionaries with selective entries and fixed-length indices. ACM Trans. Des. Autom. Electron. Syst. (TODAES), 8, 4, (Oct. 2003), 470-490.
[27] Segars, S., Clarke, K. and Goude L. 1995 Embedded control problems, thumb and the ARM7TDMI. IEEE Micro, vol. 15, no. 5, (Oct. 1995), 22–30.
[28] Kissel, K. 1997 MIPS16: High-density MIPS for the embedded market. Silicon Graphics MIPS Group, Sunnyvale, CA.
[29] Ecco, L., Lopes, B., Xavier, E. C. and Pannain, R. 2009 SPARC16 ：A new compression approach for the SPARC architecture. SBAC-PAD '09. 21st International Symposium on, (Oct. 2009), 169 - 176.
[30] Gonzalez, R. 2000 Xtensa: A configurable and extensible processor. IEEE Micro, vol. 20, no. 2, (Mar./Apr. 2000), 60–70.
[31] ARC International, San Jose, CA, 2005 ARCompact-ISA programmer’s reference manual.
[32] Cooper, K. D. and McIntosh, N. 1999 Enhanced code compression for embedded RISC processors. in Proc. SIGPLAN Conf. Program. Lang.Des. Implement (1999), 139-149.
[33] Debray, S. and Evans, W. 2002 Profile-guided code compression. in Proc.Conf. Program. Lang. Des. Implement, 95-105.
[34] Debray, S. and Evans, W. 2003 Cold code decompression at runtime. Commun. ACM, vol. 46, no. 8, (Aug. 2003), 54-60.
[35] Ozturk, O., Saputra, H., Kandemir, M. and Kolcu, I. 2005 Access patternbased code compression for memory-constrained embedded systems. in Proc. Des., Autom. Test Eur. Conf. Expo, 882-887.
[36] Shogan, S. and Childers, B. R. 2004 Compact binaries with code compression in a software dynamic translator. in Proc. Des., Autom. Test Eur.Conf. Expo, 1052-1057.
[37] [Online]. Available: http://www.synopsys.com/
[38] Synopsys, 2007. Design compiler user guide. (Dec. 2007).
[39] Synopsys, 2006. Primepower manual. (June. 2006).
[40] Texas Instruments, 2004. Literature Number: SPRU509E Code composer studio v3.0 getting started guide, (May. 2004).
[41] Texas Instruments, 2004. Application Report: SPRAA08 Code composer studio IDE v3 white paper, (July. 2004).