Article

Free access

Improving code density using compression techniques

Authors:

Charles Lefurgy,

Peter Bird,

I-Cheng Chen,

Trevor MudgeAuthors Info & Claims

MICRO 30: Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture

Pages 194 - 203

Published: 01 December 1997 Publication History

PDF eReader Publisher Site

Abstract

We propose a method for compressing programs in embedded processors where instruction memory size dominates cost. A post-compilation analyzer examines a program and replaces common sequences of instructions with a single instruction codeword. A microprocessor executes the compressed instruction sequences by fetching code words from the instruction memory, expanding them back to the original sequence of instructions in the decode stage, and issuing them to the execution stages. We apply our technique to the PowerPC, ARM, and i386 instruction sets and achieve an average size reduction of 39%, 34%, and 26%, respectively, for SPEC CINT95 programs.

References

[1]

Advanced RISE Machines Ltd., An Introduction to Thumb, March 1995.

Google Scholar

[2]

T Bell, J. Cleary, I. Witten, Text Compression, Prentice Hall, 1990.

Digital Library

Google Scholar

[3]

P. Bird and T Mudge, An Instruction Stream Compression Technique, CSE-TR-319-96, EECS Department, University of Michigan, November 1996.

Google Scholar

[4]

I. Chen, P. Bird, and T. Mudge, The Impact of Instruction Compression on I-cache Performance, CSE-TR-330- 97, EECS Department, University of Michigan, 1997.

Google Scholar

[5]

I. Chen, Enhancing Instruction Fetching Mechanism Using Data Compression, Ph.D. Dissertation, University of Michigan, 1997.

Digital Library

Google Scholar

[6]

K. Kissell, MIPS16: High-density MIPS for the Embedded Market, Silicon Graphics MIPS Group, 1997.

Google Scholar

[7]

M. Kozuch and A. Wolfe, "Compression of Embedded System Programs," IEEE International Conference on Computer Design, 1994.

Digital Library

Google Scholar

[8]

S. Liao, Code Generation and Optimization for Embedded Digital Signal Processors, Ph.D. Dissertation, Massachusetts Institute of Technology, June 1996.

Digital Library

Google Scholar

[9]

"Thumb Squeezes ARM Code Size," Microprocessor Report 9(4), 27 March 1995.

Google Scholar

[10]

S. Perl and R. Sites, "Studies of Windows NT Performance Using Dynamic Execution Traces{' Proceedings of the USENIX 2nd Symposium on Operating Systems Design and Implementation, October 1996.

Digital Library

Google Scholar

[11]

SPEC CPU'95, Technical Manual, August 1995.

Google Scholar

[12]

J. Storer, NP-completeness Results Concerning Data Compression, Technical Report 234, Department of Electrical Engineering and Computer Science, Princeton University, 1977.

Google Scholar

[13]

T. G. Szymanski, "Assembling code for machines with span-dependent instructions,' Communications of the ACM 21:4, pp. 300-308, April 1978.

Digital Library

Google Scholar

[14]

A. Wolfe and A. Chanin, "Executing Compressed Programs on an Embedded RISC Architecture," Proceedings of the 25th Annual International Symposium on Microarchitecture, December 1992.

Digital Library

Google Scholar

Cited By

View all

Hepola KMultanen JJääskeläinen P(2024)Energy-Efficient Exposed Datapath Architecture With a RISC-V Instruction Set ModeIEEE Transactions on Computers10.1109/TC.2023.333731373:2(560-573)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1109/TC.2023.3337313
Rengasamy PZhang HZhao SNachiappan NSivasubramaniam AKandemir MDas COskin MInoue K(2018)CritICs critiquing criticality in mobile appsProceedings of the 51st Annual IEEE/ACM International Symposium on Microarchitecture10.1109/MICRO.2018.00075(867-880)Online publication date: 20-Oct-2018
https://dl.acm.org/doi/10.1109/MICRO.2018.00075
Sardashti SWood D(2017)Could Compression Be of General Use? Evaluating Memory Compression across DomainsACM Transactions on Architecture and Code Optimization10.1145/313880514:4(1-24)Online publication date: 5-Dec-2017
https://dl.acm.org/doi/10.1145/3138805
Show More Cited By

Recommendations

Enhanced code density of embedded CISC processors with echo technology
CODES+ISSS '05: Proceedings of the 3rd IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis

Code density is an important issue in memory constrained systems. Some RISC processor, e.g. the THUMB extension in the ARM processor, supports aggressive code size reduction even at the cost of significant performance loss. In this paper, we develop an ...
Huffman-based code compression techniques for embedded processors

