Fast pipelined matrix multiplier

A matrix multiplication circuit comprising:

• a first stage for multiplying a first matrix X having elements x.sub.ij, i=1 . . . I, j=1 . . . J with a second matrix C.sup.t having elements c.sup.t.sub.jk, k=1 . . . K, said first stage comprising:
• a first plurality of pipeline circuits which operate in parallel, each pipeline circuit for sequentially outputting the elements:
• ##EQU9## of an intermediate matrix for a particular value of k;
• and a second stage for receiving the elements y.sub.ik as said elements y.sub.ik are output by the first stage and for multiplying said elements y.sub.ik with a third matrix C having elements C.sub.li, said second stage comprising:
• a second plurality of pipeline circuits which operate in parallel, each pipeline circuit of the second stage for sequentially outputting the products c.sub.li y.sub.ik for a particular value k;
• and
• associated accumulator means, each accumulator means for selectively accumulating products c.sub.li y.sub.ik for particular values of l from the associated pipeline circuit so that each accumulator means generates the sum ##EQU10## wherein each pipeline circuit of the first stage, for multiplying the elements of a first sequence x.sub.11, x.sub.12, . . . , z.sub.11, x.sub.21, x.sub.22, . . . x.sub.21, . . . ,x.sub.11 with the elements of a second sequence comprising I repetitions of the sequence:
• c.sup.t.sub.1k, c.sup.t.sub.2k, . . . , c.sup.t.sub.Jk for a particular value of k, comprises:
• a first processing element simultaneously receiving two inputs per cycle comprising the first bit of each element of said first sequence and each element of said second sequence, said first processing element outputting the products of said two inputs thereto, one per cycle;
• a plurality of processing elements labeled, 2, . . . , m, . . . , M, where M is the number of bits of each element of said first sequence, the m.sup.th processing element receiving two inputs per cycle comprising the m.sup.th bit of an element of said first sequence and a corresponding element of said second sequence, said m.sup.th processing element outputting the sum of the product of said two inputs thereto and the sum of the m-1.sup.th processing element.

A matrix multiplication circuit comprising:

• a first stage for multiplying a first matrix X having elements x.sub.ij, i=1 . . . I, j=1 . . . J with a second matrix C.sub.t having elements c.sup.t.sub.jk, k=1 . . . K, said first stage comprising:
• a first plurality of pipeline circuits which operate in parallel, each pipeline circuit for sequentially outputting the elements:
• ##EQU11## of an intermediate matrix for a particular value of k;
• and a second stage for receiving the elements y.sub.ik as said elements y.sub.ik are output by the first stage for multiplying said elements y.sub.ik with a third matrix C having elements C.sub.li, said second stage comprising:
• a second plurality of pipeline circuits which operate in parallel, each pipeline circuit of the second stage for sequentially outputting the products c.sub.li y.sub.ik for a particular value k;
• and
• associated accumulator means, each accumulator means for selectively accumulating products c.sub.li y.sub.ik for particular values of l from the associated pipeline circuit so that each accumulator means generates the sum ##EQU12## wherein each pipeline circuit of the second stage, for multiplying the elements of a first sequence c.sub.11, c.sub.21, . . . , c.sub.L1, c.sub.12, c.sub.22, . . . , c.sub.L2, . . . , c.sub.L1 with the elements of second sequence comprising L repetitions of each element of the sequence:
• y.sub.1k, y.sub.2k, . . . , y.sub.1k for a particular value of k, comprises:
• a first processing element simultaneously receiving two inputs per cycle comprising the first bit of each element of said first sequence and each element of said second sequence, said first processing element outputting the products of said two inputs thereto, one per cycle;
• a plurality of processing elements labeled 2, . . . , p, . . . , p, where p is the number of bits of each element of said first sequence, the p.sup.th processing element receiving two inputs per cycle comprising the p.sup.th bit of each element of said first sequence and each element of said second sequence, said p.sup.th processing element outputting the sum of the product of said two inputs thereto and the sum of the p-1.sup.th processing element.

A method for multiplying three matrices comprising the steps of:

• in a first multiplication circuit stage, multiplying a first matrix X having elements x.sub.ij i= 1 . . . I, j=1 . . . J with a second matrix A having elements a.sub.jk, k=1 . . . K said multiplication step of said first stage comprising:
• in a first plurality of pipeline circuits, sequentially generating, in each pipeline circuit simultaneously, the elements:
• ##EQU13## of an intermediate product matrix Y=X.multidot.A for a particular value of k;
• and
• in a second multiplication circuit stage, receiving the elements y.sub.ik as said elements y.sub.ik are generated by the first stage and multiplying said elements y.sub.ik with a third matrix C having elements c.sub.li, said multiplication step of said second stage comprising the steps of:
• in a second plurality of pipeline circuits, sequentially generating the products c.sub.li y.sub.ik for a particular value k from each pipeline circuit simultaneously;
• and
• in associated accumulator means, selectively accumulating said products c.sub.li y.sub.ik for particular values of l from the associated pipeline circuit so that each accumulator means generates the elements ##EQU14## of a product matrix Z=C.multidot.Y.