Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
2000-10-31
2004-04-27
Zhen, Wei Y. (Department: 2122)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
C717S140000
Reexamination Certificate
active
06728953
ABSTRACT:
BACKGROUND
1. Field of the Invention
The present invention relates to compilers for programming languages. More specifically, the present invention relates to a method and an apparatus for selectively enabling expression folding during the compilation process by using a first assignment operator to specify an expression assignment and a second assignment operator to specify a value assignment.
2. Related Art
Rapid advances in computing technology make it possible to perform trillions of computational operations each second. This tremendous computational speed makes it practical to perform computationally intensive tasks as diverse as predicting the weather and optimizing the design of an aircraft engine. Such computational tasks are typically performed using machine-representable floating-point numbers to approximate values of real numbers. (For example, see the Institute of Electrical and Electronics Engineers (IEEE) standard 754 for binary floating-point numbers.)
In spite of their limitations, floating-point numbers are generally used to perform most computational tasks.
One limitation is that machine-representable floating-point numbers have a fixed-size word length, which limits their accuracy. Note that a floating-point number is typically encoded using a 32, 64 or 128-bit binary number, which means that there are only 2
32
, 2
64
or 2
128
possible symbols that can be used to specify a floating-point number. Hence, most real number values can only be approximated with a corresponding floating-point number. This creates estimation errors that can be magnified through even a few computations, thereby adversely affecting the accuracy of a computation.
A related limitation is that floating-point numbers contain no information about their accuracy. Most measured data values include some amount of error that arises from the measurement process itself. This error can often be quantified as an accuracy parameter, which can subsequently be used to determine the accuracy of a computation. However, floating-point numbers are not designed to keep track of accuracy information, whether from input data measurement errors or machine rounding errors. Hence, it is not possible to determine the accuracy of a computation by merely examining the floating-point number that results from the computation.
Interval arithmetic has been developed to solve the above-described problems. Interval arithmetic represents numbers as intervals specified by a first (left) endpoint and a second (right) endpoint. For example, the interval [a, b], where a<b, is a closed, bounded subset of the real numbers, R, which includes a and b as well as all real numbers between a and b. Arithmetic operations on interval operands (interval arithmetic) are defined so that interval results always contain the entire set of possible values. The result is a mathematical system for rigorously bounding numerical errors from all sources, including measurement data errors, machine rounding errors and their interactions. (Note that the first endpoint normally contains the “infimum”, which is the largest number that is less than or equal to each of a given set of real numbers. Similarly, the second endpoint normally contains the “supremum”, which is the smallest number that is greater than or equal to each of the given set of real numbers.)
However, computer systems are presently not designed to efficiently handle intervals and interval computations. Consequently, performing interval operations on a typical computer system can be hundreds of times slower than performing conventional floating-point operations. In addition, without a special representation for intervals, interval arithmetic operations fail to produce results that are as narrow as possible.
What is needed is a method and an apparatus for efficiently performing arithmetic operations on intervals with results that are as narrow as possible. (Interval results that are as narrow as possible are said to be “sharp”.)
One problem in performing interval computations arises from optimizations that are often performed during the compilation process. One common optimization is “expression folding,” in which a first expression is substituted for a variable within a second expression and the resulting second expression is simplified. For example, if a program includes the instruction X=A+B, followed by the instruction Z=X−A, some compilers will substitute A+B for X in the expression for Z and will simplify, Z=(A+B)−A=B. As can be seen from this simple example, expression folding can potentially eliminate unnecessary computational operations.
However, expression folding can also create problems, especially for interval computations. For example, suppose a program must compute the summation of a number of intervals x
i
.
X
=
∑
i
=
1
n
x
i
Next, suppose that the program subsequently computes Y
j
=X−x
j
. If the compiler performs expression folding by substituting the summation for X, and then simplifies to eliminate x
j
, the program ends up computing the following partial sum.
Y
j
=
∑
i
=
1
i
≠
j
n
x
i
Note that computing this partial sum is much slower than simply computing Y
j
=X−x
j
, which simply involves performing a single subtraction operation. Hence, when possible, it is desirable not to use expression folding. However, note that if x
j
>>Y
j
, expression folding prevents rounding errors caused by a large x
j
from undermining the accuracy of Y
j
. In this case it is desirable to use expression folding.
Hence, what is needed is a method and an apparatus that facilitates expression folding in cases where expression folding is advantageous, and that facilitates disabling expression folding in cases where expression folding is not advantageous.
SUMMARY
One embodiment of the present invention provides a system that selectively enables expression folding during compilation of a program, wherein the compilation converts the program from source code into executable code. The system operates by forming an expression tree for an expression within the source code which includes an assignment operator. If the assignment operator is a first assignment operator that is a value assignment, only the computed value can be used in subsequent expressions, thereby disabling expression folding during the compilation process. On the other hand, if the assignment operator is a second assignment operator that specifies an expression assignment, the entire expression can be used in place of the variable on the left of the expression assignment, thereby enabling expression folding during the compilation process.
In one embodiment of the present invention, the expression includes a mathematical interval.
In one embodiment of the present invention, the expression folding involves substituting of a first expression for a variable within a second expression, and then simplifying the resulting second expression through mathematically-equivalent symbolic manipulation.
In one embodiment of the present invention, the first assignment operator is represented as “:=” within the source code.
In one embodiment of the present invention, the second assignment operator is represented as “=” within the source code.
In one embodiment of the present invention, if the assignment operator is an expression assignment operator, expression folding is required if the expression on the right-hand-side of the expression assignment operator contains a non-degenerate literal interval constant.
REFERENCES:
Mathematica Book, “MATLAB Compiler: mcc”, 1998, http://www.mathworks.com/access/helpdesk_r12p1/help/toolbox/compiler/appaquic.shtml, Mathworks.com, ed. 4.*
Wolfram, Stephan, “Mathematica Book: Legacy and Copywrite for Mathematica Book”, 1998, http://documents.wolfram.com/legacy.html, Wolfram Research, “Notes on the Various Editions of the Mathematica Book”.*
Wolfram, Stephen, “Mathematica Book: 2.4.8 Immediate and Delayed Definitions”, 1998, http://document
Park Vaughan & Fleming LLP
Sun Microsystems Inc.
Zhen Wei Y.
LandOfFree
Selectively enabling expression folding during program... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Selectively enabling expression folding during program..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Selectively enabling expression folding during program... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3274428