World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

PRACTICAL STEADY-STATE SCHEDULING FOR TREE-SHAPED TASK GRAPHS

    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

    • O. Beaumontet al., Int. J. of Foundations of Computer Science 16(2), 163 (2005). Link, ISIGoogle Scholar
    • D. Bertsimas and D. Gamarnik, J. Algorithms 33(2), 296 (1999). Crossref, ISIGoogle 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
    • A. Chervenaket al., Journal of Network and Computer Applications 23(3), 187 (2000), DOI: 10.1006/jnca.2000.0110. Crossref, ISIGoogle 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
    • C. Germainet al., J. of Clinical Monitoring and Computing 19(4–5), 339 (2005), DOI: 10.1007/s10877-005-0679-9. CrossrefGoogle Scholar
    • S. Leeet al., Bioinformatics 20(18), 3500 (2004), DOI: 10.1093/bioinformatics/bth435. Crossref, ISIGoogle Scholar
    • S. J. Ludtke, P. R. Baldwin and W. Chiu, Journal of Structural Biology 128, 82 (1999), DOI: 10.1006/jsbi.1999.4174. Crossref, ISIGoogle Scholar
    • T. M. Oinnet al., Bioinformatics 20(17), 3045 (2004), DOI: 10.1093/bioinformatics/bth361. Crossref, ISIGoogle Scholar
    • L. Penget al., Multimedia Tools and Applications, Computer Science 33 (Springer, 2007) pp. 245–272. Google Scholar
    • J. Pitt-Francis, A. Garny and D. Gavaghan, Philosophical Transactions of the Royal Society A 364(1843), 1501 (2006), DOI: 10.1098/rsta.2006.1783. Crossref, ISIGoogle 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