The size of embedded software is increasing at a rapid pace. It is often challenging and time consuming to fit an amount of required software functionality within a given hardware resource budget. Code compression is a means to alleviate the problem by ...
Improving Code Density with Variable Length Encoding Aware Instruction Scheduling

Variable length encoding can considerably decrease code size in VLIW processors by reducing the number of bits wasted on encoding No Operations(NOPs). A processor may have different instruction templates where different execution slots are implicitly ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

MICRO 30: Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture

December 1997

369 pages

ISBN:0818679778

Chairmen:
Mark Smotherman
Clemson Univ., Clemson, SC
,
Tom Conte
North Carolina State Univ., Raleigh

Publisher

IEEE Computer Society

United States

Publication History

Published: 01 December 1997

Check for updates

Author Tags

Qualifiers

Article

Conference

MICRO97

Sponsor:

SIGMICRO
IEEE-CS\TCMM

MICRO97: 30th Annual International Symposium on Microarchitecture

December 1 - 3, 1997

North Carolina, Research Triangle Park, USA

Acceptance Rates

MICRO 30 Paper Acceptance Rate 35 of 103 submissions, 34%;

Overall Acceptance Rate 484 of 2,242 submissions, 22%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

90
Total Citations
View Citations
582
Total Downloads

Downloads (Last 12 months)27
Downloads (Last 6 weeks)3

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Hepola KMultanen JJääskeläinen P(2024)Energy-Efficient Exposed Datapath Architecture With a RISC-V Instruction Set ModeIEEE Transactions on Computers10.1109/TC.2023.333731373:2(560-573)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1109/TC.2023.3337313
Rengasamy PZhang HZhao SNachiappan NSivasubramaniam AKandemir MDas COskin MInoue K(2018)CritICs critiquing criticality in mobile appsProceedings of the 51st Annual IEEE/ACM International Symposium on Microarchitecture10.1109/MICRO.2018.00075(867-880)Online publication date: 20-Oct-2018
https://dl.acm.org/doi/10.1109/MICRO.2018.00075
Sardashti SWood D(2017)Could Compression Be of General Use? Evaluating Memory Compression across DomainsACM Transactions on Architecture and Code Optimization10.1145/313880514:4(1-24)Online publication date: 5-Dec-2017
https://dl.acm.org/doi/10.1145/3138805
Lee SKim KKoo GJeon HAnnavaram MRo W(2017)Improving Energy Efficiency of GPUs through Data Compression and Compressed ExecutionIEEE Transactions on Computers10.1109/TC.2016.261934866:5(834-847)Online publication date: 1-May-2017
https://dl.acm.org/doi/10.1109/TC.2016.2619348
Lee SKim KKoo GJeon HRo WAnnavaram M(2015)Warped-compressionACM SIGARCH Computer Architecture News10.1145/2872887.275041743:3S(502-514)Online publication date: 13-Jun-2015
https://dl.acm.org/doi/10.1145/2872887.2750417
Lee SKim KKoo GJeon HRo WAnnavaram MMarr DAlbonesi D(2015)Warped-compressionProceedings of the 42nd Annual International Symposium on Computer Architecture10.1145/2749469.2750417(502-514)Online publication date: 13-Jun-2015
https://dl.acm.org/doi/10.1145/2749469.2750417
Sun PNunez-Yanez J(2014)Optimizing Memory Power in Hybrid ARM-FPGA Chips With Lossless Data CompressionProceedings of the FPGA World Conference 201410.1145/2674095.2674097(1-7)Online publication date: 9-Sep-2014
https://dl.acm.org/doi/10.1145/2674095.2674097
Lee JLee JLee JPaek Y(2014)Improving performance of loops on DIAM-based VLIW architecturesACM SIGPLAN Notices10.1145/2666357.259782549:5(135-144)Online publication date: 12-Jun-2014
https://dl.acm.org/doi/10.1145/2666357.2597825
Lee JLee JLee JPaek YZhang YKulkarni P(2014)Improving performance of loops on DIAM-based VLIW architecturesProceedings of the 2014 SIGPLAN/SIGBED conference on Languages, compilers and tools for embedded systems10.1145/2597809.2597825(135-144)Online publication date: 12-Jun-2014
https://dl.acm.org/doi/10.1145/2597809.2597825
Borin EAraujo GBreternitz MWu Y(2014)Microcode Compression Using Structured-Constrained ClusteringInternational Journal of Parallel Programming10.1007/s10766-012-0206-942:1(140-164)Online publication date: 1-Feb-2014
https://dl.acm.org/doi/10.1007/s10766-012-0206-9
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Enhanced code density of embedded CISC processors with echo technology

Huffman-based code compression techniques for embedded processors

Improving Code Density with Variable Length Encoding Aware Instruction Scheduling