CS40: Parallel Computation

Earlham College
Department of Computer Science
Ray Ontko and Joy Williams Lind, Instructors

Spring Semester 1999
Class: Dennis Hall, Room 214
Lab: Dennis Hall, Room 201
10:30-11:50 T Th

Syllabus

Why this course?

CS40: Parallel Computation focuses on the application of programming and problem-solving skills using parallel computation techniques to solve computationally intensive problems in a variety of disciplines. Parallel computation invites new ways of thinking about problems, and is an increasingly important skill in corporate and research environments. Students will learn about programming paradigms used in parallel computation, about the organization of parallel systems, and about the application of programs and systems to solve interesting problems.

The intended audience for the course includes students of computer science, math, physics, chemistry (and other disciplines like geology, biology, economics, sociology) who have an interest in computationally intensive numerical methods and simulations. Interested students outside Computer Science are particularly encouraged to participate.

Pre-requisite Courses

There is one pre-requisite course listed for CS40. CS38: Advanced Programming assures a level of mastery of programming. If you have significant programming experience in C, Fortran, Java, Pascal, or other similar languages, and have a strong interest in the application of parallel computation to a particular problem, you may also be sufficiently prepared for the course.

Students who have taken CS35: Programming and Problem-Solving may be able to learn the rudiments of programming in C or Fortran necessary to apply the PVM parallel programming library used in the course, but not without significant additional effort. Please consult with the instructors if you do not already know C or Fortran.

Overview

The course will be divided into two sections:

Part I: Introduction to Parallel Computation (8 weeks)
Part II: Parallel Problem-solving (6 weeks)

Part I will be primarily lecture/discussion format and will make extensive use of the two texts. Your primary activities will include reading and programming exercises.

During this portion of the course, you will also assist in the construction of a parallel computing cluster using off-the-shelf computer parts. You will be responsible for building and configuring at least one of the nodes in the cluster. This work will require some additional laboratory time outside of class during the first few weeks of the course.

Part II will be primarily seminar format. Each of you will be working on an individual projects which employ parallel techniques to solve a particular problem which you identified earlier in the course. Come prepared each day to discuss the challenges you face and the accomplishments you've achieved.

This course will use two texts (see below). One is an introduction to parallel programming and problem-solving. The other is a tutorial and reference guide for PVM (Parallel Virtual Machine), a library of sub-programs which facilitate parallel programming.

The course will include exercise problems to help you build a foundation for understanding parallel computation, lab projects to give you direct experience with the hardware you'll be using, a mid-semester examination to gauge your progress, and individual projects to help you apply what you have learned. Your full participation and engagement in the course is a critical part of learning the techniques of parallel computation and developing learning strategies that work in interdisciplinary collaborations.

Your grade for the course should reflect how well you apply yourself in each of these components of the course.

There are a number of technology-enabled components to the course: this syllabus and other handouts will be available, where practical, on the course homepage, and a listserv is available to facilitate e-mail correspondence between members of the class.

Finally, this syllabus concludes with the course schedule and information on how to reach us.

Texts

Required text:

Wilkinson, Barry, and Michael Allen. Parallel Programming: Techniques and Applications Using Networked Workstations and Parallel Computers. (Prentice-Hall, 1999).

Recommended text:

Geist, Al (editor), Adam Bequelin, Jack Dongarra. PVM: Parallel Virtual Machine : A Users' Guide and Tutorial for Networked Parallel Computing. (MIT Press, 1994).

Note: The recommended text is also available online in HTML form at http://www.netlib.org/pvm3/book/pvm-book.html.

Homepage

We have created a homepage for the course: http://www.cs.earlham.edu/courses/cs40/pvm/. We will place this syllabus, all handouts, the web pages you develop for your final projects, and other information related to the course there. If you know of any links that should be added to the page, please let me know.

Listserv

There is a listserv available to facilitate e-mail correspondence among members of the class. It is cs40@cs.earlham.edu. Feel free to use this listserv to carry on discussions related to the material, the course, or other topics of interest to class members. If everyone uses e-mail regularly, we will also distribute class announcements by e-mail when possible.

