PRACTICAL STEADY-STATE SCHEDULING FOR TREE-SHAPED TASK GRAPHS
Abstract
In this paper, we focus on the problem of scheduling a collection of similar task graphs on a heterogeneous platform, when the task graph is an intree. We rely on steady-state scheduling techniques, and aim at optimizing the throughput of the system. Contrarily to previous studies, we concentrate on practical aspects of steady-state scheduling, when dealing with a collection (or batch) of limited size. We focus here on two optimizations. The first one consists in reducing the processing time of each task graph, thus making steady-state scheduling applicable to smaller batches. The second one consists in degrading a little the optimal-throughput solution to get a simpler solution, more efficient on small batches. We present our optimizations in details, and show that they both help to overcome the limitation of steady-state scheduling: our simulations show that we are able to reach a better efficiency on small batches, to reduce the size of the buffers, and to significantly decrease the processing time of a single task graph (latency).
References
- Int. J. of Foundations of Computer Science 16(2), 163 (2005). Link, ISI, Google Scholar
- J. Algorithms 33(2), 296 (1999). Crossref, ISI, Google Scholar
- H. Casanova, A. Legrand, and M. Quinson. SimGrid: a Generic Framework for Large-Scale Distributed Experiments. In 10th IEEE International Conference on Computer Modeling and Simulation, Mar. 2008 . Google Scholar
- Journal of Network and Computer Applications 23(3), 187 (2000), DOI: 10.1006/jnca.2000.0110. Crossref, ISI, Google Scholar
- ILOG CPLEX: High-performance software for mathematical programming and optimization. http://www.ilog.com/products/cplex/ . Google Scholar
S. Diakité , J.-M. Nicod and L. Philippe , Comparison of batch scheduling for identical multitasks jobs on heterogeneous platforms, PDP (2008) pp. 374–378. Google Scholar- S. Diakité, L. Marchal, J.-M. Nicod, and L. Philippe. Steady-state for batches of identical task graphs. Research report, LIP, ENS Lyon, France, Jan. 2009. available at http://graal.enslyon.fr/~lmarchal/pub/reports/RR2009-batches-steady-state.pdf . Google Scholar
-
I. T. Foster and C. Kesselman (eds.) , The Grid 2: Blueprint for a New Computing Infrastructure ( Morgan Kaufmann Publishers , 2004 ) . Google Scholar -
M. R. Garey and D. S. Johnson , Computers and Intractability, a Guide to the Theory of NP-Completeness ( W. H. Freeman and Company , 1979 ) . Google Scholar - J. of Clinical Monitoring and Computing 19(4–5), 339 (2005), DOI: 10.1007/s10877-005-0679-9. Crossref, Google Scholar
- Bioinformatics 20(18), 3500 (2004), DOI: 10.1093/bioinformatics/bth435. Crossref, ISI, Google Scholar
- Journal of Structural Biology 128, 82 (1999), DOI: 10.1006/jsbi.1999.4174. Crossref, ISI, Google Scholar
- Bioinformatics 20(17), 3045 (2004), DOI: 10.1093/bioinformatics/bth361. Crossref, ISI, Google Scholar
L. Peng , Multimedia Tools and Applications,Computer Science 33 (Springer, 2007) pp. 245–272. Google Scholar- Philosophical Transactions of the Royal Society A 364(1843), 1501 (2006), DOI: 10.1098/rsta.2006.1783. Crossref, ISI, Google Scholar
H. Topcuoglu , S. Hariri and M.-Y. Wu , Task scheduling algorithms for heterogeneous processors, Proceedings of HCW '99 (IEEE CS, Washington, DC, USA, 1999) p. 3. Google Scholar


