i

SASTRA UNIVERSITY
Shanmugha Arts, Science, Technology and Research Academy Thirumalaisamudram Thanjavur – 613 402

BCSCCS705 PARALLEL COMPUTING AND ALGORITHMS LAB B.TECH (COMPUTER SCIENCE AND ENGINEERING) 7TH SEMESTER

ii

List of Exercises:
1. Basic arithmetic operations in parallel 2. Find out factorial of a number 3. Generation of Fibonacci series, finding prime numbers in an interval. 4. Evaluate the integral of a function 5. Merging of two sorted lists 6. Parallel tree traversals 7. Matrix multiplication 8. Enumeration sort 9. Odd-Even transposition sort 10. Bitonic merge 11. Quick sort 12. Single source shortest path

iii

Exercise 1 Aim:

Basic Arithmetic Operations in parallel

To perform a set of arithmetic operations in parallel using a cluster of computers Procedure: Step 1: Identify a set of numbers over which arithmetic operations are to be done Step 2: Identify the rank in the cluster Step 3: Split the set of numbers into domains and assign each domain to their corresponding processor Step 4: Get the result from each computer in the cluster and assimilate them at the master Step 5: Verify the time taken for the completion of each task. Algorithm:function sum(+,identity,a) = if #a == 1 then [identity] else let e = even_elts(a); o = odd_elts(a); s = scan_op(op,identity,{op(e,o): e in e; o in o}) in interleave(s,{op(s,e): s in s; e in e});

iv

Input:- An array of integers

Output: - The sum
3,2,7,6 P1 18 0,5,4,8 P2 17 62 2,0,1,5 P3 8 2,3,8,6 P4 19

Pre lab: To know the processing environment, a program using size and rank of the processors in the cluster.

v

Exercise 2 Aim:

Factorial of a number

To find a factorial of number in parallel using a cluster of processors Procedure: step 1 : Identify a number for which factorial is to calculated step 2: Identify the rank in the cluster step 3: Split the number into ranges and assign each range to one processor each step 4: Get the result from each processor in the cluster and find the cumulative result at the master step 5: Verify the time taken for the completion of each task.

Pre lab: Program to find the factorial of given no using all processors in the cluster without splitting into ranges.

vi

Exercise 3 Aim:

Generation of Fibonacci series and Finding prime numbers in an interval.

To generate the Fibonacci series of numbers and finding a set prime number in a given interval Procedure: Fibonacci step 1 : Identify a maximum limit up to which Fibonacci series has to be generated. step 2: Identify the rank step 3: if rank==1 then apply the formula , fib1[i]=fib1[i-1]+fib1[i-2] step 4: if rank==2 then apply the formula, fib2[0] = (pow((1+sqrt(5))/2,9) – pow((1-sqrt(5))/2,9))/sqrt(5) fib2[1] = (pow((1+sqrt(5))/2,10) – pow((1-sqrt(5))/2,10))/sqrt(5) step 4: Get the result from each computer in the cluster and assimilate them at the server. step 5: Verify the time taken for the completion of each task.

vii

Prime

Example:-

viii

Exercise 4 Aim:

Evaluate integral of a function

To find the integral of a function in parallel using a cluster of processors. Procedure: step 1 : Identify the function and integration limit.

( take any function for f(x) ex: Any curve fuction) step 2: Split the integral limit into ranges and assign each range to one processor. step 3: Get the result from each processor in the cluster and find the cumulative result at the master step 4: Verify the time taken for the completion of each task.

Prelab: Quadratic equation.

ix

Exercise 5 Aim:

Merging of Sorted Lists

To merge two sorted lists using a cluster of computers Procedure: step 1: Accept the list of numbers step 2: Divide the unsorted list into two sub lists of equal size. step 3: Sort each sub list using 2 processors. step 4: Let A[1 .. m] and B[1 .. n] be sorted sequences and compute the sorted merge C[1 .. m+n] of A and B. step 5: Verify the time taken for the completion of each task Algorithm merge(A, B) Input sequences A and B with n/2 elements each Output sorted sequence of A and B S ← empty sequence while ¬A.isEmpty() and ¬B.isEmpty() if A.first().element() < B.first().element() S.insertLast (A. remove (A. first ())) else S.insertLast(B.remove(B.first())) while ¬A.isEmpty()

x

S.insertLast(A.remove(A.first())) while ¬B.isEmpty() S.insertLast(B.remove(B.first())) return S

Prelab: Bubble sort.

Exercise 6 Aim:

Parallel Tree Traversal

To perform tree traversal using a cluster of computers Procedure: step 1: Create a binary tree for a given set of data step 2: Split the tree into left sub tree and right sub tree step 3: Assign them to one processor each step 4: Use any tree traversal method in processors step 4: Get the ordered data at the master end from each processor step 5: Verify the time taken for the completion of each task

xi

Algorithm:PRE-ORDER: Algorithm preorder(T, v) visit node v if T.hasLeft(v) preorder(T, T.left(v)) if T.hasRight(v) preorder(T, T.right(v)) // recursively traverse right sub tree POST-ORDER Algorithm postorder(T, v) postorder(T, T.left(v)) if T.hasRight(v) postorder(T, T.right(v)) // recursively traverse right sub tree visit node v IN-ORDER Algorithm inorder(T, v) if T.hasLeft(v) inorder(T, T.left(v)) // recursively traverse left subtree visit node v if T.hasRight(v) inorder(T, T.right(v)) // recursively traverse right sub tree // recursively traverse left sub tree // recursively traverse left sub tree

xii

INPUT: A binary tree T and a node v of T.

OUTPUT A preorder traversal of the tree shown in Figure visits the nodes in the following order:

A postorder traversal of the tree shown in Figure visits the nodes in the following order:

An inorder traversal of the tree shown in Figure visits the nodes in the following order:

Pre lab: Binary search.

xiii

Exercise 7 Aim:

Matrix Multiplication

To perform matrix multiplication using a cluster of computers Procedure: step 1: Accept two Matrices step 2: Decide on the number of processors in the cluster. step 3: Send the matrices and the range of values to be Processed by each processor step 4: Form the resultant matrix at the master end step 5: Verify the time taken for the completion of each task Algorithm:Begin For i