Requests to join or modify your subscription to the list should be sent to cs40-request@cs.earlham.edu. For a list of commands, send e-mail with the word "help" as the message body to this address.

Exercises

There are a number of exercise problems (often programming exercises) given in the text. As in many texts of this type, they are an excellent way to probe the depth of your understanding of the material and apply your new knowledge to novel problems. Read the text carefully and you should be able to do most of the exercises; the others may require you to think creatively to apply what you've learned.

Exercise programs are due almost daily. For each section in the reading, you will be asked to choose a program from those suggested in the text or recommended by us, and complete it. Take the time to examine each of the suggested exercises and pick one that you think will be sufficiently challenging and educationally appropriate for you. Note that which exercise you pick will be a factor in your grade for that exercise, so don't pick one that's so easy you won't learn much by doing it, or so hard that you won't complete it.

The exercises are an excellent way to prepare for the mid-semester exam.

The exercise problems and programs are worth 40% of your grade.

Mid-semester Examination

There will be an examination prior to the mid-semester break. This will cover all the material discussed in class or in the assigned reading or exercises.

The mid-semester examination will be given in-class and is worth 20% of your grade.

There will be no final examination.

Lab

The laboratory portion of the course will consist of constructing a node for our PVM computer cluster from off-the-shelf parts by following the instructions provided. In addition to assembling and connecting the computers, we will also install the necessary operating system and networking software. This will take place during the first few weeks of the course, and will require some time outside of class.

Your lab participation will be worth 10% of your grade.

Projects

The two programming projects are an opportunity for you to apply some of what you've learned in the course. The programs need not be large, but should apply the parallel techniques identified in the course and demonstrate your parallel problem-solving ability and represent your best programming skill.

Your programming projects will be due at three-week intervals in the final six weeks of the semester. Your program will then be available (via your web-page) for comment for two days, during which time you will be able to make changes based on comments from the others in the course. During the final week of the semester others in the class will attempt to use your program and offer their comments and criticism.

For each of your projects you should prepare a web page with an introduction to the subject matter of your project, an overview of the program logic and parallel techniques you used, and a summary of the results. Your page should also include links to the program text of all modules, any data used by the programs, and sample output. You may also include links to any other useful information you were able to find on your topic. The primary audience for your page is the other students in the class, although the page should be useful to others on the world wide web.

After you complete each project, you will have two days to review the projects of two other members of the class. You should direct your review comments to the person whose project you are reviewing, and send copies of the comments to both Ray and Joy. 20% of your grade for the programming assignment depends on the quality of your review.

Note that the objective of this assignment is NOT to produce a clever web page. The objective is to add value for your classmates (and to the world wide web in general) by providing content. For my favorite rant on bad web page design, see Eric S. Raymond's The HTML Hell Page. Consider using Weblint and Doctor HTML to help improve the HTML in your page.

The grading for the programming project will be divided between functionality, style, and peer review:

Functionality 60%
Programming style 20%
Review of others' work 20%

Note that the bulk of the grade is on the functionality of program. In other words, does the program work? If the program doesn't have to work, we're sure we can write one smaller, faster, and more quickly than the one you wrote (or at least no worse than). By definition, programs which don't work are useless.

A significant portion of your grade is for programming style, by which we mean the readability, maintainability, extensibility, and accessibility of the code. Few programs are ever the work of one person, and the most successful programs are often those that are modified and enhanced by others, both in industry and academia. Code which is unreadable or not understandable is ignored; write code which others would enjoy reading and enhancing.

Your grade for the programming projects will be based on the quality of your program and the quality of the criticism you offer others. As always, due means due (See below). Each of these programming project assignments are worth 15% of your grade in the course.

A word of warning: the functionality portion of the grade will not be a linear scale. If you set out to accomplish 10 things and only accomplish 5 of them, you will probably get 25% of the functionality points (assume an x**2 curve, 0<=x<=1). Programs which only half-work are often useless. So, choose the scope of your project carefully, and be sure to deliver what you set out to accomplish. As with many programming efforts, 80% of the project can be accomplished in 20% of the time; the remaining 20% often takes 80% of the time. Keep this in mind as you plan and work on your project.

