Methods and apparatus for predicting an underflow condition associated with a floating-point multiply-add operation

Methods and apparatus for predicting an underflow condition associated with a floating-point multiply-add operation are disclosed. Preferably, the prediction is “pessimistic” in that it predicts that an underflow condition will result in all situations where an underflow condition might result. However, the methods and apparatus may also predict that an underflow condition might result in some situations where an underflow condition will not result. If an underflow condition is predicted, the floating-point multiply-add operation is preferably performed by a software routine capable of handling the underflow condition. If an underflow condition is not predicted, the floating-point multiply-add operation is preferably performed by a hardware circuit to increase speed and reduce computational overhead.

TECHNICAL FIELD

The present invention relates in general to microprocessors, and, in particular, to methods and apparatus for predicting an underflow condition associated with a floating-point multiply-add operation.

BACKGROUND

Microprocessors are frequently required to perform mathematical operations using floating-point numbers. Often, a specialized hardware circuit (i.e., a floating-point unit) is included in the microprocessor (or electrically coupled to the microprocessor) to perform these floating-point multiply-add operations. By using a floating-point unit, floating-point multiply-add operations may be performed faster than if they were performed in software, and the software execution unit of the microprocessor is free to execute other operations.

However, when floating-point numbers are used in mathematical operations, the result of the operation may be too large or too small to be represented by the floating-point unit. When the result is too large to be represented by the floating-point unit, an ‘overflow’ condition occurs. When the result is too small to be represented by the floating-point unit, an ‘underflow’ condition occurs. In either case (overflow or underflow), a software routine must be executed to perform the operation if accurate results are required. In such an instance, the system is burdened by the overhead of both the execution time of the floating-point unit and the execution time of the software routine even though only a single floating-point multiply-add operation is performed.

DETAILED DESCRIPTION OF EXAMPLES

In general, the methods and apparatus described herein predict an underflow condition associated with a floating-point multiply-add operation. Preferably, the prediction is “pessimistic” in that it predicts that an underflow condition will result in all situations where an underflow condition will result. However, the methods and apparatus may also predict that an underflow condition will result in some situations where an underflow condition will not result. If an underflow condition is predicted, the floating-point multiply-add operation is preferably performed by a software routine capable of handling the underflow condition. If an underflow condition is not predicted, the floating-point multiply-add operation is preferably performed by a hardware circuit to increase speed and reduce computational overhead.

A block diagram of a computer system100is illustrated inFIG. 1. The computer system100may be a personal computer (PC), a personal digital assistant (PDA), an Internet appliance, a cellular telephone, or any other computing device. In the illustrated example, the computer system100includes a main processing unit102powered by a power supply103. The main processing unit102may include one or more central processing units (CPUs)104electrically coupled by a system interconnect106to one or more memory device(s)108and one or more interface circuits110. In the illustrated example, the system interconnect106is an address/data bus. Of course, a person of ordinary skill in the art will readily appreciate that interconnects other than busses may be used to connect the CPU(S)104to the memory device(s)108. For example, one or more dedicated lines and/or a crossbar may be used to connect the CPU(s)104to the memory device(s)108.

The CPU(S)104may include any type of well known microprocessor, such as a microprocessor from the Intel Pentium™ family of microprocessors, the Intel Itanium™ family of microprocessors, and/or the Intel XScale™ family of processors. The main memory device108may include dynamic random access memory (DRAM), but may also include non-volatile memory. In the illustrated example, the memory device(s)108store a software program which is executed by one or more of the CPU(s)104in a well known manner.

The interface circuit(s)110may be implemented using any type of well known interface standard, such as an Ethernet interface and/or a Universal Serial Bus (USB) interface. One or more input devices112may be connected to the interface circuits110for entering data and commands into the main processing unit102. For example, an input device112may be a keyboard, mouse, touch screen, track pad, track ball, isopoint, and/or a voice recognition system.

One or more displays, printers, speakers, and/or other output devices114may also be connected to the main processing unit102via one or more of the interface circuits110. The display114may be a cathode ray tube (CRTs), a liquid crystal display (LCDs), or any other type of display. The display114may generate visual indications of data generated during operation of the main processing unit102. The visual displays may include prompts for human operator input, calculated values, detected data, etc.

The computer system100may also include one or more storage devices116. For example, the computer-system100may include one or more hard drives, a compact disk (CD) drive, a digital versatile disk drive (DVD), and/or other computer media input/output (I/O) devices.

The computer system100may also exchange data with other devices via a connection to a network118. The network connection may be any type of network connection, such as an Ethernet connection, digital subscriber line (DSL), telephone line, coaxial cable, etc. The network118may be any type of network, such as the Internet, a telephone network, a cable network, and/or a wireless network.

