More Web Proxy on the site http://driver.im/

article

The implementation and evaluation of dynamic code decompression using DISE

Authors:

Marc L. Corliss,

E. Christopher Lewis,

Amir RothAuthors Info & Claims

ACM Transactions on Embedded Computing Systems (TECS), Volume 4, Issue 1

Pages 38 - 72

https://doi.org/10.1145/1053271.1053274

Published: 01 February 2005 Publication History

Abstract

Code compression coupled with dynamic decompression is an important technique for both embedded and general-purpose microprocessors. Postfetch 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 postfetch decompression using a new hardware facility called dynamic instruction stream editing (DISE). DISE provides a programmable decoder---similar in structure to those in many IA-32 processors---that is used to add functionality to an application by injecting custom code snippets into its fetched instruction stream. We present a DISE-based implementation of postfetch decompression and show that it naturally supports customized program-specific decompression dictionaries, enables parameterized decompression allowing similar-but-not-identical instruction sequences to share dictionary entries, and uses no decompression-specific hardware. We present extensive experimental results showing the virtue of this approach and evaluating the factors that impact its efficacy. We also present implementation-neutral results that give insight into the characteristics of any postfetch decompression technique. Our experiments not only demonstrate significant reduction in code size (up to 35%) but also significant improvements in performance (up to 20%) and energy (up to 10%).

References

[1]

Advanced RISC Machines Ltd. 1995. An Introduction to Thumb. Advanced RISC Machines Ltd, Austin, TX.

[2]

Albonesi, D. 1999. Selective cache ways: On demand cache resource allocation. In Proceedings of the 32nd International Symposium on Microarchitecture. 248--259.

[3]

Araujo, G., Centoducatte, P., and Cortes, M. 1998. Code compression based on operand factorization. In Proceedings of the 31st International Symposium on Microarchitecture. 194--201.

[4]

Brooks, D., Tiwari, V., and Martonosi, M. 2000. Wattch: A framework for architectural-level power analysis and optimizations. In Proceedings of the 27th International Symposium on Computer Architecture. 83--94.

[5]

Burger, D. and Austin, T. M. 1997. The SimpleScalar Tool Set, Version 2.0. Tech. Rep. 1342, University of Wisconsin--Madison Computer Sciences Department.

[6]

Cooper, K. and McIntosh, N. 1999. Enhanced code compression for embedded RISC processors. In Proceedings of the ACM SIGPLAN '99 Conference on Programming Language Design and Implementation. 139--149.

[7]

Corliss, M. L., Lewis, E. C., and Roth, A. 2002. DISE: Dynamic Instruction Stream Editing. Tech. Rep. MS-CIS-02-24, University of Pennsylvania. July.

[8]

Corliss, M. L., Lewis, E. C., and Roth, A. 2003a. DISE: A programmable macro engine for customizing applications. In Proceedings of the 30th International Symposium on Computer Architecture. 362--373.

[9]

Corliss, M. L., Lewis, E. C., and Roth, A. 2003b. A DISE implementation of dynamic code decompression. In Proceedings of the Conference on Languages, Compilers, and Tools for Embedded Systems. 232--243.

[10]

Cormie, D. 2002. The ARM11 microarchitecture. ARM Ltd. White Paper.

[11]

Debray, S. and Evans, W. 2002. Profile-guided code compression. In Proceedings of the 2002 ACM SIGPLAN Conference on Programming Languages Design and Implementation. 95--105.

[12]

Debray, S. K., Evans, W., Muth, R., and B. De Sutter. 2000. Compiler techniques for code compression. ACM Trans. Program. Lang. Operating Syst. 22, 2 (Mar.), 378--415.

[13]

Diefendorf, K. 1998. K7 challenges Intel. Microprocess. Rep. 12, 14 (Nov.).

[14]

Ernst, J., Evans, W., Fraser, C., Lucco, S., and Proebsting, T. 1997. Code compression. In Proceedings of the ACM SIGPLAN '97 Conference on Programming Language Design and Implementation. 358--365.

[15]

Glaskowsky, P. 2000. Pentium 4 (partially) previewed. Microprocess. Rep. 14, 8 (Aug.).

[16]

Gwenapp, L. 1997. P6 microcode can be patched. Microprocess. Rep. 11, 12 (Sep.).

[17]

Kemp, T. M., Montoye, R. K., Auerback, D. J., Harper, J. D., and Palmer, J. D. 1998. A decompression core for PowerPC. IBM Syst. J. 42, 6 (November), 807--812.

[18]

Kirovski, D., Kin, J., and Mangione-Smith, W. 1997. Procedure based program compression. In Proceedings of the 30th International Symposium on Microarchitecture. 204--213.

[19]

Kissell, K. 1997. MIPS16: High-Density MIPS for the Embedded Market. Silicon Graphics MIPS Group, Mt. View, CA.

[20]

Lee, C., Potkonjak, M., and Mangione-Smith, W. 1997. Mediabench: A tool for evaluating and synthesizing multimedia and communications systems. In Proceedings 30th International Symposium on Microarchitecture. 330--335.

[21]

Lefurgy, C., Bird, P., Cheng, I.-C., and Mudge, T. 1997. Improving code density using compression techniques. In Proceedings of the 30th International Symposium on Microarchitecture. 194--203.

[22]

Lefurgy, C., Piccininni, E., and Mudge, T. 2000. Reducing code size with run-time decompression. In Proceedings of the 6th International Symposium on High-Performance Computer Architecture. 218--227.

[23]

Lekatsas, H., Henkel, J., and Wolf, W. 2000. Code compression for low power embedded system design. In Proceedings 36th Design Automation Conference. 294--299.

[24]

