×

Stretching algorithm for global scheduling of real-time DAG tasks. (English) Zbl 1436.68072

Summary: Parallelism is becoming more important nowadays due to the increasing use of multiprocessor systems. A Directed Acyclic Graph (DAG) is a general model of parallel tasks with inter-subtask parallelism. It consists of a collection of dependent subtasks under precedence constraints. In this paper, we study the problem of scheduling \(n\) periodic parallel real-time DAG tasks on \(m\) homogeneous multiprocessor systems. The dependencies between subtasks make scheduling process more challenging. We propose a stretching algorithm to be applied on each DAG task prior to scheduling process. Thus, DAGs are transformed into a set of independent sequential threads with intermediate offsets and deadlines. The threads obtained due to the transformation are of two types, (i) fully-stretched master threads with utilization equal to 1 and (ii) independent constrained-deadline threads. We propose a scheduling method over RTOS to ensure the execution of fully-stretched master threads on dedicated processors while the remaining processors \(\overline{m} \le m\), are used to schedule the independent constrained-deadline threads using any multiprocessor scheduling algorithm. In this work, we analyze the stretching algorithm while considering two global preemptive scheduling algorithms from different priority assignment families; the Global Earliest Deadline First (GEDF) from the fixed job priority family, and the Global Deadline Monotonic (GDM) from the fixed task priority family. We prove that GEDF scheduling of stretched threads has a resource augmentation bound equal to \(\frac{3+\sqrt{5}}{2}\) for all task sets with \(n < \phi \times \overline{m}\), where \(n\) is the number of tasks in the set and \(\phi \) is the golden ratio (the value of the golden ratio is \(\frac{1+\sqrt{5}}{2}\)). While GDM has a resource augmentation bound equal to \(2+\sqrt{3}\) for all task sets with \(n < \frac{1+\sqrt{3}}{2} \times \overline{m}\).

MSC:

68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
68R10 Graph theory (including graph drawing) in computer science

Software:

YARTISS; SHUM-uCOS
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Andersson B, D De Niz (2012) Analyzing global-EDF for multiprocessor scheduling of parallel tasks. In: Proceedings of the 16th international conference on principles of distributed systems (OPODIS), pp 16-30
[2] Baruah SK (2007) Techniques for multiprocessor global schedulability analysis. In: Proceedings of the 28th IEEE international real-time systems symposium (RTSS), pp 119-128. IEEE
[3] Baruah SK, Bonifaci V, Marchetti-Spaccamela A, Stougie L, Wiese A (2012) A generalized parallel task model for recurrent real-time processes. In: Proceedings of the 33rd IEEE real-time systems symposium (RTSS), pp 63-72. IEEE Computer Society
[4] Bertogna M, Cirinei M, Lipari G (2006) New schedulability tests for real-time task sets scheduled by deadline monotonic on multiprocessors. In: Proceedings of the 9th intern0ational conference on principles of distributed systems, OPODIS’05, pp 306-321, Springer, Berlin
[5] Bonifaci V, Marchetti-Spaccamela A, Stiller S, Wiese A (2013) Feasibility analysis in the sporadic DAG task model. In: Proceedings of the 25th euromicro conference on real-time systems (ECRTS), pp 225-233
[6] Chandarli Y, Fauberteau F, Damien M, Midonnet S, Qamhieh M (2012) YARTISS: a tool to visualize, test, compare and evaluate real-time scheduling algorithms. In: Proceedings of the 3rd international workshop on analysis tools and methodologies for embedded and real-time systems (WATERS)
[7] Chetto H, Silly M, Bouchentouf T (1990) Dynamic scheduling of real-time tasks under precedence constraints. Real-Time Syst 2(3):181-194
[8] Chwa HS, Lee J, Phan K, Easwaran A, Shin I (2013) Global EDF schedulability analysis for synchronous parallel tasks on multicore platforms. In: Proceedings of the 25th euromicro conference on real-time systems (ECRTS), pp 25-34
[9] Davis RI, Burns A (2011) A survey of hard real-time scheduling algorithms and schedulability analysis techniques for multiprocessor systems. ACM Computing surveys, pp 1-44
[10] Goossens J, Devillers R (1997) The non-optimality of the monotonic priority assignmentsfor hard real-time offset free systems. Real-Time Syst 13(2):107-126
[11] Goossens J, Macq C (2001) Limitation of the hyper-period in real-time periodic task set generation. In: Proceedings of the 9th international conference on real-time systems (RTS), pp 133-148
[12] Gu Z, Kodase S, Wang S, Shin KG (2003) A model-based approach to system-level dependency and real-time analysis of embedded software. In: Real-time and embedded technology and applications symposium, 2003. Proceedings. The 9th IEEE, pp 78-85. IEEE
[13] Lakshmanan K, Kato S, Rajkumar RR (2010) Scheduling parallel real-time tasks on multi-core processors. In: Proceedings of the 31st IEEE real-time systems symposium (RTSS), pp 259-268. IEEE computer society
[14] Li J, Agrawal K, Lu C, Gill C0(2013) Analysis of global EDF for parallel tasks. In: Euromicro conference on real-time systems (ECRTS), No 314
[15] Li J, Chen J-J, Agrawal K, Lu C, Gill C, Saifullah A (2014) Analysis of federated and global scheduling for parallel real-time tasks. In: Proceedings of the 26th euromicro conference on real-time systems (ECRTS)
[16] Oliva Y, Pelcat M, Nezan J-F, Prevotet J-C, Aridhi S (2011) Building a RTOS for MPSOC dataflow programming. In: System on Chip (SoC), 2011 international symposium on, pp143-146. IEEE
[17] Qamhieh M, Fauberteau F (2013) Laurent george, and serge midonnet. Global EDF scheduling of directed acyclic graphs on multiprocessor systems. In: Proceedings of the 21st international conference on real-time networks and systems, RTNS ’13, pp 287-296. ACM
[18] Saifullah A, Agrawal K, Lu C, Gill C (2011) Multi-core real-time scheduling for generalized parallel task models. In: Proceedings of the 32nd IEEE real-time systems symposium (RTSS), pp 217-226 · Zbl 1291.68096
[19] Saifullah A, Ferry D, Agrawal K, Lu C, Gill C (2012) Real-time scheduling of parallel tasks under a general DAG model. Technical report, Washington University in St Louis
[20] Saifullah A, Ferry D, Li J, Agrawal K, Lu C, Gill C (2014) Parallel real-time scheduling of DAGs. IEEE transactions on parallel and distributed systems, 99:1
[21] Shivshankar S, Vangara S, Dean AG (2005) Balancing register pressure and context-switching delays in ASTI systems. In: Proceedings of the 2005 international conference on Compilers, architectures and synthesis for embedded systems, pp 286-294. ACM
[22] Zhou B, Qiu W, Chen Y, Peng C (2005) Shum-ucos: A RTOS using multi-task model to reduce migration cost between sw/hw tasks. In: Computer supported cooperative work in design, 2005. Proceedings of the ninth international conference on, vol 2, pp 984-989. IEEE
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.