[PDF] Nur Dean - City University of New York

3 3 Matrices - Math - The University of Utah

We call this matrix the 3 ⇥ 3 identity matrix ***** *** Matrix multiplication You can “multiply” two 3⇥3matricestoobtainanother3⇥3matrix Order the columns of a matrix from left to right, so that the 1st column is on the left, the 2nd column is directly to the right of the 1st,andthe3rd column is to the right of the 2nd

Nur Dean - City University of New York

Parallel Algorithms for Matrix Multiplication Example 3x3 Fox’s Algorithm Stage 2: Process (i;(i + 2) mod3) Broadcast along row i (0,2) a 02 (1,0) a 10 (2,1) a 21 a 02;b 20 a 02;b 21 a 02;b 22 a 10;b 00 a 10;b 01 a 10;b 02 a 21 01

Matrix Multiplication : When the number of columns of the first

matrix is the same as the number of rows in the second matrix then matrix multiplication can be performed Here is an example of matrix multiplication for two 2x2 matrices Here is an example of matrices multiplication for a 3x3 matrix When A has dimensions mxn, B has dimensions nxp Then the product of A and B is the matrix C, which has

Systolic Architectures - Computer Action Team

3x3 Systolic Array Matrix Multiplication b2,2 b2,1 b1,2 b2,0 b1,1 b0,2 b1,0 b0,1 b0,0 a0,2 a0,1 a0,0 a1,2 a1,1 a1,0 a2,2 a2,1 a2,0 Alignments in time • Processors arranged in a 2-D grid • Each processor accumulates one element of the product Rows of A Columns of B T = 0

Matrix Multiplication - Oakland University

answer is located on the matrix by the LED’s displaying the position on the matrix I INTRODUCTION For our ECE 378 we have decided to make a 2 x 2 matrix multiplier and a 3 x 3 matrix multiplier A matrix multiplication is a binary operation that takes a pair of matrices, and produces another matrix While a matrix are

Matrix Multiplication - University of Plymouth

Section 3: Matrix Multiplication 2 9 3 Matrix Multiplication 2 The extension of the concept of matrix multiplication to matrices, A, B, in which A has more than one row and B has more than one column is now possible The product matrix AB will have the same number of columns as B and each column is obtained by taking the

Matrix multiplication

Matrix multiplication 3x4 matrix 4x2 matrix The multiplication is legal since 2 3 4 5 1 3 number of columns of A is the

Matrices, transposes, and inverses

Feb 01, 2012 · Matrix multiplication For m x n matrix A and n x p matrix B, the matrix product AB is an m x p matrix “outer” parameters become parameters of matrix AB What sizes of matrices can be multiplied together? If A is a square matrix and k is a positive integer, we define Ak = ￿A · A￿￿···A￿ k factors Properties of matrix multiplication

[PDF] produit de trois matrices

[PDF] produit de 3 matrices

[PDF] calculatrice matrice en ligne

[PDF] produit de deux matrices de taille différentes

[PDF] nombre relatif multiplication et division

[PDF] multiplication de nombres relatifs 4ème exercices

[PDF] variable aléatoire pdf

[PDF] variable aléatoire discrète

[PDF] fonction de répartition d'une variable aléatoire discrète

[PDF] variable aléatoire exemple

[PDF] soliman et françois 1er

[PDF] fonction de distribution statistique

[PDF] produit scalaire deux vecteurs

[PDF] produit vectoriel de deux vecteurs dans le plan

[PDF] fonction de répartition d une variable aléatoire discrète

Matrix Multiplication

Nur Dean

PhD Program in Computer Science

The Graduate Center, CUNY

05/01/2017

Nur Dean (The Graduate Center)Matrix Multiplication05/01/2017 1 / 36 Today, I will talk about matrix multiplication and 2 parallel algorithms to use for my matrix multiplication calculation. Nur Dean (The Graduate Center)Matrix Multiplication05/01/2017 2 / 36

Overview

1Background

Denition of A Matrix

Matrix Multiplication

2Sequential Algorithm

3Parallel Algorithms for Matrix Multiplication

Checkerboard

Fox's Algorithm

Example 3x3 Fox's Algorithm

