Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
2000-11-21
2004-06-08
Chaki, Kakali (Department: 2124)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
C708S627000
Reexamination Certificate
active
06748590
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to generating sequences of shift, add, and subtract instructions to perform multiplication by an integer value.
BACKGROUND OF THE INVENTION
Many implementations of computer processors do not have a multiply instruction. For those processors that do have a multiply instruction, it is often very expensive because it can take many machine clock cycles to perform a multiply instruction. However, it is possible to perform multiplication by an integer value using just normal arithmetic and logical unit (ALU) instructions of the processor such as the common shift, add, and subtract processor instructions. An unknown value can be multiplied by a power of 2 by shifting the unknown value left by the exponent of the power of 2. The original unknown value or an intermediate result can then be added or subtracted to achieve multiplication by integers that are not powers of 2. Usually shift, add, and subtract instructions can be performed in one machine clock cycle per instruction, so sequences of these instructions to perform multiplication are preferable to a multiply instruction when a sufficiently short sequence can be found that will execute faster than the multiply instruction.
Sequences of ALU instructions to perform integer multiplication by an integer value are commonly generated using either an analytical algorithm at compile time, or by looking up a sequence in a previously generated table.
Two possible analytical approaches to generating integer multiplication sequences are discussed in D. Knuth, The Art of Computer Programming, Vol. 2: Serinumerical Algorithms, 2nd Ed., Addison-Wesley, Reading, Mass., 1981, pp. 441-462 namely the binary method and the power tree method. These two methods are further discussed in R. Bernstein, Multiplication by Integer Constants, Software—Practice and Experience, vol. 16(7), pp. 641-652, John Wiley & Sons, Ltd. (1986) and combined into a hybrid method. This hybrid method can generate a sequence of shift, add, and subtract instructions for performing multiplication by any integer value. Furthermore, Bernstein's method generates very efficient sequences that are often the minimum number of instructions possible to perform the multiplication using just shift, add, and subtract instructions. However, a skilled assembly language programmer can sometimes find sequences of shift, add, and subtract instructions that are shorter than those generated using Bernstein's method.
Another method for generating efficient sequences of instructions for performing multiplication by integer values is through the use of a lookup table. This involves generating a table that holds the optimal sequence of ALU instructions for multiplication by each integer. The advantage to using this method is that every possible combination of shift, add, and subtract instructions that combine to achieve multiplication by a particular integer can be tested until the most efficient sequence is produced. The amount of time taken to generate these sequences is not a factor because they are generated separately beforehand, rather than during a programs compilation.
The disadvantage to using the lookup table method is that sequences for every possible integer value must be stored in the lookup table, which can require a large amount of memory storage. For example, assume that each ALU instruction can be encoded such that the instruction opcode and its operands can be packed into 32 bits. For 32-bit integers, multiplication can usually be performed in 20 shift, add, and subtract instructions or fewer, so 20*32 bits should be reserved for each sequence. To encode all of this information in a table for all 32-bit integers, (2{circumflex over ( )}{circumflex over ( )}32)*(20*32 bits)=343.6 terabytes of storage would be required. Since this amount of information is far too large to be incorporated into a compiler, the table size must be reduced by restricting the length of sequences, the number of sequences included in the table, or the amount of information for each instruction.
It is difficult to represent a sequence of instructions in a compact manner without losing some flexibility in the generated sequence of instructions. The lookup table method will likely impose a maximum length on sequences of instructions so that the table size is minimized, which constrains the possible sequences generated. Also, to minimize the size of the lookup table, a subset of all integers will usually be chosen to be represented in the table. The lookup table representation disclosed in U.S. Pat. No. 5,764,990 manages to pack representations of sequences for each integer into 64 bits in the lookup table. However, this lookup table implementation faces both the constraint that only a maximum of 8 instructions can be used in a sequence and that only numbers between −65536 and 65535 are generated so that the lookup table is not too large. This approach can not always represent the most efficient sequence of shift, add, and subtract instructions for all integers, but is quite good for smaller numbers that have short generated sequences.
Also, it has been shown in T. Granlund, P. Montgomery, Division By Invariant Integers using Multiplication, Association of Computing Machinery, 0-89791-662-x/94/0006 (1994) that division by integer constants can be accomplished using integer multiplication followed by a shift right instruction. Thus, sequences of shift, add, and subtract instructions can be used to accomplish integer division as well as multiplication.
Thus, it is desirable to provide a method, system and computer program product for generating an efficient sequence of ALU instructions for performing integer multiply operations that overcomes the foregoing and other disadvantages.
SUMMARY OF THE INVENTION
The present invention is an improvement on the analytical algorithm for generating ALU instruction sequences for performing integer multiplication described by Bernstein. The present invention analytically finds an optimal sequence of shift, add and subtract instructions for performing multiplication by any integer value, improving on the results of the Bernstein algorithm which in some cases produces longer instruction sequences than required for a particular integer multiplication.
The present invention has an advantage of generating instruction sequences having at most as many instructions as would be generated by the Bernstein algorithm but optimally generating sequences having fewer instructions than as would be generated using the Bernstein algorithm, thus facilitating the increased speed at which a compiled program could run and reducing the size of the program's code. By relying on a dependent chain of instructions, what Knuth calls a “star chain”, the present invention helps reduce the number of temporary registers required during multiply (and thus increase execution speed) because each instruction depends on the result of the preceding instruction. Further, the present invention helps the reduce the actual number of ALU instructions needed in a program to perform the multiply and hence helps reduce program size.
The present invention also has an advantage of not being significantly more expensive computationally. It looks for the same instruction sequences as Bernstein's hybrid binary and power tree algorithm using the same method, and only searches for the additional performance opportunities when a sufficiently fast instruction sequence is not found with Bernstein's method.
Further, the present invention has an advantage over the table lookup method of generating instruction sequences for performing multiplication by an integer value by not having to rely on a lookup table. To generate the same optimal sequences of ALU instructions of the present invention, a relatively large amount of information would need to be stored in a lookup table for each instruction sequence, resulting in a massive storage requirement. Moreover, the present invention has no upper limit to the highest integer value it can handle, a li
Cameron Douglas W.
Chaki Kakali
Dougherty Anne V.
Vu Tuan Anh
LandOfFree
Method for generating instruction sequences for integer... 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 for generating instruction sequences for integer..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for generating instruction sequences for integer... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3363724