Generation of mask-constrained floating-point addition and subtraction test cases, and method and system therefor Number:7,028,067 from the United States Patent and Trademark Office (PTO) owispatent A method and system for generating numerical test cases for testing binary floating-point arithmetic units for addition and subtraction operations, in order to verify the proper operation of the units according to a specified standard. The space for eligible test-cases is compatible with masks which stipulate the allowable forms of the operands and the result, including constant as well as variable digits in both the exponent and significand fields. The test-cases, which are generated randomly, cover the entire solution space without excluding any eligible solutions. All standard rounding modes are supported, and if a valid solution does not exist for a given set of masks, this fact is reported. The method is general and can be applied to any standard, such as the IEEE floating-point standard, in any precision. A system according to the present invention utilizes a set of sub-generators for biased exponents and significands, and also incorporates a fixed-point generator for performing calculations common to the other generators. The method relies on searching for solutions based on feasible carry sequences, and is also capable of generating test-cases for mask-constrained carry sequences.<H subtraction, constrained, Generation, of, m, 7028067.html, Patent, pto, 7028067

Title: Generation of mask-constrained floating-point addition and subtraction test cases, and method and system therefor

Abstract: A method and system for generating numerical test cases for testing binary floating-point arithmetic units for addition and subtraction operations, in order to verify the proper operation of the units according to a specified standard. The space for eligible test-cases is compatible with masks which stipulate the allowable forms of the operands and the result, including constant as well as variable digits in both the exponent and significand fields. The test-cases, which are generated randomly, cover the entire solution space without excluding any eligible solutions. All standard rounding modes are supported, and if a valid solution does not exist for a given set of masks, this fact is reported. The method is general and can be applied to any standard, such as the IEEE floating-point standard, in any precision. A system according to the present invention utilizes a set of sub-generators for biased exponents and significands, and also incorporates a fixed-point generator for performing calculations common to the other generators. The method relies on searching for solutions based on feasible carry sequences, and is also capable of generating test-cases for mask-constrained carry sequences.

Patent Number: 7,028,067 Issued on 04/11/2006 to Abraham, et al.

Inventors: Abraham; Ziv (Haifa, IL); Asaf; Sigal (Beit Shearim, IL); Koyfman; Anatoly (Kiryat Yam, IL); Zadok; Shay (Bat Yam, IL)
Assignee: International Business Machines Corporation (Armonk, NY)

Appl. No.: 078111

Filed: February 20, 2002

Current U.S. Class: 708/530 ; 714/738

Current International Class: G06F 11/263 (20060101)

Field of Search: 708/530 714/738

References Cited [Referenced By]

U.S. Patent Documents


3921142	November 1975	Bryant et al.
5488573	January 1996	Brown et al.
5572666	November 1996	Whitman
5600658	February 1997	Qureshi
5841960	November 1998	Ibusuki et al.
6438722	August 2002	Bailey et al.
6601204	July 2003	Tsuto

Other References

Lewin et al., "Constraints Satisfaction for Test Programs Generation", IBM Israel Science and Technology, Haifa Research Laboratory, 4 pages, dlewin@haifasc.3vnet.ibm.com. cited by other .
Aharon et al., "Test Program Generation for Functional Verification of PowerPC Processors in IBM", IBM Israel-Haifa Research Lab, 7 pages, yossi@haifasc3.vnet.ibm.com. cited by other .
Grinwald et al., "User Defined Coverage--A Tool Supported Methodology for Design Verification", IBM Research Lab in Haifa, pp. 158-163, grinwald@vnet.ibm.com. cited by other .
Lichtenstein et al., "Model Based Test Generation for Processor Verification" 12 Pages, yossi@haifasc3.vnet.ibm.com. cited by other .
Software Negligence and Testing Coverage, http://www.kaner.com, 16 pages. cited by other.

Primary Examiner: Malzahn; D. H.
Attorney, Agent or Firm: Browdy and Neimark, PLLC

Claims

What is claimed is:

1. A system for generating floating-point test-cases for verifying the operation of a floating-point arithmetic unit, the system comprising a processing unit which includes: (a) an exponent generator, for generating floating-point exponents; (b) a significand generator, for generating floating-point significands; and (c) a fixed-point generator coupled to said exponent generator and to said signficand generator; wherein said processing unit is configured to receive a specified arithmetic operation, a specified rounding mode, at least one input operand mask, and an output result mask; and wherein said processing unit is configured to output a set of floating-point numbers which includes at least one input operand compatible with said at least one input operand mask, and an output result compatible with said output result mask; and wherein said output result corresponds to said specified arithmetic operation on said at least one input operand for said specified rounding mode.

2. A data storage storing a program of instructions executable by a machine for emulating a system for generating floating-point test-cases for verifying the operation of a floating-point arithmetic unit, the system comprising a processing unit which includes: (a) an exponent generator, for generating floating-point exponents; (b) a significand generator, for generating floating-point significands; and (c) a fixed-point generator coupled to said exponent generator and to said signficand generator; wherein said processing unit is configured to receive a specified arithmetic operation, a specified rounding mode, at least one input operand mask, and an output result mask; and wherein said processing unit is configured to output a set of floating-point numbers which includes at least one input operand compatible with said at least one input operand mask, and an output result compatible with said output result mask; and wherein said output result corresponds to said specified arithmetic operation on said at least one input operand for said specified rounding mode.

3. A data storage storing a program of instructions executable by a machine for emulating a system for generating floating-point test-cases for verifying the operation of a floating-point arithmetic unit, the system comprising a processing unit which includes: (a) an exponent generator, for generating floating-point exponents; (b) a significand generator, for generating floating-point significands; and (c) a fixed-point generator coupled to said exponent generator and to said signficand generator; wherein said processing unit is configured to receive a specified arithmetic operation selected from a group that includes addition and subtraction, a specified rounding mode, a first input operand mask, a second input operand mask, and an output result mask; and wherein said processing unit is configured to output a set of floating-point numbers which includes a first input operand compatible with said first input operand mask, a second input operand compatible with said second input operand mask, and an output result compatible with said output result mask; and wherein said output result corresponds to said specified arithmetic operation on said first input operand and said second input operand for said specified rounding mode.

