Parallel data processing in a single processor

The present invention relates to parallel data processing in a single processor system.

In general, single-processor systems sequentially perform two-operand operations. For example, in a 32-bit computer, each integer operand has 32 bits. In a 64-bit computer, each integer operand has 64 bits. Thus, an integer "Add" instruction in a 64-bit computer adds two 64-bit integer operands to produce a 64-bit integer result. For most pipelined 64-bit processors, a 64-bit add instruction takes one cycle of execution time.

In many cases, the relevant range of operands is 16 bits or less. However, current 32-bit and 64-bit computers still require a complete instruction to perform an operation on a pair of 16-bit operands. Thus, the number of execution cycles required to perform an operation on two 16-bit operands is the same as the number of execution cycles needed to complete the operation on 32-bit operands in a 32-bit operand. Computer or two 64-bit operands in a 64-bit computer.

In the prior art, parallel data processing required the repetition of functional units, each functional unit being able to handle data of the full word length. For example, Michael Flynn, Very High-Speed ​​Computing Systems. Proceedings of IEEE, Vol. 54, No. 12, December 1966, pages 1.901 to 1.909.

EP 0 395 348 A2 relates to a device for multi-gauge calculation with a CPU comprising four independent processing units which together have access to an instruction gauge, a cache memory, a memory management unit and a memory bus interface. Multiply subcommands are provided which multiply the bit or half word multiplicands by a common multiplier and return independent bit or half word products. Each processing unit comprises a 32-bit multiplier which is divisible into two independent 16-bit or four independent 8-bit multipliers. The multiply sub-instruction forms a signed multiplicand of each of the 4-bit or two-half words in a register B, each bit of the register B being multiplied by a register A. Each bit or half word is multiplied independently and the results are stored in the respective bits or half words of the product register. Only the high order 16 bits of register A are used as multipliers while the low order 16 bits of register A are ignored.

GB 215 498 A and GB 2 172 129 A describe binary adders and / or subtractors. In EP 0 231 899 A a multiplier array circuit is described.

However, such parallel processing implementations are significantly expensive in terms of both the hardware required and the complexity of the design.

SUMMARY OF THE INVENTION

In accordance with the preferred embodiment of the present invention, a system is presented that enables parallel data processing within a single processor. In order to allow parallel processing of data, an arithmetic logic unit or other operation-executing entity within the processing system, such B. a sliding device, parti tioned. Within each partition, operations are performed. If the operation to be performed refers to operands with a full word length, there is no parallel processing. Thus, data can run freely across boundaries between partitions. If the operation is performed using a plurality of operands whose word length is less than the full word length, the data is prevented from passing over at least one boundary between the partitions.

