Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Real-Time Systems
Published in: Real-Time Systems 2/2020

15-11-2019

Design and analysis of SIC: a provably timing-predictable pipelined processor core

Authors: Sebastian Hahn, Jan Reineke

Published in: Real-Time Systems | Issue 2/2020

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We introduce the strictly in-order core (SIC), a timing-predictable pipelined processor core. SIC is provably timing compositional and free of timing anomalies. This enables precise and efficient worst-case execution time (WCET) and multi-core timing analysis. SIC’s key underlying property is the monotonicity of its transition relation w.r.t. a natural partial order on its microarchitectural states. This monotonicity is achieved by carefully eliminating some of the dependencies between consecutive instructions from a standard in-order pipeline design. We present a formal proof framework based on satisfiability modulo theories that is able to automatically verify SIC’s timing predictability. SIC preserves most of the benefits of pipelining: it is only about 6–7% slower than a conventional non-strict in-order pipelined processor. Its timing predictability enables orders-of-magnitude faster WCET and multi-core timing analysis than conventional designs.
previous article Reduced latency DRAM for multi-core safety-critical real-time systems

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
Appendix
Available only for authorised users
Literature
Altmeyer S, Davis RI, Maiza C (2011) Cache related pre-emption delay aware response time analysis for fixed priority pre-emptive systems. In: Proceedings of the 32nd IEEE real-time systems symposium, RTSS 2011, Vienna, Austria, November 29–December 2, 2011, pp 261–271
Altmeyer S, Davis RI, Indrusiak LS, Maiza C, Nélis V, Reineke J (2015) A generic and compositional framework for multicore response time analysis. In: Proceedings of the 23rd International Conference on real time networks and systems, RTNS 2015, Lille, France, November 4–6, 2015, pp 129–138
Berg C, Engblom J, Wilhelm R (2004) Requirements for and design of a processor with predictable timing. In: Perspectives workshop: design of systems with predictable behaviour, ser. Dagstuhl Seminar Proceedings. Thiele L, Wilhelm R (Eds.) no. 03471. Dagstuhl, Germany: Internationales Begegnungs- und Forschungszentrum für Informatik (IBFI), Schloss Dagstuhl, Germany
Cousot P, Cousot R (1977) Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints. In: Conference record of the fourth ACM symposium on principles of programming languages, Los Angeles, California, USA, January 1977, pp 238–252
Dasari D, Andersson B, Nelis V, Petters S, Easwaran A, Lee J (2011) Response time analysis of COTS-based multicores considering the contention on the shared memory bus. In: 2011 IEEE 10th international conference on trust, security and privacy in computing and communications (TrustCom), pp 1068–1075
Davis RI, Altmeyer S, Indrusiak LS, Maiza C, Nelis V, Reineke J (2018) An extensible framework for multicore response time analysis. Real-Time Syst 54(3):607–661CrossRef
de Dinechin BD, van Amstel D, Poulhiès M, Lager G (2014) Time-critical computing on a single-chip massively parallel processor. In: DATE, pp 1–6
de Moura LM, Bjørner N (2008) Z3: an efficient SMT solver. In: Tools and algorithms for the construction and analysis of systems, 14th international conference, TACAS 2008, held as part of the joint European conferences on theory and practice of software, ETAPS 2008, Budapest, Hungary, March 29–April 6, 2008. Proceedings, pp 337–340
Degasperi P, Hepp S, Puffitsch W, Schoeberl M (2014) A method cache for patmos. In: 17th IEEE international symposium on object/component/service-oriented real-time distributed computing, ISORC 2014, Reno, NV, USA, June 10–12, 2014. IEEE Computer Society, pp 100–108
Edwards SA, Lee EA (2007) The case for the precision timed (PRET) machine. In: Proceedings of the 44th design automation conference, DAC 2007, San Diego, CA, USA, June 4–8, 2007. IEEE, pp 264–265
Engblom J, Jonsson B (2002) Processor pipelines and their properties for static WCET analysis. In: Embedded software, second international conference, EMSOFT 2002, Grenoble, France, October 7–9, 2002, Proceedings, ser. Lecture Notes in Computer Science, Sangiovanni-Vincentelli AL, Sifakis J (eds) vol. 2491. Springer, pp 334–348
Falk H, Altmeyer S, Hellinckx P, Lisper B, Puffitsch W, Rochange C, Schoeberl M, Sorensen RB, Wägemann P, Wegener S (2016) TACLeBench: A benchmark collection to support worst-case execution time research. In: 16th international workshop on worst-case execution time analysis, WCET 2016, July 5, Toulouse, France, 2016, pp 2:1–2:10
Ferdinand C, Wilhelm R (1999) Efficient and precise cache behavior prediction for real-time systems. Real-Time Syst 17(2–3):131–181CrossRef
Giannopoulou G, Lampka K, Stoimenov N, Thiele L (2012) Timed model checking with abstractions: towards worst-case response time analysis in resource-sharing manycore systems. In: EMSOFT. ACM, pp 63–72
Gustavsson A, Ermedahl A, Lisper B, Pettersson P (2010) Towards WCET analysis of multicore architectures using UPPAAL. In: WCET, B. Lisper, Ed., vol. 15, Dagstuhl, Germany, pp 101–112
Hahn S, Reineke J (2018) Design and analysis of SIC: a provably timing-predictable pipelined processor core. In: 2018 IEEE real-time systems symposium, RTSS 2018, Nashville, TN, USA, December 11–14, 2018, pp 469–481
Hahn S, Reineke J, Wilhelm R (2015) Towards compositionality in execution time analysis: definition and challenges. SIGBED Rev 12(1):28–36CrossRef
Hahn S, Jacobs M, Reineke J (2016) Enabling compositionality for multicore timing analysis. In: Proceedings of the 24th international conference on real-time networks and systems, RTNS 2016, Brest, France, October 19–21, 2016, pp 299–308
Hahn S, Reineke J, Wilhelm R (2015) Toward compact abstractions for processor pipelines. In: Correct system design—symposium in honor of Ernst-Rüdiger Olderog on the Occasion of His 60th Birthday, Oldenburg, Germany, September 8–9, 2015. Proceedings, pp 205–220
Hennessy JL, Patterson DA (2012) Computer architecture: a quantitative approach, 5th edn. Morgan Kaufmann, BurlingtonMATH
Huang W, Chen J, Reineke J (2016) MIRROR: symmetric timing analysis for real-time tasks on multicore platforms with shared resources. In: Proceedings of the 53rd annual design automation conference, DAC 2016, Austin, TX, USA, June 5–9, 2016. ACM, pp 158:1–158:6
Kelter T (2015) “WCET analysis and optimization for multi-core real-time systems. Ph.D. dissertation, TU Dortmund University
Kelter T, Marwedel P (2014) Parallelism analysis: precise WCET values for complex multi-core systems. In: Formal techniques for safety-critical systems—third international workshop, pp 142–158
Lampka K, Giannopoulou G, Pellizzoni R, Wu Z, Stoimenov N (2014) A formal approach to the WCRT analysis of multicore systems with memory contention under phase-structured task sets. Real-Time Syst 50(5):736–773CrossRef
Li YS, Malik S (1995) Performance analysis of embedded software using implicit path enumeration. In: Proceedings of the ACM SIGPLAN 1995 workshop on languages, compilers, & tools for real-time systems (LCT-RTS 1995). La Jolla, California, June 21–22, 1995, pp 88–98
Liu I, Reineke J, Broman D, Zimmer M, Lee EA (2012) A PRET microarchitecture implementation with repeatable timing and competitive performance. In: 30th International IEEE conference on computer design, ICCD 2012, Montreal, QC, Canada, September 30–October 3, 2012. IEEE Computer Society, pp 87–93
Lundqvist T, Stenström P (1999) Timing anomalies in dynamically scheduled microprocessors. In: Proceedings of the 20th IEEE real-time systems symposium, Phoenix, AZ, USA, December 1–3, 1999, pp 12–21
Lv M, Guan N, Reineke J, Wilhelm R, Yi W (2016) A survey on static cache analysis for real-time systems. Leibniz Trans Embed Syst 3(1):05
Lv M, Yi W, Guan N, Yu G (2010) Combining abstract interpretation with model checking for timing analysis of multicore software. In: Proceedings of the 2010 31st IEEE real-time systems symposium, pp 339–349
Müller SM, Paul WJ (2000) Computer architecture: complexity and correctness. Springer, BerlinCrossRef
Pellizzoni R, Schranzhofer A, Chen J-J, Caccamo M, Thiele L (March 2010) Worst case delay analysis for memory interference in multicore systems. In: Design, automation test in Europe Conference Exhibition (DATE), 2010, pp 741–746
Reineke J, Liu I, Patel HD, Kim S, Lee EA (2011) PRET DRAM controller: bank privatization for predictability and temporal isolation. In: Dick RP, Madsen J (eds) Proceedings of the 9th international conference on hardware/software codesign and system synthesis, CODES+ISSS 2011, part of ESWeek ’11 seventh embedded systems week, Taipei, Taiwan, 9–14 October, 2011, ACM, pp 99–108
Reineke J, Wachter B, Thesing S, Wilhelm R, Polian I, Eisinger J, Becker B (July 2006) A definition and classification of timing anomalies. In: Proceedings of 6th international workshop on worst-case execution time (WCET) analysis
Schliecker S, Ernst R (2011) Real-time performance analysis of multiprocessor systems with shared memory. ACM Trans Embed Comput Syst 10(2):22:1–22:27
Schoeberl M, Abbaspour S, Akesson B, Audsley NC, Capasso R, Garside J, Goossens K, Goossens S, Hansen S, Heckmann R, Hepp S, Huber B, Jordan A, Kasapaki E, Knoop J, Li Y, Prokesch D, Puffitsch W, Puschner PP, Rocha A, Silva C, Sparsø J, Tocchi A (2015) T-CREST: time-predictable multi-core architecture for embedded systems. J Syst Architect Embed Syst Des 61(9):449–471CrossRef
Schoeberl M, Puffitsch W, Hepp S, Huber B, Prokesch D (2018) Patmos: a time-predictable microprocessor. Real-Time Syst 54(2):389–423CrossRef
Schranzhofer A, Chen J-J, Thiele L (2010) Timing analysis for TDMA arbitration in resource sharing systems. In: Proceedings of the 2010 16th IEEE real-time and embedded technology and applications symposium, pp 215–224
Schranzhofer A, Pellizzoni R, Chen J-J, Thiele L, Caccamo M (2011) Timing analysis for resource access interference on adaptive resource arbiters. In: Proceedings of the 2011 17th IEEE real-time and embedded technology and applications symposium, pp 213–222
Thiele L, Wilhelm R (2004a) Design for timing predictability. Real-Time Syst 28(2–3):157–177
Thiele L, Wilhelm R (2004b) 03471 abstracts collection—design of systems with predictable behaviour. In: Perspectives workshop: design of systems with predictable behaviour, ser. Dagstuhl Seminar Proceedings, Thiele L, Wilhelm R (eds) no. 03471. Dagstuhl, Germany: Internationales Begegnungs- und Forschungszentrum für Informatik (IBFI), Schloss Dagstuhl, Germany
Touzeau V, Maïza C, Monniaux D, Reineke J (2019) Fast and exact analysis for LRU caches. Proc ACM Program Lang 3(POPL):54:1–54:29CrossRef
Ungerer T, Cazorla FJ, Sainrat P, Bernat G, Petrov Z, Rochange C, Quiñones E, Gerdes M, Paolieri M, Wolf J, Cassé H, Uhrig S, Guliashvili I, Houston M, Kluge F, Metzlaff S, Mische J (2010) Merasa: multicore execution of hard real-time applications supporting analyzability. IEEE Micro 30(5):66–75CrossRef
Ungerer T, Bradatsch C, Frieb M, Kluge F, Mische J, Stegmeier A, Jahr R, Gerdes M, Zaykov PG, Matusova L, Li ZJJ, Petrov Z, Böddeker B, Kehr S, Regler H, Hugl A, Rochange C, Ozaktas H, Cassé H, Bonenfant A, Sainrat P, Lay N, George D, Broster I, Quiñones E, Panic M, Abella J, Hernández C, Cazorla FJ, Uhrig S, Rohde M, Pyka A (2016) Parallelizing industrial hard real-time applications for the parMERASA multicore. ACM Trans Embed Comput Syst 15(3):53:1–53:27CrossRef
Wilhelm R, Engblom J, Ermedahl A, Holsti N, Thesing S, Whalley DB, Bernat G, Ferdinand C, Heckmann R, Mitra T, Mueller F, Puaut I, Puschner PP, Staschulat J, Stenström P (2008) The worst-case execution-time problem: overview of methods and survey of tools. ACM Trans Embed Comput Syst 7(3):36:1–36:53CrossRef
Wilhelm R, Grund D, Reineke J, Schlickling M, Pister M, Ferdinand C (2009) Memory hierarchies, pipelines, and buses for future architectures in time-critical embedded systems. IEEE Trans CAD Integr Circuits Syst 28(7):966–978CrossRef
Zimmer M, Broman D, Shaver C, Lee EA (2014) FlexPRET: A processor platform for mixed-criticality systems. In: 20th IEEE real-time and embedded technology and applications symposium, RTAS 2014, Berlin, Germany, April 15–17, 2014. IEEE Computer Society, pp 101–110
Metadata
Title
Design and analysis of SIC: a provably timing-predictable pipelined processor core
Authors
Sebastian Hahn
Jan Reineke
Publication date
15-11-2019
Publisher
Springer US
Published in
Real-Time Systems / Issue 2/2020
Print ISSN: 0922-6443
Electronic ISSN: 1573-1383
DOI
https://doi.org/10.1007/s11241-019-09341-z

Premium Partner

    Image Credits