4. A system for generating floating-point test-cases for verifying the operation of a floating-point arithmetic unit, the system comprising a processing unit which includes: (a) an exponent generator, for generating floating-point exponents; (b) a significand generator, for generating floating-point significands; and (c) a fixed-point generator coupled to said exponent generator and to said signficand generator; wherein said processing unit is configured to receive a specified arithmetic operation selected from a group that includes addition and subtraction, a specified rounding mode, a first input operand mask, a second input operand mask, and an output result mask; and wherein said processing unit is configured to output a set of floating-point numbers which includes a first input operand compatible with said first input operand mask, a second input operand compatible with said second input operand mask, and an output result compatible with said output result mask; and wherein said output result corresponds to said specified arithmetic operation on said first input operand and said second input operand for said specified rounding mode.

5. The system of claim 4, wherein said fixed-point generator has two addends and a carry sequence representing the carries from the addition of successive digits of said addends, wherein said carry sequence is compatible with a carry sequence mask.

6. The system of claim 4, said significand generator further comprising: (a) an addition significand generator, for generating floating-point significands for said addition operation; and (b) a subtraction significand generator, for generating floating-point significands for said subtraction operation.

7. The system of claim 4, wherein said first input operand has a first input operand exponent, said second input operand has a second input operand exponent, and said output result has an output result exponent, said exponent generator further comprising: (a) a definite exponent generator, for generating floating-point exponents wherein said output result exponent is a definite amount different from either of said first input operand exponent and said second input operand exponent; and (b) an indefinite exponent generator, for generating floating-point exponents wherein said output result exponent is not a definite amount different from either of said first input operand exponent and said second input operand exponent.

8. The system of claim 4, wherein said exponent generator is a biased exponent generator, for generating biased floating-point exponents.

9. The system of claim 8, wherein said first input operand has a first input operand biased exponent, said second input operand has a second input operand biased exponent, and said output result has an output result biased exponent, said biased exponent generator further comprising: (a) a definite biased exponent generator, for generating biased floating-point exponents wherein said output result biased exponent is a definite amount different from either of said first input operand biased exponent and said second input operand biased exponent and (b) an indefinite biased exponent generator, for generating biased floating-point exponents wherein said output result biased exponent is not a definite amount different from either of said first input operand biased exponent and said second input operand biased exponent.

10. The system of claim 8, further comprising an unbiased exponent shift calculator for computing an unbiased exponent shift from a biased exponent shift.

11. A method of seeking a solution, if a solution exists, to a specified mathematical condition, wherein the solution is used in constructing a floating-point test-case for verifying the operation of a floating-point arithmetic unit, wherein a complete generated test case is a set of floating-point numbers for a specified arithmetic operation and a specified rounding mode, and wherein a generated test case includes at least one input operand and an output result; and wherein an input operand is compatible with an operand mask, and the output result is compatible with an output result mask; the method comprising the steps of: (a) preparing a list of choices upon which the solution is based; (b) testing whether said list of choices is empty; (c) outputting, if said list of choices is empty, that no solution exists; (d) randomly choosing, if said list of choices is not empty, a choice of said list as a selection; (e) searching for a solution to the specified mathematical condition, based on said selection; (f) outputting, if said searching was successful, said solution; (g) erasing, if said searching was not successful, said selection from said list; and (h) repeating step (a) through step (g) until outputting occurs.

12. A data storage storing a program of instructions executable by a machine for performing a method of seeking a solution, if a solution exists, to a specified mathematical condition, wherein the solution is used in constructing a floating-point test-case for verifying the operation of a floating-point arithmetic unit, wherein a complete generated test case is a set of floating-point numbers for a specified arithmetic operation and a specified rounding mode, and wherein a generated test case includes at least one input operand and an output result; and wherein an input operand is compatible with an operand mask, and the output result is compatible with an output result mask; the method comprising the steps of: (a) preparing a list of choices upon which the solution is based; (b) testing whether said list of choices is empty; (c) outputting, if said list of choices is empty, that no solution exists; (d) randomly choosing, if said list of choices is not empty, a choice of said list as a selection; (e) searching for a solution to the specified mathematical condition, based on said selection; (f) outputting, if said searching was successful, said solution; (g) erasing, if said searching was not successful, said selection from said list; and (h) repeating step (a) through step (g) until outputting occurs.

13. A data storage storing a program of instructions executable by a machine for performing the method of seeking a solution, if a solution exists, to a specified mathematical condition, wherein the solution is used in constructing a floating-point test-case for verifying the operation of a floating-point arithmetic unit, wherein a complete generated test case is a set of floating-point numbers for a specified arithmetic operation selected from a group including addition and subtraction, and for a specified rounding mode, and wherein a generated test case includes a first input operand, a second input operand, and an output result; and wherein the first input operand is compatible with a first input operand mask, the second input operand is compatible with a second input operand mask, and the output result is compatible with an output result mask; the method comprising the steps of: (a) preparing a list of choices upon which the solution is based; (b) testing whether said list of choices is empty; (c) outputting, if said list of choices is empty, that no solution exists; (d) randomly choosing, if said list of choices is not empty, a choice of said list as a selection; (e) searching for a solution to the specified mathematical condition, based on said selection; (f) outputting, if said searching was successful, said solution; (g) erasing, if said searching was not successful, said selection from said list; and (h) repeating step (a) through step (g) until outputting occurs.

14. A method of seeking a solution, if a solution exists, to a specified mathematical condition, wherein the solution is used in constructing a floating-point test-case for verifying the operation of a floating-point arithmetic unit, wherein a complete generated test case is a set of floating-point numbers for a specified arithmetic operation selected from a group including addition and subtraction, and for a specified rounding mode, and wherein a generated test case includes a first input operand, a second input operand, and an output result; and wherein the first input operand is compatible with a first input operand mask, the second input operand is compatible with a second input operand mask, and the output result is compatible with an output result mask; the method comprising the steps of: (a) preparing a list of choices upon which the solution is based; (b) testing whether said list of choices is empty; (c) outputting, if said list of choices is empty, that no solution exists; (d) randomly choosing, if said list Df choices is not empty, a choice of sail list as a selection; (e) searching for a solution to the specified mathematical condition, based on said selection; (f) outputting, if said searching was successful, said solution; (g) erasing, if said searching was not successful, said selection from said list; and (h) repeating step (a) through step (g) until outputting occurs.

