[Dune] Fwd: Re: Dynamic load balancing with ALUGrid
Martin Nolte
nolte at mathematik.uni-freiburg.de
Fri Feb 22 10:54:19 CET 2013
-------- Original Message --------
Subject: Re: [Dune] Dynamic load balancing with ALUGrid
Date: Fri, 22 Feb 2013 10:54:06 +0100
From: Martin Nolte <nolte at mathematik.uni-freiburg.de>
To: Bernd Flemisch <bernd at iws.uni-stuttgart.de>
Hi Bernd,
well, your entity will have different local ids on different processes. This
is no problem, because in gather / scatter you have access to the entity and
you will get the correct local id on each process.
Assume that entity e is moved from process p to process q. On process p the
local id of e is 7, while on process q it will be assigned the local id 42.
Let's assume further that the associative container holding our data is simply
called 'data'. Then you will end up with the following accesses of your container:
gather (called on process p): buffer.write( data[ 7 ] );
scatter (called on process q): buffer.read( data[ 42 ] );
So, after load balancing you might want to access the data associated with e
on process q. Hence, you ask for its local id, which will be 42. But then
data[ 42 ] is exactly where we previously stored out data.
From my point of view you never need a global id set, unless you want to
completely bypass the grid in data communication (i.e., you do not even use
grid communication to build up a communication pattern). It is possible that
such code exists somewhere deep in the ISTL AMG solver.
I hope this clarifies your question a little.
Best,
Martin
On 02/22/2013 10:15 AM, Bernd Flemisch wrote:
> Hi Martin,
>
> thank you for your answer. This indeed sounds a lot easier and like the
> solution I originally wanted to achieve. Nevertheless, I am a bit puzzled now.
> I deliberately preferred global over local Ids, since
> "A local id set provides ids that are unique within one process but two
> entities in different processes may have the same id," see
> http://www.dune-project.org/doc/doxygen/dune-grid-html/class_dune_1_1_id_set.html#_details
>
>
> So I thought that with local Ids it could happen that an entity is moved from
> one process to another, where another entity with the same Id already exists.
> And then this would not work out. Or am I missing something?
>
> Kind regards
> Bernd
>
> On 02/22/2013 09:13 AM, Martin Nolte wrote:
>> Hi Bernd,
>>
>> I guess you are the first to use global ids during load balancing and it
>> seems you hit on a bug in ALUGrid (please file a complete bug report on this).
>>
>> Actually, the solution we use is far simpler. Store your data in a std::map
>> using the LocalIdSet (or use a PersistentContainer). This way, your data
>> will always be accessible, even during load balancing. Then you write a data
>> handle (warning: you communicate on the entire hierarchy). That's it.
>>
>> Let me give a bit of explaination: Behind the scenes, ALUGrid will pack data
>> for a macro element to be sent to another process. To this end, it will
>> traverse the tree and pack the element information and your data (calling
>> gather). When all macro elements have been packed, the data is sent to the
>> new processes. Here, they are unpacked, i.e., the element is constructed and
>> all scatter is called. During scatter, the ids will already be valid, so you
>> can use them to access your data container (though the global id might be
>> buggy, as you stated).
>>
>> One final opinion: GlobalIds are an artificial DUNE construct. Implementing
>> them might be quite complicated and expensive. This is the case for ALUGrid,
>> where they are generated in the DUNE bindings. Hence, they have to
>> communicated during load balancing (expensive). So, if you ask ALUGrid for
>> the global id set once, you got to pay this price. There is no way of
>> telling how long this id set is to be used (because it is returned by
>> reference).
>>
>> Best,
>>
>> Martin
>>
>>
>>
>>
>>
>> On 02/22/2013 07:35 AM, Bernd Flemisch wrote:
>>> Hi,
>>>
>>> sorry for the noise again, but I found a working solution. So if you already
>>> started to brood over the problem, you may relax.
>>>
>>> I assume that the Ids are still valid during gather and will become valid
>>> again and with the same values after load balance. I simply gather the Ids
>>> together with the data and scatter both of them. In a postprocess after load
>>> balance, I use this (now valid) information to write the values into the
>>> corresponding vector.
>>>
>>> This works for several grids and numbers of processes, so I hope for all of
>>> them. I attach the file.
>>>
>>> If you think this is important enough to become a test in dune/grid/test and
>>> feel responsible for evaluating and committing it, I am happy to provide a
>>> patch and to improve it together with you.
>>>
>>> Thanks to Andreas and Martin for the hints which helped to achieve this. Kind
>>> regards
>>> Bernd
>>>
>>> On Thu, 21 Feb 2013 19:12:44 +0100
>>> Bernd Flemisch <bernd at iws.uni-stuttgart.de> wrote:
>>>> Actually, the Ids are the same again after the load balancing step is over.
>>>> But apparently not during scatter, where I would need it. Hmmm...
>>>>
>>>> On Thu, 21 Feb 2013 17:55:51 +0100
>>>> Bernd Flemisch <bernd at iws.uni-stuttgart.de> wrote:
>>>>> Hi,
>>>>>
>>>>> only a few months have passed and I found the time to look at this again. I
>>>>> tried to follow Andreas' suggestion and work with Ids rather than indices,
>>>>> since they should be persistent. I was hoping that "persistent" means that,
>>>>> if an element is moved from one process to another, it keeps its global Id.
>>>>> Looking at
>>>>> http://www.dune-project.org/doc/doxygen/dune-grid-html/class_dune_1_1_id_set.html#_details
>>>>>
>>>>>
>>>>> does not necessarily say that (I think).
>>>>>
>>>>> I set up a test for my efforts, see the attached file. The coarse grid is
>>>>> 5x1x1. The two left elements are interior on process 1, the three right
>>>>> ones interior on process 2. The two left elements get refined. After
>>>>> adaption, loadBalance with my DataHandle is called. The three right
>>>>> elements are all moved to process 1, so that after the balancing step,
>>>>> process 1 holds all elements, while process 0 has none.
>>>>>
>>>>> During load balance, I print the cell centers, global Ids, and
>>>>> gathered/scattered values on each process. This gives the following:
>>>>> Process 0:
>>>>> 0: 0.5 0.5 0.5, ([2,3,8,14],8,0): gather 0
>>>>> 0: 0.7 0.5 0.5, ([3,4,9,15],8,0): gather 1
>>>>> 0: 0.9 0.5 0.5, ([4,5,10,16],8,0): gather 2
>>>>> Process 1:
>>>>> 1: 0.5 0.5 0.5, ([2,3,8,14],71,0): scatter 0
>>>>> 1: 0.7 0.5 0.5, ([2,3,8,14],70,0): scatter 1
>>>>> 1: 0.9 0.5 0.5, ([2,3,8,14],69,0): scatter 2
>>>>> It seems to be correct that information from three elements is sent from
>>>>> process 0 and received for the corresponding elements by process 1.
>>>>> However, the global Ids are changed. Is this correct? Then how tf can I
>>>>> find out which elements correspond to each other? Or am I still doing
>>>>> something wrong?
>>>>>
>>>>> Thank you for having another look. Kind regards
>>>>> Bernd
>>>>>
>>>>> On Sat, 27 Oct 2012 07:43:48 +0000
>>>>> "Dedner, Andreas" <A.S.Dedner at warwick.ac.uk> wrote:
>>>>>> Is it not even so that one can not use an undexset at all? Load balancing
>>>>>> changes the grid so the indexsets are not valid. You need to use id
>>>>>> containers.
>>>>>> Andreas
>>>>>>
>>>>>> Martin Nolte <nolte at mathematik.uni-freiburg.de> wrote:
>>>>>> Hi Bernd,
>>>>>>
>>>>>> I have an educated guess for you (don't blame me, if I'm wrong):
>>>>>>
>>>>>> In normal communication, you only communicate data on a certain grid view.
>>>>>> Hence
>>>>>> you can use the index set to address data stored on that grid view.
>>>>>>
>>>>>> When doing load balancing, you rather communicate data on the entire
>>>>>> hierarchy.
>>>>>> Therefore, your entity might not be contained an index set (leading to this
>>>>>> cryptic assertion). So, if you want to communicate data only on a certain
>>>>>> grid
>>>>>> view, you have to add a call to indexSet.contains to the gather / scatter
>>>>>> / size
>>>>>> methods. Usually, fixedSize will be false in such situations (I think
>>>>>> ALUGrid
>>>>>> ignores this anyway, so it should not matter, here).
>>>>>>
>>>>>> Just a side note: In my opionion, a normal communicate method exchanging
>>>>>> data on
>>>>>> the entire hierarchy would be nice, too. But alas, this method would
>>>>>> naturally
>>>>>> be "grid().communicate( dataHandle, interface, direction )".
>>>>>>
>>>>>> Best,
>>>>>>
>>>>>> Martin
>>>>>>
>>>>>> On 10/26/2012 01:32 PM, Bernd Flemisch wrote:
>>>>>>> Hey Andreas,
>>>>>>>
>>>>>>> thank you for your fast answer. This indeed solves my second issue.
>>>>>>> However, the
>>>>>>> first one remains. I attach an updated test file.
>>>>>>>
>>>>>>> Kind regards
>>>>>>> Bernd
>>>>>>>
>>>>>>> On 10/26/2012 01:08 PM, Dedner, Andreas wrote:
>>>>>>>> Hi Bernd
>>>>>>>>
>>>>>>>> You should be able to cast the derived class onto the interface class
>>>>>>>> and that triggers the call to the correct method.
>>>>>>>>
>>>>>>>> Andreas
>>>>>>>>
>>>>>>>> ________________________________________
>>>>>>>> From: dune-bounces+a.s.dedner=warwick.ac.uk at dune-project.org
>>>>>>>> [dune-bounces+a.s.dedner=warwick.ac.uk at dune-project.org] on behalf of
>>>>>>>> Bernd
>>>>>>>> Flemisch [bernd at iws.uni-stuttgart.de]
>>>>>>>> Sent: 26 October 2012 11:53
>>>>>>>> To: Dune
>>>>>>>> Subject: [Dune] Dynamic load balancing with ALUGrid
>>>>>>>>
>>>>>>>> Dear Dune,
>>>>>>>>
>>>>>>>> I try to use dynamic load balancing with ALUGrid. The grid itself gets
>>>>>>>> balanced nicely, but I don't succeed in getting data balanced.
>>>>>>>>
>>>>>>>> From dune/grid/alugrid/3d/grid.hh lines 701ff, I guess that I can pack
>>>>>>>> a "usual" data handle which is used for communication into a
>>>>>>>> ALUGridLoadBalanceDataHandle and call loadBalance with that handle. My
>>>>>>>> initial attempt to do this fails with
>>>>>>>> test-dynamiclb:
>>>>>>>> ../../../dune/grid/alugrid/common/defaultindexsets.hh:218:
>>>>>>>> Dune::DefaultIndexSet<GridImp, IteratorImp>::IndexType
>>>>>>>> Dune::DefaultIndexSet<GridImp, IteratorImp>::index(const typename
>>>>>>>> GridImp::Codim<cd>::Entity&) const [with int cd = 0; GridImp =
>>>>>>>> Dune::ALU3dGrid<(Dune::ALU3dGridElementType)7u>; IteratorImp =
>>>>>>>> Dune::EntityIterator<0, const
>>>>>>>> Dune::ALU3dGrid<(Dune::ALU3dGridElementType)7u>,
>>>>>>>> Dune::ALU3dGridLeafIterator<0, (Dune::PartitionIteratorType)4u, const
>>>>>>>> Dune::ALU3dGrid<(Dune::ALU3dGridElementType)7u> > >;
>>>>>>>> Dune::DefaultIndexSet<GridImp, IteratorImp>::IndexType = unsigned int;
>>>>>>>> typename GridImp::Codim<cd>::Entity = Dune::Entity<0, 3, const
>>>>>>>> Dune::ALU3dGrid<(Dune::ALU3dGridElementType)7u>,
>>>>>>>> Dune::ALU3dGridEntity>]: Assertion `indexContainer( cd )[ en ].index()
>>>>>>>> >= 0' failed.
>>>>>>>>
>>>>>>>> I attach my effort, where I use a data handle copied from the
>>>>>>>> grid-howto. It would be great if you could take a look.
>>>>>>>>
>>>>>>>> I have a second issue: I guess that I should be able to call loadBalance
>>>>>>>> directly with a usual data handle, so that grid.hh lines 701ff takes
>>>>>>>> care of it and packs it for me into a ALUGridLoadBalanceDataHandle
>>>>>>>> before sending it to the real loadBalance method. However, since my data
>>>>>>>> handle is only inherited from CommDataHandleIF, the packing routine is
>>>>>>>> not triggered but the real loadBalance method is called directly leading
>>>>>>>> to a compilation error. How can I trigger the execution of the packing
>>>>>>>> routine for such a derived data handle?
>>>>>>>>
>>>>>>>> Thank you for having a look. Kind regards
>>>>>>>> Bernd
>>>>>>>>
>>>>>>>> --
>>>>>>>> _____________________________________________________________________
>>>>>>>>
>>>>>>>> Bernd Flemisch phone: +49 711 685 69162
>>>>>>>> IWS, Universität Stuttgart fax: +49 711 685 60430
>>>>>>>> Pfaffenwaldring 61 email: bernd at iws.uni-stuttgart.de
>>>>>>>> D-70569 Stuttgart url:
>>>>>>>> www.hydrosys.uni-stuttgart.de<http://www.hydrosys.uni-stuttgart.de>
>>>>>>>> _____________________________________________________________________
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> _______________________________________________
>>>>>>> Dune mailing list
>>>>>>> Dune at dune-project.org
>>>>>>> http://lists.dune-project.org/mailman/listinfo/dune
>>>>>>
>>>>>> --
>>>>>> Dr. Martin Nolte <nolte at mathematik.uni-freiburg.de>
>>>>>>
>>>>>> Universität Freiburg phone: +49-761-203-5630
>>>>>> Abteilung für angewandte Mathematik fax: +49-761-203-5632
>>>>>> Hermann-Herder-Straße 10
>>>>>> 79104 Freiburg, Germany
>>>>>>
>>>>>> _______________________________________________
>>>>>> Dune mailing list
>>>>>> Dune at dune-project.org
>>>>>> http://lists.dune-project.org/mailman/listinfo/dune
>>>>>>
>>>>>
>>>>> ___________________________________________________________
>>>>>
>>>>> Bernd Flemisch phone: +49 711 685 69162
>>>>> IWS, Universitaet Stuttgart fax: +49 711 685 67020
>>>>> Pfaffenwaldring 61 email: bernd at iws.uni-stuttgart.de
>>>>> D-70569 Stuttgart url: www.hydrosys.uni-stuttgart.de
>>>>> ___________________________________________________________
>>>>
>>>> ___________________________________________________________
>>>>
>>>> Bernd Flemisch phone: +49 711 685 69162
>>>> IWS, Universitaet Stuttgart fax: +49 711 685 67020
>>>> Pfaffenwaldring 61 email: bernd at iws.uni-stuttgart.de
>>>> D-70569 Stuttgart url: www.hydrosys.uni-stuttgart.de
>>>> ___________________________________________________________
>>>>
>>>> _______________________________________________
>>>> Dune mailing list
>>>> Dune at dune-project.org
>>>> http://lists.dune-project.org/mailman/listinfo/dune
>>>
>>> ___________________________________________________________
>>>
>>> Bernd Flemisch phone: +49 711 685 69162
>>> IWS, Universitaet Stuttgart fax: +49 711 685 67020
>>> Pfaffenwaldring 61 email: bernd at iws.uni-stuttgart.de
>>> D-70569 Stuttgart url: www.hydrosys.uni-stuttgart.de
>>> ___________________________________________________________
>>>
>>>
>>> _______________________________________________
>>> Dune mailing list
>>> Dune at dune-project.org
>>> http://lists.dune-project.org/mailman/listinfo/dune
>>>
>>
>
>
--
Dr. Martin Nolte <nolte at mathematik.uni-freiburg.de>
Universität Freiburg phone: +49-761-203-5630
Abteilung für angewandte Mathematik fax: +49-761-203-5632
Hermann-Herder-Straße 10
79104 Freiburg, Germany
More information about the Dune
mailing list