[Dune] Fwd: Re: Dynamic load balancing with ALUGrid
Bernd Flemisch
bernd at iws.uni-stuttgart.de
Fri Feb 22 13:55:34 CET 2013
Hi Martin,
thank you, I think that I understand it now. And I can
balance the data, assuming that entities keep their local
id, if they are not touched during the gather/scatter of
load balance.
I attach my currently working version of the test that
uses local Ids and is as simple as I hoped for.
Kind regards
Bernd
On Fri, 22 Feb 2013 10:54:19 +0100
Martin Nolte <nolte at mathematik.uni-freiburg.de> wrote:
>
>
>
> -------- 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
>
>
>
> _______________________________________________
> 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
___________________________________________________________
-------------- next part --------------
A non-text attachment was scrubbed...
Name: test-dynamiclb.cc
Type: text/x-c++src
Size: 6015 bytes
Desc: not available
URL: <https://lists.dune-project.org/pipermail/dune/attachments/20130222/65bd1e1d/attachment.cc>
More information about the Dune
mailing list