Parallel computers are easy to build - it's the software that takes work.
I've also organized a range of seminars, and directed numerous undergraduate and graduate research projects. These included REU (Research Experience for Undergraduates) projects, one of which was written up in the EECS departmental newsletter as an example of what undergraduates were capable of doing.
One of the more unusual graduate seminars I've taught here at Michigan was a summer project in which four MS-level graduate students took turns picking computer science topics and doing readings and making an overview presentations with questioning from the others (and me). Each student was required to pick a few diverse topics, so that the overall effect was to learn a little bit about a wide range of computer science. I learned a lot from the students.
As part of this, we discuss basic issues in experimentally measuring and predicting the performance of algorithms, and in tuning performance. This area is the basis for the new electronic journal, the ACM Journal of Experimental Algorithms, and is one of the up-and-coming areas in the field of algorithms.
Since the running time of an algorithm is a random variable, this requires that we address some statistical issues, though no prior statistical background is required. Random run-time resource requirements have important effects that must be taken into account, yet the topic is rarely addressed in computer science courses.
Students are expected to be active participants in the seminar, and most of the presentations are by students, not the professor. Grading is based primarily on presentations and reports.
Some students decide to continue their project as an REU project or as a directed study.
Prerequisites: EECS 477 or Math 416 or EECS 586 or equivalent.
Students did a significant amount of reading and classroom presentations. This was a cooperative learning seminar in which all were expected to actively participate and students had to teach the teacher since he was new to the subject. However, he knows how to ask questions. There was also a term project, which was done in small groups.
The course emphasizes the design and analysis of algorithms. We examine common, key, problems, such as sorting, searching, finding shortest paths, determining a convex hull, or scheduling a set of tasks, and then develop efficient algorithms for them. This involves showing that the algorithms are correct, analyzing their time and space requirements, and determining lower bounds for the problems to show that no other algorithm could be significantly better. Systematic techniques for algorithm development, such as divide-and-conquer, dynamic programming, and greedy algorithms, are covered, as are a variety of analysis techniques such as solutions of recursive equations, worst-case and expected-case analyses, amortized analyses, competitive analyses, lower bounds, and adversary arguments.
The final portion of the class covers NP-completeness, starting with definitions and techniques for proving that a problem is NP-complete. Then we consider various ways to approach NP-complete problems, such as approximation algorithms or fast expected time algorithms.
Parallel computers are easy to build - it's the software that takes work.
This is a graduate or advanced undergraduate level course that I usually teach each Fall term. About half the class is from Computer Science and Engineering, and half is from a wide range of other areas throughout the sciences and engineering. For a CSE student, the course satisfies general 500-level requirements for the MA and PhD, or computer science electives for the BA and BS. For a student in the Scientific Computing program and various other programs, it satisfies computer science distribution requirements. For a student in the CSCS program, it is an approved course related to complex systems. Students typically range from undergraduates through postdocs, and occasionally faculty sit in on the course as well.
The course covers a wide range of aspects of parallel computing, with the emphasis on developing efficient software. Because there is not a single parallel computing model, we also have to learn some about various parallel architectures, since there is significant hardware/software interaction. We examine reasons for poor parallel performance, and various techniques for improving it.
Programs are run on machines available locally, and this is an ever-changing collection. Most are run by the Center for Advanced Computing. This class was part of the justification for NSF funding of this center.
An important part of the class is the term project. This can be in almost any aspect of parallel computing. Students have done projects in parallelizing large serial codes, designing new parallel algorithms, proposing new operating system features, doing performance evaluation of a parallel computer, etc. Often students can integrate this project in with their other work, so, for example, it may be part of their thesis. Many other students have used this to start a new research area, and have ultimately gotten a thesis in the topic. Many of the projects have lead to publications, and a few have resulted in awards of various types. Some of the application-oriented projects have included parallelized simulations of reactors, oil fields, protein folding, car crashes, galaxies, bone fractures, etc.; optimized designs of traffic flow, patient allocation in a clinical trial, error-correcting codes, etc.; image processing, learning algorithms, and so forth.
As for jobs, most of the students go on to use parallel computing in their future employment, with many of them getting their jobs specifically because of this expertise. These jobs tend to be very well-paying, and are in medium to large corporations, consulting firms, scientific laboratories, the computing industry, etc. I make various postings of such jobs available to the students.
For additional information, see the course homepage. I also have a somewhat whimsical explanation of parallel computing.
Teaching modules have been developed for a few different problems, such as sorting and addition. There is essentially no cost to utilize them (just a few 3x5 cards, for example), despite the fact that students learn a little about the workings of parallel computers costing megadollars. These modules, and their use in classrooms, are described in various publications. Most of the work in refining these ideas, and all of the classroom presentations, has been done by my colleagues Greg Bachelis, David James, and Bruce Maxim. Part of the inspiration for this was my use of this approach in college classes, at all levels, since about 1980. At public lectures I've even had deans participate as part of a parallel computer.
 |
Copyright © 1995-2005, Quentin F. Stout |