itaps-parallel Part handles

Carl Ollivier-Gooch cfog at mech.ubc.ca
Fri Jun 20 13:47:08 CDT 2008


Tim Tautges wrote:
> Hi all,
>   I realize now why I missed this discussion in March, it was in the
> middle of a 3 week/3 trip stretch for me, and I got overwhelmed and
> didn't follow the discussion closely.
> 
> Anyway, this email is an attempt to summarize my objection to embedding
> the proc rank in the part handle.  As background, you should know that I
> almost went this way in MOAB (to the point where it's still implemented
> in MOAB) but ultimately decided not to, for many of the same reasons I
> note below.
> 
> And, sorry if this is dumb and/or offensive, but I still don't see a 
> logical, non-pejorative statement of the problem whose only, or most 
> logical, solution is the two primary requirements causing me such 
> heartburn (part handles must be unique, and processor must be derivable 
> from part handle).  And that's after reading the March email thread at 
> least three times, and thinking about this for at least 4 hours over the 
> last couple of days.
> 
> The remainder of this email consists of 3 parts:
> Part I: my objections
> Part II: questions about the requirements Karen sent out Wed afternoon
> Part III: questions/comments arising while looking through current
> interface draft

Definitions:

Name: Complete unique identifier of something in the data model.
Handle:  Some series of bits of the same size as a void*; interpretation 
of those bits is implementation-dependent.

Summary (50,000 foot view)

What this debate seems to me to reduce to is this:  Should the name of a 
part consist of a local handle plus a process rank (or equivalents); or 
of a single global handle that is also used locally and can be used to 
deduce rank.

10,000 foot view

Personally, I don't see the efficiency issue as a big one:  IMO, the 
overhead of having to translate a part handle to a set handle (for 
instance) can be reduced to no more than a couple of bitwise operations 
and an array lookup, and I think all the affected functions are way more 
expensive than this, especially once you account for the work done on 
the returned data.  That's obviously true for anything with 
communication, anything with a large set of return data, and iteration 
initialization, so I'll omit those functions in my analysis below as 
being completely irrelevant from an overhead point of view.

The strongest argument for handle+rank (IMO) is that this is what's 
currently required for entities.  (Sets have no unique global ID, not 
even those that span processes and probably should have...).  On the 
other hand, a global entity handle space is Right Out for 32-bit 
machines: 4 billion entities / 100K processors = 40K entities/processor, 
which is on the thin side (and requires that all entities of all types 
be numbered consecutively... pointers need not apply).  I doubt that 4 
billion parts (or even a quarter billion, allowing for some wastage) is 
going to be a barrier...  (As an aside, are the huge parallel machines 
32 bit or 64?)

The strongest argument for global handle (IMO) is that the same handle 
is used both locally and globally for a part (perhaps only shifting 
rather than eliminating a translation burden, admittedly), and it looks 
and feels like all the other handles.  This is more elegant, and also 
eliminates some argument bloat in a number of functions.

Single Global Handle

Other advantages of the single global handle is that communication 
partners are clear from the single handle (whether for partitioning or 
for ghosting, etc), and that names for parts are congruent to names for 
all the other things in the data model.

The disadvantage is that for some (probably for all, I'm guessing) 
implementations, there will have to be some intermediate work to get 
from a part handle to the actual memory location where that data is 
stored.  This is already a fact of life for all of us with entity 
handles (I know it is for GRUMMP, and I've seen enough of MOAB part 
handles while debugging the interaction between swapping and MOAB to 
know that it's an issue there, too; FMDB may manage to avoid this 
problem, though I can't imagine how).  Personally, I don't see this as a 
big deal (I've attached an example, based on my expectation that I'll 
probably implement parts as sets with extra stuff, but represent them 
externally as handles that are easily distinguishable from pointers, 
because the low-order bit will be set).

Local functions this may invoke a cost that is not completely trivial:

getNumPartNbors, getPartNbors, getNumPartBdryEnts, isEntOwner, getEntStatus

Code that often asks for entity ownership or status is a potential 
problem from an efficiency point of view, but only if the search for an 
entity within a part has a cost that's really small (read: constant in 
the size of the part).

I suspect that calls to get*PartNbors are going to typically be 
accompanied by communication with those neighbors and that calls to 
getNumPartBdryEnts are going to typically be accompanied by work 
proportional to the number of bdry entities.  If so, any translation 
overhead is lost in the noise for those functions.

The part data access functions:

getNumOfType, getNumOfTopo (both whole part and set within a part)

The overhead for these funcs may be a noticeable percentage of the 
function cost.   Hard to see these being called enough to contribute 
significantly to overall runtime, though.

Getting and setting tag data on parts.  (get/setEntSet*Data, 
getAllEntSetTags).  The relative cost here depends on how tags are 
stored.  Personally, I'm using hash tables (hashing the handle of the 
thing being tagged), and my hash function is way more expensive than an 
array lookup, so in my implementation, the overhead of the translation 
function will be a small percentage.  Other implementations may vary.