A more detailed block diagram of the CPU104is illustrated inFIG. 2. Preferably, the CPU104includes a controller202, a prediction unit204, a normalizer206, a floating-point hardware unit208, and a floating-point software unit210. The floating-point hardware unit208may be implemented by conventional electronic circuitry in a well known manner. The floating-point software unit210may be implemented by a microprocessor executing software instructions in a well known manner. The controller202, the prediction unit204, and the normalizer206may be implemented by a microprocessor executing software instructions and/or conventional electronic circuitry. In addition, a person of ordinary skill in the art will readily appreciate that certain modules may be combined or divided according to customary design constraints. Still further, one or more of these modules202–208may be located external to the CPU104.

For the purpose of controlling the interaction of the prediction unit204, the normalizer206, the floating-point hardware unit208, and the floating-point software unit210, the CPU104includes a controller202. The controller202is operatively coupled to the prediction unit204, the normalizer206, the floating-point hardware unit208, and the floating-point software unit210in a well known manner. For example, one set of software instructions may be operatively coupled to another set of software instructions via a subroutine call, parameter passing, and/or shared memory location(s). In another example, one piece of electronic circuitry may be operatively coupled to another piece of electronic circuitry via electrical signal line(s) such as a bus. In yet another example, a set of software instructions may be operatively coupled to a piece of electronic circuitry via electrical signal line(s) stimulated by a microprocessor executing the software instructions.

For the purpose of predicting an underflow condition associated with a floating-point multiply-add operation, the CPU104includes a prediction unit204. The prediction unit204may be implemented in hardware (seeFIG. 3) or software (seeFIG. 4). The prediction unit204is structured to assert an output signal indicative of the absence of the underflow condition. Conversely, the same prediction unit204is also structured to assert an output signal indicative of a possible underflow condition. In other words, the logic level of the output signal is not material as long as subsequent circuit(s) and/or software routine(s) are structured using the same logical convention.

Floating-point numbers are represented in scientific notation (e.g., 1.01×23). Accordingly, a floating number includes a sign (e.g., positive), a significand (e.g., 1.01), a base (e.g., 2) and an exponent (e.g., 3). In a binary floating-point system, a sign bit of ‘0’ denotes a positive value and a sign bit of ‘1’ denotes a negative value. In a binary system, a base of 2 is presumed and not stored. In many binary floating-point systems, numbers are stored and/or manipulated in ‘normalized’ form (i.e., the radix point is located immediately after the first non-zero digit). In such an instance, a leading ‘1’ may be presumed and not stored (e.g., as in IEEE Standard for Binary Floating-Point Arithmetic—ANSI/IEEE Standard 754-1985).

When floating-point numbers are used in mathematical operations, the result of the operation may be too large or too small to be represented by the floating-point system. When the result is too large to be represented by the floating-point system, an ‘overflow’ condition occurs. When the result is too small to be represented by the floating-point system, an ‘underflow’ condition occurs. Underflow and overflow conditions occur when the exponent of the result is beyond the maximum value (e.g., 127 for single-precision and 1023 for double-precision), and the significand is all 1s (including the normalizing ‘1’ bit).

In this case, the floating-point multiply-add operation operates on three floating-point numbers (e.g., A+B*C). In such an instance, the operation includes a first operand exponent (ea), a second operand exponent (eb), and a third operand exponent (ec). Each of the operand exponents (ea, eb, and ec) has a predefined minimum value (emin). In addition, each of the operand exponents (ea, eb, and ec) is associated with a separate significand. Each significand has a predefined number of significant bits (N1). The result of the floating-point multiply-add operation is also associated with a significand. The significand of the result also has a predetermined number of significant bits (N2). N1is greater than or equal to N2.

Preferably, the prediction unit204is structured to assert an output signal indicative of the absence of the underflow condition if at least one of the following conditions is true:
(eb+ec−ea)<=(−3) and (ea)>=(emin+1)  (i)
(−2)<=(eb+ec−ea)<=(0) and (eb+ec)>=(emin+2*N1−2+2*(N1−N2))  (ii)
(eb+ec−ea)=(1) and (ea)>=(emin+N1−1+(N1−N2));  (iii)
(2)<=(eb+ec−ea)<=(N1−2) and (ea)>=(emin−1);  (iv)
(N1−1)<=(eb+ec−ea) and (eb+ec)>=(emin+1);  (v)
(ea)<=(emin−1) and (eb+ec)>=(emin+1).  (vi)

