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:

    http://groups.google.com/group/parasail-programming-language

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
        Add_Initial_Bottle(Bar_Stools[Initial_Owner(Bottles[B])], B);
    end loop;

The new operations, Set_Initial_Owner/Initial_Owner, and Add_Initial_Bottle, would have to be added to the Bottle and Bar_Stool interfaces, respectively. Set_Initial_Owner would update the bottle's Who_Gets_It field only if the new owner had a higher Philosopher_Index, thereby ensuring the acyclic preference graph. Originally initializing the Who_Gets_It to a default value of 1 ensures that Philosopher 1 ends up with any bottles of no interest to anyone. The Initial_Owner function would simply return the value of Who_Gets_It for the given Bottle, which, at the point of call, is the Philosopher with the highest index with an interest in the bottle. The Add_Initial_Bottle operation would then add the given bottle to the Used_Bottles set of the Bar_Stool associated with that highest-numbered Philosopher.

Clearly a programmer's goal with a language like ParaSail is to minimize the amount of sequential code, so that as the number of available processors goes up, the program will have the parallelism to take advantage of them. Having primitives which make it easy and safe to do things concurrently helps, but the programmer will still have to shift their thinking a bit to achieve the full potential benefit.