Electrical computers and digital processing systems: processing – Processing control – Specialized instruction processing in support of testing,...
Reexamination Certificate
1999-01-29
2002-08-27
Ellis, Richard L. (Department: 2183)
Electrical computers and digital processing systems: processing
Processing control
Specialized instruction processing in support of testing,...
C712S209000
Reexamination Certificate
active
06442680
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 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 relatively large size of program code written using these instruction sets. The large code size reduces instruction cache effectiveness. 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 and other hand-held devices receive executables over the network or possibly slow phone links or communication channels. These devices may have very limited memory capacity and when their memory is constrained, large programs may not fit in the available memory to run on the device. Therefore, for RISC processors to be competitive in the market place, it is necessary to have highly efficient code compression that mitigates the disadvantage of large executable sizes.
Programs written in RISC instruction sets have traditionally been difficult to compress. There are several reasons for this.
First, RISC instructions contain redundant fields. These fields pollute the data space and reduce the effectiveness of the data model that a traditional compressor builds during compression, thereby reducing the compression ratio. Furthermore, a traditional compressor will still encode these redundant fields even if they do not convey any information.
Second, because the instructions typically take several formats, it is often difficult to discern patterns in the instructions within program code.
Third, RISC instructions use registers extensively, and compressing register encoding is very difficult because they are densely coded with very large information entropy.
Fourth, the values of literals vary widely with no discernible pattern or frequent use.
Therefore there is a need for compressing instructions in a Reduced Instruction Set Computer (RISC) architecture such as the PowerPC family. 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, consecutive instructions within a program may not easily exhibit patterns that a compressor can exploit. Therefore a need exists for:
removing redundancy from instructions
processing the program to expose more patterns for a traditional compressor such that it can be more effective in compression.
Devising a coding scheme for registers and literals to expose more patterns.
The present invention solves these problems 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 a Reduced Instruction Set Architecture (RISC).
It is another object of the present invention to provide an improved method and system for performing data compression by removing redundancy from the instructions through expanding the existing architecture to include artificial instructions encoded such that there is no redundancy.
It is yet another object of the present invention to provide an improved method and system which produces compression ratios between 3.5 to 4, compared to the 2 to 2.6 range of conventional compression.
It is still yet another object of the present invention to provide an improved method and system, which utilizes compression techniques that exploit the semantics of an instruction set architecture and where traditional compression techniques work in association to produce highly compressed code.
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. Initially, a RISC instruction set is expanded to produce code that facilitates the removal of redundant fields. The program to be compressed is rewritten using this new expanded instruction set. Next, a filter is applied to remove redundant fields from the expanded instructions. The expanded instructions are then clustered into groups, such that instructions belonging to the same cluster show similar bit patterns. The grouping could be done based on the instruction formats. For example, one may group branch instructions in one cluster, load/store instructions in one cluster, and so on. However, some instructions do not fall under this model, and for which there may be a need for a more sophisticated clustering mechanism. Within each cluster, scopes are created such that register usage patterns within each scope are similar. Within each cluster, further scopes are created such that literals within each scope are drawn from a close range of integers. A conventional compression technique such as Huffman encoding is then applied on each scope within each cluster. Furthermore, Huffman encoding is also applied on the opcodes of all instructions, thus making these opcodes function as anchors within the compressed stream. Dynamic programming techniques are then used to produce the best combination of encoding among all scopes within all the different clusters. As a result of using dynamic programming, scopes and clusters may be combined that use the same encoding scheme to reduce the size of the resulting dictionary.
All objects, features, and advantages of the present invention will become apparent in the following detailed written description.
REFERENCES:
patent: 5045852 (1991-09-01), Mitchell et al.
patent: 5463746 (1995-10-01), Brodnax et al.
patent: 5680600 (1997-10-01), Childers et al.
patent: 5703907 (1997-12-01), James
patent: 5729228 (1998-03-01), Franaszek et al.
patent: 5764994 (1998-06-01), Craft
patent: 5878267 (1999-03-01), Hampapuram et al.
patent: 5943421 (1999-08-01), Grabon
patent: 5945933 (1999-08-01), Kalkstein
patent: 5946489 (1999-08-01), Yellin et al.
patent: 6005503 (1999-12-01), Burrows
patent: 6121903 (2000-09-01), Kalkstein
patent: 6125201 (2000-09-01), Zador
“Improving Code Density Using Compression Techniques” by Lefurgy et al., 1997.*
“Custom Instruction Sets for Code Compression” by Fraser et al., 1995.*
“An Object Code Compression Approach to Embedded Processors” by Yoshida et al., 1997.*
“High Speed Pattern Matching for a Fast Huffman Decoder” by Choi et al., 1995.*
“Code Compression Based on Operand Factorization” by Araujo et al., 1998.
“Evaluation of a High Performance Code Compression Method” by Lefurgy et al, 1999.
Ernst et al., Code Compression, Proceedings of the 1997 ACM SIGPLAN conference on Programming language design and implementation, Jun. 16-18, 1997, Las Vegas, NV.*
Proebsting, Todd A., Optimizing an ANSI C Interpreter with Superoperators, Papers of the 22ndACM SIGPLAN-SIGACT symposium on Principles of programming languages, Jan. 23-25, 1995, San Francisco, CA.*
Lekatsas et al., Code Compression for Embedded Systems, Proceedings of the 35th annual confrence on Design automation conference, Jun. 15-19, 1998, San Francisco, CA.*
Lekatsas, et al., Code Compression for Embedded Systems, ACM, Jun. 1998, pp. 516-521.
Breternitz, Jr., et al., Enhanced Compression Techniques to Simplify Program Decompression and Execution, IEEE, Apr. 1997, pp. 170-176.
Arnavut, Block Sorting and Compression, IEEE, Apr. 1997, pp. 181-190.
Lefurgy, et al., Improving Code Density Using Compression Techniques,IEEE, Jan. 1997, pp. 194-203.
Kirovski, Darko, et al., Procedure Based Program Compression, IEEE, 1997, pp. 204-213.
Araujo, Guido, et al., Code C
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-2954777