Internals of IndexSet

[fredrikekre]

I am wondering what the different mappings in IndexSet represent as it is not immediatly obvious to me what those acronyms are:

PartitionedArrays.jl/src/IndexSets.jl

Lines 215 to 223 in d5224f7

	struct IndexSet <: AbstractIndexSet
	part::Int
	lid_to_gid::Vector{Int}
	lid_to_part::Vector{Int32}
	oid_to_lid::Vector{Int32}
	hid_to_lid::Vector{Int32}
	lid_to_ohid::Vector{Int32}
	gid_to_lid::Dict{Int,Int32}
	end

If I could get this clarified I will add some docs and/or comments in the code to clarify. Thanks!

[amartinhuertas]

Hi @fredrikekre,

IndexSet describes the (potentially overlapping) data distribution layout of a global set of indices in each of the parts on which this set is partitioned (note there are as many IndexSet instances as parts, one per part). The part member variable represents the part corresponding to the IndexSet. These indices can be used to label entities of distributed global data structures such as cells, degrees of freedom, etc.

A given part only stores a portion of the global indices. In order to locally address the entities on the local part, these are assigned a local index. lid_to_gid stores the mapping among local and global indices. Note that the eltype of lid_to_gid is 64-bit integer, as we want to be able to address a very large number of global entities. On the other hand, gid_to_lid stores the inverse mapping. For memory efficiency reasons, gid_to_lid is a dictionary, as a part only stores a portion of the global set of entities.

Each of the global entities is assigned a part owner among the parts on which it is present (recall from above that the partition may be overlapping, thus a given entity might be present in more than one part). lid_to_part stores the part owned by each local entity present on the part.

Using the concept of part owner, we can classify the set of local entities into owned entities by the part (denoted with o), and ghost (i.e., non-owned) entitites (denoted with h). Ghost entities are those entities which are present on the local part, but are actually owned by a remote processor.

Each of the owned entities are labelled with a local index within the set of all owned entities, and the same applies for ghost entities. oid_to_lid and hid_to_lid are used to encode, resp., the mapping among these owned/ghost local indices, and the local indices of the entities in the part. lid_to_ohid stores the inverse mapping.

Finally, note that there is an optimized implementation of AbstractIndexSet, named IndexRange, that is tailored to those situations in which:

• Each part gets a set of owned entities with consecutive global indices. E.g., part 1 owns global entities 1:50, and part 2 51:100 of the global index set 1:100.
• The local indexing is such that owned entities are first locally labeled, followed by the ghost entities.

Some distribution linear algebra libraries, such as PETSc, rely on this kind of partitions.

Does all this make sense?

[termi-official]

Thanks for the detailed elaboration. I try to propose a PR to put this into the docs if I can find some time soon. However, I am still a bit confused about the role of ExtendedIndexRange. Do you by any chance know what its function is?

[fredrikekre]

Thanks, then my understanding after experimenting a bit was roughly correct. I will try to add some documentation or comments in the code to make it easier for others. The most confusing things was "gid", which, if I understand correctly sometimes means "global id" and sometimes "ghost id".

[amartinhuertas]

I will try to add some documentation or comments in the code to make it easier for others.

That would be very helpful. Thanks!

The most confusing things was "gid", which, if I understand correctly sometimes means "global id" and sometimes "ghost id".

"gid" should always mean "global id". Where does it mean "ghost id" ?

[fverdugo]

Global ids are "gids" and ghost ids are "hids". Local ids are "lids". We try to stick to this convention in all the package. If you find a notation mistake let us know!

[fredrikekre]

Ah okay, I thought that add_gids! (#60 (comment)) added the ghost IDs, but that is global IDs then? It does add both it looks like though, but perhaps the addition of global IDs is the main point of that function?

[fverdugo]

In add_gids! each part receives a vector of global ids, if a given global id is not owned in this part is appended as a new ghost id.

I see your concern. Perhaps the function could be called add_hids! but the input are always global ids (that's why I called add_gids!).

[fredrikekre]

Yea okay, that makes sense, then I think the name is okay, but I will include that description in the docstring for clarity.

[fredrikekre]

Although, the only modifications are the ghost id's, so there is not really any adding of global IDs

julia> using PartitionedArrays

julia> parts = get_part_ids(sequential, 2);

julia> I = map_parts(parts) do p
           if p == 1
               return [1, 2, 1, 2]
           else p == 2
               return [3, 4, 3, 4]
           end
       end;

julia> rows = PRange(parts, 4);

julia> add_gids!(rows, I)

is a no-op, for example (except the rows.ghost field changing from false to true). I guess this is why I was confused.