×

zbMATH — the first resource for mathematics

A comparison of random task graph generation methods for scheduling problems. (English) Zbl 1437.68035
Yahyapour, Ramin (ed.), Euro-Par 2019: parallel processing. 25th international conference on parallel and distributed computing, Göttingen, Germany, August 26–30, 2019. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11725, 61-73 (2019).
Summary: How to generate instances with relevant properties and without bias remains an open problem of critical importance to compare heuristics fairly. When scheduling with precedence constraints, the instance is a task graph that determines a partial order on task executions. To avoid selecting instances among a set populated mainly with trivial ones, we rely on properties such as the mass, which measures how much a task graph can be decomposed into smaller ones. This property and an in-depth analysis of existing random instance generators establish the sub-exponential generic time complexity of the studied problem.
For the entire collection see [Zbl 1435.68044].
MSC:
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
68R10 Graph theory (including graph drawing) in computer science
Software:
TGFF
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Adam, T.L., Chandy, K.M., Dickson, J.: A comparison of list schedules for parallel processing systems. Commun. ACM 17(12), 685-690 (1974) · Zbl 0293.68047
[2] Aho, A.V., Garey, M.R., Ullman, J.D.: The transitive reduction of a directed graph. SIAM J. Comput. 1(2), 131-137 (1972) · Zbl 0247.05128
[3] Campos, P., Dahir, N., Bonney, C., Trefzer, M., Tyrrell, A., Tempesti, G.: Xl-stage: a cross-layer scalable tool for graph generation, evaluation and implementation. In: 2016 International Conference on Embedded Computer Systems: Architectures, Modeling and Simulation (SAMOS), pp. 354-359. IEEE (2016)
[4] Canon, L.C., El Sayah, M., Héam, P.C.: A comparison of random task graph generation methods for scheduling problems. arXiv preprint arXiv:1902.05808 (2019)
[5] Canon, L.-C., Marchal, L., Simon, B., Vivien, F.: Online scheduling of task graphs on hybrid platforms. In: Aldinucci, M., Padovani, L., Torquati, M. (eds.) Euro-Par 2018. LNCS, vol. 11014, pp. 192-204. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96983-1_14
[6] Cordeiro, D., Mounié, G., Perarnau, S., Trystram, D., Vincent, J.M., Wagner, F.: Random graph generation for scheduling simulations. In: ICST, p. 60 (2010)
[7] Dick, R.P., Rhodes, D.L., Wolf, W.: TGFF: task graphs for free. In: International workshop on Hardware/software codesign, pp. 97-101. IEEE (1998)
[8] Dutot, P.F., N’takpé, T., Suter, F., Casanova, H.: Scheduling parallel task graphs on (almost) homogeneous multicluster platforms. IEEE TPDS 20(7), 940-952 (2009)
[9] Erdős, P., Rényi, A.: On random graphs I. Publ. Math. Debrecen 6, 290-297 (1959) · Zbl 0092.15705
[10] Garey, M., Johnson, D.: Strong NP-completeness results: motivation, examples, and implications. J. Assoc. Comput. Mach. 25(3), 499-508 (1978) · Zbl 0379.68035
[11] Graham, R.L., Lawler, E.L., Lenstra, J.K., Kan, A.H.G.R.: Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discret. Math. 5, 287-326 (1979) · Zbl 0411.90044
[12] Gupta, I., Choudhary, A., Jana, P.K.: Generation and proliferation of random directed acyclic graphs for workflow scheduling problem. In: International Conference on Computer and Communication Technology, pp. 123-127. ACM (2017)
[13] Hagras, T., Janecek, J.: A simple scheduling heuristic for heterogeneous computing environments. In: ISPDC, p. 104. IEEE (2003) · Zbl 1109.68035
[14] Ibarra, O.H., Kim, C.E.: Heuristic algorithms for scheduling independent tasks on nonidentical processors. J. ACM 24(2), 280-289 (1977) · Zbl 0382.90048
[15] Jain, R.: The Art of Computer Systems Performance Analysis: Techniques for Experimental design, measurement, simulation, and modeling. Wiley, Hoboken (1990)
[16] Juve, G., Chervenak, A., Deelman, E., Bharathi, S., Mehta, G., Vahi, K.: Characterizing and profiling scientific workflows. Future Gener. Comput. Syst. 29(3), 682-692 (2013)
[17] Leung, J.Y.: Handbook of Scheduling: Algorithms, Models, and Performance Analysis. CRC Press, Boca Raton (2004) · Zbl 1103.90002
[18] Levin, D.A., Peres, Y.: Markov Chains and Mixing Times, vol. 107. American Mathematical Society, Providence (2017)
[19] Liskovets, V.: On the number of maximal vertices of a random acyclic digraph. Theory Probab. Appl. 20(2), 401-409 (1975) · Zbl 0362.60030
[20] Mantel, W.: Problem 28. Wiskundige Opgaven 10(60-61), 320 (1907)
[21] Melançon, G., Dutour, I., Bousquet-Mélou, M.: Random generation of directed acyclic graphs. Electron. Not. Discrete Math. 10, 202-207 (2001) · Zbl 1171.05339
[22] Robinson, R.W.: Counting labeled acyclic digraphs. In: Harray, F. (ed.) New Directions in the Theory of Graphs, pp. 239-273. Academic Press, New York (1973) · Zbl 0259.05116
[23] Tobita, T., Kasahara, H.: A standard task graph set for fair evaluation of multiprocessor scheduling algorithms. J. Sched. 5(5), 379-394 (2002) · Zbl 1014.90044
[24] Topcuoglu, H., Hariri, S., Wu, M.Y.: Performance-effective and low-complexity task scheduling for heterogeneous computing. IEEE TPDS 13(3), 260-274 (2002)
[25] Ullman, J.: NP-complete scheduling problems. J. Comput. System Sci. 10, 384-393 (1975) · Zbl 0313.68054
[26] Winkler, P. · Zbl 0565.06002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.