Complexity Results and Heuristics for Pipelined Multicast Operations on Heterogeneous Platforms
| hal.structure.identifier | Laboratoire Bordelais de Recherche en Informatique [LaBRI] | |
| hal.structure.identifier | Algorithms and high performance computing for grand challenge applications [SCALAPPLIX] | |
| dc.contributor.author | BEAUMONT, Olivier | |
| hal.structure.identifier | Algorithms and Scheduling for Distributed Heterogeneous Platforms [GRAAL] | |
| dc.contributor.author | LEGRAND, Arnaud | |
| hal.structure.identifier | Algorithms and Scheduling for Distributed Heterogeneous Platforms [GRAAL] | |
| hal.structure.identifier | Laboratoire de l'Informatique du Parallélisme [LIP] | |
| dc.contributor.author | MARCHAL, Loris | |
| hal.structure.identifier | Regularity and massive parallel computing [REMAP] | |
| dc.contributor.author | ROBERT, Yves | |
| dc.date.accessioned | 2024-04-15T09:43:52Z | |
| dc.date.available | 2024-04-15T09:43:52Z | |
| dc.date.issued | 2004 | |
| dc.date.conference | 2004 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/197798 | |
| dc.description.abstractEn | We consider the communications involved by the execution of a complex application deployed on a heterogeneous platform. Such applications extensively use macro-communication schemes, such as multicast operations, where messages are broadcast to a set of predefined targets. We assume that there are a large number of messages to be multicast in pipeline fashion, and we seek to maximize the throughput of the steady-state operation. We target heterogeneous platforms, modeled by a graph where links have different communication speeds. We show that the problem of computing the best throughput for a multicast operation is NP-hard, whereas the best throughput to broadcast a message to every node in a graph can be computed in polynomial time. Thus, we introduce several heuristics to deal with this problem and prove that some of them are approximation algorithms. We perform, simulations to test these heuristics and show that their results are close to a theoretical upper bound on the throughput that we obtain with a linear programming approach. | |
| dc.language.iso | en | |
| dc.publisher | IEEE Computer Society Press | |
| dc.title.en | Complexity Results and Heuristics for Pipelined Multicast Operations on Heterogeneous Platforms | |
| dc.type | Communication dans un congrès | |
| dc.identifier.doi | 10.1109/ICPP.2004.1327931 | |
| dc.subject.hal | Informatique [cs]/Calcul parallèle, distribué et partagé [cs.DC] | |
| bordeaux.page | 267―274 | |
| bordeaux.hal.laboratories | Laboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800 | * |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| bordeaux.conference.title | 2004 International Conference on Parallel Processing (ICPP\'2004) | |
| bordeaux.country | XX | |
| bordeaux.conference.city | Unknown | |
| bordeaux.peerReviewed | oui | |
| hal.identifier | hal-00789448 | |
| hal.version | 1 | |
| hal.invited | non | |
| hal.proceedings | oui | |
| hal.popular | non | |
| hal.audience | Internationale | |
| hal.origin.link | https://hal.archives-ouvertes.fr//hal-00789448v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.date=2004&rft.spage=267%E2%80%95274&rft.epage=267%E2%80%95274&rft.au=BEAUMONT,%20Olivier&LEGRAND,%20Arnaud&MARCHAL,%20Loris&ROBERT,%20Yves&rft.genre=unknown |
Files in this item
| Files | Size | Format | View |
|---|---|---|---|
|
There are no files associated with this item. |
|||