CS87 Lab 1:

Pthreads and Scalability Analysis

Code Due: Wednesday Jan 29 before 11:59pm
(push to your Lab01 git repo by then)

Report Due: Thursday Feb 6 at the beginning of class
(turn in a hard copy of your report in class, and push report.tex source to your Lab01 repo before 1:15pm)

Lab 1 Partners:

This lab will be done with your lab 1 partner

Here is some documentation that I give to CS31 students about working with partners. It is a brief guide for good practices, and my expectations for how CS students should be working together on labs.

Lab 1 Goals:

Contents:

Lab 1 Overview
The main focus of this lab is on designing and running experiments to evaluate scalability of a multi-threaded discrete event simulator. You will begin by making some minor modifications to your pthreads GOL program from CS31, and then evaluate its scalability.

The coding part:
You and your partner will start with one of your solutions to the CS31 pthreads GOL lab. And also see the CS31 sequential GOL lab for input file format and GOL rules. It is possible that your pthreads gol lab may have had slightly different specifications than this one from Fall'17, which is fine for your starting point for this lab. If you used the ParaVisi gui animation in your lab, you will not need that feature in this lab.

At a minimum you will change your CS31 code in the following ways (more details here):

  1. Use different command line options and use the getops library to parse command line options.
  2. Covert your torus GOL world to a 2D GOL world. This means that edge and corner cells will have fewer neighbors than middle cells.
  3. Fix any bugs and inefficiencies with your CS31 solution, and fix any problems with poor modular design, with missing error handling, and with missing comments.

The main part of this lab consists of:

  1. Developing hypotheses about the scalability pthreads GOL
  2. Designing experiments to test your hypotheses about scalability.
  3. Running initial experiments and analyzing the results to see if you need to re-design your experiments.
  4. Collecting and evaluating experimental results.
  5. Presenting your experimental study in a written report.


Lab 1 Starting Point Repo
  1. Both you and your partner should:
    1. Create a cs87/labs subdirectory on the CS system: 
      mkdir cs87
mkdir cs87/labs
cd cs87/labs
    2. Get your Lab01 ssh-URL from the GitHub server for our class: cs87-s20
    3. On the CS system, cd into your cs87/labs subdirectory
    4. Clone a local copy of your shared repo in your private cs87/labs subdirectory: 
      git clone [your_Lab01_URL]
      Then cd into your Lab01-you-partner subdirectory.
    If all was successful, you should see the following files when you run ls: 
    Makefile report.tex run.sh testedges.txt
    If this didn't work, or for more detailed instructions on git see: the Using Git page (follow the instructions for repos on Swarthmore's GitHub Enterprise server).

  2. Next, decide whose pthread GOL program you want to use as a starting point. Read over the pthread code requirements for this lab (particularly (4)), run your solutions, look at the code, run in valgrind, and then together decide whose solution you will use as your starting point. Leave a top-level comment in .c and .h file(s) indicating the authors of your starting point code.

    Whichever one you are starting with (or if you want to start from scratch together that is fine too), copy the over pthreads gol.c (and any other .h or .c files) into your cs87 Lab01 repo to use as the starting point for this lab. Make sure the copied version compiles and runs (and fix the Makefile if not), then add these files you copied over to your git repo, commit, and push: 

    git add gol.c
git add Makefile
git add mytestfile.txt
...
git commit
git push
    Your partner should now be able to do git pull to grab what you pushed to your shared repo.

    You may also want to add to your repo config files that you may have from CS31 for initializing a GOL board (you can easily create new ones too, and you will want to create new ones for large scale experiments).

Pthread GOL Program Requirements
Your pthreads GOL solution should meet the requirements of the CS31 pthreads GOL lab assignment, with the following changes:
  1. Turn your torus world into a 2D world. In the 2D version of GOL, edge cells only have 5 neighbors and corner cells have only have 3. For example, the x's mark the set of neighbors for the three grid cells indicated with a 1 in this world (note: 3, 5 or 8 neighbors): 
    1  x  0  0  0  0  0  0  0