For example, if the operation is an addition operation (eg, a two's complement addition), each of the plurality of partitions performs an addition operation. If the addition to be made relates to operands of the full word length, carries can propagate between the partitions. If the addition operation is performed in parallel on a plurality of operand sets having a word length less than the full word length, a carry can not pass over at least one boundary between the partitions.

Similarly, when the operation is a shift, each of the plurality of partitions performs a shift operation. If the shift is to be done with operands of the full word length, the shifts between the partitions can be performed. When the operation is performed in parallel using a plurality of operands having a word length smaller than the full word length, a shift can not cross at least one boundary between the partitions.

Also in accordance with a preferred embodiment of the present invention, a multiplier implements both a multiplication of multiplicands whose length is equal to a whole word, and a parallel multiplication of subword multiplicand. Circuitry, such as an array of logical AND gates (or their equivalents), generates subproducts. Sub-product summer circuitry sums the sub-products to produce a result. A sub-product controller, in response to selecting a parallel multiplication of sub-word multiplicates, forces selected sub-products to have a value of zero, thereby implementing a parallel multiplication of sub-word multiplicands. If the multiplier implements an integer word multiplication, none of the subproducts will be forced to have a value of zero. For example, the partial product controller may be implemented using third inputs to at least a portion of the logical AND gates.

The present invention enables a single processor system to be significantly improved in performance by allowing parallel processing of operations when the operands are smaller in length than the entire word length. This convenient use of parallelism results in a significant performance gain for computations that can use this type of data parallelism without adding significant overhead to silicon space on a processor chip or design complexity. The present invention also allows parallel processing of operations performed by a processor to be performed in response to a single instruction.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 shows a simplified block diagram of an operation execution data path within a processor in accordance with preferred embodiments of the present invention.

FIG. 2 is a simplified block diagram of an arithmetic logic unit (ALU) shown in FIG. 1, in accordance with a preferred embodiment of the present invention.

FIG. 3 shows an implementation of a two's complement adder within the ALU shown in FIG. 2, in accordance with a preferred embodiment of the present invention.

Fig. 4 shows another simplified block diagram of the arithmetic logic unit (ALU) shown in Fig. 1 according to another preferred embodiment of the present invention.

Fig. 5 shows another other simplified block diagram of the arithmetic logic unit (ALU) shown in Fig. 1 according to another another preferred embodiment of the present invention.

Fig. 6 shows an implementation of a shifter shown in Fig. 1 according to a preferred embodiment of the present invention.

Fig. 7 shows a multiplier according to the prior art.

FIG. 8 shows a multiplier implemented according to preferred and 9 embodiments of the present invention. FIG.

Fig. 10 shows an implementation of a Carry Look-Ahead Adder within the ALU shown in Fig. 1 according to another preferred embodiment of the present invention.

Fig. 11 shows an example of a command layout according to another preferred embodiment of the present invention

DESCRIPTION OF THE PREFERRED EMBODIMENTS

FIG. 1 shows a simplified block diagram of an operation execution data path within a processor in accordance with preferred embodiments of the present invention. Operands for pending operations and results of operations performed are stored in general registers 25. When operations are performed, a first operand stored in a first register within the general registers 25 is placed on a first source bus 21. If the operation requires another operand, a second operand stored in a second register within the general registers 25 is placed on a second source bus 22.

After performing the operation, the result is placed on a result bus 23 and loaded into a register within the general register 25. The operation is performed by an arithmetic logic unit (ALU) 26 or 'by a shifter 29. A pre-shifter 27 and complement circuitry 28 may each be used to modify operands before they are received by the ALU 26. For a general background regarding the architecture of single processor systems constructed similarly to the present invention, see, for example, Ruby B. Lee, Precision Architecture, IEEE Computer, Vol. 22, No. 1, January 1989, pages 78 to 91 ,

In accordance with preferred embodiments of the present invention, the ALU may be partitioned to facilitate parallel data processing. For example, Figure 2 shows an ALU 26 divided into two partitions. A first partition 41 performs operations on low-order bits 42 of a first operand and low-order bits 43 of a second operand to produce results 44 for the low-order bits. A second partition 51 performs higher order bit 52 operations of the first operand and higher order bits 53 of the second operand to produce results 54 for the high order bits.

In response to a control input 49, a selector 50 is used to allow information on the data path 45 to pass from the first partition 41 to the second partition 51, or to intercept information on the data path 45 before coming from the first Partition 41 to the second partition 51 run. In particular, in arithmetic operations performed on full-word operands, information may pass from the first partition 41 through the selector 50 to the second partition 51. For performing parallel arithmetic operations on half-word operands, the selector 50 prevents information from the first partition 41 from going to the second partition 51. In general, in logic operations, there is no running of information from the first partition 41 to the second partition 51.

For example, in a computer having a 32-bit wide data path, each full-word operand has 32 bits. Therefore, when performing operations using 32-bit full-word operands, the selector 50 allows information from the first partition 41 to pass through the selector 50 to the second partition 51. When two parallel operations are performed using 16-bit half-word operands, the selector 50 prevents information from the first partition 41 from passing through the selector 50 to the second partition 51. Instead, the value is passed on a line 59 to the partition 51. When an "add" is performed, a logic zero is placed on the input line 59. When a "subtracting" is performed, a logic one is placed on the input line 59.

In the preferred embodiment of the present invention, a common arithmetic operation performed by the ALU 26 shown in FIG. 1 is a two's complement addition. As will be understood by those skilled in the art, the use of two's complement circuitry 28 to perform a two's complement on an operand before a two's complement addition operation is performed in the ALU implements a two's complement subtraction. Further, the use of a pre-shifter 27 to advance an operand before a two's compliment addition operation is performed in the ALU implements a shift-and-add operation.

Fig. 3 shows an implementation of a two's complement adder with carry-propagate addition within the ALU 26 in accordance with a preferred embodiment of the present invention. Alternatively, ALU 26 includes a carry-handle two's complement adder. A half adder 60 receives a single bit X & sub0; a first operand and a single bit Y & sub0; a second operand. The half adder 60 generates a sum bit 20 and a carry bit C0. A full adder 61 receives a single bit X & sub1; of the first operand, a single bit Y & sub1; of the second operand and the carry bit C0. The full adder 61 generates a sum bit Z & sub1; and a carry bit C & sub1 ;. A full adder 65 receives a single bit Xi-1. of the first operand, a single bit Yi-1 of the second operand, and a carry bit from a previous adder (ie, Ci-2, not shown). The full adder 65 generates a sum bit 2i-1 and a carry bit Ci-1. A full adder 66 receives a single bit X & sub1; of the first operand and a single bit Y & sub1; of the second operand. Further, depending on a value of an enable bit 49, the full adder 66 receives the carry bit Ci-1 through the selector 50 (or equivalent logic circuitry as will be apparent to those skilled in the art). The full adder 66 generates a sum bit 21 and a carry bit C₁. A full adder 69 receives a single bit of the first operand, a single bit of the second operand, and a tibertrag bit from a previous adder (not shown). The full adder 69 generates a sum bit Zi-1 and a carry bit Cj-1.

In the embodiment of the adder shown in FIG. 3, "j" is the size of the data path and the bit length of full word operations. Further, "i" is equal to "j" divided by 2. For example, "j" is equal to 32 and "i" is equal to 16.

The selector 50 is also shown in FIG. When operations are performed using "j" -bit full-word operands, the enable bit 49 is equal to a logical one and allows a carry through the selector 50 to propagate to the full-adder 66. When two parallel operations are performed using "i" -bit half word operands, the enable bit 49 is equal to a logic zero and prevents the carry from propagating through the selector 50 to the full adder 66. Instead, the value on line 59 is passed to full adder 66. When an "add" is performed, a logic zero is placed on the input line 59. When a "subtracting" is performed, a logical one is placed on the input line 59.

While FIGS. 2 and 3 discuss implementations of the ALU 26 with two partitions, an ALU designed in accordance with other preferred embodiments of the present invention may have different partitions. For example, FIG. 4 shows another simplified block diagram of the ALU 26 according to another preferred embodiment of the present invention. In Fig. 4, the ALU 26 is divided into four partitions. A first partition 71 performs operations on low-order bits 72 of a first operand and low-order bits 73 of a second operand to produce results 74 for the low-order bits. A second partition 81 performs operations on bits 82 of the first operand and bit 83 of the second operand to generate result bits 84. A third partition 91 performs operations on bits 92 of the first operand and bit 93 of the second operand to generate result bits 94. A fourth partition 101 performs operations on high-order bits 102 of the first operand and high-order bits 103 of the second operand to produce results 104 for high-order bits.

In response to a control input 79, a selector 80 is used to allow information on the data path 75 to pass from the first partition 71 to the second partition 81, or to intercept information on the data path 75 before it leaves the first partition 71 to the second partition 81 can run. In particular, for arithmetic operations performed on full-word operands or half-word operands, information may pass from the first partition 71 through the selector 80 to the second partition 81. For performing parallel arithmetic operations on quarter-word operands, the selector 80 prevents information from the first partition 71 from going to the second partition 81. Instead, the value is passed on a line 88 to the partition 81. When an "add" is performed, a logic zero is placed on line 88. When a "subtract" is performed, a logical one is placed on line 88. In general, logic operations do not propagate information between partitions.

In response to a control input 89, the selector 90 is used to run information on the data path 85 from the second partition 81 to the third partition 91, or to intercept information on the data path 85 before moving from the second partition 81 to the third Partition 91 can run. In particular, for arithmetic operations performed on full-word operands, information from the second partition 81 may pass through the selector 90 to the third partition 91. For performing parallel arithmetic operations on quarter-word operands or half-word operands, the selector 90 prevents information from the second partition 81 from going to the third partition 91. Instead, the value is passed on a line 98 to the partition 91. When an "add" is performed, a logic zero is placed on line 98. When a "subtract" is performed, a logical one is placed on line 98.

In response to a control input 99, the selector 100 is used to run information on the data path 95 from the third partition 91 to the fourth partition 101 or to intercept information on the data path 95 before moving from the third partition 91 to the fourth Partition 101 can run. In particular, in arithmetic operations performed on full-word operands and half-word operands, information may pass from the third partition 91 through the selector 100 to the fourth partition 101. For performing parallel arithmetic operations on quarter-word operands, the selector 100 prevents information from the third partition 91 from going to the fourth partition 101. Instead, the value is passed on a line 108 to the partition 101. When an "add" is performed, a logic zero is placed on line 108. When a "subtract" is performed, a logical one is placed on line 108.

For example, in a computer having a 64-bit wide data path, each full-word operand has 64 bits. Therefore, when performing operations using 64-bit full-word operands, the selector 80 allows information from the first partition 71 to pass through the selector 80 to the second partition 81, the selector 90 allows Information from the second partition 81 through the selector 90 to the third partition 91, and allows the selector 100 to that information from the third partition 91 can pass through the selector 100 to the fourth partition 101. When two parallel operations are performed using 32-bit half-word operands, the selector 80 allows information from the first partition 71 to pass through the selector 80 to the second partition 81, the selector 90 allows information to be passed from the second partition 81 through the selector 90 to the third partition 91, and allows the selector 100 to that information from the third partition 91 can pass through the selector 100 to the fourth partition 101. When four parallel operations are performed using 16-bit quarter-word operands, it prevents the selector 80 from passing information from the first partition 71 through the selector 80 to the second partition 81, preventing the selector 90 from receiving information from the second partition 81 through the selector 90 run to the third partition 91, and prevents the selection device 100, that information from the third partition 91 passes through the selector 100 to the fourth partition 101.

5 shows another other simplified block diagram of an ALU 26 according to another another preferred embodiment of the present invention. In Fig. 5, the ALU 26 is divided into partitions, each of which has a width of one bit. A first partition 111 performs operations on a low-order bit 112 of a first operand and a low-order bit 113 of a second operand to generate a low-order result bit 114. A second partition 121 performs operations on a bit 122 of the first operand and a bit 123 of the second operand to generate a result bit 124. A partition 131 performs operations on a bit 132 of the first operand and a bit 133 of the second operand to generate a result bit 134. A partition 141 performs operations on a bit 142 of the first operand and a bit 143 of the second operand to generate a result bit 144. A partition 151 performs operations on a high-quality bit 152 of the first operand and a high-quality bit 153 of the second operand to produce a high-quality result bit 154.

In response to a control input 119, a selector 120 is used to allow information on the data path 115 to pass from the first partition 111 to the second partition 121, or to intercept information on the data path 115 before being sent from the first partition 111 to the second partition 121 run. When data is intercepted, the value is passed on a line 128 to the partition 121. When an "add" is performed, a logic zero is placed on line 128. When a "subtract" is performed, a logical one is placed on line 128.

In response to a control input 129, a selector 130 is used to allow information to travel on a data path from an immediately prior partition (not shown) from the immediately preceding partition to the partition 131, or information in the data path from the immediate previous partition before they can run to partition 131. When data is intercepted, the value is passed on a line 138 to the partition 131. When an "add" is performed, a logic zero is placed on line 138. When a "subtract" is performed, a logical one is placed on line 138.

In response to a control input 139, a selector 140 is used to allow information on the data path 135 to pass from the partition 131 to a partition 141, or to intercept information on the data path 135 before proceeding from the partition 131 the partition 141 run. When data is intercepted, the value is passed on a line 148 to the partition 141. When an "add" is performed, a logic zero is placed on line 148. When a "subtract" is performed, a logical one is placed on line 148.

In response to a control input 149, a selector 150 is used to allow information to pass on a data path from an immediately preceding partition (not shown) from the immediately preceding partition to the partition 151, or information in the data path from the immediate previous partition before they can run to the partition 151. When data is intercepted, the value is passed on a line 158 to the partition 151. When an "add" is performed, a logic zero is placed on line 158. When a "subtract" is performed, a logical one is placed on line 158.

The control inputs to the selectors can be used to allow parallel processing of variable-length operands. For example, in a 64-bit wide data path processing system, the control inputs could be selected so that parallel processing of two 16-bit and four 8-bit arithmetic operations are performed simultaneously. In addition, any bit combination that does not yield more than the word size could be used. For example, parallel processing of 17-bit, 3-bit, 16-bit, 12-bit, 5-bit, and 11-bit arithmetic operations may be performed simultaneously.

The principles discussed above also refer to a carry-ahead adder, which is also known in the art as a carry-look-ahead adder. For example, FIG. 10 shows an implementation of a carry-handle two's complement adder within the ALU 26 in accordance with another preferred embodiment of the present invention. A carry prefetch circuit 470 generates carries for the adder. A half adder 460 receives a single bit X & sub0; a first operand and a single bit Y & sub0; a second operand. A half adder 460 generates a sum bit 20. A full adder 461 receives a single bit X & sub1; of the first operand, a single bit Y & sub1; of the second operand and a carry bit C0. A full adder 461 generates a sum bit 21. A full adder 165 receives a single bit Xi-1 of the first operand, a single bit Yi-1 of the second operand, and a carry bit Ci-2. A full adder 465 generates a sum bit Zi-1. A full adder 466 receives a single bit Xi of the first operand, a single bit Y & sub1; of the second operand and a carry bit Ci-1. The full adder 466 generates a sum bit 21. A full adder 469 receives a single bit Xj-1 of the first operand, a single bit of the second operand, and a carry bit Cj-2. A full adder 469 generates a sum bit Zj-1.

In the embodiment of the adder shown in Fig. 10, "j" is the size of the data path and the bit length of full word operations. Also, "i" is equal to "j" divided by 2. For example, "j" equals 32 and "i" equals 16. Alternatively, if j equals 32, i may equal an integer less than 32.

When performing operations using "j" bit full word operands, a release bit 452 is equal to a logical one and allows all carries to propagate. When two parallel operations are performed using "i" bit sub-word operands shared between bits i and i + 1, a release bit 452 is equal to a logical zero and prevents carryover across the boundary the partition spreads. Instead, the value on line 451 is used as the value that is passed to full adder 466. When an "add" is performed, a logic zero is placed on the input line 451. When a "subtracting" is performed, a logical one is placed on the input line 451.

The operation of carry-handle adders is known in the art. For example, assume that A [i] is one bit of an input, that B [i] is one bit of the other input, and S [i] is one bit of the sum of the adder. Then the sum of one bit of the adder is given by equation 1 below:

Equation 1

S [i] = A [i] XOR B [i] XOR C [i-1]

In Equation 1, C [i-1] is the carry from the previous bits of the carry-ahead adder. The carry-ahead adder works fast in generating these carry bits.

Let G [i] be a signal indicating that a carry is to be generated from this bit, and P [i] is a signal that a carry can pass from the previous bits to the output of that bit. These are determined according to Equation 2 below:

Equation 2

G [i] = A [i] AND B [i];

P [i] = A [i] OR B [i].

Therefore, for four bits within a carry-ahead adder, the carry bits may be generated as given in Equation 3 below:

Equation 3

C [i] = G [i] + P [i] * (G [i-1] + P [i-1] * (G [i-2] + P [i-2] * (G [i- 3] + P [i-3] * C [i-4])))

C [i-1] = G [i-1] + P [i-1] * (G [i-2] + P [i-2] * (G [i-3] + P (i-3) * C [i-4]))

C [i-2] = G [i-2] + P [i-2] * (G [i-3] + P [i-3] * C [i-4]) C [i-3] = G [i-3] + p [i-3] * C [i-4]

In the above Equation 3, "*" is equal to a logical AND operation, and "+" is equal to a logical OR operation.

When a preferred embodiment of the present invention is implemented, carry-over at a particular bit is halted when generating G [i] and spreading P [i] become forcibly untrue. For example, in Equation 3 above, if G [i-3] and P [i-3] are untrue, C [i-3] will be untrue, and C [i-4] can never match the value of C [i-3]. 2), C [i-1] and C [i]. Similarly, if G [i-2] and P [i-2] are untrue, C [i-2] will be untrue, and G [i-3] and P [i-3] and C [i-4] may never affect the value of C [i-1] and C [i].

