Homework 1: Parallel and Distributed Computing
DUE: See exact time on blackboard
ICSI 520
This homework has three parts. Part 1: Optimize a given problem without threads. Parts 2, 3:
Introduction to pThreads
Part 1
Your task is to optimize matrix multiplication (matmul) code to run fast(er) on a single processor core of
Ulabany’s RIT cluster.

We consider a special case of matmul:
C := C + A*B

where A, B, and C are n x n matrices. This can be performed using 2n3 floating point operations (n3 adds,
n3 multiplies), as in the following pseudocode:

for i = 1 to n
for j = 1 to n
for k = 1 to n
C(i,j) = C(i,j) + A(i,k) * B(k,j)
end
end
end

Instructions
 Your grade will mostly depend on two factors:
o Performance sustained by your code on the cluster,
o Explanations of the performance features you observed (including what didn't work)
 I will not grade submissions that do fewer computations than the 2n3 algorithm
 Your code must use double-precision to represent real numbers
 Use gcc as your compiler
 Besides compiler intrinsic functions and built-ins, your code must only call into the C standard
library.
 The matrices are all stored in column-major order
 Submission will include the following
o The naïve implementation of above algorithm
o The optimized implementation
o Document describing your observations, speedup and the optimization technique used
o Follow other submission instructions at the end

Part 2
In this part you will learn how threading helps speed up computations by leveraging multicore systems.
You will use pThreads.
You will do a serial and a parallel implementation and show the speedup.
• Write the following programs in C
• A serial program
• Write a function void SumUpto(int number). This function sums all the numbers
from 0 to “number” and prints the sum on stdout
• Call this function from main. The value for “number” should be passed in as a
command line parameter.
• Once this works, enclose the function call in a for loop (0 to p)
• The for loop upper limit (p) parameter should be passed in as a
command line parameter (if no parameter is specified, use default as 2)
• Time the execution (start of main to end of main) – time in microseconds.
• See timing example on blackboard
• A parallel program using pThreads
• Write the thread function void * SumUpto(void *arg). Note this is same as
above. You can pass in the “number” as the thread argument (arg)
• Create threads in main using the SumUpto function
• Use command line argument to determine how many threads (p) to
create. If no argument is specified, use 2
• The value for “number” should also be passed in as a command line
parameter.
• Measure the execution time and compare to corresponding serial
implementation using the table below





Fill the following table and submit it on blackboard along with your code.
Number (summing
upto this number)
#Times executed (#
of threads) p
Serial execution time
(microseconds)
Parallel execution time
(microseconds)
1000 2
10000 2
100000 2
1000000 2
1000 8
10000 8
100000 8
1000000 8
1000 16
10000 16
100000 16
1000000 16
1000 36
10000 36
100000 36
1000000 36
•

Part 3
Given is a matrix of NxN integers (you create this). The matrix is initialized to random values between 1
and 10 inclusive. The problem is to calculate the distribution of values, i.e., the number of elements that
are 1, the number that are 2, etc.
Divide the work up among P worker processes (threads). The matrix is shared by the workers.
You may NOT assume that N is a multiple of P. Divide the matrix into almost P equal-size strips of rows.
Each worker will ONLY calculate the distribution of its strip(s). When all workers have completed their
tasks, only one worker should accumulate and print the distributions.
Use the C rand number function with seed to generate psuedo-random numbers.
The values of N and P should be read as command-line arguments. Write the results to standard output.
Run experiments for N between 64 - 1000 and P between, 2 to 64. (NOTE: for serial code, P =1)
N and P are command line args
Describe your results. What do you observe? Why?
Create tabular results (can add more rows if needed)
N P Serial execution time
(microseconds)
Parallel execution time
(microseconds)


















Grading
Serial Implementation 20%
Parallel Implementation 20%
Correct execution Parallel (speedup
achievements)
35%
Correct serial execution 20%
Code clarity 10%
Observations 5%

Observations can be submitted as a text file or as comments on blackboard. These are your observations
on the results you achieve.
Code clarity includes
 Use of variable names
 Function naming
 File names
 Formatting
 Comments where needed
 Makefile
Late submissions do not get ANY points for bonus (if applicable) plus they are subject to at least 20%
grade deduction as per syllabus.
Reminder: If one or any of your binaries don’t execute on student.rit.albany.edu, you get 0 points for
this and any other homework where that happens.
Submission:
Your submission should include the following:
1. Makefile that builds all required binaries:
a. Part_N_type.out where N is the homework part and type can be serial/parallel
2. Serial code source file(s) for each part of the homework
3. Parallel code source file(s) for each part of the homework
4. Document (word or excel) detailing the tabular results
All of the above should be zipped up into one file and uploaded on blackboard
If you are doing the bonus, add a comment in your code about it. (if applicable)
Naming convention of your zipped file – If you do not follow this, you get zero points:
FirstName_LastName_Homework_.zip
Where n is the homework number.