x  x  0  0  0  0  0  0  0
0  0  0  0  0  0  0  0  0
0  0  x  x  x  0  0  0  0
0  0  x  1  x  0  0  0  0
0  0  x  x  x  0  0  0  0
0  0  0  0  0  0  0  0  0
0  0  0  x  x  x  0  0  0
0  0  0  x  1  x  0  0  0
    You can test correctness with the testedges.txt file (patterns on edges should not wrap around the world across iterations).

  2. Your code should compile with the -Werror=vla gcc flag, like in these examples (don't remove this from your Makefile): 
    # compile with -g for testing and debugging:
gcc -g -Wall -Werror=vla -o gol gol.c -lpthread

# with optimizations on -02, -g off for experiments:
gcc -O2 -Wall -Werror=vla -o gol gol.c -lpthread
    If it doesn't, it means you have one or more functions in your program that use run-time variable sized array allocation on the stack. This is bad. Instead, space should be dynamically allocated on the heap (via malloc) and then passed into functions that need to use it. You should fix this.

  3. Support the following command line options, using this syntax ( options in [ ] are optional), and use the getops library to define command line options and parse argv command lines: 
       ./gol -t t { -n n -m m -k k [-s] | -f infile} [-x] [-c] 
       -t  t:      number of threads
       -n  n:      number of rows in the game board
       -m  m:      number of columns in the game board
       -k  k:      number of iterations
       -s:         initialize to oscillator pattern (default is random)
       -f infile:  read in board config info from an input file
       -x:         disable ascii animation (printing out board every iteration) 
                   (default is to run with animation/printing)  
       -c:         do column partitioning (default is row portioning)
       -h:         print out this help message
    This syntax for command line arguments supports command line arguments in any order and optional command line arguments. You will use getopt to parse command line arguments (more details below).

    The example getopt code uses a C switch statement. If you are not familiar with switch statments, see Chapter 2.9.1 switch statements in Dive Into Systems textbook.

    NOTE: if your CS31 pthreads gol also included a run mode with a ParaVisi gui animation, you DO NOT need to support this run mode for this assignment. If you choose to leave it in, then you should add another command line option to enable this run mode (-g). Otherwise, remove the Paravisi gui code paths from your gol.c file. I suggest making this change before the others, and compile and test out your gol with the CS31 command line options, then commit these changes before doing the others.

  4. Review your CS31 solution and fix any bugs (including running through valgrind), and fix any inefficiencies in its parallelization. Your solution should only malloc up space once for the shared game board(s), and malloc up this space before any pthreads are created. All functions that need to access the board(s) should be passed the board(s) as parameters. There should be no mallocs in the function(s) that solves a single iteration of GOL. Make sure that no calls to usleep are made when the program is run without printing out the game board at each iteration. And make sure it is implemented using good modular design and is well commented. Fix it if not.

Command Line Options

The command line options specify how to initialize the game and how to run the simulation.

There are two ways to run gol and initialize the game board:

  1. The -f command line option means that the GOL problem size and initial state are read in from a file: 
    ./gol -t 16 -f infile  # init to values read in from the file "infile"
  2. or the -n -m -k [-s] command line options are used to specifying the dimensions, number of iterations, and the starting point world initial configuration: 
    ./gol -t 4 -n 20 -m 30 -k 100 -s   # init a 20x30 board to oscillator pattern
./gol -t 4 -n 20 -m 30 -k 100   # init a 20x30 board to random pattern
                                # about 25% of randomly selected cells 
                                # to 1 works okay, but you decide
                                # use column-portioning across threads
These two modes are independent---you cannot have a command line with both the -f and -m options.

The -t option is required and works with both initialization modes.

The -x and -c options are optional and work with either initialization mode. The -x option is necessary when running timed experiments. If the -f option is NOT used, then the board is initialized to one of two patterns:

  1. The -s option specifies that the board should initialize a single oscillator pattern in (or close to) the center of the board. The oscillator pattern is 3 live cells in a row, either vertically or horizontally.

  2. If -s isn't specified, then the board should be initialized to some random pattern. To generate random numbers in C use the rand function. You will also likely want to seed the random number generator by calling srand and passing it the current time value. Here is some example of how to call srand and rand: 
    #include<stdlib.h>
#include<time.h>

srand(time(NULL)); // call once in your program to seed rand num generator

int val = rand();  // returns the next random number between 0 and RAND_MAX
    Use the random value in some function to decide if a cell is 1 or 0. The mod operator in C is % (e.g. 10 % 3 is 1) Be careful in your random init function to make sure you are not setting too large a proportion of the world's cell to live...all cells may die after a few iterations if the world is too overpopulated.

Here are some example command lines: 

# initialize 20x30 board to an oscillator pattern, run with 8 threads
# print out board to stdout after each iteration:
./gol -t 8 -n 20 -m 30 -k 100 -s  

# initialize program from data read in from "infile", run with 16 threads,
# column partition, do not print any output to stdout for this run
./gol -t 16 -f infile -c -x 

# run with 4 threads, init board from file, row partition, do not print to stdout
./gol -t 4 -f infile -x
Your program should handle badly formed command lines (e.g. print out an error message and exit instead of using incompatible or incomplete command line options).

File Format

The input file format is identical to that of the sequential (and pthreads) GOL labs from CS31: GOL file format.

Additional Code Requirements

In addition to the requirements listed above, your GOL solution should:
  1. Have timing code in your solution around the GOL main computation (don't include grid initialization or outputting the result to a file). Use gettimeofday.
  2. Calls your program makes to usleep and system("clear") to implement animation of the game board should only be made when the program is run in board printing mode; runs with the -x command line option should not trigger any calls to usleep).
  3. Use perror to report errors from system calls
  4. Detect and handle all errors. Your program can call exit(1) if the error is unrecoverable (after printing out an error message of course) This means that any time you call a function that returns a value, there should be a check for error return values and they should be handled: do not just assume that every function call and every system call is always successful.
  5. Your solution should be correct, robust, and free of valgrind errors
  6. You code should be well-commented code and use good modular design. See my C documentation for C references and a C code style guide.

Scalability Analysis Study, and Experiments
You will design and run experiments that will answer questions about the scalability of your solution. Design experiments that answer questions about scalability in different ways. Some parameters to consider varying in your experiments:
  1. The grid sizes. Try different powers of two (64, 128, 256, 512, 1024, 2048, ...) You do not have to try every power of two between your min and max sizes, but run a several intermediate sizes between your smallest-sized and largest-sized boards.
  2. The number of threads. Again, increase by powers of two: (1, 2, 4, 8, 16, 32, ...), and again you do not need to include every power of two between your min and max.
  3. The number of iterations (try a couple different values that show differences across runs). You should run each gol experiment for at many iterations, so that there is some synchronization in runs and you can see synchronization effects on scalability. When you experiment with the scalability of board sizes, and are scaling up to very large sizes, you may want to reduce the number of total gol iterations to something relatively small so that the really large board size runs don't take forever. However, you should still have several iterations per run in this case.
  4. Compare row-wise vs. column-wise board partitioning.
When running scalability studies you need to make sure that you have problem sizes that are large enough to result in fairly long run times for at least some numbers of threads. For example, if the single threaded run takes 1.3 seconds and the 16 threaded run takes 1.2, it is pretty difficult to draw any conclusions about scalability by comparing these two small runtimes. Instead, you want some runs that take many seconds to many minutes.

Running Experiments and Machines

As you run experiments, make sure you are doing so in a way that doesn't interfere with others (see the Hints and Resources section below for some tips about how to ensure this). Also, remember to remove all output statements from the code you time (run without printing the board or anything else).

You should run multiple runs of each experiment. For example, don't just do a single timed run of 16 threads for 512x512 and 10 iterations, but run this same experiment multiple times (5 or 10 times each). The purpose of multiple runs is to determine how consistent your times are (look at the standard deviation across runs), and to also see if you have some odd outliers (which may indicate that something else was running on the computer that interfered with a run, and that you should discard this result).

Be careful to control experimental runs as much as possible. If other people are using the machine you using to run experiments, their use can interfere with your results. Here are some resources to see what is going on on machines:

Also, make sure that the grid sizes are not too large to fit in RAM. I don't think this really will be a problem, but double check your a run with your largest sizes before running experiments to see if the system is swapping. To do this as you run, in another window run: 

watch -n 1 cat /proc/swaps
Filename                                Type            Size    Used    Priority
/dev/sda2                               partition       2072344 0       -1
If you notice the Used value going above 0, your grid sizes are too big to fit into RAM (or there are too many other memory intensive applications running on this machine), and you need to find an idle machine.

Machines for Experiments

You should use CS lab machines as develop your set of experiments, any lab machines are fine to use. However, please avoid running intensive experiments on CS lab machines in 240, 256 or Clothier during times when classes are scheduled in those room.

In addition, we have a few machines in the server room that are only for cs87 students. Use these for both your initial experiments, and some final experiements Each of these machines have 8 or 12 cores, you should share them all for testing, but I've assigned you each a "first choice" machine for your testing and experiment development to distribute the load. If a machine is down email `local-staff`, and again, you should all share these machines (the 12 node one in particular may be one that other teams will want to try out). 

cardamom 8   : Gus and Ford
crabby 8     : Christina and Lamia
cucumber 8   : Keon and Jonathan
elderberry 8 : Ayaka and Minh
hyssop 8     : Rich and Brendan
mint 8       : Haochen and Danielle
parsley 8    : Kevin and Zach
stew 8       : Kat and Kyra
zucchini 12  : Sam and Mickey
For at least some, and possibly all, of your final experiment runs use chervil. You may use chervil to develop and test your set of experiments too, but please be mindful that all groups need some alone time on this machine for final experiment runs. I will likely set up a google signup sheet next week to reserve times to run your experiements alone on chervil.

chervil: is a physical 16 core, and 32 hyper-threaded "core", machine that only CS87 students have access to. This machine will provide an isolated platform for final experiment runs. Each group will need to take turns on this machine for running their final set of experiments, so as not to interfere with each other's results.

I'll add a google sign-up sheet for you to reserve some runtimes on chervil over the next week.

For running on lab machines, take a look at the Lab Machine specs page contains information about most of the CS lab machines, including the number of CPUs (click on the processors link). We have machines with 6-12 cores, and you have access to chervil with 16 physical cores and 32 hyper-threaded cores. Trying some experiements on machines with different numbers of cores.

As much as possible, it is good to run all of one set of your experiments on the same machine, or at least on identical machines. However, it may be intersting to see a few runs of the same problem size on machines with different numbers of cores.

Finally, be aware of other groups wanting to run experiments on the 8 and 12 node machines reserved for our class and on chervil. So, please don't run experiments on a machine for hours and hours or days and days. And, logout when you are not using a machine to run experiments. You can run who to see if someone is logged in, and run run top -H or htop to help you guess/see if a machine is currently used, before deciding it is okay for you to use to run super intensive experiments. And please log out of CS lab machines when you are done using them so that it is easier for others to tell if the machine really is being used or someone just didn't logout and left atom and web browsers running (this is the normal state in which you will find most CS lab machines, and it is often difficult to tell if someone is actually using the machine when you ssh into one...just check by running who and top, and guess as best you can). And remember, for the machines reserved for 87, someone may be logged out but running a lot of experiements in screen, so make sure to run top for a minute or so to be certain it is not in use.

Written Report Requirements
Write a 3-4 page report (3 is min, 4 is max) that describes the results of your experimentation. You must use the latex and the report.tex template included in your Lab 1 repo.

Report Requirements

Your report should include the following sections:
  1. Introduction: a brief introduction to what this report is about
  2. A description of the experiments you ran. For each experiment presented:
    1. What is the hypothesis the experiment is designed to test?
    2. What was the experiment?
    3. Why does this experiment test this hypothesis?
    4. What did you vary, what machine(s) did you run on, how many runs of each experiment.
    5. 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 graphs and/or 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).

    Also, here is a nice description of strong and weak scalability. You do not need to present your result data in terms of strong and weak scalability functions. Speed-up (Sequential Time/Parallel Time), or even average run times (with stddev), over different axes of change may be more useful for this assignment. However, it may be useful to know the difference between these to when presenting or discussing some of your results in your report.

  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?

Useful Utilities

For the pthread GOL implementation:

For Running Experiments and Writing the Report:


Submit