Method of making apparatus for computing multiple sum of products
View Patent ↗A hardware circuit component for executing multiple sum-of-products operations is manufactured as follows. A set of multiplexed sum-of-products functions of a plurality of operands (a, b, c, . . . ), any one of which functions can be selected in dependence upon a select value (sel) by multiplex operations, is received. The sum-of-products functions are then rearranged in a particular manner. The rearranged set of sum-of-products functions is merged into a single merged sum-of-products function containing one or more multiplexing operations. From this a layout design can be generated, and a hardware circuit component such as an integrated circuit manufactured from the layout design. The step of re-arranging the multiple sum-of-products functions involves aligning the elements of the set of sum-of-products functions in such a manner that the amount of multiplexing in the single merged sum-of-products function is less than in the input set of sum-of-products functions.
1. A method of manufacturing a hardware circuit component for executing multiple sum-of-products operations, characterised by the steps of:
receiving a set of multiplexed sum-of-products functions of a plurality of operands, any one of which functions can be selected in dependence upon a select value by multiplex operations;
re-arranging the sum-of-products functions;
merging the rearranged set of sum-of-products functions into a single merged sum-of-products function containing one or more multiplexing operations;
generating a layout design in dependence upon the single merged sum-of-products function; and
manufacturing a hardware circuit component from the layout design; and
in which the step of re-arranging the multiple sum-of-products functions comprises aligning the elements of the set of sum-of-products functions in such a manner that the amount of multiplexing in the single merged sum-of-products function is less than in the input set of sum-of-products functions.
2. The method according to claim 1 , in which the rearranging step comprises the step of lining up at least one of the operands such as to be in the same position in a plurality of the sum-of-products functions of the received set of multiplexed sum-of-products functions.
3. The method according to claim 1 , in which the rearranging step comprises the step of rendering the number of operands in each term of the sum-of-products substantially uniform.
4. The method according to claim 1 , in which the rearranging step comprises the step of adding one or more additional variables such that each term of each sum-of-products contains the same number of products.
5. The method according to claim 1 , in which the rearranging step includes the step of decomposing the received sum-of-products functions into k binary matrices where k is the number of operands, each matrix having a one to indicate the presence of an operand and a zero to indicate its absence.
6. The method according to claim 1 ,
in which the rearranging and merging steps are optimised by a binary linear program.
7. The method according to claim 1 , in which the merging step includes the step of replacing some or all negative terms in the sum-of-products functions by positive terms.
8. The method according to claim 7 , in which operands of the form −x are replaced with x +1 or with x−1 .
9. The method according to claim 7 , in which the merging step includes generating a sign matrix S, and transforming the sign matrix S into a transformed sign matrix S′ to reflect the changes made in the rearrangement step.
10. A method of generating a layout design for use in the manufacture of a hardware circuit component for executing multiple sum-of-products operations, characterised by the steps of:
receiving a set of multiplexed sum-of-products functions of a plurality of operands, any one of which functions can be selected in dependence upon a select value (ccl) by multiplex operations;
re-arranging the sum-of-products functions;
merging the rearranged set of sum-of-products functions into a single merged sum-of-products function containing one or more multiplexing operations; and
generating a layout design in dependence upon the single merged sum-of-products function; and
in which the step of re-arranging the multiple sum-of-products functions comprises aligning the elements of the set of sum-of-products functions in such a manner that the amount of multiplexing in the single merged sum-of-products function is less than in the input set of sum-of-products functions.