Parallel Computing in Version 6
and Beyond

Parallelizing Mathematica

Roman E. Maeder

Wolfram Research, Inc.

Environments for Parallel Computing

>From a 2 core laptop to a supercomputer with 100 thousands of processors, there is a wide variety of hardware available for parallel computing. The challenge is to find a uniform interface that adapts to most configurations.

Parallel Mathematica's only requirement is a running kernel and a TCP connection to the master kernel.

Hardware Environments

A bit of history

Parallel Computing Toolkit (PCT) was first available in 1997. At that time we had what we would now call 2 core workstations from Sun and otherwise relied on a 10MB/s ethernet for connection to other machines.

PCT's method to acquire kernels was (and still is) to specify an OS command to remote login and start a kernel.

$RemoteCommand

Starting local kernels under the same system image is straightforward on any OS.

$mathkernel

Finding CPUs

Finding available resources: resources should advertise themselves: zeroconf.

See following presentation on Remote Services.

Managing Clusters

Big, managed clusters do not allow just anyone to log into their nodes. Most are intended primarily for batch jobs.

Our solution: interface with the cluster management software to launch kernels and then pass them to PCT.

See following presentation on Cluster Integration Package.

Future: support batch submission of parallel Mathematica jobs.

Common Interface

The common interface is still the MathLink object that represents the connection to the remote kernel. It will become less visible in the case of local kernels.

Types of Parallel Computing

Doing the same thing many times

A large percentage of what people do with Mathematica involves computations with many independent subtasks.

Performing the same computation with many different inputs

doing a Monte-Carlo simulation

rendering frames of an animation

In a functional style, all of these involve Map[]. To parallelize, simply use ParallelMap[] instead.

Data parallelism

Many operations of the form f[some long list] can be parallelized using this method:

divide the list into as many pieces {(Subscript[e, i]), …, (Subscript[e, j])} as there are processors

compute f[{(Subscript[e, i]), …, (Subscript[e, j])}] in parallel (giving (Subscript[r, k]))

combine the results comb[(Subscript[r, 1]), …, (Subscript[r, m])]

$ParallelCommands

Concurrency

More general parallelism for less structured problems that requires communication among processes.

Note that a process in this context is simply a Mathematica expression to be evaluated (and a processor is a running Mathematica kernel).

A scheduler sends waiting processes to available processor and collects the results.

Domain Decomposition

For the hard cases: as single problem such as a partial differential equation that requires tight interaction among the processors that work on part of the domain. The realm of MPI.

See the following presentation on symmetric multiprocessing.

Parallel Computing Toolkit

All language additions to support the mentioned parallel programming styles are available in a Mathematica package. It makes use of a network of standard Mathematica kernels.

No other code or common file system is necessary.

The notion of programs as data makes even failure recovery rather easy to implement.

PCT interfaces nices with the Workbench, allowing debugging of remote kernels and parallel computations.

Multi-Core Workstations

For the first time, there is an environment for parallel computing that is standardized enough to make automatica setup possible.

On all platforms,

Table[LaunchSlave["localhost"],{4}]

will launch the requested number of kernels. This can obviously be automated.

Note: the statement above is possible even on a single-cpu system. It provides for a good environment to develop and debug parallel code.

The Single-Machine License Redefined

The single-machine Mathematica license will allow a single user to take advantage of all cores in a typical workstation or laptop.

All required components will be part of Mathematica.

Data Parallelism

A large number of computations involves independent operation on the elements of a long list. This includes the independent subtasks mentioned above, where the list is implicit (such as a list of random numbers).

ParallelTable[$ProcessorID,{10}]

Divide et Impera

testing numbers for primality

ParallelEvaluate[{1,2,3,4,5,6,7,8,9,10,11},PrimeQ]

parallel pattern matching: finding all odd elements of a list