Fox`s Algorithm Psuedocode

Analysis of Fox's Algorithm

SUMMA:Scalable Universal Matrix Multiplication Algorithm

Example 3x3 SUMMA Algorithm

SUMMA Algorithm

Analysis of SUMMA

Nur Dean (The Graduate Center)Matrix Multiplication05/01/2017 3 / 36

BackgroundDenition of A Matrix

Denition of A Matrix

A matrix is a rectangular two-dimensional array of numbers

We say a matrix ismxnif it hasmrows andncolumns.We useaijto refer to the entry inithrow andjthcolumn of the

matrixA.Nur Dean (The Graduate Center)Matrix Multiplication05/01/2017 4 / 36

BackgroundMatrix Multiplication

Matrix multiplication is a fundamental linear algebra operation that is at the core of many important numerical algorithms.IfA,B, andCareNxNmatrices, thenC=ABis also anNxN matrix, and the value of each element inCis dened as: C ij=PN k=0AikBkjNur Dean (The Graduate Center)Matrix Multiplication05/01/2017 5 / 36

Sequential Algorithm

Algorithm 1Sequential Algorithmfor(i=0;iSequential Algorithm During the rst iteration of loop variableithe rst matrixArow and all the columns of matrixBare used to compute the elements of the rst result matrixCrowThis algorithm is an iterative procedure and calculates sequentially the rows of the matrixC. In fact, a result matrix row is computed per

outer loop (loop variablei) iteration.Nur Dean (The Graduate Center)Matrix Multiplication05/01/2017 7 / 36

Sequential Algorithm

As each result matrix element is a scalar product of the initial matrixA row and the initial matrixBcolumn, it is necessary to carry outn2(2n1) operations to compute all elements of the matrixC. As a result the time complexity of matrix multiplication is; T

1=n2(2n1)

whereis the execution time for an elementary computational operation such as multiplication or addition. Nur Dean (The Graduate Center)Matrix Multiplication05/01/2017 8 / 36 Parallel Algorithms for Matrix MultiplicationCheckerboard

Checkerboard

Most parallel matrix multiplication functions use a checkerboard distribution of the matrices. This means that the processes are viewed as a grid, and, rather than assigning entire rows or entire columns to each process, we assign small sub-matrices. For example, if we have four processes, we might assign the element of a 4x4 matrix as shown below, checkerboard mapping of a 4x4 matrix to four processes.Process 0 a 00a01 a

10a11Process 1

a 02a03 a

12a13Process 2

a 20a21 a

30a31Process 3

a 22a23
a

32a33Nur Dean (The Graduate Center)Matrix Multiplication05/01/2017 9 / 36

Parallel Algorithms for Matrix MultiplicationFox's Algorithm

Fox's Algorithm

Process 0

a 00a01 a

10a11Process 1

a 02a03 a

12a13Process 2

a 20a21 a

30a31Process 3

a 22a23
a

32a33Fox`s algorithm is a one that distributes the matrix using a

checkerboard scheme like the above.In order to simplify the discussion, lets assume that the matrices have

ordern, and the number of processes,p, equalsn2. Then a

checkerboard mapping assignsaij,bij, andcijto process (i;j).In a process grid like the above, the process (i,j) is the same as

processp=in+j, or, loosely, process (i;j) using row major form in the process grid. Nur Dean (The Graduate Center)Matrix Multiplication05/01/2017 10 / 36 Parallel Algorithms for Matrix MultiplicationFox's Algorithm

Cont. Fox's Algorithm