If M [i] is conventionally a mask bit that interrupts the carry chain between bit [i] and bit [i + 1] when M [i] is 1, then a new equation 4 can be generated as follows:

Equation 4

Gm [i] =! M [i] * (A [i] * B [i])

Pm [i] =! M [i] * (A [i] * B [i])

If M [i] is now 1, no carry will be allowed to be generated from bit [i] or be able to pass through bit [i].

For a subtraction by generating the one's complement from one of the operands and adding it to the other operand with a carry in (two's complement arithmetic), a carry must be compulsorily generated in one bit when M [i] is 1.

Let F be a signal which, if true, forcibly causes a carry to be generated in one bit when M [i] is 1. The equation for Gs [i] and Ps [i] becomes as set forth in Equation 5 below:

Equation 5

Gs [i] = (M [i] * F) + (! M [i] * (A (i) * B [i])) - (M [i] * F) + (! M [i] * G [i])

Ps [i] = Pm [i]

Now, if M [i] is 1, the value of Gs [i] is determined by F. If M [i] is 0, the value of Gs [i] is determined by A [i] and B [i], as was previously the case. Spreading does not have to be forced by the signal F.

The equation for carry out is given by the following equation 6:

Equation 6

C [i] = Gs [i] + Ps [i] * C [i-1]

