Communication-aware processor allocation for supercomputers: Finding point sets of small average distance

Written with Michael A. Bender, Erik D. Demaine, Sandor P. Fekete, Vitus J. Leung, Henk Meijer, and Cynthia A. Phillips.
Algorithmica 50(2): 279-298, 2008.
Proceedings of the 9th Workshop on Algorithms and Data Structures (WADS), volume 3608 of LNCS, pp. 169-181, 2005.
arXiv:cs.DS/0407058

Download:

Official version
Preprint of journal version: gzipped postscript or pdf
Preprint of conference version: gzipped postscript or pdf
From arXiv: arXiv:cs.DS/0407058

Abstract:

We give processor-allocation algorithms for grid architectures, where the objective is to select processors from a set of available processors to minimize the average number of communication hops.

The associated clustering problem is as follows: Given n points in ℜ^d, find a size-k subset with minimum average pairwise L₁ distance. We present a natural approximation algorithm and show that it is a (7/4)-approximation for 2D grids. In d dimensions, the approximation guarantee is (2-1/2d), which is tight. We also give a polynomial-time approximation scheme (PTAS) for constant dimension d and report on experimental results.

Note: The experimental results in the WADS version contains a typo; the MM/MM entry of Table 1 should be 5288 rather than 5285. Also, the algorithms listed as MC1x1, MM, and MM+Inc were actually improved versions that tries to center a cluster at every processor location rather than just the candidate points specified by the algorithm.