Method and apparatus for object code compression and decompression for computer systems

Patent 6732256 Issued on May 4, 2004. Estimated Expiration Date:

June 17, 2023. Estimated Expiration Date is calculated based on simple USPTO term provisions. It does not account for terminal disclaimers, term adjustments, failure to pay maintenance fees, or other factors which might affect the term of a patent.

Abstract Claims Description Full Text

Patent References

Microcomputer executing compressed program and generating compressed branch addresses
Patent #: 5632024
Issued on: 05/20/1997
Inventor: Yajima, et al.

Processor for discriminating between compressed and non-compressed program code, with prefetching, decoding and execution of compressed code in parallel with the decoding, with modified target branch addresses accommodated at run time
Patent #: 5652852
Issued on: 07/29/1997
Inventor: Yokota

Computer system for executing instruction stream containing mixed compressed and uncompressed instructions by automatically detecting and expanding compressed instructions
Patent #: 5784585
Issued on: 07/21/1998
Inventor: Denman

Method and apparatus for allowing execution of both compressed instructions and decompressed instructions in a microprocessor
Patent #: 5794010
Issued on: 08/11/1998
Inventor: Worrell, et al.

Processor transparent on-the-fly instruction stream decompression Patent #: 6199126
Issued on: 03/06/2001
Inventor: Auerbach, et al.

Inventors

Assignee

Application

No. 10462675 filed on 06/17/2003

US Classes:

712/208, INSTRUCTION DECODING (E.G., BY MICROINSTRUCTION, START ADDRESS GENERATOR, HARDWIRED)717/136Translation of code

Examiners

Primary: Kim, Kenneth S.

Attorney, Agent or Firm

Sughrue Mion, PLLC

International Class

G06F 930

Abstract

A code compression method and apparatus for system-level power optimization that lessens the requirements imposed on main memory size. The apparatus utilizes a post-cache architecture that has a decompression engine that decompresses compressed object code instructions using dictionary look-up tables, branching instruction controllers and mathematical derivations based on bit toggling. The decompression engine extracts the compressed instructions from memory or the instruction/data cache using a bus compression technique to save power as the compressed instructions/data traverses the bus.

Other References