As will be understood by those skilled in the art, the principles of the present invention are not limited to arithmetic operations within computer system ALUs. For example, partitioning, as shown for the ALU, may also be extended to other entities within the computer system that are working with data. For example, FIG. 6 illustrates the present invention implemented in a pre-shifter 27. The same embodiment of the present invention may also be used to implement the pusher 29. The partitioning of the advancer 27 and the shifter 29 allows, for example, the implementation of parallel shift and add operations and parallel shift operations.

The advancing means 27 comprises a shift register one-bit slot 160, a shift register one-bit slot 161, a shift register one-bit slot 165, a shift register one-bit slot 166, and a shift register one-bit Slot 169.

When data is shifted to the left, a data at an input 171, typically a logical value of zero, is used as input to the shift register one-bit slot 160. When data is shifted to the right, a selector 175 either selects a data at input 181 (a logic value of zero or a logic value of one) in response to a control input 182, or selects the value currently being input from the shift register. Bit slot 169 to then input the value into the shift register one-bit slot 169.

Whenever the shifter is to be partitioned, additional selectors are added to the shifter. For example, FIG. 6 shows that the shifter is partitioned between the shift register one-bit slot 165 and the shift register one-bit slot 166. Here, a selector 174 and a selector 173 have been added. For partitioned operand shift operations, when data is shifted to the left, the selector 173, in response to a control input 185, selects a data at the input 172, typically a logical value of zero, so that the data is input to the shift register one-bit slot 166 is used. For shift operations on full-word operands, the selector 173, when shifting data to the left, selects the output from the shift register one-bit slot 165 as input to the shift register one-bit slot 166.

