CmpSci 535 Discussion 7

Number Representations

As we saw in the discussion of Boolean logic, we can perform arithmetic on binary numbers using combinations of logical operations. Now we'll take a somewhat closer look at the specifics of arithmetic operations.

Recall from assembly language that binary numbers have a power of two associated with each of their digits. If we use this to number the digits as we write them down, we get a number scheme in which a 32-bit number has bit 31 on the left and bit 0 on the right.

In decimal notation we represent a negative number by writing a minus in front of a positive number. With binary numbers we do not have the convenience of such a notation, although we could declare one bit (say bit 31) to be a sign bit and the rest of the number to be the quantity. Such a notation is called signed-magnitude representation. Suppose we were using a four-bit word. Then 6 would be represented as

0110

and -6 as

1110

This is easy to read, but it has the disadvantage that if we add the numbers in this form, we do not get 0.

0110

1110

------

0100 with a 1 overflow.

so the result of 6 + (-6) appears to be 4 with overflow.

We don't particularly care about readability of binary numbers in the computer because we rarely look at them anyway (we write software to translate them into decimal notation). So we should really be more concerned with what representation is most useful for the computer. A system that allows us to use an adder to sum positive and negative numbers will simplify the design of the ALU. There are two such systems of representation and they both depend on the complement of a number.

The complement of a number in a given base can be defined as the difference between each digit of the number and the maximum digit value for the base. Thus, in base 10 the complement of 26 would be 73, because the maximum digit value is 9. In base two, the complement is easy to compute -- it is just the bitwise inverse of a number. Thus the complement of 11010 would be 00101.

This scheme is known as ones-complement and was used on machines designed by Seymour Cray at Control Data Corporation. They used ones complement because it made negating a number as fast and simple as passing it through a word-wide bank of inverters. It is also a symmetric number system in that, for any given word size, there are an equal number of positive and negative numbers. The problem is that one of those numbers is -0. So, a ones complement machine has to recognize the presence of all 1's in a word (with a giant AND gate) and invert the bits again whenever -0 appears. In ones complement, the above addition would be represented by:

0110

1001

-----

1111 (-0) => 0000

Similarly 26 + 73 = 99 (-0) => 0

We can avoid the problem of -0 by using two's complement, in which we add 1 to the complement of a number to negate it.

0110

1010

-----

10000 => 0000 with overflow

The 10's complement of 26 would be 74.

So 26 + 74 = 100 => 0 with overflow

Thus we never have negative 0 to worry about, but we do have a minor asymmetry -- there is one more negative number than positive number in our system. The unique 0 is essentially taken from the positive side of the number line in a two's complement system.

As we saw before, we can perform the +1 part of a two's complement by using the carry-in to the low-order bit of an adder, so there is almost no cost associated with this operation.

In two's complement, a high-order bit of 1 always signifies a negative number (in ones complement, we have to check for -0 when the high order bit is 1). Thus, the high order bit is usually called the sign bit.

If we need to convert a two's complement number to a larger word size, we simply extend the sign bit into the high order digits to produce a number of the correct form. That is, if the number is positive, all of the higher order bits in the wider word will be 0. If it is negative, they are all 1.

Shifting

Shifting a word right or left (which is equivalent to multiplying or dividing by a power of 2) is used in multiplication and division and also to align data on byte or word boundaries. It can be implemented in several ways. The least expensive is with a shift register.

Basically a chain of D flip-flops is arranged with gates that connect their inputs to an external source or to each other.

We can make this bidirectional by adding a third input that takes its data from the flip-flop on the other side.

The drawback of this approach is that it requires each shift on n places to take n clock cycles. We can instead use a logic circuit that selects any of the input 32 bits to go to a given output bit, with all of the other output bits receiving a parallel selection.

For example, a shift of three to the right would establish the following pattern of connections:

Here we see one bit of a 32-bit shifter of this type:

Each bit would have this same arrangement of 32 AND gates feeding a32-bit OR gate. What is not as obvious from the logic diagram is that this results in 32 x 32 =1024 wires leading from the inputs to the AND gates. An actual implementation would use several stages of gates to avoid the 32-input OR gate and the requirement for the inputs to drive 32 AND gates at once. This arrangement is clearly more expensive but it can compute any shift in just one cycle (or even less, since it is not a clocked circuit). It is called a barrel shifter. An alternative to supporting every shift distance, which is used for shifters that do data alignment (for example, loading a specific byte into the low-order byte of a register) is to provide just a few of the possible shift distances as required by the particular application.

Carry Lookahead Addition

The book does a nice job of showing how an adder/subtractor/AND/OR/less than can be built so it won't be repeated here. Of particular interest is to note how zero detection and overflow are detected in Figure 4.17.

