Information Technology
FIT3143 – LECTURE WEEK 8
PARALLEL ALGORITHM DESIGN – PARTITIONING BASED ON MATRIX OPERATIONS
Copyright By PowCoder代写 加微信 powcoder
Topic Overview
Matrix Algorithms & Problem Statement Decomposition
Decomposition – Fox’s method
A portion of the content in the following slides were created by:
a) Gergel V.P., Nizhni Novgorod, Introduction to Parallel Programming: Matrix Multiplication, 2005.
b) , , , and , “Introduction to Parallel Computing”, , 2003.
Matrix Algorithms: Introduction
• Due to their regular structure, parallel computations involving matrices and vectors readily lend themselves to data-decomposition.
• Typical algorithms rely on input, output, or intermediate data decomposition.
• Most algorithms use one- and two-dimensional block, cyclic, and block-cyclic partitionings.
Gergel V.P., Nizhni Novgorod, Introduction to Parallel Programming: Matrix Multiplication, 2005
Problem Statement
Matrix multiplication:
The matrix multiplication problem can be reduced to the executionofm·lindependentoperations ofmatrixArowsand matrix B columns inner product calculation
Data parallelism can be exploited to design parallel computations
Gergel V.P., Nizhni Novgorod, Introduction to Parallel Programming: Matrix Multiplication, 2005
Sequential Algorithm
// Sequential algorithm of matrix multiplication double MatrixA[Size][Size];
double MatrixB[Size][Size];
double MatrixC[Size][Size];
int i,j,k;
for (i=0; i