For partitioned operand shift operations, when data is shifted to the right, in response to a control input 184, selector 174 selects either a data input 182 (a logical value of zero or a logical value of one) or the value currently in the shift register One-bit slot 166 is stored as input to the shift register one-bit slot 165. For full word operand shift operations, the selector 174, when shifting data to the right, selects the output from the shift register one-bit slot 166 to be used as an input to the shift register one-bit slot 165 ,

Fig. 6 shows a shifter with only two partitions. From the foregoing discussion of partitions in an ALU, it can be seen that the shifter can be partitioned in a variety of ways. For example, a 64-bit shifter may be partitioned into equal size partitions of 2, 4, 8, 16, 32, or 64-bit size. In addition, it is not a requirement of the present invention that the partitions always act on an equal number of bits.

Although the above embodiment describes the advancing device 27 and the shifter 29 implemented as a shift register comprising a series of one-bit slots, alternative preferred embodiments are advancing devices and shifters implemented with multiplexers. Typically, a pre-shifter 27 is implemented by a layer of multiplexers since it can usually shift by at most a small number of bits, for example 0, 1, 2, 3 or 4 bits. The shifter 29 is typically implemented by three levels of multiplexers, each level of multiplexers being a four-to-one multiplexer. For example, in a 64-bit shifter 29, the first level of multiplexers will shift either 0, 16, 32 or 48 bits. The second level of multiplexers can shift either 0, 4, 8, or 12 bits. The third level of multiplexers can shift by 0, 1, 2 or 3 bits. This results in a shift of any number of bits from 0 to 63. In such a shifter constructed of three stages of multiplexers, one-bit slots can still be identified. However, the blocking of shifts between any two bits must be done in one or more of the three multiplexer stages, as will be understood by those skilled in the art.