We'll just briefly go over the operation of the carry lookahead since we've discussed the concept before. The basic idea behind its implementation is that some clever algebra has been used to simplify the logic functions by factoring out some common terms in each of the carry expressions.

These terms depend only on the bits being input at a given position -- not on any of the other positions. They are called

generate = A AND B (because if A and B are both 1, then a carry is generated regardless of the carry in to that position.

propagate = A OR B (because if either is a 1, then a carry in will be propagated to the next stage (and if they are both 1, the carry in doesn't matter -- it is an inclusive propagate)

So we have

c1 = g0 + (p0 c0) that is, we get a carry if we have either a generate, or a propagate with a carry in

c2 = g1 + (p1 c1) = g1 + (p1 g0) + (p1 p0 c0)

c3 = g2 + (p2 c2) = g2 + (p2 g1) + p2 p1 g0) + (p2 p1 p0 c0)

c4 = g3 + (p3 c3) = g3 + (p3 g2) + (p3 p2 g1) + (p3 p2 p1 g0) + (p3 p2 p1 p0 c0)

As you can see, we can build each of the carry out computations from a circuit with just two stages of gates, but the n-th bit contains a circuit with an n+1 input OR gate and n AND gates who's input counts range from 2 to n+1.

For an 8-bit adder this works OK, but for 32 bits the fan-in is too high. So a hierarchical scheme is used instead -- it will usually consist of 4 or 8-bit carry lookahead adders and these feed another level of lookahead circuitry that produces the carry in to each of the blocks at the same time.

Multiplication

The basic idea behind multiplication is that we shift (leftwards) and add the multiplicand to a result register repeatedly. At each shift position we look at a corresponding digit of the multiplier and if it is 0 we skip the addition and if it is 1 we carry out the addition. The multiplier is thus placed in a register that shifts right, with the least significant bit being used to control the adder. Thus the multiplicand and the result are stored in double-length registers (the multiplicand to enable the shifting, and the result to accommodate the fact that it naturally grows to double the length as a result of multiplication).

More clever schemes recognize that as the data shifts out of the multiplier, space is left in its register that we can take advantage of to avoid having to use a double-length register for the result. So some of the bits recirculate to fill the space being vacated by the departing bits of the multiplier as they shift across the register.

Booth's algorithm is another approach that tries to speed up multiplication by taking advantage of the patterns of bits in the operands. The algorithm notes that if the multiplier contains a string of ones (for example)

0000111111110000

that the partial sum that results from this string is equal to the multiplicand times a 1 in the next higher bit minus itself times the 1 in the lowest order bit of the string.

That is 0000111111110000 X 1 = 0001000000000000 – 0000000000010000.

So if a number contains long strings of 1 bits, we can avoid all of the intermediate shifts and adds and replace them by one add and one subtract. The problem is that this algorithm is actually slower for patterns like

0101010101010101

where an add and subtract would be done for each 1 in the multiplier.

We can build a really fast multiplier by creating a chain of adders that each take the multiplicand as one input (controlled by the appropriate bit of the multiplier) and take the output of the preceding stage as the other input.

This scheme produces a result in the time that it takes the data to propagate through all of the adder stages. It has as many adders as there are bits in the multiplier, and the adders are as wide as the number of bits in the multiplicand. Thus, for N-bit words, N-squared gates are required for a ripple carry adder based circuit, and a CLA based circuit is even more expensive.

One point to note about this approach is that if we put a register between each pair of adders, and clock the data through the register, then we can start a new multiply operation into this circuit with each clock cycle. After N clock ticks the first result emerges and subsequent multiplies emerge on each additional tick. Such an approach is called a pipelined multiplier and is useful in machines that are doing vector operations.

Wallace proposed an alternative scheme that uses fewer gates. He recognized that we don't have to complete all of the carry operations at each stage before passing a value on to the next stage. As long as the carries get added in before the final result is produced, we will have a valid sum of all of the partial products.

Thus, in Wallace's scheme, all of the partial products are generated in parallel by gating N copies of the N-bit the multiplicand by the bits of the multiplier into the inputs of a tree of "pseudo-adders". (Much as in the diagram above, except that the pipelined stages are replaced by the adder tree).

Each pseudo-adder is a bank of full adder circuits. But instead of propagating the carry output to an adjacent bit within the pseudo-adder, the carry is simply another output number:

A pseudo-adder block can be treated as a 3-input 2-output combinational circuit that produces two sums from three inputs. If we add the two sums together, then we get the actual binary sum of the three inputs.

Wallace showed how to construct a tree of these adders. The following diagram shows how 20 partial products could be summed together with pseudo-adders. At the final stage, a carry lookahead adder is used to sum the last carry and sum output pair.

Wallace tree adders can be constructed from larger adder blocks that take more inputs and produce more outputs -- all that is required of the outputs of a pseudo adder is that if you sum them up you get the sum of the inputs. Thus, for example, one might find a convenient Boolean function that takes 15 inputs and generates 4 outputs for which the sum is the sum of the 15 inputs.

Division

The same basic approach can be used for division. Start with the dividend and divisor aligned. Shift the dividend left and subtract the divisor. If the result is positive, then the quotient gets a 1 and the remainder replaces the dividend. If the result is negative, then the quotient gets a 0 and the dividend is restored except that it is still shifted by one.

Given a fast multiplier, however, there are faster methods that can be applied based on a Newton-Raphson iterative solver. Flynn showed that a first-order Newton-Raphson formula can start with a 4-bit approximation and in just 3 iterations achieve 32-bit precision. Each of the iterations takes 2 multiplies and some shifts and complements.

The initial value can be obtained with a table lookup that uses the high order bits of the divisor as the address and produces the 4-bit approximation to the quotient. Thus, division of this form takes only about 6 times as long as multiplication. If the multiplier is like the Wallace Tree, it may be several times faster than the shift-and-subtract approach.

Elementary Functions

Computing sines, cosines, etc. in hardware, is actually included in many floating point units. One popular method that involves only simple hardware (and is used, for example, in most calculators) is the CORDIC (COordinate Rotation DIgital Computer) approach developed by Volder.

He observed that if one rotates a vector by a decreasing (in magnitude) series of positive or negative angles that the vector eventually converges on a desired angle. Further, if the angles are selected appropriately and at each stage either a positive or negative version of the rotation is applied (whichever gives the closer result) that the length of the resultant vector is a constant. Thus, if the final X and Y values are multiplied by an appropriate pair of constants to change the length of the vector into a unit, then as we know from trigonometry, the X and Y values of the unit vector at that angle are the values of the sine and cosine.

The CORDIC method uses a table of constants. For each iteration it compares the current angle to the desired angle, and either adds or subtracts the constants for that iteration to the angle, X, and Y values. The precision of the result increases one digit per iteration. At the end of this series of add/subtract operations, one multiply is required to produce the desired function.

Floating Point

As you probably recall from assembly language programming, the basic concept of floating point representation is that it provides a portion of a word that represents a mantissa, part that represents an exponent, and one bit for a sign. The sign of the exponent is usually subsumed by a bias value that must be subtracted from the stored value to obtain the correct exponent value. The advantage of the bias is that it makes the exponents all positive which saves an explicit bit for the sign and also means that the arithmetic (such as comparisons) does not have to treat positive and negative exponents differently. However, after adding two exponents (as in multiplication), the extra bias amount must be subtracted. Biased exponent representations also have the advantage that zero is represented by a word of all zeros.

The mantissa for a floating point number is usually normalized -- that is, it is shifted left until the first one bit is in the high order position. The exponent is adjusted by a corresponding amount to compensate for the shifting. Because a normalized representation always has a one in the leading position, we need not represent it explicitly. Thus, one more bit can be used to extend the precision of the mantissa.

Floating Point Operations

Addition involves aligning the mantissas of the two numbers (determining the difference between their exponents and then shifting the smaller of the two numbers right by that many positions, with the implicit one made explicit), then adding the mantissas and if there is an overflow renormalizing by shifting the result one to the right.

Subtraction is the same as addition except that one mantissa is subtracted from the other after alignment, and the renormalization may involve an arbitrary left shift of the result.

Multiplication does not require the mantissas to be aligned. They are multiplied, the exponents are added, and the result is renormalized if necessary (a shift of one position). Of course, the result is double the size of the original values, so it must be shortened either through truncation or rounding. (The other operations require this as well whenever a value is renormalized and bits of precision are lost.)

Division similarly involves no prealignment of the mantissas. When the division is performed, one exponent is subtracted from the other. Unlike multiplication, the mantissa result of the division can require arbitrary shifting to be renormalized.

IEEE Floating Point Format

The majority of computer systems today use the IEEE 754 standard that was first adopted in 1985. The adoption of this standard was a rare show of apparent cooperation among computer manufacturers. However, it was partly a matter of pragmatics (handling floating point properly is complicated, and adopting the standard saves both design cost and potentially embarrassing errors), partly competition (it became a positive marketing point to be able to claim IEEE compatibility), partly the effect that the microprocessor generation of manufacturers had a clean slate to start from (most of them did not have existing mainframe-based standards -- those that did were the ones like DEC and IBM who entered the microprocessor business late), and partly that the manufacturers uniformly underestimated the difficulty of implementing the IEEE standard (so they publicly jumped onto the bandwagon before they knew how much it would really cost).

Because the standard is well designed, its widespread adoption has been a very positive experience for the software community. However, even 15 years after it was introduced, there was very little language support to take advantage of the more sophisticated features of the standard, and some of the features are either unimplemented or very costly to employ on some machines.

The standard defines four formats for floating point numbers, of which two are commonly used (single and double). In single-precision numbers there is a one-bit sign, 23 bits in the mantissa (an implicit 24th bit is the leading 1 in all mantissas, which isn't stored), and the 8-bit exponent ranges from -126 to 127 with a bias of 127. In double-precision numbers there is the one-bit sign, 53 bits of precision in the mantissa and the exponent ranges from -1022 to 1023 with a bias of 1023.

The bias is a number that must be subtracted from the stored value of the exponent to get its value for purposes of computation. Thus, the minimum value that can appear in an exponent field of a proper single-precision floating point number is 1 and the maximum value is 254. This leaves 0 and 255 for representing special cases. In double-precision, the exponent can be 1 through 2046, with 0 and 2047 reserved for special cases.

The other two formats are "extended" versions of the two common representations. They assume that a machine will devote an entire word (32 or 64 bits) to the mantissa and at least 10 (single) or 14 (double) bits to the exponent field. The extended formats do not have defined biases.

Special Case Numbers

When the exponent of an IEEE FP number is all ones (255 or 1023) and the mantissa is all zeroes the number is explicitly equal to infinity (+ or -, depending on the sign bit). The standard requires arithmetic such as division by 0 to produce infinity as a result, and inversely, division by infinity to produce 0. Overflow can also produce an infinite result.

If the exponent is all ones and the mantissa is nonzero, then the value is called "Not a Number" or NaN. The NaN values can be used to represent results such as the square root of a negative. Arithmetic on NaN values should also produce NaN values as output so that if an improper floating point value enters a string of calculations, it cannot result in a valid floating point result.

When the exponent is zero, then the mantissa represents an unnormalized or "subnormal" number. These are numbers that are smaller than the number 1 x 2^-126. That is, the implicit leading 1 disappears and the number of significant digits in the mantissa can decrease to fewer than 24 bits. These numbers are useful when we consider that any two numbers with exponents of -126 will differ by an amount that is smaller than we can otherwise represent. So if we try to compare the numbers by subtracting them, we get an unnormalized number. In some systems, unnormalized numbers are not allowed and the difference would simply be zero. Thus, it would be possible to have two very small but different numbers that appear to be equal when we compare them.

While everyone agrees that having subnormal numbers enhances the accuracy of calculations and reduces programming effort, hardware designers find them to be a very difficult part of the standard to implement. Subnormals are a special case that occur relatively rarely, but they also require that all computations make the checks for the special combination of a zero exponent and a nonzero mantissa and then turn off the usual prealignment and renormalization hardware appropriately. Thus, implementing subnormals can both increase the cost of a floating point unit and result in slower computation overall.

In some processors, for example the PowerPC, the programmer can disable the use of subnormal numbers. In the PowerPC, when subnormals are disabled, a subnormal result generates a normalized value and an exception is raised so that the software can handle the underflow. Of course, the exception can be ignored if speed is more desirable than accuracy. When subnormals are enabled, no underflow exception is raised and the FPU takes care of all of the special handling.

Rounding

The IEEE standard has four different rounding modes. The usual mode is to round to the nearest value, with a number that falls midway between two others being rounded to the nearest value with an even (zero) low-order digit. The other modes are round toward zero, round toward plus infinity, and round toward minus infinity.

Rounding is based on two additional bits of precision that are kept in intermediate stages of a floating point calculation. These are the guard and round bits. To see why two bits are needed, consider that adding two numbers can require an extra digit in order to know how to round them (as when one value is shifted by one position with respect to the other) and that the result of such an addition can also produce a carry out of the high order place. Thus, we need to be able to store a result that is two bits longer than normal.

One problem with the "round to even" mode is that it complicates the rounding process. For example, the result of a multiply might end with a long string of zeros and then a one. Without the one, the result would be rounded down to the nearest even value. But with the one, the result does not fall half way between the two rounded possibilities -- it actually falls closer to the odd number just above. Thus, the FPU has to keep track of whether there are any one bits beyond the guard and round -- it does this with a bit called the "sticky bit" because it is often implemented by watching the low order bits as they are shifted out to the right during normalization, and sticking to a one if any one bits are seen.

Back to Chip Weems' home page.

Back to courses index page.

Back to Computer Science Department home page.