For the purpose of normalizing one or more floating-point numbers, the CPU104includes a normalizer206. Preferably, the normalizer206shifts the position of the radix point to be immediately after an implied ‘1’ by adjusting an associated exponent value in a well known manner.

For the purpose of performing one or more floating-point multiply-add operations, the CPU104includes a floating-point hardware unit208. The floating-point hardware unit208is a well known circuit capable of quickly performing one or more predetermined floating-point multiply-add operations. However, the range of the floating-point hardware unit208is inherently limited by some predetermined number of bits used to represent the floating-point numbers used in the floating-point multiply-add operations.

For the purpose of performing one or more floating-point multiply-add operations, the CPU104also includes a floating-point software unit210. Preferably, the floating-point software unit210is capable of handling larger and/or smaller floating-point results than the floating-point hardware unit208. However, the floating-point software unit210is typically slower than the floating-point hardware unit208.

A more detailed block diagram of the prediction unit204is illustrated inFIG. 3. The prediction unit204is a logic circuit for predicting a possible underflow condition associated with a floating-point multiply-add operation. In this example, the prediction unit204includes seven comparators302–314, six logic-AND gates316–326, and one logic-OR gate328. Of course, a person of ordinary skill in the art will readily appreciate that many different circuits could be employed to achieve the same result.

As discussed above, the floating-point multiply-add operation operates on three floating-point numbers (e.g., A+B*C). In such an instance, the operation includes a first operand exponent (ea), a second operand exponent (eb), and a third operand exponent (ec). Each of the operand exponents (ea, eb, and ec) has a predefined minimum value (emin). In addition, each of the operand exponents (ea, eb, and ec) is associated with a separate significand. Each significand has a predefined number of significant bits (N1). The result of the floating-point multiply-add operation is also associated with a significand. The significand of the result also has a predetermined number of significant bits (N2).

Each of these numbers (ea, eb, ec, emin, N1, and N2) as well as mathematical combinations of these numbers (e.g., eb+ec) may be available to the prediction unit204in a well known manner. For example, a number may be retrieved from memory108and placed on the system interconnect106. Similarly, one or more numbers may be retrieved from memory108, combined mathematically by hardware and/or software, and the result placed on the system interconnect106. (note: T=N1−N2).

Turning to the prediction unit204as illustrated inFIG. 3, the first logic-AND gate316is electrically connected to the first comparator302and the second comparator304. The first comparator302and the second comparator304are electrically connected to data busses representing numbers. The arrangement of the first logic-AND gate316, the first comparator302, the second comparator304, and the data busses is structured to produce a predetermined output signal from the first logic-AND gate316if (eb+ec−ea)<=(−3) and (ea)>=(emin+1).

The second logic-AND gate318is electrically connected to the third comparator306and the fourth comparator308. The third comparator306and the fourth comparator308are electrically connected to data busses representing numbers. The arrangement of the second logic-AND gate318, the third comparator306, the fourth comparator308, and the data busses is structured to produce a predetermined output signal from the second logic-AND gate318if (−2)<=(eb+ec−ea)<=(0) and (eb+ec)>=(emin+2*N1−2+2*(N1−N2)).

The third logic-AND gate320is electrically connected to the third comparator306and the fifth comparator310. The third comparator306and the fifth comparator310are electrically connected to data busses representing numbers. The arrangement of the third logic-AND gate320, the third comparator306, the fifth comparator310, and the data busses is structured to produce a predetermined output signal from the third logic-AND gate320if (eb+ec−ea)=(1) and (ea)>=(emin+N1−1+(N1−N2)).

The fourth logic-AND gate322is electrically connected to the third comparator306and the sixth comparator312. The third comparator306and the sixth comparator312are electrically connected to data busses representing numbers. The arrangement of the fourth logic-AND gate322, the third comparator306, the sixth comparator312, and the data busses is structured to produce a predetermined output signal from the fourth logic-AND gate322if (2)<=(eb+ec−ea)<=(N1−2) and (ea)>=(emin−1).

The fifth logic-AND gate324is electrically connected to the sixth comparator312and the seventh comparator314. The sixth comparator312and the seventh comparator314are electrically connected to data busses representing numbers. The arrangement of the fifth logic-AND gate324, the sixth comparator312, the seventh comparator314, and the data busses is structured to produce a predetermined output signal from the fifth logic-AND gate324if (N1−1)<=(eb+ec−ea) and (eb+ec)>=(emin+1).

The sixth logic-AND gate326is electrically connected to the second comparator304and the seventh comparator314. The second comparator304and the seventh comparator314are electrically connected to data busses representing numbers. The arrangement of the sixth logic-AND gate326, the second comparator304, the seventh comparator314, and the data busses is structured to produce a predetermined output signal from the sixth logic-AND gate326if (ea)<=(emin−1) and (eb+ec)>=(emin+1).

