Hierarchical graph partitioning
MohammadTaghi Hajiaghayi, Theodore J. Johnson, Mohammad Reza Khani, Barna Saha · 2014
One of the important optimization questions in highly parallel systems is the problem of assigning computational resources to communicating tasks. While scheduling tasks/operators, tasks assigned to nearby resources (e.g. on the same CPU core) have low communication costs, whereas tasks assigned to distant resources (e.g. on different server racks) have high communication costs. An optimal solution of task to resource assignment minimizes the communication cost of the task ensemble while satisfying the load balancing requirements. We model such an optimization question of minimizing communication cost as a new class of graph partitioning problems called hierarchical graph partitioning.