The principles of the present invention may also be extended to other elements in a computer system. For example, a multiplier in accordance with a preferred embodiment of the present invention may be implemented to enable subword parallel multiplications in addition to integer word multiplies.

For example, Fig. 7 shows a four-bit multiplier according to the prior art. The multiplier multiplies a first four-bit multiplicand X & sub3; X & sub2; X & sub1; X & sub0; (Base 2) with a second four-bit multiplicand Y & sub3; Y & sub2; Y & sub1; Y & sub0; (Base 2) to obtain an eight-bit result Z 7 Z 6 Z 5 Z 4 Z 3 Z 2 Z 1 Z 0. (Base 2). It will be understood by those skilled in the art that the logical AND gates 201, 202, 203, 204, 205, 206, 207, 208, 209, 210, 211, 212, 213, 214, 215 and 216 may be used to provide partial products for to generate the multiplication. A partial product summation circuit 220 sums the partial products generated by the logical AND gates 201 to 216 to produce the result.

The two multiplicands X & sub3; X & sub2; X & sub1; X & sub0; and Y & sub3; Y & sub2; Y & sub1; Y & sub0 ;, the partial products produced by the logical AND gates 201 to 216, and the result generated by the partial product summation circuit 220 may be placed in a table such that the operation of the multiplier is summarized. For example, such a table is shown as Table 1 below: TABLE 1

In the notation used in Table 1 above, the bit position of each bit of both multiplicands and the result are specifically identified. In addition, the bits of the multiplicand used to form each partial product are specifically set forth. As will be understood by those skilled in the art, the information shown in Table 1 above may be presented using an abbreviated or simplified notation, as set forth in Table 2 below. Table 2

In Table 2 above, each bit of the first multiplicand is represented by an "X", each bit of the second multiplicand is represented by a "Y", each bit of a partial product is represented by a "z", and each bit of the result is passed through a "Z" shown. Using the simpler notation of Table 2, an eight-bit multiplier can be described, as shown in Table 3 below: TABLE 3

The multiplier shown in Table 3 multiplies a first eight-bit multiplicand XXXXXXXX (gasis 2) by a second eight-bit multiplicand YYYYYYYY (base 2) 'to produce a 16-bit result ZZZZZZZZZZZZZZZZ (base 2). Similarly, using the simpler notation of Table 2 and Table 3 (but eliminating spaces between bit positions), a 16-bit multiplier may be described, as set forth in Table 4 below: Table 4

The multiplier shown in Table 4 multiplies a first 16-bit multiplicand XXXXXXXXXXXXXXXX (base 2) by a second 16-bit multiplicand YYYYYYYYYYYYYYYY (basis 2) 'to produce a 32-bit result ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ (base 2).

In accordance with preferred embodiments of the present invention, a standard multiplier may be modified to implement a multiplier that provides parallel multiplication of partial words in addition to a multiplication of whole words. For example, Fig. 8 shows a four-bit multiplier according to the preferred embodiment of the present invention. The logical AND gates 301, 302, 303, 304, 305, 306, 307, 308, 309, 310, 311, 312, 313, 314, 315, and 316 generate subproducts for multiplication. A partial product summation circuit 320 sums the partial products generated by the logical AND gates 310 to 316 to produce the result.

In the multiplier shown in FIG. 8, a partial product summation circuit 320 may be implemented exactly like the partial product summation circuit 220 of FIG. 7. The difference between the multiplier shown in FIG. 8 and the multiplier shown in FIG. 7 is the addition of a control line 321 connected to an additional input included in each of the logical AND gates 303, 304, 307, 308, 309 , 310, 313 and 314 is included.

