itaps-parallel Part handles

[Tim Tautges]

So I'm confused here - are we or are we not requiring that applications 
be able to derive the rank from the part handle *without making an iMesh 
function call*?

If we are requiring that, a number of issues haven't been address (F77, 
which bits and how many).

If we are not requiring that, and we already have a function for getting 
the rank from a part handle, why are we discussing this at all?  Isn't 
it then an implementation choice?

Or, and I'm guessing this is the real issue, are we saying applications 
should be able to pass part handles around, then pass them back into the 
interface and get information from them?  If so, this sounds pretty 
unique.  It also sounds pretty unlikely, considering parts can't be 
created on remote processes.

- tim

Carl Ollivier-Gooch wrote:
> 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
> 

-- 
================================================================
"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