×

zbMATH — the first resource for mathematics

A hybrid performance analysis technique for distributed real-time embedded systems. (English) Zbl 1398.68067
Summary: It remains a challenging problem to tightly estimate the worst-case response time of an application in a distributed embedded system, especially when there are dependencies between tasks. Recently, a holistic worst-case response time analysis approach called scheduling time bound analysis has been proposed to find a tight upper bound of the worst-case response times of applications specified by a set of task graphs. Since it assumes that the starting offsets of applications are known and fixed, it fails to make a tight estimation despite increased computation time when the starting offsets are dynamic. To overcome this problem, we propose a novel conservative performance analysis, called hybrid performance analysis, combining the response time analysis technique and the scheduling time bound analysis technique to compute a tighter bound faster. The proposed scheme is proven to be conservative formally. Through extensive experiments with real-life benchmarks and synthetic examples, the superior performance of our proposed approach compared with previous methods is confirmed.
MSC:
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Audsley, N; Burns, A; Richardson, M; Tindell, K; Wellings, AJ, Applying new scheduling theory to static priority pre-emptive scheduling, Softw Eng J, 8, 284-292, (1993)
[2] Brekling A, Hansen MR, Madsen J (2008) Models and formal verification of multiprocessor system-on-chips. J Logic Algebr Program 77(12):1-19. https://doi.org/10.1016/j.jlap.2008.05.002 (the 16th Nordic Workshop on the Prgramming Theory (NWPT 2006)) · Zbl 1151.68339
[3] Diemer J, Axer P (2012) Python implementation of compositional performance analysis. http://pycpa.readthedocs.org/en/latest/
[4] Guan N, Gu C, Stigge M, Deng Q, Yi W (2014) Approximate response time analysis of real-time task graphs. In: 2014 IEEE real-time systems symposium, pp 304-313. https://doi.org/10.1109/RTSS.2014.20
[5] Harbour MG (2001) Mast: modeling and analysis suite for real-time applications. http://mast.unican.es/
[6] Henia R, Ernst R (2006) Improved offset-analysis using multiple timing-references. In: Proceedings of the design automation test in Europe conference, vol 1, p 6. https://doi.org/10.1109/DATE.2006.243802
[7] Henia, R; Hamann, A; Jersak, M; Racu, R; Richter, K; Ernst, R, System level performance analysis—the symta/s approach, IEE Proc Comput Digit Tech, 152, 148-166, (2005)
[8] Kim J, Oh H, Ha H, Kang SH, Choi J, Ha S (2012) An ilp-based worst-case performance analysis technique for distributed real-time embedded systems. In: 2012 IEEE 33rd real-time systems symposium (RTSS), pp 363-372. https://doi.org/10.1109/RTSS.2012.86
[9] Kim J, Oh H, Choi J, Ha H, Ha S (2013) A novel analytical method for worst case response time estimation of distributed embedded systems. In: 2013 50th ACM/EDAC/IEEE design automation conference (DAC), pp 1-10
[10] Kurtin PS, Hausmans JPHM, Bekooij MJG (2016) Combining offsets with precedence constraints to improve temporal analysis of cyclic real-time streaming applications. In: 2016 IEEE real-time and embedded technology and applications symposium (RTAS), pp 1-12. https://doi.org/10.1109/RTAS.2016.7461325
[11] Lehoczky J, Sha L, Ding Y (1989) The rate monotonic scheduling algorithm: exact characterization and average case behavior. In: Real time systems symposium, 1989., Proceedings., pp 166-171. https://doi.org/10.1109/REAL.1989.63567
[12] Lehoczky JP (1990) Fixed priority scheduling of periodic task sets with arbitrary deadlines. In: Real-time systems symposium, 1990. Proceedings., 11th, pp 201-209. https://doi.org/10.1109/REAL.1990.128748
[13] Palencia JC, Harbour MG (1998) Schedulability analysis for tasks with static and dynamic offsets. In: Real-time systems symposium, 1998. Proceedings., The 19th IEEE, pp 26-37. https://doi.org/10.1109/REAL.1998.739728
[14] Palencia JC, Harbour MG (1999) Exploiting precedence relations in the schedulability analysis of distributed real-time systems. In: Real-time systems symposium, 1999. proceedings. The 20th IEEE, pp 328-339, https://doi.org/10.1109/REAL.1999.818860
[15] Pellizzoni R, Lipari G (2007) Holistic analysis of asynchronous real-time transactions with earliest deadline scheduling. J Comput Syst Sci 73(2):186-206. https://doi.org/10.1016/j.jcss.2006.04.002 (special Issue: Real-time and Embedded Systems) · Zbl 1178.68105
[16] Schlatow J, Ernst R (2016) Response-time analysis for task chains in communicating threads. In: 2016 IEEE real-time and embedded technology and applications symposium (RTAS), pp 1-10. https://doi.org/10.1109/RTAS.2016.7461359
[17] Schliecker, S; Ernst, R, Real-time performance analysis of multiprocessor systems with shared memory, ACM Trans Embed Comput Syst, 10, 22:1-22:27, (2011)
[18] Stuijk S, Geilen M, Basten T (2006) Sdf3:sdf for free. http://www.es.ele.tue.nl/sdf3/download/examples.php · Zbl 1390.68153
[19] Tindell, K; Clark, J, Holistic schedulability analysis for distributed hard real-time systems, Microprocess Micropr, 40, 117-134, (1994)
[20] Tindell, K; Burns, A; Wellings, AJ, Analysis of hard real-time communications, Real-Time Syst, 9, 147-171, (1995)
[21] Yen, TY; Wolf, W, Performance estimation for real-time distributed embedded systems, IEEE Trans Parallel Distrib Syst, 9, 1125-1136, (1998)
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.