Texas Instruments Inc., TI's 0.07-Micron CMOS Technology Ushers in Era of Gigahertz DSP and Analog Performance, pp. 1-4, 1999.
T.M. Kemp, R.K. Montoye, J.D. Harper, J.D. Palmer and D.J. Auerbach, A Decompression Core for PowerPC, IBM J. Res. Develop. vol. 42 No. 6, pp. 807-811, Nov. 1988.
T. Okuma, H. Tomiyama, A. Inoue, E. Fajar and H. Yasuura, Instruction Encoding Techniques for Area Minimization of Instruction ROM, IEEE, pp. 125-130, 1998.
Luca Benini, Alberto Macii, Encrico Macii and Massimo Poncino, Selective Instruction Compression for Memory Energy Reduction in Embedded Systems, ACM, pp. 206-211, 1999.
Bharat P. Dave, Ganesh Lakshminarayana, Niraj K. Jha, COSYYN: Hardware-Software Co-Synthesis of Embedded Systems, ACM, pp. 703-708, 1997.
Mircea R. Stan and Wayne P. Burleson, Bus-Invert Coding for Low-Power I/O, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 3, No. 1, pp. 49-58, Mar. 1995.
William Fornaciari, Donatella Sciuto and Cristina Silvano, Power Estimation for Architectural Exploration of HW/SW Communication on System-Level Buses, ACM, pp. 152-156, 1999.
Inki Hong, Darko Kirovski, Gang Qu, Miodrag Potkonjak and Mani B. Srivastava, Power Optimization of Variable Voltage Core-Based Systems, ACM, pp. 176-181, 1998.
Tohru Ishihara and Hiroto Yasuura, Voltage Scheduling Problem for Dynamically Variable Voltage Processors, ACM, pp. 197-202, 1998.
Cheng-Ta Hsieh, Massoud Pedram, Gaurav Mehta and Fred Rastgar, Profile-Driven Program Synthesis for Evaluation of System Power Dissipation, ACM, pp. 576-581, 1997.
Vivek Tiwari, Sharad Malik, Andrew Wolfe and Mike Tien-Chien Lee, Instruction Level Power Analysis and Optimization of Software, Journal of VLSI Signal Processing, pp. 1-18, 1996.
Vivek Tiwari, Sharad Malik and Andrew Wolfe, Power Analysis of Embedded Software: A First Step Towards Software Power Minimization, IEEE Transactions on VLSI Systems, Dec. 1994.
Mike Tien-Chen Lee, Vivek Tiwari, Sharad Malik and Masahiro Fujita, Power Analysis and Minimization Techniques for Embedded DSP Software, IEEE Transactions on VLSI Systems, Dec. 1996.
Qinru Qiu, Qing Wu and Massoud Pedram, Stochastic Modeling of a Power-Managed System: Construction and Optimization, ACM, pp. 194-199, 1999.
Luca Benini, Alessandro Bogliolo, Giuseppe A. Paleologo and Giovanni De Micheli, Policy Optimization for Dynamic Power Management, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 18, No. 6, pp. 813-833, Jun. 1999.
Tony Givargis and Frank Vahid, Interface Exploration for Reduced Power in Core-Based Systems, IEEE, pp. 117-122, 1998.
Jue-Hsien Chern, Jean Huang, Lawrence Arledge, Ping-Chung Li, and Ping Yang, Multilevel Metal Capacitance Models for CAD Design Synthesis Systems, IEEE Electron Device Letters, vol. 13, No. 1, pp. 32-34, Jan. 1992.
Yanbing Li and Jörg Henkel, A Framework for Estimating and Minimizing Energy Dissipation of Embedded HW/SW Systems, ACM, pp. 188-193, 1998.
Paul G. Howard and Jeffrey Scott Vitter, Practical Implementations of Arithmetic Coding, Brown University, pp. 1-30, 1992 (a similar version appears in Image and Text Compression, pp 85-112, 1992).
G.V. Cormack and R.N.S. Horspool, Data Compression Using Dynamic Markov Modelling, The Computer Journal, vol. 30. No. 6, pp. 541-550, 1987.
Jacob Ziv and Abraham Lempel, A Universal Algorithm for Sequential Data Compression, IEEE Transactions on Information Theory, vol. IT-23, No. 3, pp. 337-343, May 1977.
Ian H. Witten, Radford M. Neal and John G. Cleary, Arithmetic Coding For Data Compression, Communications of the ACM, vol. 30, No. 6, pp. 520-540, Jun. 1987.
Nagisa Ishiura and Masayuki Yamaguchi, Instruction Code Compression for Application Specific VLIW Processors Based on Automatic Field Partitioning, pp. 105-109. (Research Paper).
Darko Kirovski, Johnson Kin and William H. Mangione-Smith, Procedure Based Program Compression, The Departments of Computer Science and Electrical Engineering, The University of California at Los Angeles.
Kevin D. Kissell, MIPS16: High-Density MIPS for the Embedded Market, ( A version of this paper appears in the proceedings of the RTS97 conference).
Michael Kozuch and Andrew Wolfe, Compression of Embedded System Programs, (Appeared in ICCD 1994).
Guido Araujo, Paulo Centoducatte, Mario Cortes and Ricardo Pannain, Code Compression Based on Operand Factorization (Research Paper).
Martin Benes, Andrew Wolfe and Steven M. Nowick, A High-Speed Asynchronous Decompression Circuit for Embedded Processors (Research Paper).
Martin Benes, Steven M. Nowick and Andrew Wolfe, A Fast Asynchronous Huffman Decoder for Compressed-Code Embedded Processors (Research Paper).
Luca Benini, Alberto Macii, Enrico Macii and Massimo Poncino, Selective Instruction Compression for Memory Energy Reduction in Embedded Systems, ACM, pp. 206-211, 1999.
Peter L. Bird and Trevor N. Mudge, An Instruction Stream Compression Technique, EECS Department, University of Michigan, (Technical Report) pp. 1-21, Nov. 27, 1996.
John Bunda, Donald Fussell, Roy Jenevein and W.C. Athas, 16-Bit v. 32-Bit Instructions for Pipelined Microprocessors, Department of Computer Sciences, The University of Texas at Austin, (Technical Report) pp. 1-28, Oct. 23, 1992.
Paulo Centoducatte, Guido Araujo and Ricardo Pannain, Compressed Code Execution on DSP Architectures (Research Paper).
I-Cheng K. Chen, Peter L. Bird and Trevor Mudge, The Impact of Instruction Compression on I-cache Performance, University of Michigan, Technical Report CSE-TR-330-97, University of Michigan, pp. 1-7.
Lars Raeder Clausen, Ulrik Pagh Schultz, Charles Consel and Gilles Muller, Java Bytecode Compression for Embedded Systems, Institut De Recherche En Informatique Et Systèmes Aléatoires (IRISA), Publication No. 1213, pp. 1-22, Dec. 1998.
Thomas M. Conte, Sanjeev Banerjia, Sergei Y. Larin, Kishore N. Menezes and Sumedh W. Sathaye, Instruction Fetch Mechanisms for VLIW Architectures with Compressed Encodings, IEEE, pp. 201-211, 1996.
Keith D. Cooper and Nathaniel McIntosh, Enhanced Code Compression for Embedded RISC Processors, (Research Paper).
Jens Ernst, William Evans, Christopher W. Fraser, Steven Lucco and Todd A. Proebsting, Code Compression, (Research Paper).
Christopher W. Fraser and Todd A. Proebsting, Custom Instruction Sets for Code Compression, pp. 1-9, Oct. 19, 1995.
Jan Hoogerbrugge, Lex Augusteijn, Jeroen Trum and Rik Van de Wiel, A Code Compression System Based on Piplined Interpreters, Software Practice and Experience, pp. 1005-1023, 1999.
David A. Huffman, A Method for the Construction of Minimum-Redundancy Codes, Proceedings of the I.R.E., pp. 1098-1101, Sep. 1952.
Charles Lefurgy, Eva Piccininni and Trevor Mudge, Evaluation of a High Performance Code Compression Method, IEEE, 1999.
Charles Lefurgy, Eva Piccininni and Trevor Mudge, Reducing Code Size with Run Time Decompression, EECS Department, University of Michigan, (Research Paper).
Charles Lefurgy, Peter Bird, I-Cheng Chen and Trevor Mudge, Improving Code Density Using Compression Techniques, IEEE, 1999.
Charles Lefurgy and Trevor Mudge, Code Compression for DSP, EECS Department, University of Michigan, CSE-TR-380-98, pp. 1-5.
Charles Lefurgy and Trevor Mudge, Fast Software-managed Code Decompression, EECS Department, University of Michigan, presented at CASES '99, pp. 1-5, Oct. 1-3, 1999.
Haris Lekatsas and Wayne Wolf, Code Compression for Embedded Systems, Department of Electrical Engineering, Princeton University, (Research Paper).
Haris Lekatsas and Wayne Wolf, SAMC: A Code Compression Algorithm for Embedded Processors, Department of Electrical Engineering, Princeton University, pp. 1-17, Nov. 1, 1999.
Haris Lekatsas and Wayne Wolf, Random Access Decompression Using Binary Arithmetic Coding, Department of Electrical Engineering Princeton University, (Research Paper).
Stan Y. Liao, Sprinivas Devadas and Kurt Keutzer, Code Density Optimization for Embedded DSP Processors Using Data Compression Techniques, (Research Paper).
Stan Liao, Sprinivas Devadas and Kurt Keutzer, A Text-Compression-Based Method for Code Size Minimization in Embedded Systems, pp. 1-38, 1998.
Advanced RISC Machines (ARM), An Introduction to Thumb™, pp. 9-26, Mar. 1995.
Maarten Wegdam, Compact Code Generation through Custom Instruction Sets, Nat. Lab. Unclassified Report 822/98, pp. 1-60, Sep. 1998.
Andrew Wolfe and Alex Chanin, Executing Compressed Programs on An Embedded RISC Architecture, (Appears in Proceedings of 25th Annual International Symposium on Microarchitecture), pp. 1-19, Dec. 1992.
Yukihiro Yoshida, Boa-Yu Song, Hiroyuki Okuhata, Takao Onoye and Isao Shirakawa, An Object Code Compression Approach to Embedded Processors, ACM, pp. 265-268, 1997.