Throughput-driven Partitioning of Stream Programs on Heterogeneous Distributed Systems
Nguyen, Vu Thien Nga; Kirner, Raimund
Citation: Nguyen , V T N & Kirner , R 2016 , ' Throughput-driven Partitioning of Stream Programs on Heterogeneous Distributed Systems ' IEEE Transactions on Parallel and Distributed Systems , vol 27 , no. 3 , pp. 913-926 . DOI: 10.1109/TPDS.2015.2416726
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.
This is an Open Access article. © 2015 IEEE. Translations and content mining are permitted for academic research only. Personal use is also permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.
This item appears in the following Collection(s)
Your requested file is now available for download. You may start your download by selecting the following link: test