Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2000-12-08
2003-12-16
Malzahn, David H. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S210000
Reexamination Certificate
active
06665691
ABSTRACT:
TECHNICAL FIELD OF THE INVENTION
The present invention is directed, in general, to data processors and, more specifically, to a circuit that determines whether or not a number on a data bus is a power of two.
BACKGROUND OF THE INVENTION
The demand for high performance computers and communication devices requires that state-of-the-art digital signal processors (DSPs) and general purpose microprocessors, such as x86 based microprocessors, execute instructions in the minimum amount of time. A number of different approaches have been taken to decrease instruction execution time, thereby increasing processor throughput. One way to increase processor throughput is to use a pipeline architecture in which the processor is divided into separate processing stages that form the pipeline. Instructions are broken down into elemental steps that are executed in different stages in an assembly line fashion.
Pipelining refers to the simultaneous processing of multiple instructions in the pipeline. For example, if a processor executes each instruction in five stages and each stage requires a single clock cycle to perform its function, then five separate instructions can be processed simultaneously in the pipeline, with the processing of one instruction completed during each clock cycle. Hence, the instruction throughput of an N stage pipelined architecture is, in theory, N times greater than the throughput of a non-pipelined architecture that completes only one instruction every N clock cycles. However, the speed improvements provided by pipeline architectures and superpipelining processing are ultimately limited by speed at which the individual stages in the pipeline execute. It is therefore important to minimize the time required to execute each part of an instruction.
Mathematical operations often incur substantial time delays in calculating a value. Counting the number of Logic 1 bits on a data bus is a common operation encountered in computer instruction sets (e.g.,
ST
20
C
2
Core Instruction Set Reference Manual
, SGS-Thomson Microelectronics, November 1997) and as a component function in various digital blocks, such as memory interface units (e.g., N. J. Richardson,
Private Communication
). The function can serve a number of different purposes, including determining the number of valid bits set in some control logic and performing a simple error detection operation. The input to such a function is an n-bit wide bus in which an arbitrary number of bits are set to a Logic 1 value and the other bits are set to a Logic 0 value. The output for this function is a log
2
(n) bit binary number equal to the number of ones on the input bus.
The problem of counting the number of ones on a bus is a simplified analog to the compression tree in a multiplier. Writing the numbers to be added as a vertical row, it is observed that the numbers represent a single column of a multiplier. Designing large multipliers is a well-known problem in digital design (See D. Goldberg,
Appendix A: Computer Arithmetic in Computer Architecture—A Quantitative Approach
, by J. L. Hennessy and D. A. Patterson, 2nd Edition, Morgan Kaufmann Publishers Inc., San Francisco, Calif., 1996. See also I. Koren,
Computer Arithmetic Algorithms
, Prentice Hall, Englewood Cliffs, N.J., 1993).
The procedure for completing the multiplication operation involves two steps. On the first step, the partial products terms are compressed to two terms. This can be done using a number of different compression schemes, including Booth encoding and various trees of full adders, 4:2 carry-save adders (CSA
42
s), 5:3 carry-save adders (CSA
53
s), 7:3 carry-save adders (CSA
73
s), and the like. With two partial products, the final result of the multiplication operation is calculated using a carry-propagate adder (CPA). Again, there is a large literature on the optimum design of adders, including carry-select adders, carry look-ahead adders, and the like.
Because the problem of counting the number of Logic 1 bits on a data bus is such a common operation encountered in computer instruction sets, it is important to minimize the execution time of such an operation. However, as the bus grows larger, more stages of adders are required to perform the count and more propagation delays are encountered.
A related mathematical operation is the detection of numbers equal to power of 2 on a data bus. In binary notation, a number that is a power of 2 contains one and only one Logic 1 bit. All other bits are Logic 0. Therefore, on an 8-bit bus, a power of 2 would appear as a single Logic 1 bit and seven Logic 0 bits. For example, on an 8-bit bus, 8=2
3
=00001000. Similarly, on an 8-bit bus, 128=2
7
=01000000. A circuit that counts the number of Logic 1 bits on an address bus or data bus can also be used to detect powers of two on the bus. Powers of two represent the special case where the count of Logic 1 bits on the bus equals one.
Therefore, there is a need in the art for data processors that minimize the execution time of common mathematical operations. In particular, there is a need for a circuit capable of rapidly determining the number of Logic 1 bits on a bus in a microprocessor, memory interface, or other data processing device. More particularly, there is a need for a Logic 1 bit counting circuit that minimizes the number of stages required to count Logic 1 bits on a data bus. Moreover, there is a need for a circuit capable of rapidly determining that there is one and only one Logic 1 bit on a bus in a microprocessor, memory interface, or other data processing device in order to detect values that are equal to a power of two.
SUMMARY OF THE INVENTION
The present disclosure uses the following abbreviations and definitions to designate adder cells:
1. HA—Half adder. A half adder adds two input bits and provides the result as a two bit output, generally called sum (S) and carry (C). Carry has a weight of 2 and sum has a weight of 1.
2. CSA
32
—Full adder. A full adder that counts three input bits and provides the result (i.e., the number of Logic 1 bit) as a two bit output. The outputs are generally called the sum and carry, with the carry having a weight of 2 and the sum of 1.
3. CSA
42
—4:2 carry-save adder. A 4:2 carry-save adder is a 4-to-2 (4:2) compressor circuit that adds the result of five input bits (four regular bits and a carry-in (CIN) bit) and produces three output bits (a carry bit and a sum bit, and a carry-out (COUT) bit) for the result. The COUT bit has a weight of 2, the carry bit has a weight of 2, and the sum bit has a weight of 1.
4. CSA
53
—5:3 carry-save adder. A 5:3 carry-save adder is a 5-to-3 compressor circuit that adds five input bits, three of which have bit weights of 1 and two of which have bit weights of 2. The three output bits have bit weights of 4, 2 and 1.
5. CSA
73
—7:3 carry-save adder. A 7:3 carry-save adder is a 7-to-3 compressor circuit that counts seven input bits, each having a bit weight of 1. The three outputs bits have bit weights of 4, 2, and 1.
6. CPA—Carry-propagate adder. An adder circuit that gives the binary result of adding two binary numbers.
7. CSA
43
—4:3 carry-save adder. A 4:3 carry-save adder is a 4-to-3 compressor circuit that adds four input bits and provides three outputs (S
2
, S
1
, and S
0
) having bit weights of 4, 2 and 1, respectively. This compressor is not efficient for general purpose multiplication, but is one of a family of compressors, introduced in the present application (along with the CSA
63
and CSA
84
), shown to have advantages when used to count the number of Logic 1 bits on a bus.
8. CSA
63
—6:3 carry-save adder. A 6:3 carry-save adder is a 6-to-3 compressor circuit that adds six equally weighted input bits and produces three output bits with weights of 4, 2, and, 1, respectively.
9. CSA
84
—8:4 carry-save adder. An 8:4 carry-save adder is an 8-to-4 compressor circuit with adds eight equally weighted input bits. The output bits have weights of 8, 4, 2 and 1, respectively.
To address the above-discussed deficiencies of the prior art, it is a primar
Jorgenson Lisa K.
Malzahn David H.
Munck William A.
STMicroelectronics Inc.
LandOfFree
Circuit for detecting numbers equal to a power of two on a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Circuit for detecting numbers equal to a power of two on a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Circuit for detecting numbers equal to a power of two on a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3096514