A number of specific numerical problems arise in parallel programming, including use of halos in computation, parallel linear algebra, long range forces, and random number generation.

High Performance Computing (HPC) is an engineering discipline which develops the technology (hardware, algorithms, and software) to deliver cost-effective computational results.

Selection of the appropriate algorithm often requires some knowledge of the likely platform to be used.

• Press, W.H., Teulkolsky S.A., Vetterling, W.T. and Flannery B.P., 1997. Numerical Recipes in FORTRAN 77, (Cambridge: Cambridge University Press). See also the Fortran 90 and C versions. [NR]

• Quinn, M.J., 1994. Parallel Computing: Theory and Practice. New York: McGraw-Hill.

A parallel computer is a set of processors that work together to solve a computational problem. But first: get to know the beast.

Why use a large number of processors?

1. To combine their processing power (e.g. device modelling).
2. To exploit their aggregate memory (e.g. ocean modelling and lattice calculations).
3. To use increased disk space or parallel I/O (e.g. Databases).
4. Explore the phase space of a model independently on each processor (e.g. genetic algorithms).

A generic parallel computer consists of a number of processors connected together.

However this covers a multitude of sins:

• There may be only a few processors (e.g. a dual Pentium)
• The "fast interconnection network" may simply be that the memory of the processors is shared as a central resource (e.g. Silicon Graphics).
• The memory of the processors may be distributed between the nodes (e.g. IBM SP) with a "fast interconnection" network between the nodes.
• The nodes may be connected with ethernet, or fast ethernet (e.g. a cluster).
• The machine may be very expensive or very cheap. I have deliberately not written examples here.

Increasingly we need to focus on "cost-effective" use of computational resources. It may not be cost effective to use an expensive parallel machine with a fast interconnection network to perform independent simulations on each node if there a cluster of machines available which will perform the same task.

The card example demonstrates:

• Speedup. Not necessarily a factor of P on P processors.
• Contention for a resource
• Network bandwidth and latency

• The choice of algorithm may depend on the platform and number of processors
• Load balancing
• Overlapping computation and communication

With 6 decks and 6 people, better to simply give each person a deck: "task farming".

With 1000 decks and 6 people, we would need a queue: "scheduling" (or hungry puppies). Would each person take a single deck, or several decks at each visit to the supervisor? What if the people worked at different speeds?

In parallel processing "superlinear" effects may occur when a speedup of >P is obtained on P processors. This may be for a number of reasons

• The speedup should be measured wrt to the best sequential algorithm on a single node.
• The aggregate memory on several nodes may allow a different algorithm.
• Increased cache on several nodes may allow more of the code and instructions to run in core.

Speedup is of academic interest. It is possible to obtain perfect speedup curves with a poor parallel algorithm if the single node time is slow.

Speed is what counts. When do I get the answer? How large a simulation can I run overnight?

Part of the job of a scheduler is to maximise the number of computational tasks to run subject to the constraints imposed by the user. This is a non-trivial task.

Divide up the work into a large number of tasks.

How and when do the tasks need to communicate with other? Do they communicate globally, or locally?

Gather the tasks together. Can tasks which need to communicate often be brought together? Are there load balancing issues?

Map the tasks onto the processors.

In this simple example, we have 16 tasks and 4 (and 8) processors.

A number of tricks exist to reduce the communication in addition to the agglomeration. In this case some of the data is replicated in a "buffer zone" to decrease the amount of communication required.

This one suffers from load balancing problems

Good libraries exist for most common linear algebra tasks.

The hardest part is that the optimal layout for one part of a complex piece of code may be the worst in another part. Compromises have to be made!

Though it is bad practice, this sometimes means a global data transfer midway through a run, or replicated data sets on each node.

Scalable parallel computing requires O(N) algorithms (where N is some number of grid points, for example).

This is because the most general constraint on running a code is how long you are prepared to wait for results. Given a larger number of nodes, this usually remains the same, and so the question becomes "how large a problem can I now run given the additional nodes."

An O(N²) algorithm would only solve a problem twice as large given 4 nodes, if it were 100% efficient.

A naïve implementation of an N body problem scales with N². Techniques exist which scale with O(N log N) and O(N).

Considerable effort has been put into designing efficient O(N log N) and O(N) algorithms to perform e.g. convex hull, Delaunay triangulation.

O’ Rourke, J., 1993. Computational Geometry in C. Cambridge: Cambridge University Press.

Pseudo-Random number generators exhibits small fluctuations from truly random behaviour.

A random number generator typically has a seed, from which subsequent random numbers are generated.

Generating random numbers on parallel machines requires:

• High quality random numbers. Some current random number generators spectacularly fail tests of randomness
• Large periods. A generator with a long period of a few years ago can now be exhausted in a few hours on a Pentium.
• The simulation must be repeatable independent of the number of processors used.

• We should be able to compute any number in the sequence without stepping through all of the preceding numbers.

The previous generation of random number generators does not measure up on most of these accounts.

The new generation of generators, pioneered by Marsaglia and others meet all of these requirements.

It is worth noting that the new generation of random number generators were only designed to fix the quality issue on sequential processors, but happen simultaneously to fix all the problems of parallel random number generation. Oh yes, and they are also faster by up to a factor of 2 (or more) than other generators. There may not be such a thing as a free lunch, but…

A new generation random number generator typically has an immense period, a seed vector, from which any number in the sequence may be precomputed.

As an example of the incredible periods available recall that those in Numerical Recipes in Fortran 77 have a period of 2^31-1 (~2e9). Generators now exist with a period of 2^19937 - 1, a number with about 6000 decimal digits; the 32-bit random numbers exhibit best possible equidistribution properties in dimensions up to 623. A DEC Alpha Station would require about 10^5983 millennia to exhaust the period.

When any number in the sequence can be precomputed in advance, parallelism is trivial. Simply start each processor on the random number m p / P, where p = processor number p of P in total, m = period.

Parallel programming for scientific and engineering problems is (or should be) "the norm."

• The definition and goalposts of parallel programming are always changing, which results in the observation that parallel computing has always been "getting easier".

• The single node performance of the code is crucial.
• Using P nodes introduces some overhead. The only task is to reduce this overhead subject to the constraint of solving the problem in reasonable time.

• At present the choice of algorithm may depend upon the machine to be used. Ideally this should be the other way round.
• A number of special problems arise when using a parallel machine, such as how to arrange data in the code, and how to generate random numbers.

Parallel computing can be summed up by single node performance and scalability.