Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1998-11-18
2001-10-09
Malzahn, David H. (Department: 2187)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S670000
Reexamination Certificate
active
06301597
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to digital computing, and more particularly to an apparatus and method for saturation in an N-NARY adder/subtractor.
2. Description of the Related Art
Where wide adders exist in a design, it is desirable for some computation workloads (such as graphics processing) to selectively partition the adders such that they may perform several independent operations in parallel on a set of operands. Also useful in these workloads is the independent feature of saturating arithmetic.
U.S. Pat. No. 5,448,509, issued to Lee et al., describes a system for handling positive and negative overflow and performing saturation. However, Lee '509 suffers several shortcomings that are overcome by the present invention. First, Lee '509 is not partitionable while the present invention is partitionable. Also, Lee '509 restricts itself to several rather unusual combinations of inputs and outputs: the addition of an unsigned operand to a signed operand to produce an unsigned saturable result, and the addition of two signed operands to produce a positive-only signed result. In the latter case, the Lee '509 invention deprives the result of half its possible range. This is because Lee '509 saturates underflow at zero, rather than the largest negative number, −2
(N−1)
. While Lee '509 saturates overflow at 2
(N−1)
−1, the usual value for signed overflow, the zero saturation for underflow deprives the result of half of its possible range. In contrast, the present invention provides a saturating capability that takes signed inputs to produce a full range signed output or takes unsigned inputs and produces an unsigned output. Finally, Lee '509 examines the final result of the arithmetic operation to determine overflow or underflow. In contrast, the present invention discloses a more efficient method of determining overflow and underflow through the use of carry-lookahead logic to detect overflow/underflow before the result is computed.
The present invention also discloses a more desirable approach than that described in U.S. Pat. No. 5,164,914, issued to Daryl E. Anderson. Anderson '914 describes an approach for a saturating adder in which the carry into the most significant result bit is used to detect overflow. Because Anderson '914 does not disclose a partitionable adder, and because Anderson '914 restricts itself to signed saturation, it has limited usefulness.
The invention described herein combine a selectable arithmetic operation (addition, subtraction) and selectable saturating modes (signed, unsigned) with selectable partitioning (8-bit, 16-bit, 32-bit). The present invention also provides selectable add/subtract capability for a 64-bit partition, but does not support saturation for 64-bit partitioning. The present invention is implemented in the dynamic N-NARY logic design style, to create a versatile high-performance adder/subtractor. The present invention overcomes the deficiencies of the prior art in that it combines signed and unsigned saturating arithmetic with partitionability, which allows the adder/subtractor to perform a larger number of narrow additions or a smaller number of wider additions.
SUMMARY OF THE INVENTION
The present invention provides an apparatus and method for performing saturating arithmetic on two unsigned operands using N-NARY logic. In an alternative embodiment, signed saturation may be selectably performed. In such case, saturation may be deselected, but if saturation is selected then it will be performed for either signed or unsigned addition or subtraction. The two operands may be selectably partitioned into 8-bit, 16-bit, 32-bit, or 64-bit operands. For multiple partitions, carry propagation is interrupted on partition boundaries so that partitions may be saturated independently.
For unsigned arithmetic, the arithmetic result of the operation on the two operands is forced to an overflow saturation constant if an overflow occurs and an underflow saturation constant if an underflow occurs. For signed arithmetic, the arithmetic result of the operation on the two operands is forced to the same overflow saturation constant discussed above for all but the most significant N-NARY grouping of bits within a partition. For the most significant N-NARY grouping of bits within a partition, the arithmetic result is forced to an overflow saturation constant that reflects the proper value of the sign bit. Similarly, signed underflow involves either the underflow saturation constant discussed above or a constant that reflects the proper value of the sign bit for the most significant N-NARY grouping within a partition.
The apparatus will perform saturation for either addition or subtraction operations, for either signed or unsigned operands that may be divided into one or more partitions. Each selectable feature described herein may be implemented singly, or in combination with other selectable features.
REFERENCES:
patent: 5164914 (1992-11-01), Anderson
patent: 5299145 (1994-03-01), Yoshida
patent: 5448509 (1995-09-01), Lee et al.
patent: 5463571 (1995-10-01), Kim et al.
patent: 5463572 (1995-10-01), Kim et al.
patent: 5463573 (1995-10-01), Yoshida
patent: 5467298 (1995-11-01), Yoshida
patent: 5847978 (1998-12-01), Ogura et al.
patent: 5887181 (1999-03-01), Volkonsky
Blomgren James S.
Petro Anthony M.
Booth Matthew J.
Booth & Wright, L.L.P.
Intrinsity, Inc.
Malzahn David H.
Wright Karen S.
LandOfFree
Method and apparatus for saturation in an N-NARY... 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 saturation in an N-NARY..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for saturation in an N-NARY... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2581812