Efficient Algorithms for Temporal Balanced Graph Partitioning of Datacenter Workloads

The popularity of distributed machine learning applications and hardware training imposes increasingly stringent performance requirements on the interconnecting communication network. A clever scheduling of the computational workload has the potential to greatly improve datacenter resource utilization, by keeping frequently communicating nodes topologically close. A fundamental underlying optimization problem is known as (static) balanced graph partitioning: How to partition a graph (describing a workload) into equally-sized subgraphs (“clusters”) to minimize the number of inter-cluster edges?