Non-clairvoyant Scheduling of Multiple Bag-of-Tasks Applications

Abstract : The bag-of-tasks application model, albeit simple, arises in many application domains and has received a lot of attention in the scheduling literature. Previous works propose either theoretically sound solutions that rely on unrealistic assumptions, or ad-hoc heuristics with no guarantees on performance. This work attempts to bridge this gap through the design of non-clairvoyant heuristics based on solid theoretical foundations. The performance achieved by these heuristics is studied via simulations in a view to comparing them both to previously proposed solutions and to theoretical upper bounds on achievable performance. Also, an interesting theoretical result in this work is that a straightforward on-demand heuristic delivers asymptotically optimal performance when the communications or the computations can be neglected.
Complete list of metadatas

Cited literature [16 references]  Display  Hide  Download

https://hal.inria.fr/inria-00527111
Contributor : Frédéric Vivien <>
Submitted on : Monday, October 18, 2010 - 10:54:36 AM
Last modification on : Thursday, August 1, 2019 - 10:42:20 AM
Long-term archiving on : Wednesday, January 19, 2011 - 2:40:26 AM

File

EuroPar2010-CGV.pdf
Publisher files allowed on an open archive

Identifiers

Collections

Citation

Henri Casanova, Matthieu Gallet, Frédéric Vivien. Non-clairvoyant Scheduling of Multiple Bag-of-Tasks Applications. Euro-Par 2010, Aug 2010, Ischia, Italy. pp.168-179, ⟨10.1007/978-3-642-15277-1_17⟩. ⟨inria-00527111⟩

Share

Metrics

Record views

326

Files downloads

207