first acquire the lock associated with it. This lock is held
until the iteration terminates, at which point the iteration
releases all of its locks. If an iteration is unable to acquire a
lock on an object, this means that a second iteration is currently accessing the object, and one of the two iterations
must be rolled back. Rollbacks are accomplished by copying
an object before it is modified, and restoring from that copy
upon rollback. Thus, in a system in which all objects use the
catch-and-keep policy, serialization of iterations is easy to
ensure. Acquiring and releasing locks, making backup copies of objects, etc., is performed automatically by our run-time system, as explained in Section 3. 3. It is also possible to
use hardware transactional memory (TM). 7
While catch-and-keep classes are simple to implement,
they may not provide enough concurrency. Work-sets are themselves data structures, and they are implemented using classes
in the Galois library. Since each iteration gets an element from
the work-set at the beginning and may add elements to it at the
end, a catch-and-keep implementation of the work-set class
would permit only one iteration to execute at a time.
Catch-and-release Classes: To solve this problem,
the Galois system supports the catch-and-release policy
for concurrently accessed objects such as the graph and
work-set in mesh refinement, or the kd-tree in agglomerative clustering. To access a catch-and-release object, an
iteration must acquire the lock on the object. However,
unlike in catch-and-keep, the lock is released as soon as
the method completes. Releasing the lock allows interleaving of method invocations from different iterations, which
increases concurrency.
The key problem in catch-and-release is to ensure that
the method interleavings do not violate serializability of
iterations. This is nontrivial, as demonstrated by the programs in Figure 7, which show iterations manipulating
a set that supports add, remove, and contains, with
the standard semantics. In Figure 7(a), we see that in any
sequential execution, the call contains(x) will return
false. However, for the interleaving shown in the figure, the
call will return true. On the other hand, for the program
in Figure 7(b), all possible interleavings of the methods
match a serial execution. For a catch-and-release object,
figure 7. interleaving method invocations from different iterations.
Set S
S.add(x)
S.add(x)
Set S
S.contains?(x)
S.contains?(y)
S.remove(x)
S.remove(x)
(a)
(b)
how can we determine which interleavings are legal, and
which should be disallowed?
The key is semantic commutativity, described at the
beginning of this section. Method invocations to a given
object from two iterations can be interleaved safely provided that the final abstract state is consistent with some
serial order of iteration execution. In Figure 7(a), the invocation contains(x) does not commute with the operations from the other thread, so the invocations from the
two iterations must not be interleaved. In Figure 7(b),
contains(y) commutes with the other operations, so
the iterations can execute in parallel. Note that commutativity may depend on the arguments or return values of
methods.
Because iterations are executed in parallel, it is possible for commutativity conflicts to prevent an iteration
from completing, requiring that iterations be rolled back.
Because semantic commutativity does not track the concrete state of an object, simply creating copies of the concrete state (as in catch-and-keep classes) does not suffice.
Instead, every method of a catch-and-release object that
may modify the state of that object must have an associated
inverse method that undoes the side-effects of that method
invocation. For example, for a set that does not contain x,
the inverse of a method invocation that adds an element x
to a set is a method invocation that removes it from that set.
As in the case of commutativity, what is relevant for our purpose is an inverse in the semantic sense; invoking a method
and its inverse in succession may not restore the concrete
data structure to what it was.
Note that when an iteration rolls back, all of the methods
which it invokes during roll-back must succeed. Thus, we
must never encounter conflicts when invoking inverse methods. When the Galois system checks commutativity, it also
checks commutativity with the associated inverse method.
Putting It All Together: ADT commutativity and undo must
be specified by the class designer. Figure 8 illustrates how
figure 8. example Galois class for a set.
class Set {
//interface methods
void add ( Element x );
[ commutes ]
— add ( y ) { y != x }
— remove (y) {y != x}
— contains (y) {y != x}
[ inverse ] remove (x)
void remove ( Element x );
[ commutes ]
— add ( y ) { y != x }
— remove (y) {y != x}
— contains (y) {y != x}
[ inverse ] add ( x )
boolean contains ( Element x );
[ commutes ]
— add ( y ) { y != x }
— remove (y) {y != x}
— contains (*)//any call to contains