Reconfigurable arithmetic datapath

Abstract

A method and apparatus that combines the same basic hardware elements in several ways to perform a plurality of arithmetic operations over different numbers of operands of different lengths. The allowed options include the multiplication and summing of several operands in a single operation. The reuse of hardware elements is obtained by the use of a multiplication hardware structure together with multiplexer logic (or similar selection logic) at appropriate points in the hardware structure, which allows a minimum of extra hardware and a small number of extra gate delays along any critical path, thereby ensuring that the flexibility to use different operand lengths and numbers of operands incurs only a small penalty in processing speed and/or chip area in a VLSI circuit implementation.

What is claimed is: 
     
       1. An apparatus comprising: a partial product generator to generate sets of partial products, wherein each set of partial products is generated to perform a different operation, at least certain of the different operations involving at least one of a different number of operands and operands of a different numeric precision, wherein said partial product generator generates, responsive to signals indicating the currently selected operation, at least the set of partial products for the currently selected operation;   a carry save adder including a plurality of columns of sufficient height to sum any of the sets of partial products; and   a partial product selector coupled between the partial product generator and the carry save adder, and coupled to receive one or more signals indicating a currently selected operation.   
     
     
       2. The apparatus of claim 1, further comprising: a subtraction unit to selectively subtract different multiplicand inputs and provide the results to said partial product generator.   
     
     
       3. The apparatus of claim 2, wherein said different operations include at least one of a sum of squares of differences, a complex multiply, a multiplication of multiple different pairs of numbers, and a dot product. 
     
     
       4. The apparatus of claim 3, where said different operations also include an operation that performs at least two dot products, where one of the dot products is performed on inputs shifted with respect to the other dot product of the operation. 
     
     
       5. The apparatus of claim 1, wherein said partial product generator comprises: multiplicand preprocessing circuitry; and   a plurality of partial product row generators having inputs coupled to said multiplicand preprocessing circuitry and having outputs coupled to said partial product selector.   
     
     
       6. The apparatus of claim 5, wherein one or more of said plurality of partial product row generators are used to generate partial products in more than one of said sets of partial products. 
     
     
       7. The apparatus of claim 1, wherein: the partial product generator comprises, a plurality of multiplicand pre-multipliers that each receive a multiplicand and that each provide the result of multiplying that multiplicand by a plurality of predetermined numbers, and   a plurality of multiplexers each coupled to receive the output of one of said plurality of multiplicand pre-multipliers as data inputs, and each coupled to receive a part of a multiplier as a control input; and     said partial product selector is coupled to the outputs of said plurality of multiplexers.   
     
     
       8. The apparatus of claim 7, wherein said apparatus is pipelined with stages between said plurality of multiplicand pre-multipliers and said plurality of multiplexers, and between said carry save adder and a carry propagate adder. 
     
     
       9. The apparatus of claim 8, wherein said different operations include at least one of, a complex multiply, a multiplication of multiple different pairs of numbers, and a dot product. 
     
     
       10. The apparatus of claim 7, wherein the output of one or more of said plurality of multiplexers is used as part of the partial products in more than one of said sets of partial products. 
     
     
       11. The apparatus of claim 1, wherein the partial product selector is also coupled to receive as selectable inputs the output of the carry save adder. 
     
     
       12. The apparatus of claim 1, further comprising: a carry propagate adder coupled to the outputs of said carry save adder, wherein the partial product selector is also coupled to receive as selectable inputs the output of the carry propagate adder.   
     
     
       13. An apparatus comprising: multiplicand preprocessing circuitry coupled to receive a multiplicand input representing one or more multiplicands; and   a plurality of partial product row generators having inputs coupled to said multiplicand preprocessing circuitry and having inputs coupled to receive a multiplier input representing one or more multipliers, said plurality of partial product row generators to generate the partial products for at least a dynamically selectable one of a plurality of different operations of which at least certain ones differ in at least one of the number of multiplicands and the numeric precision of the multiplicands;   a plurality of multiplexers having inputs coupled to outputs of said plurality of partial product row generators and coupled to receive a control input identifying the partial products for the currently selected operation as a set of carry save adder inputs; and   a carry save adder including a plurality of columns coupled to outputs of said plurality of multiplexers.   
     
     
       14. The apparatus of claim 13, wherein said apparatus is pipelined with stages between said multiplicand preprocessing circuitry and said plurality of partial product row generators, and between said carry save adder and a carry propagate adder. 
     
     
       15. The apparatus of claim 13, further comprising: an set of subtractors coupled to receive an input;   a set of multiplexers coupled to receive said input, an output of said set of subtractors, and a control signal, said multiplicand preprocessing circuitry coupled to the output of said set of multiplexers to receive the one or more multiplicands.   
     
     
       16. The apparatus of claim 15, wherein at least one of said plurality of different operations is a sum of squares of differences, a complex multiply, a multiplication of multiple different pairs of numbers, and a dot product. 
     
     
       17. The apparatus of claim 13, wherein one or more of said plurality of partial product row generators are used to generate partial products for more than one of said plurality of different operations. 
     
     
       18. The apparatus of claim 13, wherein said partial product row generators generate a plurality of partial products responsive to control signals identifying the currently selected operation, wherein said plurality of partial products includes a first set having the partial products for the currently selected operation and a second set having at least certain partial products for others of the plurality of different operations. 
     
     
       19. The apparatus of claim 13, wherein: the multiplicand preprocessing circuitry comprises a plurality of multiplicand pre-multipliers to each receive a multiplicand and to each provide the result of multiplying that multiplicand by a plurality of predetermined numbers;   each of the plurality of partial product row generators comprise a multiplexer coupled to receive the output of one of said plurality of multiplicand pre-multipliers as data inputs, and to receive a part of a multiplier as a control input; and   each of said plurality of multiplexers is coupled to outputs of the multiplexers in said plurality of partial product row generators.   
     
     
       20. The apparatus of claim 19, wherein at least one of said plurality of different operations is a complex multiply, a multiplication of multiple different pairs of numbers, and a dot product. 
     
     
       21. The apparatus of claim 20, where another of said plurality of different operations is two dot products, where one of the dot products is performed on inputs shifted with respect to the other dot product of the operation. 
     
     
       22. The apparatus of claim 19, further comprising: an set of subtractors coupled to receive an input;   a set of multiplexers coupled to receive said input, an output of said set of subtractors, and a control signal, said multiplicand preprocessing circuitry coupled to the output of said set of multiplexers to receive the one or more multiplicands.   
     
     
       23. The apparatus of claim 19, wherein the output of one or more of the multiplexers in said plurality of partial product row generators is used as part of the partial products in more than one of said plurality of different operations. 
     
     
       24. The apparatus of claim 13, wherein the set of carry save adder inputs is also selected from other inputs into the plurality of multiplexers that include at least one of the one or more multiplicands, the one or more multipliers, the outputs of said carry save adder, or the outputs of a carry propagate adder coupled to said carry save adder. 
     
     
       25. A method comprising the computer implemented steps of: generating sets of partial products in response to an input wherein each set of partial products is generated to perform a different mathematical operation on the input, wherein said step of generating include: for each of one or more multiplicands, generating a plurality of results that represent the result of multiplying that multiplicand by a predetermined set of numbers, and   for each of the one or more multiplicands, selecting from the plurality of results based on one of one or more multipliers;     selecting a currently selected set of partial products from said sets of partial products based upon a currently selected one of said different operations; and   summing said currently selected set of partial products to generate the result of the currently selected one of said different operations.   
     
     
       26. The method of claim 25, wherein the method includes the preliminary step of: subtracting certain parts of the input to generate one or more multiplicands.   
     
     
       27. The method of claim 26, wherein said different operations include at least one sum of squares of differences. 
     
     
       28. The method of claim 25, wherein said step of summing includes the steps of: summing the currently selected set of partial products into a carry and save vectors; and   summing the carry and save vectors.   
     
     
       29. The method of claim 25, wherein a plurality of bits in at least two of said sets of partial products are generated with the same bits of one or more multiplicands and multipliers inputs, and wherein said step of generating also includes the step of generating the at least two of said sets of partial products using a single version of said plurality of bits. 
     
     
       30. The method of claim 25, wherein said step of selecting includes the step of: selecting said currently selected set of partial products also from an output of summing a previously selected set of partial products to generate the result of a previously selected one of said different operations.   
     
     
       31. The method of claim 25, wherein said different operations include at least one a complex multiply, a multiplication of multiple different pairs of numbers, and a dot product. 
     
     
       32. The method of claim 31, where said different operations also include an operation that performs at least two dot products, where one of the dot products is performed on inputs shifted with respect to the other dot product of the operation. 
     
     
       33. The method of claim 25, wherein at least one of the differences between certain of the different operations is the size of one or more multipliers or the size of one or more multiplicands. 
     
     
       34. An apparatus comprising: a partial product generator coupled to receive operand inputs and dynamically configure partial product row generators responsive to control signals to generate at least the partial products for a a currently selected one of a plurality of different mathematical operations on those operand inputs;   a carry save adder including a plurality of columns of sufficient height to sum the partial products for any of said plurality of operations; and   a partial product selector coupled between said partial product generator and said carry save adder to select which of the currently generated partial products are provided to said carry save adder, said partial product selector to select the partial products for the currently selected operation.   
     
     
       35. An apparatus comprising: a partial product generator means for generating partial products for a plurality of distinct mathematical operations, including operations that add or subtract results of multiplying several pairs of input numbers together, said partial product generator means for dynamically configuring partial products row generators for the currently selected mathematical operation responsive to control signals;   a carry save adder means; and   a routing means for routing partial products from said partial product generator means to reduction elements of said carry save adder means so that the summation pattern of the carry save adder is configured according to the currently selected mathematical operation.   
     
     
       36. A method comprising the machine implemented steps of: generating control signals responsive to dynamic selection of one of at least two distinct mathematical operations on input operands, wherein said two operations differ by at least one of the number of multiplicands and the numeric precision of the multiplicands;   dynamically configuring partial products row generators for the currently selected operation responsive to said control signals;   generating a plurality of partial products that includes all partial products for the selected operation and at least certain partial products for the unselected operation;   dynamically routing, responsive to said control signals, all partial products for the selected operation to columns of a carry save adder; and   summing the partial products for the selected operation.