itaps-parallel Diagram of set-based parallel data

[Tim Tautges]

Hi all,
   As promised, attached is a cartoon describing set-based parallel 
data.  Note I've stuck to the simplest example (as wisely advocated by 
Mark S).  I show the representation of the same mesh in the serial and 
3-processor cases.  I don't show ghosted elements, for simplicity, 
though those "fit" in the model.

PARALLEL

In the parallel representation, each processor has a set it understands 
as "partition1" (labeled "Partn1").  In this example, on each processor, 
that set contains one set corresponding to the part assigned to that 
processor.  The part set contains 3d entities assigned to that 
processor.  In this example, all 3d entities are objects in the 
decomposition, therefore each 3d entity is a member of exactly one Part.

There are other entity sets defined in this mesh, including a boundary 
condition set (BC1), material sets (Matl1, Matl2), and 
application-defined sets (App1-App3).  In this example, the BC1 set 
contains faces in the mesh (2d elements), but not all of them.  Matl1 
and Matl2 are meant to form a covering over 3d elements, defining the 
materials for those elements.  Application-defined sets are for 
arbitrary groupings.  Whether such "shared" sets would exist on 
processors even if there were no set contents on those processors is 
currently implementation-defined, though maybe there should be a common 
convention for that.

Some of the sets on each processor are implicitly linked with sets on 
other processors.  For example, the Partn1 set on each processor is 
linked to the corresponding sets on other procs.  For this set, that 
means that if the mesh were ever to be assembled in a single file, the 
contents of Partn1 on various processors would all go into a single set, 
which would be assigned the union of all tags on that set on all 
processors.  Presumably those tags would all be the same.  Similarly, 
BC1 and Matl1, Matl2 are sets that are implicitly linked and which would 
be combined.  App1-App3 are application-defined sets which would be 
considered separate, even if the mesh was written to a single file. 
Note that the decision or designation of which sets across the 
processors are really the same sets is application- or 
implementation-defined.  In MOAB, we do it based on tag and optionally 
tag value.  So, for example, any set with a "MATERIAL_SET" tag whose 
value is the same is understood to be the same set.  This is used in the 
HDF5-based file writer in MOAB, which writes a single file in parallel 
from all processors.

SERIAL

In the serial case, all sets having implicitly-defined counterparts on 
other processors have been combined.  Thus, part sets (Part1-Part3) are 
contained in the Partn1 set, and there are single BC1, Matl1 and Matl2 
sets.  App1-App3 are still separate, since they were not designated to 
be the same sets.  The Part1-Part3 sets and Matl1-Matl2 sets are 
different coverings of all 3d entities in this mesh for this example. 
The BC1 set includes a subset of 2d entities in the mesh.

DISCUSSION

As I've mentioned before, I've implemented MOAB's parallel reader such 
that any collection of sets which forms a covering over the things I 
want to partition can be used to define the partition.  Thus, in this 
example, one could use Matl1/Matl2 as the part sets.  In this case, 
those sets would serve multiple purposes.  Similarly, I don't see any 
reason we shouldn't allow a given part set to be a member of multiple 
partitions.

Part sets should also be allowed to include sets; in this case, maybe 
the sets are the objects in the partition.  This would be a very nice 
thing to use for e.g. hypergraph partitioning methods. 
Counter-intuitively, I would lean toward using contains relations to go 
down that hypergraph hierarchy.  If a given implementation did not 
implement Parts as legitimate entity sets, then this property could be 
used to reduce bookkeeping for adaptive applications, e.g. have the part 
contain sets which themselves contain 3d elements of a given material or 
geometric volume.  Of course, that assumes you're using sets for those 
other things...

This method for representing partitions also has the following benefits:
- allows multiple partitions to exist in the same file/instance/database
- would allow current set operations to be used to query contents of 
parts and partitions
- parallel view is only different when asking about parallel data; in 
other cases it looks the same as serial interface
- other parts of RPI partition model can be embedded similarly, by using 
sets related to part sets using parent/child relations

I'll be elaborating on this at the SIAM mtg in March, as well as pulling 
in other examples where sets can be used to do various things.  I guess 
that means I've already started my talk, which has to be some sort of 
record for me!

Comments welcome, fire when ready!

- tim



-- 
================================================================
"You will keep in perfect peace him whose mind is
   steadfast, because he trusts in you."               Isaiah 26:3

              Tim Tautges            Argonne National Laboratory
          (tautges at mcs.anl.gov)      (telecommuting from UW-Madison)
          phone: (608) 263-8485      1500 Engineering Dr.
            fax: (608) 263-4499      Madison, WI 53706

-------------- next part --------------
A non-text attachment was scrubbed...
Name: setrels.png
Type: image/png
Size: 71250 bytes
Desc: not available
URL: <http://lists.mcs.anl.gov/pipermail/itaps-parallel/attachments/20071218/a724df02/attachment.png>