Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
1999-01-29
2001-11-13
Chaki, Kakali (Department: 2122)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
Reexamination Certificate
active
06317867
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
The present invention relates to a method and system for compressing data in general. More particularly, the present invention relates to a method and system for compressing an executable program.
2. Description of the Prior Art
As software systems become more complex, the executable code of the programs implementing these systems have grown large in size. 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. 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. Highly efficient code compression mitigates the disadvantage of large executable sizes. However, compressing executable programs has traditionally been difficult.
The fundamental reason of why compressing executable code is difficult is the lack of common patterns that a traditional compressor can discern easily. In prior art, compression schemes use some form of spatial or temporal proximity when analyzing the input stream. Alternatively, a traditional compressor may use some form of a histogram to gather information about the various patterns that occur within an input stream. In either case, similar instructions that follow a common pattern may not necessary occur close to one another. Furthermore, forming a histogram may not be straightforward if instructions do not follow uniform formats, such as in Complex Instruction Set Architecture (CISC) or an elaborate Reduced Instruction Set Architecture like the PowerPC, which contains over 30 different instruction formats.
Disclosed herein is a better approach than the traditional schemes, where instructions are clustered within a program according to common patterns. The instructions within each cluster are then compressed independently by an appropriate compressor. Operating on a cluster instead of the entire instruction stream, a traditional compressor is effective in producing compact code due to the ease of discerning patterns among structurally similar instructions, and the limited number of patterns within each cluster. It is also desirable to use different compressors for different clusters. Therefore there is a need to maximize the compression of an overall program by grouping instructions within the program into clusters, then compressing each cluster using the compression scheme that would yield the best results for that particular cluster. 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 programs.
It is another object of the present invention to provide an improved method and system for compressing executable programs by clustering instructions such that instructions within each cluster show similar patterns.
It is yet another object of the present invention to provide an improved method and system for compressing the clusters of instructions using different compressors, such that each cluster is compressed independently by an appropriate compressor to produce highly compressed code.
In accordance with a method and system of the present invention, a compression scheme for program executables is disclosed. First, instruction clustering starts by placing each instruction in a cluster by itself. The method and system then compute in an iterative manner the distance between clusters, and merge the nearest clusters to form larger clusters. Therefore, instructions are clustered into groups, such that instructions belonging to the same cluster show similar bit patterns. This process stops when the number of clusters reaches a pre-specified goal. This goal is defined empirically, and may be adjusted if better compression can result. After all clusters have been defined, a suitable compressor is applied to each cluster to produce the compressed executable.
All objects, features, and advantages of the present invention will become apparent in the following detailed written description.
REFERENCES:
patent: 5729228 (1998-03-01), Franaszek et al.
patent: 5764994 (1998-06-01), Craft
patent: 6125201 (2000-09-01), Zador
Lekatsas et al. Code Compression for Embedded Systems. ACM. pp. 516-521, Jun. 1998.*
Breternitz Jr et al. Enhanced Compression Techniques to Simplify Program Decompression and Execution. IEEE. pp. 170-176, Apr. 1997.*
Arnavut et al. Block Sorting and Compression. IEEE. pp. 181-190, Apr. 1997.*
Lefurgy et al. Improving Code Density Using Compression Techniques. IEEE. pp. 194-203, Jan. 1997.*
Tong L. 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, “Code Compression,” University of Arizona, pp. 358-365.
Bracewell & Patterson L.L.P.
Chaki Kakali
International Business Machines - Corporation
Salys Casimer K.
Zhen Wei
LandOfFree
Method and system for clustering instructions within... 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 clustering instructions within..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for clustering instructions within... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2586967