Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1999-01-12
2001-09-18
Mai, Tan V. (Department: 2121)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S709000, C708S710000, C340S146200
Reexamination Certificate
active
06292818
ABSTRACT:
TECHNICAL FIELD OF THE INVENTION
The present invention generally relates to a method and apparatus for performing a sum-and-compare operation and, more particularly, to a high-speed sum-and-compare circuit which mizes propagation delay and which can be implemented in a minimum amount of die area.
BACKGROUND OF THE INVENTION
Rapid detection and prediction of arithmetic overflow and underflow exceptions are crucial to the performance of advanced microprocessors. These operations typically require a comparison of a single operand, A, with a constant, K, such as by the comparison operation A>=K. These operations more frequently involve comparing the sum of two operands, A and B, with a constant, K, such as by the sum-and-compare operation A+B>=K. The speed of this sum-and-compare operation depends on the speed of the carry bit propagation through an n-bit addition, where n is the number of bits of each operand.
The traditional method for performing a sum-and-compare operation, A+B>=K, employs an adder followed by a subtractor.
FIG. 1
is a block diagram functionally illustrating the sum-and-compare circuit for performing this operation. The adder circuit
1
obtains the sum of the operands A and B and outputs the sum to a second adder circuit
2
. The adder circuit
2
functions as the subtractor and adds the twos complement, J, of the constant K to the sum output from the adder circuit
1
. The most significant carry output bit, Cout, is true if the condition A+B>=K is true.
The performance of the sum-and-compare circuit shown in
FIG. 1
is limited by the propagation or “rippling” of carry bits from the least significant bit of the result to the most significant bit of the result. Several adder architectures have been developed for accelerating carry propagation to reduce the propagation delay, such as carry-lookahead architectures, carry-skip architectures and carry-select architectures. These adder architectures are well known in the art and their characteristics are summarized in the following table in terms of propagation delay and area complexity.
Type
Delay
Area
Ripple
D(n)
A(n)
Carry
D(log n)
A(n log n)
Lookahead
Carry Skip
D(sqrt n)
A(n)
Carry Select
D(sqrt n)
A(n)
In the table shown above, the letter D represents the intrinc delay, the letter A represents the die area required for logic needed for one bit of the operation, and the letter n is the number of bits of the adder, commonly referred to as the adder width. As the table indicates, with all of these adder architectures, delay and die area increase as the number of bits of the adder increases. The fastest of these architectures, and the most costly in terms of die area, is the carry-lookahead adder architecture.
A traditional carry-lookahead circuit
5
is shown in FIG.
2
. The traditional carry-lookahead circuit
5
has the form of a binary tree comprised of “generate” and “propagate” signals and cells
7
, which operate on the generate and propagate signals. The term “binary tree” is used to describe this circuit due to the fact that the number of outputs of each cell
7
is equal to the number of inputs to the cell divided by two. For comparitor applications, it is sufficient to compute only the most significant “generate” output. It is unnecessary to provide additional circuity for low order sum outputs.
The P and G inputs, P
0
and G
0
through P
7
and G
7
, are the propagate and generate values, respectively, previously calculated from addends A and B in accordance with the following equations:
P=A OR B Equation (1)
G=AB Equation (2)
In the interest of brevity, the circuitry for performing these operations is not show. Each cell
7
in the carry-lookahead circuit
5
executes the operations given by the following equations:
G
out
=G
i
OR P
i
G
i−1
Equation (3)
P
out
=P
i
P
i−1
Equation (4)
Optimal performance in a CMOS implementation of a sum-and-compare circuit requires that the gate-level granularity of the cells be appropriate to the process technology being used to implement the sum-and-compare circuit. If the gates are too complex, then nonlinear delays associated with the series field effect transistors (FETs) comprising the gates will dominate the critical ting paths. Also, increased complexity of the gates increases die area. On the other hand, if the gates are too simple, then intrinsic inverter delays will dominate the critical timing paths. Therefore, in order to maximize performance of the sum-and-compare circuit without increasing the amount of die area needed to implement the circuit, all of these factors should be taken into consideration.
Accordingly, a need exists for a sum-and-compare circuit which implements logic gates with a gate-level granularity appropriate to the process used to design and fabricate the sum-and-compare circuit, and which balances series FET delays with intrinsic inverter delays so that the propagation delay of the sum-and-compare circuit is minimized.
SUMMARY OF THE INVENTION
The present invention provides a sum-and-compare circuit which minimizes propagation delay and which minimizes the amount of die area required to implement the sum-and-compare circuit. The sum-and-compare circuit comprises a propagate/generate block followed by a carry-lookahead tree structure. The propagate/generate logic block receives a first operand, A, a second operand, B, and a third operand, J. each of the operands is comprised of a plurality of bits. The first operand A corresponds to an addend, the second operand B corresponds to an augend, and the third operand J corresponds to the twos complement of the constant K. The propagate/generate logic block comprises logic configured to add the operand A to the operand B to obtain a first sum. The propagate/generate logic block comprises logic configured to add the first sum to the operand J to obtain a plurality of propagate signals and a plurality of generate signals, which are then output from the propagate/generate logic block to a carry-lookahead tree structure.
The carry-lookahead tree structure comprises logic configured to operate on the propagate and generate signals to produce an output, Gout. The output Gout can be analyzed to determine whether the equation A+B>=K is true. The output Gout corresponds to the most significant bit of the carry output. If the output Gout is true, then the equation A+B>=K is also true.
The carry-lookahead tree structure preferably is partitioned into dynamic logic gates of a gate-level granularity appropriate to the process by which the carry-lookahead tree structure is fabricated, which preferably is a deep sub-micron CMOS process. The sum-and-compare circuit is designed in such a way that the series FET delays are balanced with the intrinsic inverter delays so that the propagation delay of the sum-and-compare circuit is minimized while also minimizing the amount of die area needed to implement the sum-and-compare circuit.
The sum-and-compare circuit of the present invention is faster and requires less die area than typical sum-and-compare circuits, which normally utilize separate adders with binary carry-lookahead tree structures to perform the sum-and-compare operation. Also, the sum-and-compare circuit of the present invention is well suited to implementation in deep submicron processes, which are capable of producing logic gates with fine gate-level granularity. Preferably, the sum-and-compare circuit of the present invention is implemented using dynamic domino logic with minimal gate loading.
Other features and advantages of the present invention will become apparent from the following description, drawings and claims.
REFERENCES:
patent: 4163211 (1979-07-01), Miura
patent: 5144577 (1992-09-01), Linnenberg
patent: 5426743 (1995-06-01), Phillips et al.
patent: 5923579 (1999-07-01), Widigen et al.
Hewlett--Packard Company
Mai Tan V.
LandOfFree
Method and apparatus for performing a sum-and-compare operation 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 apparatus for performing a sum-and-compare operation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for performing a sum-and-compare operation will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2514722