## Tuesday, February 1, 2011

### Thinking/Drinking in Parallel in ParaSail

As mentioned in an earlier post, we have put up a "Drinking Philosopher's" example in the google group for ParaSail:

When writing this example, there was only one loop which ended up sequential which seems like it could have been concurrent -- the one in the Eliminate_Duplicates function:

```    function Eliminate_Duplicates(Bottle_Map : Phil_To_Bottle_Map)
-> Result : Phil_To_Bottle_Map
{(for all P1 in Philosopher_Index =>
for all P2 in Philosopher_Index =>
if P1 != P2 then Result[P1] * Result[P2] == [])}
// Ensure that there are no duplicates in resulting mapping
{(for all B in Bottle_Index => for some P in Philosopher_Index =>
B in Result[P])}
// Ensure that every bottle is somewhere
is
var Earlier_Bottles : Bottle_Set := [];

for Phil in Philosopher_Index loop
// Remove bottles assigned to earlier philosophers
// NOTE: We don't actually need a "forward loop" here
//       so long as the loop runs sequentially.
//       "Earlier" bottles merely means earlier iterations,
//       independent of the order in which they are performed.
Result[Phil] := Bottle_Map[Phil] - Earlier_Bottles;
Earlier_Bottles += Result[Phil];
end loop;

if Count(Earlier_Bottles) != Num_Bottles then
// Some bottles not assigned to anyone
// Give them to Philosopher 1
Result[1] += [1..Num_Bottles] - Earlier_Bottles;
end if;

end function Eliminate_Duplicates;
```

When first written, it was written as a forward loop, but after looking at the logic, it became clear that there was no particular dependence on order, so making it the default unordered loop seemed preferable.  But upon further thought, it seems that there is a straightforward concurrent solution to removing duplicates from a mapping like this.

The input mapping (Bottle_Map) is a map from philosophers to bottles, where to make it interesting, multiple philosophers are interested in the same bottle.  However, to start the simulation going, we want to know where the bottles should start out, so we want a mapping from philosophers to bottles that has no duplicates; that is, a bottle is associated with only one philosopher.  As you can see above, we eliminated duplicates by accumulating a set of bottles already assigned (Earlier_Bottles) as we went through the sequence of philosophers, and subtracted this set from each set of bottles in the Bottle_Map as we processed the next philosopher.  This is inherently a sequential algorithm (even if the actual sequential order doesn't matter).

If we want to think in parallel, we might think about a more free for all approach.  Namely, each philosopher tries to grab each of the bottles of interest, and first come, first serve!  It turns out with this approach there is one danger: if we end up with a perfectly symmetrical initial state, such that each philosopher ends up with one of the two bottles they want, then the simulation could enter an immediate deadlock.

In Chandy and Misra's paper, they show that so long as the initial graph of preferences is not cyclic, then the individual steps will preserve the acyclic nature.  We accomplished this originally with the sequential loop, where the first philosopher gets all of the bottles they want, the next gets all but those already assigned, and so on.  This avoids starting out with a symmetric, deadlock-prone, cyclic preference graph.

We can accomplish the same thing in a series of concurrent loops using a different approach: we initialize the bottles and bar stools to a default state, and then complete the initialization incrementally, rather than trying to precompute the initial mapping of philosophers to bottles:

```    var Bottles : Array<Bottle, Indexed_By=> Bottle_Index> :=
[Bottle_Index => Create(1)];

var Bar_Stools : Array<Bar_Stool, Indexed_By=> Philosopher_Index> :=
[Philosopher_Index => Create([])];

for Phil in Philosopher_Index concurrent loop
for B in Who_Drinks_What[Phil] concurrent loop
Set_Initial_Owner(Bottles[B], Phil);
end loop;
end loop;

for B in Bottle_Index concurrent loop