← Back to team overview

yade-mpi team mailing list archive

Re: Method on partitioning

 

Hey Deepak,

Feel free to add it! I should also point out that I just pushed 2 methods
for automatic 3D domain decomposition. One of the methods uses least
squares to minimize the differences between subdomain x,y,z lengths and
[1]. If you ask it for an "odd" number of workers (domains) it splits some
of the domains to make use of remaining workers (you can also manually
control the decomposition so you could just decompose evenly along one
axis, maybe more suitable for "odd" worker requests). The other
decomposition method uses a sparsely generated random point cloud to set an
arbitrary number of randomly shaped subdomains [2].  Feel free to test them
out [3].

Cheers,

Robert

[1]
https://github.com/bchareyre/yade-mpi/commit/dc34c3801d7ef66bab7db5a07c25fc38f7bc5b83#diff-b44541014df947eb2c06425e4ee14771R128
[2]
https://github.com/bchareyre/yade-mpi/commit/dc34c3801d7ef66bab7db5a07c25fc38f7bc5b83#diff-b44541014df947eb2c06425e4ee14771R29
[3]
https://github.com/bchareyre/yade-mpi/blob/master/examples/mpi/testMPI_3D.py

On Tue, Nov 27, 2018 at 8:01 PM Deepak Kn <deepak.kn1990@xxxxxxxxx> wrote:

> Hi,
>
> I found a paper[1] which deals with partitioning for optimal load
> balancing. It uses a recursive binary decomposition --> splitting the
> domain in each axes alternatively.
> (it's similar to a kd-tree space partitioning)
> [1] https://drive.google.com/open?id=16F2jLDSeSEIM2nZBh06eAOSOylugzHys
>
> here's a naive pseudo-code (my understanding of this paper) that can be
> implemented :
> bodylist = []
> for b in O.bodies:
>    blist.append(b.state.pos, b.id)  #list of coords and body id
>
> # single cut -> 2 partitions,
> def split_byids(list_coord, ncut =0): #ncut is used for the splitting
> axis
>   split_axis = ncut%ndim
>    sorted_bodies = sorted(blist, key=split_axis) # need to check lambda
> expr.
>    mid = len(sorted_bodies)//2
>    bodylist_1 = sorted[:mid] #
>    bodylist_2 = sorted[mid+1 :]
>    # recursive split again
>     split_byids(bodylist1, ncut+1);split_byids(bodylist2, ncut+1)
>
>
> #use recursion for (2**(n)) parts.. on bodylist1, and bodylist2
>
> bodyllist1  bodylist2 has ids which can be assigned to subD1, and subD2 ...
> let me know what  you think.
>
> deepak
>
>
>
>
>
>
>
> --
> Mailing list: https://launchpad.net/~yade-mpi
> Post to     : yade-mpi@xxxxxxxxxxxxxxxxxxx
> Unsubscribe : https://launchpad.net/~yade-mpi
> More help   : https://help.launchpad.net/ListHelp
>

Follow ups

References