Document Open Access Logo

WCET Derivation under Single Core Equivalence with Explicit Memory Budget Assignment

Authors Renato Mancuso, Rodolfo Pellizzoni, Neriman Tokcan, Marco Caccamo

PDF

File

Thumbnail PDF
PDF
LIPIcs.ECRTS.2017.3.pdf
  • Filesize: 0.69 MB
  • 23 pages

Document Identifiers

Subject Classification

Keywords
  • real-time multicore
  • WCET
  • single-core equivalence
  • DRAM management
  • certification

Metrics

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

Abstract

In the last decade there has been a steady uptrend in the popularity of embedded multi-core platforms. This represents a turning point in the theory and implementation of real-time systems. From a real-time standpoint, however, the extensive sharing of hardware resources (e.g. caches, DRAM subsystem, I/O channels) represents a major source of unpredictability. Budget-based memory regulation (throttling) has been extensively studied to enforce a strict partitioning of the DRAM subsystem’s bandwidth. The common approach to analyze a task under memory bandwidth regulation is to consider the budget of the core where the task is executing, and assume the worst-case about the remaining cores' budgets.

In this work, we propose a novel analysis strategy to derive the WCET of a task under memory bandwidth regulation that takes into account the exact distribution of memory budgets to cores. In this sense, the proposed analysis represents a generalization of approaches that consider (i) even budget distribution across cores; and (ii) uneven but unknown (except for the core under analysis) budget assignment. By exploiting the additional piece of information, we show that it is possible to derive a more accurate WCET estimation. Our evaluations highlight that the proposed technique can reduce overestimation by 30% in average, and up to 60%, compared to the state of the art.

Cite As Get BibTex

