Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2000-04-27
2004-08-17
Ngo, Chuong Dinh (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S205000, C708S501000
Reexamination Certificate
active
06779008
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention generally relates to computer systems, more specifically to a method of determining the number of leading zeros (or ones) in a binary value for computational processing, and particularly for providing an encoded leading-zero count augmented by a constant bias value.
2. Description of Related Art
The basic structure of a conventional computer system includes a central processing unit (CPU) or processor which is connected to several peripheral devices, including input/output (I/O) devices such as a display monitor and keyboard for the user interface, a permanent memory device (such as a hard disk or floppy diskette) for storing the computer's operating system and user programs, and a temporary memory device (such as random-access memory or RAM) that is used by the processor to carry out program instructions. A processor communicates with the peripheral devices by various means, including a bus or a direct channel. A computer system may have many additional components such as serial and parallel ports for connection to, e.g., modems or printers. Those skilled in the art will further appreciate that there are other components that might be used in conjunction with the foregoing; for example, a display adapter connected to the processor might be used to control a video display monitor, and a memory controller may be used as an interface between the temporary memory device and the processor.
A typical processor configuration is shown in FIG.
1
. Processor
1
includes a bus interface unit
2
which controls the flow of data between processor
1
and the remainder of the data-processing system (not shown). Bus interface unit
2
is connected to both a data cache
3
and an instruction cache
4
. Instruction cache
4
supplies instructions to branch unit
5
, which determines what sequence of instructions is appropriate given the contents of general-purpose registers (GPRs)
6
and floating-point registers (FPRs)
7
in processor
1
, the availability of load/store unit
8
, fixed-point execution unit
9
, and floating-point execution unit
10
, and the nature of the instructions themselves. Branch unit
5
forwards the ordered instructions to dispatch unit
11
, which issues the individual instructions to the appropriate execution unit (load/store unit
8
, fixed-point execution unit
9
, or floating-point execution unit
10
).
Fixed-point execution unit
9
reads data from and writes data to general-purpose registers
6
. Floating-point execution unit
10
reads data from and writes data to floating-point registers
7
. Load/store unit
8
reads data from general-purpose registers
6
, or floating-point registers
7
, and writes the data to data cache
3
or to an external memory (not shown) depending on the memory hierarchy and caching protocol employed by the data-processing system, which are beyond the scope of the present invention. Load/store unit
8
also reads data from data cache
3
and writes the data to general-purpose registers
6
and floating-point registers
7
.
A processor can perform arithmetic operations on different types of numbers, or operands. For example, the simplest operations involve integer operands, which are represented using a “fixed-point” notation. Non-integers are typically represented according to a “floating-point” notation. Standard number 754 of the Institute of Electrical and Electronics Engineers (IEEE) sets forth particular formats which are used in most modern computers for floating-point operations. For example, a “single-precision” floating-point number is represented using a 32-bit (one word) field, and a “double-precision” floating-point number is represented using a 64-bit (two-word) field. Most processors handle floating-point operations with a floating-point unit (FPU).
Floating-point notation (which is also referred to as exponential notation), can be used to represent both very large and very small numbers. A floating-point notation has three parts, a mantissa (or significand), an exponent, and a sign (positive or negative). The mantissa specifies the digits of the number, and the exponent specifies the magnitude of the number, i.e., the power of the base which is to be multiplied with the mantissa to generate the number. For example, using base 10, the number 28330000 would be represented as 2833E+4, and the number 0.054565 would be represented as 54565E-6. Since processors use binary values, floating-point numbers in computers use 2 as a base (radix). Thus, a floating-point number may generally be expressed in binary terms according to the form
n
=(−1)
s
×1
.F
×2
E
,
where n is the floating-point number (in base 10), S is the sign of the number (0 for positive or 1 for negative), F is the fractional component of the mantissa (in base 2), and E is the exponent of the radix. In accordance with IEEE standard 754, a single-precision floating-point number uses the 32 bits as follows: the first bit indicates the sign (S), the next eight bits indicate the exponent offset by a bias amount of 127 (E+bias), and the last 23 bits indicate the fraction (F). So, for example, the decimal number ten would be represented by the 32-bit value
0 10000010 01000000000000000000000
as this corresponds to (−1)
0
×1.01
2
×2
130-127
=1.25×2
3
=10.
When a value is expressed in accordance with the foregoing convention, it is said to be normalized, that is, the leading bit in the significand is nonzero, or a “1” in the case of a binary value (as in “1.F”). If the explicit or implicit most significant bit is zero (as in “0.F”), then the number is said to be unnormalized. Unnormalized numbers can easily occur as an output result of a floating-point operation, such as the effective subtraction of one number from another number that is only slightly different in value. The fraction is shifted left (leading zeros are removed from the fraction) and the exponent adjusted accordingly; if the exponent is greater than or equal to E
min
(the minimum exponent value), then the result is said to be normalized. If the exponent is less than E
min
, an underflow has occurred. If the underflow is disabled, the fraction is shifted right (zeros inserted) until the exponent is equal to E
min
. The exponent is replaced with “000” (hexadecimal), and the result is said to be denormalized. For example, two numbers (having the same small exponent E) may have mantissas of 1.010101 and 1.010010, and when the latter number is subtracted from the former, the result is 0.000011, an unnormalized number. If E<5, the final result will be a denormalized number.
The hardware of many conventional computers is adapted to process only normalized numbers. Therefore, when a denormalized number is presented as an output result of a floating-point operation, it must be normalized before further processing of the number can take place. Various techniques are used to normalize the values, generally by removing leading zeros from the fraction and accordingly decrementing the exponent. See U.S. Pat. No. 5,513,362. One technique involves leading zero anticipator (LZA) logic which predicts the number of zeros to remove before the floating-point arithmetic is completed. See IBM Journal of Research and Development, vol. 34, no. 1 (January 1990), pp. 71-77.
Referring to
FIG. 2
, a high-level block diagram of a conventional construction for floating-point execution unit
10
is illustrated. Floating-point execution unit
10
includes three inputs
202
,
204
, and
206
for receiving input operands A, B, and C, respectively, expressed as floating-point numbers. Floating-point execution unit
10
uses these operands to perform a “multiply-add” instruction. The multiply-add instruction executes the arithmetic operation ±[(A×C)±B]. The exponent portions of operands A, B, and C received at inputs
202
,
204
, and
206
are provided to an exponent calculator
208
. The mantissa portions of operands A and C are provided to a multi
Erle Mark
Kelly Michael R.
Bracewell & Patterson L.L.P.
England Anthony V. S.
McBurney Mark E.
Ngo Chuong Dinh
LandOfFree
Method and apparatus for binary leading zero counting with... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for binary leading zero counting with..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for binary leading zero counting with... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3302579