Liao, S., Devadas, S., and Keutzer, K. 1999. A text-compression-based method for code size minimization in embedded systems. ACM Trans. Design Autom. Electr. Syst. 4, 1 (Jan.), 12--38.

[25]

Nam, S.-J., Park, I.-C., and Kyung, C.-M. 1999. Improving dictionary-based code compression in VLIW architectures. IEICE Trans. Fundam. E82-A, 11 (Nov.), 2318--2324.

[26]

Phelan, R. 2003. Improving ARM Code Density and Performance. Tech. Rep., Advanced RISC Machines Ltd, Austin, TX.

[27]

Szymanski, T. 1978. Assembling code for machines with span dependent instructions. Commun. ACM 21, 4 (Apr.), 300--308.

[28]

Wilton, S. and Jouppi, N. 1994. An Enhanced Access and Cycle Time Model for On-Chip Caches. Tech. Rep., DEC Western Research Laboratory, Palo Alto, CA.

[29]

Wolfe, A. and Chanin, A. 1992. Executing compressed programs on an embedded RISC architecture. In Proceedings of the 25th International Symposium on Microarchitecture. 81--91.

[30]

Yang, S.-H., Powell, M., Falsafi, B., and Vijaykumar, T. 2002. Exploiting choice in resizable cache design to optimize deep-submicron processor energy-delay. In Proceedings 8th International Symposium on High Performance Computer Architecture.

Cited By

Lopes BEcco LXavier EAzevedo R(2016)Design and evaluation of compact ISA extensionsMicroprocessors & Microsystems10.1016/j.micpro.2015.09.01040:C(1-15)Online publication date: 1-Feb-2016
https://dl.acm.org/doi/10.1016/j.micpro.2015.09.010
Edler von Koch TFranke BBhandarkar PDasgupta A(2014)Exploiting function similarity for code size reductionACM SIGPLAN Notices10.1145/2666357.259781149:5(85-94)Online publication date: 12-Jun-2014
https://dl.acm.org/doi/10.1145/2666357.2597811
Edler von Koch TFranke BBhandarkar PDasgupta AZhang YKulkarni P(2014)Exploiting function similarity for code size reductionProceedings of the 2014 SIGPLAN/SIGBED conference on Languages, compilers and tools for embedded systems10.1145/2597809.2597811(85-94)Online publication date: 12-Jun-2014
https://dl.acm.org/doi/10.1145/2597809.2597811
Show More Cited By

Index Terms

The implementation and evaluation of dynamic code decompression using DISE
1. Computer systems organization
  1. Architectures
2. Hardware
  1. Integrated circuits
    1. Semiconductor memory

Recommendations

A DISE implementation of dynamic code decompression
LCTES '03: Proceedings of the 2003 ACM SIGPLAN conference on Language, compiler, and tool for embedded systems

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, ...
A DISE implementation of dynamic code decompression
Special Issue: Proceedings of the 2003 ACM SIGPLAN conference on Language, compiler, and tool support for embedded systems (San Diego, CA).

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, ...
Code compression for performance enhancement of variable-length embedded processors

Most of the work done in the field of code compression pertains to processors with fixed-length instruction encoding. The design of a code-compression scheme for variable-length instruction encodings poses newer design challenges. In this work, we first ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Embedded Computing Systems

ACM Transactions on Embedded Computing Systems Volume 4, Issue 1

February 2005

254 pages

ISSN:1539-9087

EISSN:1558-3465

DOI:10.1145/1053271

Issue’s Table of Contents

Copyright © 2005 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Journal Family

ACM Journals for the Design of Smart and Connected Systems

Publication History

Published: 01 February 2005

Published in TECS Volume 4, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
511
Total Downloads

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

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Lopes BEcco LXavier EAzevedo R(2016)Design and evaluation of compact ISA extensionsMicroprocessors & Microsystems10.1016/j.micpro.2015.09.01040:C(1-15)Online publication date: 1-Feb-2016
https://dl.acm.org/doi/10.1016/j.micpro.2015.09.010
Edler von Koch TFranke BBhandarkar PDasgupta A(2014)Exploiting function similarity for code size reductionACM SIGPLAN Notices10.1145/2666357.259781149:5(85-94)Online publication date: 12-Jun-2014
https://dl.acm.org/doi/10.1145/2666357.2597811
Edler von Koch TFranke BBhandarkar PDasgupta AZhang YKulkarni P(2014)Exploiting function similarity for code size reductionProceedings of the 2014 SIGPLAN/SIGBED conference on Languages, compilers and tools for embedded systems10.1145/2597809.2597811(85-94)Online publication date: 12-Jun-2014
https://dl.acm.org/doi/10.1145/2597809.2597811
(2014)ReferencesHigh-Performance Embedded Computing10.1016/B978-0-12-410511-9.16001-0(441-472)Online publication date: 2014
https://doi.org/10.1016/B978-0-12-410511-9.16001-0
Ecco LLopes BXavier EPannain RCentoducatte Pde Azevedo R(2009)SPARC16Proceedings of the 2009 21st International Symposium on Computer Architecture and High Performance Computing10.1109/SBAC-PAD.2009.22(169-176)Online publication date: 28-Oct-2009
https://dl.acm.org/doi/10.1109/SBAC-PAD.2009.22
Kumar RDas D(2008)Code compression for performance enhancement of variable-length embedded processorsACM Transactions on Embedded Computing Systems10.1145/1347375.13473887:3(1-36)Online publication date: 8-May-2008
https://dl.acm.org/doi/10.1145/1347375.1347388
(2007)ReferencesHigh-Performance Embedded Computing10.1016/B978-012369485-0/50010-5(467-499)Online publication date: 2007
https://doi.org/10.1016/B978-012369485-0/50010-5

View Options

Login options

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

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents