Computer Science 341-02 Parallel Processing Mount Holyoke College Fall 2007

As with all of our weekly assignments, this document tells you what you will need to read, write, code, and otherwise prepare for the next week's lab and discussion meetings. It includes some work (in the "Lab Tasks" section) that should be submitted by the deadline in the header. Readings and other preparation for our meetings must be done before the actual meetings. In each meeting, I will have some points I will be sure we discuss, but you are encouraged to come with questions and ideas for discussion as well.

Be prepared to discuss the readings from the Quinn text and the notes on this handout during our meeting on September 13. In particular, we will discuss some of the questions in this section during the meeting.

Read Quinn Chapter 1.

Why Parallel Computing?

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

• Taking a census of South Hadley. 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 west of Route 116 and the other everything east of Route 116. 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.
  Discussion item: 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.
• Discussion item: 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

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

Big difference: multiple program counters.

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

• single processor - logical concurrency (see Operating System course)
• 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. Also known as: 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. Also known as the "interacting peers" model. This is the model we will use most in this class.

Some examples:

• SISD: Pre-"multi-core" desktops and laptops.
• MIMD: MHC Cluster: several nodes, some have UltraSparc II processors, some have Intel x86 processors.
• 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/.

• We need to determine where concurrency is possible, then break up the work accordingly
• This is 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.

Instead of a class meeting on Tuesday, September 11, we will meet in my office (Clapp 220) and proceed to a computer lab to work on these lab tasks.

There are several files to turn in for this assignment, due at 9:00 AM, Thursday, September 13, 2007. They should all be included in a file named assignment01.tar that will extract into a directory assignment01 that contains files as specified below. You will submit assignment01.tar by e-mail as an attachment. 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 attaching it to an e-mail.

1. Log into and familiarize yourself with your MHC Cluster account. When you are ready to do this, I will provide you with a username and an initial password.
   1. First, make sure you can log into the head node, accessible as mhccluster.teresco.org.
   2. 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.
   3. Log into the main Solaris cluster node (login node: bullpen).
   4. Log into a FreeBSD cluster node (login node: joba).
2. Read the web page for the MHC cluster here. Don't worry if some of the terminology is not yet familiar.
3. Copy the C program here that computes the late penalties for this course to your MHC cluster 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)
4. Copy the file /cluster/home/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 assignment01.txt how make uses the rules in the Makefile to produce the executable main. (1 point)
5. The MHC cluster 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.
   • Run the program with two processes interactively on bullpen and redirect the output to a file mpihello-bullpen.out.
   • Run the program with two processes interactively on head and redirect the output to a file mpihello-head.out.
   • Run the program three ways through the SGE batch system:
     • Create and run an SGE script twoonone.sge that runs the program with two processes on any one node and sends the output to a file twoonone.out.
     • Create and run an SGE script twoontwo.sge that runs the program with two processes on any two nodes and sends the output to a file twoontwo.out.
     • Create and run an SGE script fourontwo.sge that runs the program with four processes on two different nodes, two processes per node, and sends the output to a file fourontwo.out.
   • Include the files mpihello.c, Makefile, and all required SGE scripts and output files in your submitted tar file. Do not include any ".o" files or the mpihello executable.

Remember, your tar file should be named assignment01.tar, and when extracted should create a directory assignment01 that contains the files you wish to submit.