Parallel Processing
Spring 2013

Assignment 03

Distribution date: 21.02.2013 Due date of Part A: 07.03.2013

Due date of Part B: 22.03.2013

Marks : 300

Read Carefully:

Instructions: (Bonus Point 10)

1- You only need to submit programs of part A on March 7, 2013 and after mid term you need to compile & run your programs on case HPC cluster. 2- Part A & Part B have equal marks. i.e each has weight age of one assignment.

3- If two assignment solutions are found to be copied then both will be awarded zero and a disciplinary action will be taken against both students. Be careful regarding plagiarism. TA will check Report plagiarism by turnitin and object code of the programs will be checked by another tool. If you will only change the variables of other assignment it will be caught by code plagiarism checker. So don’t give your assignment solution to other students otherwise both students will be affected.

4- Late assignment will NOT be accepted, what so ever is the reason.

5- Name your code files as “yourname_Questionxx_PartX” e.g Muhammad_imran_question01_Part_a”. (1.5)

6- Make a folder and name it as “Ass03_yournameRooll_YourName”. e.g ‘Ass03_Muhammad_Imran_F-06_047”. Place your codes files. (1.5)

7- Email zip file to mimran_047@yahoo.com & mfarooqarif@gmail.com

8- Subject field of your email must be “PP_Ass03_PartX_Yourname” (2)

9- Email must be received till 12:30 pm on due date. After that I will not accept the assignment.

10- TA will have right to call any student for explanation and running of his/her codes & report. If students will fail to explain and run the programs he/she will be awarded zero.
Part A

Due date of Part A: 07.03.2013

Marks Part A: 150

Question # 1 (Marks 25)

A 1024-node parallel computer has 40 bit RISC processor with clock rate of 200 MHz and local memory of 64 MB. Memory access time for local load/store is 5 clock cycles. While overhead of 12 clock cycles is required to initiate transmission of a request to remote node. The bandwidth of the interconnection network is 75MB/sec. In a set of program 10 % instruction are load and 8 % are stores. If 250,000 instructions are executed compute:

a) Load/store time if all accesses are to local nodes.

b) Repeat part (a) if 15 % of accesses are to the remote node.

Packet format is given below.

|Source address (Bytes ) |Destination address (Bytes) |Payload (Bytes) |
| | |(note: Ack code is of one byte) |

Programming:

Objective:

The objective of the programming Questions in this assignment is to get you familiar with parallel programming using OpenMP & MPI.

Question # 2 (Marks 30)

Threshold Detector System of an image

Build a threshold detection system of an image which counts the no of pixels above a threshold level of 128(decimal). Image has 512 x 64 pixels and each pixel has 8 bit gray code intensity level.

a) Write Pseudo code & C code for sequential program to solve the above problem where input matrix of pixels intensity values is generated by the random no. generator

b) Solve the above problem using SPMD approach; hence give

a) Pseudo code

b) C code Using OpenMP for a single node (Quad core system)

Question # 3 (Marks 30)

Dot Product of two vectors

Compute the dot product of two vectors A and B, each of 220 integer elements where each element is less than 100.

a) Write the pseudo code & C code for sequential program to solve the above problem where vectors A and B are generated by random no. generator

b) Solve the above problem using SPMD approach; hence give

a. Pseudo code

b. C code Using MPI for a 32 cores cluster

Where Input vectors A and B are generated at P0 by the random no. generator and task distribution & final result should also done by P0

Question # 4 (40)

Matrix-Vector Multiplication

Multiply matrix A of size 1024 x 2048 with a vector B of size 2048 x 1 where vectors A and B are generated by random no. generator where each element is less than 100 .

a) Write the pseudo code and C code for sequential program to solve the above problem

b) Solve the above problem using SPMD approach; hence give

• Pseudo code

• C code Using MPI and OpenMP

Note: use MPI among the nodes and Open MP within node to implement where

• Matrix A and vector B are generated by P0

• P0 distribute the tasks among nodes using MPI

• Each node use OpenMP to build the partial result.

• P0 collects the results from nodes and builds the resultant vector

(Cluster consist of eight nodes, each having four cores)

NOTE: your program Codes should be properly commented (25 points)

Deliverables:

• Solution of Q#01

• Program codes files for part a) and b) of Q#02 - Q#04

• A report (in PDF) which must includes pseudo codes you have used to write the programs for part a) and b) of Q#02 - Q#04

.

Part B

Due date of Part B: 22.03.2013

Marks Part B: 150

Objective:

The objective of this part is to get you familiar how to compile, execute and analyze the parallel programs ( OpenMP, MPI & hybrid programs) on a Cluster.

Question 01

a) Run and execute your written codes for Question#2-4 on CASE HPC cluster

b) Analyze the sequential & parallel execution times.

For sequential and parallel execution time measurement exclude the time for input matrix generation and display of the output matrix.

Deliverables:

• Source Code files for part a) and b) of Q#02 - Q#04

• Your programs code must be running on CASE HPC cluster of 32 cores.

• Input matrices and exe files for part a) and b) of Q#02 - Q#04

• A report (in PDF) which must includes

o Pseudo codes you have used to write the programs for part a) and b) of Q#02 - Q#04

o Results of part a) and b) of Q#02 - Q#04.

o ,sequential and parallel execution times of Q#02 - Q#04

o Your comments on the results.