18-645:  How to Write Fast Code

Assignment 4:- Shared Memory Parallelism

 

 

 

 

General Instructions.

–  A PDF report and a zipped file is to be submitted via Canvas on the due date.  Both files should be named asg 4 《your  andrew  id> with the approprate file extensions.

–  The zipped file should contain the following

1.  Source code (appropriately named) for all implementations;

2.  A Makefile that compiles all implementations on one of the machine on the ECE cluster;

3.  Readme.txt that explains how to run your implementations.   (Optional,  but strongly recom- mended)

–  Each program has to be named using the exact name found in parenthesis in the question.

1.  OpenMP parallelism The source file (triangle.c) contains a function for computing the number of triangles in a graph stored in compressed-row-format. Parallelize the function using the three methods of parallelization in OpenMP

(a)  Parallel For.(tri for.c) Parallelize the triangle counting function with the parallel  for con-

struct.

(b)  Parallel Region.(tri par.c) Parallelize the triangle counting function by creating parallel regions

in the function.

(c)  Tasks.(tri task.c) Parallelize the triangle counting function by making the body of the loops into tasks.

For all three implementations, provide plots of the execution time of your implementations for 1, 2, 4, 8, 16 and the total number of hardware threads available on the provided datasets.

Hint:

–  All iterations of the outer loop can be done in parallel but a reduction of across iterations must be performed

–  There is no reduction clause for task parallelism.

–  The perfomances are not expected to be identical.

2.  Effects of scheduling Recall that there are different scheduling mechanism that can be chosen with OpenMP pragmas. Update your parallel  for implementation with the following scheduling schemes:

(a)  Dynamic scheduling.  (tri dyn.c)

(b)  Chuck scheduling with chunk size of 1.  (tri one.c)

(c)  Chuck scheduling with chunk size of N/p.(tri Noverpc) N is the number of vertices in the graph, and p is the number of threads being used.

Provide plots of timings for for 1, 2, 4, 8 16, and the total number of hardware threads available on the provided datasets.