Systolic Arrays Matrix-Vector Multiplication.ppt

1、10/14/2018,1,Systolic Arrays Matrix-Vector Multiplication,Cathy Yen,10/14/2018,2,Introduction,The developments in microelectronics have revolutionized computer design Component density has been doubling every one to two years A multiplier can fit on a very large scale integrated (VLSI) circuit chip

2、It is feasible to build low-cost, special-purpose, peripheral devices to solve sophisticated problems.,10/14/2018,3,What is Systolic Arrays?,(By analogy with the regular pumping of blood by the heart) . Systolic arrays are examples of single-instruction-multiple-data machines . special purpose machi

3、nes used mainly in dedicated equipment and not in general purpose computers. . A systolic array is a form of parallel architecture with a regular, nearest-neighbour interconnection .,10/14/2018,4,What do Systolic Arrays do?,data compression; Royals Discrete Cosine Transforms; Chang, Chang Fourier tr

4、ansformations; Peng, Lippert genetic algorithms; Megson image processing and detection systems; Hwang , Cheng, Ker, Diamantaras, Liu, Gasteratos, Kim,10/14/2018,5,What do Systolic Arrays do?,matrix inversion; Margaritis matrix multiplication; Wan shortest-path problems; Myoupo signal processing; Li,

5、 Robert, Speiser tridiagonal banded matrix multiplication; Evans, Naritomi and sorting.,10/14/2018,6,The functioning of a systolic array depends on:,the structure of the individual cells that are replicated across the array; how the data is moved across the array (a function of how they are connecte

6、d); and how the data is feed into the array.,10/14/2018,7,a Closer look at Systolic Arrays,Processing Elements,a,y,y,x,x,a,a,a,y,y,x,x,matrix-vector matrix,10/14/2018,8,a Closer look at Systolic Arrays,Processor Arrays,Linearly connected,Orthogonally connected,Hexagonally connected,10/14/2018,9,Matr

7、ix-Vector Multiplication,(A*X = Y),a11 a12 a13 x1 y1 a21 a22 a23 x2 = y2 a31 a32 a33 x3 y3,10/14/2018,10,Matrix-Vector Multiplication(A*X = Y),Yi(1) = 0, Ts (n)= w*n = (2n-1)*n = 2n2-n Yi(k+1) = yi(k) + aikxk O(wn) Yi = yi(n+1),a11 a12 a13 x1 y1 a21 a22 a23 x2 = y2 a31 a32 a33 x3 y3,10/14/2018,11,Ma

8、trix-Vector Multiplication(A*X = Y),Bandwidth: w = n+n1 = 2n-1 O(n) Tp(n) = 2n + w 2n+(2n-1) 4n-1 O(n),a11 a12 a13 x1 y1 a21 a22 a23 x2 = y2 a31 a32 a33 x3 y3,10/14/2018,12,Matrix-Vector Multiplication(A*X = Y),10/14/2018,13,10/14/2018,14,10/14/2018,15,10/14/2018,16,Matrix-Vector Multiplication(A*X

9、= Y),Y1 = a11*x1 + a12*x2 + a13*x3 Y2 = a21*x1 + a22*x2 + a23*x3 Y3 = a31*x1 + a32*x2 + a33*x3,a11 a12 a13 x1 y1 a21 a22 a23 x2 = y2 a31 a32 a33 x3 y3,10/14/2018,17,Matrix-Vector Multiplication(A*X = Y),Ts (n)= w*n = (2n-1)*n = 2n2-n O(wn) Tp(n)= 2n + w 2n+(2n-1) 4n-1 O(n),10/14/2018,18,Conclusion,O

10、n the positive side systolic arrays are highly compact, robust, provide high performance, and can be massively and cheaply produced as they are accessible via VLSI technology. On the negative side the arrays are inflexible to the type of problem they solve and often are inflexible to the size of the

11、 problem they address.,10/14/2018,19,Conclusion,Systolic arrays may be used to solve many regular problems containing repetitive operations on large arrays of data. They are not yet suited to general purpose computers.,10/14/2018,20,References:,H.T. Kung and C.E. Leiserson, “Systolic arrays (for VLS

12、I),” pp. 271-276 Manohar, S.; Baudet, G.; Computers and Digital Techniques, IEE Proceedings E Volume: 137 Issue: 4 , July 1990 Page(s): 277 282 Milovanovic, I.Z.; Milovanovic, E.I.; Tokic, T.I.; Stojanovic, N.M.; Stojcev, M.K.; Modern Problems of Radio Engineering, Telecommunications and Computer Science, 2002. Proceedings of the International Conference , 18-23Feb. 2002 Page(s): 90 -92,