As for various subsetting functions, those should never have a part 
handle passed to them, so they aren't affected.

LOCAL HANDLE PLUS PROCESS RANK

The advantage here is that the same handle space can be used for sets 
and parts (applies to MOAB, probably GRUMMP; not FMDB).

The disadvantage is that now the full name of a part has two pieces 
(handle and rank), which makes it a completely different animal than all 
other handles.

getRankOfPart:   This function would have to be removed.

Functions that will require a rank input arg in addition to part handle:

testPart (which will now require communication), getNumPartBdryEnts, 
getPartBdryEnts, initPartBdryEnt*Iter, getCopyOnPart

Functions that will require a rank or array of ranks to be returned (in 
addition to the current part return data):  (Note that copying the extra 
data also incurs a small cost.)

getNumPartNbors, getPartNbors, getEntOwnerPart, getCopyParts, getCopies, 
getOwnerCopy

All comm functions will now require a rank as well as a part (yes, 
internally the implementation has to do this anyway):

exchEntArrToParts, addGhostOf, rmvGhostOf, exchTags, exchTagsEnt, 
IExchTags, IExchTagsEnt

Functions that are a little dicy (because they are currently defined to 
give errors for remote parts):

isEntOwner, getEntStatus

While adding args to functions isn't necessarily that big a deal, why 
expand the call list if it isn't necessary?


> Part I
> 
> 1. If we are required to embed the proc rank in the handle, then either 
> I cannot use entity sets to represent parts, or I have to embed the proc 
> in all my set handles, which allows at most 2**(32-n)-1 other sets 
> available on any processor, where n is the log of the number of 
> processors; if we need to support millions of processors, n >= 20, 
> leaving me only 4k sets.  Putting that kind of limitation on the number 
> of sets will not be acceptable for some important applications of sets, 
> e.g. geometric topology sets, sets to represent kdtree decomposition of 
> the local mesh (for point location), or OBB tree decomposition of 
> surface triangulations (for ray firing).  Saying we must not implement 
> parts as sets is at least as bad as saying we must implement parts as 
> sets; furthermore, it prevents the dual-use of a given set as a part 
> also (something which I already do, and which is quite useful).

Tim, as I understand the way MOAB manages its handle space (based on 
looking at entity handles), handles are partitioned integers:  the 
high-order bits tell what kind of entity, while the rest tell which of 
those entities it is.  So why not add another prefix specifically for 
parts?  Then you've got an ample space for dealing with globally unique 
part handles, the low order part of which can still be an index into an 
array of sets (now there will be two arrays of sets, a (typically) small 
one for parts and a large one for other sets).  It's no harder to grab 
the memory for a part/set than a regular set, -and- you have an easy way 
to identify erroneous calls to iMesh subsetting functions with part 
handles.  Now, it's possible (even likely) than my understanding of how 
MOAB does things is way off and it isn't nearly as easy as this.  But if 
it is, then your implementation issues for global part handles vanish, 
and we can lay this whole thing to rest without additional debate.

> 2. Deriving the proc from a part handle will still need to be done
> through a function in iMeshP, to avoid forcing applications to do
> bit-wise operations on the handles (e.g. Fortran 77 doesn't have bitwise
> operations).  If we need to do this interpretation in a function anyway, 
> why not also let the implementation decide how to track the part/proc 
> assignment?
> 
> 3. If you allow applications to directly find the proc from the part 
> handle (without going through an iMesh function), then besides 
> specifying embedding the proc in the handle, you'll also
> need to specify exactly how that's done, e.g. which bits hold the rank,
> and whether that number of bits can change depending on the max # procs
> you'd like to support with that mesh.  Are we confident we can get a
> consensus on that?

We've currently got a function for that in the interface.

> 4. If the application is telling Zoltan about the parts, and a part can 
> reside on only one processor, then doesn't that mean that Zoltan finds 
> out where the parts reside at the same time?  If messages are sent 
> containing the part handle, is it so much trouble to add one extra 
> integer denoting the proc where that part resides?  If it's a point to 
> point message, you won't even have to do that, since you know where the 
> message came from (for MPI, anyway).

Yes.  But (IMO) the main advantage to a global handle space for parts is 
in having all handles be congruent and in the iMeshP interface, not in 
how Zoltan massages data.

> Part II
> 
> Also, some comments on the proposed requirements and justification of them:
> 
>   + Part handles are globally unique (so that remote part handles make
> sense and Zoltan doesn't go insane);
> - remote part handles won't exist on a processor unless they were 
> communicated there somehow; in that case the implementation will be able 
> to store the proc # with (not in) the handle if it so chooses

Right.  We're debating whether -passing- the rank through the iMeshP 
interface should be mandatory or forbidden (or at least, that's a 
consequence of the outcome).

> - didn't I hear you say, Karen, that Zoltan computes its own 0..n-1
> numbering of parts anyway?  Or, will you eliminate that if we have
> unique part handles?
> - are we assuming an application will allocate all the part handles
> before calling Zoltan for the partitioning case?  Does it actually have
> to migrate entities to the processor owning a part in order to assign
> those entities to that part?  Or, can a given processor only assign 
> local entities to local parts?  That seems like a pretty severe 
> limitation (and would only allow you to partition for increasing #'s of 
> processors besides)

For repartitionings with the same number of parts, when Zoltan hands 
back a list of part names (of whatever form) for each entity on each 
process, the local process has enough information to then spray data 
around to where it needs to go.

For repartitionings with different numbers of parts, I can easily 
imagine a service that creates parts with no entities (for the case of 
the new partition having more parts), calls Zoltan, redistributes data, 
and deletes parts (for the case of the new partition having fewer parts).

I don't see that either of these cases is materially affected (either in 
how it operates or in efficiency) by how the part name is represented, 
although Zoltan might have to be tweaked to accept a two-piece part name 
--- a longer collection of bits to go into the lookup table.

>    +  Part handles allow identification (without communication or
> O(#parts) storage) of what process the part lives on;
> 
> - so let the implementation decide whether to store the process 
> alongside the part handle.  Even if an implementation decides to do 
> that, that still allows retrieval of the process assignment w/o 
> communication or O(#parts) storage, except in the case where you have 
> O(#parts) handles, in which case you're already storing that amount of 
> information.

That's fine, but we have to either pass that rank through the interface 
or not, which is what we're trying to decide.

> Part III: questions/comments arising from reading current draft:
> 
> _createPartitionPar: do all processors have to assign the same handle to
> the partition?  How does one designate partitions on the remote processor?

I thought we'd agreed that the partition handle isn't necessarily the 
same on all procs, but that since all processes will be running the same 
code, the partition handle will have the same variable name, so it won't 
matter.

> _getNumPartsOnRank, _getPartsOnRank: having unique part handles and proc
> rank embedded in the part handle is insufficient for satisfying these
> functions.  These functions require either O(n) storage or communication
> (or assumptions about how a total # parts is distributed).  I just noted 
> that that was discussed in the bootcamp and email thread.  However, 
> these functions are still in the DraftInterface doc as of 5/27 (with 
> comments later about this issue)

I agree with Tim here:  these funcs require either storage or 
communication.  And do we have a need for them?

Carl

-- 
------------------------------------------------------------------------
Dr. Carl Ollivier-Gooch, P.Eng.                   Voice: +1-604-822-1854
Associate Professor                                 Fax: +1-604-822-2403
Department of Mechanical Engineering             email: cfog at mech.ubc.ca
University of British Columbia              http://www.mech.ubc.ca/~cfog
Vancouver, BC  V6T 1Z4                  http://tetra.mech.ubc.ca/ANSLab/
------------------------------------------------------------------------
-------------- next part --------------
A non-text attachment was scrubbed...
Name: trial.cc
Type: text/x-c++src
Size: 1189 bytes
Desc: not available
URL: <http://lists.mcs.anl.gov/pipermail/itaps-parallel/attachments/20080620/15c85fe0/attachment.cc>


More information about the itaps-parallel mailing list