Electrical computers and digital processing systems: processing – Processing architecture – Microprocessor or multichip or multimodule processor having...
Reexamination Certificate
1999-01-29
2001-02-27
Coleman, Eric (Department: 2783)
Electrical computers and digital processing systems: processing
Processing architecture
Microprocessor or multichip or multimodule processor having...
C717S152000
Reexamination Certificate
active
06195743
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
The present invention relates to a method and system for compressing data in general and in particular to a method and system for compressing executable code. Still more particularly, the present invention relates to a method and system for compressing executable code in the context of Reduced Instruction Set Computer (RISC) architectures.
2. Description of the Prior Art
Reduced Instruction Set Computer (RISC) architectures simplify processor and compiler design by making all instructions have the same size and follow a few simple formats. A price to pay for these advantages is the large size of executable program code written using these instruction sets. The large code size reduces instruction cache effectiveness and utilization of memory resources. It also increases program-loading time when code is shipped over in a network environment or retrieved from a slow mechanical device like a disk.
Currently, network computers, embedded controllers, set-top boxes, hand-held devices and the like receive executables over a network or possibly through slow phone links or communication channels. Additionally, these devices may have very limited memory capacity that make large programs not fit in the available memory to run on the device. Therefore, for devices using RISC processors to be competitive in the market place, they may require highly efficient code compression that mitigates the disadvantage of large executable sizes.
Executable code written for RISC processors has traditionally been difficult to compress. Therefore there is a need for compressing instructions in a reduced instruction set computer (RISC) architecture such as the PowerPC family owned by International Business Machines. Traditional compressors in the prior art treat the instructions in a program as a stream of bits, and try to find patterns within this stream to help construct a more compact presentation of the program (e.g. Ziv-Lempel compression, Huffman encoding, etc.). However, RISC instructions often contain redundant fields. Redundant fields pose two problems. They pollute the compression model that a traditional compressor builds as it compresses the data, and therefore it will produce lower quality compression. Another problem with redundant fields is that they do not carry any information, yet a traditional compressor needs to generate code for them. The compressed code, however small it may be, does not convey any information. It one instead exploits the semantics of the instructions, a better solution is to eliminate the redundant fields so that the compressor does not have to generate code for them. These redundant fields then can be reconstructed during decompression in a straightforward manner. Therefore a need exists for a technique of identifying redundancy in RISC instructions and utilizing this information with commercial compression methods to yield better compression results. The present invention solves this problem by presenting a technique in a novel and unique manner, which is not previously known in the art.
SUMMARY OF THE INVENTION
In view of the foregoing, it is therefore an object of the present invention to provide an improved method and system for compressing executable code in the context of RISC processors.
It is another object of the present invention to provide an improved method and system to expand a RISC instruction set by exploiting the semantics of existing instructions and designing additional instructions that have no redundancy.
It is yet another object of the present invention to provide an improved method and system for compressing executable code in the context of RISC processors by rewriting a program using an expanded instruction set designed specifically to have little or no redundancy.
In accordance with a method and system of the present invention, a compression scheme for program executables that run in a reduced instruction set computer (RISC) architecture such as the PowerPC is disclosed. The method and system add opcodes to the RISC instruction set, producing instructions that have no redundant fields. The program is then rewritten using this new expanded instruction set, replacing many instructions from the original set that contain redundant fields with new instructions that contain no redundancy. A conventional compression technique such as Huffman encoding is then applied on the resulting code to produce better compression ratio than if it were to operate on the code written in the unexpanded instruction set.
All objects, features, and advantages of the present invention will become apparent in the following detailed written description.
REFERENCES:
patent: 5680600 (1997-10-01), Childers
patent: 5946489 (1999-08-01), Yellin
patent: 6005503 (1999-12-01), Burrows
Tong Lai Yu, “Data Compression for PC Software Distribution,” Software Practice and Experience, vol. 26(11), pp. 1181-1195, Nov. 1996.
Christopher Fraser et al, “Custom Instruction Sets for Code Compression,” pp. 1-9, Oct. 19, 1995.
Michael Franz et al., “Slim Binaries,” Department of Information and Computer Science, University of California at Irvine, pp. 1-16.
Jens Ernst et al., “Code Compression,” University of Arizona, pp. 358-365.
Coleman Eric
Felsman Bradley Vaden Gunter & Dillon, LLP
International Business Machines - Corporation
Salys Casimer K.
LandOfFree
Method and system for compressing reduced instruction set... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for compressing reduced instruction set..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for compressing reduced instruction set... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2584437