Method and system for large number multiplication

A computer implemented method of operating a multiplication circuit to compute the product of two operands (hereby identified as A and B), at least one of which is wider than the multiplication circuit, where operand A comprises one or more contiguous ordered word-wide operand segments characterized by weight j and identified as Aj, where j is an integer from 0 to k and operad B comprises one or more contiguous ordered word-wide operand segments characterized by weight and identified as Bi, where i is an integer from 0 to m, and a word is a specified number of bits (n), and where the multiplication circuit executes a matrix of word-wide operand segment pair multiplication operations, the matrix comprising m+1 rows and k+m+2 columns, each row having a weight x where x is an integer from 0 to m and each column having a weight y where y is an integer from 0 to (k+m+1), the multiplication circuit having access to a memory, the method comprising:

• for each pair of rows in the matrix, the rows having weights x1 and x2, reading a pair of B operand segments from the memory, where the weight of a first B operand segment (Bx1) is x1 and the weight of a second B operand segment (B2) is x2, and further performing the following:
• (a) for a column having a weight y, reading an Aj operand segment from the memory identified for the column as Aj where the weight j1 together with the weight (x1) of the first B operand segment equals the weight y of the column;
• (b) for a column having a weight y, reading an intermediate column result (Inty) if any, an intermediate column result being a previously determined result for the column corresponding to a different pair or pairs of rows;
• (c) multiplying the Aj1 operand segment by the first B operand segment (Bx1);
• (d) if j>0, then multiplying a previously read Aj operand segment stored in a cache (Aj0) by the second B operand segment (Bx2), where the weight (j0) of the previously read Aj0 operand segment together with the weight (x2) of the second B operand segment equals the weight y of the column;
• (e) accumulating the results of the one or two multiplication operations and the intermediate column result Inty (if any) and a carry value Cy−1 (if any) for a previously calculated column having a weight y−1 to provide an accumulation result;
• (f) if there are no further rows to calculate for the column, then writing the least significant n bits of the accumulation result to the memory as a final column result Ry, else writing the least significant n bits of the accumulation result to the memory as an intermediate column result Inty;
• and
• (g) incrementing j by 1 and reiterating the steps (a) through (g) until incrementing j by 1 will exceed a value of k;
• where the steps (a) through (d) do not have to be performed in the order shown.

A computer program product, tangibly stored on a computer-readable medium, for operating a multiplication circuit to compute the product of two operands (hereby identified as A and B), at least one of which is wider than the multiplication circuit, where operand A comprises one or more contiguous ordered word-wide operand segments characterized by weight j and identified as Aj, where j is an integer from 0 to k and operand B comprises one or more contiguous ordered word-wide operand segments characterized by weight i and identified as Bj, where i is an integer from 0 to m, and a word is a specified number of bits (n), and where the multiplication circuit executes a matrix of word-wide operand segment pair multiplication operations, the matrix comprising m+1 rows and k+m+2 columns, each row having a weight x where x is an integer from 0 to m and each column having a weight y where y is an integer from 0 to (k+m+1), the multiplication circuit having access to a memory, comprising instructions operable to cause a programmable processor to:

• performing multiplication operations on a pair of rows at one time, where for each pair of rows a pair of Bi word-wide operand segments are read from the memory which Bi segments have weights (i) that correspond to the weights (x) of the rows in the pair and word-wide operand segment pair multiplication operations (Aj*Bi) are iteratively performed for each of k+2 columns where for a cell that corresponds to a row with weight x and a column with weighty the word-wide operand segment pair multiplication operation comprises Aj multiplied by Bi where weight j is equal to (y−x) and where weight i is equal to x, such that for each column in the matrix a maximum of two additional memory read operations in addition to reading the pair of Bi word-wide operand segments from memory and one memory write operation is required.

A system for computing the product of two operands (hereby identified as A and B), at least one of which is wider than a width associated with the multiplication circuit, where operand A comprises one or more contiguous ordered word-wide operand segments characterized by weight j and identified as Aj, where j is an integer from 0 to k and operand B comprises one or more contiguous ordered word-wide operand segments characterized by weight i and identified as Bi, where i is an integer from 0 to m, and a word is a specified number of bits (n), and where the system executes a matrix of word-wide operand segment pair multiplication operations, the matrix comprising m+1 rows and k+m+2 columns, each row having a weight x where x is an integer from 0 to m and each column having a weight y where y is an integer from 0 to (k+m+1), the multiplication circuit having access to a memory, the system comprising:

