Approximation Proofs of a Fast and Efficient List Scheduling Algorithm for Task-Based Runtime Systems on Multicores and GPUs
| 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] | |
| hal.structure.identifier | Reformulations based algorithms for Combinatorial Optimization [Realopt] | |
| hal.structure.identifier | High-End Parallel Algorithms for Challenging Numerical Simulations [HiePACS] | |
| dc.contributor.author | KUMAR, Suraj | |
| dc.date.accessioned | 2024-04-04T03:10:48Z | |
| dc.date.available | 2024-04-04T03:10:48Z | |
| dc.date.created | 2016-10 | |
| dc.date.conference | 2017-05-29 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/193715 | |
| dc.description.abstractEn | In High Performance Computing, heterogeneity is now the norm with specialized accelerators like GPUs providing efficient computational power. The added complexity has led to the development of task-based runtime systems, which allow complex computations to be expressed as task graphs, and rely on scheduling algorithms to perform load balancing between all resources of the platforms. Developing good scheduling algorithms , even on a single node, and analyzing them can thus have a very high impact on the performance of current HPC systems. The special case of two types of resources (namely CPUs and GPUs) is of practical interest. HeteroPrio is such an algorithm which has been proposed in the context of fast multipole computations, and then extended to general task graphs with very interesting results. In this paper, we provide a theoretical insight on the performance of HeteroPrio, by proving approximation bounds compared to the optimal schedule in the case where all tasks are independent and for different platform sizes. Interestingly, this shows that spoliation allows to prove approximation ratios for a list scheduling algorithm on two unrelated resources, which is not possible otherwise. We also establish that almost all our bounds are tight. Additionally, we provide an experimental evaluation of HeteroPrio on real task graphs from dense linear algebra computation, which highlights the reasons explaining its good practical performance. | |
| 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.subject.en | Approximation proofs | |
| dc.subject.en | Runtime systems | |
| dc.subject.en | Heterogeneous scheduling | |
| dc.subject.en | List scheduling | |
| dc.subject.en | Dense linear algebra | |
| dc.title.en | Approximation Proofs of a Fast and Efficient List Scheduling Algorithm for Task-Based Runtime Systems on Multicores and GPUs | |
| dc.type | Communication dans un congrès | |
| dc.identifier.doi | 10.1109/IPDPS.2017.71 | |
| dc.subject.hal | Informatique [cs]/Calcul parallèle, distribué et partagé [cs.DC] | |
| bordeaux.hal.laboratories | Institut de Mathématiques de Bordeaux (IMB) - UMR 5251 | * |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| bordeaux.conference.title | IEEE International Parallel & Distributed Processing Symposium (IPDPS) | |
| bordeaux.country | US | |
| bordeaux.conference.city | Orlando | |
| bordeaux.peerReviewed | oui | |
| hal.identifier | hal-01386174 | |
| hal.version | 1 | |
| hal.invited | non | |
| hal.proceedings | oui | |
| hal.conference.end | 2017-06-02 | |
| hal.popular | non | |
| hal.audience | Internationale | |
| hal.origin.link | https://hal.archives-ouvertes.fr//hal-01386174v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.au=BEAUMONT,%20Olivier&EYRAUD-DUBOIS,%20Lionel&KUMAR,%20Suraj&rft.genre=unknown |
Files in this item
| Files | Size | Format | View |
|---|---|---|---|
|
There are no files associated with this item. |
|||