Restricted process groups

At the end of Section 2 we saw that in fact the DAD should be able to reference a restricted slice of a process grid. Specifically what is needed is the ability to reference a portion of a process grid selected by fixing the coordinates in any subset of the dimensions to single values. Figure 5 gives some examples.

Figure 5: Example restricted groups in a 2-dimensional process grid

Luckily there is a very compact way to represent this kind of subgroup. If we call the horizontal dimension in the figure dim(0) and the vertical dimension dim(1), then a) represents the whole of the grid and has dimension set $\{\mbox{\tt dim(0)},\mbox{\tt dim(1)}\}$, b) has dimension set $\{\mbox{\tt dim(0)}\}$, c) has dimension set $\{\mbox{\tt dim(1)}\}$, and d) has the empty dimension set $\{\}$. With the dimension set given, a group can be uniquely specified by its lead process--the process with coordinates 0 relative to the effective dimensions. In our examples a) has lead process 0, b) has lead process 8, c) has lead process 1, and d) has lead process 6.

The dimension set can be represented as a subset of the parent grid dimensions using a bitmask. Since any reasonable grid will have less than 32 dimensions, this bitmask will always fit in a single word. So we see that our 4 examples can be parametrized by the tuples $(11_2, 0)$, $(10_2, 8)$, $(01_2, 1)$ and $(00_2, 6)$, respectively, together with a pointer to the Procs object representing the parent grid.

The Group class will have an interface like

    class Group {
    public:
        Group(const Procs& p) ;

        void restrict(Dimension d, const int coord) ;

        int member() const ;
        ...
    } ;

and it can be implemented in about 3 words of memory. So Group objects can be freely copied and discarded: they fit naturally in the DAD. The conversion constructor provides a user-defined type conversion from a process grid object to a group object representing the whole of the grid. The restrict() method restricts the group in one of its dimensions.