As shown in Fig. 8, when the control line 321 is set to a logic one, the multiplier applies a whole word multiplication to a first four-bit multiplicand X 3 X 2 X 1 X 0. (Base 2) and a second four-bit multiplicand Y & sub3; Y & sub2; Y & sub1; Y & sub0; (Base 2) to obtain an eight-bit result Z 7 Z 6 Z 5 Z 4 Z 3 Z 2 Z 1 Z 0. (Base 2). The two multiplicands X & sub3; X & sub2; X & sub1; X & sub0; and Y & sub3; Y & sub2; Y & sub1; Y & sub0 ;, the partial products produced by the logical AND gates 301 to 316, and the result produced by the partial product summation circuit 320 may be in tabular form as shown in the following table 5: Table 5

A comparison of Table 5 and Table 1 above confirms that, when line 321 is set to a logical one, the operation of the multiplier shown in Figure 8 is identical to an operation of the multiplier shown in Figure 7. Therefore, similar to Table 2 above, the simplified notation can be used to describe the operation of the multiplier shown in FIG. 8, resulting in Table 6 below: Table 6

Fig. 9 shows the multiplier shown in Fig. 8, except that the control line is set to a logic zero. This inevitably results in half of the partial products being set to zero, allowing the multiplier to perform a parallel multiplication of partial (two-bit) words. That is, in a first multiplication, a two-bit multiplicand A & sub1; A & sub0; (Base 2) with a two-bit multiplicand C & sub1; C & sub0; (Base 2) is multiplied to obtain a four-bit result E 3 E 2 E 1 E 0. (Base 2). In a second multiplication, a two-bit multiplicand B & sub1; B & sub0; (Base 2) with a two-bit multiplicand D & sub1; D & sub0; (Base 2) is multiplied to obtain a four-bit result F & sub3; F & sub2; F & sub1; F & sub0; (Base 2). The partial products which are not used for the parallel multiplications are forcibly set to a logical zero. The parallel multiplication can be represented in tabular form, as has been done in Table 7 below: TABLE 7

Using the simplified notation first introduced in Table 2, the multiplier shown in Figure 9 can be represented as set forth in Table 8 below: TABLE 8

As shown by Table 7 and Table 8, parallel multiplication of partial words in a multiplier by forcibly setting selected partial products in the multiplier to zero is implemented. In general, a standard arbitrary size multiplier can be used to perform parallel multiplication by forcing unused subproducts to zero. The partial products are forcibly brought to a logical zero, for example using one or more control inputs and three logical AND input gates (or their equivalents).

For example, as discussed above, an eight-bit multiplier as described by Table 3 may be implemented. This multiplier can be used to perform parallel multiplication of subword multiplicandes by providing circuitry such as shown in Figs. 8 and 9 for forcing subproducts to zero according to the teachings of the present invention. No modification is required for the partial product summation circuitry. Thus, modifying the multiplier described by Table 3, in accordance with the teachings of the present invention, for example, allows performing two parallel multiplications using four-bit multiplicand, as implemented by Table 9 below: Table 9

As can be seen from Table 9 above, in a first parallel multiplication of subword multiplicand, a four-bit multiplicand AAAA (base 2) is multiplied by a four-bit multiplicand 0000 (base 2) to obtain an eight-bit multiplicand. Generate bit result EEEEEEEE (basis 2). In a second parallel multiplication of subword multiplicand, a four bit multiplicand BBBB (base 2) is multiplied by a four bit multiplicand DDDD (gasis 2) to produce an eight bit result FFFFFFFF (base 2). The multiplication of two whole-word (eight-bit) multiplicands is implemented by the multiplier by forcibly zeroing out all of the partial products.

Likewise, as discussed above, a 16-bit multiplier may be implemented, as shown by Table 4. This same multiplier can be used to perform parallel multiplications of sub-word multiplicands by providing circuitry as shown in Figs. 8 and 9 to forcibly nullify partial products, in accordance with the teachings of the present invention , No modification must be made to the partial product summation circuitry. Thus, for example, modifying the multiplier described by Table 4 according to the teachings of the present invention allows two parallel multiplications to be performed using eight-bit (subword) multiplicand, as set forth in Table 10 below: Table 10

From the above Table 10, it can be seen that in a first parallel multicast, an eight-bit multiplicand AAAAAAAA (base 2) is multiplied by an eight-bit multiplicand CCCCCCCC (base 2) to produce a 16-bit EEEEEEEEEEEEEEEE ( Base 2). In a second parallel multicast, an eight-bit multiplicand BBBBBBBB (base 2) is multiplied by an eight-bit multiplicand DDDDDDDD (base 2) to produce a 16-bit result FFFFFFFFFFFFFFFF (base 2). The multiplication of two fullword (16-bit) multiplicand is implemented by the multiplier by not forcing all of the subproducts to zero.

Although the above description shows a parallel multiplication of half-words, it will be apparent to those skilled in the art that both the number of parallel multiplies that are performed and the size of the subword can be varied by forcibly zeroing the corresponding subproducts ,