15. The method of claim 14, wherein said list of choices contains an exponent shift.

16. The method of claim 14, wherein the solution is a set of floating-point numbers.

17. The method of claim 14, wherein the solution is an exponent.

18. The method of claim 14, wherein the solution is a significand.

19. The method of claim 18, wherein said list of choices contains a tails triplet.

20. A method of generating a set of fixed-point numbers containing a first addend, a second addend, and a sum, wherein the first addend is compatible with a first addend mask, the second addend is compatible with a second addend mask, the sum is compatible with a sum mask, and wherein the addition of the first addend and the second addend results in a carry sequence of carry bits, wherein each carry bit has a unique index in the carry sequence, wherein the carry sequence is compatible with a carry sequence mask and wherein each carry bit has a value in the group consisting of 0, 1, and 2, and wherein there exists a boundary index in the carry sequence corresponding to the lowest index of a carry bit having the value 2; the method comprising the steps of: (a) constructing a list of possible boundary indices; (b) testing whether said list is empty; (c) outputting, if said list is empty, that no solution exists; (d) randomly choosing, if said list is not empty, a boundary index from said list as a selection; (e) searching for a carry sequence based on said selection, which is compatible with the carry sequence mask; (f) erasing, if said searching was not successful, said selection from said list; (g) constructing, if said searching was successful, a first addend compatible with tie first addend mask, a second addend compatible with the second addend mask, and a sum compatible with the sum mask; (h) outputting said first addend, said second addend, said sum, and said carry sequence; and (i) repeating step (a) through step (h) until outputting occurs.

21. A data storage storing a program of instructions executable by a machine for performing the method of generating a set of fixed-point numbers containing a first addend, a second addend, and a sum, wherein the first addend is compatible with a first addend mask, the second addend is compatible with a second addend mask, the sum is compatible with a sum mask, and wherein the addition of the first addend and the second addend results in a carry sequence of carry bits, wherein each carry bit has a unique index in the carry sequence, wherein the carry sequence is compatible with a carry sequence mask and wherein each carry bit has a value in the group consisting of 0, 1, and 2, and wherein there exists a boundary index in the carry sequence corresponding to the lowest index of a carry bit having the value 2; the method comprising the steps of: (a) constructing a list of possible boundary indices; (b) testing whether said list is empty; (c) outputting, if said list is empty, that no solution exists; (d) randomly choosing, if said list is not empty, a boundary index from said list as a selection; (e) searching for a carry sequence based on said selection, which is compatible with the carry sequence mask; (f) erasing, if said searching was not successful, said selection from said list; (g) constructing, if said searching was successful, a first addend compatible with the first addend mask, a second addend compatible with the second addend mask, and a sum compatible with the sum mask; (h) outputting said first addend, said second addend, said sum, and said carry sequence; and (i) repeating step (a) through step (h) until outputting occurs.

Description

FIELD OF THE INVENTION

The present invention relates to the testing of floating-point arithmetic units, and, more particularly, to the generation of numerical test cases for binary floating-point adders.

BACKGROUND OF THE INVENTION

When developing integrated circuits that perform floating-point arithmetic, designers typically base the representations of floating-point (FP) numbers and the constraints on the results of arithmetic operations on published standards, such as the well-known "IEEE standard for binary floating point arithmetics, An American National Standard, ANSI/IEEE Std 754-1995". Adherence to such standards guarantees that the circuitry will perform floating-point arithmetic with acceptable and predictable results. Although it is a relatively straightforward task to implement floating-point standards in a floating-point hardware unit, designers usually make modifications in the implementation to improve performance in special cases. Because of this, it is necessary to verify compliance of the finished design to the selected standard. In many instances, errors in floating-point implementation escape detection and find their way into production. Cases such as the well-known Pentium bug show that the verification process in this area is still far from being optimal. The ever-growing demand for increased performance, reduced time-to-market, and decreasing tolerance for errors all combine to make verification increasingly harder. The term "floating-point unit" herein denotes any device or system capable of performing binary floating-point computations by any means including, but not limited to, hardware, firmware, programmable logic arrays, and software.

There are many places problems can occur in the implementation of a floating-point unit, ranging from data problems on single instructions to the correct handling of sequences of instructions in which back-to-back events challenge superscalar implementations. This complexity stems both from the interpretation of the specification (architecture) as well as the peculiarities of the implementation (microarchitecture).

Although there is on-going work to develop formal proofs of adherence to a standard, formal methods are still far from providing a complete answer to the problem. The simulation of test cases (generating the test case data, running the test case on the target floating-point unit, and confirming the accuracy of the result), has traditionally been employed for verification, and therefore remains the foundation of the verification process.

It is the generating of floating-point test cases that is of interest regarding the present invention.

Test Case Generating Background

First, it is clear that there is an enormous, practically unlimited number of different calculation cases to test. In practice then, simulation can be done on only a very small portion of the existing space. Reducing the enormous number of potential test cases to a manageable number that can actually be tested is done through placing suitable constraints on the machine numbers so that the constrained set of machine numbers used in the test will be representative of a particular aspect of testing, but will still constitute a sufficient number of cases for thorough testing. (Constraints are discussed below.)

The rationale behind verification-by-simulation is that one acquires confidence in the correctness of a floating-point unit design by running a set of test cases that encompass a sufficiently large number of different cases, which in some sense is assumed to be a representative sample of the full space. The ability of the floating-point unit design to correctly handle all cases is inferred from the correct handling of the cases actually tested.