• a multiplier including one or more inputs configured to receive word-wide operand segments to be multiplied to form a two-word-wide intermediate product and configured to perform a multiplication operation of a pair of word-wide operand segments;
• an accumulator including:
• one or more inputs configured to receive the two-word-wide intermediate product from the multiplier, an intermediate column result from a cache and a carry value from the cache;
• one or more outputs configured to provide the least significant n bits of an accumulation of the two-word-wide intermediate product, intermediate column result and carry value to the cache as an intermediate or final column result and further configured to provide the upper bits of the said accumulation to the cache as a carry value;
• where said accumulator is configured to perform an accumulation operation of the inputs received therein;
• a cache configured to receive and transmit word-wide operand segments from and to a memory and connected to the multiplier and the accumulator to supply inputs thereto and receive outputs therefrom;
• and
• an operations sequencer configured to control the cache's accessing of the memory and to control the sequence of multiply and accumulate operations performed by the multiplier and accumulator respectively;
• wherein said sequences are defined to perform multiplication operations on a pair of rows at one time, where for each pair of rows a pair of Bi word-wide operand segments are read from the memory into the cache which Bi segments have weights (i) that correspond to the weights (x) of the rows in the pair and word-wide operand segment pair multiplication operations (Aj*Bi) are iteratively performed by the multiplier for each of k+2 columns where for a cell that correspond to a row with weight x and a column with weight y the word-wide operand segment pair multiplication operation comprises Aj multiplied by Bi where weight j is equal to (y−x) and where weight i is equal to x, such that for each column in the matrix a maximum of two memory read operations in addition to reading the pair Bj word-wide operand segments from memory and one memory write operation to and from the cache is required.

A computer implemented method to compute the product of two operands (hereby identified as A and B), at least one of which is wider than a width associated with a multiplication circuit performing the multiplication, the method comprising:

• creating a matrix of word-wide operand segment pair multiplication operations, the matrix comprising m+1 rows and k+m+2 columns, each row having a weight x where x is an integer from 0 to m and each column having a weight y where y is an integer from 0 to (k+m+1), where operand A comprises one or more contiguous ordered word-wide operand segments characterized by weight j and identified as Aj, where j is an integer from 0 to k and operand B comprises one or more contiguous ordered word-wide operand segments characterized by weight i and identified as Bi, where i is an integer from 0 to m, and a word is a specified number of bits (n);
• and
• performing multiplication operations on a pair of rows at one time, where for each pair of rows a pair of Bi word-wide operand segments are read from the memory which Bi segments have weights (i) that correspond to the weights (x) of the rows in the pair and word-wide operand segment pair multiplication operations (Aj*Bi) are iteratively performed for each of k+2 columns where for a cell that corresponds to a row with weight x and a column with weight y the word-wide operand segment pair multiplication operation comprises Aj multiplied by Bi where weight j is equal to (y−x) and where weight i is equal to x, such that for each column in the matrix a maximum of two memory read operations in addition to reading the pair of Bi word-wide operand segments from memory and one memory write operation is required.

A system for operating a multiplication circuit to compute the product of two operands (hereby identified a A and B), at least one of which is wider than the multiplication circuit, where operand A comprises one or more contiguous ordered word-wide operand segments characterized by weight j and identified as Aj, where j is an integer from 0 to k and operand B comprises one or more contiguous ordered word-wide operand segments characterized by weight i and identified as Bi, where i is an integer from 0 to m, and a word is a specified number of bits (n), and where the multiplication circuit executes a matrix of word-wide operand segment pair multiplication operations, the matrix comprising m+1 rows and k+m+2 columns, each row having a weight x where x is an integer from 0 to m and each column having a weight y where y is an integer from 0 to (k+m+1), the multiplication circuit having access to a memory, comprising:

• a means to perform multiplication operations on a pair of rows at one time, where for each pair of rows a pair of Bi word-wide operand segments are read from the memory which Bi segments have weights (i) that correspond to the weights (x) of the rows in the pair and word-wide operand segment pair multiplication operations (Aj*Bi) are iteratively performed for each of k+2 columns where for a cell that corresponds to a row with weight x and a column with weight y the word-wide operand segment pair multiplication operation comprises Aj multiplied by Bi where weight j is equal to (y−x) and where weight i is equal to x, such that for each column in the matrix a maximum of two memory read operations in addition to reading the pair of Bi word-wide operand segments from memory and one memory write operation is required.