Participation

This course is not only about learning the material in the texts, configuring a computer cluster, and writing a few programs. If it were, there would be very little reason for us to meet as a class. A good student could learn the material in about one fifth the time by studying the text carefully, working through all the problems and programming assignments in the text, and following up on many of the citations given throughout the text and in the bibliography. Indeed, this is the point of the text.

We meet as a class for a number of reasons:

To discuss the material and to share insights that each of us may have had while working through the text. Doing so enables us to learn more (or better) than we might as independent scholars. In discussion, we also have the opportunity to discover our misconceptions by expressing ourselves and listening carefully to others.
To present our research to one another. By presenting the fruits of our individual labors we take a stand for what we believe to be true and put our own work in the light for review by our peers. This is perhaps the most important aspect of method in computer science, or in any discipline for that matter.
To review the work of others. We learn not only by exploring material through independent scholarship, but also by seeing others' approaches and solutions to similar problems.
To develop our abilities to express our thoughts in real-time. It is one thing to be able to figure things out, and another to have the thoughts fully developed and ready for action. How well do we know the material if we can't engage in signficant discussion and inquiry?

Your full participation in the course, then, is essential. Engagement in the course includes, but is not limited to:

Preparation. Read the text carefully, inquisitively.
Punctuality. Show up to class on time.
Attendance. Come to all the classes.
Discussion. Come prepared to ask questions, and ask them. Come prepared to answer questions, and answer them.
Projects. Get excited about your project. Follow as many leads as you can, as deeply as you can. Make a contribution by summarizing what you have learned so that others may follow.
Programming. Write lucid programs that get directly to the core of the problem, that are readable by others, that you would be proud to publish to the world as an expression of your intellectual integrity and character.

Participation will be a factor of your grade, literally. Your grade on the subject matter will be multiplied by your grade in participation. 100% mastery of the material accompanied by 50% engagement in the course results in a 50% (i.e., non-passing) grade.

Grading

The primary goals of this course are to learn the material and the methods. We have attempted to create a mechanism for grading that supports a wide variety of learning styles, but you will not do well in this course (indeed you may not pass) without learning the material and participating. Participating without learning is not acceptable; learning without participating is not acceptable.

Therefore, your subject-matter grade will be multiplied by your participation grade.

Exercises 40%
Mid-semester Exam 20%
Labs 10%
Projects 30%

For your participation grade, we will assess your level of engagement in the course based on the criteria listed above under participation.

Again, your final grade for the course will be computed by multiplying your subject-matter grade by your participation grade.

Letter Grades

We will use a weighted average numerical grade when computing your grade for the course. For the purpose of assigning letter grades, the following conversion table will be used:

A+	greater than 97%	less than or equal to 100%
A	greater than 93%	less than or equal to 97%
A-	greater than 90%	less than or equal to 93%
B+	greater than 87%	less than or equal to 90%
B	greater than 83%	less than or equal to 87%
B-	greater than 80%	less than or equal to 83%
C+	greater than 77%	less than or equal to 80%
C	greater than 73%	less than or equal to 77%
C-	greater than 70%	less than or equal to 73%
D+	greater than 67%	less than or equal to 70%
D	greater than 63%	less than or equal to 67%
D-	greater than 60%	less than or equal to 63%
NP	greater than 0%	less than or equal to 60%

Show Your Work

When doing the exercise problems and those on the mid-semester exam, show your work. We will not give credit for the correct answer unless all the appropriate steps leading from known or given facts to the correct answer are shown. By definition, the answer is demonstrably correct only if you have shown it to be correct and true.

Due Means Due

Assignments will not be accepted for credit after they are due. Assignments are due during class when called for, or at the beginning of class if you are absent. Do not miss class to finish an assignment.

Course Schedule

The following schedule lists due dates for all assignments and reading. We reserve the right to adjust the schedule to meet the needs of the class, particularly with regard to the reading and problem assignments.

On days when problem sets are due, we will devote available time to answering specific questions about the problems, or other questions from the reading. We will address questions of interest to the largest number of class members present before addressing questions of individual interest.

