Processor with architecture for improved pipelining of arithmetic instructions by forwarding redundant intermediate data forms

A processor providing a redundant intermediate form of a result in fewer than the total number of clock cycles needed to calculate a final complete result. The redundant form is forwarded to subsequent instructions or operations capable of utilizing the redundant intermediate form to enhance the performance of the processor.

FIELD OF THE INVENTION 
The present invention relates generally to the field of computers and 
computer arithmetic; particularly to the architecture and design of 
arithmetic logic units, and to the control of pipelined computers. 
BACKGROUND OF THE INVENTION 
Pipelining is a well-understood implementation technique whereby multiple 
instructions are overlapped in execution to increase the processing speed 
of a throughput-oriented computer system. Pipelines within a computer 
resemble an assembly line in that each portion of the pipeline (commonly 
referred to as "pipestages") completes a portion of the instruction's 
execution. Instructions enter one end of the pipeline and exit the other 
end--with the time required for moving an instruction one pipestage down 
the assembly line being known as a machine cycle. 
Some modern computer systems employ what is known as "superpipelining". 
Superpipelined machines have higher clock rates and deeper pipelines and 
are characterized by pipelining of most functional units. Superpipelining 
refers to taking a function that is currently performed in, say, one 
pipestage, and spreading it over two or more pipestages. In general, the 
purpose of increasing the number of pipestages in a superpipelined machine 
is to produce a shorter clock cycle. 
Today, processors are commercially available which superpipeline memory 
operation units such as cache memories. Superpipelining of actual 
arithmetic units, however, has yet to be successfully achieved. While 
academicians have proposed designs for superpipelining arithmetic units, 
these proposals suffer from serious drawbacks. 
For example, many proposed superpipelined arithmetic units for computer 
systems suffer poor performance because the result of an arithmetic 
operation is often used immediately when it is ready or available. Very 
often there is a need to use the results of a computation soon afterwards, 
e.g., one instruction later. If it takes two machine cycles to perform a 
computation on a simple machine, a pipeline STALL cycle (also frequently 
referred to as a "pipeline bubble") must be inserted into the pipeline 
flow to allow a needed result to propagate through an arithmetic unit. The 
basic problem therefore is that while pipelining is a valuable concept in 
a purely throughput-oriented computer system--where the assumption is that 
computation results are not needed until much, much later--in arithmetic 
logic units the performance advantage of pipelining or superpipelining 
techniques is drastically reduced because many computations are latency 
sensitive. 
As will be seen, the present invention makes it possible to improve the 
performance of a pipelined or superpipelined machine by taking advantage 
of the redundant intermediate form of a result, even though the full 
result has not yet completed execution. The redundant form of a result 
refers to a numerical representation where the particular value being 
represented has more than one bit pattern encoding. Computer arithmetic 
and number systems are described generally in the book entitled "Computer 
Arithmetic Principles, Architecture and Design," by Kih Wang, John Wiley 
and Sons, 1979, pages 1-12. Redundant representations of numbers are also 
described generally in pages 97-127 of Mr. Wang's book. 
SUMMARY OF THE INVENTION 
A general purpose processor providing a redundant intermediate form of a 
result is disclosed. The processor comprises an arithmetic execution unit 
that performs simple operations like ADD, SUBtract, compare (CMP), in one 
or more clock cycles. The arithmetic execution unit of the processor 
produces redundant form intermediate results in fewer than the total 
number of clock cycles needed to calculate a final complete result. The 
redundant form is forwarded or bypassed by logic to subsequent 
instructions or operations capable of utilizing the available redundant 
intermediate form. By making the redundant intermediate form available 
before the final, complete result, subsequent operations or instructions 
may execute sooner, thereby enhancing the performance of the processor. 
Optionally, the invention further includes a mechanism to stall 
instructions in the pipeline that require non-redundant inputs.

