Dynamic and Static Task Allocation for Hard Real-Time Video Stream Decoding on NoCs

Hashan R. Mendis, Neil C. Audsley, Leandro Soares Indrusiak


Hard real-time (HRT) video systems require admission control decisions that rely on two factors. Firstly, schedulability analysis of the data-dependent, communicating tasks within the application need to be carried out in order to guarantee timing and predictability. Secondly, the allocation of the tasks to multi-core processing elements would generate different results in the schedulability analysis. Due to the conservative nature of the state-of-the-art schedulability analysis of tasks and message flows, and the unpredictability in the application, the system resources are often under-utilised. In this paper we propose two blocking-aware dynamic task allocation techniques that exploit application and platform characteristics, in order to increase the number of simultaneous, fully schedulable, video streams handled by the system. A novel, worst-case response time aware, search-based, static hard real-time task mapper is introduced to act as an upper-baseline to the proposed techniques. Further evaluations are carried out against existing heuristic-based dynamic mappers. Improvements to the admission rates and the system utilisation under a range of different workloads and platform sizes are explored.


Real-time multimedia; Task mapping; Network-on-chip

Full Text:



Hazem Ismail Abdel Aziz Ali, Luís Miguel Pinho, and Benny Akesson.Critical-Path-First based allocation of real-time streaming applications on 2D mesh-type multi-cores. In 2013 IEEE 19th International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2013, Taipei, Taiwan, August 19-21, 2013, pages 201-208. IEEE Computer Society, 2013. URL: http://dx.doi.org/10.1109/RTCSA.2013.6732220

Giuseppe Ascia, Vincenzo Catania, and Maurizio Palesi.A Multi-objective Genetic Approach to Mapping Problem on Network-on-Chip. J. UCS, 12(4):370-394, 2006. URL: http://dx.doi.org/10.3217/jucs-012-04-0370

Neil C. Audsley, Alan Burns, Mike M. Richardson, Ken Tindell, and Andy J. Wellings.Applying new scheduling theory to static priority pre-emptive scheduling. Software Engineering Journal, 8(5):284-292, 1993. URL: http://dx.doi.org/10.1049/sej.1993.0034

Mohamed A. Bamakhrama and Todor P. Stefanov.On the hard-real-time scheduling of embedded streaming applications. Design Autom. for Emb. Sys., 17(2):221-249, 2013. URL: http://dx.doi.org/10.1007/s10617-012-9086-x

Evgeny Bolotin, Israel Cidon, Ran Ginosar, and Avinoam Kolodny.QNoC: QoS architecture and design process for network on chip. Journal of Systems Architecture, 50(2-3):105-128, 2004. URL: http://dx.doi.org/10.1016/j.sysarc.2003.07.004

Giorgio C. Buttazzo, Enrico Bini, and Yifan Wu.Partitioning Real-Time Applications Over Multicore Reservations.IEEE Trans. Industrial Informatics, 7(2):302-315, 2011. URL: http://dx.doi.org/10.1109/TII.2011.2123902

William J. Dally and Brian Towles.Route Packets, Not Wires: On-Chip Interconnection Networks. In Proceedings of the 38th Design Automation Conference, DAC 2001, Las Vegas, NV, USA, June 18-22, 2001, pages 684-689. ACM, 2001. URL: http://dx.doi.org/10.1145/378239.379048

Ewerson Luiz de Souza Carvalho, Ney Laert Vilar Calazans, and Fernando Gehm Moraes.Dynamic Task Mapping for MPSoCs.IEEE Design & Test of Computers, 27(5):26-35, 2010. URL: http://dx.doi.org/10.1109/MDT.2010.106

Michael Ditze, Peter Altenbernd, and Chris Loeser.Improving Resource Utilization for MPEG-4 Decoding in Embedded End-Devices. In Vladimir Estivill-Castro, editor, Computer Science 2004, Twenty-Seveth Australasian Computer Science Conference (ACSC2004), Dunedin, New Zealand, January 2004, volume 26 of CRPIT, pages 133-142. Australian Computer Society, 2004. URL: http://crpit.com/confpapers/CRPITV26Ditze.pdf.

Piotr Dziurzanski, Amit Kumar Singh, and Leandro Soares Indrusiak.Feedback-Based Admission Control for Hard Real-Time Task Allocation Under Dynamic Workload on Many-Core Systems. In Frank Hannig, João M. P. Cardoso, Thilo Pionteck, Dietmar Fey, Wolfgang Schröder-Preikschat, and Jürgen Teich, editors, Architecture of Computing Systems - ARCS 2016 - 29th International Conference, Nuremberg, Germany, April 4-7, 2016, Proceedings, volume 9637 of Lecture Notes in Computer Science, pages 157-169. Springer, 2016. URL: http://dx.doi.org/10.1007/978-3-319-30695-7_12

