Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH scholarly article en Bisseling, Rob; van Leeuwen, Tristan; Catalyurek, Umit V. License: Creative Commons Attribution 4.0 license (CC BY 4.0)
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-20818

; ;

Combinatorial Problems in High-Performance Computing: Partitioning



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

  author =	{Bisseling, Rob and van Leeuwen, Tristan and Catalyurek, Umit V.},
  title =	{{Combinatorial Problems in High-Performance Computing: Partitioning}},
  booktitle =	{Combinatorial Scientific Computing},
  pages =	{1--5},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9061},
  editor =	{Uwe Naumann and Olaf Schenk and Horst D. Simon and Sivan Toledo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-20818},
  doi =		{10.4230/DagSemProc.09061.6},
  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 | Privacy Published by LZI