Method and system for clustering instructions within executable code for compression

[0002] This application relates to co-pending applications, entitled “METHOD AND SYSTEM FOR COMPRESSING REDUCED INSTRUCTION SET COMPUTER (RISC) EXECUTABLE CODE THROUGH INSTRUCTION SET EXPANSION”, now U.S. Pat. No. 6,195,743 “METHOD AND SYSTEM FOR COMPRESSING REDUCED INSTRUCTION SET COMPUTER (RISC) EXECUTABLE CODE”, application Ser. No. 09/239,259 and “METHOD AND SYSTEM FOR SCOPE-BASED COMPRESSION OF REGISTER AND LITERAL ENCODING IN A REDUCED INSTRUCTION SET COMPUTER (RISC)”, now U.S. Pat. No. 6,233,674, all filed of even date herewith and assigned to the assignee herein named, the subject matter of each of which is incorporated herein by reference.

[0003] 1. Technical Field

[0004] 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.

[0005] 2. Description of the Prior Art

[0006] 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.

[0007] 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.

[0008] 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.

[0009] 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.

[0010] 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.

[0011] 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.

[0012] 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.

[0013] 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.

[0014] All objects, features, and advantages of the present invention will become apparent in the following detailed written description.

[0015] The invention itself, as well as a preferred mode of use, further objects, and advantages thereof, will best be understood by reference to the following detailed description of an illustrative embodiment when read in conjunction with the accompanying drawings, wherein:

[0016] FIG. 1 is a block diagram of a compressor unit in which a preferred embodiment of the present invention may be incorporated; and

[0017] FIG. 2 is a high-level flowchart illustrating the steps for clustering instructions within a program executable.

[0018] Those skilled in the art may appreciate that the disclosed invention herein may be implemented in hardware or in software. With reference now to the figures and in particular with reference to FIG. 1, there is depicted a block diagram of a data compressor unit in which a preferred embodiment of the present invention may be incorporated. As shown, compressor unit 52 is coupled to a controller 54 and a random-access memory (RAM) 56. The controller 54 contains the permanent logic of the compressor in the form of non-volatile memory. During operation, compressor unit 52 receives from a data source 58 an uncompressed stream representing the executable. After clustering the instructions within the program as described herein, the compressor applies different compression techniques on various clusters and produces the compressed data stream to a data sink 60. The data sink 60 could be a storage device or a communication link.

[0019] The main idea of the disclosed technique follows. When compressing executable code of a computer program, a compressor would not achieve the best results because the sequence of instructions according to the order in which they appear in a program may not easily reveal common patterns that could be exploited in compression. The technique disclosed herein clusters instructions into groups, such that instructions belonging to the same cluster show common patterns. In accordance with the preferred embodiment of the present invention, the clustering starts by placing each instruction in a cluster by itself. The method then computes in an iterative fashion the distance between clusters, and merges the nearest clusters to form larger clusters. The method stops when the number of clusters reaches a pre-specified goal. This goal is defined empirically, and it could 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.

[0020] Referring now to FIG. 2, there is illustrated a high-level flowchart for implementing the clustering technique in accordance with the present invention. Before following the flowchart however, we must first define the majority bit m of n bits to be 0 if t bits out of n are 0, 1 if t bits out of n are 1, or x (don't care) otherwise, where t>n/2. We call t the majority threshold. Next, the modulus |a | of a 32 -bit quantity “a” as the number of bits equal 1 in “a”. The average of a group of n 32 -bit instructions is defined as the 32 -bit quantity a₀, a₁, . . . , a₃₁where:

[0021] a_i=m(b_ij), where b_ijis the i^thbit of the j^thinstruction, j≦n.

[0022] The distance d between any two 32 -bit instructions i and j is defined as:

[0023] d(i,j)=|i ⊕j| where ⊕ is the bitwise XOR of the two instructions. The distance d between an instruction i and the average j of a set of n instructions is computed in the same manner as the distance between two instructions, except that when a don't care bit is XOR'ed with 1 or 0, it produces 1. Similarly, define the distance d between the averages of two sets of instructions in the same manner.

[0024] Referring to FIG. 2, the technique for clustering starts at step 98 with the variable T set equal to zero, and C the number of clusters set equal to n, the number of instructions, as shown in step 98. The variable T represents the threshold for deciding when to merge two clusters. The process proceeds to step 100, with variables i and j set equal to one. These variables are used for iterating over the available clusters and computing the distances between them as defined above. The process continues to step 102 with j equal to i +1. At this point in the process the distance d between any two clusters ci and cj is examined in step 104 to see if it is less than T. If it is, the process proceeds to step 116 and the clusters are merged and cj is set to empty in step 118. C is then equal to C minus 1 and checked to see if it matches with G, shown in steps 120 and 122. When C equals G than the process ends at step 124 as described above. G is the desired number of clusters.

[0025] If the test in step 104 fails, then processing proceeds to step 106 which together with steps 108, 110 and 114 implement two nested loops that enable the process to compute the distances among every two conceivable clusters. After all such possible combinations have been examined, it is clear that the threshold for combining clusters is too tight. Therefore, it is relaxed by incrementing the variable T in step 112. This process continues, until the desired cluster level is reached in step 122.

[0026] After all clusters have been formed, the compressor applies traditional compression schemes on the various clusters and produces the best combination of results.

[0027] It is also important to note that although the present invention has been described in the context of a hardware compressor, those skilled in the art will appreciate that the mechanisms of the present invention can be implemented in software and be distributed as a program product in a variety of forms, and that the present invention applies equally regardless of the particular type of signal bearing media utilized to actually carry out the distribution. Examples of signal bearing media include but are not limited to recordable type media such as floppy disks or CD ROMs, and transmission type media such as analog or digital communications links.

[0028] While the invention has been particularly shown and described with reference to a preferred embodiment, it will be understood by those skilled in the art that various changes in form and detail may be made therein without departing from the spirit and scope of the invention.