Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
2000-04-21
2004-02-10
Kim, Kenneth S. (Department: 2181)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
C712S041000, C710S068000
Reexamination Certificate
active
06691305
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field of the Invention
This invention is related to a method and apparatus for compressing and decompressing object code instructions that are included in a software program that executes on a computer system. In particular, the compressing of object code instructions for a computer system provides for lower power consumption by the computer, more efficient transferal of compressed object code instructions from the memory storage devices, and a reduction in the number and size of power-consuming memory storage devices. The decompression apparatus of the invention advantageously uses a decompression engine to achieve the energy consumption savings incorporated into the compressed object code instructions. The invention is embodied in a compression method that compresses object code instructions for a computer system, a computer system for implementing the compression method, a computer program product bearing software instructions that implement the compression method, a decompression method that decompresses the compressed object code instructions and a decompression engine that decompresses the compressed object code instructions.
2. Description of the Related Art
The following references provide useful background information on the indicated topics, all of which relate to the invention, and are incorporated herein by reference:
M. Keaton and P. Bricaud,
Reuse Methodology Manual for System
-
On
-
A
-
Chip Designs
, Kluwer Academic Publishers (1998);
TI's
0.07
Micron CMOS Technology Ushers In Era of Gigahertz DSP and Analog Performance
, Texas Instruments, (1998);
T. M. Kemp, R. K. Montoye, J. D. Harper, J. D. Palmer and D. J. Auerbach,
A Decompression Core for PowerPC
, IBM Journal of Research and Development, vol. 42(6), pp. 807-812 (November 1998);
Y. Yoshida, B. Y. Song, H. Okuhata and T. Onoye,
An Object Code Compression Approach to Embedded Processors
, Proceedings of the International Symposium on Low Power Electronics and Design, pp. 265-268 (August 1997);
T. Okuma, H. Tomiyama, A. Inoue, E. Fajar and H. Yasuura,
Instruction Encoding Techniques for Area Minimization of Instruction ROM
, International Symposium on System Synthesis, pp. 125-130 (December 1998);
A. Wolfe and A. Chanin,
Executing Compressed Programs on an Embedded RISC Architecture
, Proceedings of 25
th
Annual International Symposium on MicroArchitecture, pp. 81-91, (December 1992).
C. Lefurgy, P. Bird, I. Cheng and T. Mudge,
Code Density Using Compression Techniques
, Proceedings of the 30
th
Annual International Symposium on MicroArchitecture, pp. 194-203 (December 1997);
S. Y. Liao, S. Devadas and K. Keutzer,
Code Density Optimization for Embedded DSP Processors Using Data Compression Techniques
, Proceedings of the 1995 Chapel Hill Conference on Advanced Research in VLSI, pp. 393-399 (1995);
D. A. Huffman,
A Method for the Construction of Minimum
-
Redundancy Codes
, Proceedings of the IRE, vol. 4D, pp. 1098-1101 (September 1952);
L. Benini, A. Macii, E. Macii and M. Poncino,
Selective Instruction Compression for Memory Energy Reduction in Embedded Systems
, IEEE/ACM Proceedings of International Symposium on Low Power Electronics and Design, pp. 206-211 (1999);
B. P. Dave, G. Lakshminarayana, and N. K. Jha, COSYN:
Hardware
-
Software Co
-
Synthesis of Embedded Systems
, Proceedings of Design Automation Conference, pp. 703-708 (1997);
I. Hong, D. Kirovski, G. Qu, M. Potkonjak and M. Srivastava,
Power Optimization of Variable Voltage Core
-
Based Systems
, Proceedings of Design Automation Conference, pp.176-181 (1998);
T. Ishihara and H. Yasuura,
Voltage Scheduling Problem for Dynamically Variable Voltage Processors
, IEEE/ACM Proceedings of International Symposium on Low Power Electronics and Design, pp. 197-201 (1998);
C. Ta Hsieh, M. Pedram, G. Mehta and F. Rastgar,
Profile
-
Driven Program Synthesis for Evaluation of System Power Dissipation
, IEEE Proceedings of 34
th
Design Automation Conference, pp. 576-581, 1997;
V. Tiwari,
Logic and System Design for Low Power Consumption
, Ph.D thesis, Princeton University (November 1996);
Q. Qiu, Q. Wu and M. Pedram,
Stochastic Modeling of a Power
-
Managed System: Construction and Optimization
, IEEE/ACM Proceedings of International Symposium on Low Power Electronics and Design, pp. 194-199 (1999);
L. Benini, A. Bogliolo, G. Paleologo and G. De Micheli,
Policy Optimization for Dynamic Power Management
, IEEE Transactions on CAD, vol. 18, no. 6, pp. 813-33 (June 1999);
W. Fornaciari, D. Sciuto and C. Silvano,
Power Estimation for Architectural Explorations of HW/SW Communication on System
-
Level Buses
, HW/SW Codesign Workshop, Rome (May 1999);
M. R. Stan and W. P. Burleson,
Bus
-
Invert Coding for Low Power I/O
, IEEE Transactions on VLSI (March 1995);
M. R. Stan and W. P. Burleson,
Limited
-
Weight Codes for Low Power I/O
, International Workshop on Low Power Design (April 1994);
T. Givargis and F. Vahid,
Interface Exploration for Reduced Power in Core
-
Based Systems
, International Symposium on System Synthesis (December 1998);
Jue-Hsien Chern, et al.,
Multilevel Metal Capacitance Models for CAD Design Synthesis Systems
, IEEE Electron Device Letters, vol. 13, no. 1, pp. 32-34 (January 1992).
P. G. Howard and J. S. Vitter,
Practical Implementations of Arithmetic Coding
, invited paper in Images and Text Compression (Kluwer Academic Publishers, Norwell, Mass.).
There will now be provided a discussion of various topics to provide a proper foundation for understanding the invention.
The advent of new VLSI technologies as well as the advent of state-of-the-art design techniques like core-based System-on-a-Chip (hereinafter “SOC”) design methodologies, such as those described by Keaton and Bricaud in
Reuse Methodology Manual for System
-
on
-
a
-
Chip Designs
, has made multi-million gate chips a reality. SOC designs are especially important to low-power devices like personal digital assistants, cellular phones and digital cameras. Obviously, since the amount of available energy in a low-power device is limited, these devices have to wisely budget energy consumption in order to enable the user to increase the number and/or length of telephone calls, to shoot more pictures, etc., between recharging phases. From the viewpoint of a system designer, the reduction of energy/power consumption is a major design goal. The physically important factor power per square millimeter must be kept at reasonable levels to avoid overheating, malfunctions and electro-migration. Keeping power per square millimeter at reasonable levels leads to longevity of the device. Due to the various problems related to high energy and power consumption, designers have come up with diverse approaches at all levels of abstraction, starting from the physical level up to the system level. Experience shows that a high-level method may provide additional degrees of freedom that result in a more optimized design. However, a major drawback in system-level optimization is the complexity of the design space as a result of the vast amount of possible parameters. In order to conduct efficient system-level optimizations, powerful design space explorations are needed. In case of system-level power optimization, a tool that delivers fast and reliable power estimates for various chosen system parameters in order to evaluate the impact of any optimization step is required.
Code compression has increasingly become a popular technique, mainly as a method to reduce chip area in embedded computers. Most methods targeted for embedded systems use a run-time decompression unit to decode compressed instructions on-the-fly. Wolfe and Chanin were the first to propose such a scheme, wherein Huffman codes were used to encode cache blocks. A hardware decompression unit is interposed between the cache and main memory to decompress cache blocks to their original size before they are inserted into the cache. Kemp, et al. at IBM, developed a similar technique using sophisticated Huffman tables. Other techniques use a table to index sequences of freque
Henkel Jörg
Lekatsas Haris
Wolf Wayne
Kim Kenneth S.
NEC Corporation
LandOfFree
Object code compression using different schemes for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Object code compression using different schemes for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Object code compression using different schemes for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3284534