Communication - A ware processor allocation for supercomputers

Michael A. Bender; David P. Bunde; Erik D. Demaine; Sándor P. Fekete; Vitus J. Leung; Henk Meijer; Cynthia A. Phillips

doi:10.1007/11534273_16

Communication - A ware processor allocation for supercomputers

Michael A. Bender
, David P. Bunde
, Erik D. Demaine
, Sándor P. Fekete
, Vitus J. Leung
, Henk Meijer
, Cynthia A. Phillips

Computer Science

University of Illinois at Urbana-Champaign
Massachusetts Institute of Technology
Technical University of Braunschweig
Sandia National Laboratories, New Mexico
Queen's University Kingston

Research output: Contribution to journal › Conference article › peer-review

10 Scopus citations

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.

Original language	English
Pages (from-to)	169-181
Number of pages	13
Journal	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	3608
DOIs	https://doi.org/10.1007/11534273_16
State	Published - 2005
Event	9th International Workshop on Algorithms and Data Structures, WADS 2005 - Waterloo, Canada Duration: Aug 15 2005 → Aug 17 2005

Access to Document

10.1007/11534273_16

Cite this

@article{a6eb6f877ea247888cd13a9bacbf71e4,

title = "Communication - A ware processor allocation for supercomputers",

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 L1 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.",

author = "Bender, \{Michael A.\} and Bunde, \{David P.\} and Demaine, \{Erik D.\} and Fekete, \{S{\'a}ndor P.\} and Leung, \{Vitus J.\} and Henk Meijer and Phillips, \{Cynthia A.\}",

year = "2005",

doi = "10.1007/11534273\_16",

language = "English",

volume = "3608",

pages = "169--181",

journal = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

issn = "0302-9743",

note = "9th International Workshop on Algorithms and Data Structures, WADS 2005 ; Conference date: 15-08-2005 Through 17-08-2005",

}

Communication - A ware processor allocation for supercomputers. / Bender, Michael A.; Bunde, David P.; Demaine, Erik D. et al.
In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 3608, 2005, p. 169-181.

Research output: Contribution to journal › Conference article › peer-review

TY - JOUR

T1 - Communication - A ware processor allocation for supercomputers

AU - Bender, Michael A.

AU - Bunde, David P.

AU - Demaine, Erik D.

AU - Fekete, Sándor P.

AU - Leung, Vitus J.

AU - Meijer, Henk

AU - Phillips, Cynthia A.

PY - 2005

Y1 - 2005

N2 - 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 L1 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.

AB - 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 L1 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.

UR - https://www.scopus.com/pages/publications/26844502874

U2 - 10.1007/11534273_16

DO - 10.1007/11534273_16

M3 - Conference article

AN - SCOPUS:26844502874

SN - 0302-9743

VL - 3608

SP - 169

EP - 181

JO - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

JF - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

T2 - 9th International Workshop on Algorithms and Data Structures, WADS 2005

Y2 - 15 August 2005 through 17 August 2005

ER -

Communication - A ware processor allocation for supercomputers

Abstract

Access to Document

Other files and links

Fingerprint

Cite this