More Web Proxy on the site http://driver.im/

survey

A Survey of Timing Verification Techniques for Multi-Core Real-Time Systems

Authors:

Joël Goossens,

Sebastian Altmeyer,

Robert I. DavisAuthors Info & Claims

ACM Computing Surveys (CSUR), Volume 52, Issue 3

Article No.: 56, Pages 1 - 38

https://doi.org/10.1145/3323212

Published: 18 June 2019 Publication History

Abstract

This survey provides an overview of the scientific literature on timing verification techniques for multi-core real-time systems. It reviews the key results in the field from its origins around 2006 to the latest research published up to the end of 2018. The survey highlights the key issues involved in providing guarantees of timing correctness for multi-core systems. A detailed review is provided covering four main categories: full integration, temporal isolation, integrating interference effects into schedulability analysis, and mapping and allocation. The survey concludes with a discussion of the advantages and disadvantages of these different approaches, identifying open issues, key challenges, and possible directions for future research.

Supplementary Material

a56-maiza-suppl.pdf (maiza.zip)

Supplemental movie, appendix, image and software files for, A Survey of Timing Verification Techniques for Multi-Core Real-Time Systems

Download
686.07 KB

References

[1]

A. Agrawal, G. Fohler, J. Freitag, J. Nowotsch, S. Uhrig, and M. Paulitsch. 2017. Contention-aware dynamic memory bandwidth isolation with predictability in cots multicores: An avionics case study. Proceedings of the Euromicro Conference on Real-Time Systems (ECRTS)2 (2017), 1--2.

[2]

A. Agrawal, R. Mancuso, R. Pellizzoni, and G. Fohler. 2018. Analysis of dynamic memory bandwidth regulation in multi-core real-time systems. In Proceedings of the IEEE Real-Time Systems Symposium (RTSS). 230--241.

[3]

A. Alhammad and R. Pellizzoni. 2014. Schedulability analysis of global memory-predictable scheduling. In Proceedings of the IEEE 8 ACM International Conference on Embedded Software (EMSOFT’14). 1--10.

[4]

A. Alhammad and R. Pellizzoni. 2014. Time-predictable execution of multithreaded applications on multicore systems. In Proceedings of the Conference on Design, Automation and Test in Europe (DATE’14). 1--6.

Digital Library

[5]

A. Alhammad, S. Wasly, and R. Pellizzoni. 2015. Memory efficient global scheduling of real-time tasks. In Proceedings of the IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS’15). 285--296.

[6]

S. Altmeyer, R. I. Davis, L. Indrusiak, C. Maiza, V. Nelis, and J. Reineke. 2015. A generic and compositional framework for multicore response time analysis. In Proceedings of the International Conference on Real-Time Networks and Systems (RTNS’15). 129--138.

[7]

J. H. Anderson, J. M. Calandrino, and U. C. Devi. 2006. Real-time scheduling on multicore platforms. In Proceedings of the IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS’06). 179--190.

Digital Library

[8]

B. Andersson, A. Easwaran, and J. Lee. 2010. Finding an upper bound on the increase in execution time due to contention on the memory bus in COTS-based multicore systems. SIGBED Rev. 7, 1 (Jan. 2010), Article 4, 4 pages.

Digital Library

[9]

B. Andersson, H. Kim, D. de Niz, M. Klein, R. Rajkumar, and J. Lehoczky. 2018. Schedulability analysis of tasks with corunner-dependent execution times. ACM Transactions on Embedded Computing Systems 17, 3 (2018), 71:1--71:29.

Digital Library

[10]

A. Andrei, P. Eles, Z. Peng, and J. Rosen. 2008. Predictable implementation of real-time applications on multiprocessor systems-on-chip. In 21st International Conference on VLSI Design (VLSID 2008). 103--110.

Digital Library

[11]

M. A. Awan, P. F. Souto, K. Bletsas, B. Akesson, and E. Tovar. 2018. Mixed-criticality scheduling with memory bandwidth regulation. In Proceedings of the Conference on Design, Automation and Test in Europe (DATE’18).

[12]

M. A. Awan, P. F. Souto, K. Bletsas, B. Akesson, and E. Tovar. 2018. Worst-case stall analysis for multicore architectures with two memory controllers. In Proceedings of the Euromicro Conference on Real-Time Systems (ECRTS’18). 2:1--2:22.

[13]

M. A. Awan, P. F. Souto, B. Akesson, K. Bletsas, and E. Tovar. 2018. Uneven memory regulation for scheduling IMA applications on multi-core platforms. Real-Time Systems (Nov. 2018).

Digital Library

[14]

S. Bak, G. Yao, R. Pellizzoni, and M. Caccamo. 2012. Memory-aware scheduling of multicore task sets for real-time systems. In Proceedings of the IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA’12). 300--309.

Digital Library

[15]

M. Becker, D. Dasari, B. Nicolic, B. Åkesson, V. Nélis, and T. Nolte. 2016. Contention-free execution of automotive applications on a clustered many-core platform. In Proceedings of the Euromicro Conference on Real-Time Systems (ECRTS’16). 14--24.

[16]

M. Behnam, R. Inam, T. Nolte, and M. Sjödin. 2013. Multi-core composability in the face of memory-bus contention. SIGBED Rev. 10, 3 (Oct. 2013), 35--42.

Digital Library

[17]