DETAILED DESCRIPTION 
A general purpose processor containing an arithmetic execution unit that 
utilizes the intermediate redundant form of results is described. In the 
following description, numerous specific details are set forth, such as 
particular architectures, circuits, computations, etc., in order to 
provide a thorough understanding of the present invention. It should be 
understood, however, that these specific details need not be used to 
practice the invention. In other instances, well-known structures, 
circuits, architectures, etc., have not been shown in detail in order to 
avoid unnecessarily obscuring the present invention. 
A redundant form of a number refers to any one of the many possible 
representations of a number; wherein a particular numerical value may be 
represented by more than one bit pattern encoding. For example, the 
"CARRY/SAVE" form is a commonly used form of redundant representation in 
the field of computer arithmetic. 
Table 1 below provides an example of several numerical values and their 
representations in CARRY/SAVE form. 
TABLE 1 
______________________________________ 
Carry Bit Value 
______________________________________ 
0 0 0 
0 1 1 
1 0 1 
1 1 2 
______________________________________ 
As appreciated by practitioners in the art, the CARRY/SAVE form is a 
convenient redundant form representation in which the numerical 
representation is divided into N-bit chunks, and the "carry" across the 
N-bit boundary is saved. Practitioners in the art will further appreciate 
that there are several other redundant forms for representing numerical 
values. The present invention works equally well with all types of 
redundant numerical representations. 
The invention takes advantage of redundant forms by utilizing the redundant 
form of numerical representation to make calculations run faster. 
Redundant form representations are utilized in accordance with the present 
invention to provide a pipelined or superpipelined general purpose 
arithmetic unit. The invention improves the overall performance of a 
processor by forwarding the redundant arithmetic form of a number prior to 
the final completion of the result. 
Referring now to FIG. 1, there is shown a pipeline 10 of a general purpose 
microprocessor. For example, the first stage of the pipeline is the 
instruction fetch (IF) process which involves fetching an instruction from 
memory, decoding the instruction and placing it into a queue or buffer. 
The next stage in the pipeline is the operand fetch (OF) process. Here, 
operands required for the computation are retrieved from a memory location 
such as a cache or main memory. 
The first execution unit pipestage is illustrated in FIG. 1 by the block 
EU.sub.0. For simple logic operations such as AND or OR operations, the 
first execution unit pipestage produces the complete result. For other 
arithmetic operations, such as ADD, SUBTRACT, MULTIPLY, etc., the first 
execution unit pipestage makes available the redundant intermediate form 
of the result. In the second execution unit pipestage, EU.sub.1, the 
non-redundant form of the arithmetic calculation is completed. Finally, in 
the writeback (WB) stage, the result is written back to memory. 
Now consider the example instruction sequence shown below in conjunction 
with the illustration of FIG. 2. 
INSTR 1: EBX.rarw.ADD (EBX, 1) 
INSTR 2: ECX.rarw.2 
INSTR 3: CMP (EBX, EDX) 
FIG. 2 illustrates the pipelining for the above instruction sequence 
consisting of an ADD operation, followed by a STORE and a COME logical 
operation. The first pipestage of FIG. 2 shows the occurrence of the 
instruction fetch process for instructions INSTR.sub.1 and INSTR.sub.2. In 
the next pipestage, operands are fetched, followed by the first execution 
unit pipestage for both instructions. In the third pipestage, concurrent 
with the operand fetch process for INSTR.sub.1 and INSTR.sub.2, the 
instruction fetch process is carried out for instruction INSTR.sub.3. That 
is, in the third pipestage, operands are fetched for the third instruction 
while INSTR.sub.1 and INSTR.sub.2 are executing in the first instruction 
unit pipestage, EU.sub.0, and so on. 
Arrow 12 in FIG. 2 indicates the forwarding of the redundant form of the 
calculated result. For example, since INSTR.sub.3 utilizes the results of 
INSTR.sub.1, the redundant form calculation must be completed before the 
fourth pipestage in the example of FIG. 2. 
Certain operations, of course, require, or are simpler to implement, with a 
non-redundant input. An example of this category of operations are logical 
operations such as AND/OR, comparisons against zero, etc. By way of 
illustration, consider the example instruction sequence given below. 
INSTR 1: EAX.rarw.ADD (EBX, 1) 
INSTR 2: ECX.rarw.2 
INSTR 3: CMP (EBX, EDX) 
INSTR 4: ESI.rarw.OR (EAX, EBP) 
The above listing is the same as the earlier example, except that a fourth 
instruction, INSTR.sub.4 has been added. The execution of this sequence in 
a pipelined machine is illustrated by FIG. 3. In FIG. 3, the forwarding or 
bypassing of the redundant form of the intermediate calculation results 
from INSTR.sub.1 is illustrated by arrow 14. The execution results from 
the EU.sub.0 cycle calculated in INSTR.sub.1 (pipeline cycle 3) are 
forwarded to pipestage 4, where the EU.sub.0 pipestage is executed as part 
of INSTR.sub.3. 
Bypass of the non-redundant form is illustrated in FIG. 3 by arrow 15. In 
this case, because the non-redundant form of the result is required for 
the first execution stage (EU.sub.0) of INSTR.sub.4, a STALL must be 
inserted in the fourth pipestage for INSTR.sub.4 in order to wait for the 
execution results of INSTR.sub.1 to arrive. 
It is important to recognize that while many modern processors pipeline 
units such as a floating point units (because of their throughput-oriented 
nature), integer computations are rarely pipelined. The reason for this is 
because many integer computations are latency sensitive. 
In accordance with the present invention, certain computations (such as the 
addition of large numbers; e.g. 64-bits) are split into two different 
cycles. The operations are then pipelined. While the true final result is 
only available after completion of the second execution clock cycle, an 
intermediate result can be used as an input immediately upon completion of 
the first execution cycle. This means that a redundant form of the result 
can be used for many next instructions in the program sequence. 
In the examples of FIGS. 2 and 3, the redundant intermediate form is 
available after the first execution cycle for the ADD instruction 
(INSTR.sub.1). Even though the ADD operation will not provide a final 
result until after the second execution cycle (i.e., EU.sub.1), the 
redundant intermediate form is available for use by instruction 
INSTR.sub.3 in the program flow. 
One arithmetic operation where the use of the redundant intermediate form 
is particularly useful is CARRY/SAVE addition. When the two numbers are 
added together, the propagate CARRY-bit is typically generated. In prior 
art circuits, this CARRY-bit must be propagated throughout all of the bit 
positions before a final result is achieved. The fastest that most 
CARRY/SAVE circuits can run is logarithmic with the number of bit 
positions. This means that for the very large numbers (e.g. 64-bits) a 
considerable time may pass before a final result is available. 
An example of this situation is the addition of the two numbers 0001 and 
1111. For this addition, a CARRY-bit must be propagated across all bit 
positions of the result. Instead of propagating a CARRY-bit in the 
traditional manner, the present invention recognizes that all numerical 
representations are essential polynomials where each digit represents a 
coefficient multiplied by some number. This means that the above example 
can be represented as shown below. 
##STR1## 
Here, the true value of 16 is represented as: 
EQU (2.times.2.sup.0)+(1.times.2.sup.1)+(1.times.2.sup.2)+(1.times.2.sup.3)=16 
In this redundant form, the CARRY is represented by the binary pattern 10. 
There is no need to propagate the CARRY-bit all the way through to arrive 
at this intermediate result. The present invention recognizes the 
usefulness of calculating intermediate results in redundant form to 
increase the computational speed of a processor. Whereas most systems only 
utilize non-redundant forms (e.g. binary representations) the present 
invention performs redundant operations to enhance computer performance. 
It is appreciated that the CARRY/SAVE form is only one of many possible 
non-redundant forms. The same result can be achieved if bits are grouped 
along certain bit positions. For example, grouping bits two-by-two would 
produce the result shown below for the previous example. 
##STR2## 
In other words, the CARRY can be propagated along one, two, four, . . . , 
N-bit positions; as many bit positions as is convenient to do in a given 
cycle of time. Typically, if two 64-bit numbers are to be added, one 
possible solution might be to propagate the CARRY across the 32-bit 
boundary in a first cycle, followed by the remaining 32-bits in a second 
execution cycle. 
Thus, the concept of the present invention is to divide up the CARRY in a 
convenient place in order to improve the processing speed of the 
arithmetic unit. Returning back to the examples of FIG. 3, since 
INSTR.sub.3 depends on INSTR.sub.1, in a traditional arithmetic logic unit 
the second execution stage EU.sub.1 of INSTR.sub.3 would have to execute 
one pipeline stage later than shown. But because the present invention 
allows the use of redundant intermediate forms, INSTR.sub.3 can execute on 
the very next pipestage following the calculation of the intermediate 
redundant form. This is shown occurring by arrow 14 in FIG. 3. 
FIG. 3 also illustrates that there are a certain number of situations where 
an operation cannot tolerate a non-redundant input. For example, this 
situation is illustrated by INSTR.sub.4 depending on the result of 
INSTR.sub.1. Because INSTR.sub.4 is a logical operation (i.e., OR) which 
tests for equality, a STALL must be introduced into the fourth pipestage. 
FIG. 4 lists the various programming situations where forwarding can be 
performed using the redundant and non-redundant bypass mechanisms of the 
present invention for a particular embodiment (e.g., a x86 instruction set 
architecture). In FIG. 4, bypassing occurs from the operation shown on the 
left to the operation shown on the right. Note that in FIG. 4, the number 
"1" is used to denote a situation where the fast forwarding path can be 
used, typically involving redundant forwarding of intermediate results. 
The number "2" is used to denote a situation in which the slow 
(non-redundant) path must be used. An "X" indicates a situation that does 
not occur in the example microarchitecture described herein. The symbol 
"*" denotes uninteresting situations that occur with multiplies and 
divides. These situations are uninteresting because multiplies and divides 
have such long latencies that saving one clock cycle is insignificant. 
Nevertheless, the associated latencies are indicated parenthetically in 
FIG. 4 for most of these "*" situations. 
By way of example, in FIG. 4 an ADD can be forwarded to another ADD with no 
penalty. But an ADD followed by a logical operation requires that the 
non-redundant path must be used. The reason for this is that you need the 
values of every bit position to perform a logical operation such as OR, 
AND, XOR, etc. Note, however, that a comparison of two arbitrary non-zero 
values occurs less often than a comparison to zero. As shown by FIG. 4, 
comparisons to zero allow for redundant forwarding of intermediate results 
to improve performance speed. 
It should be understood that the information provided in FIG. 4 is 
particular to one embodiment, which is to x86-type compatible computer 
architecture. Thus, it is to be understood that other computer 
architectures might utilize the present invention in a different manner. 
Referring now to FIG. 5, there is shown one implementation of the present 
invention including instruction fetch and decode units 41 and 42, 
respectively, which decode new instructions to be executed. Instruction 
decode unit 42 provides source register numbers to a register file 40, 
which, in turn, provides source register values to the stage 0 arithmetic 
execution unit (AEU) 44. By way of example, AEU 44 may comprise a carry 
save adder (CSA), which is known to perform one type of redundant 
operation. 
The resulting intermediate redundant form output by AEU 44 is coupled to 
AEU 45 (stage 1), and also to one input of MUX 48. In the embodiment shown 
in FIG. 5, stage 1 arithmetic execution unit 45 is implemented by a carry 
propagate adder (CPA). AEU 45 outputs the non-redundant form of the 
result, which is then coupled back to one input of MUX 48. The number and 
values generated by the calculation are also stored in a result register 
in file 40, were they can be used for future arithmetic operations. 
Pipeline control logic 50 controls the operation of units 41, 42, 44, 45 
and MUX 48. In particular, control logic 50 selects either the redundant 
or non-redundant form to be used in the stage 0 execution of AEU 44. This 
allows the use of an intermediate redundant form for the next instruction. 
FIG. 6 illustrates, by way of example, one implementation of pipeline 
control logic 50. Pipeline control logic 50 includes opcode comparison 
logic 52 which compares the opcodes of both the old and new instructions 
in the programming sequence. Comparison logic 52 implements the forwarding 
path information provided in FIG. 4 based on these opcodes. For example, 
if two consecutive ADD operations occurred in the program flow, then 
opcode comparison logic 52 would select the FAST path by driving line 53 
logically high and by driving line 54 (i.e., the SLOW path) logically low. 
The AND logic network comprising gates 61-64 sets the appropriate source 
bypass path (i.e., redundant or STALL), depending upon the equivalence of 
the source and destination register numbers of the new and old 
instructions, respectively. It is appreciated that ordinary pipeline 
latches may be utilized to temporarily store the redundant intermediate 
form part-way through the computation cycle. 
The result of the structure of FIG. 6 is that an existing adder mechanism 
can be modified by splitting the ADD at a convenient point and 
incorporating pipeline latches to hold redundant intermediate results. 
Splitting the ADD and latching the redundant form of the computation in 
the pipeline allows implementation an arithmetic unit that dramatically 
improves processor performance by forwarding of redundant intermediate 
forms. 
FIG. 7 is an embodiment of an adder architecture which forwards redundant 
intermediate forms. Basically, the architecture of FIG. 7 is a unit that 
adds each of two bits and is four components deep. When a portion of bits 
of two numbers are added there is typically a need to know the value of 
the CARRY bit from the lower grouping of bits. A CARRY/SAVE adder produces 
two sums: SUM.sub.1 (the sum of the CARRY=0) and SUM.sub.0 (the sum of the 
CARRY=0). In the embodiment of FIG. 7, both numbers can be added quickly, 
but the CARRY input will be available late. This means that the CARRY 
input of the previous cell can be used as a multiplexer select input 
between the SUM.sub.0 and SUM.sub.1 elements. A true sum of all of the 
numbers is generated several machine cycles later. The individual adders 
of FIG. 7 are represented by adders 26-29 while the multiplexers are shown 
as MUXs 33-35. The location of the pipestage latches is represented in 
FIG. 7 by dashed line 25. The ADD operation of adders 26-28 consumes a 
time t.sub.A =4, followed by three multiplexer delays t.sub.M =1. 
It is important to understand that pipestage latches 25 may be placed 
anywhere along the data propagation path. That is, latching could be 
performed further down the propagation path depending upon how many bits 
are to be forwarded in a redundant form. The basic idea, however, remains 
the same: to be able to forward a redundant form of an arithmetic result 
from one arithmetic operation to a subsequent operation (e.g., ADD to ADD, 
ADD to Memory Reference, ADD, SUBTRACT, NEGATE to another instruction, 
etc.). 
The crux of the invention, therefore, is to provide a redundant form of the 
arithmetic operation as an input to a subsequent operation--where the 
redundant form is forwarded part-way through the execution cycle. 
Depending upon the number of bits that are to be forwarded, the clock 
period can be divided into 2, 3, 4, or N divisions (where N is a positive 
integer greater than one). The salient feature is that the present 
invention allows the forwarding of the redundant intermediate form of a 
result in cases that are dynamically most important, e.g., ADDs to Memory 
References.