CIS-4230/5230 Homework #1 (Introduction)

Due: Friday, February 2, 2024

Read the section Why Parallel Computing? in Parallel and High Performance Computing by Zamora and Robey.

Also in my tutorial about pthreads, read the section on creating and terminating threads.

The main purpose of this assignment is to get you up to speed with our development environment. The actual programming is relatively straightforward.

Point your SSH client to lemuria.cis.vermontstate.edu and log in using the credentials I provided in email (or your existing credentials if you already had an account before this class). Change your password using the passwd command.

SSH to one of the nodes using a command such as ssh nodeN where N is a digit 1–4. Verify that your new password works on the nodes. If it does not, try your original password. Account information is supposed to synchronize between Lemuria and the nodes; let your instructor know if it does not.

Type exit to log out of the node and return to Lemuria. For the first part of this course, we'll be using just Lemuria, but you may find it interesting to also test your programs on the nodes.

Note that the nodes "see" your normal home directory. Lemuria is exporting your home directory to the nodes, and thus acting as a file server to the nodes. This means any files/programs you create on Lemuria will be immediately available to you on the nodes without you having to explicitly transfer them there.

Note that you can develop your programs on your own system using whatever tools you like, but be aware their behavior may be quite different in your environment as compared to on Lemuria. Parallel programs are much more sensitive to OS and hardware specifics than ordinary programs. You may see very different performance characteristics as you move your program from system to system.
Lemuria (and the nodes) have a console-only interface. As such, you'll need a non-graphical text editor for writing and editing programs on those platforms. There are several editors installed including emacs, vim, and nano. Feel free to use whichever editor you like. The nano editor is the easiest to use, but emacs and vim are much more powerful.

If you don't have a preference and are up for learning one of the Unix power editors, I recommend vim. It has a steep learning curve but is extremely powerful. Take the time you need to get to know it, but don't expect that to happen in one sitting. There are quick reference cards on the Internet such as this one. Download and print one of those cards for easy reference. Consider working through a Vim tutorial or two.

If you do try to learn vim, I also recommend installing Vim for Windows on your Windows system, and plan to use vim and nothing but vim for your editing needs this semester. It's the best way to really get to know the editor.
We will be using Git to obtain some of the sample code and supporting libraries we need. Set up the global Git configuration to include your name and email address. See my Git document for the specific commands required. After setting up Git, use the following commands in your home directory:
```
  $ mkdir Projects
  $ cd Projects
  $ git clone https://github.com/pchapin/solarium Solarium
```
This creates a clone of my Solarium sample program. You don't need to do anything with this repository right now, but I will use it later as a source of examples.
Create a suitable work area in your home directory on Lemuria. I recommend creating a cis-4230 directory to hold all your material for this course with a C subdirectory for your C language files. For example, while in your home directory use the command:
```
  $ mkdir -p cis-4230/C
```
The -p option causes mkdir to create any intermediate directories it needs, as necessary

By putting all your work in the cis-4230 directory, you can use the script backup.sh to create a single backup file of your work that you can then transfer to another machine. I strongly recommend you do this regularly. Lemuria is ancient and is starting to show signs of impending failure. You don't want to lose your work if one day Lemuria simply dies.
In your cis-4230/C directory, create a further subdirectory named Sum and populate it with the Sum sample program and its Makefiles. Sum is an Eclipse/CDT project, but its Makefiles have been pre-generated, so you can build the program without Eclipse. While the directory structure I'm recommending might seem overly complex, it sets the stage for additional samples of various kinds later.

Build the Sum sample program, both Debug and Release configurations, and verify that it works. To build the program, change into the appropriate subdirectory (Debug or Release) and run make all. Just using make by itself will build the "clean" target, which is the first target defined in the makefile. Note that the makefile was generated by Eclipse/CDT on a Windows system, so it refers to the "Cygwin GCC." However, it invokes plain GCC, which on Lemuria will be the Linux version. The two versions are compatible, so you can ignore what you see about Cygwin.
Modify the Sum sample program to use different sized arrays ranging from 100,000 to 100,000,000 elements, changing the size by a factor of 10 each time. For this assignment it is fine to just modify the array size and recompile the program each time.

For each run compare the serial and parallel times, using both parallel versions, and for each array size compute the speedups: the ratio of serial time to parallel time. For example, if the parallel program is twice as fast, the speedup would be 2.0. You can do this computation manually; you don't need to modify the program to do it—unless you want to. You should run the program three times for each array size and report the maximum speedups of the three runs (why not the average?).

Note that you should change ITERATIONS as you change SIZE. For example, when SIZE shrinks by a factor of 10, ITERATIONS should grow by a factor of 10 to keep the overall execution time about the same. If the overall time is too short, it may not be accurate; the timing library we are using only has a precision on the order of tens of milliseconds. Be sure the execution takes long enough to be noticeable (i.e., several seconds at least).
(OPTIONAL) If you dare, try using an array size of 1,000,000,000 (one billion). WARNING: Such an array will consume 8 GiB of RAM. Lemuria has 24 GiB of RAM installed, so in theory, this should not be a problem. However, if the system begins to swap physical memory to the swap device, your timing results will be severely distorted and hard to interpret. On the other hand, if this size works well, it will give you another data point to consider.
Submit a table showing array size, serial time, parallel times (two of them), and speedups (maximum of three runs) for each array size you tried. If you are feeling adventurous, plot a graph of speedup vs array size (with array size on a log scale) for both the 2-thread and fully "dynamic" thread versions.

What you should see is the effect of thread creation overhead. For small arrays, the speedup is poor because the time required to create the threads is a fixed cost independent of array size and thus has a larger impact on the smaller (faster) sizes. The effect should be extreme in the fully dynamic case where a large number of threads are created to handle a small problem.

However, for the larger arrays the speedups should improve and, for the very largest sizes, the benefit of creating more than two threads should start to become apparent.