Systolic array for multidimensional matrix computations

Abstract

A multidimensional systolic array processor uses a multidimensional array of systolically coupled processing elements to perform matrix-vector multiplication of matrix and vector signal sets. A two-dimensional array uses a P×Q matrix (P rows and Q columns) of processing elements which are coupled to systolically process the signals, e.g. via multiplication and accumulation. The processing elements are coupled both row-to-row and column-to-column for pipeline processing within each row and each column, i.e. multidimensional pipelining, thereby increasing processing parallelism and speed. Interconnectivity of the processing elements is minimized by forming separate column and row signal subsets of the vector signal set which are coupled simultaneously to each processing element in the first row and first column, respectively. Size of the processing elements is minimized by reducing local storage of matrix signal subsets within each processing element. Separate column and row signal subsets of the matrix signal set are formed and coupled into each processing element of the first row and first column, respectively. As the matrix column and row signal subsets are systolically processed and transferred row-to-row and column-to-column, respectively, each signal subset is reduced in size by one signal, thereby requiring the transfer and temporary local storage of successively smaller matrix signal subsets. A three-dimensional processor uses a P×Q×T array (T planes of P rows and Q columns) of processing elements which are coupled plane-to-plane-to-plane.

What is claimed is: 
     
       1. A multidimensional systolic array processor comprising: a signal processing array systolically coupled in a PxQ matrix having P rows and Q columns of processing means N A ,B, where Aε{1,2,3, . . . ,P} and Bε{1,2,3, . . . ,Q}, to systolically process a matrix signal set W having a plurality of matrix signals W I ,J and a vector signal set V having a plurality of vector signals V J , where Iε{1,2,3, . . . M} and Jε{1,2,3, . . . ,K}, said matrix signal set W representing a matrix parameter set selectively represented as an MxK matrix having M rows and K columns f parameters, and said vector signal set V representing a vector element vector having K parameters, wherein each processing means N 1 ,B in a first one of said rows of processing means N A ,B is coupled to receive a vector column signal subset V C  of said vector signal set V, wherein said vector column signal subset V C  includes a first subplurality of said plurality of vector signals V J  and where   V.sub.C =V.sub.Y,Z =V.sub.J ##EQU8##       
     
     
       2. An array processor as recited in claim 1, wherein each processing means N A ,1 in a first one of said columns of processing means N A ,B is coupled to receive a vector row signal subset V R  of said vector signal set V, wherein said vector row signal subset V R  includes a second subplurality of said plurality of vector signals V J  and where   V.sub.R =V.sub.Y,Z =V.sub.J ##EQU9##     
     
     
       3. An array processor as recited in claim 1, wherein said systolic coupling of said processing means N A ,B comprises individually coupling each processing means N A ,B in each row with a corresponding processing means N A-1 ,B in a preceding row via a vector column subset signal line L VC (A-1) and a matrix column subset signal line L WC (A-1), and individually coupling each processing means N A ,B in each row with a corresponding processing means N A+1 ,B in a subsequent row via a vector column subset signal line L VC (A+1) and a matrix column subset signal line L WC (A+1). 
     
     
       4. An array processor as recited in claim 2, wherein said systolic coupling of said processing means N A ,B comprises individually coupling each processing means N A ,B in each column with a corresponding processing means N A ,B-1 in a preceding column via a vector row subset signal line L VR (B-1) and a matrix row subset signal line L WR (B-1), and individually coupling each processing means N A ,B in each column with a corresponding processing means N A ,B+1 in a subsequent column via a vector row subset signal line L VR (B+1) and a matrix row subset signal line L WR (B+1). 
     
     
       5. An array processor as recited in claim 1, wherein each one of said processing means N 1 ,B in said first row of processing means N A ,B is coupled to receive said vector column signal subset V C  substantially simultaneously. 
     
     
       6. An array processor as recited in claim 2, wherein each one of said processing means N A ,1 in said first column of processing means N A ,B is coupled to receive said vector row signal subset V R  substantially simultaneously. 
     
     
       7. An array processor as recited in claim 1, wherein each one of said processing means N A ,B comprises a multiplier-accumulator. 
     
     
       8. An array processor as recited in claim 7, wherein said multiplier-accumulator comprises a digital adder and a digital register. 
     
     
       9. An array processor as recited in claim 1, wherein each one of said processing means N A ,B comprises a plurality of digital registers. 
     
     
       10. A multidimensional systolic array processor comprising: a signal processing array systolically coupled in a PxQ matrix having P rows and Q columns of processing means N A ,B, where Aε{1,2,3, . . . ,P} and Bε{1,2,3, . . . ,Q}, to systolically process a matrix signal set W having a plurality of matrix signals W I ,J and a vector signal set V having a plurality of vector signals V J , where Iε{1,2,3, . . . ,M} and Jε{1,2,3, . . . K}, said matrix signal set W representing a matrix parameter set selectively represented as an MxK matrix having M rows and K columns of parameters, and said vector signal set V representing a vector parameter set selectively represented as a K-element vector having K parameters, wherein each processing means N 1 ,B in a first one of said rows of processing means N A ,B is coupled to receive a matrix column signal subset W C  of said matrix signal set W, wherein said matrix column signal subset W C  includes a first subplurality of said plurality of matrix signals W I ,J and where   W.sub.C =W.sub.A,B;Y,Z ##EQU10##  and further wherein said matrix column signal subset W.sub.C is systolically coupled row-to-row within said matrix of processing means N.sub.A,B, said coupled matrix column signal subset W.sub.C having a second subplurality of said matrix signals W.sub.I,J as said matrix column signal subset W.sub.C is coupled from one of said rows of processing means N.sub.A,B to a subsequent row of processing means N.sub.A+1,B, and still further wherein said second subplurality of matrix signals W.sub.I,J is smaller than said first subplurality of matrix signals W.sub.I,J.       
     
     
       11. An array processor as recited in claim 10, wherein each processing means N A ,B is coupled to receive a matrix row signal subset W R  of said matrix signal set W, wherein said matrix row signal subset W R  includes a third subplurality of said plurality of matrix signals W I ,J and where   W.sub.R =W.sub.A,B;Y,Z ##EQU11## and further wherein said matrix row signal subset W.sub.R is systolically coupled column-to-column within said matrix of processing means N.sub.A,B, said coupled matrix row signal subset W.sub.R having a fourth subplurality of said matrix signals W.sub.I,J as said matrix row signal subset W.sub.R is coupled from one of said columns of processing means N.sub.A,B to a subsequent column of processing means N.sub.A,B+1, and still further wherein said fourth subplurality of matrix signals W.sub.I,J is smaller than said third subplurality of matrix signals W.sub.I,J.     
     
     
       12. An array processor as recited in claim 10, wherein said systolic coupling of said processing means N A ,B comprises individually coupling each processing means N A ,B in each row with a corresponding processing means N A-1 ,B in a preceding row via a vector column subset signal line L VC (A-1) and a matrix column subset signal line L WC (A-1), and individually coupling each processing means N A ,B in each row with a corresponding processing means N A+1 ,B in a subsequent row via a vector column subset signal line  VC (A+1) and a matrix column subset signal line L WC (A+1). 
     
     
       13. An array processor as recited in claim 11, wherein said systolic coupling of said processing means N A ,B comprises individually coupling each processing means N A ,B in each column with a corresponding processing means N A ,B-1 in a preceding column via a vector row subset signal line L VR (B-1) and a matrix row subset signal line L WR (B-1), and individually coupling each processing means N A ,B in each column with a corresponding processing means N A ,B+1 in a subsequent column via a vector row subset signal line L VR (B+1) and a matrix row subset signal line L WR (B+1). 
     
     
       14. An array processor as recited in claim 10, wherein each one of said processing means N 1 ,B in said first row of processing means N A ,B is coupled to receive said matrix column signal subset W C  substantially simultaneously. 
     
     
       15. An array processor as recited in claim 11, wherein each one of said processing means N A ,1 in said first column of processing means N A ,B is coupled to receive said matrix row signal subset W R  substantially simultaneously. 
     
     
       16. An array processor as recited in claim 10, wherein each one of said processing means N A ,B comprises a multiplier-accumulator. 
     
     
       17. An array processor as recited in claim 16, wherein said multiplier-accumulator comprises a digital adder and a digital register. 
     
     
       18. An array processor as recited in claim 10, wherein each one of said processing means N A ,B comprises a plurality of digital registers. 
     
     
       19. A multidimensional systolic array processor comprising: a signal processing array systolically coupled in a PxQ matrix having P rows and Q columns of processing means N A ,B, where Aε{1,2,3, . . . P} and Bε{1,2,3, . . . Q}, to systolically process a matrix signal set W having a plurality of matrix signals W I ,J and a vector signal set V having a plurality of vector signals V J , where Iε{1,2,3, . . . M} and Jε{1,2,3, . . . K}, said matrix signal set W representing a matrix parameter set selectively represented as an MxK matrix having M rows and K columns of parameters, and said vector signal set V represented as a K-element vector having K parameters, wherein each processing means N 1 ,B in a first one of said rows of processing means N A ,B is coupled to receive a vector column signal subset V C  of said vector signal set V, wherein said vector column signal subset V C  includes a first subplurality of said plurality of vector signals V J  and where   V.sub.C =V.sub.Y,Z =V.sub.J ##EQU12##  and further wherein each processing means N.sub.1,B in a first one of said rows of processing means N.sub.A,B is coupled to receive a matrix column signal subset W.sub.C of said matrix signal set W, wherein said matrix column signal subset W.sub.C includes a second subplurality of said plurality of matrix signals W.sub.I,J and where       W.sub.C =W.sub.A,B;Y,Z ##EQU13##  and still further wherein said matrix column signal subset W.sub.C is systolically coupled row-to-row within said matrix of processing means N.sub.A,B, said coupled matrix column signal subset W.sub.C having a third subplurality of said matrix signals W.sub.I,J as said matrix column signal subset W.sub.C is coupled from one of said rows of processing means N.sub.A,B to a subsequent row of processing means N.sub.A+1,B, and still further wherein said third subplurality of matrix signals W.sub.I,J is smaller than said second subplurality of matrix signals W.sub.I,J.       
     
     
       20. An array processor as recited in claim 19, wherein each processing means N A ,1 in a first one of said columns of processing means N A ,B is coupled to receive a vector row signal subset V R  of said vector signal set V, wherein said vector row signal subset V R  includes a fourth subplurality of said plurality of vector signals V J  and where   V.sub.R =V.sub.Y,Z =V.sub.J ##EQU14##     
     
     
       21. An array processor as recited in claim 20, wherein each processing means N A ,1 in a first one of said columns of processing means N A ,B is coupled to receive a matrix row signal subset W R  of said matrix signal set W, wherein said matrix row signal subset W R  includes a fifth subplurality of said plurality of matrix signals W I ,J and where   W.sub.R =W.sub.A,B;Y,Z ##EQU15## and further wherein said matrix row signal subset W.sub.R is systolically coupled column-to-column within said matrix of processing means N.sub.A,B, said coupled matrix row signal subset W.sub.R having a sixth subplurality of said matrix signal W.sub.I,J as said matrix row signal subset W.sub.R is coupled from one of said columns of processing means N.sub.A,B to a subsequent column of processing means N.sub.A,B+1, and still further wherein said sixth subplurality of matrix signals W.sub.I,J is smaller than said fifth subplurality of matrix signals W.sub.I,J.     
     
     
       22. An array processor as recited in claim 19, wherein said systolic coupling of said processing means N A ,B comprises individually coupling each processing means N A ,B in each row with a corresponding processing means N A-1 ,B in a preceding row via a vector column subset signal line L VC (A-1) and a matrix column subset signal line L WC (A-1), and individually coupling each processing means N A ,B in each row with a corresponding processing means N A+1 ,B in a subsequent row via a vector column subset signal line L VC (A+1) and a matrix column subset signal line L WC (A+1). 
     
     
       23. An array processor as recited in claim 20, wherein said systolic coupling of said processing means N A ,B comprises individually coupling each processing means N A ,B in each column with a corresponding processing means N A ,B-1 in a preceding column via a vector row subset signal line L VR (B-1) and a matrix row subset signal line L WR (B-1), and individually coupling each processing means N A ,B in each column with a corresponding processing means N A ,B+1 in a subsequent column via a vector row subset signal line L VR (B+1) and a matrix row subset signal line L WR (B+1). 
     
     
       24. An array processor as recited in claim 19, wherein each one of said processing means N 1 ,B in said first row of processing means N A ,B is coupled to receive said vector column signal subset V C  substantially simultaneously. 
     
     
       25. An array processor as recited in claim 20, wherein each one of said processing means N A ,1 in said first column of processing means N A ,B is coupled to receive said vector row signal subset V R  substantially simultaneously. 
     
     
       26. An array processor as recited in claim 19, wherein each one of said processing means N 1 ,B in said first row of processing means N A ,B is coupled to receive said matrix column signal subset W C  substantially simultaneously. 
     
     
       27. An array processor as recited in claim 20, wherein each one of said processing means N A ,1 in said first column of processing means N A ,B is coupled to receive said matrix row signal subset W R  substantially simultaneously. 
     
     
       28. An array processor as recited in claim 19, wherein each one of said processing means N A ,B comprises a multiplier-accumulator. 
     
     
       29. An array processor as recited in claim 28, wherein said multiplier-accumulator comprises a digital adder and a digital register. 
     
     
       30. An array processor as recited in claim 19, wherein each one of said processing means N A ,B comprises a plurality of digital registers. 
     
     
       31. A method of systolically processing a plurality of signal sets, comprising the steps of: (a) providing a signal processing array systolically coupled in a PxQ matrix having P rows and Q columns of processing means N A ,B, where Aε{1,2,3, . . . P} and Bε{1,2,3, . . . Q};   (b) coupling into said processing array a matrix signal set W having a plurality of matrix signal W I ,J representing a matrix parameter set selectively represented as an MxK matrix having M rows and K columns of parameters, where Iε{1,2,3, . . . M} and Jε{1,2,3, . . . K};   (c) coupling into said processing array a vector signal set V having a plurality of vector signals V J  representing a vector parameter set selectively represented as a K-element vector having K parameters, wherein a vector column signal subset V C  of said vector signal set V is coupled into each processing means N 1 ,B in a first one of said rows of processing means N A ,B, wherein said vector column signal subset V C  includes a first subplurality of said plurality of vector signals V J  and where   V.sub.C =V.sub.Y,Z =V.sub.J ##EQU16## (d) systolically processing said matrix W and vector V signal sets.       
     
     
       32. A processing method as recited in claim 31, wherein said step (c) of coupling said vector signal set V into said processing array further comprises coupling a vector row signal subset V R  of said vector signal set V into each processing means N A ,1 in a first one of said columns of processing means N A ,B, wherein said vector row signal subset V R  includes a second subplurality of said plurality of vector signals V J  and where   V.sub.R =V.sub.Y,Z =V.sub.J ##EQU17##     
     
     
       33. A processing method as recited in claim 31, wherein said step (c) of coupling said vector signal set V into said processing array further comprises coupling said vector column signal subset V C  into each one of said processing means N 1 ,B in said first row of processing means N A ,B substantially simultaneously. 
     
     
       34. A processing method as recited in claim 32, wherein said step (c) of coupling said vector signal set V into said processing array further comprises coupling said vector row signal subset V R  into each one of said processing means N A ,1 in said first column of processing means N A ,B substantially simultaneously. 
     
     
       35. A method of systolically processing a plurality of signal sets, comprising the steps of: (a) providing a signal processing array systolically coupled in a PxQ matrix having P rows and Q columns of processing means N A ,B, where Aε{1,2,3, . . . P} and Bε{1,2,3, . . . Q};   (b) coupling into said processing array a matrix signal set W having a plurality of matrix signals W I ,J representing a matrix parameter set selectively represented as an MxK matrix having M rows of K columns of parameters, where Iε{1,2,3, . . . M} and J{1,2,3, . . . K}, wherein a matrix column signal subset W C  of said matrix signal set W is coupled into each processing means N 1 ,B in a first one of said rows of processing means N A ,B, wherein said matrix column signal subset W C  includes a first subplurality of said plurality of matrix signals W I ,J and where   W.sub.C =W.sub.A,B;Y,Z ##EQU18##  and further wherein said matrix column signal subset W.sub.C is systolically coupled row-to-row within said matrix of processing means N.sub.A,B, said coupled matrix column signal subset W.sub.C having a second subplurality of said matrix signals W.sub.I,J as said matrix column signal subset W.sub.C is coupled from one of said rows of processing means N.sub.A,B to a subsequent row of processing means N.sub.A+1,B, and still further wherein said second subplurality of matrix signals W.sub.I,J is smaller than said first subplurality of matrix signals W.sub.I,J ;       (c) coupling into said processing array a vector signal set V having a plurality of vector signals V J  representing a vector parameter set selectively represented as a K-element vector having K parameters; and   (d) systolically processing said matrix W and vector V signal sets.   
     
     
       36. A processing method as recited in claim 35, wherein said step of (b) coupling said matrix signal set W into said processing array further comprises coupling a matrix row signal subset W R  of said matrix signal set W into each processing means N A ,1 in a first one of said columns of processing means N A ,B, wherein said matrix row signal subset W R  includes a third subplurality of said plurality of matrix signals W I ,J and where   W.sub.R =W.sub.A,B;Y,Z ##EQU19## and further wherein said matrix row signal subset W.sub.R is systolically coupled column-to-column within said matrix of processing means N.sub.A,B, said coupled matrix row signal subset W.sub.R having a fourth subplurality of said matrix signals W.sub.I,J as said matrix row signal subset W.sub.R is coupled from one of said columns of processing means N.sub.A,B to a subsequent column of processing means N.sub.A,B+1, and still further wherein said fourth subplurality of matrix signals W.sub.I,J is smaller than said third subplurality of matrix signals W.sub.I,J.     
     
     
       37. A processing method as recited in claim 35, wherein said step of (b) coupling said matrix signal set W into said processing array further comprises coupling said matrix column signal subset W C  into each one of said processing means N 1 ,B in said first row of processing means N A ,B substantially simultaneously. 
     
     
       38. A processing method as recited in claim 36, wherein said step of (b) coupling said matrix signal set W into said processing array further comprises coupling said matrix row signal subset W R  into each one of said processing means N A ,1 in said first column of processing means N A ,B substantially simultaneously. 
     
     
       39. A method of systolically processing a plurality of signal sets, comprising the steps of: (a) providing a signal processing array systolically coupled in a PxQ matrix having P rows and Q columns of processing means N A ,B, where Aε{1,2,3, . . . P} and Bε{1,2,3, . . . Q};   (b) coupling into said processing array a matrix signal set W having a plurality of matrix signal W I ,J representing a matrix parameter set selectively represented as an MxK matrix having M rows and K columns of parameters, where Iε{1,2,3, . . . M} and Jε{1,2,3, . . . K}, wherein a matrix column signal subset W C  of said matrix signal set W is coupled into each processing means N 1 ,B in a first one of said rows of processing means N A ,B, wherein said matrix column signal subset W C  includes a first subplurality of said plurality of matrix signals W I ,J and where   W.sub.C =W.sub.A,B;Y,Z ##EQU20##  and further wherein said matrix column signal subset W.sub.C is systolically coupled row-to-row within said matrix of processing means N.sub.A,B, said coupled matrix column signal subset W.sub.C having a second subplurality of said matrix signals W.sub.I,J as said matrix column signal subset W.sub.C is coupled from one of said rows of processing means N.sub.A,B to a subsequent row of processing means N.sub.A+1,B, and still further wherein said third subplurality of matrix signals W.sub.I,J is smaller than said second subplurality of matrix signals W.sub.I,J ;       (c) coupling into said processing array a vector signal set V having a plurality of vector signals V J  representing a vector parameter set selectively represented as a K-element vector having K parameters, wherein a vector column signal subset V C  of said vector signal set V is coupled into each processing means N 1 ,B in a first one of said rows of processing means N A ,B, wherein said vector column signal subset V C  includes a first subplurality of said plurality of vector signals V J  and where   V.sub.C =V.sub.Y,Z =V.sub.J ##EQU21## (d) systolically processing said matrix W and vector V signal sets.       
     
     
       40. A processing method as recited in claim 39, wherein said set of (b) coupling said matrix signal set W into said processing array further comprises coupling a matrix row signal subset W R  of said matrix signal set W into each processing means N A ,1 in a first one of said columns of processing means N A ,B, wherein said matrix row signal subset W R  includes a fourth subplurality of said plurality of matrix signals W I ,J and where   W.sub.R =W.sub.A,B;Y,Z ##EQU22## and further wherein said matrix row signal subset W.sub.R is systolically coupled column-to-column within said matrix of processing means N.sub.A,B, said coupled matrix row signal subset W.sub.R having a fifth subplurality of said matrix signals W.sub.I,J as said matrix row signal subset W.sub.R is coupled from one of said columns of processing means N.sub.A,B to a subsequent column of processing means N.sub.A,B+1, and still further wherein said fifth subplurality of matrix signals W.sub.I,J is smaller than said third subplurality of matrix signals W.sub.I,J.     
     
     
       41. A processing method as recited in claim 39, wherein said step (b) coupling said matrix signal set W into said processing array further comprises coupling said matrix column signal subset W C  into each one of said processing means N 1 ,B in said first row of processing means N A ,B substantially simultaneously. 
     
     
       42. A processing method as recited in claim 40, wherein said step of (b) coupling said matrix signal set W into said processing array further comprises coupling said matrix row signal subset W R  into each one of said processing means N A ,1 in said first column of processing means N A ,B substantially simultaneously. 
     
     
       43. A processing method as recited in claim 39, wherein said step (c) of coupling said vector signal set V into said processing array further comprises coupling a vector row signal subset V R  of said vector signal set V into each processing means N A ,1 in a first one of said columns of processing means N A ,B, wherein said vector row signal subset V R  includes a sixth subplurality of said plurality of vector signals V J  and where   V.sub.R =V.sub.Y,Z =V.sub.J ##EQU23##     
     
     
       44. A processing method as recited in claim 39, wherein said step (c) of coupling said vector signal set V into said processing array further comprises coupling said vector column signal subset V C  into each one of said processing means N 1 ,B in said first row of processing means N A ,B substantially simultaneously. 
     
     
       45. A processing method as recited in claim 43, wherein said step (c) of coupling means vector signal set V into said processing array further comprises coupling said vector row signal subset V R  into each one of said processing means N A ,1 in said first column of processing means N A ,B substantially simultaneously.