yade-mpi team mailing list archive
-
yade-mpi team
-
Mailing list archive
-
Message #00010
Method on partitioning
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
Follow ups