License
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-20818
URL: http://drops.dagstuhl.de/opus/volltexte/2009/2081/
Bisseling, Rob ; van Leeuwen, Tristan ; Catalyurek, Umit V.

Combinatorial Problems in High-Performance Computing: Partitioning

pdf-format:
Dokument 1.pdf (90 KB)

Abstract

This extended abstract presents a survey of combinatorial problems encountered in scientific computations on today's high-performance architectures, with sophisticated memory hierarchies, multiple levels of cache, and multiple processors on chip as well as off-chip. For parallelism, the most important problem is to partition sparse matrices, graph, or hypergraphs into nearly equal-sized parts while trying to reduce inter-processor communication. Common approaches to such problems involve multilevel methods based on coarsening and uncoarsening (hyper)graphs, matching of similar vertices, searching for good separator sets and good splittings, dynamical adjustment of load imbalance, and two-dimensional matrix splitting methods.

BibTeX - Entry

@InProceedings{bisseling_et_al:DSP:2009:2081,
  author =	{Rob Bisseling and Tristan van Leeuwen and Umit V. Catalyurek},
  title =	{Combinatorial Problems in High-Performance Computing: Partitioning},
  booktitle =	{Combinatorial Scientific Computing},
  year =	{2009},
  editor =	{Uwe Naumann and Olaf Schenk and Horst D. Simon and Sivan Toledo},
  number =	{09061},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2009/2081},
  annote =	{Keywords: Partitioning, sparse matrix, hypergraph, parallel, HPC}
}

Keywords: Partitioning, sparse matrix, hypergraph, parallel, HPC
Seminar: 09061 - Combinatorial Scientific Computing
Issue date: 2009
Date of publication: 24.07.2009

DROPS-Home | Fulltext Search | Imprint Published by LZI