------------------------------------------------ Background and Terminology: Terminology -- CYA: - In this document, the term "set" is used generically to describe a collection of entities; it does not necessarily imply an implementation via EntitySets. The term "EntitySet" will be used where EntitySets are actually required. Terminology -- Abstract Data Model: - The term "mesh" refers to an abstraction in the data model; it does not imply a serial or parallel distribution. - The term "partition" refers to an assignment of a set of entities to subsets; like a "mesh," it does not imply a serial or parallel implementation. - An application may use one or more meshes. - Parititions can create subsets of entities from one or more meshes. - Meshes can be subdivided by one or more partitions. - Partitions contain parts. Parts contain the subsets of entities in the partition. Terminology -- Parallelism - A "process" can be thought of as an MPI process. The number of processes can be considered to be the result of MPI_Comm_size. The rank of a process can be thought of as the result of MPI_Comm_rank. We will think in terms of processes rather than processors. Initial implementations of the parallel interface will likely use MPI terminology directly; future implementations may accommodate other communication paradigms and libraries. - Partitions have communicators associated with them. These communicators can be thought of as MPI communicators. - "Global" operations are operations performed with respect to a partition's communicator. - "Local" operations are operations performed with respect to a part. Terminology -- Interfaces - Each process has one or more "mesh instances." A mesh instance can be thought of as a mesh database. An implementation should support the existence of more than one mesh instance per process (e.g., it should always associate mesh data with a mesh instance). However, we expect applications would most often use only one mesh instance per process. - There is one root set per mesh instance. - Each process may have one or more partition instances. - A partition instance partitions entities in one mesh instance. Partition instances know which mesh instance's entities they partition. - Entities in a mesh instance can be partitioned by one or more partitions. Mesh instances know which partition instances they are in. - Parts can be accessed by either part IDs (integers) or part handles. Assumptions that aren't currently causing heartburn: - Each part is wholly contained within a process. - A process may have multiple parts. - Many iMesh functions that accept a mesh instance and an EntitySet handle are also useful in the context of partition instances and part handles. These functions will be reinterpreted so that they can accept either a mesh instance and EntitySet handle, or a partition instance and a part handle. See Carl's Oct 15 email for more detail. - Entities in partitions can have unique global IDs. Uniqueness of global IDs is managed at the partition level. - For **each item** of functionality in this document, there will be a function (or set of functions) to provide the functionality. The implementation can decide whether these functions should be simple wrappers over existing data model functionality or more intrusive functions in the implementation. ------------------------------------------------ Partition Functionality: - Create a partition instance: Given a mesh instance to be included in the partition and a communicator, return a partition instance. - Destroy a partition instance: Given a partition instance, destroy it and set its handle to NULL. - Given a partition instance, return its communicator. - Given a partition instance, return the mesh instance that is included in the partition. - Given a partition instance, return the total global number of parts in the partition. - Map from parts to processes: + Given a partition instance and a part ID, return the rank of the process that owns the part. Need single-part-ID and array-of-part-IDs versions of this function. - Map from processes to parts: + Given a partition instance and an process rank, return the number of parts owned by the process. + Given a partition instance and a process rank, return the part IDs owned by the process. Need single-process and array-of-processes versions of this function. - Map from the process rank to part handles. + Given a partition instance, return the number of on-process parts in the partition. + Given a partition instance, return all on-process part handles in the partition. - Provide global mesh information about a partition. Given a partition instance, return: + Total number of entities in the partition. + Total number of entity sets in the partition. + Total number of entities with given type or topology in the partition. Note: these operations require communication. Note: these operations are analogous to the global operations on EntitySets defined below. Indeed, perhaps these operations should not be in this section. See EntitySet functionality below. - Manage global IDs of entities that are partitioned. + set/retrieve global IDs; generate global IDs; set/retrieve global ID size; map between entities and global IDs; compare global IDs. Since there was little disagreement with Vitus'/Karen's document on global IDs, we will use it in the first draft with modifications to associate the "global" nature of the IDs with partitions; these changes address some of Tim's concerns. We will keep the helper functions defined, rather than require the application to manage them with special tags. ------------------------------------------------ Part Functionality: - Given a partition instance, create a part and add it to the partition on the process invoking the creation. Return part handle. - Given a partition instance and a part handle, remove the part from the partition, destroy the part, and set the part handle to NULL. - Map between part handles and part IDs. + Given a partition instance and a part handle, return the part ID. + Given a partition instance and a part ID, return the part handle if on process; return error code otherwise. Need single-part and array-of-parts versions of these functions. - Identify parts that neighbor a given part. + Given a partition instance and a part handle, return the number of parts in the partition that neighbor the given part. + Given a partition instance and a part handle, return the part IDs of all parts in the partition that neighbor the given part. Need single-part and array-of-parts versions of these functions. - Provide part boundary info: + Given a partition instance, a part handle, and a neighboring part ID, return the number of boundary entities on the part boundary shared with the neighboring part ID. + Given a partition instance, a part handle, and a neighboring part ID, return an array of entity handles for all entities along the part boundary shared with the neighboring part ID. + Boundary iterators: Given a partition instance, a part handle, and a neighboring part ID, return an iterator over all entities along the part boundary shared with the neighboring part ID. Note: Allow optional specification of desired entity types and topologies; allow neighboring part ID = -1 to count/include all qualifying boundary entities of part. - Provide entity information about a part; e.g., given a partition instance and a part handle, return the number of entities in the part, lists of entities in the part, etc. This functionality is largely accomplished by substituting the partition handle for the mesh handle and the part handle for the entity set handle in existing iMesh functions. - Provide part information about an entity: Given an entity and a partition instance, return the part ID of the part that owns the entity. Must return an error code if the entity is not in the partition (e.g., if the partition assigns surfaces to parts, it doesn't make sense to ask which part owns a given region). Need single-entity and array-of-entities versions of this function. - Add/remove on-process entities to/from on-process part: Given a partition instance, an entity handle, and a part handle, add/remove the entity to/from the part. This operation can be accomplished by functions that add/remove entities to/from EntitySets. - Add entities to on-process and/or off-process parts: This functionality could be implemented through a send/receive message pair: Input is a partition instance, a source part handle, an entity handle, a target part ID, and a command code (e.g., MIGRATE/COPY); e.g., + sendEntArrToParts(partition, source_part_handle, ent_handle_array, target_part_ID_array, MIGRATE) moves an entity to a new part; and sendEntArrToParts(source_part_handle, ent_handle_array, target_part_ID_array, COPY) copies an entity in a new part. + receiveEntArr: a receive that blocks until all expected data is received; also can update ghost/boundary/internal data as needed. Note: Some set-up communication may be needed for the receive to determine what messages it is waiting for. Note: Using a pair of calls allows at least some latency hiding. ------------------------------------------------ Mesh Instance Functionality: - Given a mesh instance, return all partition instances that include the mesh. ------------------------------------------------ EntitySet Functionality: - Note: If multiple meshes are stored in a single mesh instance as separate EntitySets, we need functions to get information about an individual mesh. - Return global information about an EntitySet. Given a partition instance and an EntitySet handle, return: + Total number of entities in the EntitySet. + Total number of entity sets in the EntitySet. + Total number of entities with given type or topology in the EntitySet. Note: these operations all require communication. Note: these functions are analogous to the global partition operations above. Indeed, we could have only these global functions, providing the root set as the EntitySet to match the global partition operations above. - Also, need functions that return information like, "Given a partition instance, a part handle, and an EntitySet handles, how many entities are there in this EntitySet in this part?" Adding this functionality might argue against our previous decision to overload the EntitySet functions to use part handles. ------------------------------------------------ Entity Functionality: - Provide entity categorization within part (boundary, copy, owned, etc.): + Given a partition instance, a part handle, and an entity handle, return a flag indicating whether the entity is owned by the part or is a copy. + Given a partition instance, a part handle, and an entity handle, return a flag indicating whether the entity is strictly internal, on a boundary, or a ghost. Need single-entity and array-of-entities versions of these functions. - Provide information about copies of entities. + Given a partition instance and an entity handle, return the number of copies of the entity on processes in the partition's communicator. + Given a partition instance, an entity handle and a part ID, return the (remote) entity handle of the entity in the specified part. Return an error if the entity does not exist in the specified part. + Given a partition instance and an entity handle, return (remote) entity handles and part IDs of all copies of the entity. + Given a partition instance and an entity handle, return the (remote) entity handle and part ID from the owner of the entity (e.g., the entity handle of the copy that has right-to-modify). All these functions should work on the local process as well as remote processes; entity handles returned are likely but not necessarily remote. For example, for a valid entity handle, the first function above should return an integer >= 1, and the third function should return at least the owned entity handle. ------------------------------------------------ Comments and resolved questions: - Applications will build partitions by (1) creating a partition instance on each process to be included in the partition; (2) adding parts to the partition instance within the process; and (3) populating the parts with entities. - All parts will have global (across the partition's communicator) part IDs, but will not have local (to a process) part IDs. Part handles will serve as local IDs. - For now, we will not include an iterator over local (to a process) parts within a partition. If it is needed, it can be added later. - Functions returning global information (such as the total number of parts in a partition) would have the option of using communication to return their answer and, thus, would have to be called synchronously by users. We agreed that implementations did not necessarily have to use communication, but the documentation would warn users that communication might occur. - We will not provide capability to move entire parts to new processes; instead, the new process must create the part in its partition instance and then receive (perhaps in bulk) the entities to populate the part. In other words, parts can be added to only a local partition instance. - Currently, iMesh doesn't have the functionality to get entities or entity sets by type and tag in serial. Should it? Many people said it would be useful; others said it could be costly (in parallel) or numerically difficult (for floating point values). This issue is an iMesh issue, not a parallel interface issue, so for this document, the issue is resolved. The resolution: If iMesh adopts this capability, we will consider adding it to the parallel interface. Removed the following global queries; are there analogous serial iMesh functions? + Total number of entity sets with given type, tag and/or tag name in the partition; + Total entities with given type, tag and/or tag name in the partition; - We will not include functions that return all entities with given characteristics within a partition; the memory use of these functions can be large. Instead, we will return entity information with respect to parts and/or mesh instances. If the user wants such info, he should go through the mechanics of gathering it himself so that he is painfully aware of how much memory he is allocating. Removed the following global queries: + All tag names over the partition; + All entities in this partition having a given type, tag and/or tag name. + All entity sets in this partition having a given type, tag and/or tag name. - We will not include functions that return information about each part and/or process in a partition. Such functions limit memory scalability for large numbers of parts. If the user wants such info, he should go through the mechanics of gathering it himself so that he is painfully aware of how much memory he is allocating. Removed the following global queries: + The number of entities in each part of the partition; + The number of entity sets in each part of the partition; + The number of entities with given type, tag, and/or tag name in each part of the partition; + The number of entity sets with given type, tag, and/or tag name in each part of the partition; + All tag names in each part of the partition; - For functions that replace a set handle with a part handle, return all appropriate entities in a part, whether they are owned or are copies. The application can test for ownership if needed. ------------------------------------------------ Discussed but unresolved questions: - We discussed but did not yet accept the possibility of adding a partition-syncing function that would compute and store global info about a partition after modifications of a partition were completed. We discussed allowing this function to compute and store some scalar values (e.g., total number of parts in a partition), but ruled out allowing it to compute and store vector data of size O(number of processors) (e.g., the number of parts on each processor). - Do we need a mechanism to store a mapping of parts to processes in files? This capability could be used in static partitioning to compute on, say, 10 processes a partition with 10K parts that will be used on 5K processes. - We discussed and deferred a decision on adding functions that give hints to an implementation about which data mappings the application will use, allowing the implementation to pre-compute them if it chooses to. The example discussed was mapping between entities and parts, but other examples in iMesh may also exist. - We discussed and deferred a decision on adding an iterator over entities with given type/topology in a set or part. We have non-iterator functionality, but not an iterator. - We discussed and deferred a decision on storing in a partition information about which "objects" were used in computing the partition. These objects can be single entities or groups of entities. - We discussed and deferred a decision on whether part assignments apply only to the entities involved in generating a partition, or whether they induce part assignments on lower-dimensional entities. - We discussed and deferred a decision on designating a given partition as the "active" partition; i.e., the partition that is actually used in the distribution of mesh data in distributed memory. We were concerned that when multiple partitions were used, multiple copies of mesh entities would be needed to fully support multiple partitions at the same time. Designating one partition as "active" would store data with respect to only one partition. ------------------------------------------------ Not-yet-discussed, unresolved questions Part Questions: - Need a precise definition of "neighbor" for returning neighbor part info. EntitySet Questions: - The EntitySet functionality is entirely new. Look it over carefully! - In our mesh instance discussions, I was told that multiple meshes would be loaded into one mesh instance using separate EntitySets. If so, we need functionality that returns mesh data with respect to a given partition, part, and EntitySet. For example, say we want the number of elements in mesh A assigned to part 3. We would need to ask: "Given a partition instance, the part handle for part 3, and the EntitySet handle that mesh A was loaded into, how many entities of type REGION are there in this EntitySet in this part?" Our plan to overload EntitySet functions to accept part handles is insufficient to handle this type of query. - If we define such functions, should we abandon our idea to overload the EntitySet functions and, instead, use these new functions with the root set to gain similar capability? - The global EntitySet functions above are analogous to the global partition functions. The global EntitySet functions return data for a particular EntitySet within a partition; the global partition functions return data for the root set of the mesh instance in a partition. Do we need/want both? Or should we have only the more general case? Entity questions: - From Carl: "getTag*Operate: Again, we haven't got this in serial. Does the existence of such operations imply that we expect to implement fields as tags? (Because that wasn't what I was assuming about field implementations at all, personally...) Note that I'm not opposed to this sort of global reduction operation, I just wonder whether it'll see use outside of field-like situations. If not, then it should be in parallel fields, not parallel mesh, and usage for fields-implemented-as-tags should be handled there." ------------------------------------------------ % CVS File Information % $RCSfile: CombinedModelByKaren.txt,v $ % $Author: kddevin $ % $Date: 2007/12/03 21:51:14 $ % $Revision: 1.14 $