Dakota State University
Madison, SD
57042-1799
(605) 256-5166
rolfe@dsuvax.dsu.edu
http://www.dsu.edu/~rolfe/index.html
Current information
Timothy J. Rolfe
Professor, Computer Science
Eastern Washington University
Cheney, WA 99004-2412
(509) 359-6162
Electronic mail: TRolfe@ewu.edu
WWW home page: http://penguin.ewu.edu/~trolfe/
Copyright 1994 by the Small College Computing Symposium
Permission to make printed or digital copies of all or part of this material for educational or personal use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies include this notice on the first page.
Appears in SCCS Proceedings: 27th Annual Small College Computing Symposium (SCCS, 1994), pp. 118-125.
This paper is available as a (six-page) word-processor file in RTF format. Click here.
ABSTRACTPhysics sets limits on computer technology for the speed of computations: if nothing else, the speed of transmission of a signal in a conductor or ultimately the speed of light itself. Thus if we wish to steadily increase the size of the problems we undertake with computers, we must look beyond the single processor to a way to share the computation of one problem among several processors.Physical limitations require parallel processing to allow solution of very large compute-bound applications. To prepare our students for this environment we need to find some way to expose them to parallel processing, but budget limitations may preclude purchase even of low-end parallel computers. The Oak Ridge National Laboratory's Parallel Virtual Machine (PVM) system provides a parallel programming environment usable both for instruction and for research using existing resources.
A keyword search under InfoTrack EF using the General Periodical Index-A [1] finds 45 entries on parallel processing or parallel computers in 1993 alone. Beside the expected journals such as PC Week and Electronic News, articles appear in such disparate sources as The Banker, The Economist, The New York Times, and the Oil and Gas Journal.
A similar search under the February 1994 database of technical journals within Computer Select encounters 679 articles. [2] One excellent article that the search uncovered is Kevin Dowd and David Radin's "The Cray T3D: from fringe to forefront" in which they provide an overview of parallel processing as a prelude to their discussion of Cray Research's new product. [3]
Thus parallel processing is evidently a current trend in computing. As such it is one for which we should train our students. But limitations in a small college's computing budget may even rule out lower-end parallel machines such as the MASPAR or transputers. Still, the computing environment even on a small college campus probably does have the components necessary for a parallel programming environment on which students can experience the unique problems, challenges, and rewards of breaking a problem into parallel pieces.
Oak Ridge National Laboratory has developed a message-based parallel processing system called "Parallel Virtual Machine" (PVM). [4, 5] (Comparable systems available for purchase include Scientific Computing Associates' Network Linda and Parasoft's Express. [3]) PVM provides a distributed parallel environment of loosely coupled heterogeneous computers. The component computers in the virtual parallel machine are networked computers and workstations running UNIX (OSF/1) or UNIX-like operating systems that support interprocessor communication through sockets.
PVM daemon processes on the component computers of the virtual machine provide the necessary message passing for the distributed parallel processing. These PVM processes do not require anything beyond user privileges on any of the machines, and PVM even allows for password access to component machines, should security considerations require it.
PVM is available in source code at no cost through electronic mail requests to netlib@ornl.gov; it is also available via netlib (electronic mail) or anonymous ftp from a number of other sites (for instance, netlib.att.com). Included in the distributed code are the necessary files to bring PVM up under a wide variety of systems. [6]
While version 3.2.6 of PVM is presently available, the following discussion is based on version 2.4.2 which the author used within an Operating Systems course in the Spring 1993 semester. [7]
Under a message-based parallel processing system like PVM, the programmer is responsible for all of the details for decomposing the over-all problem into components to execute in parallel as well as for the necessary communications among those components. PVM itself provides a channel for process initiation, termination, and communications.
The virtual machine used by PVM is composed of one or more networked computers capable of communicating through sockets. The user initiates the PVM environment by executing the PVM daemon process pvmd on one machine, identifying at that time the machines that will comprise the virtual machine. (Version 3 of PVM provides for run- time configuration of the virtual machine.) The initial pvmd process then initiates daemon processes on all of the component machines.
The machines comprising the virtual machine need not be of the same type. PVM allows a heterogeneous mix of machines and does the necessary translations among the various internal data representations. Each machine is identified by its "architecture", and the programmer when initiating a component process within PVM is free to request a specific architecture or even a specific machine within the virtual machine.
The cooperating processes interact with PVM by calls to library procedures delivered with PVM. These processes may be initiated explicitly by the user (as indeed at least one of them must be, typically the host/master process) or may be initiated by another process under PVM (typically the node/slave processes).
Each cooperating process is responsible for "registering" with the daemon process on its machine, which then communicates with the daemons throughout the virtual machine. PVM identifies the component as an "instance" of a particular process, so that each component is identified by a character string naming the process type and a number giving the instance of that process type.
Interprocess communications are handled by having the originating process generate a message by library calls that fill a buffer with heterogeneous data (character strings, integers, single- and double-procession floating point numbers). The originating process can then either send the buffer to a specific process (identified by process type and instance number) or broadcast the buffer to all processes of a particular type. Part of the procedure call that sends the buffer also associates with that message a message number so that the receiving process can distinguish in-coming message types. PVM uses a non- blocking send; i.e., the originating process does not wait on receipt of the message but immediately continues with its own processing.
The receiving process has several options available. It may check for in-coming messages without accepting one (and without being blocked), or it may actually accept a message. Further, it may do this for a single message type, for a list of message types, or for any message. If the receiving process attempts to accept a message when there is as yet no message of the requested type, the process blocks until such a message is received.
In addition to process communication, PVM also allows for barrier synchronization, should one wish a number of component processes to begin a code segment at the same time. It also allows for individual processes to wait for a particular named event, which another process generates through a "Ready" call.
The major bottleneck in parallel processing is communication among the cooperating processes. Problems lending themselves to such coarse-grain parallelization are those that require little communication among those processes.
The flavor of programming in parallel might be better shown by an example. One specimen problem requiring minimal interprocess communication is that of generating the Mandelbrot set. [3] An implementation under PVM might break out functionalities thus.
Host Process
Node Process
PVM is process-oriented in its implementation of parallelism rather than machine-oriented. This means that one can develop parallel applications even within a single-machine environment. The cooperating processes will in fact all execute on the same processor and the problem solution will show no speed-up due to the parallel execution, but the programmer will still generate a system runnable in a truly parallel environment. Hence the programmer is faced with most of the problems encountered in writing parallel code.
Thus even if one only has access to a single-processor computing environment, under PVM one can still develop --- and teach the development of --- parallel programs.
At Dakota State University, PVM was used as one component in the upper-division undergraduate Operating Systems course in the Spring 1992 semester. Even though the DSU UNIX computing environment was then limited to one MicroVAX-II under Ultrix and one Sun SPARCstation-SLC under SunOS, students were able to develop and test parallel applications involving multiple cooperating processes communicating through PVM.
As part of their introduction to the PVM system, the students were shown implementations of several parallel programming tools and problems in PVM: the Semaphore abstract data type, used in the Readers/Writers problem [8] (which also included a "shared memory server"), and the Producer/Consumer problem [9]. They were then required to develop two processes to fit into an implementation of Lamport's bakery problem [10].
Students were required to generate the code for the "Clerk" processes and the "Customer" processes, as noted in Tanenbaum's posing of the problem. To allow them to test their code within a functioning system, though, they were provided with several other processes and the messages types and information that those processes expected.
Later in the semester there was a second PVM programming assignment. In the problems for the chapter on deadlocks, Tanenbaum restates Dijkstra's problem of two-way traffic on a single track in terms of baboons crossing a single rope. [11] The statement of the problem breaks it into two phases: (a) prevent collisions, and (b) prevent starvation. The students were expected to develop the full parallel system themselves, but they were reminded of the similarities between this problem and the Readers/Writers problem (and they had access to the complete PVM solution of that problem). Eventually it was necessary to provide explicit code for the first phase of the problem (collision avoidance) to insure that all of the students would be able to handle the second part (starvation avoidance).
Given the subject matter of the course, the problems posed were not in fact ones for which one could expect any speed- up on parallel execution but instead examined multiprocessing problems. As such, the students were not required to break a sequential problem apart into parallelizable segments. One could easily envision, however, a numerical analysis course in which one could easily address such issues. Even here, a single-processor PVM system would allow code development, though of course one could not measure speed-up without access to several processors.
PVM also provides a usable parallel machine for student and faculty research, not just classroom exercises. Indeed, the author's first exposure to PVM was in the summer of 1992. William Reinhardt of the University of Washington had a large molecular dynamics program that he wanted to execute in parallel on a set of RS/6000 processors. While Professor Reinhardt had purchased Parasoft's Express as the parallel environment to do this, initial problems using Parasoft Express with RS/6000 computers made the parallel development of code under PVM desirable. (The problems with Express were later resolved.)
PVM provides a fairly painless mechanism to increase workstation utilization by allowing workstations assigned to student program development (typically an I/O bound application) to provide nodes in a virtual machine devoted to a student or faculty research problem. [12] Since the UNIX system allows processes to decrease their execution priorities, the presence of such a compute-bound process need not significantly degrade the response time of the workstation for program development. (On the other hand, the research application would have to have fairly robust error recovery since it is hard to protect against the student's hand moving to the power switch.)
Of course if the research is explicitly on parallel programming and the speed-ups achieved, the nodes would have to be cleared of any other activity. There are, however, other interesting problems amenable to parallel solution. One category could be simulations in which generation of the single time step is computationally intensive, especially if the only non-local information required is that of adjacent cells, as in weather simulations. Even if global information is required, as in astrophysical calculations or some molecular dynamical calculations, one is still trading order(N) communications to speed up order(N^2) or worse calculations, so that there are problem sizes above which parallel execution is faster, as was indeed the case for the molecular dynamics calculations that the author worked with in the summer of 1992.
The Summer 1992 work with William Reinhard at the University of Washington was funded under an ACS fellowship.