To confidently make the above inference requires the building of a set of test cases that covers all special implementations of the floating-point unit design. The problem then becomes one of how best to do this. Since both the architecture specification and the microarchitecture implementation tend to yield a myriad of special cases, generating the test cases using a uniform random distribution over the entire floating-point space would be highly inefficient. For example, it is common that executing an FADD instruction that results in a sum of zero exercises a specific part of the design logic, and therefore such a case should be verified. The probability of randomly generating two floating-point numbers that add to zero, however, is extremely low. Therefore, prior-art random test generators usually possess some internal Testing Knowledge (TK) to bias the test generation towards cases of interest. Such test generators are described in "Model-Based Test Generation For Processor Design Verification" by Y. Lichtenstein, Y. Malka and A. Aharon, Innovative Applications of Artificial Intelligence (IAAI), AAAI Press, 1994; "Constraint Satisfaction for Test Program Generation" by L. Fournier, D. Lewin, M. Levinger, E. Roytman and Gil Shurek, Int. Phoenix Conference on Computers and Communications, March 1995; and "Test Program Generation for Functional Verification of PowerPC Processors in IBM" by A. Aharon, D. Goodman, M. Levinger, Y. Lichtenstein, Y. Malka, C. Metzger, M. Molcho and G. Shurek, 32nd Design Automation Conference, San Francisco, June 1995, pp. 279 285.

In effect, TK changes the probability distribution of a test space, better adapting that test space to existing knowledge. In a test-generator described in the foregoing references, the TK is in the form of C-language functions (called "generation functions") which can be added incrementally to the generator, such as by the users themselves. A serious limitation of this prior art approach, however, is that such generation functions are very complex and difficult to write, requiring a deep understanding of the Floating Point unit design. In practice, then, very few generating functions have been added.

Definitions

The following terms and abbreviations are used herein:

TABLE-US-00001 Biased exponent the sum of the exponent and a constant "bias" selected so that the biased exponent is always non-negative over the exponent's range. The use of a biased exponent allows representing both positive and negative exponents without requiring a sign. Denormal (a "denormalized number") a non-zero FP number whose exponent has a reserved value (usually the minimum permitted by the format), and whose explicit or implicit leading bit of the significand is zero. Exponent the component of a binary floating-point number that normally specifies the integer power of 2 which is multiplied by the significand to express the value of the represented number. In certain formats, reserved values of the exponent are used to indicate that the number is denormalized. FP Floating-Point. A binary loating-point number contains a sign, an exponent, and a significand. FxP Fixed-Point Mask a template for a binary number. A mask is a series of characters, each of which represents allowable values for the bit in the corresponding position of the binary number. There is exactly one character in a mask for each bit of the corresponding binary number, with characters in a one-to-one correspondence with the bits. Allowable mask characters include `0`, `1`, and `x`. A `0` character indicates that the corresponding bit of the binary number must be a 0, whereas a `1` character indicates that the corresponding bit of the binary number must be a 1. An `x` character is a "don't care", meaning that the corresponding bit of the binary number may be either 0 or 1. In a floating-point number, it is possible to specify separate masks for sign, exponent, and significand. NaN ("Not a Number") a symbolic entity encoded in FP format. Normal (a "normalized number") a non-zero FP number whose explicit or implicit leading bit of the significand is one. Signficand the component of a binary FP number that consists of a single explicit or implicit leading bit to the left of an implied binary point and a field of fraction bits to the right of the binary point. Even in implementations where the significand's leading bit (to the left of the binary point) is implied and is not explicitly present, the significand still includes that leading bit. Note that a significand differs from a "mantissa" in that a mantissa includes only the fraction field to the right of the binary point, whereas a significand also includes the bit to the left of the binary point. The concept of mantissa may be defined in such a way to include all of the bits of the significand, including the leftmost bit and not only the fraction bits. In this case and for a binary normalized significand, the mantissa would simply be the significand shifted one place to the right, or divided by a scaling factor of 2.

The Set of Machine Numbers

For purposes of illustration, a non-limiting example of a binary floating-point number system is the IEEE standard 754 previously referenced. We assume that three integer constants are given, E.sub.min, E.sub.max, p. The machine numbers are those which can be represented in the form v=(-1).sup.s.times.2.sup.E.times.b.sub.0b.sub.1b.sub.2 . . . b.sub.p-i, where s.epsilon.{0, 1} represents the sign of v. E, representing the exponent of v, is an integer satisfying E.sub.min.ltoreq.E.ltoreq.E.sub.max. The bit values are denoted as b.sub.i.epsilon.{0, 1}, and p is the "precision" of the system. The significand is b.sub.0b.sub.1b.sub.2 . . . b.sub.p-1, whose binary point lies between b.sub.0 and b.sub.1. All machine numbers v that satisfy |v|.gtoreq.2.sup.Emin are assumed to be normalized (b.sub.0=1). Those machine numbers which are smaller in magnitude than 2.sup.Emin (including zero) have E-E.sub.min and are denormalized (b.sub.0=0). Thus, each machine number has a unique representation (note that the IEEE standard 754 requires the same uniqueness for single and double formats but not for extended formats).

Binary Representations of Machine Numbers and the Mask Constraint

Machine numbers are herein represented as strings of binary digits (bits). This is true for fixed point numbers as well as for floating point numbers. A mask related to a number is a string of characters of the same length (number of bits) as the number, all of whose characters are in the set {`0`, `1`, `x`}. A number and a mask are compatible if all the following conditions are met: The number and the mask are of the same length (hence each bit of the number corresponds to a specific character of the mask); For each `1` character of the mask, there is a 1 value in the corresponding bit of the number; and For each `0` character of the mask, there is a 0 value in the corresponding bit of the number.

If one or more of the above conditions are not met, the number and the mask are incompatible. Thus, a `1` or a `0` character of the mask determines uniquely the value of the corresponding bit of the number. An `x` character in the mask leaves the corresponding bit value of the number undetermined.

A number is constrained by requiring it to be compatible with a given mask.

Where it is not convenient to represent a floating-point machine number by a single string of bits, it is possible (although not necessary) to split such a representation into a triplet of numbers:

TABLE-US-00002 Sign: A string of one bit, which is 0 for a `+' and 1 for a `-'. The numerical value is denoted by s (s = 0 or 1). Biased exponent: A string of w bits. This is interpreted to be a binary integer with the numerical value e, where 0 .ltoreq. e .ltoreq. 2.sup.w - 1. In a non-limiting generalization from the single and double formats of the IEEE standard 754, E.sub.min = 2 - 2.sup.w-1, E.sub.max = bias = 2.sup.w-1 - 1. Significand: A string of p bits, b.sub.0b.sub.1b.sub.2 . . . b.sub.p-1. Unlike the single and double formats of IEEE standard 754, note that b.sub.0 is explicitly included in the string. Interpreting the string as a binary number with the binary point placed between b.sub.0 and b.sub.1, the numerical value of the significand is S, where 0 .ltoreq. S .ltoreq. 2 - 2.sup.1-p.