Renato Mancuso, Rodolfo Pellizzoni, Neriman Tokcan, and Marco Caccamo. WCET Derivation under Single Core Equivalence with Explicit Memory Budget Assignment. In 29th Euromicro Conference on Real-Time Systems (ECRTS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 76, pp. 3:1-3:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ECRTS.2017.3

Author Details

Renato Mancuso
Rodolfo Pellizzoni
Neriman Tokcan
Marco Caccamo

References

  1. AbsInt. aiT worst-case execution time analyzers, 2014. URL: http://www.absint.com/ait/.
  2. B. Akesson, K. Goossens, and M. Ringhofer. Predator: A predictable SDRAM memory controller. In Proceedings of the 5th IEEE/ACM International Conference on Hardware/Software Codesign and System Synthesis, CODES+ISSS'07, pages 251-256, New York, NY, USA, 2007. ACM. URL: http://dx.doi.org/10.1145/1289816.1289877.
  3. S. Altmeyer, R. I. Davis, L. Indrusiak, C. Maiza, V. Nelis, and J. Reineke. A generic and compositional framework for multicore response time analysis. In Proceedings of the 23rd International Conference on Real Time and Networks Systems, RTNS'15, pages 129-138, New York, NY, USA, 2015. ACM. URL: http://dx.doi.org/10.1145/2834848.2834862.
  4. D. Bui, E. A. Lee, I. Liu, H. Patel, and J. Reineke. Temporal isolation on multiprocessing architectures. In Proceedings of the 48th Design Automation Conference, DAC'11, pages 274-279, New York, NY, USA, 2011. ACM. URL: http://dx.doi.org/10.1145/2024724.2024787.
  5. S. Chattopadhyay, C. L. Kee, A. Roychoudhury, T. Kelter, P. Marwedel, and H. Falk. A unified wcet analysis framework for multi-core platforms. ACM Trans. Embed. Comput. Syst., 13(4s):124:1-124:29, April 2014. URL: http://dx.doi.org/10.1145/2584654.
  6. S. Chattopadhyay, A. Roychoudhury, and T. Mitra. Modeling shared cache and bus in multi-cores for timing analysis. In Proceedings of the 13th International Workshop on Software &Compilers for Embedded Systems, SCOPES'10, pages 6:1-6:10, New York, NY, USA, 2010. ACM. URL: http://dx.doi.org/10.1145/1811212.1811220.
  7. P. Cousot. Abstract interpretation based formal methods and future challenges. In Informatics - 10 Years Back. 10 Years Ahead., volume 2000 of Lecture Notes in Computer Science, pages 138-156, London, UK, UK, 2001. Springer-Verlag. URL: http://dx.doi.org/10.1007/3-540-44577-3_10.
  8. R. I. Davis and A. Burns. Resource sharing in hierarchical fixed priority pre-emptive systems. In 2006 27th IEEE International Real-Time Systems Symposium (RTSS'06), RTSS'06, pages 257-270, Washington, DC, USA, 2006. IEEE Computer Society. URL: http://dx.doi.org/10.1109/RTSS.2006.42.
  9. S. A. Edwards and E. A. Lee. The case for the precision timed (PRET) machine. In 44th Annual Design Automation Conference, DAC'07, pages 264-265, New York, NY, USA, 2007. ACM. URL: http://dx.doi.org/10.1145/1278480.1278545.
  10. G. Gracioli and A. Fröhlich. On the influence of shared memory contention in real-time multicore applications. In Proceedings of the IV Brazilian Symposium on Computing Systems Engineering (SBESC), Washington, DC, USA, 2014. IEEE Computer Society. URL: http://dx.doi.org/10.1109/SBESC.2014.8.
  11. S. Hahn, M. Jacobs, and J. Reineke. Enabling compositionality for multicore timing analysis. In Proceedings of the 24th International Conference on Real-Time Networks and Systems, RTNS'16, pages 299-308, New York, NY, USA, 2016. ACM. URL: http://dx.doi.org/10.1145/2997465.2997471.
  12. D. Hardy, T. Piquet, and I. Puaut. Using bypass to tighten WCET estimates for multi-core processors with shared instruction caches. In Proceedings of the 2009 30th IEEE Real-Time Systems Symposium, RTSS'09, pages 68-77, Washington, DC, USA, 2009. IEEE Computer Society. URL: http://dx.doi.org/10.1109/RTSS.2009.34.
  13. B. Jacob, S. Ng, and D. Wang. Memory systems: cache, DRAM, disk. Morgan Kaufmann, 2007. Google Scholar
  14. T. Kelter, H. Falk, P. Marwedel, S. Chattopadhyay, and A. Roychoudhury. Bus-aware multicore wcet analysis through tdma offset bounds. In Real-Time Systems (ECRTS), 2011 23rd Euromicro Conference on, pages 3-12, July 2011. URL: http://dx.doi.org/10.1109/ECRTS.2011.9.
  15. H. Kim, D. de Niz, B. Andersson, M. Klein, O. Mutlu, and R. R. Rajkumar. Bounding and reducing memory interference in COTS-based multi-core systems. Real-Time Systems, 52(3):356-395, 2016. URL: http://dx.doi.org/10.1007/s11241-016-9248-1.
  16. L. Kosmidis, E. Quiñones, J. Abella, G. Farrall, F. Wartel, and F. J. Cazorla. Containing timing-related certification cost in automotive systems deploying complex hardware. In Proceedings of the 51st Annual Design Automation Conference, DAC'14, pages 22:1-22:6, New York, NY, USA, 2014. ACM. URL: http://dx.doi.org/10.1145/2593069.2593112.
  17. Y. Li, V. Suhendra, Y. Liang, T. Mitra, and A. Roychoudhury. Timing analysis of concurrent programs running on shared cache multi-cores. Real-Time Systems, 48(6):638-680, November 2012. URL: http://dx.doi.org/10.1007/s11241-012-9160-2.
  18. T. Lundqvist and P. Stenström. Timing anomalies in dynamically scheduled microprocessors. In Proceedings of the 20th IEEE Real-Time Systems Symposium, pages 12-, Washington, DC, USA, 1999. IEEE Computer Society. URL: http://dx.doi.org/10.1109/REAL.1999.818824.
  19. R. Mancuso, R. Dudko, E. Betti, M. Cesati, M. Caccamo, and R. Pellizzoni. Real-time cache management framework for multi-core architectures. In Proceedings of the IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), RTAS'13, pages 45-54, Philadelphia, PA, USA, April 2013. IEEE Computer Society. URL: http://dx.doi.org/10.1109/RTAS.2013.6531078.
  20. R. Mancuso, R. Dudko, and M. Caccamo. Light-prem: Automated software refactoring for predictable execution on cots embedded systems. In Embedded and Real-Time Computing Systems and Applications (RTCSA), 2014 IEEE 20th International Conference on, pages 1-10, Aug 2014. URL: http://dx.doi.org/10.1109/RTCSA.2014.6910515.
  21. R. Mancuso, R. Pellizzoni, M. Caccamo, L. Sha, and H. Yun. WCET(m) estimation in multi-core systems using single core equivalence. In Real-Time Systems (ECRTS), 2015 27th Euromicro Conference on, pages 174-183, July 2015. URL: http://dx.doi.org/10.1109/ECRTS.2015.23.
  22. M. Paolieri, E. Quiñones, F. J. Cazorla, G. Bernat, and M. Valero. Hardware Support for WCET Analysis of Hard Real-time Multicore Systems. SIGARCH Comput. Archit. News, 37(3):57-68, June 2009. URL: http://dx.doi.org/10.1145/1555815.1555764.
  23. R. Pellizzoni, E. Betti, S. Bak, G. Yao, J. Criswell, M. Caccamo, and R. Kegley. A predictable execution model for COTS-based embedded systems. In Proceedings of the 2011 17th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), RTAS'11, pages 269-279, Washington, DC, USA, 2011. IEEE Computer Society. URL: http://dx.doi.org/10.1109/RTAS.2011.33.
  24. R. Pellizzoni and H. Yun. Memory servers for multicore systems. In 2016 IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), pages 1-12, April 2016. Google Scholar
  25. J. Reineke, I. Liu, H. D. Patel, S. Kim, and E. A. Lee. PRET DRAM controller: bank privatization for predictability and temporal isolation. In Proceedings of the seventh IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, CODES+ISSS'11, pages 99-108, New York, NY, USA, 2011. ACM. URL: http://dx.doi.org/10.1145/2039370.2039388.
  26. J. Rosén, A. Andrei, P. Eles, and Zebo Peng. Bus access optimization for predictable implementation of real-time applications on multiprocessor Systems-on-Chip. In Proceedings of the 28th IEEE International Real-Time Systems Symposium, RTSS'07, pages 49-60. IEEE Computer Society, 2007. URL: http://dx.doi.org/10.1109/RTSS.2007.13.
  27. A. Schranzhofer, J. J. Chen, and L. Thiele. Timing analysis for tdma arbitration in resource sharing systems. In 2010 16th IEEE Real-Time and Embedded Technology and Applications Symposium, pages 215-224, April 2010. URL: http://dx.doi.org/10.1109/RTAS.2010.24.
  28. L. Sha, M. Caccamo, R. Mancuso, J. E. Kim, M. K. Yoon, R. Pellizzoni, H. Yun, R. B. Kegley, D. R. Perlman, G. Arundale, and R. Bradford. Real-time computing on multicore processors. Computer, 49(9):69-77, Sept 2016. URL: http://dx.doi.org/10.1109/MC.2016.271.
  29. I. Shin and I. Lee. Periodic resource model for compositional real-time guarantees. In RTSS 2003. 24th IEEE Real-Time Systems Symposium, 2003, pages 2-13, Dec 2003. URL: http://dx.doi.org/10.1109/REAL.2003.1253249.
  30. R. Tabish, R. Mancuso, S. Wasly, A. Alhammad, S. S. Phatak, R. Pellizzoni, and M. Caccamo. A real-time scratchpad-centric OS for multi-core embedded systems. In Real-Time and Embedded Technology and Applications Symposium (RTAS), 2016 IEEE 22th, April 2016. URL: http://dx.doi.org/10.1109/RTAS.2016.7461321.
  31. R. Tabish, R. Mancuso, S. Wasly, S. S. Phatak, R. Pellizzoni, and M. Caccamo. A reliable and predictable scratchpad-centric OS for multi-core embedded systems. In Real-Time and Embedded Technology and Applications Symposium (RTAS), 2017 IEEE 23th, April 2017. Google Scholar
  32. T. Ungerer, F. Cazorla, P. Sainrat, G. Bernat, Z. Petrov, C. Rochange, E. Quinones, M. Gerdes, M. Paolieri, J. Wolf, H. Casse, S. Uhrig, I. Guliashvili, M. Houston, F. Kluge, S. Metzlaff, and J. Mische. MERASA: Multicore execution of hard real-time applications supporting analyzability. IEEE Micro, 30(5):66-75, 2010. URL: http://dx.doi.org/10.1109/MM.2010.78.
  33. S. Wasly and R. Pellizzoni. A dynamic scratchpad memory unit for predictable real-time embedded systems. In Real-Time Systems (ECRTS), 2013 25th Euromicro Conference on, pages 183-192. IEEE, 2013. URL: http://dx.doi.org/10.1109/ECRTS.2013.28.
  34. I. Wenzel, R. Kirner, B. Rieder, and P. Puschner. Measurement-based worst-case execution time analysis. In Third IEEE Workshop on Software Technologies for Future Embedded and Ubiquitous Systems (SEUS'05), pages 7-10, May 2005. URL: http://dx.doi.org/10.1109/SEUS.2005.12.
  35. J. Yan and W. Zhang. WCET analysis for multi-core processors with shared L2 instruction caches. In Proceedings of the 2008 IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS'08, pages 80-89, Washington, DC, USA, 2008. IEEE Computer Society. URL: http://dx.doi.org/10.1109/RTAS.2008.6.
  36. G. Yao, R. Pellizzoni, S. Bak, E. Betti, and M. Caccamo. Memory-centric scheduling for multicore hard real-time systems. Real-Time Systems, 48(6):681-715, November 2012. URL: http://dx.doi.org/10.1007/s11241-012-9158-9.
  37. G. Yao, H. Yun, Z. P. Wu, R. Pellizzoni, M. Caccamo, and L. Sha. Schedulability analysis for memory bandwidth regulated multicore real-time systems. IEEE Transactions on Computers, 65(2):601-614, February 2016. URL: http://dx.doi.org/10.1109/TC.2015.2425874.
  38. H. Yun, R. Mancuso, Z.-P. Wu, and R. Pellizzoni. PALLOC: DRAM Bank-Aware Memory Allocator for Performance Isolation on Multicore Platforms. In Proceedings of the IEEE Intl. Conference on Real-Time and Embedded Technology and Applications Symposium (RTAS), Berlin, Germany, April 2014. URL: http://dx.doi.org/10.1109/RTAS.2014.6925999.
  39. H. Yun, G. Yao, R. Pellizzoni, M. Caccamo, and L. Sha. Memory access control in multiprocessor for real-time systems with mixed criticality. In Proceedings of the 2012 24th Euromicro Conference on Real-Time Systems, ECRTS'12, pages 299-308, Washington, DC, USA, 2012. IEEE Computer Society. URL: http://dx.doi.org/10.1109/ECRTS.2012.32.
  40. H. Yun, G. Yao, R. Pellizzoni, M. Caccamo, and L. Sha. MemGuard: Memory bandwidth reservation system for efficient performance isolation in multi-core platforms. In Proceedings of the 2013 IEEE 19th Real-Time and Embedded Technology and Applications Symposium (RTAS), RTAS'13, pages 55-64. IEEE Computer Society, 2013. URL: http://dx.doi.org/10.1109/RTAS.2013.6531079.
  41. H. Yun, G. Yao, R. Pellizzoni, M. Caccamo, and L. Sha. Memory bandwidth management for efficient performance isolation in multi-core platforms. IEEE Transactions on Computers, 65(2):562-576, February 2016. URL: http://dx.doi.org/10.1109/TC.2015.2425889.
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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