[Trilinos-Users] Maps having multiple local indices per processor for a single given global index

[Hoemmen, Mark]

On 6/25/15, 2:15 AM, "trilinos-users-request at trilinos.org"
<trilinos-users-request at trilinos.org> wrote:
>Message: 5
>Date: Wed, 24 Jun 2015 17:27:50 -0500
>From: Michael Brothers <brothers.michael.d at gmail.com>
>To: trilinos-users at trilinos.org
>Subject: [Trilinos-Users] Maps having multiple local indices per
>	processor for a single given global index
>Message-ID:
>	<CAKX1btfzDoeq9jPB=q-LmQ7BppRzZhieiLU2eEmVLHUhnEjjjw at mail.gmail.com>
>Content-Type: text/plain; charset="utf-8"
>
>Hello,
>
>in order to allow a sequential memory access pattern while maintaining
>managed importing and exporting I would like to specify maps which contain
>multiple local indices per processor for a single given global index.
>
>In other words I want to be able to do this:
>
>Num processors: 2
>Global indices: 0,1,2,3
>Globals owned by processor one: 0,3,1,1,0,2
>Globals owned by processor two:  2,1,3,3,2,0
>
>Such that the resulting Epetra/Tpetra vectors have duplicated elements,
>even within the same processor.
>
>I am aware this would increase memory use substantially, but this is not
>the most important concern.
>
>Obviously I could just write some code in an attempt to do this, but that
>would not tell me immediately if the code were failing silently.
>
>Is this an official mode of use?

No.  You _could_ create a Map like this; detection adds to Map
construction cost, so we don't do it.  Howver, the interface for
global-to-local index lookup currently assumes that per MPI process, the
mapping from global to local indices is single valued.  Furthermore, this
mapping does not have well-defined behavior in the case of multiple global
indices on a process.  This means that Import and Export will not behave
as you might expect.

In the above example, if "processor 1" asks for the local index
corresponding to global index 1, the Map may return 2 or 3.  For global
index 0, the Map may return 0, 4, or even 3 (if it decides not to count
the duplicate 1 -- it currently does, though).

This undefined behavior means that an Import or Export to a Map like this
will not correctly "broadcast" results that affect a global index, to all
repetitions of that global index on a process.  The Import or Export will
only modify entries of the target object corresponding to the one local
index that the Map gives it for that global index.

Changing Epetra or Tpetra to behave as you expect would require the
following modifications:

  1. "Map" would need to be a "multimap" -- that is, store possibly
multiple local indices per global index on a process.
  2. This would likely add another level of indirect indexing to
applications that work with global indices to fill data structures, as
well as to the pack and unpack kernels for communication.  This will make
Import and Export slower.
  3. We would need to refactor parts of Directory, and carefully test
Zoltan2 (which depends on Tpetra for communication primitives).

So, this would be a whole lot of work.  Furthermore, "we" in the above
list means "I" -- I'm the expert (Turing help us! ;-) ), and I've got
enough work to keep a handful of clones of me busy for years.

People have asked for this feature in the past, but have generally been
able to work around.  For example, you could set up the "multimap"
yourself.  Create a version of your Map without duplicate global indices,
and fill an std::multimap on each process, where each key is a _local_
index in the "non-duplicate" Map, and that key's value(s) is/are the local
indices in your "Map" with duplicates.  First do MPI communication using
Import / Export with data structures from the non-duplicate Map.  Then,
use the std::multimap to "locally broadcast" into your final data
structure.

Please feel free to ask more questions if you like!

mfh