Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1998-11-18
2001-08-07
Malzahn, David H. (Department: 2121)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06272514
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 interruption of carry propagation on partition boundaries.
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.
Disclosed herein is an adder that combines a selectable arithmetic operation (addition, subtraction) and selectable saturating modes (signed, unsigned) with selectable partitioning (8-bit, 1 16-bit, 32-bit). The adder also provides selectable add/subtract capability for a 64-bit partition, but does not support saturation for 64-bit partitioning. The adder 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. The invention claimed herein allows partitionable arithmetic by interrupting the carry propagation chain on partition boundaries.
SUMMARY OF THE INVENTION
The present invention provides an apparatus and method that perform partitionable carry-lookahead logic on two N-nary operands. The operands may be selectably partitioned into 8-bit, 16-bit, 32-bit, or 64-bit operands, with each partition containing one or more blocks of N-nary groupings of bits. For multiple partitions, carry propagation is interrupted on partition boundaries in the following manner. An intermediate sum and carry-lookahead indicator are generated for each N-nary grouping of the partitioned operand. (Such groupings for 1-of4 operands are referred to as “dits”). These dit-level carry-lookahead indicators are combined to provide a carry-lookahead indicator for an entire block of dits. The block-level carry-lookahead indicator will be forced to a “Halt” indication if the block is the most significant block of a partition.
In addition to selectable partition size, the adder described herein can selectably perform either addition or subtraction. The partitionable carry-lookahead logic claimed herein will support either addition or subtraction. Each selectable feature described herein may be implemented singly, or in combination with other selectable features.
REFERENCES:
patent: 3987291 (1976-10-01), Gooding et al.
patent: 5164914 (1992-11-01), Anderson
patent: 5299145 (1994-03-01), Yoshida
patent: 5327369 (1994-07-01), Ashkenazi
patent: 5448509 (1995-09-01), Lee et al.
patent: 5463573 (1995-10-01), Yoshida
patent: 5467298 (1995-11-01), Yoshida
patent: 5600583 (1997-02-01), Bosshart et al.
patent: 5943251 (1999-08-01), Jiang et al.
Blomgren James S.
Petro Anthony M.
Booth Matthew J.
Booth & Wright, L.L.P.
Intrinsity, Inc.
Malzahn David H.
LandOfFree
Method and apparatus for interruption of carry propagation... 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 interruption of carry propagation..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for interruption of carry propagation... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2519670