Computer Science 338 Parallel Processing Williams College Spring 2006

Readings

Be prepared to discuss the readings from the text and the notes on this handout during your tutorial meeting on February 7 and 8. In particular, we will discuss some of the questions in this section during the meetings.

Read Quinn Chapter 1.

Why Parallel Computing?

Let's consider a few "real world" examples:

• Taking a census of Williamstown.

  One person doing this would visit each house. count the people, and ask whatever questions are supposed to be asked. This person would keep running counts. At the end, this person has gathered everything.

  If there are two people, they can work concurrently. Each visits some houses, and they need to "report in" along the way or at the end to combine their information. But how to split up the work?

  • Each person could do what the individual was originally doing, but would check to make sure each house along the way had not yet been counted.
  • Each person could start at the town hall, get an address that has not yet been visited, go visit it, then go back to the town hall to report the result and get another address to visit. Someone at town hall keeps track of the cumulative totals. This is nice because neither person will be left without work to do until the whole thing is done. This is the master-slave method of breaking up the work.
  • The town could be split up beforehand. Each could get a randomly selected collection of addresses to visit. Maybe one person takes all houses with even street numbers and the other all houses with odd street numbers. Or perhaps one person would take everything north of Route 2 and the other everything south of Route 2. The choice of how to divide up the town may have a big effect on the total cost. There could be excessive travel if one person walks right past a house that has not yet been visited. Also, one person could finish completely while the other still has a lot of work to do. This is a domain decomposition approach.

  If there are a few dozen people, which approaches work well? How about 1000 people? 20,000 people?

• Grading a stack of exams. Suppose each has several questions. Again, assume two graders to start.
  • Each person could take half of the stack. Simple enough. But we still have the potential of one person finishing before the other.
  • Each person could take a paper from the "ungraded" stack, grade it, then put it into the "graded" stack.
  • Perhaps it makes more sense to have each person grade half of the questions instead of half of the exams, maybe because it would be unfair to have the same question graded by different people. Here, we could use variations on the approaches above. Each takes half the stack, grades his own questions, then they swap stacks.
  • Or we form a pipeline, where each exam goes from one grader to the next to the finished pile. Some time is needed to start up the pipeline and drain it out, especially if we add more graders. These models could be applied to the census example, if different census takers each went to every house to ask different questions.
  • Suppose we also add in a "grade totaler and recorder" person. Does that make any of the approaches better or worse?
• Adding two 1,000,000 ×1,000,000 matrices.
  • Each matrix entry in the sum can be computed independently, so we can break this up any way we like. Could use the master-slave approach, though a domain decomposition would probably make more sense. Depending on how many processes we have, we might break it down by individual entries, or maybe by rows or columns.
• Exercises 1.3 and 1.4 of Quinn.

In each of these cases, we have taken what we might normally think of as a sequential process, and taken advantage of the availability of concurrent processing to make use of multiple workers (processing units).

Parallelism adds complexity (as we will see in great detail), so why bother?

• want to solve the same problem but in a shorter time than possible on one processor
• want to solve larger problems than can currently be solved at all on a single processor
• some algorithms are more naturally expressed or organized concurrently

Some Basics

Sequential Program: sequence of actions that produce a result (statements + variables), called a process, task, or thread (of control). The state of the program is determined by the code, data, and a single program counter.

Concurrent Program: two or more processes that work together. Big difference: multiple program counters.

To cooperate, the processes need communication and synchronization, which can be achieved through shared variables, or message passing.

Hardware to run concurrent processes:

• single processor - logical concurrency (see CS 432)
• multiprocessor - shared memory
• multicomputer - separate memories
• network - slower communication

Computers may be classified as:

• SISD: single instruction, single data - one processor doing one thing at a time to one piece of data at a time
• SIMD: single instruction, multiple data - multiple processors all doing the same thing at the same time, but operating on different data. a.k.a. vector computers. Program operates in "lock step" on each processor.
• MIMD: multiple instruction, multiple data - multiple processors each doing their own thing.
• SPMD: single program, multiple data - not really a classification of the computer, but of a model used to program a MIMD computer. Multiple processors run the same program, but do not operate in lock step. a.k.a. the "interacting peers" model. This is the model we will use most in this class.

Some examples:

• SISD: Squall, Williams College: Macintosh PowerBook, 1.25 GHz Power PC G4
• MIMD: Bullpen Cluster, Williams College: 8-node Sun cluster, total of 20 450 MHz UltraSparc II processors (plus some older stuff)
• MIMD: ASCI Red, Sandia National Labs: 4600+ nodes, each with 2 Intel Pentium II Xeon processors, first TeraOp machine in 1997
• MIMD: ASCI White, LLNL: 512 nodes, each with 16 Power3 Nighthawk-2 processors, 12 TeraOps total, was number 1 until 2002
• Hybrid: Earth Simulator, Yokohama Institute for Earth Sciences, Japan: 640-node NEC system, each node with 8 vector processors, total of 5,120 CPUs, peak performance of 40 TeraOps

See http://www.top500.org/.

How to Achieve Parallelism

