Lab 2: Pthreads and Scalability Analysis

Contents:

./matrixmult -n 1024 -m 512 -t 4 -i 10

// given matrices A, B, and C of the following dimensions:
A[N][M] // N rows and M columns
B[M][N] // M rows and N columns
C[N][N] // N rows and N columns

// compute C = AxB
for i from 0 to N // for each row in C 
  for j from 0 to N // for each column in C 
    // compute the value of C[i][j] 
    val = 0.0
    for k from 0 to M  // num elms in row i of A and col j of B
       val += A[i][k]*B[k][j]
    C[i][j] = val

cp ~newhall/public/cs87/pthreads_example/* .

 usage:
    ./matrixmult -n n_dim  -m m_dim -t num_tids -i iters [-c]
       -n  n_dim       number of rows in A
       -m  m_dim       number of cols in A
       -t  num_tidst   number of threads
       -i  iters       number of iterations
       -c              optional arg to parallelize by columns of C (default is by rows) 
       -h:             print out this help message

• You must use a makefile. Your code should be free of valgrind errors, and be well designed and well commented.
• You should use mostly C to code up your solution. It is fine to use some features of C++, but use C's dynamic memory allocation for the arrays (malloc).
• You must dynamically allocate memory for two source 2D arrays, A and B, and for the result 2D array, C, using malloc. Also, make sure to use the dynamic memory allocation strategy that mallocs up a single chunk of contiguous heap memory for each of array (only 1 malloc each for A, B, and C). See Arrays in C.
• You will implement two different ways of parallelizing the computation: one partitions C's rows across threads, the other partitions C's columns across threads (i.e each thread computes the result for some number of C's columns). As an example, suppose that A is 8x5, B 5x8, and C 8x8, and that there are 4 threads. Here is how the threads (with tids 0-3) would be assigned to computing elements of C using row and column partitioning:

  row partitioning                        column partitioning
  ----------------                        ----------------
  0 0 0 0 0 0 0 0                         0 0 1 1 2 2 3 3  
  0 0 0 0 0 0 0 0                         0 0 1 1 2 2 3 3
  1 1 1 1 1 1 1 1                         0 0 1 1 2 2 3 3
  1 1 1 1 1 1 1 1                         0 0 1 1 2 2 3 3
  2 2 2 2 2 2 2 2                         0 0 1 1 2 2 3 3
  2 2 2 2 2 2 2 2                         0 0 1 1 2 2 3 3
  3 3 3 3 3 3 3 3                         0 0 1 1 2 2 3 3
  3 3 3 3 3 3 3 3                         0 0 1 1 2 2 3 3
  

  If the optional command line argument -c is given, run with column partitioning, otherwise run with row partitioning.

  You are welcome to implement and test other ways of partitioning of the problem, but the row-wise and column-wise partitioning are required.

• You should use arrays of double and initialize A and B to contain randomly selected double values. Here is how you can select random doubles between 0 and 1:

  double val = (double)(rand()/(RAND_MAX*1.0)); 
  

  I recommend picking random values between some small range (like (0.0,2.0)). You can test for correctness of your two parallelization schemes by commenting out the call to seed the random number generator so that every run of your program generates the same random sequence, and then print out the resulting C matrix at the end to see if the values are the same. You can just print out the same small chunk of C (like a 10x10 upper corner) and compare to avoid massive amounts of hard to read output.
• It is fine to only allow runs of your program for combinations of command line arguments that result in an even distribution of the computation across the threads. For example, given a C matrix with 512 rows where rows are distributed across threads, rows can be evenly distributed across 4 or 8 threads but not across 3 threads. It is fine to not allow runs with 3 threads in this case. If you add this type of restriction, then after parsing arguments your program should check for these types of "invalid" command line arguments and exit with a helpful error message for bad size combinations. You are also welcome to write your program so that it handles any array size for any number of threads too.
• You must perform a scalability study of your implementation that varies the size of the problem and the number of threads, and compares the two partitioning schemes for these different sizes. You will write a report describing your experiments, hypotheses, results and an explanation of what the results show and why. Run experiments on the lab machines with 16 processors so that you can test with the highest degree of physical parallelism (you should run some experiments with more threads then there are physical processors too).

watch -n 1 cat /proc/swaps
Filename                                Type            Size    Used    Priority
/dev/sda5                               partition       2072344 0       -1

As much as possible, it is good to run all your experiments on the same machine, or at least identical machines.

Written Report

1. A brief description of how you implemented the row-wise and column-wise thread assignment.
2. A description of the experiments you ran. What did you vary, what machine(s) did you run on, how many runs of each experiment. Also, briefly describe what you thought the expected outcome would be and why? It is fine if your expected outcome was different than what your experimental results show.
3. Experimental results: present your results AND describe what they show. You can use tables or graphs to present the data. Choose quality over quantity in the data you present. A couple tables with data that show scalability results in terms of number of threads and problem size is fine. It is also okay to present and discuss negative results..."we thought the X experiment would be better because...,but as shown in table 2, the Y experiment performed better. This is (or we think that this is) because ...". There is, however, a difference between negative results (well designed experiments that produce unexpected results) and bad results (results from poorly designed experiments).
4. Conclusions: what did you learn from your experiments? what do they say about the scalability of your solution? did they match your expectations? if not, do you have an idea of why not? did the row-wise and column-wise versions perform differently? explain why do you think they did or did not?

• time ./a.out: show the total runtime, and user and system times associated with executing a.out. As long as you remove all output (printf's) statements before experimentation, you can use this method to time your experiments.
• Use gettimeofday if you want to time specific sections of your code.
• some pthread programming links
  I recommend using Pthread's barrier synchronization primative for synchronizing threads, but you are welcome to use other pthread synchronization primatives if you'd like. Here are some code snippets for initializing and using a pthreads barrier syncrhonization:

  // declare a global pthread_barrier_t var
  static pthread_barrier_t barrier;
  
  // initialize it somewhere before using it:
  if(pthread_barrier_init(&barrier, NULL, num_threads)){
     perror("Error: with pthread barrier init\n");
     exit(1); 
  }
  
  // threads than can call pthread_barrier_wait to synchronize: 
  ret = pthread_barrier_wait(&barrier);
  if(ret != 0 && ret != PTHREAD_BARRIER_SERIAL_THREAD) {
    perror("Error: can't wait on pthread barrier\n");
    exit(1);
  }
  

• top, who, xload to get system usage info
  top -H: a dynamic display of information about system resource usage of the current threads that are the biggest consumers of CPUs. You should see your matrix multiply threads rise to the top. You can also use this to see if someone else is using a machine for experiments (in which case you should pick another one).
• /proc/ more useful system info. You can cat out files in here to find system-wide or per-process information: meminfo has information about system memory use, cpuinfo has information about the cpus, including cache line sizes.
• CS Project Etiquette Tools and Guidelines for using shared CS resources to run long-running, intensive applications.
• Tools for running experiments and collecting performance measurements
screen, script, ... I suggest running experiments in script, which will save all terminal output in a file (the default name is typescript). just run script, start your experiments on the command line, and then run exit to exit out of script.
• latex links. latex is Unix's document writing software. You do not have to use latex for writing your report, but it has very good support for some things that are common in scientific writing such as representing mathematical expressions, so you may want to give it a try. I have some example latex documents that you can grab to use as a starting point in ~newhall/public/latex_examples/.
• getopt command line parsing.
• rand and srand: C library random number generator and seeding function (pass srand time(NULL) to seed with current time).
• use perror to print out error messages from failed system calls.
• Here is a guide for using gdb to debug pthread programs

• You can write and use shell scripts for running a set of experiments. To run a shell script, first make sure that the shell script file has permissions set to executable (e.g. chmod 777 run.sh), and then just run it from the Unix prompt ( ./run.sh). Here is a example script for running a set of row-wise experiments (you may want to change thread and size ranges in your real experiments):

  #!/bin/bash
  
  for((n=256; n <= 2048; n=n*2))
  do
  for ((t=1; t <= 32; t=t*2))
    do 
       echo ""
       echo "matrixmult -n $n -m $n -t $t -i 10"
       time matrixmult -n $n -m $n -t $t -i 10
    done
  done
  

  See bash shell programing links for more information.

1. A README file with:
   1. Your name and your partner's name
   2. If you have not fully implemented some functionality, then list the parts that work (and how to test them if it is not obvious) so that you can be sure to receive credit for the parts you do have working.

2. All the source files needed to compile, run and test your code (Makefile, .c files, .h files, and optional test scripts). Please do not submit object (.o) or executable files (I can build these using your Makefile).

Turn in a hard copy of your written report at the beginning of class on Thursday.