ETSI.ETSITS 101 154 v1.10.1 (2011-06) - digital video broadcasting (DVB) - specification for the use of video and audio coding in broadcasting applications based on the MPEG-2 transport stream. Technical report, European Telecommunications Standards Institute (ETSI), June 2011.

Mohammad Abdullah Al Faruque and Jörg Henkel.QoS-supported On-chip Communication for Multi-processors. International Journal of Parallel Programming, 36(1):114-139, 2008. URL: http://dx.doi.org/10.1007/s10766-007-0039-0

Georgia Giannopoulou, Nikolay Stoimenov, Pengcheng Huang, Lothar Thiele, and Benoît Dupont de Dinechin.Mixed-criticality scheduling on cluster-based manycores with shared communication and storage resources. Real-Time Systems, 52(4):399-449, 2016. URL: http://dx.doi.org/10.1007/s11241-015-9227-y

Blake Hannaford, Jacob Rosen, Diana C. W. Friedman, Hawkeye H. I. King, Phillip Roan, Lei Cheng, Daniel Glozman, Ji Ma, Sina Nia Kosari, and Lee White.Raven-II: An Open Platform for Surgical Robotics Research.IEEE Trans. Biomed. Engineering, 60(4):954-959, 2013. URL: http://dx.doi.org/10.1109/TBME.2012.2228858

Jia Huang, Andreas Raabe, Christian Buckl, and Alois Knoll.A workflow for runtime adaptive task allocation on heterogeneous MPSoCs. In Design, Automation and Test in Europe, DATE 2011, Grenoble, France, March 14-18, 2011, pages 1119-1134. IEEE, 2011. URL: http://dx.doi.org/10.1109/DATE.2011.5763189

Leandro Soares Indrusiak.End-to-end schedulability tests for multiprocessor embedded systems based on networks-on-chip with priority-preemptive arbitration. Journal of Systems Architecture - Embedded Systems Design, 60(7):553-561, 2014. URL: http://dx.doi.org/10.1016/j.sysarc.2014.05.002

Leandro Soares Indrusiak, James Harbin, and Osmar Marchi dos Santos.Fast Simulation of Networks-on-Chip with Priority-Preemptive Arbitration.ACM Trans. Design Autom. Electr. Syst., 20(4):56:1-56:22, 2015. URL: http://dx.doi.org/10.1145/2755559

Damir Isovic and Gerhard Fohler.Quality Aware MPEG-2 Stream Adaptation in Resource Constrained Systems. In 16th Euromicro Conference on Real-Time Systems (ECRTS 2004), 30 June - 2 July 1004, Catania, Italy, Proceedings, pages 23-32. IEEE Computer Society, 2004. URL: http://dx.doi.org/10.1109/ECRTS.2004.29

Damir Isovic, Gerhard Fohler, and Liesbeth Steffens.Timing Constraints of MPEG-2 Decoding for High Quality Video: Misconceptions and Realistic Assumptions. In 15th Euromicro Conference on Real-Time Systems (ECRTS 2003), 2-4 July 2003, Porto, Portugal, Proceedings, pages 73-82. IEEE Computer Society, 2003. URL: http://dx.doi.org/10.1109/EMRTS.2003.1212730

Ben Kao and Hector Garcia-Molina.Deadline Assignment in a Distributed Soft Real-Time System.IEEE Trans. Parallel Distrib. Syst., 8(12):1268-1274, 1997. URL: http://dx.doi.org/10.1109/71.640019

Samarth Kaushik, Amit Kumar Singh, and Thambipillai Srikanthan.Computation and communication aware run-time mapping for NoC-based MPSoC platforms. In IEEE 24th International SoC Conference, SOCC 2011, Taipei, Taiwan, September 26-28, 2011, pages 185-190. IEEE, 2011. URL: http://dx.doi.org/10.1109/SOCC.2011.6085078

Cor Meenderinck, Arnaldo Azevedo, Ben H. H. Juurlink, Mauricio Alvarez, and Alex Ramírez.Parallel Scalability of Video Decoders. Signal Processing Systems, 57(2):173-194, 2009. URL: http://dx.doi.org/10.1007/s11265-008-0256-9

Hashan Roshantha Mendis, Neil C. Audsley, and Leandro Soares Indrusiak.Task allocation for decoding multiple hard real-time video streams on homogeneous NoCs. In 13th IEEE International Conference on Industrial Informatics, INDIN 2015, Cambridge, United Kingdom, July 22-24, 2015, pages 246-251. IEEE, 2015. URL: http://dx.doi.org/10.1109/INDIN.2015.7281742

Hashan Roshantha Mendis, Leandro Soares Indrusiak, and Neil C. Audsley.Predictability and Utilisation Trade-off in the Dynamic Management of Multiple Video Stream Decoding on Network-on-Chip based Homogeneous Embedded Multi-cores. In Mathieu Jan, Belgacem Ben Hedia, Joël Goossens, and Claire Maiza, editors, 22nd International Conference on Real-Time Networks and Systems, RTNS'14, Versaille, France, October 8-10, 2014, page 161. ACM, 2014. URL: http://dx.doi.org/10.1145/2659787.2659826

Marcelo Ruaro, Guilherme A. Madalozzo, and Fernando Gehm Moraes.A hierarchical LST-based task scheduler for NoC-based MPSoCs with slack-time monitoring support. In 2015 IEEE International Conference on Electronics, Circuits, and Systems, ICECS 2015, Cairo, Egypt, December 6-9, 2015, pages 308-311. IEEE, 2015. URL: http://dx.doi.org/10.1109/ICECS.2015.7440310

M. Norazizi Sham Mohd Sayuti and Leandro Soares Indrusiak.Real-time low-power task mapping in Networks-on-Chip. In IEEE Computer Society Annual Symposium on VLSI, ISVLSI 2013, Natal, Brazil, August 5-7, 2013, pages 14-19. IEEE Computer Socity, 2013. URL: http://dx.doi.org/10.1109/ISVLSI.2013.6654616

Andreas Schranzhofer, Jian-Jia Chen, and Lothar Thiele.Dynamic Power-Aware Mapping of Applications onto Heterogeneous MPSoC Platforms.IEEE Trans. Industrial Informatics, 6(4):692-707, 2010. URL: http://dx.doi.org/10.1109/TII.2010.2062192

Zheng Shi, Alan Burns, and Leandro Soares Indrusiak.Schedulability Analysis for Real Time On-Chip Communication with Wormhole Switching.IJERTCS, 1(2):1-22, 2010. URL: http://dx.doi.org/10.4018/jertcs.2010040101

Amit Kumar Singh, Muhammad Shafique, Akash Kumar, and Jörg Henkel.Mapping on multi/many-core systems: survey of current and emerging trends. In The 50th Annual Design Automation Conference 2013, DAC'13, Austin, TX, USA, May 29 - June 07, 2013, pages 1:1-1:10. ACM, 2013. URL: http://dx.doi.org/10.1145/2463209.2488734

Amit Kumar Singh, Thambipillai Srikanthan, Akash Kumar, and Wu Jigang.Communication-aware heuristics for run-time task mapping on NoC-based MPSoC platforms. Journal of Systems Architecture - Embedded Systems Design, 56(7):242-255, 2010. URL: http://dx.doi.org/10.1016/j.sysarc.2010.04.007

Ying Tan, Parth Malani, Qinru Qiu, and Qing Wu.Workload prediction and dynamic voltage scaling for MPEG decoding. In Fumiyasu Hirose, editor, Proceedings of the 2006 Conference on Asia South Pacific Design Automation: ASP-DAC 2006, Yokohama, Japan, January 24-27, 2006, pages 911-916. IEEE, 2006. URL: http://dx.doi.org/10.1109/ASPDAC.2006.1594802

Mitchell D. Theys, Tracy D. Braun, H. J. Siegal, Anthony A. Maciejewski, and Y. K. Kwok.Mapping tasks onto distributed heterogeneous computing systems using a genetic algorithm approach. Solutions to Parallel and Distributed Computing Problems: Lessons from Biological Sciences, pages 135-178, 2001.

Wayne H. Wolf.Multimedia Applications of Multiprocessor Systems-on-Chips, pages 86-89.IEEE Computer Society, 2005. URL: http://dx.doi.org/10.1109/DATE.2005.217

DOI: http://dx.doi.org/10.4230/LITES-v004-i002-a001

URN (PDF): http://nbn-resolving.de/urn:nbn:de:0030-lites-v004-i002-a001-pdf3

Copyright (c) 2017 Hashan R. Mendis, Neil C. Audsley, and Leandro Soares Indrusiak

Creative Commons License CC BY
This work is licensed under a Creative Commons Attribution 3.0 Germany License (CC BY 3.0 DE).

License URL: http://creativecommons.org/licenses/by/3.0/de/deed.en

Published by the European Design and Automation Association (EDAA) \ EMbedded Systems Special Interest Group (EMSIG) and Schloss Dagstuhl -- Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing.