Show simple item record

dc.contributor.authorNguyen, Vu Thien Nga
dc.contributor.authorKirner, Raimund
dc.date.accessioned2017-07-14T14:40:32Z
dc.date.available2017-07-14T14:40:32Z
dc.date.issued2016-02-12
dc.identifier.citationNguyen , 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 . https://doi.org/10.1109/TPDS.2015.2416726
dc.identifier.issn1045-9219
dc.identifier.otherPURE: 8172917
dc.identifier.otherPURE UUID: be8eb61e-3c24-4109-9bfc-b46ec1646c31
dc.identifier.otherScopus: 84962516755
dc.identifier.urihttp://hdl.handle.net/2299/18951
dc.descriptionThis 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.
dc.description.abstractGraph 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.en
dc.format.extent14
dc.language.isoeng
dc.relation.ispartofIEEE Transactions on Parallel and Distributed Systems
dc.rights/dk/atira/pure/core/openaccesspermission/open
dc.subjectgraph partitioning
dc.subjectheterogeneous systems
dc.subjectdistributed systems
dc.subjectparallel computing
dc.subjectstream processing
dc.subjectComputer Science (miscellaneous)
dc.titleThroughput-driven Partitioning of Stream Programs on Heterogeneous Distributed Systemsen
dc.contributor.institutionSchool of Computer Science
dc.contributor.institutionScience & Technology Research Institute
dc.contributor.institutionCentre for Computer Science and Informatics Research
dc.description.statusPeer reviewed
dc.relation.schoolSchool of Computer Science
dc.description.versiontypeFinal Published version
dcterms.dateAccepted2015-02-14
rioxxterms.versionAM
rioxxterms.versionVoR
rioxxterms.versionofrecordhttps://doi.org/10.1109/TPDS.2015.2416726
rioxxterms.typeJournal Article/Review
herts.preservation.rarelyaccessedtrue
herts.rights.accesstypeopenAccess


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record