Likewise, for convenience it is possible to speak of a triplet of masks corresponding to the above triplet of numbers. For example, it is possible to prepare and manipulate a particular mask as a significand mask.

Note that the above splitting of a floating-point number (or a mask) is for convenience and is non-limiting. In particular, it is still possible to represent a complete floating-point machine number as a single sequence of bits, and it is still possible to speak of a single mask corresponding to such a complete floating-point machine number.

The value v, which corresponds to such a triplet of bit strings is given by: 1. If e=2.sup.w-1 and S.noteq.1, then v is NaN regardless of s. 2. If e=2.sup.w-1 and S=1, then v=(-1).sup.s.times..infin. (Infinity). 3. If 0<e<2.sup.w-1 and S.gtoreq.1, then v=(-1).sup.s.times.2.sup.e-bias.times.s (Normalized numbers). 4. If e=0 and S<1 then v=(-1).sup.s.times.2.sup.Emin.times.S (Denormalized numbers and zeroes).

Machine numbers are herein denoted in underlined italics (such as a machine number a).

Rounding

Mathematically, most numbers in the set of real numbers cannot be represented by a finite number of digits (not even the entire subset of rational numbers), and most of those rational numbers which can be represented by a finite number of digits cannot be represented by the small fixed number of digits in the various floating-point formats. It is common, therefore, that the results of a floating-point operation be adjusted, or "rounded" to fit within the confines of the floating-point representation. The result of a rounding operation is a floating-point number that approximates the precise value that should result from the computation. Rounding, when applied, always introduces an error into the computation, but this error is small enough to be ignored in the vast majority of practical applications.

In practice, the precise value is not necessarily computed, but rather an intermediate result that represents floating-point numbers using a larger number of significand bits than the permitted format of the output (also ref erred to herein as the "output result"). The rounding thus consists of a truncation of the excess digits of the intermediate result, and a possible incrementing of the least significant bit of the significand, with a possible carry of this incrementing to more significant bits of the significand.

There are several different rounding modes, all of which must be taken into account when generating test cases: round up--round toward the closest floating-point number to the intermediate result that lies between the intermediate result and +.infin.. round down--round toward the closest floating-point number to the intermediate result that lies between the intermediate result and -.infin.. round to zero--round toward the closest floating-point number to the intermediate result that lies between the intermediate result and zero. round to nearest/even--round toward the floating point number closest to the intermediate result regardless of the direction. If the intermediate result lies exactly halfway between the nearest larger floating-point number and the nearest smaller floating-point number, choose the nearest floating-point number whose least significant significand bit is zero ("even"). Coverage

How does one know that a certain set of tests is sufficient? This question is related to the notion of coverage, that is, to the comprehensiveness of the set related to the target floating-point unit. Coverage models are usually defined, and the set of teats should fulfill all the existing requirements. A coverage model constitutes a set of related cases. Coverage modeling is discussed in "Software negligence and testing coverage" by C. Kaner, Proceedings of STAR 96: the Fifth International Conference, Software Testing, Analysis and Review, pages 299 327, June 1996; and "User defined coverage--a tool supported methodology for design verification" by R. Grinwald, E. Harel, M. Orgad, S. Ur, and A. Ziv, Proceedings of the 35th Design Automation Conference (DAC), pages 158 163, June 1998.

