Fast Approximation Algorithms for Task-Based Runtime Systems
| hal.structure.identifier | Reformulations based algorithms for Combinatorial Optimization [Realopt] | |
| dc.contributor.author | BEAUMONT, Olivier | |
| hal.structure.identifier | Reformulations based algorithms for Combinatorial Optimization [Realopt] | |
| dc.contributor.author | EYRAUD-DUBOIS, Lionel | |
| hal.structure.identifier | STatic Optimizations, Runtime Methods [STORM] | |
| dc.contributor.author | KUMAR, Suraj | |
| dc.date.accessioned | 2024-04-04T03:05:10Z | |
| dc.date.available | 2024-04-04T03:05:10Z | |
| dc.date.issued | 2018-09-10 | |
| dc.identifier.issn | 1532-0626 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/193222 | |
| dc.description.abstractEn | In High Performance Computing, heterogeneity is now the norm with specialized accelerators like GPUs providing efficient computational power. Resulting complexity led to the development of task-based runtime systems, where complex computations are described as task graphs, and scheduling decisions are made at run-time to perform load balancing between all resources of the platforms. Developing good scheduling strategies, even at the scale of a single node, and analyzing them both theoretically and in practice is expected to have a very high impact on the performance of current HPC systems. The special case of two kinds of resources, typically CPUs and GPUs is already of great practical interest. The scheduling policy Hetero-Prio has been proposed in the context of fast multipole computations (FMM), and has been extended to general task graphs with very promising results. In this paper, we provide a theoretical study of the performance of HeteroPrio, by proving approximation bounds compared to the optimal schedule, both in the case of independent tasks and in the case of general task graphs. Interestingly, our results establish that spoliation (a technique that enables resources to restart uncompleted tasks on another resource) is enough to prove bounded approximation ratios for a list scheduling algorithm on two unrelated resources, which is known to be impossible otherwise. This result holds true both for independent and dependent tasks graphs. Additionally, we provide an experimental evaluation of HeteroPrio on real task graphs from dense linear algebra computation, that establishes its strong performance in practice. | |
| dc.description.sponsorship | Solveurs pour architectures hétérogènes utilisant des supports d'exécution - ANR-13-MONU-0007 | |
| dc.language.iso | en | |
| dc.publisher | Wiley | |
| dc.subject.en | List scheduling | |
| dc.subject.en | Approximation proofs | |
| dc.subject.en | Runtime systems | |
| dc.subject.en | Heterogeneous scheduling | |
| dc.subject.en | Dense linear algebra | |
| dc.title.en | Fast Approximation Algorithms for Task-Based Runtime Systems | |
| dc.type | Article de revue | |
| dc.identifier.doi | 10.1002/cpe.4502 | |
| dc.subject.hal | Informatique [cs]/Calcul parallèle, distribué et partagé [cs.DC] | |
| bordeaux.journal | Concurrency and Computation: Practice and Experience | |
| bordeaux.volume | 30 | |
| bordeaux.hal.laboratories | Institut de Mathématiques de Bordeaux (IMB) - UMR 5251 | * |
| bordeaux.issue | 17 | |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| bordeaux.peerReviewed | oui | |
| hal.identifier | hal-01878606 | |
| hal.version | 1 | |
| hal.popular | non | |
| hal.audience | Internationale | |
| hal.origin.link | https://hal.archives-ouvertes.fr//hal-01878606v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=Concurrency%20and%20Computation:%20Practice%20and%20Experience&rft.date=2018-09-10&rft.volume=30&rft.issue=17&rft.eissn=1532-0626&rft.issn=1532-0626&rft.au=BEAUMONT,%20Olivier&EYRAUD-DUBOIS,%20Lionel&KUMAR,%20Suraj&rft.genre=article |
Files in this item
| Files | Size | Format | View |
|---|---|---|---|
|
There are no files associated with this item. |
|||