Abstract

Multi-core architectures, which have multiple processing units on a single chip, are widely used as a way to achieve higher processor performance. They have potential to deliver increased performance over single-core processors. Multi-core processors have become mainstream in processor design. In multiprocessing, only inter task parallelism can be achieved. But, computation-intensive real-time systems must exploit intra-task parallelism to take full advantage of multi-core processing. In this paper, the problem of scheduling periodic parallel tasks with implicit deadlines on multi-core processors is addressed. A task decomposition method that decomposes each parallel task into a set of sequential tasks is discussed. In this paper, a general model for deterministic parallel tasks, where a task is represented as a DAG with different nodes having different execution requirements is discussed. First, a DAG generation method for the tasks is discussed and secondly, task decomposition that splits a DAG into sequential tasks is discussed.

References

• R. I. Davis and A. Burns, "A survey of hard real-time scheduling for multiprocessor systems," ACM Comp. Surv. , vol. 43, pp. 35:1–44, 2011.
• A. Saifullah, K. Agrawal, C. Lu, and C. Gill, "Multi-core real-time scheduling for generalized parallel task models," in RTSS '11.
• K. Lakshmanan, S. Kato, and R. R. Rajkumar, "Scheduling parallel realtime tasks on multi-core processors," in RTSS '10.
• "OpenMP," http://openmp. org.
• "Intel CilkPlus," http://software. intel. com/en-us/articles/intel-cilk-plus.
• X. Deng, N. Gu, T. Brecht, and K. Lu, "Preemptive scheduling of parallel jobs on multiprocessors," in SODA '96.
• K. Agrawal, Y. He, W. J. Hsu, and C. E. Leiserson, "Adaptive task scheduling with parallelism feedback," in PPoPP '06.
• J. M. Calandrino and J. H. Anderson, "On the design and implementation of a cache-aware multicore real-time scheduler," in ECRTS '09.
• J. M. Calandrino, J. H. Anderson, and D. P. Baumberger, "A hybrid real-time scheduling approach for large-scale multicore platforms," in ECRTS '07.
• J. H. Anderson and J. M. Calandrino, "Parallel real-time task scheduling on multicore platforms," in RTSS '06.
• C. -C. Han and K. -J. Lin, "Scheduling parallelizable jobs on multiprocessors," in RTSS '89.
• S. Baruah, "Techniques for multiprocessor global schedulability analysis,"in RTSS '07.
• J. Goossens, S. Funk, and S. Baruah, "Priority-driven scheduling of periodic task systems on multiprocessors," Real-Time Syst. , vol. 25, no. 2-3, pp. 187–205, 2003.
• S. Baruah, "The non-preemptive scheduling of periodic tasks upon multiprocessors," Real-Time Syst. , vol. 32, pp. 9–20, 2006.
• Jos´e Carlos Fonseca, Lu´?s Nogueira, Cl´audio Maia, and Lu´?s Miguel Pinho,"Real-Time Scheduling of Parallel Tasks in the Linux Kernel"
• D. I. George Amalarethinam and G. J. Joyce Mary, "A new DAG based Dynamic Task Scheduling Algorithm (DYTAS) for Multiprocessor Systems", in International Journal of Computer Applications (0975 – 8887) Volume 19– No. 8, April 2011
• D. I. George Amalarethinam1 and G. J. Joyce Mary, "DAGEN - A Tool To Generate Arbitrary Directed Acyclic Graphs Used For Multiprocessor Scheduling", in International Journal of Research and Reviews in Computer Science (IJRRCS) Vol. 2, No. 3, June 2011
• C. -C. Han and K. -J. Lin, "Scheduling parallelizable jobs on multiprocessors,"in RTSS '89.
• K. Jansen, "Scheduling malleable parallel tasks: An asymptotic fullypolynomial time approximation scheme," Algorithmica, vol. 39, no. 1,pp. 59–81, 2004.
• W. Y. Lee and H. Lee, "Optimal scheduling for real-time parallel tasks,"IEICE Trans. Inf. Syst. , vol. E89-D, no. 6, pp. 1962–1966, 2006.
• S. Collette, L. Cucu, and J. Goossens, "Integrating job parallelism in real-time scheduling theory," Inf. Process. Lett. , vol. 106, no. 5, pp. 180–187, 2008.
• G. Manimaran, C. S. R. Murthy, and K. Ramamritham, "A new approach for scheduling of parallelizable tasks inreal-time multiprocessor systems," Real-Time Syst. , vol. 15, no. 1, pp. 39–60, 1998
• S. Kato and Y. Ishikawa, "Gang EDF scheduling of parallel task systems," in RTSS '09.
• N. Fisher, T. P. Baker, and S. Baruah, "Algorithms for determining the demand-based load of a sporadic task system," in TCSA '06.
• J. Goossens, S. Funk, and S. Baruah, "Priority-driven scheduling of periodic task systems on multiprocessors," Real-Time Syst. , vol. 25, no. 2-3, pp. 187–205, 2003.
• Daniel Cordeiro, Grégory Mounié, Swann Perarnau, Denis Trystram, Jean-Marc Vincent, Frédéric Wagner, "Random graph generation for scheduling simulations" in simutools'10
• N. S. Arora, R. D. Blumofe, and C. G. Plaxton, "Thread scheduling for multiprogrammed multiprocessors," in SPAA '98.
• Ricardo Garibay-Martínez, Luis Lino Ferreira, Luis Miguel Pinho,"A Framework for the Development of Parallel and Distributed Real-Time Embedded Systems "
• R. I. Davis and A. Burns, "A survey of hard real-time scheduling for multiprocessor systems," ACM Comp. Surv. , vol. 43, pp. 35:1–44, 2011.