Sum interval detector

Details Sum interval detector Sum interval detector

1999-12-27

2002-10-22

Mai, Tan V. (Department: 2124)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

C708S700000, C708S710000, C340S146200

Reexamination Certificate

active

06470373

ABSTRACT:

CROSS-REFERENCE TO RELATED APPLICATIONS
Danish patent application PA 1998 01743 entitled ‘Sum-intervaldetektor’ filed Dec. 29, 1998.
STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT
Not Applicable
REFERENCE TO A MICROFICHE APPENDIX
Not Applicable
BACKGROUND OF THE INVENTION
The sum interval detector is a general arithmetic circuit that may be used to avoid conflicting memory accesses in superscalar processors. Scalar processors execute instructions in program order and the associated memory accesses will execute in the same order and no conflicts can exist between these accesses. In contrast hereto, superscalar processors may execute instructions out of order although the semantics of program order must be maintained which require many checks for dependencies both among register references and among memory references. In most cases, memory accesses may be reordered if they do not deal with the same data; but since an access is given not only by its effective address but also its size in bytes it becomes a bit more complex to detect whether two memory accesses overlap and thus may not be reordered. If all memory accesses are aligned, i.e. every effective address is a multiple of the data size, which in turn is a power of two (2
N
), then the comparison will be a simple identity comparison that excludes the lower N bits of the effective addresses. If no alignment restriction exists no reordering may take place if the absolute difference between the two effective addresses is less than the data size.
Since effective memory addresses normally are the sum of a base address and an offset the straightforward approach would be to add the base address and offset for each effective address and then, in case of alignment restrictions, compare the effective addresses excluding the lower N bits or, without restrictions on alignment, subtract the two sums from each other and check whether the absolute difference is less than the data size, i.e. the difference lies in the interval-size . . . size. In particular in the last case this is a slow process.
The special case of determining whether two effective addresses as defined above are identical corresponds to the degenerate interval 0 . . . 0, i.e. the single value 0. This case has been solved in expired U.S. Pat No. 5,144,577 entitled ‘Two-sum comparator’.
The present invention in part relies on a known method to detect whether a sum is equal to a constant described in ‘Comments on “Evaluation of A+B=K Conditions Without Carry Propagation”’ by Behrooz Parhami (IEEE Transactions on Computers, Vol. 43, No. 4, April 1994), where the goal is reduction of the negative effect of conditional jumps in pipelined processor architectures.
BRIEF SUMMARY OF THE INVENTION
The sum interval detector is a novel way of detecting whether the sum of two n-bit inputs and a carry input computed modulo 2
n
is within the interval −2
p
. . . 2
p
−1 without having to calculate the sum explicitly which takes both additional time and additional hardware. The word width n and the power p determining the interval may vary from implementation to implementation. The interval may be modified by only including negative values −2
p
. . . −1 or non-negative values 0 . . . 2
p
−1. Further the interval may be expanded or limited by including or excluding, respectively, specific values. In particular the interval may be limited by excluding the value −2
p
thereby producing the symmetric interval −2
p
+1 . . . 2
p
−1, or including the value 2
p
thereby producing the symmetric interval −2
p
. . . 2
p
.
Detection of whether a sum A+B+C
0
computed modulo 2
n
belongs to the interval −2
p
. . . 2
p
−1 may be split into detection of whether the sum belongs to the subinterval −2
p
. . . −1 or 0 . . . 2
p
−1. The first subinterval corresponds to the binary values 111 . . . 1XXX . . . X, while the second subinterval corresponds to the binary values 000 . . . 0XXX . . . X, where n is the word width and p is the number of don't cares (X).
The invention utilizes a known method to detect whether a sum is equal to a constant to detect whether the upper n−p bit of the sum is binary 000 . . . 0 or 111 . . . 1, i.e. 0 or −1, respectively, while the lower p bits of the sum are ignored corresponding to XXX . . . X. This requires that the carry C
p
be known, which occurs with a known p-bit carry look-ahead circuit CLA, which may calculate C
p
as follows:
C
p
=(
C
0
AND P
0
AND . . . P
p−1
)
OR
(
G
0
AND P
1
AND . . . P
p−1
)
OR . . .
(
G
p−2
AND P
p−1
)
OR G
p−1
,
where
G
i
=A
i
AND B
i
and
P
i
=A
i
OR B
i
.
The known method to detect whether a sum is equal to a constant may briefly be described as
A+B=K
A+B+K
complement
=2
n
−1
S+C=
2
n
−1
S
i
=C
i
complement
, for
i=
0 . . .
n−
1,
which corresponds to a reduction of A+B+K
complement
to S+C (sum and carry) using carry-save addition with a number of full-adders followed by a check of whether the sum bit and the carry bit (from the previous bit position) are different in all bit positions. The carry C
0
is 0 in the known method but is used as a carry input in the following.


REFERENCES:
patent: 5144577 (1992-09-01), Linnenberg
patent: 5923579 (1999-07-01), Widigen et al.
patent: 6292818 (2001-09-01), Winters
patent: 6341296 (2002-01-01), Menon
Parhami, B. “Comments on Evaluation of A+B=K Conditions without Carry Propagation”, IEEE Trans. on Computers, vol. 43, No. 4, Apr. 1994, p. 381.*
Cortadella et al, “Evaluation of A+B=K Conditions Without Carry Propagation,” IEEE Trans. on Computers, vol. 41, No. 11, Nov. 1992, pp. 1484-1488.

Affiliated with

Also associated with

Rating

Sum interval detector does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Sum interval detector, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sum interval detector will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2989965