Communication-Aware Processor Allocation for Supercomputers

Simple item page
dc.creatorBender, Michael A.
dc.creatorBunde, David P.
dc.creatorDemaine, Erik D.
dc.creatorFekete, Sandor P.
dc.creatorLeung, Vitus J.
dc.creatorMeijer, Henk
dc.creatorPhillips, Cynthia A.
dc.date2004-07-24
dc.date2005-12-06
dc.date.accessioned2026-07-07T06:38:04Z
dc.date.available2026-07-07T06:38:04Z
dc.descriptionThis 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.
dc.description19 pages, 7 figures, 1 table, Latex, submitted for journal publication. Previous version is extended abstract (14 pages), appeared in Proceedings WADS, Springer LNCS 3608, pp. 169-181
dc.identifierhttps://arxiv.org/abs/cs/0407058
dc.identifierhttp://arxiv.org/abs/cs/0407058
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/100610
dc.subjectData Structures and Algorithms
dc.subjectDistributed, Parallel, and Cluster Computing
dc.subjectF.2.2; C.1.4
dc.titleCommunication-Aware Processor Allocation for Supercomputers
dc.typetext

Files

Collections

arXiv