Automatic Parallelism

Roman E. Maeder

Wolfram Research

We look at several aspects of automating the parallelization of evaluations, including load balancing, code distribution, data parallelism, and program transformation.

Introduction

Mathematica contains all tools needed to develop and run parallel programs, that is, programs that send off parts of an evaluation to available Mathematica kernels and synchronize sending expressions and receiving results.

The tools offer great flexibility, but require a fair understanding of parallel programming techniques.

Many of the frequently encountered calculation types can be automated, however, essentially writing

Parallelize[..your program goes here..]

The topics covered in this presentation are

Load Balancing

Data Parallelism

Code Distribution

Program Analysis

All examples are computed live using this many subkernels:

$KernelCount

Load Balancing

Distribution of many similar evaluations to available subkernels

ParallelMap[f,{a,b,c,d,e}]

The challenge is to decide on how many pieces (individual jobs for the subkernels) to create, between the two extremes:

Individual jobs for all elementary evaluations. This choice creates the largest number of jobs for best load balancing, but also maximises the amount of communication.

ParallelMap[Labeled[Framed[#],$KernelID]&,Range[10],Method->"FinestGrained"]

One job per kernel with several elementary evaluations. This choice does no load balancing, but minimises communication.

ParallelMap[Labeled[Framed[#],$KernelID]&,Range[10],Method->"CoarsestGrained"]

The default scheduling is a balanced mixture that allows for some load balancing, while avoiding gross inefficiencies for a large number of simple evaluations.

ParallelMap[Labeled[Framed[#],$KernelID]&,Range[10],Method->Automatic]

Watch scheduling in action

Observing a parallel calculation can help you identify inefficiencies.

Emulate FinestGrained with ParallelSubmit/WaitAll, submitting all evaluations individually, then running the scheduler and waiting for all evaluations to finish.

factors=Table[ParallelSubmit[{i},Plus@@FactorInteger[2^i-1][[All,2]]],{i,195,180,-1}];
PrintTemporary[factors];
WaitAll[factors]

Obtain timing statistics

Rather than only watching the scheduling, you can instrument your program and collect statistics for further analysis along the way.

A shared function for recording timings.

record[k_,t_]:=AppendTo[counts[[k]],t];
SetSharedFunction[record]

Setup the dynamic display.

ids=ParallelEvaluate[$KernelID];mi=Max[ids];
counts=Table[{0},{mi}];
Dynamic[BarChart[counts[[ids]],PerformanceGoal->"Speed",ChartLayout->"Stacked",ChartLabels->{ids,None}]]

Run a calculation.

ParallelTable[Module[{t},t=Timing[Plus@@FactorInteger[2^i-1][[All,2]]];
record[$KernelID,t[[1]]];t[[2]]],
{i,192,160,-1},Method->"FinestGrained"]

Efficient distribution of a large number of small evaluations

pop up the parallel kernel status here

The most efficient scheduling for evaluations that all take the same amount of time.

AbsoluteTiming[ sines=ParallelTable[Integrate[Cos[Sin[p]x],{x,0.0,1}],{p,0.0,1.0,0.005},Method->"CoarsestGrained"];]

Beware:

AbsoluteTiming[ sines=ParallelTable[Integrate[Cos[Sin[p] x],{x,0.0,1}],{p,0.0,1.0,0.005},Method->"FinestGrained"];]

The default scheduling avoids gross mistakes.

AbsoluteTiming[ sines=ParallelTable[Integrate[Cos[Sin[p]x],{x,0.0,1}],{p,0.0,1.0,0.005}];]

Example: Calculate and display the Feigenbaum (or bifurcation) diagram of the logistics map

line[r_,dy_,np_,n0_,n_]:=Module[{pts},
With[{logistics=Function[x,r x(1-x)]},
pts=Join@@NestList[logistics,Nest[logistics,RandomReal[{0,1},np],n0],n-1]];
Log[1.0+BinCounts[pts,{0,1,dy}]]]

With[{w=600,h=350,r0=2.95,r1=4.0},
ArrayPlot[ParallelTable[line[r,1/(w-1),w,1000,100],{r,r0,r1,(r1-r0)/(h-1)}],ImageSize->{w,h},PixelConstrained->True]]

Data Parallelism

Common theme: Independent operations on long lists

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

Select[Range[20],PrimeQ]

Count[Range[10^6],_?PrimeQ]

Prime[{1,2,3,4,5,6}]

Inner[t,{a,b,c},{x,y,z},p]

Parallelization

Break the computation into smaller instances, each working on a part of the original list, then combine the results.

ParallelCombine[Map[f,#]&,{a,b,c,d}, Join]

ParallelCombine[Select[#,PrimeQ]&,Range[20],Join]

Join is the default combination function.

ParallelCombine[Select[#,PrimeQ]&,Range[20]]

If it is not suitable, we have to let it know what to do.

ParallelCombine[Count[#,_?PrimeQ]&,Range[10^6], Plus]

It also works for listable functions.

ParallelCombine[Prime,{1,2,3,4,5,6}]

Sometimes we need to be a bit clever.

ParallelCombine[p@@t@@@#&,Transpose[{{a,b,c},{x,y,z}}]]

Automatic Transformation

The similarity of these example is obvious. We can easily teach Mathematica to do it for us.

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

Parallelize[Select[Range[20],PrimeQ]]

Parallelize[Count[Range[10^6],_?PrimeQ]]

Parallelize[Prime[{1,2,3,4,5,6}]]

Parallelize[Inner[t,{a,b,c},{x,y,z},p]]

All such cases:

Parallel`Developer`$ParallelCommands

Iterators

Be efficient! Do not expand ranges or iterators.

Parallelize[Count[Range[10^7],_?PrimeQ]]

How it works:

ParallelCombine[Hold,Table[i,{i,20}]]

Code Distribution

You may take this for granted:

Parallelize[Select[Range[500],testf]]

However, for this to work, the definition of testf (and its dependencies!) has to be made known to all subkernels in some way. The function that does that is

DistributeDefinitions[f, g, h,…]

It is invoked automatically on all symbols from the default context that appear in a parallel calculation, so that interactive experiments work without any hassle.

It is not used automatically on symbols from packages, however. When you develop a package, you have to consider which definitions needs to be distributed and issue the necessary commands. You may also have to perform other initializations.

Program Analysis

What about

Parallelize[your program...]

Obviously use pattern matching to discover parallelizable parts, and evaluate the rest sequentially.

SetOptions[$Parallel,Tracers->{SendReceive}];

Parallelize[
list=Table[First/@FactorInteger[2^i-1],{i,100,107}];
bases=Times@@@list;
Max@@bases
]

SetOptions[$Parallel,Tracers->{}];

Peek inside

Parallelize does not evaluate its argument, but it may have to peek inside.

list={1,2,3,4};
Parallelize[Times@@list]

If all else fails, give up

Parallelize[f[a,b,c]]

Silently, in some cases.

Parallelize[myfun[x_]:=x^2]

The End

Much more can be done. Not covered here are questions of discovering dependencies, distribution of large data sets, and symmetric multiprocessing.