Graph cutting algorithms for distributed applications partitioning
Karin Högstedt, Doug Kimelman, V. T. Rajan, Tova Roth, Mark N. Wegman · ACM SIGMETRICS Performance Evaluation Review · 2001
The problem of optimally allocating the components of a distributed program over several machines can be shown to reduce to a multi-terminal graph cutting problem. In case of three of more terminals, this problem has been shown to be NP-hard. This paper introduces a number of heuristic graph algorithms for use in partitioning distributed object applications --- that is, for deciding which objects should be placed on which machines in order to minimize communication and achieve best overall performance of the application. These heuristics are particularly effective for graphs with characteristics specific to representative distributed object applications.