Throughput-driven Partitioning of Stream Programs on Heterogeneous Distributed Systems

Vu Thien Nga Nguyen, Raimund Kirner

Research output: Contribution to journalArticlepeer-review

5 Citations (Scopus)
133 Downloads (Pure)

Abstract

Graph partitioning is an important problem in computer science and is of NP-hard complexity. In practice it is usually solved using heuristics. In this article we introduce the use of graph partitioning to partition the workload of stream programs to optimise the throughput on heterogeneous distributed platforms. Existing graph partitioning heuristics are not adequate for this problem domain.
In this article we present two new heuristics to capture the problem space of graph partitioning for stream programs to optimise throughput. The first algorithm is an adaptation of the well-known Kernighan-Lin algorithm, called KL-Adapted (KLA), which is relatively slow. As a second algorithm we have developed the Congestion Avoidance (CA) partitioning algorithm, which performs reconfiguration moves optimised to our problem type. We compare both KLA and CA with the generic meta-heuristic Simulated Annealing (SA). All three methods achieve similar throughput results for most cases, but with significant differences in calculation time. For small graphs KLA is faster than SA, but KLA is slower for larger graphs. CA on the other hand is always orders of magnitudes faster than both KLA and SA, even for large graphs. This makes CA potentially useful for re-partitioning of systems during runtime.
Original languageEnglish
Pages (from-to)913-926
Number of pages14
JournalIEEE Transactions on Parallel and Distributed Systems
Volume27
Issue number3
Early online date25 Mar 2015
DOIs
Publication statusPublished - 12 Feb 2016

Keywords

  • graph partitioning
  • heterogeneous systems
  • distributed systems
  • parallel computing
  • stream processing

Fingerprint

Dive into the research topics of 'Throughput-driven Partitioning of Stream Programs on Heterogeneous Distributed Systems'. Together they form a unique fingerprint.

Cite this