F. Boniol, H. Cassé, E. Noulard, and C. Pagetti. 2012. Deterministic execution model on COTS hardware. In Architecture of Computing Systems -- ARCS 2012. 98--110.

Digital Library

[18]

T. Carle and H. Cassé. 2018. Reducing timing interferences in real-time applications running on multicore architectures. In Proceedings of the Workshop on Worst-Case Execution Time Analysis (WCET’18), Vol. 63. 3:1--3:12.

[19]

T. Carle, D. Potop-Butucaru, Y. Sorel, and D. Lesens. 2015. From dataflow specification to multiprocessor partitioned time-triggered real-time implementation. Leibniz Transactions on Embedded Systems (LITES) 2, 2 (2015), 01:1--01:30.

[20]

Certification Authorities Software Team (CAST). 2016. Position Paper CAST-32A Multi-core Processors. Technical Report.

[21]

C. W. Chang, J. J. Chen, T. W. Kuo, and H. Falk. 2015. Real-time task scheduling on island-based multi-core platforms. IEEE Transactions on Parallel and Distributed Systems 26, 2 (Feb. 2015), 538--550.

Digital Library

[22]

C. W. Chang, J. J. Chen, W. Munawar, T. W. Kuo, and H. Falk. 2012. Partitioned scheduling for real-time tasks on multiprocessor embedded systems with programmable shared srams. In Proceedings of the T10th ACM International Conference on Embedded Software. ACM, 153--162.

[23]

S. Chattopadhyay, L. K. Chong, A. Roychoudhury, T. Kelter, P. Marwedel, and H. Falk. 2014. A unified WCET analysis framework for multicore platforms. ACM Transactions on Embedded Computing Systems (TECS) 13, 4s (2014), 124.

Digital Library

[24]

S. Chattopadhyay, C. L. Kee, A. Roychoudhury, T. Kelter, P. Marwedel, and H. Falk. 2012. A unified WCET analysis framework for multi-core platforms. In Proceedings of the IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS’12). 99--108.

Digital Library

[25]

S. Chattopadhyay and A. Roychoudhury. 2011. Static bus schedule aware scratchpad allocation in multiprocessors. SIGPLAN Not. 46, 5 (April 2011), 11--20.

Digital Library

[26]

S. Chattopadhyay, A. Roychoudhury, and T. Mitra. 2010. Modeling shared cache and bus in multi-cores for timing analysis. In Proceedings of the 13th International Workshop on Software and Compilers for Embedded Systems (SCOPES’10). ACM, 6:1--6:10.

[27]

S. W. Cheng, J. J. Chen, J. Reineke, and T. W. Kuo. 2017. Memory bank partitioning for fixed-priority tasks in a multi-core system. In Proceedings of the IEEE Real-Time Systems Symposium (RTSS’17). 209--219.

[28]

S. W. Cheng, C. W. Chang, J. J. Chen, T. W. Kuo, and P. C. Hsiu. 2016. Many-core real-time task scheduling with scratchpad memory. IEEE Transactions on Parallel and Distributed Systems 27, 10 (Oct. 2016), 2953--2966.

Digital Library

[29]

M. Chisholm, N. Kim, B. C. Ward, N. Otterness, J. H. Anderson, and F. D. Smith. 2016. Reconciling the tension between hardware isolation and data sharing in mixed-criticality, multicore systems. In Proceedings of the IEEE Real-Time Systems Symposium (RTSS’16). IEEE, 57--68.

[30]

M. Chisholm, B. C. Ward, N. Kim, and J. H. Anderson. 2015. Cache sharing and isolation tradeoffs in multicore mixed-criticality systems. In Proceedings of the IEEE Real-Time Systems Symposium (RTSS’15). 305--316.

Digital Library

[31]

J. Choi, D. Kang, and S. Ha. 2016. Conservative modeling of shared resource contention for dependent tasks in partitioned multi-core systems. In Proceedings of the Conference on Design, Automation and Test in Europe (DATE’16). 181--186.

[32]

D. Dasari, B. Akesson, V. Nelis, M. A. Awan, and S. M. Petters. 2013. Identifying the sources of unpredictability in COTS-based multicore systems. In Proceedings of the IEEE International Symposium on Industrial Embedded Systems (SIES’13). 39--48.

[33]

D. Dasari, B. Andersson, V. Nelis, S. M. Petters, A. Easwaran, and J. Lee. 2011. Response time analysis of COTS-based multicores considering the contention on the shared memory bus. In International Conference on Trust, Security and Privacy in Computing and Communications. 1068--1075.

Digital Library

[34]

D. Dasari and V. Nelis. 2012. An analysis of the impact of bus contention on the WCET in multicores. In Proceedings of the IEEE International Conference on High Performance Computing and Communication. IEEE Computer Society, Washington, DC, 1450--1457.

Digital Library

[35]

D. Dasari, V. Nelis, and B. Akesson. 2015. A framework for memory contention analysis in multi-core platforms. Real-Time Systems (2015), 1--51.

[36]

D. Dasari, V. Nelis, and Benny Akesson. 2016. A framework for memory contention analysis in multi-core platforms. Real-Time Systems 52, 3 (May 2016), 272--322.

Digital Library

[37]

R. I. Davis, S. Altmeyer, L. S. Indrusiak, C. Maiza, V. Nelis, and J. Reineke. 2017. An extensible framework for multicore response time analysis. Real-Time Systems 54, 3 (2017), 607--661.

