Fast floating-point truncation to integer form

Details Fast floating-point truncation to integer form Fast floating-point truncation to integer form

2000-01-24

2003-03-18

Malzahn, David H. (Department: 2124)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

C708S497000, C708S551000

Reexamination Certificate

active

06535898

ABSTRACT:

TECHNICAL FIELD
The present invention relates to electronic data processing, and more particularly concerns the conversion of individual numeric data items from floating-point form to integer form in a computer.
COPYRIGHT
A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction of the patent document or the patent disclosure as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever. The following notice applies to the software and data described herein: “Copyright© 1999, Microsoft Corp., all rights reserved.”
BACKGROUND
A computer represents numeric data items in two types of format. Floating-point formats employ a form of scientific notation to encode a number such as −0.777328×10
34
. Floating-point data formats allow very large and very small numbers to be encoded, and permit consistent precision for numbers having a very great range of magnitudes. Typically, a processing engine's internal floating-point format includes a sign bit or field to distinguish between positive and negative numbers, a relatively short exponent or characteristic field to signify a power of a base (usually ‘2’), and a longer significand, fraction, or mantissa field to specify certain significant digits of the number with an implied fixed point, usually near the first digit. Some conventional formats allow denormalized significands, contain another bit or field that can specify a position for a decimal, binary, or other point, and include facilities for indicating whether the contents represent a valid number. A single engine may support multiple floating-point formats, either by explicit mode switching, by internal conversion, by codes in the data items themselves, or by other means. The prevalent format at the present time is found in the ANSI/IEEE-754 standard dated 1985. A later -854 revision is not yet widely used.
Fixed-point data items employ a certain number of bits to represent numbers with points at an implied location in the bit pattern. When, as is the usual case, the point is implied after the least-significant digit, the data items represent whole numbers, or integers. The terms fixed-point and integer are usually used synonymously. Although integer data cannot represent as wide a range of values, arithmetical operations on them are much easier and much faster in a computer. Different processors support different lengths and/or types of integers, and the same processor frequently supports multiple lengths, such as 8-bit bytes, 16-bit words, 32-bit double words, 64-bit quad words, and even 16-byte frames.
Conversion between floating-point and integer representations of the same number is frequently necessary. Because floating-point values often cannot be represented exactly in the integer format, some method of rounding to a nearest integer is required. Several different methods or modes are in common use, and each has multiple names.
Nearest, or round-to-even, mode selects the nearest of two adjacent integer values. If neither is nearer, then the even value is chosen.
Positive-infinity, or ceiling, mode selects the integer equal to or more positive than the floating value.
Negative-infinity, or floor, mode chooses the integer equal to or more negative than the floating value.
Truncate, chop, or zero, mode rounds to the integer that is closest to zero. That is, it merely drops any fractional part.
Different applications and different languages may prefer or mandate one of these modes. Therefore, a processing engine of any generality must be able to convert numbers using multiple modes. The most common implementation, from microprocessors to mainframes, is to provide a machine-level instruction that converts one floating-point data item to one integer item, and to provide another instruction to set a flag or register that specifies which of several rounding modes is to be used in the conversion. This is an optimum strategy for many purposes, because any single program almost always uses only one rounding mode throughout its execution. Even though the instruction that changes the mode is often agonizingly slow (e.g., 60-70 machine cycles, slower than a floating-point division operation), it need only be executed once for an entire execution of a program. To accommodate multi-tasking, the current mode can be incorporated into a machine state that is saved and restored when the processor switches among tasks.
The truncate mode was the first rounding method. It is simplicity itself to implement: any fractional part of a number is simply lopped off and discarded. Many graphics algorithms still employ truncation, for historical reasons and also for its fast execution. The Bresenham algorithm for drawing a line or circle on a raster display, for example, uses truncation of any floating-point values that specify the line position. This algorithm is described in many classic texts, such as Foley and Van Dam, Fundamentals of Interactive Computer Graphics (First Ed., 1983), pp. 433-436 and 442-445. Graphics is a sufficiently common requirement in so many areas of computer usage, and truncation occurs so often in so many graphics computations, that the efficiency of its implementation is of prime importance.
On the other hand, most modem languages and application programs prefer, or even mandate, another mode; round-to-even currently enjoys a large lead. It is almost always impractical to set truncate mode only for those routines that use it, and then reset it for the remainder of a program. It is also not usually possible to find out what mode is currently in force in a program. The mode can be set, but cannot be easily read. Also, many modem machines have out-of-order or non-sequential execution of instructions on a real-time basis that varies for each run, and they pipeline instructions for execution at unpredictable times. A processor must clear out all execution units and pipeline stages before setting a new rounding mode, in order to guarantee that the new mode will not incorrectly operate upon previously launched instructions. This hardware must then fill again with new instructions, before further useful work can be performed. Even older processors decouple the floating-point hardware from the integer-unit's timing sufficiently that exceptions, mode changes, and so forth within the floating-point unit bog down the entire processor for relatively long periods of time.
Therefore, even when processors allow multiple rounding modes, and even though some need only two instructions to switch modes, the amount of time required to accomplish a switch appreciably slows the processor for common tasks such as drawing graphics objects. A much more efficient truncation method would be beneficial in programming environments.
SUMMARY OF THE INVENTION
The present invention provides methods for converting processor representations of floating-point data items to corresponding representations of truncated integer items in an efficient manner. Significant time savings are achieved without setting and resetting a mode register in the processor. A basic implementation operates without any knowledge of which conversion mode a processor is currently using, by converting a floating-point data item to an integer representation in whatever mode the processor happens to be in, then introducing one of multiple correction values to the integer representation in response to the sign of the original data and a difference between the integer and the original data. When the conversion mode is known to be in a particular state, another implementation detects the sign of the data item, and, in response thereto, produces two different integer representations from the data item and selects one or the other of them as an output integer data item. Conversions according to the invention further reduce execution time by minimizing or totally eliminating the use of conditional jumps or branches. Low-level machine instructi

Affiliated with

Also associated with

Rating

Fast floating-point truncation to integer form does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Fast floating-point truncation to integer form, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast floating-point truncation to integer form will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3016158