# Parallel Algorithm Matrix Multiplication - Parallel Algorithm

## How to implement matrix multiplication in parallel algorithm?

The numerical and non-numerical data is arranged in a fixed number of rows and columns forming a matrix. An important multiplication design in parallel computation is matrix multiplication. In this chapter, Multiplication matrix is implemented on various communication networks such as mesh and hypercube is discussed. Network connectivity is high in mesh and hypercube enabling faster algorithm than other networks.

## What is Mesh Network?

When a p-dimensional grid is formed by a set of nodes, such a topology is called mesh topology. All the nodes can communicate with each other and the edges are parallel to the grid axis.

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

The factors used for evaluating a mesh network are -

• Diameter
• Bisection width

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

Bisection width – When a mesh network is divided into two halves, the minimum number of edges removed from the network is Bisection width.

### Matrix Multiplication Using Mesh Network

A 2D mesh network SIMD model which has wraparound connections is considered. An algorithm is designed for multiplying two n × n arrays using n2 processors in a particular amount of time.

Elements for matrices A and B areaijandbijrespectively. aij and bij are represented by the processing elementPEij. The matrices A and B are arranged in such a manner that every processor contains a pair of elements for multiplication. The elements of matrix A will move in left direction and the elements of matrix B will move in upward direction. A new pair of values for multiplication are represented by these position changes of the elements of matrix A and B.

Steps in Algorithm

• Stagger two matrices.
• Calculate sums when step 2 is complete.

Algorithm

## Hypercube Network

An n-dimensional construct where the edges are of the same length and are perpendicular among them is hypercube. N-dimensional hypercube is also known as an n-cube or an n-dimensional cube.

Features of Hypercube with 2k

• Diameter = k
• Bisection width = 2k–1
• Number of edges = k

### Matrix Multiplication using Hypercube Network

General specification of Hypercube networks −

• Let N =2mbe the total number of processors. Let the processors beP0,P1…..PN-1.
• Let i and ib be two integers, 0 < i,ib< N-1 and its binary representation differ only in position b, 0 < b < k–1.
• Consider two n × n matrices, matrix A and matrix B.
• Step 1 − The elements of matrix A and matrix B are assigned to then3processors such that the processor in position i, j, k will haveajiandbik.
• Step 2 − All the processor in position (i,j,k) computes the product

C(i,j,k) = A(i,j,k) × B(i,j,k)

• Step 3 − The sum C(0,j,k) = ΣC(i,j,k) for 0 ≤ i ≤ n-1, where 0 ≤ j, k < n–1.

## Block Matrix

A matrix in which each element itself represents an individual matrix is known as block matrix. The individual matrix within are known as block or suAn b-matrix.

Example

In Figure (a), X is a block matrix where A, B, C, D are matrix themselves. Figure (f) shows the total matrix.

### Block Matrix Multiplication

If the two block matrices are square matrices, they can be multiplied as simple matrix multiplication.