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