Predictability and Utilisation Trade-off in Video Stream Decoding Management

This study explores the trade-off between predictability and utilisation in managing multiple video stream decoding tasks on Network-on-Chip based embedded multi-cores. The objective is to make predictable admission control decisions while maintaining high system utilisation. Metrics include minimizing lateness of tasks and reducing dropped tasks, while improving processing element utilisation. The system overview, application model, and assumptions in the context of soft real-time embedded systems are discussed.

• Video Stream Decoding
• Network-on-Chip
• Embedded Systems
• Predictability
• Utilisation

ben_wal Follow

Uploaded on Sep 21, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. Predictability and Utilisation Trade-off in the Dynamic Management of Multiple Video Stream Decoding on Network-on-Chip based Homogeneous Embedded Multi-cores Hashan Roshantha Mendis (Rosh), Leandro Soares Indrusiak, Neil Audsley (Real-time Systems Group, University of York) RheonMedia 09/10/2014 RTNS 2014 - Versailles, France

2. Outline Motivation System overview Application model Platform model Task mapping Admission control tests Deterministic Heuristic based Evaluation method Results Conclusion and future work 2 09/10/2014 RTNS 2014 - Versailles, France

3. Motivation Context NoC based soft real-time embedded systems Heuristicbased admission control of multiple video stream decoding tasks. Objectives Make predictable admission control decisions of video stream decoding requests, while maintaining high system utilisation. 3 09/10/2014 RTNS 2014 - Versailles, France

4. Motivation Metrics definition Improving predictability: Minimising the maximum and mean lateness of the admitted video stream tasks Reducing the number of dropped task (due to platform global input buffer overflow) Improving utilisation: Reduce idle time of processing elements 4 09/10/2014 RTNS 2014 - Versailles, France

5. System overview 5 09/10/2014 RTNS 2014 - Versailles, France

6. System overview - Application model 6 09/10/2014 RTNS 2014 - Versailles, France

7. System overview - Application model 7 09/10/2014 RTNS 2014 - Versailles, France

8. System overview - Application model Assumptions Frame-rate = 25 fps Fixed GoP structure - each job has the same predefined dependency pattern End-to-end deadline of job (De2e) known Aperiodic tasks Fixed priority All tasks of a job arrive at the same time. Video stream start/end not known Task execution times unknown. Worst- case/average-case can be estimated 8 09/10/2014 RTNS 2014 - Versailles, France

9. System overview - Platform model Processing Elements Homogeneous Separate individual kernel instances. Same application code Fixed priority-preemptive local task scheduler Network-on-Chip 2D Mesh XY routing Fixed priority-preemptive arbitration 9 09/10/2014 RTNS 2014 - Versailles, France

10. System overview - Platform model Processing Elements Homogeneous Separate individual kernel instances. Same application code Fixed priority-preemptive local task scheduler Tasks are held until dependencies are met and PE task queue is not full. Network-on-Chip 2D Mesh XY routing Fixed priority-preemptive arbitration 10 09/10/2014 RTNS 2014 - Versailles, France

11. System overview Task mapping Semi-dynamic mapping The same task mapping pattern is used for every subsequent job in a given video stream. This job-level task to core mapping is established by the RM upon admission of a new video stream. Shortest task queue first (STQF) 11 09/10/2014 RTNS 2014 - Versailles, France

12. Admission control tests Deterministic Using classical schedulability tests Heuristic based Based on subtask-lateness 12 09/10/2014 RTNS 2014 - Versailles, France