Later in the semester the focus will shift toward your projects; always be prepared to discuss your own work. Although you will each have different subject-matter for your project, the methods you use will be similar; some discussion of research and programming method will be appropriate during that part of the course.

In general, the class sessions are available for you to get answers to questions you generate while reading, working on the problems, or from your research and programming. Always be prepared to discuss the material from the text and your own work in depth. We will facilitate or lead discussion which we think will be most valuable for the class as a whole. Be sure to bring your brain and your most inquisitive self. Make the most out of coming to class; it's your time.

Week 1 Jan 11-15

Thu: First day of class (Ray)

Week 2 Jan 18-22

Tue: read Wilk 1.1-1.3; prob 1-1 through 1-6 due (Ray)
Thu: read Wilk 1.4-1.6; prob 1-7 through 1-12 due (Ray)

Week 3 Jan 25-29

Tue: read Wilk 2.1, Geist 3; program due (Joy)
Thu: read Wilk 2.2, Geist 4; program due (Joy)

Week 4 Feb 1-5

Tue: read Wilk 2.3, Geist 5
Thu: read Geist 4.1; Wilkinson 3-x Algorithm #1 due

Week 5 Feb 8-12

Tue: read Geist 4.2; Wilkinson 3-x Algorithm #2 due
Thu: Standard Deviation Crowd Algorithm due; Linux Kernel Installation due

Week 6 Feb 15-19

Tue: Standard Deviation Crowd Program due
Thu: Linux Additional Software Installation due

Week 7 Feb 22-26

Tue: tba
Thu: tba

Week 8 Mar 1-5

Tue: tba
Thu: Mergesort algorithms discussion.

Week 9 Mar 8-12

Tue: Mergesort discussion.
Thu: Mergesort program due.

Week 10 Mar 15-19

Tue: Spring Break (no class)
Thu: Spring Break (no class)

Week 11 Mar 22-26

Tue: Project 1 choice due. Lecture.
Thu: 5 minute project introduction presentation by each student.

Week 12 Mar 29 - Apr 2

Tue: 10 minute project progress report by 1/2 of students.
Thu: 10 minute project progress report by 1/2 of students.

Week 13 Apr 5-9

Tue: Project 1 due. 5 minute project results presentation by students.
Thu: Project 2 choice due. Lecture.

Week 14 Apr 12-16

Tue: 10 minute project introduction presentation by 1/2 of students.
Thu: 10 minute project introduction presentation by 1/2 of students.

Week 15 Apr 19-23

Tue: 10 minute project progress report by 1/2 of students.
Thu: 10 minute project progress report by 1/2 of students.

Week 16 Apr 26 - 30

Tue: Project 2 Due. 5 minute project results presentation by students.
Thu: Review. Last day of class.

How to Reach Us

Joy's office is Dennis 202E. Ray is sharing an office, Dennis 202D, with Tim McLarnan. Both offices are in the Math/Computer Science area in Dennis Hall, 2nd Floor.

We check e-mail several times each day, and e-mail is often the best way to get a specific answer to a specific question. Our e-mail addresses: rayo@ontko.com and willijo@earlham.edu. Note that rayo@cs.earlham.edu and ontkora@earlham.edu may also work, but these are forwarded hopefully to the first address listed above.

Ray's campus mailing address is Drawer 98. Joy's is Drawer 106. Due to the open access of our mailboxes, we do not recommend that you place your assignments there. If you want to turn in an assignment when we're not around, please place it under the door to Joy's office with the following clearly shown: your name, the name of the course, and the date and time you left it.

Joy's campus extension is 1683. Ray does not have a campus extension. If you wish to leave voice mail for Ray, dial his company voice mail at 966-6221, voicemail box 9001.

Ray's phone number at Ray Ontko & Company is 935-4283. Please feel free to call him there. When he is not on campus, it's where you're most likely to find him, often past 5:00 pm. If he's not there, leave a message including the phone number he should call and when he might reach you there.

Ray's home phone number is 935-1598. Joy's home phone number is 935-1318. Please don't call either of us before 9:00 am or after 9:00 pm unless it is an emergency. If it is an emergency, please do not hesitate to call.