Digital Library

[38]

R. I. Davis and A. Burns. 2011. A survey of hard real-time scheduling for multiprocessor systems. ACM Computing Surveys 43, 4 (Oct. 2011), Article 35, 44 pages.

Digital Library

[39]

H. Ding, Y. Liang, and T. Mitra. 2013. Shared cache aware task mapping for WCRT minimization. In Proceedings of the 2013 18th Asia and South Pacific Design Automation Conference (ASP-DAC’13). 735--740.

[40]

F. Farshchi, P. K. Valsan, R. Mancuso, and H. Yun. 2018. Deterministic memory abstraction and supporting multicore system architecture. In Proceedings of the Euromicro Conference on Real-Time Systems (ECRTS’18). 1:1--1:25.

[41]

J. Freitag, S. Uhrig, and T. Ungerer. 2018. Virtual timing isolation for mixed-criticality systems. In Proceedings of the Euromicro Conference on Real-Time Systems (ECRTS’18), Vol. 106. 13:1--13:23.

[42]

G. Giannopoulou, K. Lampka, N. Stoimenov, and L. Thiele. 2012. Timed model checking with abstractions: Towards worst-case response time analysis in resource-sharing manycore systems. In Proceedings of the 10th ACM International Conference on Embedded Software. ACM, 63--72.

[43]

G. Giannopoulou, N. Stoimenov, P. Huang, and L. Thiele. 2013. Scheduling of mixed-criticality applications on resource-sharing multicore systems. In Proceedings of the IEEE 8 ACM International Conference on Embedded Software (EMSOFT’13). 1--15.

Digital Library

[44]

G. Giannopoulou, N. Stoimenov, P. Huang, and L. Thiele. 2014. Mapping mixed-criticality applications on multi-core architectures. In Proceedings of the Conference on Design, Automation and Test in Europe (DATE’14). 1--6.

Digital Library

[45]

G. Giannopoulou, N. Stoimenov, P. Huang, L. Thiele, and B. D. de Dinechin. 2016. Mixed-criticality scheduling on cluster-based manycores with shared communication and storage resources. Real-Time Systems 52, 4 (2016), 399--449.

Digital Library

[46]

G. Gracioli, A. Alhammad, R. Mancuso, A. A. Fröhlich, and R. Pellizzoni. 2015. A survey on cache management mechanisms for real-time embedded systems. ACM Computing Surveys 48, 2 (Nov. 2015), Article 32, 36 pages.

Digital Library

[47]

G. Gracioli and A. A. Fröhlich. 2014. On the influence of shared memory contention in real-time multicore applications. In Brazilian Symposium on Computing Systems Engineering. 25--30.

Digital Library

[48]

N. Guan, M. Stigge, W. Yi, and G. Yu. 2009. Cache-aware scheduling and analysis for multicores. In Proceedings of the IEEE 8 ACM International Conference on Embedded Software (EMSOFT’09). 245--254.

[49]

D. Guo, M. Hassan, R. Pellizzoni, and H. Patel. 2018. A comparative study of predictable DRAM controllers. ACM Transactions on Embedded Computing Systems 17, 2 (Feb. 2018), Article 53, 23 pages.

Digital Library

[50]

Z. Guo, Y. Zhang, L. Wang, and Z. Zhang. 2017. Work-in-progress: Cache-aware partitioned EDF scheduling for multi-core real-time systems. In Proceedings of the IEEE Real-Time Systems Symposium (RTSS’17). 384--386.

[51]

A. Gustavsson, A. Ermedahl, B. Lisper, and P. Pettersson. 2010. Towards WCET analysis of multicore architectures using UPPAAL. In Proceedings of the Workshop on Worst-Case Execution Time Analysis (WCET’10). 101--112.

[52]

S. Hahn, M. Jacobs, and J. Reineke. 2016. Enabling compositionality for multicore timing analysis. In Proceedings of the International Conference on Real-Time Networks and Systems (RTNS’16). 299--308.

[53]

S. Hahn, J. Reineke, and R. Wilhelm. 2013. Towards compositionality in execution time analysis -- Definition and challenges. In Proceedings of the Workshop on Compositional Theory and Technology for Real-Time Embedded Systems (CRTS’13).

[54]

D. Hardy, T. Piquet, and I. Puaut. 2009. Using bypass to tighten WCET estimates for multi-core processors with shared instruction caches. In Proceedings of the IEEE Real-Time Systems Symposium (RTSS’09). 68--77.

[55]

M. Hassan. 2018. On the off-chip memory latency of real-time systems: Is DDR DRAM really the best option? In Proceedings of the IEEE Real-Time Systems Symposium (RTSS’18). 495--505.

[56]

M. Hassan, A. M. Kaushik, and H. Patel. 2017. Predictable cache coherence for multi-core real-time systems. In Proceedings of the IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS’17). 235--246.

[57]

M. Hassan and R. Pellizzoni. 2018. Bounding DRAM interference in COTS heterogeneous MPSoCs for mixed criticality systems. In Proceedings of the IEEE 8 ACM International Conference on Embedded Software (EMSOFT’18).

[58]

F. Hebbache, M. Jan, F. Brandner, and L. Pautet. 2018. Shedding the shackles of time-division multiplexing. In Proceedings of the IEEE Real-Time Systems Symposium (RTSS’18). 456--468.

