<div class="csl-bib-body">
<div class="csl-entry">Träff, J. L. (2019). On Optimal Trees for Irregular Gather and Scatter Collectives. <i>IEEE Transactions on Parallel and Distributed Systems</i>, <i>30</i>(9), 2060–2074. https://doi.org/10.1109/tpds.2019.2899843</div>
</div>
-
dc.identifier.issn
1045-9219
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/142989
-
dc.description.abstract
We study the complexity of finding communication trees with the lowest possible completion time for rooted, irregular gather and scatter collective communication operations in fully connected, $k$k-ported communication networks under a linear-time transmission cost model. Consecutively numbered processors specify data blocks of possibly different sizes to be collected at (gather) or distributed from (scatter) some (given) root processor where they are stored in processor order. We distinguish between ordered and non-ordered communication trees depending on whether segments of blocks are maintained in processor order. We show that lowest completion time, ordered communication trees under one-ported communication can be found in polynomial time by giving simple, but costly dynamic programming algorithms. In contrast, we show that it is an NP-hard problem to construct completion-time optimal, non-ordered communication trees. We have implemented the dynamic programming algorithms for homogeneous networks to evaluate the quality of different types of communication trees, in particular to analyze a recent, distributed, problem-adaptive tree construction algorithm. Model experiments show that this algorithm is close to optimum for a selection of block size and root processor distributions. A concrete implementation for specially structured problems shows that optimal, non-binomial trees can possibly have even further practical advantage.
en
dc.language.iso
en
-
dc.relation.ispartof
IEEE Transactions on Parallel and Distributed Systems
-
dc.subject
Hardware and Architecture
-
dc.subject
Computational Theory and Mathematics
-
dc.subject
Signal Processing
-
dc.title
On Optimal Trees for Irregular Gather and Scatter Collectives
en
dc.type
Artikel
de
dc.type
Article
en
dc.description.startpage
2060
-
dc.description.endpage
2074
-
dc.type.category
Original Research Article
-
tuw.container.volume
30
-
tuw.container.issue
9
-
tuw.journal.peerreviewed
true
-
tuw.peerreviewed
true
-
tuw.researchTopic.id
I2
-
tuw.researchTopic.id
C5
-
tuw.researchTopic.name
Computer Engineering and Software-Intensive Systems
-
tuw.researchTopic.name
Computer Science Foundations
-
tuw.researchTopic.value
90
-
tuw.researchTopic.value
10
-
dcterms.isPartOf.title
IEEE Transactions on Parallel and Distributed Systems