A dictionary construction technique for code compression systems with echo instructions

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A dictionary construction technique for code compression systems with echo instructions

Full text

Pdf (472 KB)

Source

ACM SIGPLAN Notices archive
Volume 40 , Issue 7 (July 2005) table of contents
Proceedings of the 2005 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems

SESSION: Memory optimization table of contents

Pages: 105 - 114

Year of Publication: 2005

ISSN:0362-1340

Also published in ...

Authors

Philip Brisk	University of California, Los Angeles, Los Angeles, CA
Jamie Macbeth	University of California, Los Angeles, Los Angeles, CA
Ani Nahapetian	University of California, Los Angeles, Los Angeles, CA
Majid Sarrafzadeh	University of California, Los Angeles, Los Angeles, CA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 18, Citation Count: 1

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1070891.1065926 What is a DOI?

ABSTRACT

Dictionary compression mechanisms identify redundant sequences of instructions that occur in a program. The sequences are extracted and copied to a dictionary. Each sequence is then replaced with a codeword that acts as an index into the dictionary, thereby enabling decompression of the program at runtime. The problem of optimally organizing a dictionary consisting solely of redundant sequences in order to maximize compression has long been known to be NP-Complete [23]. This paper addresses the problem of dictionary construction when redundant code fragments are represented as Data Flow Graphs (DFGs) rather than linear sequences of instructions. Since there are generally multiple legal schedules for a given DFG G, a compiler must determine a schedule for G so that other DFGs that are subgraphs of G can reference some substring of G's final code sequence. This reduces the size of the dictionary, and in turn, the size of the compressed program. Our experiments with 10 MediaBench [18] applications yielded reductions in dictionary size ranging from 21.14% to 29.76% compared to a naïve approach.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Advanced RISC Machines Ltd. An Introduction to Thumb, Ver. 2.0. White Paper, March 1995.
	2	Luca Benini , Alberto Macii , Alberto Nannarelli, Cached-code compression for energy minimization in embedded processors, Proceedings of the 2001 international symposium on Low power electronics and design, p.322-327, August 2001, Huntington Beach, California, United States [doi>10.1145/383082.383177]
	3	Brisk, P., Nahapetian, A., and Sarrafzadeh, M. Instruction Selection for Compilers that Target Architectures with Echo Instructions. Int. Workshop on Software and Compilers for Embedded Systems (SCOPES), 2004, 229--243.
	4	Chen, I., Bird, P., and Mudge, T. The Impact of Instruction Compression on I-cache Performance. Tech. Rpt. CSE-TR-330-97, EECS Dept., University of Michigan, 1997.
	5	Chen, W-K., Li, B., and Gupta, R. Code Compaction of Matching Single-Entry Multiple-Exit Regions. Static Analysis Symp., 2003, 401--417.
	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, A DISE implementation of dynamic code decompression, Proceedings of the 2003 ACM SIGPLAN conference on Language, compiler, and tool for embedded systems, June 11-13, 2003, San Diego, California, USA
	8	Bjorn De Sutter , Bruno De Bus , Koen De Bosschere, Sifting out the mud: low level C++ code reuse, Proceedings of the 17th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, November 04-08, 2002, Seattle, Washington, USA
	9	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]
	10	Fraser, C.W. An Instruction for Direct Interpretation of LZ77-compressed Programs. MSR-TR-2002-90, Microsoft Research, September, 2002.
	11	Christopher W. Fraser , Eugene W. Myers , Alan L. Wendt, Analyzing and compressing assembly code, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.117-121, June 17-22, 1984, Montreal, Canada
	12	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	13	R. Kastner , A. Kaplan , S. Ogrenci Memik , E. Bozorgzadeh, Instruction generation for hybrid reconfigurable systems, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.7 n.4, p.605-627, October 2002 [doi>10.1145/605440.605446]
	14	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
	15	Kissel, K. D. MIPS16: High-density MIPS for the Embedded Market. White Paper. Silicon Graphics MIPS Group, 1997.
	16	Kunchithapadam, K., and Larus, J. R. Using Lightweight Procedures to Improve Instruction Cache Performance. Tech. Rept. 1390, CS Dept., University of Wisconsin-Madison, 1999.
	17	Jeremy Lau , Stefan Schoenmackers , Timothy Sherwood , Brad Calder, Reducing code size with echo instructions, Proceedings of the 2003 international conference on Compilers, architecture and synthesis for embedded systems, October 30-November 01, 2003, San Jose, California, USA [doi>10.1145/951710.951724]
	18	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
	19	Charles Robert Lefurgy , Trevor Mudge, Efficient execution of compressed programs, 2000
	20	Haris Lekatsas , Wayne Wolf, Code compression for embedded systems, Proceedings of the 35th annual conference on Design automation, p.516-521, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277185]
	21	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]
	22	Runeson, J. Code Compression through Procedural Abstraction before Register Allocation. Master's Thesis. Computing Science Department, Uppsalla University, Sweden, March, 2000.
	23	Storer, J. NP-Completeness Results Concerning Data Compression. Tech. Rpt. 234, Dept. Electrical Engineering and Computer Science, Princeton University, 1977.
	24	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
	25	http://www.eecs.harvard.edu/hube/research/machsuif.html