For example, the 16-bit multiplier implemented as described by Table 4 (and / or Table 10) may be used to perform three concurrent parallel multiplications by providing circuitry as shown in Figs 8 and 9 to force partial products to zero according to the teachings of the present invention. Thus, modifying the multiplier described by Table 4, in accordance with the teachings of the present invention, for example, enables performing parallel multiplication using eight-bit multiplicand and two parallel multiplications using four-bit multiplicand as described by US Pat Table 11 below is implemented: Table 11

From Table 11 above, it can be seen that in a first parallel multicast, an eight-bit multiplicand AAAAAAAA (base 2) is multiplied by an eight-bit multiplicand DDDDDDDD (base 2) to produce a 16-bit result GGGGGGGGGGGGGGGG (gasis 2) to produce. In a second parallel multicast, a four-bit multiplicand BBBB (base 2) is multiplied by a four-bit multiplier EEEE (base 2) to produce an eight-bit result HHHHHHHH (base 2). In a third parallel multicast, a four-bit multiplicand CCCC (base 2) is multiplied by a four-bit multiplicand FFFF (gasis 2) to produce an eight-bit result IIIIIIII (base 2). It will be apparent to those skilled in the art that for each partial product shown in Table 11, with a value of zero, it is necessary to have a three input logical AND gate or a logical equivalent thereof so as to force the partial product to zero can if parallel multiplication operations are performed. However, if a mixture of differently sized partitions is used, as in Table 11, certain implementations may require different control inputs to force different partial product terms to zero, as will be apparent to those skilled in the art.

From the above discussion, it can be seen that parallel multiplication of partial words can be fully implemented in a multiplier by selectively forcing partial products of a multiplier to zero. The size of the word, the number of concurrent parallel multiplications, and the size of the subwords may be varied freely according to the teachings of the present invention.

Fig. 11 shows an example of instructions that may be executed in accordance with the preferred embodiment of the present invention. For example, a command 500 includes a field 501, a subfield 502 of the field 501, a field 503, a field 504, and a field 505. The field 501 includes the operation code. For example, field 501 includes an add, a move-and-add, a subtract, a move-and-subtract, a move-to-left, a shift-to-right, a multiply, or any number from other operations. Subfield 502 of 501 indicates whether the operation is to be performed as parallel operations and, if so, what is the size of the operands. Field 503 indicates a first source register. Field 504 indicates a second source register. Field 505 indicates a destination register.

As is known in the art, command 500 represents one of a large number of possible ways a command can be organized. For example, instruction 510 shows another embodiment in which the parallel operation indicator is in a separate field. In particular, instruction 510 includes a field 511, a field 512, a field 513, a field 514, and a field 515. Field 511 represents the operation code. For example, field 511 sets an add, a move and add, a subtract, a move and subtract, a move to in, a shift to right, a multiply, or any number of others Field 512 indicates whether the operation should be performed as parallel operations and, if so, what is the size of the operands. Field 513 indicates a first source register. Field 514 indicates a second source register. Field 515 indicates a destination register.

As will be understood in the art, the present invention also works for other multipliers where partial products are generated. For example, the present invention may be used in a booth-coded multiplier. In a Booth coded multiplier, fewer rows of partial product terms are generated by taking into account more than one bit of the multiplier (y multiplicand) for each row of the partial product term. For example, refer to John Hennessy & David Patterson, Computer Architecture, A Ouantitative Aporoach. Morgan Kaufmann, 1990, Appendix, pages A-39 to A-49. As in the case of the above multiplier, the values ​​of particular sub-product terms generated by the Booth-coded multiplier are altered to account for parallel processing, as will be apparent to those skilled in the art.

More specifically, in a stall coded multiplier, the AND gates 301 to 316 shown in Figs. 8 and 9 are replaced by multiplexers. For example, using the method of the "overlapping triplets", a booth coded multiplier examines three bits of the multiplier (ie y multiplicand) each time, instead of one bit at a time, to generate a series of partial products that is + x, + 2x, -2x, -x, or zero instead of a series of partial products that is always + x or zero as in the multiplier shown in FIGS. 8 and 9. This can be implemented as a five-to-one multiplexer. The name "overlapping triplets" is due to the fact that this method looks for three bits of the multiplier (y-multiplicand) and retracts two bits of the multiplier (y-multiplicand) for each row. The overlap occurs when, for the next row, the least significant bit of the three multiplier bits (y multiplicand) used by this next row was the most significant bit of the three multiplier bits used by the previous row were.

To implement a parallel subword multiplication, the bits of the x multiplicand that do not correspond to the subword product whose subproduct rows are formed are set to zero. This can be implemented with multiplexers as in the unmodified Booth coded multiplier, thereby modifying the control signals for the multiplexers. The sign of the sub-product series can also be used as additional input to the multiplexers.