hankd@engr.uky.eduAlthough this HOWTO has been "republished" (v2.0, 2004-06-28) to update the author contact info, it has many broken links and some information is seriously out of date. Rather than just repairing links, this document is being heavily rewritten as a Guide which we expect to release in July 2004. At that time, the HOWTO will be obsolete. The prefered home URL for both the old and new documents is http://aggregate.org/LDP/
Parallel Processing refers to the concept of speeding-up the execution of a program by dividing the program into multiple fragments that can execute simultaneously, each on its own processor. A program being executed across n processors might execute n times faster than it would using a single processor.
Traditionally, multiple processors were provided within a specially designed "parallel computer"; along these lines, Linux now supports SMP systems (often sold as "servers") in which multiple processors share a single memory and bus interface within a single computer. It is also possible for a group of computers (for example, a group of PCs each running Linux) to be interconnected by a network to form a parallel-processing cluster. The third alternative for parallel computing using Linux is to use the multimedia instruction extensions (i.e., MMX) to operate in parallel on vectors of integer data. Finally, it is also possible to use a Linux system as a "host" for a specialized attached parallel processing compute engine. All these approaches are discussed in detail in this document.
Although use of multiple processors can speed-up many operations, most applications cannot yet benefit from parallel processing. Basically, parallel processing is appropriate only if:
The good news is that if all the above are true, you'll find that parallel processing using Linux can yield supercomputer performance for some programs that perform complex computations or operate on large data sets. What's more, it can do that using cheap hardware... which you might already own. As an added bonus, it is also easy to use a parallel Linux system for other things when it is not busy executing a parallel job.
If parallel processing is not what you want, but you would like to achieve at least a modest improvement in performance, there are still things you can do. For example, you can improve performance of sequential programs by moving to a faster processor, adding memory, replacing an IDE disk with fast wide SCSI, etc. If that's all you are interested in, jump to section 6.2; otherwise, read on.
Although parallel processing has been used for many years in many systems, it is still somewhat unfamiliar to most computer users. Thus, before discussing the various alternatives, it is important to become familiar with a few commonly used terms.
SIMD (Single Instruction stream, Multiple Data stream) refers to a parallel execution model in which all processors execute the same operation at the same time, but each processor is allowed to operate upon its own data. This model naturally fits the concept of performing the same operation on every element of an array, and is thus often associated with vector or array manipulation. Because all operations are inherently synchronized, interactions among SIMD processors tend to be easily and efficiently implemented.
MIMD (Multiple Instruction stream, Multiple Data stream) refers to a parallel execution model in which each processor is essentially acting independently. This model most naturally fits the concept of decomposing a program for parallel execution on a functional basis; for example, one processor might update a database file while another processor generates a graphic display of the new entry. This is a more flexible model than SIMD execution, but it is achieved at the risk of debugging nightmares called race conditions, in which a program may intermittently fail due to timing variations reordering the operations of one processor relative to those of another.
SPMD (Single Program, Multiple Data) is a restricted version of MIMD in which all processors are running the same program. Unlike SIMD, each processor executing SPMD code may take a different control flow path through the program.
The bandwidth of a communication system is the maximum amount of data that can be transmitted in a unit of time... once data transmission has begun. Bandwidth for serial connections is often measured in baud or bits/second (b/s), which generally correspond to 1/10 to 1/8 that many Bytes/second (B/s). For example, a 1,200 baud modem transfers about 120 B/s, whereas a 155 Mb/s ATM network connection is nearly 130,000 times faster, transferring about about 17 MB/s. High bandwidth allows large blocks of data to be transferred efficiently between processors.
The latency of a communication system is the minimum time taken to transmit one object, including any send and receive software overhead. Latency is very important in parallel processing because it determines the minimum useful grain size, the minimum run time for a segment of code to yield speed-up through parallel execution. Basically, if a segment of code runs for less time than it takes to transmit its result value (i.e., latency), executing that code segment serially on the processor that needed the result value would be faster than parallel execution; serial execution would avoid the communication overhead.
Message passing is a model for interactions between processors within a parallel system. In general, a message is constructed by software on one processor and is sent through an interconnection network to another processor, which then must accept and act upon the message contents. Although the overhead in handling each message (latency) may be high, there are typically few restrictions on how much information each message may contain. Thus, message passing can yield high bandwidth making it a very effective way to transmit a large block of data from one processor to another. However, to minimize the need for expensive message passing operations, data structures within a parallel program must be spread across the processors so that most data referenced by each processor is in its local memory... this task is known as data layout.
Shared memory is a model for interactions between processors within a parallel system. Systems like the multi-processor Pentium machines running Linux physically share a single memory among their processors, so that a value written to shared memory by one processor can be directly accessed by any processor. Alternatively, logically shared memory can be implemented for systems in which each processor has it own memory by converting each non-local memory reference into an appropriate inter-processor communication. Either implementation of shared memory is generally considered easier to use than message passing. Physically shared memory can have both high bandwidth and low latency, but only when multiple processors do not try to access the bus simultaneously; thus, data layout still can seriously impact performance, and cache effects, etc., can make it difficult to determine what the best layout is.
In both the message passing and shared memory models, a communication is initiated by a single processor; in contrast, aggregate function communication is an inherently parallel communication model in which an entire group of processors act together. The simplest such action is a barrier synchronization, in which each individual processor waits until every processor in the group has arrived at the barrier. By having each processor output a datum as a side-effect of reaching a barrier, it is possible to have the communication hardware return a value to each processor which is an arbitrary function of the values collected from all processors. For example, the return value might be the answer to the question "did any processor find a solution?" or it might be the sum of one value from each processor. Latency can be very low, but bandwidth per processor also tends to be low. Traditionally, this model is used primarily to control parallel execution rather than to distribute data values.
This is another name for aggregate functions, most often used when referring to aggregate functions that are constructed using multiple message-passing operations.
SMP (Symmetric Multi-Processor) refers to the operating system concept of a group of processors working together as peers, so that any piece of work could be done equally well by any processor. Typically, SMP implies the combination of MIMD and shared memory. In the IA32 world, SMP generally means compliant with MPS (the Intel MultiProcessor Specification); in the future, it may mean "Slot 2"....
SWAR (SIMD Within A Register) is a generic term for the concept of partitioning a register into multiple integer fields and using register-width operations to perform SIMD-parallel computations across those fields. Given a machine with k-bit registers, data paths, and function units, it has long been known that ordinary register operations can function as SIMD parallel operations on as many as n, k/n-bit, field values. Although this type of parallelism can be implemented using ordinary integer registers and instructions, many high-end microprocessors have recently added specialized instructions to enhance the performance of this technique for multimedia-oriented tasks. In addition to the Intel/AMD/Cyrix MMX (MultiMedia eXtensions), there are: Digital Alpha MAX (MultimediA eXtensions), Hewlett-Packard PA-RISC MAX (Multimedia Acceleration eXtensions), MIPS MDMX (Digital Media eXtension, pronounced "Mad Max"), and Sun SPARC V9 VIS (Visual Instruction Set). Aside from the three vendors who have agreed on MMX, all of these instruction set extensions are roughly comparable, but mutually incompatible.
Attached processors are essentially special-purpose computers that are connected to a host system to accelerate specific types of computation. For example, many video and audio cards for PCs contain attached processors designed, respectively, to accelerate common graphics operations and audio DSP (Digital Signal Processing). There is also a wide range of attached array processors, so called because they are designed to accelerate arithmetic operations on arrays. In fact, many commercial supercomputers are really attached processors with workstation hosts.
RAID (Redundant Array of Inexpensive Disks) is a simple technology for increasing both the bandwidth and reliability of disk I/O. Although there are many different variations, all have two key concepts in common. First, each data block is striped across a group of n+k disk drives such that each drive only has to read or write 1/n of the data... yielding n times the bandwidth of one drive. Second, redundant data is written so that data can be recovered if a disk drive fails; this is important because otherwise if any one of the n+k drives were to fail, the entire file system could be lost. A good overview of RAID in general is given at http://www.uni-mainz.de/~neuffer/scsi/what_is_raid.html, and information about RAID options for Linux systems is at http://linas.org/linux/raid.html. Aside from specialized RAID hardware support, Linux also supports software RAID 0, 1, 4, and 5 across multiple disks hosted by a single Linux system; see the Software RAID mini-HOWTO and the Multi-Disk System Tuning mini-HOWTO for details. RAID across disk drives on multiple machines in a cluster is not directly supported.
IA32 (Intel Architecture, 32-bit) really has nothing to do with parallel processing, but rather refers to the class of processors whose instruction sets are generally compatible with that of the Intel 386. Basically, any Intel x86 processor after the 286 is compatible with the 32-bit flat memory model that characterizes IA32. AMD and Cyrix also make a multitude of IA32-compatible processors. Because Linux evolved primarily on IA32 processors and that is where the commodity market is centered, it is convenient to use IA32 to distinguish any of these processors from the PowerPC, Alpha, PA-RISC, MIPS, SPARC, etc. The upcoming IA64 (64-bit with EPIC, Explicitly Parallel Instruction Computing) will certainly complicate matters, but Merced, the first IA64 processor, is not scheduled for production until 1999.
Since the demise of many parallel supercomputer companies, COTS (Commercial Off-The-Shelf) is commonly discussed as a requirement for parallel computing systems. Being fanatically pure, the only COTS parallel processing techniques using PCs are things like SMP Windows NT servers and various MMX Windows applications; it really doesn't pay to be that fanatical. The underlying concept of COTS is really minimization of development time and cost. Thus, a more useful, more common, meaning of COTS is that at least most subsystems benefit from commodity marketing, but other technologies are used where they are effective. Most often, COTS parallel processing refers to a cluster in which the nodes are commodity PCs, but the network interface and software are somewhat customized... typically running Linux and applications codes that are freely available (e.g., copyleft or public domain), but not literally COTS.
In order to better understand the use of the various parallel programming approaches outlined in this HOWTO, it is useful to have an example problem. Although just about any simple parallel algorithm would do, by selecting an algorithm that has been used to demonstrate various other parallel programming systems, it becomes a bit easier to compare and contrast approaches. M. J. Quinn's book, Parallel Computing Theory And Practice, second edition, McGraw Hill, New York, 1994, uses a parallel algorithm that computes the value of Pi to demonstrate a variety of different parallel supercomputer programming environments (e.g., nCUBE message passing, Sequent shared memory). In this HOWTO, we use the same basic algorithm.
The algorithm computes the approximate value of Pi by summing the area under x squared. As a purely sequential C program, the algorithm looks like:
#include <stdlib.h>;
#include <stdio.h>;
main(int argc, char **argv)
{
register double width, sum;
register int intervals, i;
/* get the number of intervals */
intervals = atoi(argv[1]);
width = 1.0 / intervals;
/* do the computation */
sum = 0;
for (i=0; i<intervals; ++i) {
register double x = (i + 0.5) * width;
sum += 4.0 / (1.0 + x * x);
}
sum *= width;
printf("Estimation of pi is %f\n", sum);
return(0);
}
However, this sequential algorithm easily yields an "embarrassingly parallel" implementation. The area is subdivided into intervals, and any number of processors can each independently sum the intervals assigned to it, with no need for interaction between processors. Once the local sums have been computed, they are added together to create a global sum; this step requires some level of coordination and communication between processors. Finally, this global sum is printed by one processor as the approximate value of Pi.
In this HOWTO, the various parallel implementations of this algorithm appear where each of the different programming methods is discussed.
The remainder of this document is divided into five parts. Sections 2, 3, 4, and 5 correspond to the three different types of hardware configurations supporting parallel processing using Linux:
The final section of this document covers aspects that are of general interest for parallel processing using Linux, not specific to a particular one of the approaches listed above.
As you read this document, keep in mind that we haven't tested everything, and a lot of stuff reported here "still has a research character" (a nice way to say "doesn't quite work like it should" ;-). However, parallel processing using Linux is useful now, and an increasingly large group is working to make it better.
The author of this HOWTO is Hank Dietz, Ph.D., currently Professor & James F. Hardymon Chair in Networking at the University of Kentucky, Electrical & Computer Engineering Dept in Lexington, KY, 40506-0046. Dietz retains rights to this document as per the Linux Documentation Project guidelines. Although an effort has been made to ensure the correctness and fairness of this presentation, neither Dietz nor University of Kentucky can be held responsible for any problems or errors, and University of Kentucky does not endorse any of the work/products discussed.
This document gives a brief overview of how to use
SMP Linux systems
for parallel processing. The most up-to-date information on SMP Linux
is probably available via the SMP Linux project mailing list; send
email to
majordomo@vger.rutgers.edu with the text subscribe
linux-smp to join the list.
Does SMP Linux really work? In June 1996, I purchased a brand new
(well, new off-brand ;-) two-processor 100MHz Pentium system. The
fully assembled system, including both processors, Asus motherboard,
256K cache, 32M RAM, 1.6G disk, 6X CDROM, Stealth 64, and 15" Acer
monitor, cost a total of $1,800. This was just a few hundred
dollars more than a comparable uniprocessor system. Getting SMP Linux
running was simply a matter of installing the "stock" uniprocessor
Linux, recompiling the kernel with the SMP=1 line in the
makefile uncommented (although I find setting SMP to
1 a bit ironic ;-), and informing lilo about the new
kernel. This system performs well enough, and has been stable enough,
to serve as my primary workstation ever since. In summary, SMP Linux
really does work.
The next question is how much high-level support is available for writing and executing shared memory parallel programs under SMP Linux. Through early 1996, there wasn't much. Things have changed. For example, there is now a very complete POSIX threads library.
Although performance may be lower than for native shared-memory mechanisms, an SMP Linux system also can use most parallel processing software that was originally developed for a workstation cluster using socket communication. Sockets (see section 3.3) work within an SMP Linux system, and even for multiple SMPs networked as a cluster. However, sockets imply a lot of unnecessary overhead for an SMP. Much of that overhead is within the kernel or interrupt handlers; this worsens the problem because SMP Linux generally allows only one processor to be in the kernel at a time and the interrupt controller is set so that only the boot processor can process interrupts. Despite this, typical SMP communication hardware is so much better than most cluster networks that cluster software will often run better on an SMP than on the cluster for which it was designed.
The remainder of this section discusses SMP hardware, reviews the basic Linux mechanisms for sharing memory across the processes of a parallel program, makes a few observations about atomicity, volatility, locks, and cache lines, and finally gives some pointers to other shared memory parallel processing resources.
Although SMP systems have been around for many years, until very recently, each such machine tended to implement basic functions differently enough so that operating system support was not portable. The thing that has changed this situation is Intel's Multiprocessor Specification, often referred to as simply MPS. The MPS 1.4 specification is currently available as a PDF file at http://www.intel.com/design/pro/datashts/242016.htm, and there is a brief overview of MPS 1.1 at http://support.intel.com/oem_developer/ial/support/9300.HTM, but be aware that Intel does re-arrange their WWW site often. A wide range of vendors are building MPS-compliant systems supporting up to four processors, but MPS theoretically allows many more processors.
The only non-MPS, non-IA32, systems supported by SMP Linux are Sun4m multiprocessor SPARC machines. SMP Linux supports most Intel MPS version 1.1 or 1.4 compliant machines with up to sixteen 486DX, Pentium, Pentium MMX, Pentium Pro, or Pentium II processors. Unsupported IA32 processors include the Intel 386, Intel 486SX/SLC processors (the lack of floating point hardware interferes with the SMP mechanisms), and AMD & Cyrix processors (they require different SMP support chips that do not seem to be available at this writing).
It is important to understand that the performance of MPS-compliant systems can vary widely. As expected, one cause for performance differences is processor speed: faster clock speeds tend to yield faster systems, and a Pentium Pro processor is faster than a Pentium. However, MPS does not really specify how hardware implements shared memory, but only how that implementation must function from a software point of view; this means that performance is also a function of how the shared memory implementation interacts with the characteristics of SMP Linux and your particular programs.
The primary way in which systems that comply with MPS differ is in how they implement access to physically shared memory.
Some MPS Pentium systems, and all MPS Pentium Pro and Pentium II systems, have independent L2 caches. (The L2 cache is packaged within the Pentium Pro or Pentium II modules.) Separate L2 caches are generally viewed as maximizing compute performance, but things are not quite so obvious under Linux. The primary complication is that the current SMP Linux scheduler does not attempt to keep each process on the same processor, a concept known as processor affinity. This may change soon; there has recently been some discussion about this in the SMP Linux development community under the title "processor binding." Without processor affinity, having separate L2 caches may introduce significant overhead when a process is given a timeslice on a processor other than the one that was executing it last.
Many relatively inexpensive systems are organized so that two Pentium processors share a single L2 cache. The bad news is that this causes contention for the cache, seriously degrading performance when running multiple independent sequential programs. The good news is that many parallel programs might actually benefit from the shared cache because if both processors will want to access the same line from shared memory, only one had to fetch it into cache and contention for the bus is averted. The lack of processor affinity also causes less damage with a shared L2 cache. Thus, for parallel programs, it isn't really clear that sharing L2 cache is as harmful as one might expect.
Experience with our dual Pentium shared 256K cache system shows quite a wide range of performance depending on the level of kernel activity required. At worst, we see only about 1.2x speedup. However, we also have seen up to 2.1x speedup, which suggests that compute-intensive SPMD-style code really does profit from the "shared fetch" effect.
The first thing to say is that most modern systems connect the processors to one or more PCI buses that in turn are "bridged" to one or more ISA/EISA buses. These bridges add latency, and both EISA and ISA generally offer lower bandwidth than PCI (ISA being the lowest), so disk drives, video cards, and other high-performance devices generally should be connected via a PCI bus interface.
Although an MPS system can achieve good speed-up for many compute-intensive parallel programs even if there is only one PCI bus, I/O operations occur at no better than uniprocessor performance... and probably a little worse due to bus contention from the processors. Thus, if you are looking to speed-up I/O, make sure that you get an MPS system with multiple independent PCI busses and I/O controllers (e.g., multiple SCSI chains). You will need to be careful to make sure SMP Linux supports what you get. Also keep in mind that the current SMP Linux essentially allows only one processor in the kernel at any time, so you should choose your I/O controllers carefully to pick ones that minimize the kernel time required for each I/O operation. For really high performance, you might even consider doing raw device I/O directly from user processes, without a system call... this isn't necessarily as hard as it sounds, and need not compromise security (see section 3.3 for a description of the basic techniques).
It is important to note that the relationship between bus speed and processor clock rate has become very fuzzy over the past few years. Although most systems now use the same PCI clock rate, it is not uncommon to find a faster processor clock paired with a slower bus clock. The classic example of this was that the Pentium 133 generally used a faster bus than a Pentium 150, with appropriately strange-looking performance on various benchmarks. These effects are amplified in SMP systems; it is even more important to have a faster bus clock.
Memory interleaving actually has nothing whatsoever to do with MPS, but you will often see it mentioned for MPS systems because these systems are typically more demanding of memory bandwidth. Basically, two-way or four-way interleaving organizes RAM so that a block access is accomplished using multiple banks of RAM rather than just one. This provides higher memory access bandwidth, particularly for cache line loads and stores.
The waters are a bit muddied about this, however, because EDO DRAM and various other memory technologies tend to improve similar kinds of operations. An excellent overview of DRAM technologies is given in http://www.pcguide.com/ref/ram/tech.htm.
So, for example, is it better to have 2-way interleaved EDO DRAM or non-interleaved SDRAM? That is a very good question with no simple answer, because both interleaving and exotic DRAM technologies tend to be expensive. The same dollar investment in more ordinary memory configurations generally will give you a significantly larger main memory. Even the slowest DRAM is still a heck of a lot faster than using disk-based virtual memory....
Ok, so you have decided that parallel processing on an SMP is a great thing to do... how do you get started? Well, the first step is to learn a little bit about how shared memory communication really works.
It sounds like you simply have one processor store a value into memory and another processor load it; unfortunately, it isn't quite that simple. For example, the relationship between processes and processors is very blurry; however, if we have no more active processes than there are processors, the terms are roughly interchangeable. The remainder of this section briefly summarizes the key issues that could cause serious problems, if you were not aware of them: the two different models used to determine what is shared, atomicity issues, the concept of volatility, hardware lock instructions, cache line effects, and Linux scheduler issues.
There are two fundamentally different models commonly used for shared memory programming: shared everything and shared something. Both of these models allow processors to communicate by loads and stores from/into shared memory; the distinction comes in the fact that shared everything places all data structures in shared memory, while shared something requires the user to explicitly indicate which data structures are potentially shared and which are private to a single processor.
Which shared memory model should you use? That is mostly a question of religion. A lot of people like the shared everything model because they do not really need to identify which data structures should be shared at the time they are declared... you simply put locks around potentially-conflicting accesses to shared objects to ensure that only one process(or) has access at any moment. Then again, that really isn't all that simple... so many people prefer the relative safety of shared something.
The nice thing about sharing everything is that you can easily take an existing sequential program and incrementally convert it into a shared everything parallel program. You do not have to first determine which data need to be accessible by other processors.
Put simply, the primary problem with sharing everything is that any action taken by one processor could affect the other processors. This problem surfaces in two ways:
errno; if two shared
everything processes perform various calls, they would interfere with
each other because they share the same errno. Although there
is now a library version that fixes the errno problem,
similar problems still exist in most libraries. For example, unless
special precautions are taken, the X library will not work if calls
are made from multiple shared everything processes.
core file that
clues you in to what happened. In shared everything parallel
processing, it is very likely that the stray accesses will bring the
demise of a process other than the one at fault, making it
nearly impossible to localize and correct the error.Neither of these types of problems is common when shared something is used, because only the explicitly-marked data structures are shared. It also is fairly obvious that shared everything only works if all processors are executing the exact same memory image; you cannot use shared everything across multiple different code images (i.e., can use only SPMD, not general MIMD).
The most common type of shared everything programming support is a threads library. Threads are essentially "light-weight" processes that might not be scheduled in the same way as regular UNIX processes and, most importantly, share access to a single memory map. The POSIX Pthreads package has been the focus of a number of porting efforts; the big question is whether any of these ports actually run the threads of a program in parallel under SMP Linux (ideally, with a processor for each thread). The POSIX API doesn't require it, and versions like http://www.aa.net/~mtp/PCthreads.html apparently do not implement parallel thread execution - all the threads of a program are kept within a single Linux process.
The first threads library that supported SMP Linux parallelism was the
now somewhat obsolete bb_threads library,
ftp://caliban.physics.utoronto.ca/pub/linux/, a very small
library that used the Linux clone() call to fork new,
independently scheduled, Linux processes all sharing a single address
space. SMP Linux machines can run multiple of these "threads" in
parallel because each "thread" is a full Linux process; the trade-off
is that you do not get the same "light-weight" scheduling control
provided by some thread libraries under other operating systems. The
library used a bit of C-wrapped assembly code to install a new chunk
of memory as each thread's stack and to provide atomic access
functions for an array of locks (mutex objects). Documentation
consisted of a README and a short sample program.
More recently, a version of POSIX threads using clone() has
been developed. This library,
LinuxThreads, is clearly the preferred shared everything
library for use under SMP Linux. POSIX threads are well documented,
and the
LinuxThreads README and
LinuxThreads FAQ are very well done. The primary problem now
is simply that POSIX threads have a lot of details to get right and
LinuxThreads is still a work in progress. There is also the problem
that the POSIX thread standard has evolved through the standardization
process, so you need to be a bit careful not to program for obsolete
early versions of the standard.
Shared something is really "only share what needs to be shared." This approach can work for general MIMD (not just SPMD) provided that care is taken for the shared objects to be allocated at the same places in each processor's memory map. More importantly, shared something makes it easier to predict and tune performance, debug code, etc. The only problems are:
Currently, there are two very similar mechanisms that allow groups of
Linux processes to have independent memory spaces, all sharing only a
relatively small memory segment. Assuming that you didn't foolishly
exclude "System V IPC" when you configured your Linux system, Linux
supports a very portable mechanism that has generally become known as
"System V Shared Memory." The other alternative is a memory mapping
facility whose implementation varies widely across different UNIX
systems: the mmap() system call. You can, and should, learn
about these calls from the manual pages... but a brief overview of
each is given in sections 2.5 and 2.6 to help get you started.
No matter which of the above two models you use, the result is pretty much the same: you get a pointer to a chunk of read/write memory that is accessible by all processes within your parallel program. Does that mean I can just have my parallel program access shared memory objects as though they were in ordinary local memory? Well, not quite....
Atomicity refers to the concept that an operation on an object is accomplished as an indivisible, uninterruptible, sequence. Unfortunately, sharing memory access does not imply that all operations on data in shared memory occur atomically. Unless special precautions are taken, only simple load or store operations that occur within a single bus transaction (i.e., aligned 8, 16, or 32-bit operations, but not misaligned nor 64-bit operations) are atomic. Worse still, "smart" compilers like GCC will often perform optimizations that could eliminate the memory operations needed to ensure that other processors can see what this processor has done. Fortunately, both these problems can be remedied... leaving only the relationship between access efficiency and cache line size for us to worry about.
However, before discussing these issues, it is useful to point-out
that all of this assumes that memory references for each processor
happen in the order in which they were coded. The Pentium does this,
but also notes that future Intel processors might not. So, for future
processors, keep in mind that it may be necessary to surround some
shared memory accesses with instructions that cause all pending memory
accesses to complete, thus providing memory access ordering. The
CPUID instruction apparently is reserved to have this
side-effect.
To prevent GCC's optimizer from buffering values of shared memory
objects in registers, all objects in shared memory should be declared
as having types with the volatile attribute. If this is
done, all shared object reads and writes that require just one word
access will occur atomically. For example, suppose that p
is a pointer to an integer, where both the pointer and the integer it
will point at are in shared memory; the ANSI C declaration might be:
volatile int * volatile p;
In this code, the first volatile refers to the int
that p will eventually point at; the second volatile
refers to the pointer itself. Yes, it is annoying, but it is the
price one pays for enabling GCC to perform some very powerful
optimizations. At least in theory, the -traditional option
to GCC might suffice to produce correct code at the expense of some
optimization, because pre-ANSI K&R C essentially claimed that all
variables were volatile unless explicitly declared as
register. Still, if your typical GCC compile looks like
cc -O6 ..., you really will want to explicitly mark
things as volatile only where necessary.
There has been a rumor to the effect that using assembly-language
locks that are marked as modifying all processor registers will cause
GCC to appropriately flush all variables, thus avoiding the
"inefficient" compiled code associated with things declared as
volatile. This hack appears to work for statically allocated
global variables using version 2.7.0 of GCC... however, that behavior
is not required by the ANSI C standard. Still worse, other
processes that are making only read accesses can buffer the values in
registers forever, thus never noticing that the shared memory
value has actually changed. In summary, do what you want, but only
variables accessed through volatile are guaranteed
to work correctly.
Note that you can cause a volatile access to an ordinary variable by
using a type cast that imposes the volatile attribute. For
example, the ordinary int i; can be referenced as a volatile
by *((volatile int *) &i); thus, you can explicitly
invoke the "overhead" of volatility only where it is critical.
If you thought that ++i; would always work to add one to a
variable i in shared memory, you've got a nasty little
surprise coming: even if coded as a single instruction, the load and
store of the result are separate memory transactions, and other
processors could access i between these two transactions.
For example, having two processes both perform ++i; might
only increment i by one, rather than by two. According to
the Intel Pentium "Architecture and Programming Manual," the
LOCK prefix can be used to ensure that any of the following
instructions is atomic relative to the data memory location it
accesses:
BTS, BTR, BTC mem, reg/imm XCHG reg, mem XCHG mem, reg ADD, OR, ADC, SBB, AND, SUB, XOR mem, reg/imm NOT, NEG, INC, DEC mem CMPXCHG, XADD
However, it probably is not a good idea to use all these operations.
For example, XADD did not even exist for the 386, so coding
it may cause portability problems.
The XCHG instruction always asserts a lock, even
without the LOCK prefix, and thus is clearly the preferred
atomic operation from which to build higher-level atomic constructs
such as semaphores and shared queues. Of course, you can't get GCC to
generate this instruction just by writing C code... instead, you must
use a bit of in-line assembly code. Given a word-size volatile object
obj and a word-size register value reg, the GCC
in-line assembly code is:
__asm__ __volatile__ ("xchgl %1,%0"
:"=r" (reg), "=m" (obj)
:"r" (reg), "m" (obj));
Examples of GCC in-line assembly code using bit operations for locking are given in the source code for the bb_threads library.
It is important to remember, however, that there is a cost associated with making memory transactions atomic. A locking operation carries a fair amount of overhead and may delay memory activity from other processors, whereas ordinary references may use local cache. The best performance results when locking operations are used as infrequently as possible. Further, these IA32 atomic instructions obviously are not portable to other systems.
There are many alternative approaches that allow ordinary instructions to be used to implement various synchronizations, including mutual exclusion - ensuring that at most one processor is updating a given shared object at any moment. Most OS textbooks discuss at least one of these techniques. There is a fairly good discussion in the Fourth Edition of Operating System Concepts, by Abraham Silberschatz and Peter B. Galvin, ISBN 0-201-50480-4.
One more fundamental atomicity concern can have a dramatic impact on SMP performance: cache line size. Although the MPS standard requires references to be coherent no matter what caching is used, the fact is that when one processor writes to a particular line of memory, every cached copy of the old line must be invalidated or updated. This implies that if two or more processors are both writing data to different portions of the same line a lot of cache and bus traffic may result, effectively to pass the line from cache to cache. This problem is known as false sharing. The solution is simply to try to organize data so that what is accessed in parallel tends to come from a different cache line for each process.
You might be thinking that false sharing is not a problem using a
system with a shared L2 cache, but remember that there are still
separate L1 caches. Cache organization and number of separate levels
can both vary, but the Pentium L1 cache line size is 32 bytes and
typical external cache line sizes are around 256 bytes. Suppose that
the addresses (physical or virtual) of two items are a and
b and that the largest per-processor cache line size is
c, which we assume to be a power of two. To be very precise,
if ((int) a) & ~(c - 1) is equal to
((int) b) & ~(c - 1), then both
references are in the same cache line. A simpler rule is that if
shared objects being referenced in parallel are at least c
bytes apart, they should map to different cache lines.
Although the whole point of using shared memory for parallel processing is to avoid OS overhead, OS overhead can come from things other than communication per se. We have already said that the number of processes that should be constructed is less than or equal to the number of processors in the machine. But how do you decide exactly how many processes to make?
For best performance, the number of processes in your parallel
program should be equal to the expected number of your program's
processes that simultaneously can be running on different
processors. For example, if a four-processor SMP typically has
one process actively running for some other purpose (e.g., a WWW
server), then your parallel program should use only three processes.
You can get a rough idea of how many other processes are active on
your system by looking at the "load average" quoted by the
uptime command.
Alternatively, you could boost the priority of the processes in your
parallel program using, for example, the renice command or
nice() system call. You must be privileged to increase
priority. The idea is simply to force the other processes out of
processors so that your program can run simultaneously across all
processors. This can be accomplished somewhat more explicitly using
the prototype version of SMP Linux at
http://luz.cs.nmt.edu/~rtlinux/, which offers real-time
schedulers.
If you are not the only user treating your SMP system as a parallel machine, you may also have conflicts between the two or more parallel programs trying to execute simultaneously. This standard solution is gang scheduling - i.e., manipulating scheduling priority so that at any given moment, only the processes of a single parallel program are running. It is useful to recall, however, that using more parallelism tends to have diminishing returns and scheduler activity adds overhead. Thus, for example, it is probably better for a four-processor machine to run two programs with two processes each rather than gang scheduling between two programs with four processes each.
There is one more twist to this. Suppose that you are developing a program on a machine that is heavily used all day, but will be fully available for parallel execution at night. You need to write and test your code for correctness with the full number of processes, even though you know that your daytime test runs will be slow. Well, they will be very slow if you have processes busy waiting for shared memory values to be changed by other processes that are not currently running (on other processors). The same problem occurs if you develop and test your code on a single-processor system.
The solution is to embed calls in your code, wherever it may loop
awaiting an action from another processor, so that Linux will give
another process a chance to run. I use a C macro, call it
IDLE_ME, to do this: for a test run, compile with
cc -DIDLE_ME=usleep(1); ...; for a "production" run,
compile with cc -DIDLE_ME={} .... The
usleep(1) call requests a 1 microsecond sleep, which has the
effect of allowing the Linux scheduler to select a different process
to run on that processor. If the number of processes is more than
twice the number of processors available, it is not unusual for codes
to run ten times faster with usleep(1) calls than without
them.
The bb_threads ("Bare Bones" threads) library,
ftp://caliban.physics.utoronto.ca/pub/linux/, is a remarkably
simple library that demonstrates use of the Linux clone()
call. The gzip tar file is only 7K bytes! Although this
library is essentially made obsolete by the LinuxThreads library
discussed in section 2.4, bb_threads is still usable, and it is
small and simple enough to serve well as an introduction to use of
Linux thread support. Certainly, it is far less daunting to read this
source code than to browse the source code for LinuxThreads. In
summary, the bb_threads library is a good starting point, but
is not really suitable for coding large projects.
The basic program structure for using the bb_threads library is:
bb_threads_stacksize(b).
MAX_MUTEXES, and initializes lock i by
bb_threads_mutexcreate(i).
void-returning function f with the
single argument arg, you do something like
bb_threads_newthread(f, &arg),
where f should be declared something like void
f(void *arg, size_t dummy). If you need to pass
more than one argument, pass a pointer to a structure initialized to
hold the argument values.
bb_threads_lock(n) and
bb_threads_unlock(n) where n
is an integer identifying which lock to use. Note that the lock and
unlock operations in this library are very basic spin locks using
atomic bus-locking instructions, which can cause excessive
memory-reference interference and do not make any attempt to ensure
fairness.
The demo program packaged with bb_threads did not correctly use
locks to prevent printf() from being executed simultaneously
from within the functions fnn and main... and
because of this, the demo does not always work. I'm not saying this
to knock the demo, but rather to emphasize that this stuff is very
tricky; also, it is only slightly easier using LinuxThreads.
return, it actually destroys
the process... but the local stack memory is not automatically
deallocated. To be precise, Linux doesn't support deallocation, but
the memory space is not automatically added back to the
malloc() free list. Thus, the parent process should reclaim
the space for each dead child by
bb_threads_cleanup(wait(NULL)).
The following C program uses the algorithm discussed in section 1.3 to compute the approximate value of Pi using two bb_threads threads.
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/wait.h>
#include "bb_threads.h"
volatile double pi = 0.0;
volatile int intervals;
volatile int pids[2]; /* Unix PIDs of threads */
void
do_pi(void *data, size_t len)
{
register double width, localsum;
register int i;
register int iproc = (getpid() != pids[0]);
/* set width */
width = 1.0 / intervals;
/* do the local computations */
localsum = 0;
for (i=iproc; i<intervals; i+=2) {
register double x = (i + 0.5) * width;
localsum += 4.0 / (1.0 + x * x);
}
localsum *= width;
/* get permission, update pi, and unlock */
bb_threads_lock(0);
pi += localsum;
bb_threads_unlock(0);
}
int
main(int argc, char **argv)
{
/* get the number of intervals */
intervals = atoi(argv[1]);
/* set stack size and create lock... */
bb_threads_stacksize(65536);
bb_threads_mutexcreate(0);
/* make two threads... */
pids[0] = bb_threads_newthread(do_pi, NULL);
pids[1] = bb_threads_newthread(do_pi, NULL);
/* cleanup after two threads (really a barrier sync) */
bb_threads_cleanup(wait(NULL));
bb_threads_cleanup(wait(NULL));
/* print the result */
printf("Estimation of pi is %f\n", pi);
/* check-out */
exit(0);
}
LinuxThreads
http://pauillac.inria.fr/~xleroy/linuxthreads/ is a fairly
complete and solid implementation of "shared everything" as per the
POSIX 1003.1c threads standard. Unlike other POSIX threads ports,
LinuxThreads uses the same Linux kernel threads facility
(clone()) that is used by bb_threads. POSIX
compatibility means that it is relatively easy to port quite a few
threaded applications from other systems and various tutorial
materials are available. In short, this is definitely the threads
package to use under Linux for developing large-scale threaded
programs.
The basic program structure for using the LinuxThreads library is:
pthread_mutex_t lock. Use
pthread_mutex_init(&lock,val) to initialize
each one you will need to use.
pthread_t to identify each thread. To
create a thread pthread_t thread running f(),
one calls pthread_create(&thread,NULL,f,&arg).
pthread_mutex_lock(&lock) and
pthread_mutex_unlock(&lock) as appropriate.
pthread_join(thread,&retval) to clean-up
after each thread.
-D_REENTRANT when compiling your C code.An example parallel computation of Pi using LinuxThreads follows. The algorithm of section 1.3 is used and, as for the bb_threads example, two threads execute in parallel.
#include <stdio.h>
#include <stdlib.h>
#include "pthread.h"
volatile double pi = 0.0; /* Approximation to pi (shared) */
pthread_mutex_t pi_lock; /* Lock for above */
volatile double intervals; /* How many intervals? */
void *
process(void *arg)
{
register double width, localsum;
register int i;
register int iproc = (*((char *) arg) - '0');
/* Set width */
width = 1.0 / intervals;
/* Do the local computations */
localsum = 0;
for (i=iproc; i<intervals; i+=2) {
register double x = (i + 0.5) * width;
localsum += 4.0 / (1.0 + x * x);
}
localsum *= width;
/* Lock pi for update, update it, and unlock */
pthread_mutex_lock(&pi_lock);
pi += localsum;
pthread_mutex_unlock(&pi_lock);
return(NULL);
}
int
main(int argc, char **argv)
{
pthread_t thread0, thread1;
void * retval;
/* Get the number of intervals */
intervals = atoi(argv[1]);
/* Initialize the lock on pi */
pthread_mutex_init(&pi_lock, NULL);
/* Make the two threads */
if (pthread_create(&thread0, NULL, process, "0") ||
pthread_create(&thread1, NULL, process, "1")) {
fprintf(stderr, "%s: cannot make thread\n", argv[0]);
exit(1);
}
/* Join (collapse) the two threads */
if (pthread_join(thread0, &retval) ||
pthread_join(thread1, &retval)) {
fprintf(stderr, "%s: thread join failed\n", argv[0]);
exit(1);
}
/* Print the result */
printf("Estimation of pi is %f\n", pi);
/* Check-out */
exit(0);
}
The System V IPC (Inter-Process Communication) support consists of a number of system calls providing message queues, semaphores, and a shared memory mechanism. Of course, these mechanisms were originally intended to be used for multiple processes to communicate within a uniprocessor system. However, that implies that it also should work to communicate between processes under SMP Linux, no matter which processors they run on.
Before going into how these calls are used, it is important to understand that although System V IPC calls exist for things like semaphores and message transmission, you probably should not use them. Why not? These functions are generally slow and serialized under SMP Linux. Enough said.
The basic procedure for creating a group of processes sharing access to a shared memory segment is:
shmget() to create a new segment of the desired size.
Alternatively, this call can be used to get the ID of a pre-existing
shared memory segment. In either case, the return value is either the
shared memory segment ID or -1 for error. For example, to create a
shared memory segment of b bytes, the call might be shmid
= shmget(IPC_PRIVATE, b, (IPC_CREAT | 0666)).
shmat() call allows the programmer to specify
the virtual address at which the segment should appear, the address
selected must be aligned on a page boundary (i.e., be a multiple of
the page size returned by getpagesize(), which is usually
4096 bytes), and will override the mapping of any memory formerly at
that address. Thus, we instead prefer to let the system pick the
address. In either case, the return value is a pointer to the base
virtual address of the segment just mapped. The code is shmptr =
shmat(shmid, 0, 0).
Notice that you can allocate all your static shared variables into
this shared memory segment by simply declaring all shared variables as
members of a struct type, and declaring shmptr to be
a pointer to that type. Using this technique, shared variable
x would be accessed as
shmptr->x.
shmctl() to set-up this default action. The code is
something like shmctl(shmid, IPC_RMID, 0).
fork() call to make the desired
number of processes... each will inherit the shared memory segment.
shmdt(shmptr).
Although the above set-up does require a few system calls, once the shared memory segment has been established, any change made by one processor to a value in that memory will automatically be visible to all processes. Most importantly, each communication operation will occur without the overhead of a system call.
An example C program using System V shared memory segments follows. It computes Pi, using the same algorithm given in section 1.3.
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <sys/ipc.h>
#include <sys/shm.h>
volatile struct shared { double pi; int lock; } *shared;
inline extern int xchg(register int reg,
volatile int * volatile obj)
{
/* Atomic exchange instruction */
__asm__ __volatile__ ("xchgl %1,%0"
:"=r" (reg), "=m" (*obj)
:"r" (reg), "m" (*obj));
return(reg);
}
main(int argc, char **argv)
{
register double width, localsum;
register int intervals, i;
register int shmid;
register int iproc = 0;;
/* Allocate System V shared memory */
shmid = shmget(IPC_PRIVATE,
sizeof(struct shared),
(IPC_CREAT | 0600));
shared = ((volatile struct shared *) shmat(shmid, 0, 0));
shmctl(shmid, IPC_RMID, 0);
/* Initialize... */
shared->pi = 0.0;
shared->lock = 0;
/* Fork a child */
if (!fork()) ++iproc;
/* get the number of intervals */
intervals = atoi(argv[1]);
width = 1.0 / intervals;
/* do the local computations */
localsum = 0;
for (i=iproc; i<intervals; i+=2) {
register double x = (i + 0.5) * width;
localsum += 4.0 / (1.0 + x * x);
}
localsum *= width;
/* Atomic spin lock, add, unlock... */
while (xchg((iproc + 1), &(shared->lock))) ;
shared->pi += localsum;
shared->lock = 0;
/* Terminate child (barrier sync) */
if (iproc == 0) {
wait(NULL);
printf("Estimation of pi is %f\n", shared->pi);
}
/* Check out */
return(0);
}
In this example, I have used the IA32 atomic exchange instruction to implement locking. For better performance and portability, substitute a synchronization technique that avoids atomic bus-locking instructions (discussed in section 2.2).
When debugging your code, it is useful to remember that the
ipcs command will report the status of the System V IPC
facilities currently in use.
Using system calls for file I/O can be very expensive; in fact, that is
why there is a user-buffered file I/O library (getchar(),
fwrite(), etc.). But user buffers don't work if multiple
processes are accessing the same writeable file, and the user buffer
management overhead is significant. The BSD UNIX fix for this was the
addition of a system call that allows a portion of a file to be mapped
into user memory, essentially using virtual memory paging mechanisms to
cause updates. This same mechanism also has been used in systems from
Sequent for many years as the basis for their shared memory parallel
processing support. Despite some very negative comments in the (quite
old) man page, Linux seems to correctly perform at least some of the
basic functions, and it supports the degenerate use of this system
call to map an anonymous segment of memory that can be shared across
multiple processes.
In essence, the Linux implementation of mmap() is a plug-in
replacement for steps 2, 3, and 4 in the System V shared memory scheme
outlined in section 2.5. To create an anonymous shared memory segment:
shmptr =
mmap(0, /* system assigns address */
b, /* size of shared memory segment */
(PROT_READ | PROT_WRITE), /* access rights, can be rwx */
(MAP_ANON | MAP_SHARED), /* anonymous, shared */
0, /* file descriptor (not used) */
0); /* file offset (not used) */
The equivalent to the System V shared memory shmdt()
call is munmap():
munmap(shmptr, b);
In my opinion, there is no real benefit in using mmap()
instead of the System V shared memory support.
This section attempts to give an overview of cluster parallel processing using Linux. Clusters are currently both the most popular and the most varied approach, ranging from a conventional network of workstations (NOW) to essentially custom parallel machines that just happen to use Linux PCs as processor nodes. There is also quite a lot of software support for parallel processing using clusters of Linux machines.
Cluster parallel processing offers several important advantages:
OK, so clusters are free or cheap and can be very large and highly available... why doesn't everyone use a cluster? Well, there are problems too:
ps command only reports the
processes running on one Linux system, not all processes running
across a cluster of Linux systems.
Thus, the basic story is that clusters offer great potential, but that potential may be very difficult to achieve for most applications. The good news is that there is quite a lot of software support that will help you achieve good performance for programs that are well suited to this environment, and there are also networks designed specifically to widen the range of programs that can achieve good performance.
Computer networking is an exploding field... but you already knew that. An ever-increasing range of networking technologies and products are being developed, and most are available in forms that could be applied to make a parallel-processing cluster out of a group of machines (i.e., PCs each running Linux).
Unfortunately, no one network technology solves all problems best; in fact, the range of approach, cost, and performance is at first hard to believe. For example, using standard commercially-available hardware, the cost per machine networked ranges from less than $5 to over $4,000. The delivered bandwidth and latency each also vary over four orders of magnitude.
Before trying to learn about specific networks, it is important to recognize that these things change like the wind (see http://www.linux.org.uk/NetNews.html for Linux networking news), and it is very difficult to get accurate data about some networks.
Where I was particularly uncertain, I've placed a ?. I have spent a lot of time researching this topic, but I'm sure my summary is full of errors and has omitted many important things. If you have any corrections or additions, please send email to hankd@engr.uky.edu.
Summaries like the LAN Technology Scorecard at http://web.syr.edu/~jmwobus/comfaqs/lan-technology.html give some characteristics of many different types of networks and LAN standards. However, the summary in this HOWTO centers on the network properties that are most relevant to construction of Linux clusters. The section discussing each network begins with a short list of characteristics. The following defines what these entries mean.
If the answer is no, the meaning is pretty clear. Other answers try to describe the basic program interface that is used to access the network. Most network hardware is interfaced via a kernel driver, typically supporting TCP/UDP communication. Some other networks use more direct (e.g., library) interfaces to reduce latency by bypassing the kernel.
Years ago, it used to be considered perfectly acceptable to access a floating point unit via an OS call, but that is now clearly ludicrous; in my opinion, it is just as awkward for each communication between processors executing a parallel program to require an OS call. The problem is that computers haven't yet integrated these communication mechanisms, so non-kernel approaches tend to have portability problems. You are going to hear a lot more about this in the near future, mostly in the form of the new Virtual Interface (VI) Architecture, http://www.viarch.org/, which is a standardized method for most network interface operations to bypass the usual OS call layers. The VI standard is backed by Compaq, Intel, and Microsoft, and is sure to have a strong impact on SAN (System Area Network) designs over the next few years.
This is the number everybody cares about. I have generally used the theoretical best case numbers; your mileage will vary.
In my opinion, this is the number everybody should care about even more than bandwidth. Again, I have used the unrealistic best-case numbers, but at least these numbers do include all sources of latency, both hardware and software. In most cases, the network latency is just a few microseconds; the much larger numbers reflect layers of inefficient hardware and software interfaces.
Simply put, this describes how you get this type of network hardware. Commodity stuff is widely available from many vendors, with price as the primary distinguishing factor. Multiple-vendor things are available from more than one competing vendor, but there are significant differences and potential interoperability problems. Single-vendor networks leave you at the mercy of that supplier (however benevolent it may be). Public domain designs mean that even if you cannot find somebody to sell you one, you or anybody else can buy parts and make one. Research prototypes are just that; they are generally neither ready for external users nor available to them.
How does one hook-up this network? The highest performance and most common now is a PCI bus interface card. There are also EISA, VESA local bus (VL bus), and ISA bus cards. ISA was there first, and is still commonly used for low-performance cards. EISA is still around as the second bus in a lot of PCI machines, so there are a few cards. These days, you don't see much VL stuff (although http://www.vesa.org/ would beg to differ).
Of course, any interface that you can use without having to open your PC's case has more than a little appeal. IrDA and USB interfaces are appearing with increasing frequency. The Standard Parallel Port (SPP) used to be what your printer was plugged into, but it has seen a lot of use lately as an external extension of the ISA bus; this new functionality is enhanced by the IEEE 1284 standard, which specifies EPP and ECP improvements. There is also the old, reliable, slow RS232 serial port. I don't know of anybody connecting machines using VGA video connectors, keyboard, mouse, or game ports... so that's about it.
A bus is a wire, set of wires, or fiber. A hub is a little box that knows how to connect different wires/fibers plugged into it; switched hubs allow multiple connections to be actively transmitting data simultaneously.
Here's how to use these numbers. Suppose that, not counting the network connection, it costs $2,000 to purchase a PC for use as a node in your cluster. Adding a Fast Ethernet brings the per node cost to about $2,400; adding a Myrinet instead brings the cost to about $3,800. If you have about $20,000 to spend, that means you could have either 8 machines connected by Fast Ethernet or 5 machines connected by Myrinet. It also can be very reasonable to have multiple networks; e.g., $20,000 could buy 8 machines connected by both Fast Ethernet and TTL_PAPERS. Pick the network, or set of networks, that is most likely to yield a cluster that will run your application fastest.
By the time you read this, these numbers will be wrong... heck, they're probably wrong already. There may also be quantity discounts, special deals, etc. Still, the prices quoted here aren't likely to be wrong enough to lead you to a totally inappropriate choice. It doesn't take a PhD (although I do have one ;-) to see that expensive networks only make sense if your application needs their special properties or if the PCs being clustered are relatively expensive.
Now that you have the disclaimers, on with the show....
ARCNET is a local area network that is primarily intended for use in embedded real-time control systems. Like Ethernet, the network is physically organized either as taps on a bus or one or more hubs, however, unlike Ethernet, it uses a token-based protocol logically structuring the network as a ring. Packet headers are small (3 or 4 bytes) and messages can carry as little as a single byte of data. Thus, ARCNET yields more consistent performance than Ethernet, with bounded delays, etc. Unfortunately, it is slower than Ethernet and less popular, making it more expensive. More information is available from the ARCNET Trade Association at http://www.arcnet.com/.
Unless you've been in a coma for the past few years, you have probably heard a lot about how ATM (Asynchronous Transfer Mode) is the future... well, sort-of. ATM is cheaper than HiPPI and faster than Fast Ethernet, and it can be used over the very long distances that the phone companies care about. The ATM network protocol is also designed to provide a lower-overhead software interface and to more efficiently manage small messages and real-time communications (e.g., digital audio and video). It is also one of the highest-bandwidth networks that Linux currently supports. The bad news is that ATM isn't cheap, and there are still some compatibility problems across vendors. An overview of Linux ATM development is available at http://lrcwww.epfl.ch/linux-atm/.
CAPERS (Cable Adapter for Parallel Execution and Rapid Synchronization) is a spin-off of the PAPERS project, http://garage.ecn.purdue.edu/~papers/, at the Purdue University School of Electrical and Computer Engineering. In essence, it defines a software protocol for using an ordinary "LapLink" SPP-to-SPP cable to implement the PAPERS library for two Linux PCs. The idea doesn't scale, but you can't beat the price. As with TTL_PAPERS, to improve system security, there is a minor kernel patch recommended, but not required: http://garage.ecn.purdue.edu/~papers/giveioperm.html.
For some years now, 10 Mbits/s Ethernet has been the standard network technology. Good Ethernet interface cards can be purchased for well under $50, and a fair number of PCs now have an Ethernet controller built-into the motherboard. For lightly-used networks, Ethernet connections can be organized as a multi-tap bus without a hub; such configurations can serve up to 200 machines with minimal cost, but are not appropriate for parallel processing. Adding an unswitched hub does not really help performance. However, switched hubs that can provide full bandwidth to simultaneous connections cost only about $100 per port. Linux supports an amazing range of Ethernet interfaces, but it is important to keep in mind that variations in the interface hardware can yield significant performance differences. See the Hardware Compatibility HOWTO for comments on which are supported and how well they work; also see http://cesdis1.gsfc.nasa.gov/linux/drivers/.
An interesting way to improve performance is offered by the 16-machine Linux cluster work done in the Beowulf project, http://cesdis.gsfc.nasa.gov/linux/beowulf/beowulf.html, at NASA CESDIS. There, Donald Becker, who is the author of many Ethernet card drivers, has developed support for load sharing across multiple Ethernet networks that shadow each other (i.e., share the same network addresses). This load sharing is built-into the standard Linux distribution, and is done invisibly below the socket operation level. Because hub cost is significant, having each machine connected to two or more hubless or unswitched hub Ethernet networks can be a very cost-effective way to improve performance. In fact, in situations where one machine is the network performance bottleneck, load sharing using shadow networks works much better than using a single switched hub network.
Although there are really quite a few different technologies calling themselves "Fast Ethernet," this term most often refers to a hub-based 100 Mbits/s Ethernet that is somewhat compatible with older "10 BaseT" 10 Mbits/s devices and cables. As might be expected, anything called Ethernet is generally priced for a volume market, and these interfaces are generally a small fraction of the price of 155 Mbits/s ATM cards. The catch is that having a bunch of machines dividing the bandwidth of a single 100 Mbits/s "bus" (using an unswitched hub) yields performance that might not even be as good on average as using 10 Mbits/s Ethernet with a switched hub that can give each machine's connection a full 10 Mbits/s.
Switched hubs that can provide 100 Mbits/s for each machine simultaneously are expensive, but prices are dropping every day, and these switches do yield much higher total network bandwidth than unswitched hubs. The thing that makes ATM switches so expensive is that they must switch for each (relatively short) ATM cell; some Fast Ethernet switches take advantage of the expected lower switching frequency by using techniques that may have low latency through the switch, but take multiple milliseconds to change the switch path... if your routing pattern changes frequently, avoid those switches. See http://cesdis1.gsfc.nasa.gov/linux/drivers/ for information about the various cards and drivers.
Also note that, as described for Ethernet, the Beowulf project, http://cesdis.gsfc.nasa.gov/linux/beowulf/beowulf.html, at NASA has been developing support that offers improved performance by load sharing across multiple Fast Ethernets.
I'm not sure that Gigabit Ethernet, http://www.gigabit-ethernet.org/, has a good technological reason to be called Ethernet... but the name does accurately reflect the fact that this is intended to be a cheap, mass-market, computer network technology with native support for IP. However, current pricing reflects the fact that Gb/s hardware is still a tricky thing to build.
Unlike other Ethernet technologies, Gigabit Ethernet provides for a level of flow control that should make it a more reliable network. FDRs, or Full-Duplex Repeaters, simply multiplex lines, using buffering and localized flow control to improve performance. Most switched hubs are being built as new interface modules for existing gigabit-capable switch fabrics. Switch/FDR products have been shipped or announced by at least http://www.acacianet.com/, http://www.baynetworks.com/, http://www.cabletron.com/, http://www.networks.digital.com/, http://www.extremenetworks.com/, http://www.foundrynet.com/, http://www.gigalabs.com/, http://www.packetengines.com/. http://www.plaintree.com/, http://www.prominet.com/, http://www.sun.com/, and http://www.xlnt.com/.
There is a Linux driver, http://cesdis.gsfc.nasa.gov/linux/drivers/yellowfin.html, for the Packet Engines "Yellowfin" G-NIC, http://www.packetengines.com/. Early tests under Linux achieved about 2.5x higher bandwidth than could be achieved with the best 100 Mb/s Fast Ethernet; with gigabit networks, careful tuning of PCI bus use is a critical factor. There is little doubt that driver improvements, and Linux drivers for other NICs, will follow.
The goal of FC (Fibre Channel) is to provide high-performance block I/O (an FC frame carries a 2,048 byte data payload), particularly for sharing disks and other storage devices that can be directly connected to the FC rather than connected through a computer. Bandwidth-wise, FC is specified to be relatively fast, running anywhere between 133 and 1,062 Mbits/s. If FC becomes popular as a high-end SCSI replacement, it may quickly become a cheap technology; for now, it is not cheap and is not supported by Linux. A good collection of FC references is maintained by the Fibre Channel Association at http://www.amdahl.com/ext/CARP/FCA/FCA.html
FireWire, http://www.firewire.org/, the IEEE 1394-1995 standard, is destined to be the low-cost high-speed digital network for consumer electronics. The showcase application is connecting DV digital video camcorders to computers, but FireWire is intended to be used for applications ranging from being a SCSI replacement to interconnecting the components of your home theater. It allows up to 64K devices to be connected in any topology using busses and bridges that does not create a cycle, and automatically detects the configuration when components are added or removed. Short (four-byte "quadlet") low-latency messages are supported as well as ATM-like isochronous transmission (used to keep multimedia messages synchronized). Adaptec has FireWire products that allow up to 63 devices to be connected to a single PCI interface card, and also has good general FireWire information at http://www.adaptec.com/serialio/.
Although FireWire will not be the highest bandwidth network available, the consumer-level market (which should drive prices very low) and low latency support might make this one of the best Linux PC cluster message-passing network technologies within the next year or so.
HiPPI (High Performance Parallel Interface) was originally intended to provide very high bandwidth for transfer of huge data sets between a supercomputer and another machine (a supercomputer, frame buffer, disk array, etc.), and has become the dominant standard for supercomputers. Although it is an oxymoron, Serial HiPPI is also becoming popular, typically using a fiber optic cable instead of the 32-bit wide standard (parallel) HiPPI cables. Over the past few years, HiPPI crossbar switches have become common and prices have dropped sharply; unfortunately, serial HiPPI is still pricey, and that is what PCI bus interface cards generally support. Worse still, Linux doesn't yet support HiPPI. A good overview of HiPPI is maintained by CERN at http://www.cern.ch/HSI/hippi/; they also maintain a rather long list of HiPPI vendors at http://www.cern.ch/HSI/hippi/procintf/manufact.htm.
IrDA (Infrared Data Association, http://www.irda.org/) is that little infrared device on the side of a lot of laptop PCs. It is inherently difficult to connect more than two machines using this interface, so it is unlikely to be used for clustering. Don Becker did some preliminary work with IrDA.
Myrinet http://www.myri.com/ is a local area network (LAN) designed to also serve as a "system area network" (SAN), i.e., the network within a cabinet full of machines connected as a parallel system. The LAN and SAN versions use different physical media and have somewhat different characteristics; generally, the SAN version would be used within a cluster.
Myrinet is fairly conventional in structure, but has a reputation for being particularly well-implemented. The drivers for Linux are said to perform very well, although shockingly large performance variations have been reported with different PCI bus implementations for the host computers.
Currently, Myrinet is clearly the favorite network of cluster groups that are not too severely "budgetarily challenged." If your idea of a Linux PC is a high-end Pentium Pro or Pentium II with at least 256 MB RAM and a SCSI RAID, the cost of Myrinet is quite reasonable. However, using more ordinary PC configurations, you may find that your choice is between N machines linked by Myrinet or 2N linked by multiple Fast Ethernets and TTL_PAPERS. It really depends on what your budget is and what types of computations you care about most.
The ParaStation project http://wwwipd.ira.uka.de/parastation at University of Karlsruhe Department of Informatics is building a PVM-compatible custom low-latency network. They first constructed a two-processor ParaPC prototype using a custom EISA card interface and PCs running BSD UNIX, and then built larger clusters using DEC Alphas. Since January 1997, ParaStation has been available for Linux. The PCI cards are being made in cooperation with a company called Hitex (see http://www.hitex.com:80/parastation/). Parastation hardware implements both fast, reliable, message transmission and simple barrier synchronization.
For just the cost of a "LapLink" cable, PLIP (Parallel Line Interface Protocol) allows two Linux machines to communicate through standard parallel ports using standard socket-based software. In terms of bandwidth, latency, and scalability, this is not a very serious network technology; however, the near-zero cost and the software compatibility are useful. The driver is part of the standard Linux kernel distributions.
The goal of SCI (Scalable Coherent Interconnect, ANSI/IEEE 1596-1992) is essentially to provide a high performance mechanism that can support coherent shared memory access across large numbers of machines, as well various types of block message transfers. It is fairly safe to say that the designed bandwidth and latency of SCI are both "awesome" in comparison to most other network technologies. The catch is that SCI is not widely available as cheap production units, and there isn't any Linux support.
SCI primarily is used in various proprietary designs for logically-shared physically-distributed memory machines, such as the HP/Convex Exemplar SPP and the Sequent NUMA-Q 2000 (see http://www.sequent.com/). However, SCI is available as a PCI interface card and 4-way switches (up to 16 machines can be connected by cascading four 4-way switches) from Dolphin, http://www.dolphinics.com/, as their CluStar product line. A good set of links overviewing SCI is maintained by CERN at http://www.cern.ch/HSI/sci/sci.html.
SCSI (Small Computer Systems Interconnect) is essentially an I/O bus that is used for disk drives, CD ROMS, image scanners, etc. There are three separate standards SCSI-1, SCSI-2, and SCSI-3; Fast and Ultra speeds; and data path widths of 8, 16, or 32 bits (with FireWire compatibility also mentioned in SCSI-3). It is all pretty confusing, but we all know a good SCSI is somewhat faster than EIDE and can handle more devices more efficiently.
What many people do not realize is that it is fairly simple for two computers to share a single SCSI bus. This type of configuration is very useful for sharing disk drives between machines and implementing fail-over - having one machine take over database requests when the other machine fails. Currently, this is the only mechanism supported by Microsoft's PC cluster product, WolfPack. However, the inability to scale to larger systems renders shared SCSI uninteresting for parallel processing in general.
ServerNet is the high-performance network hardware from Tandem, http://www.tandem.com. Especially in the online transation processing (OLTP) world, Tandem is well known as a leading producer of high-reliability systems, so it is not surprising that their network claims not just high performance, but also "high data integrity and reliability." Another interesting aspect of ServerNet is that it claims to be able to transfer data from any device directly to any device; not just between processors, but also disk drives, etc., in a one-sided style similar to that suggested by the MPI remote memory access mechanisms described in section 3.5. One last comment about ServerNet: although there is just a single vendor, that vendor is powerful enough to potentially establish ServerNet as a major standard... Tandem is owned by Compaq.
The SHRIMP project, http://www.CS.Princeton.EDU/shrimp/, at the Princeton University Computer Science Department is building a parallel computer using PCs running Linux as the processing elements. The first SHRIMP (Scalable, High-Performance, Really Inexpensive Multi-Processor) was a simple two-processor prototype using a dual-ported RAM on a custom EISA card interface. There is now a prototype that will scale to larger configurations using a custom interface card to connect to a "hub" that is essentially the same mesh routing network used in the Intel Paragon (see http://www.ssd.intel.com/paragon.html). Considerable effort has gone into developing low-overhead "virtual memory mapped communication" hardware and support software.
Although SLIP (Serial Line Interface Protocol) is firmly planted at the low end of the performance spectrum, SLIP (or CSLIP or PPP) allows two machines to perform socket communication via ordinary RS232 serial ports. The RS232 ports can be connected using a null-modem RS232 serial cable, or they can even be connected via dial-up through a modem. In any case, latency is high and bandwidth is low, so SLIP should be used only when no other alternatives are available. It is worth noting, however, that most PCs have two RS232 ports, so it would be possible to network a group of machines simply by connecting the machines as a linear array or as a ring. There is even load sharing software called EQL.
The PAPERS (Purdue's Adapter for Parallel Execution and Rapid Synchronization) project, http://garage.ecn.purdue.edu/~papers/, at the Purdue University School of Electrical and Computer Engineering is building scalable, low-latency, aggregate function communication hardware and software that allows a parallel supercomputer to be built using unmodified PCs/workstations as nodes.
There have been over a dozen different types of PAPERS hardware built that connect to PCs/workstations via the SPP (Standard Parallel Port), roughly following two development lines. The versions called "PAPERS" target higher performance, using whatever technologies are appropriate; current work uses FPGAs, and high bandwidth PCI bus interface designs are also under development. In contrast, the versions called "TTL_PAPERS" are designed to be easily reproduced outside Purdue, and are remarkably simple public domain designs that can be built using ordinary TTL logic. One such design is produced commercially, http://chelsea.ios.com:80/~hgdietz/sbm4.html.
Unlike the custom hardware designs from other universities, TTL_PAPERS clusters have been assembled at many universities from the USA to South Korea. Bandwidth is severely limited by the SPP connections, but PAPERS implements very low latency aggregate function communications; even the fastest message-oriented systems cannot provide comparable performance on those aggregate functions. Thus, PAPERS is particularly good for synchronizing the displays of a video wall (to be discussed further in the upcoming Video Wall HOWTO), scheduling accesses to a high-bandwidth network, evaluating global fitness in genetic searches, etc. Although PAPERS clusters have been built using IBM PowerPC AIX, DEC Alpha OSF/1, and HP PA-RISC HP-UX machines, Linux-based PCs are the platforms best supported.
User programs using TTL_PAPERS AFAPI directly access the SPP
hardware port registers under Linux, without an OS call for each
access. To do this, AFAPI first gets port permission using either
iopl() or ioperm(). The problem with these calls is
that both require the user program to be privileged, yielding a
potential security hole. The solution is an optional kernel patch,
http://garage.ecn.purdue.edu/~papers/giveioperm.html, that
allows a privileged process to control port permission for any process.
USB (Universal Serial Bus, http://www.usb.org/) is a hot-pluggable conventional-Ethernet-speed, bus for up to 127 peripherals ranging from keyboards to video conferencing cameras. It isn't really clear how multiple computers get connected to each other using USB. In any case, USB ports are quickly becoming as standard on PC motherboards as RS232 and SPP, so don't be surprised if one or two USB ports are lurking on the back of the next PC you buy. Development of a Linux driver is discussed at http://peloncho.fis.ucm.es/~inaky/USB.html.
In some ways, USB is almost the low-performance, zero-cost, version of FireWire that you can purchase today.
WAPERS (Wired-AND Adapter for Parallel Execution and Rapid Synchronization) is a spin-off of the PAPERS project, http://garage.ecn.purdue.edu/~papers/, at the Purdue University School of Electrical and Computer Engineering. If implemented properly, the SPP has four bits of open-collector output that can be wired together across machines to implement a 4-bit wide wired AND. This wired-AND is electrically touchy, and the maximum number of machines that can be connected in this way critically depends on the analog properties of the ports (maximum sink current and pull-up resistor value); typically, up to 7 or 8 machines can be networked by WAPERS. Although cost and latency are very low, so is bandwidth; WAPERS is much better as a second network for aggregate operations than as the only network in a cluster. As with TTL_PAPERS, to improve system security, there is a minor kernel patch recommended, but not required: http://garage.ecn.purdue.edu/~papers/giveioperm.html.
Before moving on to discuss the software support for parallel applications, it is useful to first briefly cover the basics of low-level software interface to the network hardware. There are really only three basic choices: sockets, device drivers, and user-level libraries.
By far the most common low-level network interface is a socket interface. Sockets have been a part of unix for over a decade, and most standard network hardware is designed to support at least two types of socket protocols: UDP and TCP. Both types of socket allow you to send arbitrary size blocks of data from one machine to another, but there are several important differences. Typically, both yield a minimum latency of around 1,000 microseconds, although performance can be far worse depending on network traffic.
These socket types are the basic network software interface for most of the portable, higher-level, parallel processing software; for example, PVM uses a combination of UDP and TCP, so knowing the difference will help you tune performance. For even better performance, you can also use these mechanisms directly in your program. The following is just a simple overview of UDP and TCP; see the manual pages and a good network programming book for details.
UDP is the User Datagram Protocol, but you more easily can remember the properties of UDP as Unreliable Datagram Processing. In other words, UDP allows each block to be sent as an individual message, but a message might be lost in transmission. In fact, depending on network traffic, UDP messages can be lost, can arrive multiple times, or can arrive in an order different from that in which they were sent. The sender of a UDP message does not automatically get an acknowledgment, so it is up to user-written code to detect and compensate for these problems. Fortunately, UDP does ensure that if a message arrives, the message contents are intact (i.e., you never get just part of a UDP message).
The nice thing about UDP is that it tends to be the fastest socket protocol. Further, UDP is "connectionless," which means that each message is essentially independent of all others. A good analogy is that each message is like a letter to be mailed; you might send multiple letters to the same address, but each one is independent of the others and there is no limit on how many people you can send letters to.
Unlike UDP, TCP is a reliable, connection-based, protocol. Each block sent is not seen as a message, but as a block of data within an apparently continuous stream of bytes being transmitted through a connection between sender and receiver. This is very different from UDP messaging because each block is simply part of the byte stream and it is up to the user code to figure-out how to extract each block from the byte stream; there are no markings separating messages. Further, the connections are more fragile with respect to network problems, and only a limited number of connections can exist simultaneously for each process. Because it is reliable, TCP generally implies significantly more overhead than UDP.
There are, however, a few pleasant surprises about TCP. One is that,
if multiple messages are sent through a connection, TCP is able to
pack them together in a buffer to better match network hardware packet
sizes, potentially yielding better-than-UDP performance for groups of
short or oddly-sized messages. The other bonus is that networks
constructed using reliable direct physical links between machines can
easily and efficiently simulate TCP connections. For example, this was
done for the ParaStation's "Socket Library" interface software, which
provides TCP semantics using user-level calls that differ from the
standard TCP OS calls only by the addition of the prefix
PSS to each function name.
When it comes to actually pushing data onto the network or pulling data
off the network, the standard unix software interface is a part of the
unix kernel called a device driver. UDP and TCP don't just transport
data, they also imply a fair amount of overhead for socket management.
For example, something has to manage the fact that multiple TCP
connections can share a single physical network interface. In
contrast, a device driver for a dedicated network interface only needs
to implement a few simple data transport functions. These device
driver functions can then be invoked by user programs by using
open() to identify the proper device and then using system
calls like read() and write() on the open "file."
Thus, each such operation could transport a block of data with little
more than the overhead of a system call, which might be as fast as
tens of microseconds.
Writing a device driver to be used with Linux is not hard... if you know precisely how the device hardware works. If you are not sure how it works, don't guess. Debugging device drivers isn't fun and mistakes can fry hardware. However, if that hasn't scared you off, it may be possible to write a device driver to, for example, use dedicated Ethernet cards as dumb but fast direct machine-to-machine connections without the usual Ethernet protocol overhead. In fact, that's pretty much what some early Intel supercomputers did.... Look at the Device Driver HOWTO for more information.
If you've taken an OS course, user-level access to hardware device registers is exactly what you have been taught never to do, because one of the primary purposes of an OS is to control device access. However, an OS call is at least tens of microseconds of overhead. For custom network hardware like TTL_PAPERS, which can perform a basic network operation in just 3 microseconds, such OS call overhead is intolerable. The only way to avoid that overhead is to have user-level code - a user-level library - directly access hardware device registers. Thus, the question becomes one of how a user-level library can access hardware directly, yet not compromise the OS control of device access rights.
On a typical system, the only way for a user-level library to directly access hardware device registers is to:
mmap()
call (first mentioned in section 2.6) can be used to map a special
file which represents the physical memory page addresses of the I/O
devices. Alternatively, it is relatively simple to write a device
driver to perform this function. Further, this device driver can
control access by only mapping the page(s) containing the specific
device registers needed, thereby maintaining OS access control.
*((char *) 0x1234) =
5; would store the byte value 5 into memory location 1234
(hexadecimal).Fortunately, it happens that Linux for the Intel 386 (and compatible processors) offers an even better solution:
ioperm() OS call from a privileged process,
get permission to access the precise I/O port addresses that
correspond to the device registers. Alternatively, permission can be
managed by an independent privileged user process (i.e., a "meta OS")
using the
giveioperm() OS call patch for Linux.
This second solution is preferable because it is common that multiple I/O devices have their registers within a single page, in which case the first technique would not provide protection against accessing other device registers that happened to reside in the same page as the ones intended. Of course, the down side is that 386 port I/O instructions cannot be coded in C - instead, you will need to use a bit of assembly code. The GCC-wrapped (usable in C programs) inline assembly code function for a port input of a byte value is:
extern inline unsigned char
inb(unsigned short port)
{
unsigned char _v;
__asm__ __volatile__ ("inb %w1,%b0"
:"=a" (_v)
:"d" (port), "0" (0));
return _v;
}
Similarly, the GCC-wrapped code for a byte port output is:
extern inline void
outb(unsigned char value,
unsigned short port)
{
__asm__ __volatile__ ("outb %b0,%w1"
:/* no outputs */
:"a" (value), "d" (port));
}
PVM (Parallel Virtual Machine) is a freely-available, portable, message-passing library generally implemented on top of sockets. It is clearly established as the de-facto standard for message-passing cluster parallel computing.
PVM supports single-processor and SMP Linux machines, as well as clusters of Linux machines linked by socket-capable networks (e.g., SLIP, PLIP, Ethernet, ATM). In fact, PVM will even work across groups of machines in which a variety of different types of processors, configurations, and physical networks are used - Heterogeneous Clusters - even to the scale of treating machines linked by the Internet as a parallel cluster. PVM also provides facilities for parallel job control across a cluster. Best of all, PVM has long been freely available (currently from http://www.epm.ornl.gov/pvm/pvm_home.html), which has led to many programming language compilers, application libraries, programming and debugging tools, etc., using it as their "portable message-passing target library." There is also a network newsgroup, comp.parallel.pvm.
It is important to note, however, that PVM message-passing calls generally add significant overhead to standard socket operations, which already had high latency. Further, the message handling calls themselves do not constitute a particularly "friendly" programming model.
Using the same Pi computation example first described in section 1.3, the version using C with PVM library calls is:
#include <stdlib.h>
#include <stdio.h>
#include <pvm3.h>
#define NPROC 4
main(int argc, char **argv)
{
register double lsum, width;
double sum;
register int intervals, i;
int mytid, iproc, msgtag = 4;
int tids[NPROC]; /* array of task ids */
/* enroll in pvm */
mytid = pvm_mytid();
/* Join a group and, if I am the first instance,
iproc=0, spawn more copies of myself
*/
iproc = pvm_joingroup("pi");
if (iproc == 0) {
tids[0] = pvm_mytid();
pvm_spawn("pvm_pi", &argv[1], 0, NULL, NPROC-1, &tids[1]);
}
/* make sure all processes are here */
pvm_barrier("pi", NPROC);
/* get the number of intervals */
intervals = atoi(argv[1]);
width = 1.0 / intervals;
lsum = 0.0;
for (i = iproc; i<intervals; i+=NPROC) {
register double x = (i + 0.5) * width;
lsum += 4.0 / (1.0 + x * x);
}
/* sum across the local results & scale by width */
sum = lsum * width;
pvm_reduce(PvmSum, &sum, 1, PVM_DOUBLE, msgtag, "pi", 0);
/* have only the console PE print the result */
if (iproc == 0) {
printf("Estimation of pi is %f\n", sum);
}
/* Check program finished, leave group, exit pvm */
pvm_barrier("pi", NPROC);
pvm_lvgroup("pi");
pvm_exit();
return(0);
}
Although PVM is the de-facto standard message-passing library, MPI (Message Passing Interface) is the relatively new official standard. The home page for the MPI standard is http://www.mcs.anl.gov:80/mpi/ and the newsgroup is comp.parallel.mpi.
However, before discussing MPI, I feel compelled to say a little bit about the PVM vs. MPI religious war that has been going on for the past few years. I'm not really on either side. Here's my attempt at a relatively unbiased summary of the differences:
Put simply, PVM has one and MPI doesn't specify how/if one is implemented. Thus, things like starting a PVM program executing are done identically everywhere, while for MPI it depends on which implementation is being used.
PVM grew-up in the workstation cycle-scavenging world, and thus directly manages heterogeneous mixes of machines and operating systems. In contrast, MPI largely assumes that the target is an MPP (Massively Parallel Processor) or a dedicated cluster of nearly identical workstations.
PVM evidences a unity of purpose that MPI 2.0 doesn't. The new MPI 2.0 standard includes a lot of features that go way beyond the basic message passing model - things like RMA (Remote Memory Access) and parallel file I/O. Are these things useful? Of course they are... but learning MPI 2.0 is a lot like learning a complete new programming language.
MPI was designed after PVM, and clearly learned from it. MPI offers simpler, more efficient, buffer handling and higher-level abstractions allowing user-defined data structures to be transmitted in messages.
By my count, there are still significantly more things designed to use PVM than there are to use MPI; however, porting them to MPI is easy, and the fact that MPI is backed by a widely-supported formal standard means that using MPI is, for many institutions, a matter of policy.
Conclusion? Well, there are at least three independently developed, freely available, versions of MPI that can run on clusters of Linux systems (and I wrote one of them):
No matter which of these (or other) MPI implementations one uses, it is fairly simple to perform the most common types of communications.
However, MPI 2.0 incorporates several communication paradigms that are fundamentally different enough so that a programmer using one of them might not even recognize the other coding styles as MPI. Thus, rather than giving a single example program, it is useful to have an examp