13. Admission control tests - Deterministic ?? response time of task ?? ?? worst-case execution time of task ?? ?? period of task ?? ? ? higher priority tasks blocking ?? ?? response time of flow Msg? ??? interference jitter of flow Msg? ?? basic latency of flow Msg? ??? direct interferers of flow Msg? Schedulability analysis Worst-case response time of a task ?? [1]: ??? ?? ???+1= ??+ ?? Eq 1: ?? ? ? Worst case response time of a flow ???? [2][3]: ? ???+ ??+ ?? ?? ???+1= ??+ Eq 2: ?? ???? ??? A job is considered schedulable if the end-to-end response time of its critical path is less than or equal to the end-to-end deadline (De2e) [1] N. Audsley, A. Burns, M. Richardson, K. Tindell, and A. J. Wellings. Applying new scheduling theory to static priority pre-emptive scheduling. Software Eng. Journal, Sept. 1993 [2] Z. Shi, A. Burns, and L. S. Indrusiak. Schedulability analysis for real time on-chip communication with wormhole switching. Int. Journal of Embedded and Real-Time Comms. Systems, 2010. [3] L. S. Indrusiak. End-to-end schedulability tests for multiprocessor embedded systems based on networks-on-chip with priority-preemptive arbitration. Journal of Sys. Arch., May 2014. 13 09/10/2014 RTNS 2014 - Versailles, France

14. Admission control tests - Deterministic ?? response time of task ?? ?? worst-case execution time of task ?? ?? period of task ?? ? ? higher priority tasks blocking ?? ?? response time of flow Msg? ??? interference jitter of flow Msg? ?? basic latency of flow Msg? ??? direct interferers of flow Msg? Schedulability analysis Worst-case response time of a task ?? [1]: ??? ?? ???+1= ??+ ?? Eq 1: ?? ? ? Worst case response time of a flow ???? [2][3]: ? ???+ ??+ ?? ?? ???+1= ??+ Eq 2: ?? ???? ??? A job is considered schedulable if the end-to-end response time of its critical path is less than or equal to the end-to-end deadline (De2e) [1] N. Audsley, A. Burns, M. Richardson, K. Tindell, and A. J. Wellings. Applying new scheduling theory to static priority pre-emptive scheduling. Software Eng. Journal, Sept. 1993 [2] Z. Shi, A. Burns, and L. S. Indrusiak. Schedulability analysis for real time on-chip communication with wormhole switching. Int. Journal of Embedded and Real-Time Comms. Systems, 2010. [3] L. S. Indrusiak. End-to-end schedulability tests for multiprocessor embedded systems based on networks-on-chip with priority-preemptive arbitration. Journal of Sys. Arch., May 2014. 14 09/10/2014 RTNS 2014 - Versailles, France

15. Admission control tests - Deterministic Schedulability analysis Non-interferers We assume there is no overlap between executions and invocations of different jobs within the same video stream. Precedence constraints are taken into account when determining interfering tasks Exclusion of possible non-interferers makes analysis tighter but still safe for deterministic AC decisions. 15 09/10/2014 RTNS 2014 - Versailles, France

16. Admission control tests Heuristic based Instantaneous task lateness We assume the individual task deadline is a ratio of the overall end-to- end deadline of the job. We make admission decisions based on the instantaneous lateness of the tasks (??) in the Global input buffers and the PE task queues. ????????????? = ?? ?? ??2? ??? Eq 3: ??????????? = ?? ?? ??2? ??? Eq 4: ?? current time ?? task dispatch time ??? 0 ??? 1}, ??? 0 ??? 1} If any of the tasks in the global input buffers or the PE task queues are late, then the new video stream admission request is rejected. 16 09/10/2014 RTNS 2014 - Versailles, France

17. Admission control tests Heuristic based Instantaneous task lateness Previous work of determining the subtask deadline - by Kao and Garcia-Molina [4]; termed DeadlineEqual flexibility scheme (D-EQF) Total remaining slack is divided among the subtasks in proportion to their estimated execution times (WCET). [4] B. Kao and H. Garcia-Molina. Deadline assignment in a distributed soft real-time system. IEEE Trans. on Parallel and Distributed Systems, Dec. 1997 17 09/10/2014 RTNS 2014 - Versailles, France

