Feature #1677

improved topology-aware partitioner

Added by Jim Phillips almost 2 years ago. Updated over 1 year ago.

Machine Layers
Target version:
Start date:
Due date:
% Done:



The current topology-aware recursive-bisection partitioner (described in Phillips et al., SC14) was based on an algorithm designed to map the patch grid to the overall torus, and is therefore sub-optimal for partitioning where communication between neighboring partitions is irrelevant. This results in large outlier partitions when there are gaps in the torus, as is increasingly the case on Blue Waters as "communication transparent" jobs may be scattered throughout the allocation.
A better solution may be to use a variant of k-means clustering that guarantees an equal numbers of elements in each cluster (i.e., find k clusters of n elements each that minimize the maximum cluster Manhattan metric diameter). This seems like a good researchy CS topic.


#1 Updated by Sam White almost 2 years ago

  • Target version changed from 6.8.1 to 6.9.0

#2 Updated by Juan Galvez almost 2 years ago

I assume this issue refers to code inside Charm++?

I don't quite understand your description of the issue with the previous code, but the new ST_RecursivePartition code can be used to do recursive partitioning on Blue Waters that "makes sense". It might be what you are looking for.

#3 Updated by Jim Phillips almost 2 years ago

Yes, the code in Charm++ that handles the +partitions (+replicas) setup.

#4 Updated by Phil Miller almost 2 years ago

  • Assignee set to Juan Galvez

Juan, please follow up with more details/discussion, and decide on scheduling this.

#5 Updated by Juan Galvez over 1 year ago

  • Target version changed from 6.9.0 to Unscheduled

Also available in: Atom PDF