Equality comparator using propagates and generates

• US 20080021943A1
• Filed: 07/20/2006
• Published: 01/24/2008
• Est. Priority Date: 07/20/2006
• Status: Abandoned Application

• Current Assignee: GlobalFoundries, Inc.
• Original Assignee: Advanced Micro Devices, Inc.
• Inventors: Chiu, Kok-Hoong
• Application Number:
  US11/490,338
• Publication Number:
  US 20080021943A1
• Time in Patent Office: Days
• US Class Current: 708/212
• CPC Class Codes: G06F 7/026 Magnitude comparison, i.e. determining the relative order of operands based on their numerical value, e.g. window comparator

Abstract

A carry lookahead adder is employed to determine an equality relationship and one or more inequality relationships between two operands. The carry lookahead adder includes a hierarchy of carry lookahead stages, each carry lookahead stage using either corresponding bits of the two operands or the carry generate values and carry propagate values from the prior stage to generate carry generate values and carry propagate values for use at the next stage. Equality logic receives a subset of the carry generate values and carry propagate values and, based on this subset of values, provides an equality relationship indicator that indicates the equality relationship between the two operands, or portions thereof. Further, inequality logic also receives a subset of the carry generate values and carry propagate values, and based on this subset of values, provides an inequality relationship indicator that indicates an inequality relationship between the two operands, or portions thereof.

Claims

1. A method comprising:

determining a first carry propagate value and a second carry generate value based on a first carry lookahead operation for a first operand and a second operand;

determining a second carry propagate value and a second carry generate value based on a second carry lookahead operation for the first operand and the second operand;

determining an equality relationship between the first operand and the second operand based on at least two of the first carry propagate value, the second carry propagate value, the first carry generate value and the second carry generate value; and

determining a first inequality relationship between the first operand and the second operand based on at least two of the first carry propagate value, the second carry propagate value, the first carry generate value and the second carry generate value.

2. The method of claim 1, further comprising:

determining a second inequality relationship between the first operand and the second operand.

3. The method of claim 1, further comprising:

determining a sum of the first operand and the second operand based on the first carry propagate value, the second carry propagate value, the first carry generate value and the second carry generate value.

4. The method of claim 3, wherein determining the equality relationship, determining the first inequality relationship, and determining the sum occur substantially in parallel.

5. The method of claim 1, wherein determining the equality relationship and determining the first inequality relationship occur substantially in parallel.

6. The method of claim 1, wherein determining the first carry propagate value and the first carry generate value occurs substantially in parallel with determining the second carry propagate value and the second carry generate value.

7. The method of claim 1, further comprising:

determining a third carry propagate value and a third carry generate value based on a third carry lookahead operation for the first carry propagate value, the second carry propagate value, the first carry generate value and the second carry generate value;

wherein determining the equality relationship between the first operand and the second operand comprises determining the equality relationship based on at least one of the second propagate value and the second carry generate value; and

wherein determining the inequality relationship between the first operand and the second operand comprises determining the inequality relationship based on at least one of the second propagate value and the second carry generate value.

8. A device comprising:

a carry lookahead adder comprising a first input to receive a first operand, a second input to receive a second operand, a plurality of carry lookahead stages, a first plurality of outputs and a second plurality of outputs, each of the first plurality of outputs to provide a corresponding carry propagate value of a corresponding carry lookahead stage of the plurality of hierarchical carry lookahead stages and each of the second plurality of outputs to provide a corresponding carry generate value of a corresponding carry lookahead stage of the plurality of carry lookahead stages; and

logic having a first plurality of inputs, each coupled to a corresponding one of the first plurality of outputs, a second plurality of inputs, each coupled to a corresponding one of the second plurality of outputs, and an output to provide an equality relationship indicator based on at least a first subset of the carry propagate values and at least a first subset of the carry generate values of the carry lookahead adder.

9. The device of claim 8, wherein each carry lookahead stage of a subset of the plurality of carry lookahead stages generates a corresponding plurality of carry propagate values and a corresponding plurality of carry generate values based on a carry propagate value and a carry generate value generated at a prior carry lookahead stage of the plurality of carry lookahead stages.

10. The device of claim 9, wherein a first carry lookahead stage of the plurality of carry lookahead stages generates a plurality of carry propagate values and a plurality of carry generate values based on bit values of the first operand and the second operand.

11. The device of claim 8, wherein the logic is to determine, for each carry lookahead stage of the plurality of carry lookahead stages, whether each carry propagate value at the carry lookahead stage has a first value and each carry generate value at the carry lookahead stage has a second value.

12. The device of claim 11, wherein:

the logic provides a third value for the equality relationship indicator in response to determining that each carry propagate value at each carry lookahead stage of the plurality of carry lookahead stages has the first value and determining that each carry generate value at each carry lookahead stage of the plurality of carry lookahead stages has the second value; and

wherein the third value for the equality relationship indicator indicates that the first operand is equal to the second operand.

13. The device of claim 12, wherein:

the logic provides a fourth value for the equality relationship indicator in response to determining that any carry propagate value at any carry lookahead stage of the plurality of carry lookahead stages has the second value or determining that any carry generate value at any carry lookahead stage of the plurality of carry lookahead stages has the second value; and

wherein the fourth value for the equality relationship indicator indicates that the first operand is not equal to the second operand.

14. The device of claim 8, wherein the logic further comprises a second output to provide a first inequality relationship indicator based on at least a second subset of the carry propagate values and at least a second subset of the carry propagate values of the carry lookahead adder.

15. The device of claim 14, wherein the logic further comprises a third output to provide a second inequality relationship indicator based on the equality relationship indicator and the first inequality relationship indicator.

16. A processing device comprising:

logic to determine a first carry propagate value and a second carry generate value based on a first carry lookahead operation for a first operand and a second operand;

logic to determine a second carry propagate value and a second carry generate value based on a second carry lookahead operation for the first operand and the second operand;

logic to determine an equality relationship between the first operand and the second operand based on at least two of the first carry propagate value, the second carry propagate value, the first carry generate value and the second carry generate value; and

logic to determine a first inequality relationship between the first operand and the second operand based on at least two of the first carry propagate value, the second carry propagate value, the first carry generate value and the second carry generate value.

17. The processing device of claim 16, further comprising:

logic to determine a second inequality relationship between the first operand and the second operand.

18. The processing device of claim 16, further comprising:

logic to determine a sum of the first operand and the second operand based on the first carry propagate value, the second carry propagate value, the first carry generate value and the second carry generate value.

19. The processing device of claim 16, wherein the logic to determine the equality relationship and the logic to determine the first inequality relationship are configured to operate substantially in parallel.

20. The processing device of claim 16, further comprising:

logic to determine a third carry propagate value and a third carry generate value based on a third carry lookahead operation for the first carry propagate value, the second carry propagate value, the first carry generate value and the second carry generate value;

wherein the logic to determine the equality relationship between the first operand and the second operand comprises logic to determine the equality relationship based on at least one of the second propagate value and the second carry generate value; and

wherein the logic to determine the inequality relationship between the first operand and the second operand comprises logic to determine the inequality relationship based on at least one of the second propagate value and the second carry generate value.