A DISE implementation of dynamic code decompression

ABSTRACT

Code compression coupled with dynamic decompression is an important technique for both embedded and general-purpose microprocessors. Post-fetch decompression, in which decompression is performed after the compressed instructions have been fetched, allows the instruction cache to store compressed code but requires a highly efficient decompression implementation. We propose implementing post-fetch decompression using dynamic instruction stream editing (DISE), a programmable decoder---similar in structure to those in many IA32 processors---that is used to add functionality to an application by injecting custom code snippets into its fetched instruction stream. A DISE implementation of post-fetch decompression naturally supports customized program-specific decompression dictionaries, enables parameterized decompression allowing similar instruction sequences to share dictionary entries, and uses no decompression-specific hardware. Cycle-level simulation of DISE decompression shows that it can reduce static program size by 35% and execution time by 20%. Parameterized decompression, a feature unique to DISE, accounts for 20% of the code size reduction by making more effective use of the dictionary and allowing PC-relative branches to be included in compressed sequences. DISE-based compression can reduce total energy consumption by 10% and the energy-delay product by as much as 20%.

REFERENCES

• 1: Advanced RISC Machines Ltd. An Introduction to Thumb, Mar. 1995.
• 2: David H. Albonesi, Selective cache ways: on-demand cache resource allocation, Proceedings of the 32nd annual ACM/IEEE international symposium on Microarchitecture, p.248-259, November 16-18, 1999, Haifa, Israel
• 3: Guido Araujo , Paulo Centoducatte , Mario Cartes , Ricardo Pannain, Code compression based on operand factorization, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.194-201, November 1998, Dallas, Texas, United States
• 4: David Brooks , Vivek Tiwari , Margaret Martonosi, Wattch: a framework for architectural-level power analysis and optimizations, Proceedings of the 27th annual international symposium on Computer architecture, p.83-94, June 2000, Vancouver, British Columbia, Canada
• 5: D. Burger and T. M. Austin. The SimpleScalar tool set, version 2.0. Technical Report 1342, University of Wisconsin--Madison Computer Sciences Department, 1997.
• 6: Keith D. Cooper , Nathaniel McIntosh, Enhanced code compression for embedded RISC processors, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.139-149, May 01-04, 1999, Atlanta, Georgia, United States
• 7: Marc L. Corliss , E. Christopher Lewis , Amir Roth, DISE: a programmable macro engine for customizing applications, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 8: Saumya K. Debray , William Evans , Robert Muth , Bjorn De Sutter, Compiler techniques for code compaction, ACM Transactions on Programming Languages and Systems (TOPLAS), v.22 n.2, p.378-415, March 2000 [doi>10.1145/349214.349233]
• 9: K. Diefendorf. K7 challenges Intel. Microprocessor Report, 12(14), Nov. 1998.
• 10: P. Glaskowsky. Pentium 4 (partially) previewed. Microprocessor Report, 14(8), Aug. 2000.
• 11: L. Gwenapp. P6 microcode can be patched. Microprocessor Report, 11(12), Sept. 1997.
• 12: T. M. Kemp , R. K. Montoye , J. D. Harper , J. D. Palmer , D. J. Auerbach, A decompression core for powerPC, IBM Journal of Research and Development, v.42 n.6, p.807-812, November 1998
• 13: Darko Kirovski , Johnson Kin , William H. Mangione-Smith, Procedure based program compression, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.204-213, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 14: K. Kissell. MIPS16: High-Density MIPS for the Embedded Market. Silicon Graphics MIPS Group, 1997.
• 15: Chunho Lee , Miodrag Potkonjak , William H. Mangione-Smith, MediaBench: a tool for evaluating and synthesizing multimedia and communicatons systems, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.330-335, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 16: Charles Lefurgy , Peter Bird , I-Cheng Chen , Trevor Mudge, Improving code density using compression techniques, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.194-203, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 17: C. Lefurgy, E. Piccininni, and T. Mudge. Reducing code size with run-time decompression. In Proc. 6th International Symposium on High-Performance Computer Architecture, pages 218--227, Jan. 2000.
• 18: Haris Lekatsas , Jörg Henkel , Wayne Wolf, Code compression for low power embedded system design, Proceedings of the 37th conference on Design automation, p.294-299, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337423]
• 19: Stan Liao , Srinivas Devadas , Kurt Keutzer, A text-compression-based method for code size minimization in embedded systems, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.4 n.1, p.12-38, Jan. 1999 [doi>10.1145/298865.298867]
• 20: Thomas G. Szymanski, Assembling code for machines with span-dependent instructions, Communications of the ACM, v.21 n.4, p.300-308, April 1978 [doi>10.1145/359460.359474]
• 21: S. Wilton and N. Jouppi. An enhanced access and cycle time model for on-chip caches. Technical report, DEC Western Research Laboratory, 1994.
• 22: Andrew Wolfe , Alex Chanin, Executing compressed programs on an embedded RISC architecture, Proceedings of the 25th annual international symposium on Microarchitecture, p.81-91, December 01-04, 1992, Portland, Oregon, United States
• 23: Se-Hyun Yang , Babak Falsafi , Michael D. Powell , T. N. Vijaykumar, Exploiting Choice in Resizable Cache Design to Optimize Deep-Submicron Processor Energy-Delay, Proceedings of the 8th International Symposium on High-Performance Computer Architecture, p.151, February 02-06, 2002

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES

General Terms:
Design, Experimentation, Performance

Keywords:
DISE, code compression, code decompression