Communication-Aware Processor Allocation for Supercomputers
<|reference_start|>Communication-Aware Processor Allocation for Supercomputers: This paper gives processor-allocation algorithms for minimizing the average number of communication hops between the assigned processors for grid architectures, in the presence of occupied cells. The simpler problem of assigning processors on a free grid has been studied by Karp, McKellar, and Wong who show that the solutions have nontrivial structure; they left open the complexity of the problem.   The associated clustering problem is as follows: Given n points in Re^d, find k points that minimize their average pairwise L1 distance. We present a natural approximation algorithm and show that it is a 7/4-approximation for 2D grids. For d-dimensional space, 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.<|reference_end|>
@article{bender2004communication-aware,
    title={Communication-Aware Processor Allocation for Supercomputers},
    author={Michael A. Bender, David P. Bunde, Erik D. Demaine, Sandor P. Fekete,
  Vitus J. Leung, Henk Meijer and Cynthia A. Phillips},
    journal={arXiv preprint arXiv:cs/0407058},
    year={2004},
    archivePrefix={arXiv},
    eprint={cs/0407058},
    primaryClass={cs.DS cs.DC}
}