18. Admission control tests buffer overflow Free space in buffers and task queues If global input buffers or task queues do not have sufficient space, taskset will be dropped without receiving Hence buffer overflow is also a cause for rejecting new video streams. 18 09/10/2014 RTNS 2014 - Versailles, France

19. Evaluation method Admission control (AC) tests compared : Baselines : No AC test, Deterministic AC, Heuristic based (0.1 (IBL , TQL ) 1.0) Measurements: Number of video streams admitted/rejected/admitted but deadlines missed Job lateness Overall average PE busy time High and Low workloads Abstract system-level simulation with lightweight NoC simulation component [5]. 35 simulation runs [5] L. S. Indrusiak and O. M. dos Santos. Fast and accurate transaction-level model of a wormhole network-on-chip with priority preemptive virtual channel arbitration. In DATE 2011, IEEE, 2011. 19 09/10/2014 RTNS 2014 - Versailles, France

20. Experiment results Video stream admission summary As the Heuristic ratios increase, the number of admitted video streams increase; however at the cost of, increased late streams and many jobs being dropped. Heu (D-EQF) offers best predictability guarantees : no late streams, higher admission rate than Deterministic AC-test. 20 09/10/2014 RTNS 2014 - Versailles, France

21. Experiment results Completed job (i.e. GoP) lateness As the Heuristic ratios increase, the distribution, mean and maximum job lateness increases. No-AC test shows very high job lateness levels. 21 09/10/2014 RTNS 2014 - Versailles, France

22. Experiment results Percentage system busy time (system utilisation) As the Heuristic ratios increase, the average system utilisation levels increase more admitted video streams. Very low utilisation levels when deterministic AC test is used. 22 09/10/2014 RTNS 2014 - Versailles, France

23. Experiment results - summary Heuristic based AC tests (IBL , TQL ) Higher value of IBL combined with a mid/high value of TQL provides best trade-off 23 09/10/2014 RTNS 2014 - Versailles, France

24. Conclusion and future work Application specific task model Heuristic based admission control approach. Subtask lateness evaluated as a ratio of the end-to-end deadline of the overall taskset. Improvedutilisation over the deterministic AC test and better predictability guarantees than when No-AC is used. The IBL and TQL thresholds can be chosen depending on the specific requirements . Future work : explore better dynamic/semi-dynamic mapping approaches, compare other ACs 24 09/10/2014 RTNS 2014 - Versailles, France

25. Thank You ! Questions ? 25 09/10/2014 RTNS 2014 - Versailles, France

26. EXTRA SLIDES 26 09/10/2014 RTNS 2014 - Versailles, France

27. Evaluation method Simulation experiment parameters Number of workflows High (=16), Low(=8) Heuristic ratios (combinations) 0.1 (IBL , TQL ) 1.0 35 Simulation runs Number of PEs 9 (3x3) PE task queue size 10 Dependency buff size 10 Global input buffer size 12 NoC frequency 1000MHz Videos per workflow (min/max) (6,7) GoPs per video stream (min/max) (7,8) 27 09/10/2014 RTNS 2014 - Versailles, France

28. Admission control tests - Deterministic Example task and flow timeline 28 09/10/2014 RTNS 2014 - Versailles, France

29. Admission control tests Heuristic based Instantaneous task lateness Previous work of determining the subtask deadline (di) by Kao and Garcia-Molina [4]; termed Equal flexibility scheme (EQF) ? ?? ??= ??+ ??+ ??2? ?? ?? Eq 5: ??? ?=1 ?=1 ?: number of tasks in the taskset ??: absolute deadline of subtask Total remaining slack is divided among the subtasks in proportion to their estimated execution times (WCET). [4] B. Kao and H. Garcia-Molina. Deadline assignment in a distributed soft real-time system. IEEE Trans. on Parallel and Distributed Systems, Dec. 1997 29 09/10/2014 RTNS 2014 - Versailles, France