Use spmdReduce to Achieve MPI_Allreduce Functionality

Introduction

When doing parallel programming, we often run into the situation of having a variable defined on all workers, and we want to perform an operation on the variable as it exists on all workers. For example, if we enter an spmd statement and define

spmd
    x = spmdIndex;
end

on all workers, we might want to calculate the sum of the values of x across the workers. This is exactly what the spmdPlus operation does, it sums the x across the workers and duplicates the result on all workers:

spmd
    s = spmdPlus(x);
end

The variables assigned to inside an spmd statement are represented on the client as Composite. We can bring the resulting values from the workers to the client by indexing into the Composite much like that of cell arrays:

s{1} % Display the value of s on worker 1.  All workers store the same value.

ans =

    21

Also, spmdReduce, spmdPlus, and spmdCat allow us to specify a single worker to which the function output should be returned, and they return an empty vector on the other workers.

spmd
    s = spmdPlus(x, 1);
end
s{1}

ans =

    21

This example shows how to perform a host of operations similar to addition across all workers. In MPI, these are known as collective operations, such as MPI_SUM, MPI_PROD, MPI_MIN, MPI_MAX, etc.

Create the Input Data for Our Examples

The data we use for all our examples is very simple: a 1-by-2 variant array that is only slightly more complicated than the x we defined in the beginning:

spmd
    x = spmdIndex + (1:2)
end

Using spmdPlus and spmdCat

Now that we have initialized our vector x to different values on the workers, we can ask questions such as what is the element-by-element sum of the values of x across the workers? What about the product, the minimum, and the maximum? As to be expected from our introduction,

spmd
    s = spmdPlus(x);
end
s{1}

ans =

    27    33

returns the element-by-element addition of the values of x. However, spmdPlus is only a special case of the spmdReduce operation. The spmdReduce function allows us to perform any associative operation across the workers on the elements of a variant array. The most basic example of an associative operation is addition; it is associative because addition is independent of the grouping which is used:

(a + b) + c = a + (b + c)

In MATLAB®, addition can be denoted by the @plus function handle, so we can also write spmdPlus(x) as

spmd
    s = spmdReduce(@plus, x);
end
s{1}

ans =

    27    33

We can concatenate the vector x across the workers by using the spmdCat function, and we can choose the dimension to concatenate along.

spmd
    y1 = spmdCat(x, 1); % Concatenate along rows.
    y2 = spmdCat(x, 2); % Concatenate along columns.
end
y1{1}
y2{1}

ans =

     2     3
     3     4
     4     5
     5     6
     6     7
     7     8


ans =

     2     3     3     4     4     5     5     6     6     7     7     8

Other Elementary Uses of spmdReduce

It is simple to calculate the element-by-element product of the values of x across the workers:

spmd
    p = spmdReduce(@times, x);
end
p{1}

ans =

        5040       20160

We can also find the element-by-element maximum of x across the workers:

spmd
    M = spmdReduce(@max, x);
    m = spmdReduce(@min, x);
end
M{1}
m{1}

ans =

     7     8


ans =

     2     3

Logical Operations

MATLAB has even more built-in associative operations. The logical AND, OR, and XOR operations are represented by the @and, @or, and @xor function handles. For example, look at the logical array

spmd
    y = (x > 4)
end

We can then easily perform these logical operations on the elements of y across the workers:

spmd
    yand = spmdReduce(@and, y);
    yor = spmdReduce(@or, y);
    yxor = spmdReduce(@xor, y);
end
yand{1}
yor{1}
yxor{1}

ans =

  1×2 logical array

   0   0


ans =

  1×2 logical array

   1   1


ans =

  1×2 logical array

   1   0

Bitwise Operations

To conclude our tour of the associative operations that are built into MATLAB, we look at the bitwise AND, OR, and XOR operations. These are represented by the @bitand, @bitor, and @bitxor function handles.

spmd
    xbitand = spmdReduce(@bitand, x);
    xbitor = spmdReduce(@bitor, x);
    xbitxor = spmdReduce(@bitxor,  x);
end
xbitand{1}
xbitor{1}
xbitxor{1}

ans =

     0     0


ans =

     7    15


ans =

     1    11

Finding Locations of Min and Max

We need to do just a little bit of programming to find the spmdIndex corresponding to where the element-by-element maximum of x across the workers occurs. We can do this in just a few lines of code:

type pctdemo_aux_gop_maxloc

function [val, loc] = pctdemo_aux_gop_maxloc(inval)
%PCTDEMO_AUX_GOP_MAXLOC Find maximum value of a variant and its spmdIndex.
%   [val, loc] = pctdemo_aux_gop_maxloc(inval) returns to val the maximum value
%   of inval across all workers.  The spmdIndex where this maximum value
%   resides is returned to loc.

%   Copyright 2007 The MathWorks, Inc.

    out = spmdReduce(@iMaxLoc, {inval, spmdIndex*ones(size(inval))});
    val = out{1};
    loc = out{2};
end

function out = iMaxLoc(in1, in2)
% Calculate the max values and their locations.  Return them as a cell array.
    in1Largest = (in1{1} >= in2{1});
    maxVal = in1{1};
    maxVal(~in1Largest) = in2{1}(~in1Largest);
    maxLoc = in1{2};
    maxLoc(~in1Largest) = in2{2}(~in1Largest);
    out = {maxVal, maxLoc};
end

and when the function has been implemented, it can be applied just as easily as any of the built-in operations:

spmd
    [maxval, maxloc] = pctdemo_aux_gop_maxloc(x);
end
[maxval{1}, maxloc{1}]

ans =

     7     8     6     6

Similarly, we only need a few lines of code to find the spmdIndex where the element-by-element minimum of x across the workers occurs:

type pctdemo_aux_gop_minloc

function [val, loc] = pctdemo_aux_gop_minloc(inval)
%PCTDEMO_AUX_GOP_MINLOC Find minimum value of a variant and its spmdIndex.
%   [val, loc] = pctdemo_aux_gop_minloc(inval) returns to val the minimum value
%   of inval across all workers.  The spmdIndex where this minimum value
%   resides is returned to loc.

%   Copyright 2007 The MathWorks, Inc.

    out = spmdReduce(@iMinLoc, {inval, spmdIndex*ones(size(inval))});
    val = out{1};
    loc = out{2};
end

function out = iMinLoc(in1, in2)
% Calculate the min values and their locations.  Return them as a cell array.
    in1Smallest = (in1{1} < in2{1});
    minVal = in1{1};
    minVal(~in1Smallest) = in2{1}(~in1Smallest);
    minLoc = in1{2};
    minLoc(~in1Smallest) = in2{2}(~in1Smallest);
    out = {minVal, minLoc};
end

We can then easily find the minimum with spmdReduce:

spmd
    [minval, minloc] = pctdemo_aux_gop_minloc(x);
end
[minval{1}, minloc{1}]

ans =

     2     3     1     1