Question

Discuss and write parallel matrix multiplication algorithm usmg pram model

Answer 1

A matrix is a set of numerical and non-numerical data arranged in a fixed number of rows and column. Matrix multiplication is an important multiplication design in parallel computation. Here, we will discuss the implementation of matrix multiplication on various communication networks like mesh and hypercube. Mesh and hypercube have higher network connectivity, so they allow faster algorithm than other networks like ring network.

Mesh Network

A topology where a set of nodes form a p-dimensional grid is called a mesh topology. Here, all the edges are parallel to the grid axis and all the adjacent nodes can communicate among themselves.

Total number of nodes = (number of nodes in row) × (number of nodes in column)

A mesh network can be evaluated using the following factors −

DiameterBisection width

Diameter − In a mesh network, the longest distance between two nodes is its diameter. A p-dimensional mesh network having kP nodes has a diameter of p(k–1).

Bisection width − Bisection width is the minimum number of edges needed to be removed from a network to divide the mesh network into two halves.

Matrix Multiplication Using Mesh Network

We have considered a 2D mesh network SIMD model having wraparound connections. We will design an algorithm to multiply two n × n arrays using n2 processors in a particular amount of time.

Matrices A and B have elements aij and bijrespectively. Processing element PEij represents aijand bij. Arrange the matrices A and B in such a way that every processor has a pair of elements to multiply. The elements of matrix A will move in left direction and the elements of matrix B will move in upward direction. These changes in the position of the elements in matrix A and B present each processing element, PE, a new pair of values to multiply.

Steps in AlgorithmStagger two matrices.Calculate all products, aik × bkjCalculate sums when step 2 is complete.