[59]

S. Hesham, J. Rettkowski, D. Goehringer, and M. A. Abd El Ghany. 2017. Survey on real-time networks-on-chip. IEEE Transactions on Parallel and Distributed Systems 28, 5 (May 2017), 1500--1517.

Digital Library

[60]

W. H. Huang, J. J. Chen, and J. Reineke. 2016. MIRROR: Symmetric timing analysis for real-time tasks on multicore platforms with shared resources. In Proceedings of the Design Automation Conference (DAC’16). 1--6.

Digital Library

[61]

R. Inam, M. Behnam, T. Nolte, and M. Sjödin. 2015. Compositional analysis for the multi-resource server. In Proceedings of the IEEE Conference on Emerging Technologies Factory Automation (ETFA’15). 1--10.

[62]

M. Jacobs, S. Hahn, and S. Hack. 2015. WCET analysis for multi-core processors with shared buses and event-driven bus arbitration. In Proceedings of the International Conference on Real-Time Networks and Systems (RTNS’15). 193--202.

[63]

M. Jacobs, S. Hahn, and S. Hack. 2016. A framework for the derivation of WCET analyses for multi-core processors. In Proceedings of the Euromicro Conference on Real-Time Systems (ECRTS’16). 141--151.

[64]

M. M. Kafshdooz and A. Ejlali. 2015. Dynamic shared SPM reuse for real-time multicore embedded systems. ACM Transactions on Architecture and Code Optimization 12, 2 (May 2015), Article 12, 25 pages.

Digital Library

[65]

T. Kelter, H. Borghorst, and P. Marwedel. 2014. WCET-aware scheduling optimizations for multi-core real-time systems. In Proceedings of the International Conference on Embedded Computer Systems: Architectures, Modeling, and Simulation (SAMOS XIV). 67--74.

[66]

T. Kelter, H. Falk, P. Marwedel, S. Chattopadhyay, and A. Roychoudhury. 2011. Bus-aware multicore WCET analysis through TDMA offset bounds. In Proceedings of the Euromicro Conference on Real-Time Systems (ECRTS’11). 3--12.

Digital Library

[67]

T. Kelter, H. Falk, P. Marwedel, S. Chattopadhyay, and A. Roychoudhury. 2014. Static analysis of multi-core TDMA resource arbitration delays. Real-Time Systems 50, 2 (2014), 185--229.

Digital Library

[68]

T. Kelter, T. Harde, P. Marwedel, and H. Falk. 2013. Evaluation of resource arbitration methods for multi-core real-time systems. In Proceedings of the Workshop on Worst-Case Execution Time Analysis (WCET’13), Vol. 30. 1--10.

[69]

T. Kelter and P. Marwedel. 2015. Parallelism analysis: Precise WCET values for complex multi-core systems. In Formal Techniques for Safety-Critical Systems. 142--158.

[70]

A. E. Kiasari, A. Jantsch, and Z. Lu. 2013. Mathematical formalisms for performance evaluation of networks-on-chip. ACM Computing Surveys 45, 3, Article 38 (July 2013), 41 pages.

Digital Library

[71]

H. Kim, D. De Niz, B. Andersson, M. Klein, O. Mutlu, and R. Rajkumar. 2014. Bounding memory interference delay in COTS-based multi-core systems. In Proceedings of the IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS’14). 145--154.

[72]

H. Kim, D. De Niz, B. Andersson, M. Klein, O. Mutlu, and R. Rajkumar. 2016. Bounding and reducing memory interference in COTS-based multi-core systems. Real-Time Systems 52, 3 (May 2016), 356--395.

Digital Library

[73]

H. Kim, A. Kandhalu, and R. Rajkumar. 2013. A coordinated approach for practical OS-level cache management in multi-core real-time systems. In Proceedings of the Euromicro Conference on Real-Time Systems (ECRTS’13). 80--89.

Digital Library

[74]

J. E. Kim, M. K. Yoon, R. Bradford, and L. Sha. 2014. Integrated modular avionics (IMA) partition scheduling with conflict-free I/O for multicore avionics systems. Proceedings - International Computer Software and Applications Conference (2014), 321--331.

Digital Library

[75]

J. E. Kim, M. K. Yoon, S. Im, R. Bradford, and L. Sha. 2013. Optimized scheduling of multi-IMA partitions with exclusive region for synchronized real-time multi-core systems. In Proceedings of the Conference on Design, Automation and Test in Europe (DATE’13). 970--975.

Digital Library

[76]

Y. Kim, D. Broman, J. Cai, and A. Shrivastaval. 2014. WCET-aware dynamic code management on scratchpads for software-managed multicores. In Proceedings of the IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS’14). 179--188.

[77]

K. Lampka, G. Giannopoulou, R. Pellizzoni, Z. Wu, and N. Stoimenov. 2014. A formal approach to the WCRT analysis of multicore systems with memory contention under phase-structured task sets. Real-Time Systems 50, 5 (2014), 736--773.

Digital Library

[78]

Y. Li, V. Suhendra, Y. Liang, T. Mitra, and A. Roychoudhury. 2009. Timing analysis of concurrent programs running on shared cache multi-cores. In Proceedings of the IEEE Real-Time Systems Symposium (RTSS’09). 57--67.

[79]

