Virtual Shared Memory

Shared Memory versus Distributed Memory

Special-purpose multiprocessing hardware comes in two types, shared memory and distributed memory. In a shared-memory machine, all processors have access to a common main memory. In a distributed-memory machine, each processor has its own main memory, and the processors are connected through a sophisticated network. A collection of networked PCs is also a kind of distributed-memory parallel machine.

Communication between processors is an important prerequisite for all but the most trivial parallel processing tasks. In a shared-memory machine, a processor can simply write a value into a particular memory location, and all other processors can read this value. In a distributed-memory machine, exchanging values of variables involves explicit communication over the network.

Virtual Shared Memory

Virtual shared memory is a programming model that allows processors on a distributed-memory machine to be programmed as if they had shared memory. A software layer takes care of the necessary communication in a transparent way.

The Wolfram Language uses independent kernels as parallel processors. It is clear that these kernels do not share a common memory, even if they happen to reside on the same machine. However, the Wolfram Language provides functions that implement virtual shared memory for these remote kernels.

This is done with a simple programming model. If a variable a is shared, any kernel that reads the variable (simply by evaluating it), reads a common value that is maintained by the master kernel. Any kernel that changes the value of a, for example by assigning it with a=val, will modify the one global copy of the variable a, so that all other kernels that subsequently read the variable will see its new value.

The drawback of a shared variable is that every access for read or write requires communication over the network, so it is slower than access to a local unshared variable.

Declaring Shared Variables and Functions

Declaring shared variables and functions.

The command (RefLink[SetSharedVariable, paclet:ref/SetSharedVariable]) has the attribute (RefLink[HoldAll, paclet:ref/HoldAll]) to prevent evaluation of the given variables, which usually have values.

The effect of (RefLink[SetSharedVariable, paclet:ref/SetSharedVariable]) or (RefLink[SetSharedFunction, paclet:ref/SetSharedFunction]) is that all currently connected and newly launched remote kernels will perform all accesses to the shared variables through the master kernel.

Manipulating the set of shared variables and functions.

Clearing kernels with Parallel`Developer`ClearSlaves[] will also clear any shared variables and downvalues.

Shared Variables

A variable s that has been declared shared with (RefLink[SetSharedVariable, paclet:ref/SetSharedVariable])[s] exists only in the master (local) kernel. The following operations on a remote kernel are redefined so that they have the described effect.

Operations on shared variables.

For technical reasons, every shared variable must have a value. If the variable in the master kernel does not have a value, it is set to (RefLink[Null, paclet:ref/Null]).

Note that other forms of assignments, such as conditional assignments involving side conditions, are not supported.

The customary form of part extraction, s[[i]], will transmit the whole value of s to the slave kernels. Use (RefLink[Part, paclet:ref/Part])[(RefLink[Unevaluated, paclet:ref/Unevaluated])[s],i] to transmit only the i(^th) component.

If a variable is (RefLink[Protected, paclet:ref/Protected]) at the time you declare it as shared, remote kernels can only access the variable, but not change its value.

Basic Example

Start a few local or remote kernels.

ParallelEvaluate[$ProcessID]

Assign the initial value 17 to x and declare x as a shared variable.

x=17;
SetSharedVariable[x]

At least two remote kernels should be running. Assign them to two variables for easier use.

r1=Kernels[][[1]];r2=Kernels[][[2]];

The kernel r1 now has access to the common value of x.

ParallelEvaluate[x,r1]

Kernel r2 can change the value of x to 18.

ParallelEvaluate[x=18,r2]

The local copy of x on the master kernel has been changed as well.

x

Kernel r1 sees the new value, too.

ParallelEvaluate[x,r1]

Shared Functions

A symbol f that has been declared shared with (RefLink[SetSharedFunction, paclet:ref/SetSharedFunction])[f] exists only in the master (local) kernel. The following operations on a remote kernel are redefined so that they have the described effect.

Operations on shared functions.

For technical reasons, every expression of the form f[…] must have a value. If the expression f[…] in the master kernel does not evaluate, the result is set to (RefLink[Null, paclet:ref/Null]).

Note that other forms of assignments, such as conditional assignments involving side conditions, are not supported.

You can define shared functions, as in the following. Be sure that the symbol x does not have a value in either the remote kernels or in the master kernel. The symbol x should not be a shared variable.

If you make a delayed assignment on a remote kernel, the right side of the definition will be evaluated on the kernel where you use the function. Any immediate assignment is always evaluated on the master kernel.

You can implement indexed variables or arrays using shared downvalues of the form x[1], x[2], and so forth.

If a function is (RefLink[Protected, paclet:ref/Protected]) when you declare it as shared, remote kernels can only use it, but not change its definition.

Synchronization

In a situation where several concurrently running remote kernels access the same shared variable for reading and writing, there is no guarantee that the value of a variable is not changed by another process between the time you read a value and write a new value. Any other new value that another process wrote in the meantime would get overwritten.

Example: Critical Sections

This classic example of uncontrolled access to a shared variable illustrates the problem. To try out this example, you should have between two and 10 remote kernels running.

The code inside the first argument of (RefLink[ParallelMap, paclet:ref/ParallelMap]) is the client code that is executed independently on the available remote kernels. The code reads the shared variable y, stores its value in a local variable a, performs some computations (here simulated with (RefLink[Pause, paclet:ref/Pause])), and then wants to increment the value of y by setting it to a+1. But by that time, the value of y is most likely no longer equal to a, because another process will have changed it.

SetSharedVariable[y];

y=0;
ParallelMap[(
Pause[0.4Random[]];
(* begin critical section *)
 a=y;
Pause[Random[]];
y=a+1
(* end critical section *)
)&,
Range[10]]

If this code were run sequentially (by changing (RefLink[ParallelMap, paclet:ref/ParallelMap]) into (RefLink[Map, paclet:ref/Map])), the final value of y would be 10, but with enough parallel processes, it will most likely be lower.

y

The code between reading the variable y and setting it to a new value is called a critical section. During its execution, no other process should read or write y. To reserve a critical section, a process can acquire an exclusive lock before entering the critical section and release the lock after leaving the critical section.

The Wolfram Language provides the function (RefLink[CriticalSection, paclet:ref/CriticalSection])[lck,expr] to acquire a lock, evaluate an expr and then release the lock. Once a process has acquired the lock, no other process can do so. The lock is released when the expression finishes evaluation.

Here is the previous example with the additional code to implement locking. If a kernel fails to acquire a lock, it has no choice but to try again until it eventually succeeds.

Note that between attempts to acquire the lock (inside (RefLink[While, paclet:ref/While])) the process waits for a while. Otherwise, processes waiting to acquire a lock that is reserved for another process will put a heavy load onto the master kernel.

SetSharedVariable[y];

y=0;
ParallelMap[(
Pause[0.4Random[]];
CriticalSection[{lck},
a=y;
Pause[Random[]];
y=a+1;
a+1])&,
Range[10]]

y

Locking slows down a computation because remote processes may have to wait for one another. In this example, the result is essentially sequential execution. You should keep critical sections as short as possible. If two processes each have locks and then try to gain each other's lock, a deadlock will occur in which the process will wait forever.