Document Open Access Logo

PAStime: Progress-Aware Scheduling for Time-Critical Computing

Authors Soham Sinha , Richard West , Ahmad Golchin

PDF
Thumbnail PDF

File

LIPIcs.ECRTS.2020.3.pdf
  • Filesize: 0.8 MB
  • 24 pages

Document Identifiers

Author Details

Soham Sinha
  • Department of Computer Science, Boston University, MA, USA
Richard West
  • Department of Computer Science, Boston University, MA, USA
Ahmad Golchin
  • Department of Computer Science, Boston University, MA, USA

Funding

This work is supported in part by the National Science Foundation (NSF) under Grant #1527050.

Acknowledgements

Special thanks to Dr. Ramesh Peri and Intel for generous support and feedback. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the NSF.

Cite As Get BibTex

Soham Sinha, Richard West, and Ahmad Golchin. PAStime: Progress-Aware Scheduling for Time-Critical Computing. In 32nd Euromicro Conference on Real-Time Systems (ECRTS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 165, pp. 3:1-3:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ECRTS.2020.3

Abstract

Over-estimation of worst-case execution times (WCETs) of real-time tasks leads to poor resource utilization. In a mixed-criticality system (MCS), the over-provisioning of CPU time to accommodate the WCETs of highly critical tasks may lead to degraded service for less critical tasks. In this paper we present PAStime, a novel approach to monitor and adapt the runtime progress of highly time-critical applications, to allow for improved service to lower criticality tasks. In PAStime, CPU time is allocated to time-critical tasks according to the delays they experience as they progress through their control flow graphs. This ensures that as much time as possible is made available to improve the Quality-of-Service of less critical tasks, while high-criticality tasks are compensated after their delays.
This paper describes the integration of PAStime with Adaptive Mixed-criticality (AMC) scheduling. The LO-mode budget of a high-criticality task is adjusted according to the delay observed at execution checkpoints. This is the first implementation of AMC in the scheduling framework of LITMUS^RT, which is extended with our PAStime runtime policy and tested with real-time Linux applications such as object classification and detection. We observe in our experimental evaluation that AMC-PAStime significantly improves the utilization of the low-criticality tasks while guaranteeing service to high-criticality tasks.

Subject Classification

ACM Subject Classification
  • Computer systems organization → Real-time systems
  • Software and its engineering → Real-time systems software
Keywords
  • progress-aware scheduling
  • code instrumentation
  • timing annotation

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Jayvant Anantpur and R Govindarajan. PRO: Progress-aware GPU Warp Scheduling Algorithm. In Proceedings of the IEEE International Parallel and Distributed Processing Symposium (IPDPS), pages 979-988, 2015. Google Scholar
  2. Neil C Audsley. On Priority Assignment in Fixed Priority Scheduling. Information Processing Letters, 79(1):39-44, 2001. Google Scholar
  3. Sanjoy Baruah and Alan Burns. Fixed-priority Scheduling of Dual-criticality Systems. In Proceedings of the 21st International conference on Real-Time Networks and Systems, pages 173-181. ACM, 2013. Google Scholar
  4. Sanjoy Baruah, Alan Burns, and Zhishan Guo. Scheduling Mixed-criticality Systems to Guarantee Some Service under All Non-erroneous Behaviors. In 2016 28th Euromicro Conference on Real-Time Systems (ECRTS), pages 131-138. IEEE, 2016. Google Scholar
  5. Sanjoy Baruah, Haohan Li, and Leen Stougie. Towards the Design of Certifiable Mixed-criticality Systems. In Proceedings of the 16th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), pages 13-22, 2010. Google Scholar
  6. Sanjoy Baruah and Steve Vestal. Schedulability Analysis of Sporadic Tasks with Multiple Criticality Specifications. In Proceedings of the Euromicro Conference on Real-Time Systems (ECRTS), pages 147-155, 2008. Google Scholar
  7. Sanjoy K Baruah, Alan Burns, and Robert I Davis. Response-time Analysis for Mixed Criticality Systems. In Proceedings of the 32nd IEEE Real-Time Systems Symposium (RTSS), pages 34-43, 2011. Google Scholar
  8. Big Buck Bunny. https://www.bigbuckbunny.org, 2018. URL: https://www.bigbuckbunny.org.
  9. Enrico Bini and Giorgio C Buttazzo. Measuring the Performance of Schedulability Tests. Real-Time Systems, 30(1-2):129-154, 2005. Google Scholar
  10. Björn Brandenburg and James H Anderson. Scheduling and Locking in Multiprocessor Real-time Operating Systems. PhD thesis, PhD thesis, The University of North Carolina at Chapel Hill, 2011. Google Scholar
  11. Alan Burns and Sanjoy Baruah. Towards a more practical model for mixed criticality systems. In Workshop on Mixed-Criticality Systems (colocated with RTSS), 2013. Google Scholar
  12. Alan Burns and Robert I. Davis. A Survey of Research into Mixed Criticality Systems. ACM Comput. Surv., 50(6):82:1-82:37, November 2017. URL: https://doi.org/10.1145/3131347.
  13. Kevin Burr and William Young. Combinatorial Test Techniques: Table-based Automation, Test Generation and Code Coverage. In Proceedings of the International Conference on Software Testing Analysis & Review, 1998. Google Scholar
  14. John M Calandrino, Hennadiy Leontyev, Aaron Block, UmaMaheswari C Devi, and James H Anderson. LITMUSsuperscriptRT: A Testbed for Empirically Comparing Real-time Multiprocessor Schedulers. In 2006 27th IEEE International Real-Time Systems Symposium (RTSS'06), pages 111-126. IEEE, 2006. Google Scholar
  15. Dionisio De Niz, Karthik Lakshmanan, and Ragunathan Rajkumar. On the Scheduling of Mixed-criticality Real-time Task Sets. In Proceedings of the 30th IEEE Real-Time Systems Symposium (RTSS), pages 291-300, 2009. Google Scholar
  16. dlib C++ Library. dlib: Video Tracking. http://dlib.net/video_tracking_ex.cpp.html, 2019. URL: http://dlib.net/video_tracking_ex.cpp.html.
  17. Stijn Eyerman and Lieven Eeckhout. Per-thread Cycle Accounting in SMT Processors. ACM Sigplan Notices, 44(3):133-144, 2009. Google Scholar
  18. Josue Feliu, Julio Sahuquillo, Salvador Petit, and José Duato. Addressing Fairness in SMT Multicores with a Progress-aware Scheduler. In Proceedings of the IEEE International Parallel and Distributed Processing Symposium (IPDPS), pages 187-196, 2015. Google Scholar
  19. Feliu, Josue and Sahuquillo, Julio and Petit, Salvador and Duato, Jose. Perf&Fair: A Progress-aware Scheduler to Enhance Performance and Fairness in SMT Multicores. IEEE Transactions on Computers, 66(5):905-911, 2017. Google Scholar
  20. FFmpeg Multimedia Framework. https://www.ffmpeg.org/, 2019. URL: https://www.ffmpeg.org/.
  21. Chris Gill, James Orr, and Steven Harris. Supporting Graceful Degradation through Elasticity in Mixed-Criticality Federated Scheduling. In Proc. 6th Workshop on Mixed Criticality Systems (WMC), RTSS, pages 19-24, 2018. Google Scholar
  22. Google. trucov. https://code.google.com/archive/p/trucov/, 2018. URL: https://code.google.com/archive/p/trucov/.
  23. Huang-Ming Huang, Christopher Gill, and Chenyang Lu. Implementation and Evaluation of Mixed-criticality Scheduling Approaches for Sporadic Tasks. ACM Transactions on Embedded Computing Systems (TECS), 13(4s):126, 2014. Google Scholar
  24. Intel. Intelregistered NUC Kit NUC6i7KYK (Skull Canyon): Features and Configurations. https://www.intel.com/content/www/us/en/products/docs/boards-kits/nuc/nuc-kit-nuc6i7kyk-features-configurations.html, 2019. URL: https://www.intel.com/content/www/us/en/products/docs/boards-kits/nuc/nuc-kit-nuc6i7kyk-features-configurations.html.
  25. Min Kyu Jeong, Mattan Erez, Chander Sudanthi, and Nigel Paver. A QoS-aware Memory Controller for Dynamically Balancing GPU and CPU Bandwidth Use in an MPSoC. In Proceedings of the 49th annual Design Automation Conference, pages 850-855. ACM, 2012. Google Scholar
  26. Angeliki Kritikakou, Olivier Baldellon, Claire Pagetti, Christine Rochange, and Matthieu Roy. Run-time Control to Increase Task Parallelism in Mixed-critical Systems. In Proceedings of the 26th Euromicro Conference on Real-Time Systems (ECRTS), 2014. Google Scholar
  27. Angeliki Kritikakou, Thibaut Marty, and Matthieu Roy. DYNASCORE: DYNAmic Software COntroller to increase REsource Utilization in Mixed-critical Systems. ACM Transactions on Design Automation of Electronic Systems (TODAES), 23(2), 2017. Google Scholar
  28. Angeliki Kritikakou, Christine Rochange, Madeleine Faugère, Claire Pagetti, Matthieu Roy, Sylvain Girbal, and Daniel Gracia Pérez. Distributed Run-time WCET Controller for Concurrent Critical Tasks in Mixed-critical Systems. In Proceedings of the 22nd International Conference on Real-Time Networks and Systems. ACM, 2014. Google Scholar
  29. Chris Lattner and Vikram Adve. LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation. In Proceedings of the International Symposium on Code Generation and Optimization: Feedback-directed and Runtime Optimization, page 75. IEEE Computer Society, 2004. Google Scholar
  30. Juri Lelli, Giuseppe Lipari, Dario Faggioli, and Tommaso Cucinotta. An Efficient and Scalable Implementation of Global EDF in Linux. In Proceedings of the 7th International Workshop on Operating Systems Platforms for Embedded Real-Time Applications (OSPERT), pages 6-15, 2011. Google Scholar
  31. Juri Lelli, Claudio Scordino, Luca Abeni, and Dario Faggioli. Deadline Scheduling in the Linux kernel. Software: Practice and Experience, 46(6):821-839, 2016. Google Scholar
  32. Tsung-Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C Lawrence Zitnick. Microsoft COCO: Common Objects in Context. In Proceedings of the European Conference on Computer Vision, pages 740-755. Springer, 2014. Google Scholar
  33. Linux. hrtimers - Subsystem for High-resolution Kernel Timers. https://www.kernel.org/doc/Documentation/timers/hrtimers.txt, Last Accessed: May 2019. URL: https://www.kernel.org/doc/Documentation/timers/hrtimers.txt.
  34. Linux. SCHED_DEADLINE Scheduling Policy. https://www.kernel.org/doc/Documentation/scheduler/sched-deadline.txt, Last Accessed: May 2019. URL: https://www.kernel.org/doc/Documentation/scheduler/sched-deadline.txt.
  35. Di Liu, Nan Guan, Jelena Spasic, Gang Chen, Songran Liu, Todor Stefanov, and Wang Yi. Scheduling analysis of imprecise mixed-criticality real-time tasks. IEEE Transactions on Computers, 67(7):975-991, 2018. Google Scholar
  36. Di Liu, Jelena Spasic, Nan Guan, Gang Chen, Songran Liu, Todor Stefanov, and Wang Yi. Edf-vd scheduling of mixed-criticality systems with degraded quality guarantees. In 2016 IEEE Real-Time Systems Symposium (RTSS), pages 35-46. IEEE, 2016. Google Scholar
  37. LLVM LoopInfo Class. https://llvm.org/doxygen/LoopInfo_8h_source.html, Last Accessed: May 2019. URL: https://llvm.org/doxygen/LoopInfo_8h_source.html.
  38. Renato Mancuso, Roman Dudko, and Marco Caccamo. Light-PREM: Automated Software Refactoring for Predictable Execution on COTS Embedded Systems. In 2014 IEEE 20th International Conference on Embedded and Real-Time Computing Systems and Applications, pages 1-10. IEEE, 2014. Google Scholar
  39. Eric Missimer, Katherine Missimer, and Richard West. Mixed-criticality scheduling with i/o. In 2016 28th Euromicro Conference on Real-Time Systems (ECRTS), pages 120-130. IEEE, 2016. Google Scholar
  40. Alessandro Papadopoulos, Enrico Bini, Sanjoy Baruah, and Alan Burns. AdaptMC: A control-theoretic approach for achieving resilience in mixed-criticality systems. In Proceeding ECRTS Conference, page 14. LIPICS, 2018. Google Scholar
  41. PAStime. Source Code, 2020. URL: http://cs-people.bu.edu/soham1/pastime/.
  42. Rodolfo Pellizzoni, Emiliano Betti, Stanley Bak, Gang Yao, John Criswell, Marco Caccamo, and Russell Kegley. A Predictable Execution Model for COTS-based Embedded Systems. In 2011 17th IEEE Real-Time and Embedded Technology and Applications Symposium, pages 269-279. IEEE, 2011. Google Scholar
  43. Saravanan Ramanathan, Arvind Easwaran, and Hyeonjoong Cho. Multi-rate Fluid Scheduling of Mixed-criticality Systems on Multiprocessors. Real-Time Systems, 54(2):247-277, 2018. Google Scholar
  44. Joseph Redmon. Darknet: Open Source Neural Networks in C. http://pjreddie.com/darknet/, 2013-2016. URL: http://pjreddie.com/darknet/.
  45. Francois Santy, Laurent George, Philippe Thierry, and Joël Goossens. Relaxing mixed-criticality scheduling strictness for task sets scheduled with fp. In 2012 24th Euromicro Conference on Real-Time Systems, pages 155-165. IEEE, 2012. Google Scholar
  46. Hang Su, Peng Deng, Dakai Zhu, and Qi Zhu. Fixed-priority Dual-rate Mixed-criticality Systems: Schedulability Analysis and Performance Optimization. In 2016 IEEE 22nd International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA), pages 59-68. IEEE, 2016. Google Scholar
  47. Hang Su, Nan Guan, and Dakai Zhu. Service guarantee exploration for mixed-criticality systems. In 2014 IEEE 20th International Conference on Embedded and Real-Time Computing Systems and Applications, pages 1-10. IEEE, 2014. Google Scholar
  48. Hang Su and Dakai Zhu. An Elastic Mixed-criticality Task Model and its Scheduling Algorithm. In Design, Automation & Test in Europe Conference & Exhibition (DATE), pages 147-152. IEEE, 2013. Google Scholar
  49. Hang Su, Dakai Zhu, and Scott Brandt. An Elastic Mixed-Criticality Task Model and Early-Release EDF Scheduling Algorithms. ACM Transactions on Design Automation of Electronic Systems (TODAES), 22(2):28, 2017. Google Scholar
  50. Mustafa M Tikir and Jeffrey K Hollingsworth. Efficient Instrumentation for Code Coverage Testing. In ACM SIGSOFT Software Engineering Notes, volume 27, pages 86-96. ACM, 2002. Google Scholar
  51. Manohar Vanga, Andrea Bastoni, Henrik Theiling, and Björn B Brandenburg. Supporting Low-Latency, Low-Criticality Tasks in A Certified Mixed-Criticality OS. In Proceedings of the 25th International Conference on Real-Time Networks and Systems, pages 227-236. ACM, 2017. Google Scholar
  52. Steve Vestal. Preemptive Scheduling of Multi-criticality Systems with Varying Degrees of Execution Time Assurance. In Proceedings of the 28th IEEE Real-Time Systems Symposium (RTSS), pages 239-243, 2007. Google Scholar
  53. Richard West, Puneet Zaroo, Carl A Waldspurger, and Xiao Zhang. Online Cache Modeling for Commodity Multicore Processors. ACM SIGOPS Operating Systems Review, 44(4):19-29, 2010. Google Scholar
  54. Reinhard Wilhelm, Jakob Engblom, Andreas Ermedahl, Niklas Holsti, Stephan Thesing, David Whalley, Guillem Bernat, Christian Ferdinand, Reinhold Heckmann, Tulika Mitra, et al. The Worst-case Execution-time Problem - Overview of Methods and Survey of Tools. ACM Transactions on Embedded Computing Systems, 7(3):36, 2008. Google Scholar
  55. Ying Ye, Richard West, Zhuoqun Cheng, and Ye Li. COLORIS: A Dynamic Cache Partitioning System using Page Coloring. In 2014 23rd International Conference on Parallel Architecture and Compilation Techniques (PACT), pages 381-392. IEEE, 2014 . Google Scholar
  56. Heechul Yun, Renato Mancuso, Zheng-Pei Wu, and Rodolfo Pellizzoni. PALLOC: DRAM Bank-aware Memory Allocator for Performance Isolation on Multicore Platforms. In 2014 IEEE 19th Real-Time and Embedded Technology and Applications Symposium (RTAS), pages 155-166. IEEE, 2014. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact