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:

• Refresher on pthread programming and thread synchronization
• Refresher on C programming, using libraries, and C programming tools
  • 2D arrays and file I/O in C
  • pointers, dynamic memory allocation, and pass by reference
  • debugging threaded programs (gdb and valgrind)
  • using getops library
• Designing and running experiments for scalability analysis.
• Evaluating experimental results.
• Writing a report describing your experimental design and results.

Contents:

• Lab 1 Overview
• Starting Point Git Repo
• Pthread Program
• Scalability Study and Experiments
• Running Experiments and Machines
• Scalability Report Requirements
• Useful Utilities and Resources

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.

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).

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.

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:

• who to see who else is on a machine you are running on, and try another machine if you are not alone.
• top to see the system load on the machine.
• top -H to see individual threads running on the machine (you can see your 4, 8, 16, etc running).

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.

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.tex contains some commented-out examples of latex formatting for figures, tables, lists, etc. Uncomment to try out.
• make report will compile report.pdf, make clean to clean up all pdflatex generated files.
• report.tex is a simplified version of my report template that has latex examples with some more features (here ~newhall/public/latex_examples/report ).
• see my latex links below for help with latex.

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?

For the pthread GOL implementation:

• The CS31 pthreads GOL lab and the CS31 sequential GOL lab assignment have hints and resource for implementing the GOL and pthreads GOL programs.
• The man pages for pthread functions are very helpful. In addition I have links to pthreads documentations and tutorials
• A guide for using gdb to debug pthread programs

• getopt command line parsing.

  I also have an example program using getopts that you can copy over and try out:

  cp -r ~newhall/public/getopts_example/* .
  

• Chapter 2 of Dive into Systems covers C programming, structs, pointers, pass-by-pointer parameters, switch statment, dynamic memory allocation, etc.
• man pages for C library functions and system calls, and be careful about who is responsible for allocating and freeing memory space passed to (and returned by) these routines.
• rand and srand: C library random number generator and seeding function (pass srand time(NULL) to seed with current time).
• Some C programming references.
• valgrind and gdb guides.
• atoi converts a string to an integer. For example, int x = atoi("1234"), assigns x the int value 1234. See the man page for more info and similar functions: (man 3 atoi)
• use perror to print out error messages from failed system calls:

  FILE *in;
  in = fopen(input_file, "r");
  if(in == NULL) { 
    perror("fopen failed. Exiting\n");
    exit(1);
  }
  

• gettimeofday: to add timing code around jut the GOL game playing part of your code (you should already have this in your CS31 starting point, see the CS31 GOL assignment page for more details if not)
• File I/O in C (you should not need to modify the file I/O part from your CS31 solution)
• make and writing Makefiles

For Running Experiments and Writing the Report:

• See the Machines for Experiments section above for information about choosing machines and running on chervil.
• See my Tools for examining system and runtime state for some tools you can use to determine the
  • 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 prints information about system memory use; cpuinfo prints information about the cpus, including L1 cache and cache line sizes.

    $ cat /proc/cpuinfo
    $ cat /proc/meminfo
    

• time ./a.out: show the total runtime, and user and system times associated with executing a.out.

• You can write and use shell scripts for running a set of experiments. With your repo is one example of a bash script for running a set of experiments that you can use as a starting point for different run scripts to run sets of your experiments. Here is another example.

  To run a bash script file, first make sure the script file is executable:

  ls -l     # lists file permissions (rwx)   x: means execute is set
  

  You can set execute permission on a file using chmod:

  chomd 700 testrun.sh    # sets rwx permission for file owner
  

  Then run the script at the unix prompt:

  ./testrun.sh
  

  It is often useful to redirect the output from these runs to a file. For, example to redirect stdout and stderr to a file named "resultfile":

  ./testrun.sh  &> resultfile
  

  Or to run your bash script inside script to capture its output to a file.

  See bash shell programing links for more information.

• See my Tools for running experiments and collecting performance measurements. screen, script, and bash scripts may be particularly useful. To avoid losing test results, I suggest either redirecting test output to a file, or running experiments in script, which will save all terminal output in a file (the default name is typescript). Just run script outfile, start your experiments on the command line, and then run exit to exit out of script. All the terminal output will be saved in a file named outfile. You can clean up the output file a bit by running dos2unix on it:

  $ script results
  Script started, file is results
  % ./run
    ...
  % exit
  Script done, file is results
  $ dos2unix -f results
  $ dos2unix -f results
  

  screen is useful for running a long set of experiments: you can run scripts from within a screen session late at night, wake up the next morning re-attach to the screen session and see the results.

• 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/.

• Code, test scripts, and report.tex:
  Before the Due Date, one of you or your partner should push your solution to github from one of your local repos to the GitHub remote repo. Be sure to do a make clean before you git add anything:

  make clean
  git add gol.c report.tex ...
  git commit
  git push
  git status
  

  See the Using git page "Troubleshooting" section for git help.

• Additionally, hand in a printout of your report.pdf in class.