Copy Of Parallel Graph Algorithms

National Institute of Science & Technology

Parallel Graph Algorithms

A technical Seminar on Parallel Graph Algorithms

By Anshuman Chakraborty CS200118214 under the guidance of Anisur Rahman Anshuman Chakraborty

[1]

National Institute of Science & Technology

Parallel Graph Algorithms

What is Parallel Processing? • Parallel processing is processing a task with several processing units, or many processors • Most powerful computers contain two or more processing units that share among themselves the jobs submitted for processing Anshuman Chakraborty

[2]

National Institute of Science & Technology

Parallel Graph Algorithms

Why Parallel processing?

• Several operations are performed simultaneously, so the time taken by a computation can be reduced. • A problem to be solved is broken into a no.of subproblems. These subproblems are now solved simultaneously, each on different processors. The results are then combined to produce an answer to the original problem. • To achieve “speedup” of processing Anshuman Chakraborty

[3]

National Institute of Science & Technology

Parallel Graph Algorithms

Speedup of Computation • Sppedup is measured in contrast with sequential version of the same algorithm • speedup =ws/wp where ws=worst case running time of fastest known sequential algorithm for the problem and wp= worst case running time of the parallel algorithm for the same problem. • Pipelines have been extensively used in processors to increase the performance.

Anshuman Chakraborty

[4]

National Institute of Science & Technology

Parallel Graph Algorithms

Computational Model • 1. 2. 3. 4.

The stream of instruction tells the computer what to do at each step and are divided into four types: Single Instruction stream, single Data stream (SISD) Multiple Instruction stream, Single Data stream(MISD) Single Instruction stream, Multiple Data stream(SIMD) Multiple Instruction stream, Multiple Data stream(MIMD)

Anshuman Chakraborty

[5]

National Institute of Science & Technology

Parallel Graph Algorithms

Introducing Graph • A graph consists of a finite set of nodes and a finite set of edges connecting pairs of these nodes • One graph can be represented either by an adjacency matrix or adjacency list Anshuman Chakraborty

[6]

National Institute of Science & Technology

Parallel Graph Algorithms

The connectivity matrix • The connectivity matrix of an n-node graph G is an n x n matrix C whose elements are defined as follows: cjk =1 if there is a path of length 0 or more from vj to vk • • =0 otherwise • The procedure takes the adjacency matrix A as input and returns the connectivity matrix C as output. It runs on a cube-connected SIMD computer with N = n3 processors arranged in an (n x n x n) array pattern. In this array • The Parallel algorithm is as

Anshuman Chakraborty

[7]

National Institute of Science & Technology

Parallel Graph Algorithms

The connectivity matrix contd Procedure: CUBE CONNECTIVITY (A, C) Step 1: {The diagonal elements of the adjacency matrix are made equal to 1} for j = 0 to n -1 do in parallel A(0, j, j) ←1 end for. Step 2: {The A registers are copied into the B registers} for j = 0 to n-1 do in parallel for k = 0 to n-1 do in parallel B(0, j, k)<--A(0,j, k) end for end for.

Anshuman Chakraborty

[8]

National Institute of Science & Technology

Parallel Graph Algorithms

The connectivity matrix contd Step 3: {The connectivity matrix is obtained through repeated Boolean multiplication) for i = 1 to [log(n - 1)] do [3.1]CUBE MATRIX MULTIPLICATION (A, B, C) [3.2] for j=0 to n-1 do in parallel for k = 0 to n -1 do in parallel (i)A(0, j, k) ←C(0, j, k) (ii) B(0, j ,k) ←C(0, j, k) end for end for end for • It takesO(log n) time. This step is iterated (log n) times. It follows that the overall running time of this procedure is t (n) = O (log2 n).

Anshuman Chakraborty

[9]

National Institute of Science & Technology

Parallel Graph Algorithms

All pair shortest path

k • Let d ij denote the length of the shortest path from vi to vj that goes through at most k-1 intermediate vertices. 1 • Thus d ij =wij ,(the weight of the edge from vi to vj. 1 1 • d ij =∞. Also d ii =0. G has no cycles of negative line, there is no advantage in visiting any vertex more than once in a shortest path from vi to vj

• In order to compute for k > 1 we can use the fact that k k/2 k/2 n-1 • d ij = minl{d il +d lj }and dij =d ij 3 • The procedure runs on a cube-connected SIMD computer with N = n processors, each with three registers A, B, and C. As before, the processors can be regarded as being arranged in an (n x n x n) array pattern.

Anshuman Chakraborty

[10]

National Institute of Science & Technology

Parallel Graph Algorithms

All Pair Shortest Path algo Procedure CUBE SHORTEST PATHS (A, C) Step 1: (Construct the matrix D1 and store it in registers A and B) for j = 0 to n-1 do in parallel for k = 0 to n-1 do in parallel if j!=k and A(0, j, k) = 0 then A(0, j, k) = Inf end if [1.2] B(0, j, k) = A(0, j, k) end for end for

Anshuman Chakraborty

Slep 2: (Construct the matrices D2, D4, ….., Dn-1 through repeated matrix multiplication} for i = l to log(n-1) do [2.1] CUBE MATRIX MULTIPLICATION (A, B, C) [2.2] for j = 0 to n-1 do in parallel for k = 0 lo n-1 do in parallel [1]A(0, j, k ) =C(0, j, k) [2]B(0, j, k) =C(0, j, k) end for end for end for.

[11]

National Institute of Science & Technology

Parallel Graph Algorithms

All Pair Shortest Path(complexity) • Steps 1 and 2 take constant time. There are [log(n1)] iterations of step 2.1 each requiring O(logn) time. • The overall running time of procedure CUBE SHORTEST PATHS is therefore t(n) = O(log2n). Since p(n)=n3 ,c(n) = O(n3log2n) • The sequential algorithm takes O(n3) time • The speed up = 2k .k2 where k=log2n. Anshuman Chakraborty

[12]

National Institute of Science & Technology

Parallel Graph Algorithms

Example

Anshuman Chakraborty

[13]

National Institute of Science & Technology

Parallel Graph Algorithms

Computation of All pair Shortest Path

Anshuman Chakraborty

[14]

National Institute of Science & Technology

Parallel Graph Algorithms

Computation of All pair Shortest Path

Anshuman Chakraborty

[15]

National Institute of Science & Technology

Parallel Graph Algorithms

Conclusion • Graph Theory and algorithms has a very wide area of application in practical problems of Networking • So it is very good if a speed up is achieved in few graph algorithms like finding MST or finding Transitive Closure • It is a great experience in doing a Technical seminar related to Parallel Processing Anshuman Chakraborty

[16]

National Institute of Science & Technology

Parallel Graph Algorithms

Thank You!!!

Anshuman Chakraborty

[17]