×

On the scalability of constraint solving for static/off-line real-time scheduling. (English) Zbl 1465.68031

Sankaranarayanan, Sriram (ed.) et al., Formal modeling and analysis of timed systems. 13th international conference, FORMATS 2015, Madrid, Spain, September 2–4, 2015. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 9268, 108-123 (2015).
Summary: Recent papers have reported on successful application of constraint solving techniques to off-line real-time scheduling problems, with realistic size and complexity. Success allegedly came for two reasons: major recent advances in solvers efficiency and use of optimized, problem-specific constraint representations. Our current objective is to assess further the range of applicability and the scalability of such constraint solving techniques based on a more general and agnostic evaluation campaign. For this, we have considered a large number of synthetic scheduling problems and a few real-life ones, and attempted to solve them using 3 state-of-the-art solvers, namely CPLEX, Yices2, and MiniZinc/G12. Our findings were that, for all problems considered, constraint solving does scale to a certain limit, then diverges rapidly. This limit greatly depends on the specificity of the scheduling problem type. All experimental data (synthetic task systems, SMT/ILP models) are provided so as to allow experimental reproducibility.
For the entire collection see [Zbl 1319.68012].

MSC:

68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
90B35 Deterministic scheduling theory in operations research

Software:

CPLEX
PDFBibTeX XMLCite
Full Text: DOI HAL

References:

[1] Bahn, J.H., Yang, J., Bagherzadeh, N.: Parallel fft algorithms on network-on-chips. In: Proceedings ITNG 2008, April 2008
[2] Baptiste, P., Le Pape, C., Nuijten, W.: Constraint-based scheduling: applying constraint programming to scheduling problems, vol. 39. Springer Science & Business Media (2001) · Zbl 1094.90002
[3] Bini, E.; Buttazzo, G., Measuring the performance of schedulability tests, Real Time Systems, 30, 129-154 (2005) · Zbl 1083.68008 · doi:10.1007/s11241-005-0507-9
[4] Carle, T.; Potop-Butucaru, D., Predicate-aware, makespan-preserving software pipelining of scheduling tables, TACO, 11, 1, 12 (2014) · doi:10.1145/2579676
[5] Carle, T., Potop-Butucaru, D., Sorel, Y., Lesens, D.: From dataflow specification to multiprocessor partitioned time-triggered real-time implementation. Research Report RR-8109 (2012). https://hal.inria.fr/hal-00742908
[6] Coffman Jr, APE; Graham, RL, Optimal scheduling for two-processor systems, Acta informatica, 1, 3, 200-213 (1972) · Zbl 0248.68023 · doi:10.1007/BF00288685
[7] Craciunas, S., Oliver, R.S.: SMT-based task- and network-level static schedule generation for time-triggered networked systems. In: Proceedings RTNS 2014. pp. 45:45-45:54. ACM, New York (2014). doi:10.1145/2659787.2659812
[8] Garey, M.; Johnson, D., Complexity results for multiprocessor scheduling under resource constraints, SIAM Journal of Computing, 4, 4, 397-411 (1975) · Zbl 0365.90076 · doi:10.1137/0204035
[9] Gu, Z., He, X., Yuan, M.: Optimization of static task and bus access schedules for time-triggered distributed embedded systems with model-checking. In: 44th ACM/IEEE Design Automation Conference, DAC 2007, pp. 294-299, June 2007
[10] Hang, C.; Manolios, P.; Papavasileiou, V.; Gopalakrishnan, G.; Qadeer, S., Synthesizing cyber-physical architectural models with real-time constraints, Computer Aided Verification, 441-456 (2011), Heidelberg: Springer, Heidelberg · doi:10.1007/978-3-642-22110-1_35
[11] Leyton-Brown, K.; Hoos, HH; Hutter, F.; Xu, L., Understanding the empirical hardness of np-complete problems, Commun. ACM, 57, 5, 98-107 (2014) · doi:10.1145/2594413.2594424
[12] Megel, T., Sirdey, R., David, V.: Minimizing task preemptions and migrations in multiprocessor optimal real-time schedules. In: 2010 IEEE 31st Real-Time Systems Symposium (RTSS), pp. 37-46, November 2010
[13] Nowatzki, T.; Sartin-Tarm, M.; Carli, LD; Sankaralingam, K.; Estan, C.; Robatmili, B., A general constraint-centric scheduling framework for spatial architectures, SIGPLAN Not., 48, 6, 495-506 (2013) · doi:10.1145/2499370.2462163
[14] Tendulkar, P.; Poplavko, P.; Maler, O.; Braberman, V.; Fribourg, L., Symmetry breaking for multi-criteria mapping and scheduling on multicores, Formal Modeling and Analysis of Timed Systems, 228-242 (2013), Heidelberg: Springer, Heidelberg · Zbl 1390.68154 · doi:10.1007/978-3-642-40229-6_16
[15] Topcuoglu, H.; Hariri, S.; Wu, MY, Performance-effective and low-complexity task scheduling for heterogeneous computing, IEEE Transactions on Parallel and Distributed Systems, 13, 3, 260-274 (2002) · doi:10.1109/71.993206
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.