Y. Liang, H. Ding, T. Mitra, A. Roychoudhury, Y. Li, and V. Suhendra. 2012. Timing analysis of concurrent programs running on shared cache multi-cores. Real-Time Systems 48, 6 (2012), 638--680.

Digital Library

[80]

Y. Liu and W. Zhang. 2012. Exploiting multi-level scratchpad memories for time-predictable multicore computing. In Proceedings of the 2012 IEEE 30th International Conference on Computer Design (ICCD’12). 61--66.

Digital Library

[81]

Y. Liu and W. Zhang. 2015. Scratchpad memory architectures and allocation algorithms for hard real-time multicore processors. Journal of Computing Science and Engineering 9, 2 (2015), 51--72.

[82]

M. Lv, W. Yi, N. Guan, and G. Yu. 2010. Combining abstract interpretation with model checking for timing analysis of multicore software. In Proceedings of the IEEE Real-Time Systems Symposium (RTSS’10). IEEE Computer Society, 339--349.

[83]

R. Mancuso, R. Pellizzoni, M. Caccamo, L. Sha, and H. Yun. 2015. WCET (m) estimation in multi-core systems using single core equivalence. In Proceedings of the Euromicro Conference on Real-Time Systems (ECRTS’15). IEEE, 174--183.

[84]

R. Mancuso, R. Pellizzoni, N. Tokcan, and M. Caccamo. 2017. WCET derivation under single core equivalence with explicit memory budget assignment. In Proceedings of the Euromicro Conference on Real-Time Systems (ECRTS’17).

[85]

A. Melani, M. Bertogna, V. Bonifaci, A. Marchetti-Spaccamela, and G. Buttazzo. 2015. Memory-processor co-scheduling in fixed priority systems. In Proceedings of the International Conference on Real-Time Networks and Systems (RTNS’15). 87--96.

[86]

K. Nagar and Y. N. Srikant. 2016. Fast and precise worst-case interference placement for shared cache analysis. ACM Transactions on Embedded Computing Systems 15, 3 (Mar. 2016), 1--26.

Digital Library

[87]

B. Nikolic and S. M. Petters. 2015. Real-time application mapping for many-cores using a limited migrative model. Real-Time Systems 51, 3 (June 2015), 314--357.

Digital Library

[88]

B. Nikolic, P. M. Yomsi, and S. M. Petters. 2013. Worst-case memory traffic analysis for many-cores using a limited migrative model. In Proceedings of the IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA’13). 42--51.

[89]

J. Nowotsch and M. Paulitsch. 2013. Quality of service capabilities for hard real-time applications on multi-core processors. Proceedings of the International Conference on Real-Time Networks and Systems (RTNS’13), 151--160.

[90]

J. Nowotsch, M. Paulitsch, D. Bühler, H. Theiling, S. Wegener, and M. Schmidt. 2014. Multi-core interference-sensitive WCET analysis leveraging runtime resource capacity enforcement. In Proceedings of the Euromicro Conference on Real-Time Systems (ECRTS’14). 109--118.

[91]

International Organization for Standardization. 2011. ISO 26262 Road Vehicles Functional Safety. Technical Report.

[92]

D. Oehlert, A. Luppold, and H. Falk. 2017. Bus-aware static instruction SPM allocation for multicore hard real-time systems. In Proceedings of the Euromicro Conference on Real-Time Systems (ECRTS’17).

[93]

C. Pagetti, J. Forget, H. Falk, D. Oehlert, and A. Luppold. 2018. Automated generation of time-predictable executables on multicore. In Proceedings of the International Conference on Real-Time Networks and Systems (RTNS’18). ACM, 104--113.

[94]

M. Paolieri, J. Mische, S. Metzlaff, M. Gerdes, E. Quiñones, S. Uhrig, T. Ungerer, and F. J. Cazorla. 2013. A hard real-time capable multi-core SMT processor. ACM Transactions on Embedded Computing Systems 12, 3 (2013), 79:1--79:26.

Digital Library

[95]

M. Paolieri, E. Quiñones, F. J. Cazorla, R. I. Davis, and M. Valero. 2011. : An interference aware allocation algorithm for multicore hard real-time systems. In Proceedings of the IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS’11). 280--290.

Digital Library

[96]

R. Pellizzoni, E. Betti, S. Bak, G. Yao, J. Criswell, M. Caccamo, and R. Kegley. 2011. A predictable execution model for COTS-based embedded systems. In Proceedings of the IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS’11). 269--279.

[97]

R. Pellizzoni, B. D. Bui, M. Caccamo, and L. Sha. 2008. Coscheduling of CPU and I/O transactions in COTS-based embedded systems. In Proceedings of the IEEE Real-Time Systems Symposium (RTSS’08). 221--231.

Digital Library

[98]

R. Pellizzoni, A. Schranzhofer, J-J. Chen, M. Caccamo, and L. Thiele. 2010. Worst case delay analysis for memory interference in multicore systems. In Proceedings of the Conference on Design, Automation and Test in Europe (DATE’10). 741--746.

Digital Library

[99]

R. Pellizzoni and H. Yun. 2016. Memory servers for multicore systems. In Proceedings of the IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS’16). 1--12.

[100]

Q. Perret, P. Maurère, E. Noulard, C. Pagetti, P. Sainrat, and B. Triquet. 2016. Mapping hard real-time applications on many-core processors. In Proceedings of the International Conference on Real-Time Networks and Systems (RTNS’16). 235--244.

[101]

Q. Perret, P. Maurere, E. Noulard, C. Pagetti, P. Sainrat, and B. Triquet. 2016. Predictable composition of memory accesses on many-core processors. In Proceedings of the 8th European Congress on Embedded Real Time Software and Systems (ERTS’16).

[102]

Q. Perret, P. Maurere, E. Noulard, C. Pagetti, P. Sainrat, and B. Triquet. 2016. Temporal isolation of hard real-time applications on many-core processors. In Proceedings of the IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS’16). 1--11.

[103]

H. Rihani, M. Moy, C. Maiza, and S. Altmeyer. 2015. WCET analysis in shared resources real-time systems with TDMA buses. In Proceedings of the International Conference on Real-Time Networks and Systems (RTNS’15). ACM, 183--192.

[104]

H. Rihani, M. Moy, C. Maiza, R. I. Davis, and S. Altmeyer. 2016. Response time analysis of synchronous data flow programs on a many-core processor. In Proceedings of the International Conference on Real-Time Networks and Systems (RTNS’16). 67--76.

[105]

J. Rosèn, A. Andrei, P. Eles, and Z. Peng. 2007. Bus access optimization for predictable implementation of real-time applications on multiprocessor systems-on-chip. In Proceedings of the IEEE Real-Time Systems Symposium (RTSS’07).

[106]

S. Saidi and A. Syring. 2018. Exploiting locality for the performance analysis of shared memory systems in MPSoCs. In Proceedings of the IEEE Real-Time Systems Symposium (RTSS’18). 350--360.

[107]

S. Schliecker and R. Ernst. 2011. Real-time performance analysis of multiprocessor systems with shared memory. ACM Transactions on Embedded Computing Systems 10, 2, Article 22 (Jan. 2011), Article 22, 27 pages.

Digital Library

[108]

S. Schliecker, M. Negrean, and R. Ernst. 2010. Bounding the shared resource load for the performance analysis of multiprocessor systems. In Proceedings of the Design Automation Conference (DAC’10). 759--764.

[109]

S. Schliecker, M. Negrean, G. Nicolescu, P. Paulin, and R. Ernst. 2008. Reliable performance analysis of a multicore multithreaded system-on-chip. In Proceedings of the 6th IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis. 161--166.

Digital Library

[110]

S. Schliecker, J. Rox, M. Negrean, K. Richter, M. Jersak, and R. Ernst. 2009. System level performance analysis for real-time automotive multicore and network architectures. IEEE Transactions on CAD of Integrated Circuits and Systems 28, 7 (2009), 979--992.

Digital Library

[111]

M. Schoeberl, S. Abbaspour, B. Akesson, N. Audsley, R. Capasso, J. Garside, K. Goossens, S. Goossens, S. Hansen, R. Heckmann, S. Hepp, B. Huber, A. Jordan, E. Kasapaki, J. Knoop, Y. Li, D. Prokesch, W. Puffitsch, P. Puschner, A. Rocha, C. Silva, J. Sparsø, and A. Tocchi. 2015. T-CREST: Time-predictable multi-core architecture for embedded systems. Journal of Systems Architecture 61, 9 (2015), 449--471.

Digital Library

[112]

A. Schranzhofer, J. J. Chen, and L. Thiele. 2010. Timing analysis for TDMA arbitration in resource sharing systems. In Proceedings of the IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS’10). 215--224.

[113]

A. Schranzhofer, R. Pellizzoni, J. J. Chen, L. Thiele, and M. Caccamo. 2010. Worst-case response time analysis of resource access models in multi-core systems. In Proceedings of the Design Automation Conference (DAC’10). 332--337.

[114]

A. Schranzhofer, R. Pellizzoni, J.-J. Chen, L. Thiele, and M. Caccamo. 2011. Timing analysis for resource access interference on adaptive resource arbiters. In Proceedings of the IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS’11). 213--222.

[115]

J. P. Shen and M. H. Lipasti. 2013. Modern Processor Design: Fundamentals of Superscalar Processors. Waveland Press.

[116]

S. Skalistis and A. Simalatsar. 2016. Worst-case execution time analysis for many-core architectures with NoC. In International Conference on Formal Modeling and Analysis of Timed Systems. 211--227.

[117]

S. Skalistis and A. Simalatsar. 2017. Near-optimal deployment of dataflow applications on many-core platforms with real-time guarantees. In Proceedings of the Conference on Design, Automation and Test in Europe (DATE’17). 752--757.

[118]

P. Souto, P. B. Sousa, R. I. Davis, K. Bletsas, and E. Tovar. 2015. Overhead-aware schedulability evaluation of semi-partitioned real-time schedulers. In Proceedings of the IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA’15). 110--121.

Digital Library

[119]

L. R. Still and L. S. Indrusiak. 2018. Memory-aware genetic algorithms for task mapping on hard real-time networks-on-chip. In Proceedings of the Euromicro International Conference on Parallel, Distributed and Network-based Processing (PDP’18).

[120]

V. Suhendra, C. Raghavan, and T. Mitra. 2006. Integrated scratchpad memory optimization and task scheduling for mpsoc architectures. In Proceedings of the International Conference on Compilers, Architecture and Synthesis for Embedded Systems. ACM, New York, NY, 401--410.

Digital Library

[121]

V. Suhendra, A. Roychoudhury, and T. Mitra. 2010. Scratchpad allocation for concurrent embedded software. ACM Transactions on Programming Languages and Systems 32, 4 (April 2010), Article 13, 47 pages.

Digital Library

[122]

R. Tabish, R. Mancuso, S. Wasly, A. Alhammad, S. S Phatak, and R. Pellizzoni. 2016. A real-time scratchpad-centric OS for multi-core embedded systems. In Proceedings of the IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS’16).

[123]

P. K. Valsan, H. Yun, and F. Farshchi. 2016. Taming non-blocking caches to improve isolation in multicore real-time systems. In Proceedings of the IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS’16). 1--12.

[124]

P. K. Valsan, H. Yun, and F. Farshchi. 2017. Addressing isolation challenges of non-blocking caches for multicore real-time systems. Real-Time Systems 53, 5 (2017), 673--708.

Digital Library

[125]

S. Wasly and R. Pellizzoni. 2014. Hiding memory latency using fixed priority scheduling. In Proceedings of the IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS’14). 75--86.

[126]

J. Xiao, S. Altmeyer, and A. Pimentel. 2017. Schedulability analysis of non-preemptive real-time scheduling for multicore processors with shared caches. In Proceedings of the IEEE Real-Time Systems Symposium (RTSS’17). 199--208.

[127]

M. Xu, L. T. X. Phan, H. Y. Choi, and I. Lee. 2016. Analysis and implementation of global preemptive fixed-priority scheduling with dynamic cache allocation. In Proceedings of the IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS’16). 1--12.

[128]

J. Yan and W. Zhang. 2008. WCET analysis for multi-core processors with shared L2 instruction caches. In Proceedings of the IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS’08). 80--89.

[129]

G. Yao, R. Pellizzoni, S. Bak, E. Betti, and M. Caccamo. 2012. Memory-centric scheduling for multicore hard real-time systems. Real-Time Systems 48, 6 (Nov. 2012), 681--715.

Digital Library

[130]

G. Yao, R. Pellizzoni, S. Bak, H. Yun, and M. Caccamo. 2016. Global real-time memory-centric scheduling for multicore systems. IEEE Transactions on Computers 65, 9 (Sept. 2016), 2739--2751.

Digital Library

[131]

G. Yao, H. Yun, Z. P. Wu, R. Pellizzoni, M. Caccamo, and L. Sha. 2016. Schedulability analysis for memory bandwidth regulated multicore real-time systems. IEEE Transactions on Computers 65, 2 (Feb. 2016), 601--614.

Digital Library

[132]

M. K. Yoon, J. E. Kim, and L. Sha. 2011. Optimizing tunable WCET with shared resource allocation and arbitration in hard real-time multicore systems. In Proceedings of the IEEE Real-Time Systems Symposium (RTSS’11). 227--238.

[133]

H. Yun, R. Mancuso, Z. P. Wu, and R. Pellizzoni. 2014. PALLOC: DRAM bank-aware memory allocator for performance isolation on multicore platforms. In Proceedings of the IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS’14). 155--166.

[134]

H. Yun, R. Pellizzoni, and P. K. Valsan. 2015. Parallelism-aware memory interference delay analysis for cots multicore systems. In Proceedings of the Euromicro Conference on Real-Time Systems (ECRTS’15). IEEE, 184--195.

[135]

H. Yun, G. Yao, R. Pellizzoni, M. Caccamo, and L. Sha. 2012. Memory access control in multiprocessor for real-time systems with mixed criticality. In Proceedings of the Euromicro Conference on Real-Time Systems (ECRTS’12). 299--308.

[136]

H. Yun, G. Yao, R. Pellizzoni, M. Caccamo, and L. Sha. 2013. MemGuard: Memory bandwidth reservation system for efficient performance isolation in multi-core platforms. Proceedings of the IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS’13), 55--64.

[137]

W. Zhang and J. Yan. 2009. Accurately estimating worst-case execution time for multi-core processors with shared direct-mapped instruction caches. In Proceedings of the IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA’09). 455--463.

Digital Library

[138]

Y. Zhang, Z. Guo, L. Wang, H. Xiong, and Z. Zhang. 2017. Integrating cache-related preemption delay into GEDF analysis for multiprocessor scheduling with on-chip cache. In IEEE Trustcom/BigDataSE/ICESS. 815--822.

[139]

W. Zheng, H. Wu, and C. Nie. 2017. Integrating task scheduling and cache locking for multicore real-time embedded systems. In Proceedings of the ACM SIGPLAN/SIGBED Conference on Languages, Compilers, and Tools for Embedded Systems. 71--80.

Cited By

Mahdi MWalshe RFarrell SPandit H(2024)Comprehensive Review and Future Research Directions on ICT StandardisationInformation10.3390/info1511069115:11(691)Online publication date: 2-Nov-2024
https://doi.org/10.3390/info15110691
Xing YLi YTakada H(2024)A Multi-core RTOS Benchmark Methodology To Assess System Services Under ContentionsJournal of Information Processing10.2197/ipsjjip.32.82932(829-843)Online publication date: 2024
https://doi.org/10.2197/ipsjjip.32.829
Levieux SSinghoff FRubini SPlasson PGouel PMalac-Allain LMiné LBrusq G(2024)An Iterative Benchmark Configuration Method forQuantifying Multi-core InterferenceACM SIGAda Ada Letters10.1145/3706601.370661544:1(78-84)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3706601.3706615
Show More Cited By

Index Terms

A Survey of Timing Verification Techniques for Multi-Core Real-Time Systems
1. Computer systems organization
  1. Real-time systems
    1. Real-time system architecture
2. Software and its engineering
  1. Software organization and properties
    1. Software functional properties
      1. Correctness
        Real-time schedulability
      2. Formal methods
        Automated static analysis

Recommendations

Quality of service capabilities for hard real-time applications on multi-core processors
RTNS '13: Proceedings of the 21st International conference on Real-Time Networks and Systems

Computing Worst-Case Execution Times (WCETs) for applications executed on multi-core processors is a challenging topic since possible interferences on shared resources need to be considered. Some approaches are already proposed in literature, but the ...
parMERASA -- Multi-core Execution of Parallelised Hard Real-Time Applications Supporting Analysability
DSD '13: Proceedings of the 2013 Euromicro Conference on Digital System Design

Engineers who design hard real-time embedded systems express a need for several times the performance available today while keeping safety as major criterion. A breakthrough in performance is expected by parallelizing hard real-time applications and ...
A Survey of WCET Analysis of Real-Time Operating Systems
ICESS '09: Proceedings of the 2009 International Conference on Embedded Software and Systems

Timing correctness of hard real-time systems is guaranteed by schedulability analysis and worst-case execution time (WCET) analysis of programs. Traditional WCET analysis mainly deals with application programs and has achieved success in industry. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Computing Surveys

ACM Computing Surveys Volume 52, Issue 3

May 2020

734 pages

ISSN:0360-0300

EISSN:1557-7341

DOI:10.1145/3341324

Editor:
Sartaj Sahni
Department of Computer and Information Science and Engineering

Issue’s Table of Contents

Copyright © 2019 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 18 June 2019

Accepted: 01 February 2019

Revised: 01 February 2019

Received: 01 October 2018

Published in CSUR Volume 52, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Survey
Research
Refereed

Funding Sources

ESPRC
Wallonia region BEWARE grant
UK SECT-AIR

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

52
Total Citations
View Citations
1,253
Total Downloads

Downloads (Last 12 months)153
Downloads (Last 6 weeks)22

Reflects downloads up to 17 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Mahdi MWalshe RFarrell SPandit H(2024)Comprehensive Review and Future Research Directions on ICT StandardisationInformation10.3390/info1511069115:11(691)Online publication date: 2-Nov-2024
https://doi.org/10.3390/info15110691
Xing YLi YTakada H(2024)A Multi-core RTOS Benchmark Methodology To Assess System Services Under ContentionsJournal of Information Processing10.2197/ipsjjip.32.82932(829-843)Online publication date: 2024
https://doi.org/10.2197/ipsjjip.32.829
Levieux SSinghoff FRubini SPlasson PGouel PMalac-Allain LMiné LBrusq G(2024)An Iterative Benchmark Configuration Method forQuantifying Multi-core InterferenceACM SIGAda Ada Letters10.1145/3706601.370661544:1(78-84)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3706601.3706615
Bechtel MYun H(2024)Analysis and Mitigation of Shared Resource Contention on Heterogeneous Multicore: An Industrial Case StudyIEEE Transactions on Computers10.1109/TC.2024.338605973:7(1753-1766)Online publication date: Jul-2024
https://doi.org/10.1109/TC.2024.3386059
Doose DBouchebaba YGonzalez A(2024)Optimal Real-Time Task Allocation in Heteregeneous Multi-Core Embedded Systems2024 IEEE 30th International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA)10.1109/RTCSA62462.2024.00024(108-113)Online publication date: 21-Aug-2024
https://doi.org/10.1109/RTCSA62462.2024.00024
Arora JRashid SNelissen GMaia CTovar E(2024)Improved Memory Contention Analysis for the 3-Phase Task Model2024 IEEE 30th International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA)10.1109/RTCSA62462.2024.00012(11-20)Online publication date: 21-Aug-2024
https://doi.org/10.1109/RTCSA62462.2024.00012
Fischer TFalk H(2024)Timing-aware analysis of shared cache interference for non-preemptive schedulingReal-Time Systems10.1007/s11241-024-09430-860:4(570-624)Online publication date: 30-Sep-2024
https://doi.org/10.1007/s11241-024-09430-8
Aceituno JGuasque ABalbastre PSimó JPereira CCrespo A(2023)Técnicas de planificación para optimizar el rendimiento de los sistemas de tiempo real multiprocesadorRevista Iberoamericana de Automática e Informática industrial10.4995/riai.2023.1993521:1(29-38)Online publication date: 11-Sep-2023
https://doi.org/10.4995/riai.2023.19935
Ye YNie ZLiu XXie FLi ZLi P(2023)ROS2 Real-time Performance Optimization and EvaluationChinese Journal of Mechanical Engineering10.1186/s10033-023-00976-536:1Online publication date: 4-Dec-2023
https://doi.org/10.1186/s10033-023-00976-5
Thilakasiri TBecker M(2023)Methods to Realize Preemption in Phased Execution ModelsACM Transactions on Embedded Computing Systems10.1145/360913222:5s(1-25)Online publication date: 31-Oct-2023
https://dl.acm.org/doi/10.1145/3609132
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Media

Figures

Other

Tables

View Issue’s Table of Contents