Fox`s algorithm takesnstages for matrices of ordernone stage for each termaikbkjin the dot product C

ij=ai0b0j+ai1b1i+. . . +ai;n1bn1;jInitial stage, each process multiplies the diagonal entry ofAin its

process row by its element ofB: Stage 0 on process(i;j):cij=aiibijNext stage, each process multiplies the element immediately to the right of the diagonal ofAby the element ofBdirectly beneath its own element ofB:

Stage 1 on process(i;j):cij=cij+ai;i+1bi+1;jIn general, during thekthstage, each process multiplies the elementk

columns to the right of the diagonal ofAby the elementkrows below its own element ofB:

Stagekon process(i;j):cij=cij+ai;i+kbi+k;jNur Dean (The Graduate Center)Matrix Multiplication05/01/2017 11 / 36

Parallel Algorithms for Matrix MultiplicationFox's Algorithm

Example of the Algorithm Applied to 2x2 Matrices

A= a 00a01 a 10a11 B=b 00b01 b 10b11 C= a

00b00+a01b10a00b01+a01b11

a

10b00+a11b10a10b01+a11b11

Assume that we haven2processes, one for each of the elements inA,B, andC. Call the processesP00,P01,P10, andP11, and think of them as being arranged in a grid as follows:P 00P 01P 10P

11Nur Dean (The Graduate Center)Matrix Multiplication05/01/2017 12 / 36

Parallel Algorithms for Matrix MultiplicationFox's Algorithm

Stage 0

(a) We wantai;ion processPi;j, so broadcast the diagonal elements ofAacross the rows, (aii!Pij) This will placea0;0on eachP0;jand a

1;1on eachP1;j. TheAelements on thePmatrix will bea

00a 00a 11a

11(b) We wantbi;jon processPi;j, so broadcastBacross the rows

(bij!Pij) TheAandBvalues on thePmatrix will bea 00 b 00a 00 b 01a 11 b 10a 11 b

11Nur Dean (The Graduate Center)Matrix Multiplication05/01/2017 13 / 36

Parallel Algorithms for Matrix MultiplicationFox's Algorithm (c) Computecij=ABfor each processa 00 b 00 c

00=a00b00a

00 b 01 c

01=a00b01a

11 b 10 c

10=a11b10a

11 b 11 c

11=a11b11We are now ready for the second stage. In this stage, we broadcast the

next column (mod n) ofAacross the processes and shift-up (mod n) the Bvalues.Nur Dean (The Graduate Center)Matrix Multiplication05/01/2017 14 / 36 Parallel Algorithms for Matrix MultiplicationFox's Algorithm

Stage 1

(a) The next column ofAisa0;1for the rst row anda1;0for the second row (it wrapped around, mod n). Broadcast nextAacross the rowsa 01 b 00 c

00=a00b00a

01 b 01 c

01=a00b01a

10 b 10 c

10=a11b10a

10 b 11 c

11=a11b11Nur Dean (The Graduate Center)Matrix Multiplication05/01/2017 15 / 36

Parallel Algorithms for Matrix MultiplicationFox's Algorithm (b) Shift theBvalues up.B1;0moves up from processP1;0to process P

0;0andB0;0moves up (mod n) fromP0;0toP1;0. Similarly forB1;1

andB0;1.a 01 b 10 c

00=a00b00a

01 b 11 c

01=a00b01a

10 b 00 c

10=a11b10a

10 b 01 c

11=a11b11Nur Dean (The Graduate Center)Matrix Multiplication05/01/2017 16 / 36

Parallel Algorithms for Matrix MultiplicationFox's Algorithm (c) ComputeCij=ABfor each processa 01 b 10 c

00=c00+a01b10a

01 b 11 c

01=c01+a01b11a

10 b 00 c

10=c10+a10b00a

10 b 01 c

11=c11+a10b01The algorithm is complete afternstages and processPi;jcontains the nal

result forci;j.Nur Dean (The Graduate Center)Matrix Multiplication05/01/2017 17 / 36 Parallel Algorithms for Matrix MultiplicationExample 3x3 Fox's Algorithm

Example 3x3 Fox's Algorithm

Consider multiplying 3x3 block matrices:

2

41 2 1

0 1 2

1 1 13

5 2

41 0 2

2 0 3

1 2 13

5 =2

46 2 9

4 4 5

4 2 63

5 Nur Dean (The Graduate Center)Matrix Multiplication05/01/2017 18 / 36 Parallel Algorithms for Matrix MultiplicationExample 3x3 Fox's Algorithm

Stage 0:Process

(i;i mod3)Broadcast along rowi(0,0)a00(1,1)a11(2,2)a22a

00;b00a00;b01a00;b02

a

11;b10a11;b11a11;b12

a

22;b20a22;b21a22;b22

Process (i;j) computes:c

00=1x1=1c

01=1x0=0c

02=1x2=2c

10=1x2=2c

11=1x0=0c

12=1x3=3c

20=1x1=1c

21=1x2=2c

22=1x1=1Shift-rotate on the columns ofBNur Dean (The Graduate Center)Matrix Multiplication05/01/2017 19 / 36

Parallel Algorithms for Matrix MultiplicationExample 3x3 Fox's Algorithm

Stage 1:Process

(i;(i+ 1)mod3)Broadcast along rowi(0,1)a01(1,2)a12(2,0)a20a

01;b10a01;b11a01;b12

a

12;b20a12;b21a12;b22

a

20;b00a20;b01a20;b02

Process (i;j) computes:c

00=1+(2x2)=5c

01=0+(2x0)=0c

02=2+(2x3)=8c

10=2+(2x1)=4c

11=0+(2x2)=4c

12=3+(2x1)=5c

20=1+(1x1)=2c

21=2+(1x0)=2c

22=1+(1x2)=3Shift-rotate on the columns ofBNur Dean (The Graduate Center)Matrix Multiplication05/01/2017 20 / 36

Parallel Algorithms for Matrix MultiplicationExample 3x3 Fox's Algorithm

Stage 2:Process

(i;(i+ 2)mod3)Broadcast along rowi(0,2)a02(1,0)a10(2,1)a21a

02;b20a02;b21a02;b22

a

10;b00a10;b01a10;b02

a

21;b10a21;b11a21;b12

Process (i;j) computes:c

00=5+(1x1)=6c

01=0+(1x2)=2c

quotesdbs_dbs6.pdfusesText_11