• Need to determine where concurrency is possible, then break up the work accordingly
• Easiest if a compiler can do this for you - take your sequential program and extract the concurrency automatically. This is sometimes possible, especially with fixed-size array computations.
• If the compiler can't do it, it is possible to give "hints" to the compiler to tell it what is safe to parallelize.
• But often, the parallelization must be done explicitly: the programmer has to create the threads or processes, assign work to them, and manage necessary communication.

Lab Tasks

There are several files to turn in for this assignment. They should all be included in a file named tut01.tar that will extract into a directory tut01 that contains files as specified below. You will submit tut01.tar using the turnin utility. Please use the filenames specified and be sure to include your name in each file. Please ask if you have any questions about creating the tar file or using the turnin utility.

Get started on these as soon as you can. You will need to ask questions. You should feel free to ask for help from and offer help to your classmates on all parts of this week's assignment. However, everyone should submit their own work.

1. Send me mail at terescoj@cs.williams.edu with a brief (a couple sentences) description of your level of experience with the Unix operating system and its variants. Also include list programming languages you have used and your proficiency in each, any experience you've had with parallel programming, and anything else you'd like me to know about your background.
2. Log into and familiarize yourself with your CSLab Unix account.
   1. First, make sure you can log into the FreeBSD systems in the lab (see the list of names under "Resources" on the Williams CS web pages if you wish to do this remotely).
   2. Read the links in the FreeBSD section of the "Documentation and FAQ for all platforms" on the Williams CS web page under "Resources." You may ignore the links related to "GJ".
   3. Forward your CSLab electronic mail to an address you read regularly, as I or the queueing systems may sometimes use your @cs.williams.edu address.
   4. Create a directory in your account for work from this class. Change the permissions on the directory so only the only operations permitted are reading and writing by you. Have your tutorial partner verify that he or she cannot access this directory.
   5. Log into the Solaris "Bullpen" cluster (login node: bullpen). This system uses a different password scheme, so you may need to see Mary in TCL 312 to get your account set up to be able to log in. Once you're in, you should find your regular CSLab Unix account files there.
   6. Log into the Linux "Dhanni" cluster (login node: cscluster). This uses the same password scheme as the FreeBSD lab, so you should have no trouble logging in. However, you should be placed in your "cluster home directory" under /dists/cscluster. If you don't, see Mary to get your account set up correctly. Make a directory here for your course work and set appropriate permissions.
3. Read the web page for the Bullpen cluster here. Don't worry if some of the terminology is not yet familiar.
4. Copy the C program here that computes the late penalties for this course to your CSLab Unix account. Compile and run it, redirecting your output to a file late.txt. Include this file in the tar file that you submit when you are finished. (1 point)
5. Copy the file /home/faculty/terescoj/shared/make-example.tar to your directory. It is a "tar file" of a small C program that demonstrates the use of multiple source files and Makefiles. Extract the files (tar xvf make-example.tar) and compile the program with make. Breifly describe in a plain text file tut01.txt how make uses the rules in the Makefile to produce the executable main. (1 point)
6. The Bullpen web page includes a simple parallel program called mpihello.c.
   • Copy mpihello.c to your account.
   • Create a Makefile that builds an executable called mpihello when you type make or gmake. Be sure to create a 64-bit MPICH executable and use the Sun compilers.
   • Run the program with two processes interactively on bullpen and redirect the output to a file mpihello.out.
   • Run the program three ways through the PBS batch system:
     • Create and run a PBS script twoonone.pbs that runs the program with two processes on any one node and sends the output to a file twoonone.out.
     • Create and run a PBS script fouronfour.pbs that runs the program with four processes on four different nodes, one process per node, and sends the output to a file fouronfour.out.
     • Create and run a PBS script all23.pbs that runs the program with 23 processes on all available nodes, one process per processor, and sends the output to a file all23.out. Hint: the cluster has two 4-processor nodes (ppn=4), six 2-processor nodes (ppn=2), and three uniprocessor nodes.
   • Include the files mpihello.c, Makefile, mpihello.out, twoonone.pbs, twoonone.out, fouronfour.pbs, fouronfour.out, all23.pbs, and all23.out in a subdirectory called bullpen in your submitted tar file. Do not include any ".o" files or the mpihello executable.
7. Read the web page for the "CS Cluster" under "Resources" on the Williams CS web page.
8. Next, write, compile and run a simple "Hello, World" program hello.c on the Dhanni cluster. To do this, you will need to create and submit a PBS script (compile.pbs) and write an appropriate Makefile to compile the program on a cluster node, then create and submit a PBS script to run the program on one of the nodes of the cluster. Call this script dhanni.pbs and save the output to a file dhanni.out. Submit these two PBS scripts, hello.c, your Makefile, and dhanni.out in a subdirectory dhanni in your tar file.

Remember, your tar file should be named tut01.tar, and when extracted should create a directory tut01 that contains the files you wish to submit. tut01.txt should be in the tut01 directory, and the bullpen-related and dhanni-related files should be in subdirectories bullpen and dhanni, respectively.