The output of each of the logic-AND gates316–326is preferably fed into the logic-OR gate328. As a result, the output of the logic-OR gate328predicts the presence of a possible underflow condition or the absence of the underflow condition associated with a floating-point multiply-add operation represented by the numbers (ea, eb, ec, emin, N1, and N2). The prediction produced by the prediction unit204is “pessimistic” in that it predicts that an underflow condition will result in all situations where an underflow condition will result. However, the prediction unit204also predicts that an underflow condition might result in some situations where an underflow condition will not result.

As mentioned above, the prediction unit204may be implemented in hardware or software. A flowchart of a process400for predicting an underflow condition associated with the floating-point multiply-add operation is illustrated inFIG. 4. Preferably, the process400is embodied in a software program which is stored in the memory108and executed by the CPU104in a well known manner. However, some or all of the components of the process400may be performed by another device. Although the process400is described with reference to the flowchart illustrated inFIG. 4, a person of ordinary skill in the art will readily appreciate that many other methods of performing the acts associated with process400may be used. For example, the order of many of the blocks may optionally be changed. In addition, many of the blocks described are optional.

Generally, the process400causes the CPU104to predict an underflow condition associated with a floating-point multiply-add operation in certain circumstances. Again, the prediction is preferably “pessimistic” in that it predicts that an underflow condition might result in all situations where an underflow condition will result, but also predicts that an underflow condition might result in some situations where an underflow condition will not result.

Although the tests may be performed in any order, the process400depicted inFIG. 4begins by causing the CPU104to test if (eb+ec−ea)<=(−3) (block402). If the test in block402produces a true result, the process400causes the CPU104to test if (ea)>=(emin+1) (block404). If both block402and block404produce a true result, the process400causes the CPU104and/or the normalizer206to normalize the operands if necessary (block406) and perform the floating-point multiply-add operation using the floating-point hardware unit208(block408).

If necessary, the process400also causes the CPU104to test if (−2)<=(eb+ec−ea)<=(0) (block410). If the test in block410produces a true result, the process400causes the CPU104to test if (eb+ec)>=(emin+2*N1−2+2*(N1−N2)) (block412). If both block410and block412produce a true result, the process400causes the CPU104and/or the normalizer206to normalize the operands if necessary (block406) and perform the floating-point multiply-add operation using the floating-point hardware unit208(block408).

If necessary, the process400also causes the CPU104to test if (eb+ec−ea)=(1) (block414). If the test in block414produces a true result, the process400causes the CPU104to test if (ea)>=(emin+N1−1+(N1−N2) (block416). If both block414and block416produce a true result, the process400causes the CPU104and/or the normalizer206to normalize the operands if necessary (block406) and perform the floating-point multiply-add operation using the floating-point hardware unit208(block408).

If necessary, the process400also causes the CPU104to test if (2)<=(eb+ec−ea) (block418). If the test in block418produces a true result, the process400causes the CPU104to test if (N1−2) and (ea)>=(emin−1) (block420). If both block418and block420produce a true result, the process400causes the CPU104and/or the normalizer206to normalize the operands if necessary (block406) and perform the floating-point multiply-add operation using the floating-point hardware unit208(block408).

If necessary, the process400also causes the CPU104to test if (N1−1)<=(eb+ec−ea) (block422). If the test in block422produces a true result, the process400causes the CPU104to test if (eb+ec)>=(emin+1) (block424). If both block422and block424produce a true result, the process400causes the CPU104and/or the normalizer206to normalize the operands if necessary (block406) and perform the floating-point multiply-add operation using the floating-point hardware unit208(block408).

If necessary, the process400also causes the CPU104to test if (ea)<=(emin−1) (block426). If the test in block426produces a true result, the process400causes the CPU104to test if (eb+ec)>=(emin+1) (block428). If both block426and block428produce a true result, the process400causes the CPU104and/or the normalizer206to normalize the operands if necessary (block406) and perform the floating-point multiply-add operation using the floating-point hardware unit208(block408).

If an underflow condition is predicted by the prediction unit204(i.e., if the process flow continues to block430), the process400causes the CPU104to perform the floating-point multiply-add operation using the floating-point software unit210(block430).

In summary, persons of ordinary skill in the art will readily appreciate that methods and apparatus for predicting an underflow condition associated with the floating-point multiply-add operation have been provided. Systems implementing the teachings described herein may benefit from reduced computational overhead when performing floating-point multiply-add operations using both hardware and software floating-point units.