As an example, a common coverage model--albeit one that is far from trivial to fulfill--requires enumerating all major IEEE Floating Point types simultaneously for all operands of all FP instructions. For a given instruction with three operands, say ADD, this potentially yields in the order of a thousand (10.sup.3) cases to cover, assuming 10 major FP types (.+-.NaN's, .+-.Infinity, .+-.Zero, .+-.Denormal, .+-.Normal). This model can be further refined by adding more FP types, such as Minimum and Maximum Denormals, and so forth. Obviously, not all cases are possible (for example, the addition of two positive denormal numbers cannot reach infinity), so that the actual number of cases is in fact lower than the size of the Cartesian product. A coverage model, or the set of all coverage models, is really an attempt to partition the set of all calculation cases in such away that the probability distribution should be similar for all subsets.

A Generalized Test-Case Generator

Consider an automatic test generator whose input is the description of a coverage model, and whose output is a set of tests covering that model. A coverage model is defined by specifying a set of different constraints to be fulfilled, where each constraint corresponds to a particular task targeted by the coverage model. More precisely, a coverage model will have the form of a sequence of FP instructions, with sets of constraints on the input operand(s), the intermediate result(s), and the results of the participating instructions. Covering the model then requires providing a set of tests which display the instruction sequence, and which possesses the property that each constraint is satisfied by at least one test of the set. The general appearance of a single instruction constraint is of the following form: FPinst (Op1 in Pattern1) (Op2 in Pattern2) (IntRes in Pattern3) (Res in Pattern4) (1)

where FPinst is a generic floating point instruction with two input operands (Op1 and Op2), one intermediate result (IntRes), and one output result (Res). The case of two input operands and a single intermediate result is used here for simplicity, but of course generalization to any number of such parameters is possible.

A Pattern is a construct representing the logical union (.orgate.) among sets of FP numbers. The sets serve as constraints defining (in fact limiting) the allowable FP numbers for each term of expression (1). Patterns have the general following form: Pattern=Set.sub.1.orgate.Set.sub.2.orgate. . . . .orgate. Set.sub.N (2)

where each Set.sub.1 is a set of FP numbers. Each task of the coverage model corresponds to a specific selection of Set.sub.i for each Pattern. Covering the task reduces then to select a data--tuple where each individual datum belongs to the corresponding selected Set.sub.i. Thus, the number of different tasks originated from a single such instruction is the product of the number of Sets for each participating Pattern. The number of tasks for a sequence is the product of the number of tasks for each individual Instruction.

There are different kinds of constraints on FP numbers: Ranges--constraints on the upper and lower limits of a machine number or element of number triplet (for example, an exponent between 0 and 2); Weights--constraints on the limits of the number of bits of value 1 within a machine number or element of a number triplet (for example: at least 1 bit set in the significand); Run-length--constraints on the lengths of continuous streams of 1's and/or 0's (for example: a stream of at least 45 consecutive 1's in the significand); and Masks--constraints on individual bits of a machine number (described herein in detail).

It is also possible to specify a set for which the selected value should be a function of the value previously selected for another input operand. For example, a selected exponent can be at a distance of at most 2 from the exponent selected for the previous input operand. Set operations (intersection, union, complement, of same and different set types) are also possible.

For a generalized test-case generator, any architecture resource which might influence FP instruction's results is settable as an input. For example, in the non-limiting case of IEEE standard architecture, this applies to Rounding Modes and Enabled Flags.

A generalized test-case generator solves constraints that are derived from set restrictions on instruction operands. Given a restriction, the generator ideally seeks a random instance that solves the restriction, where the solutions are uniformly distributed among the set of all solutions. In practice, the complexity involved is sometimes overwhelming, especially for complex or multiple restrictions. In such cases, the generator at least ensures that each solution has a reasonable probability of being selected. As described above, constraints can be given on the input operands, the output or even on both simultaneously. It should be clear that there is a significant leap in complexity involved in solving constraints on outputs. Indeed, in contrast to the case of the input operands, the constraint on outputs includes the instruction semantics. However, even output constraints are usually solvable analytically In reasonable time complexity. Constraint restrictions start to become largely intractable when simultaneous constraints are requested on both input operands and outputs. For example, it is largely unclear how to find an instance in which the result of a MUL instruction has at least 45 bits set in its significand and the inputs are restricted by specific ranges or masks. Such a case might seem artificial, but it is often the case that cases such as this one are important to check due to specific implementation methods. Moreover, during the implementation itself, it is sometimes important to explore whether some cases are possible at all--it is desirable to know if a solution does not exist. Knowing that some cases can be neglected can be critical in optimizing the microarchitecture. In fact, in many cases, it can be shown that the constraint problem is NP-Hard. Thus, the generalized test case generator's approach for these problems should be heuristic, mixing probabilistic, search spaces and semi-analytic algorithms. Some important cases of simultaneous constraints, however, are solvable analytically, including, for example, Range constraints or Mask constraints on all operands for the FP ADD instruction.

Test Generation Via Masks

The present inventors have realized that it is possible to advantageously specify the generation of test cases using masks to constrain the floating-point numbers of the test cases, as described previously. Masks are an important way of defining sets of floating-point machine numbers by providing constraints on the bits of those numbers.

There are a number of important advantages in utilizing masks for specifying constraints in the generating of test cases: Masks are easy to visualize, understand, and manipulate. Using masks does not require the user to develop any complicated algorithms or to write any software code, as is required for prior-art generation functions. Masks can be easily created to describe a wide range of machine numbers having specific properties of interest to floating-point unit designers. It is common for an implementation to treat a specific bit, or set of specific bits, in a particular manner, and masks are a natural means to introduce a bias towards numbers having specific bits set to prescribed values, while the values of other bits are assigned randomly. At the architectural level, masks allow defining all the IEEE generic types of FP numbers and symbolic objects: Normals, Denormals, infinities, zeroes, NaN's, and so forth. Thus, a coverage model handling all types of numbers and symbols is expressible through masks. Although masks are not as general as the range, weight, or run-length constraints previously described, it is relatively straightforward to produce a finite (though possibly large) mask set which incorporates and expressed all the properties of a given range, weight, or run-length constraint.

FIG. 1 illustrates the development of mask-constrained test cases. (Note that in this particular illustration, a floating-point number is taken as being associated with a single mask, as opposed to a triplet of masks as previously discussed.) Starting with a test concept 101, a specified floating-point operation along with some Testing Knowledge 102 is compiled into an operation, mask, and rounding specification 103, which selects a rounding mode for the given floating-point operation and a set of suitable masks 104, which includes: Mask(s) for input operand(s); and Mask for the output result.

Floating-point operation, rounding mode, and mask set 104 are input to a floating-point test case generator 105. Floating-point test case generator 105 in turn outputs the floating-point operation, rounding mode, and a set of machine numbers 106, which includes: Machine number(s) for the input operand(s); and Machine number for the output result.

Floating-point operation, rounding mode, and machine number set 106 constitute a solution 107. If, however, there exists no set of machine numbers 106 compatible with mask set 104 (which is possible, such as when the specified result mask is incompatible with the input operand masks given the specified floating-point operation), then there is no solution. In this case, solution 107 is a determination that no solution actually exists.

If there exists a set 106, the machine numbers thereof, along with the floating-point operation and rounding mode, would then be input to the target floating-point unit (not shown) to see if how the unit performs for the given floating-point operation on the given inputs, and if the unit produces the given output result. If the target floating-point unit properly duplicates the machine number for the output result as given in set 106, then the unit has passed this particular test. Otherwise, if the target unit does not properly duplicate the machine number for the output result as given in set 106, there is a design error in the unit which must be corrected. Likewise, if solution 107 determines that there is in fact no solution, it may be possible to test the target unit to verify that the unit in fact does not perform any computation that results in a set of machine numbers corresponding to the masks given in set 106, because doing so also indicates a design error in the unit. Thorough testing requires exercising the target floating-point unit with a large number of such test cases for a variety of conditions.

As an example (based on the concepts in IEEE standard 754), consider a hypothetical binary floating point format of eight bits, whose structure is seeeffff. Namely, there is one bit for a sign, three bits for a biased exponent and four bits for a fraction. In analogy with the IEEE formats single and double, the significand has five bits, E.sub.min=-2, E.sub.max=bias-3. Given three masks M.sub.a=0100x101, M.sub.b=001x1011, and M.sub.c=010xx10x, the solution requires three floating point numbers a, b, and c, which are compatible with the respective masks, such that c=round (a+b). Assuming that round stands for round to nearest/even, one solution is a=01000101, b=00101011, and c=01001100.

In the scheme illustrated in FIG. 1, it is necessary to construct floating-point test-case generator 105 with the following properties in mind: All valid solutions must have roughly the same probability of being produced by the test-case generator; and in particular, The solution set must not arbitrarily exclude any valid solution. In other words, every valid solution must have a non-zero probability of being selected.

Currently, however, there are no such mask-constrained floating-point test-case generators available, even for a restricted set of floating-point operations such as addition and subtraction. In order to create a floating-point test-case generator, it is necessary to have as a minimum, a floating-point test-case generator for addition and subtraction, which can solve the hollowing problem: Given masks for three machine numbers and a rounding mode, generate machine numbers a, b, and c, which are compatible with the given masks and satisfy c=round(a.+-.b), where round corresponds to the given rounding mode.

There is thus a need for, and it would be highly advantageous to have, a mask-constrained floating-point test case generator for floating-point addition and floating-point subtraction which has the desired properties listed above. This goal is met by the present invention.

SUMMARY OF THE INVENTION

The present inventors have recognized that the lack of a practical framework for generating constrained, meaningful test cases is a major deficiency in the prior art, and represents the principal obstacle to efficient verification. The present invention, therefore, approaches this problem from the overview presented in the following sections.

It is an object of the present invention to solve the following problem: Given masks for three machine numbers and a rounding mode round, generate machine numbers, a, b, c, which are compatible with the masks and satisfy c=round(a.+-.b).

It is an object of the present invention to develop a method for generating three floating-point machine numbers a, b, and c corresponding to three given masks M.sub.a, M.sub.b, and M.sub.c, and a rounding mode round, such that c=round(a+b), where either or both a and b may be positive or non-positive.

It is also an object of the present invention that all valid solutions have roughly the same probability of being produced by the method, and that no valid solutions be excluded.

It is moreover an object of the present invention that the method support general binary floating-point standards, including but not limited to IEEE standard floating-point arithmetic when generalized to include all allowed FP format sizes (such as 32 bits, 64 bits, 80 bits, 128 bits). With respect to this particular goal, it is noted that the innovations of the present invention are not necessarily limited to binary implementations, but can be applied in other number systems as well. Although binary systems are of primary importance, because current floating-point standards are expressed explicitly in terms of binary numbers, it is understood that the present invention is not limited to binary arithmetic, and the details of the embodiments herein presented are to be taken as non-limiting examples.

It is further an object of the present invention to develop a system for implementing the method.

The basic problem may be split into two sub-problems, which may be solved by two generators of machine numbers, respectively: Floating-point generator for addition: Given six masks, for biased exponents and for significands, M.sub.ea, M.sub.Sa, M.sub.eb, M.sub.Sb, M.sub.ec, M.sub.Sc, the generator either generates three non-negative machine numbers, a, b, c, whose biased exponents and whose significands are compatible with the corresponding masks and satisfy, c=round(a+b), or states that there is no solution. Floating-point generator for subtraction: Given six masks, for biased exponents and for significands, M.sub.ea, M.sub.Sa, M.sub.eb, M.sub.Sb, M.sub.ec, M.sub.Sc, the generator either generates three non-negative machine numbers, a, b, c, whose biased exponents and whose significands are compatible with the corresponding masks and satisfy, c=round(a-b), or states that there is no solution.

Note that when the problem is reduced to the two cases above, the three machine numbers, a, b, and c, are all non-negative. In the case of the floating-point generator for subtraction, the values assigned to a and b are interchanged if necessary so that a.gtoreq.b. Note also that in the case of the floating-point generator for subtraction, where a.noteq.b it is possible to exercise the target floating-point unit with two test cases resulting from a single solution found by the generator: one test case is simply c=round(a-b), where c is positive; and the other test case is c=round(b-a), where c is negative. As far as the floating-point test-case generator is concerned, these are mathematically identical and do not require a separate method of solution. From the standpoint of verification testing of the target floating-point unit, however, they are distinct problems, and the successful passing of one test by the target floating-point unit does not necessarily imply the successful passing of the other test.

The method of the present invention solves the above problem for simultaneous mask constraints. That is, there is a mask constraint on both input operands a and b, and on the output result c for any specified rounding mode and for the floating-point operations FADD and FSUB. It is noted that the distinction between addition and subtraction can be implied in the sign of the operand b: If b<0, a subtraction operation is implied; otherwise, an addition operation is implied. It is further noted that a single solution found by the binary floating-point test-case generator of the present invention can be verified on the target floating-point unit for both FADD and FSUB by adjusting the sign of one of the input operands. That is, given the solution a, b, and c where c=round(a+b), it is possible to verify FADD on the floating-point unit for a, b, and c, and it is also possible to verify FSUB on the floating-point unit for a, -b, and c. The internal implementation of FADD in the target floating-point unit can be structurally different from that of FSUB, justifying a separate verification pass, but the identical result c should be output in both cases.

Rounding Modes Needed

In the general case, there are the following rounding modes: round.epsilon.{round down, round up, round toward zero, round to nearest/even} (3)

However, since the problem has been reduced to cases where the three machine numbers are all non-negative, it is possible to omit, without loss of generality, the round toward zero mode. Since all non-zero machine numbers will be positive, this mode is equivalent to round down.

Novelty

There are several novel aspects of the present invention: The present invention goes beyond the employment of masks for expressing floating-point machine number constraints to include a novel use of masks for controlling the stream of carry bits created during the floating-point addition operation. In addition to providing a key portion of the method, this also enriches the verification process by allowing a floating-point unit to be exercised through different carry configurations. The present invention discloses a fixed-point generator which has a number of unexpected uses in various places throughout the floating-point test-case generation. Notational Conventions

The following notation is employed herein in the context c=round (a.+-.b): a, b, c floating-point machine numbers e.sub.i biased exponent E.sub.i unbiased exponent M.sub.i mask n boundary index, the position of the leftmost 2 in a carry sequence N number of bits in a fixed-point machine number p number of bits in a significand (including the most significant bit) q maximum definite binary point shift, usually comparable in magnitude to p (shifts greater than q are considered indefinite) q.sub.i biased exponent shift q.sub.a=e.sub.c-e.sub.a, q.sub.b=e.sub.c-e.sub.b (1) Q.sub.i unbiased exponent shift Q.sub.a=E.sub.c-E.sub.a, Q.sub.b=E.sub.c-E.sub.b (2) S.sub.i significand w number of bits in a biased exponent x, y, z fixed-point machine numbers

FIG. 2 is a block diagram of a floating-point addition/subtraction test-case generator according to the present invention. A mask set 201 is input into a processing unit 202, which generates test-cases in an output 250, which, as previously noted, may be either floating-point machine numbers compatible with mask set 201 and a specified rounding mode (not shown) or the case of "no solution". In the non-limiting example presented herein, processing unit 202 includes a q.sub.a, q.sub.b/q.sub.b, q.sub.c selector 205 whose output goes to a biased exponent generator 210, which includes a definite biased exponent generator 215 and an indefinite biased exponent generator 220. For addition, q.sub.a, q.sub.b/q.sub.b, q.sub.c selector 205 selector selects q.sub.a and q.sub.b, whereas for subtraction q.sub.a, q.sub.b/q.sub.b, q.sub.c selector 205 selector selects q.sub.b and q.sub.c. Then, a Q.sub.a, Q.sub.b/Q.sub.b, Q.sub.c calculator 225 computes Q.sub.a and Q.sub.b for addition or Q.sub.b and Q.sub.c for subtraction, and sends them to a significand generator 230, which includes an addition significand generator 235 and a subtraction significand generator 240. Both biased exponent generator 210 and significand generator 230 rely on a fixed-point generator 245 in making their respective computations. Finally, the output of biased exponent generator 210 and significand generator 230 are combined to output solution set 250.

Note that, in FIG. 2, biased exponent generator 210 is a non-limiting example of a more general exponent generator that need not be restricted to biased exponents only. Because an unbiased exponent shift is calculated, it is also possible to conceptualize the system of FIG. 2 in terms of such general exponent generator.

Given the selected and calculated values for q.sub.a, q.sub.b, Q.sub.a, Q.sub.b for addition (or q.sub.b, q.sub.c, Q.sub.b, Q.sub.c, in the case of subtraction), it is possible to produce the biased exponents and the significands independently, by invoking number generators such as those shown in FIG. 2, and defined as follows:

Definite biased exponent generator 215 performs the following: Given the two non-negative integers q.sub.1, q.sub.2, with q.sub.1.epsilon.{0, 1}, and three masks of length w, M.sub.1, M.sub.2, M.sub.3, for the biased exponents, definite biased exponent generator 215 either generates and outputs three biased exponents e.sub.1, e.sub.2, e.sub.3, which are compatible with the respective masks and satisfy e.sub.3=e.sub.1+q.sub.1=e.sub.2+q.sub.2, or outputs that no solution exists.

Indefinite biased exponent generator 220 performs the following: Given the two non-negative integers q.sub.1, q.sub.2, with q.sub.1.epsilon.{0, 1}, and three masks of length w, M.sub.1, M.sub.2, M.sub.3, for the biased exponents, indefinite biased exponent generator 220 either generates an integer q.sub.2 and three biased exponents e.sub.1, e.sub.2, e.sub.3, which are compatible with the respective masks and satisfy e.sub.3=e.sub.1+q.sub.1=e.sub.2+q.sub.2, such that q.sub.2>q, or outputs that no solution exists.

Addition significand generator 235 performs the following: Given two non-negative integers Q.sub.a, Q.sub.b, one of which is 0 or 1, three masks of length p for the significands, M.sub.Sa, M.sub.Sb, M.sub.Sc, and a rounding mode, round.epsilon.{round down, round up, round to nearest/even}, addition significand generator 235 either generates three significands S.sub.a, S.sub.b, S.sub.c which are compatible with the respective masks and satisfy S.sub.c=round (2.sup.-Qa S.sub.a+2.sup.-Qb S.sub.b), or outputs that no solution exists.

Subtraction significand generator 240 performs the following: Given two non-negative integers Q.sub.b, Q.sub.c, one of which is 0 or 1, and three masks of length p for the significands, M.sub.Sa, M.sub.Sb, M.sub.Sc, and a rounding mode, round.epsilon.{round down, round up, round to nearest/even}, subtraction significand generator 240 either generates three significands S.sub.a, S.sub.b, S.sub.c, which are compatible with the respective masks and satisfy 2.sup.-QcS.sub.c=round (S.sub.a-2.sup.-Qb S.sub.b), or outputs that no solution exists.

FIG. 3 is a simplified block diagram of fixed-point generator 245 (as also appears in FIG. 2) according to the present invention. A mask set 303 containing masks M.sub.x, M.sub.y, and M.sub.z, for three fixed-point machine numbers x, y, and z is input into fixed-point generator 245. In additions a mask M.sub.c 305 for the carry stream is also input. Note that M.sub.x, M.sub.y, and M.sub.z each have N characters corresponding to the N bits of x, y, and z, whereas M.sub.c has N+1 characters. Based on the inputs, fixed-point generator 245 outputs a solution 307, which either contains a set of three fixed-point machine numbers x, y, and z which are compatible with mask set 303 (M.sub.x, M.sub.y, and M.sub.z) and mask 305 (M.sub.c); or which is the case of "no solution".

It is to be noted that all of the generators of the present invention generate a solution that is in effect randomly selected from the complete set of valid solutions, and if the set of valid solutions is empty, the case of "no solution" is output instead. It is not required that a generator output all of the valid solutions, but only a single solution, provided that at least one valid solution exists. It is also not required that a generator be able to determine how many valid solutions there are. The generators, however, do not arbitrarily exclude any valid solution. That is, there is a non-zero probability that any specific valid solution will be generated. Subsequent operation of a generator will usually generate a different, randomly-generated solution. If the complete set of valid solutions is of high order, then it will be overwhelmingly probable that repeated operations of a generator will result in the output of distinct solutions, so repetitions of identical solutions are normally rare.

Solution-Seeking Method

As will be discussed in detail below, the generators make extensive use of a solution-seeking method illustrated in FIG. 4. In the present invention, the solution-seeking method is used in a number of places to se