Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2000-10-23
2004-09-07
Chaki, Kakali (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S200000
Reexamination Certificate
active
06789098
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a method, data processing system and computer program for comparing floating point numbers.
2. Description of the Prior Art
It is common for data processing systems to be required to perform various floating point computations on data. To ensure that a consistent approach was adopted in the way in which floating point computations are handled by various data processing systems, a standard was produced in 1985 called the “IEEE Standard for Binary Floating-Point Arithmetic”, ANSI/IEEE Standard 754-1985, the Institute of Electrical and Electronic Engineers, Inc., New York, 10017 (hereafter referred to as the IEEE754-1985 Standard).
Performing comparisons of floating point numbers in accordance with the IEEE754-1985 Standard is non-trivial as there are a number of exception conditions which need to be identified, in order that appropriate exception routines can be applied to deal with such exception conditions. One example of such an exception condition is where one or more of the floating point numbers being compared are NaNs (Not a Number). It is clear that, irrespective of whether the comparison is performed in hardware or software, the time taken to determine whether such exception conditions exist will impact on the efficiency of the comparison process. For example, assuming a software approach, a generic check that detects whether either of two floating point numbers are NaNs takes 6 cycles, as illustrated by the following instruction sequence:
MOV
tmp, #0 × FFE00000
CMP
tmp, dOP1h, LSL #1
CMPEQ
dOP1l, #0
; HI -> NaN found
CMPLS
tmp, dOP2h, LSL #1
; no NaN, check opnd2
CMPEQ
dOP2l, #0
BHI
NaN_lab
; NaN found -> exception
The MOV instruction stores the number 0×FFE00000 in the register tmp. The CMP instruction then compares the value of the first floating point number, shifted left by one position, with the number stored in the register tmp. In the embodiment to which the above instruction sequence relates, a floating point number is represented by a mantissa value, an exponent value, and a sign bit indicating whether the number is positive or negative, in double precision mode these three values comprising a total of 64 bits, with the top 32 bits including the sign bit, followed by the exponent, followed by the first part of the mantissa. Accordingly, the CMP instruction compares the top 32 bits of the first floating point number, shifted left by one to remove the sign bit, with the number stored in the register tmp, and thus it can be seen that this instruction compares the exponent of the first floating point number with the number stored in the register tmp.
A NaN shifted left by one will have a value greater than FFE00000 00000000. Hence, if the result of the first comparison is HI, i.e. the top 32 bits of the first floating point number shifted left by one was greater than FFE00000, this clearly indicates the presence of an NaN.
However, if the result of this first comparison was equal (i.e. the top 32 bits of the first floating point number shifted left by one was FFE00000), the instruction CMPEQ then compares the bottom 32 bits of the first floating point number with the number 0, since it is still possible that the first floating point number may be a NaN. Hence, if a HI signal is produced by either the first or second comparison, then this indicates that the first floating point number is a NaN.
If the result of the previous two comparisons were less than or equal, and hence an NaN was determined not to be present, the next two instructions then perform a similar comparison for the second floating point number, again a high signal indicating that a NaN has been found. The final instruction then branches to an exception routine called NaN_lab if a high signal has been produced.
It will be appreciated that the performance of such a check as part of each floating point compare operation introduces a significant overhead, and adversely affects the efficiency of the compare operation. It is an object of the present invention to alleviate this overhead.
SUMMARY OF THE INVENTION
Viewed from a first aspect, the present invention provides a method of comparing first and second floating point numbers to generate a result indicative of the comparison unless one or more exception conditions exist, comprising the steps of: (a) providing a hierarchy of tests arranged to identify from said first and second floating point numbers whether said one or more exception conditions exist, a first test in said hierarchy predicting whether said one or more exception conditions may exist, and each subsequent test in the hierarchy being arranged to determine with more accuracy than the previous test whether said one or more exception conditions exist, each test being arranged to generate a hit signal if that test predicts that said one or more exception conditions exist; (b) executing the first test in said hierarchy; (c) if the executed test does not generate a hit signal, branching to a compare function, and executing the compare function to generate the result indicative of the comparison of the first and second floating point numbers; (d) if the executed test generates a hit signal and is not a final test in the hierarchy, performing the steps of: (d)(i) branching to the next test in the hierarchy; (d) (ii) executing the test branched to at said step (d)(i); and (d)(iii) returning to said step (c); (e) if the executed test generates a hit signal and is the final test in the hierarchy, generating an exception signal indicating the presence of said one or more exception conditions.
In accordance with the present invention, a hierarchy of tests are provided to predict the presence of one or more exception conditions. The first test predicts whether the one or more exception conditions may exist, and preferably is a “catch all” test that identifies any situations where the one or more exception conditions may exist, including ones which ultimately may not give rise to an exception condition. If the test indicates that one or more exception conditions may exist, then a hit signal is generated and the method branches to a next test in the hierarchy, which is arranged to determine with more accuracy than the previous test whether said one or more exception conditions exist. Each time the hit signal is generated by a test, the process branches to the next, more accurate, test in the hierarchy, unless the test is the final test in the hierarchy, at which point an exception signal is generated to indicate the presence of said one or more exception conditions.
The benefit of this approach is that as soon as one of the tests does not produce a hit signal, i.e. the test has determined that the one or more exception conditions do not exist, the process can branch immediately to a compare function in order to generate a result indicative of the comparison of the first and second floating point numbers.
Generally speaking, the more accurate the test, the longer than test will take to perform, and accordingly the earlier tests in the hierarchy can be performed significantly quicker than a precise test which identifies definitely whether the one or more exception conditions exist. Accordingly, assuming that exception conditions occur relatively infrequently, it will be appreciated that the method of the present invention will enable most compare operations to branch relatively quickly to the compare function, without needing to perform more precise checks provided later in the hierarchy. Hence, such an approach significantly improves the efficiency of floating point comparisons over the known prior art software techniques.
In preferred embodiments, the hierarchy of tests includes a choice of first tests, each first test having subsequent tests dependent thereon, and the method further comprises the steps of, prior to said step (b): (i) determining whether either the first or second floating point number is negative; (ii) branching to a positive number first test if both the first an
Arm Limited
Chaki Kakali
Do Chat
LandOfFree
Method, data processing system and computer program for... 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, data processing system and computer program for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method, data processing system and computer program for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3242123