A post-compilation register reassignment technique for improving hamming distance code compression

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A post-compilation register reassignment technique for improving hamming distance code compression

Full text

Pdf (193 KB)

Source

International Conference on Compilers, Architecture and Synthesis for Embedded Systems archive
Proceedings of the 2005 international conference on Compilers, architectures and synthesis for embedded systems table of contents

San Francisco, California, USA

SESSION: Memories table of contents

Pages: 97 - 104

Year of Publication: 2005

ISBN:1-59593-149-X

Authors

Montserrat Ros	The University of New England, Armidale, Australia
Peter Sutton	The University of Queensland, Brisbane, Australia

Sponsors

ACM: Association for Computing Machinery
SIGBED: ACM Special Interest Group on Embedded Systems
SIGMICRO: ACM Special Interest Group on Microarchitectural Research and Processing

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 50, Citation Count: 1

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	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/1086297.1086311 What is a DOI?

ABSTRACT

Code compression is a field where compression ratios between compiler-generated code and subsequent compressed code are highly dependent on decisions made at compile time. Most optimizations employed by compilers tend to focus on parameters such as program performance, minimizing resource dependencies and sometimes the option of reducing code size.This paper describes a post-compilation technique for the greedy reassignment of general purpose scratch registers to improve Hamming distance based code compression. The code translation renumbers registers based on the frequency of registers used by isomorphic instructions and employs a Gray coding scheme to reduce Hamming distances between similar instructions.Register reassignment has been successfully implemented in areas where the compiler optimizations do not include a particular metric, for example, power savings. Pro-gram values can be reassigned register numbers that reduce overall power consumption of the address bus and register file decoder, at no cost to code size or performance.The application of the register reassignment technique in this paper reduced the number of dictionary vectors required by a program on average by 9.74%. Code compression ratios of register-reassigned binaries were consistently around 3-4% (of original program size) lower than code compression applied to original binaries, with the highest such reduction at nearly 7%. General purpose register reassignment is a technique that allows for gains in compression efficiency with no penalty in hardware. Other techniques that could be trialed include commutative register switching, dead register detection and assignment and complete register re-allocation.

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	"Mediabench Benchmarks", http://cares.icsl.ucla.edu/MediaBench/
	2	"SPEC CPU2000 Benchmarks", http://www.spec.org/cpu2000/
	3	Atmel-Corporation, "AT572D740 Summary (Datasheet)", http://www.atmel.com/dyn/resources/prod_documents/7001s.pdf
	4	Paulo Centoducatte , Guido Araujo , Ricardo Pannain, Compressed Code Execution on DSP Architectures, Proceedings of the 12th international symposium on System synthesis, p.56, November 01-04, 1999
	5	Keith D. Cooper , Nathaniel McIntosh, Enhanced code compression for embedded RISC processors, ACM SIGPLAN Notices, v.34 n.5, p.139-149, May 1999
	6	Jens Ernst , William Evans , Christopher W. Fraser , Todd A. Proebsting , Steven Lucco, Code compression, ACM SIGPLAN Notices, v.32 n.5, p.358-365, May 1997
	7	IBM, CodePack™ PowerPC Code Compression Utility User's Manual Version 4.1: IBM, 1998.
	8	N. Ishiura and M. Yamaguchi, "Instruction Code Compression for Application Specific VLIW Processors BAsed on Automatic Field Partitioning," 1997.
	9	Sergei Y. Larin , Thomas M. Conte, Compiler-driven cached code compression schemes for embedded ILP processors, Proceedings of the 32nd annual ACM/IEEE international symposium on Microarchitecture, p.82-92, November 16-18, 1999, Haifa, Israel
	10	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
	11	C. Lefurgy and T. Mudge, "Code Compression for DSP", Compiler and Architecture Support for Embedded Computing Systems, George Washington University, Washington DC, 1998.
	12	C. Lefurgy, E. Piccininni, and T. Mudge, "Reducing code size with run-time decompression," in Proceedings Sixth International Symposium on High Performance Computer Architecture. HPCA 6 Cat. No.PR00550. 1999: IEEE Comput. Soc, Los Alamitos, CA, USA, 1999, pp. 218--28.
	13	H. A. Lekatsas, "Code compression for embedded systems," Princeton University, 2000, pp. 171.
	14	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]
	15	Steven S. Muchnick, Advanced compiler design and implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
	16	S. J. Nam, In Cheol Park, and Chong Min Kyung, "Improving dictionary-based code compression in VLIW architectures," IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol. E82-A, pp. 2318--24, 1999.
	17	Peter Petrov , Alex Orailoglu, Transforming Binary Code for Low-Power Embedded Processors, IEEE Micro, v.24 n.3, p.21-33, March 2004 [doi>10.1109/MM.2004.18]
	18	J. Prakash , C. Sandeep , Priti Shankar , Y. N. Srikant, A Simple and Fast Scheme for Code Compression for VLIW Processors, Proceedings of the Conference on Data Compression, p.444, March 25-27, 2003
	19	Montserrat Ros , Peter Sutton, Compiler optimization and ordering effects on VLIW code compression, 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.951725]
	20	Montserrat Ros , Peter Sutton, A hamming distance based VLIW/EPIC code compression technique, Proceedings of the 2004 international conference on Compilers, architecture, and synthesis for embedded systems, September 22-25, 2004, Washington DC, USA [doi>10.1145/1023833.1023853]
	21	Texas-Instruments, "TMS320 DSP Algorithm Standard Rules and Guidelines", http://focus.ti.com/lit/ug/spru352e/spru352e.pdf
	22	Andrew Wolfe , Alex Chanin, Executing compressed programs on an embedded RISC architecture, ACM SIGMICRO Newsletter, v.23 n.1-2, p.81-91, Dec. 1992
	23	Y. Xie , H. Lekatsas , W. Wolf, Code Compression for VLIW Processors, Proceedings of the Data Compression Conference (DCC '01), p.525, March 27-29, 2001
	24	Yuan Xie , Wayne Wolf , Haris Lekatsas, Code compression for VLIW processors using variable-to-fixed coding, Proceedings of the 15th international symposium on System Synthesis, October 02-04, 2002, Kyoto, Japan [doi>10.1145/581199.581231]
	25	Kun Zhang , Tao Zhang , Santosh Pande, Binary translation to improve energy efficiency through post-pass register re-allocation, Proceedings of the 4th ACM international conference on Embedded software, September 27-29, 2004, Pisa, Italy [doi>10.1145/1017753.1017769]