← Back to team overview

yade-mpi team mailing list archive

Method on partitioning



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
   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.


Follow ups