ParallelEvaluate[{1,2,3,4,5,6,7,8},Cases[#,_?OddQ]&]

membership testing

ParallelEvaluate[{1,2,3,4,5,6,7},MemberQ[#,5]&,Or]

counting elements

ParallelEvaluate[{1,2,3,4,5,6,7},Count[#,_?PrimeQ]&,Plus]

Automatic Parallelization

Simple upvalues allow for the automatic transformation of expressions involving one of the parallelizable functions.

$ParallelCommands

ParallelEvaluate[Count[{1,2,3,4,5,6,7},_?PrimeQ]]

Ultimate goal

ParallelEvaluate[your program goes here...]

Concurrency

The Life of a Process

pid=Queue[1+2]

Wait[pid]

Watch the scheduler in action.

pids=Queue[PrimeQ[2^#-1]]&/@{1,2,3,4,5,6,7}

SetOptions[$DebugObject,Trace->{Queueing}]

Wait[pids]

SetOptions[$DebugObject,Trace->{}]

Functional Programming and Process Generation

Wait[Queue[expr]] is just the evaluation function (or identity).

Wait[Queue[1+2]]

To evaluate a function remotely, you can use

Wait[Composition[Queue,f][x]]

This observation gives us a powerful recipe for parallelizing functional operations. This example develops a parallel version of the Mathematica function Map[].

Map[f,{a,b,c}]

We compose f with Queue[]. The result is a list of process IDs that represent the individual function applications.

Map[Composition[Queue,f],{a,b,c}]

Wait[] runs the scheduler and returns with the results, which were computed in parallel on any available slave kernels.

Wait[%]

The powerful functional language allows us to derive parallel code automatically.

Speculative Evaluation and Nondeterminism

After submitting a number of processes the master kernel usually has to wait for at least one of them to finish.

It does not need to wait for all of them to finish, however. Processes can be aborted (a kind of parallel ⌘-.)

Searching

Finding an irreducible polynomial by testing random polynomials

Finding a prime in a given range

In general: find an element of an implicit or explicit search space with a desired property

Distribute the search space and run concurrent searches.
As soon as a result comes back, abort all remaining processes.

Try out different methods

Compare different ways of solving the same problem (or compare different versions of Mathematica).

With[{a=Reverse/@Distribute[{{-32,-16,0,16,32},{-32,-16,0,16,32}},List]},f[x_,y_]:=1/(0.002+Plus@@MapIndexed[1/(#2[[1]]+Plus@@(({x,y}-#1)^6))&,a])
]

ranges={{x,-50,50},{y,-50,50}};

Plot3D[f@@First/@ranges,Evaluate[Sequence@@ranges]]

tryMethod[method_]:=
Module[{time,res},
{time,res}=Timing[NMinimize[f[x,y],ranges,Method->method,PrecisionGoal->12]];
Join[{method/.{meth_,___}:>meth,time/.Second->1},res]
]

methods={
"DifferentialEvolution",
"NelderMead",
"RandomSearch",
"SimulatedAnnealing",
Automatic
};

tryMethod[methods[[1]]]

In parallel

ExportEnvironment[f,ranges,tryMethod]

TableForm[ParallelMap[tryMethod,methods],TableDepth->2,TableHeadings->{None, {Method,Timing,Minimum,Position}}]

Let the first one win

trials=tryMethod/@Hold@@Complement[methods,{Automatic}];

ParallelTry@@trials

Shared Resources

For non-trivial problems, there is some communication among the running processes.

Some resources are shared (sequential) and access needs to be synchronized.

Distributed Values

Distribute the current definitions of variables and functions to all kernels, but let each one maitain its own independent local copy thereafter.

Used for distributing code and parameters.

ExportEnvironment[variable, function,…]

RemoteNeeds["Package`"]

Kernels can be initialized solely through the existing MathLink connection, no common file system or code distribution is necessary.

Shared Variables

Variables global to the computation. There is only one copy, maintained by the master kernel. All access is through callbacks to the master kernel.

SharedVariables[{x}]; x=0;

SetOptions[$DebugObject,Trace->{SharedMemory}];

RemoteEvaluate[x=x+1, $Slaves[[1]]]

RemoteEvaluate[x,$Slaves[[2]]]

SetOptions[$DebugObject,Trace->{}];
ClearShared[x];

Synchronization

What if two kernels do x=x+1 at the same time?

What if two kernels write to the same file at the same time?

Locking

Parallel Computing Toolkit contains all primitives needed to implement locking and exclusive access to critical sections.

Here, we run five processes that all access a shared variable y, first reading it and sometime later updating it. The code in between is protected by obtaining a lock and releasing it afterward.

SharedVariables[{y,lock}]

y=0;
ParallelMap[Module[{a},
	Pause[Random[]];
	While[TestAndSet[lock,#]=!=#,Pause[0.1Random[]]];
	a=y;
	Pause[0.5Random[]];
	y=a+1;
	lock=Null;
	a+1]&,
  Range[5]]

ClearShared[y,lock]

Shared Definitions

Shared variables for downvalues (definitions of functions).

SharedDownValues[f]

RemoteEvaluate[f[$ProcessID]=$MachineName]

?f

ClearShared[f]

Can even do parallel dynamic programming.

Callbacks, Threads

Shared variables are essentially implemented via shared downvalues. The callback is atomic (thread-safe), and can therefore be used for synchronization.

Example: Parallel Sow and Reap

Parallelizing Sow/Reap: sow on the slave kernels, reap all results in the master kernel. But the calls of Sow[] need to be executed on the master, not the slaves, where they are generated. We define an auxiliary shared downvalue sow[e].

sow[e_]:=(Sow[e];Null)
Protect[sow];
SharedDownValues[sow]

The extra Null prevents the value being needlessly sent back to the remote kernel where it came from.

Reap[
RemoteEvaluate[sow[$ProcessorID]]
]

ClearShared[sow]

Great for parallel searching.

Dynamic

Great new toy: Dynamic variants of PCT's inspection features.

Setup

Simplify`PiecewiseThread;
PiecewiseDump`$ShowIntegrals=True;

Length[pieces=List@@Integrate[Abs[(-x2 y1+x3 y1+x1 y2-x3 y2-x1 y3+x2 y3)],{x1,0,1},{x2,0,1},{x3,0,1},{y1,0,1},{y2,0,1},{y3,0,1}]]

IntegrateWithAssumptions[integrand_,dx__,opts___?OptionQ]:=Module[{ineqs=#2<#1<#3&@@@{dx},conds,simp=Simplification/.{opts}/.Options[IntegrateWithAssumptions],assum=Assumptions/.{opts}/.Options[IntegrateWithAssumptions]},conds=And@@@NestList[Most,Most[ineqs],Length[ineqs]-1];
Fold[simp[Integrate[#1,#2[[1]],Assumptions->assum&&#2[[2]]],assum&&#2[[2]]]&,integrand,Transpose[{Reverse[{dx}],conds}]]]
Options[IntegrateWithAssumptions]={Simplification->Simplify,Assumptions->True};

item[pid_]:=Replace[ProcessState[pid],{
queued:>Item[Process[pid]/.IntegrateWithAssumptions->Integrate],
running[s_]:>Item[Process[pid]/.IntegrateWithAssumptions->Integrate,Background->Yellow],
finished[r_]:>Item[r,Background->Green],
else_:>Item[else,ItemStyle->Red]
}]

pidDisplay[pids_List]:=
Grid[Composition[Through,{ProcessID,item}]/@pids,Dividers->{False,All}]

ExportEnvironment[IntegrateWithAssumptions]

Run it

ids=Queue@@@(List@@pieces/.Integrate->IntegrateWithAssumptions);
Length[ids]

NotebookOpen["WTC07-Parallel-popup.nb"];

CheckAbort[
up=0;While[$QueueLength>0,If[QueueRun[],up++,Pause[0.1]]],
Print["aborting..."];
ResetSlaves[];
];up

ClearSlaves[];

Conclusions

A functional, mathematical, language such as Mathematica is enormously better suited to parallel programming than the traditional procedural languages, where the compiler's main function is to infer the programmer's original intention from the low-level code imposed by the language's limitations.

a=Range[5];b=Range[5];

s=0.0;
Do[s+=a[[i]]*b[[i]],{i,Length[a]}];
s

What I really wanted:

Dot[a,b]

Let's use it!