The ACCORD project addresses the Analysis of Multicore Communication and its Optimization in Real-time Devices. We are investigating a formal performance analysis approach and have applied it to various industrial examples.
The transition of consumer products from SoC to MpSoC is driven by higher performance needs at low power consumption demands. Like in distributed embedded systems, multiprocessing comes at the cost of higher computation and communication complexity. Other than in distributed embedded systems, task communication is overlaid by memory traffic leading to very complex communication patterns including the effects of multithreading and non-blocking memory accesses.
Predicting the timing behaviour of such multiprocessor systems is fundamentally more difficult than in the single processor case: The interaction and correlation between distributed system components, such as a shared memory or coprocessors, makes it nearly impossible to uncover corner cases with purely simulative approaches. Memory accesses are highly dynamic and can routinely lead to overload situations which must be handled by communication mechanisms such as buffering and traffic shaping which have a feedback effect on task execution. It is very difficult if not impossible to systematically create corner cases for simulations that reliably trigger such situations. Even worse, memory access patterns are sensitive to changes in the software code which cannot be appropriately modelled in simulation. This makes it difficult to start system verification at early design phases and plan for later software updates. Thus, a risk remains that the system fails. This risk increases system complexity. Simulation alone simply is not appropriate any more.
At our institute, we have developed a performance analysis tool, SymTA/S, and an appropriate design methodology. This framework can back up a simulation by supplying robust data on cornercase behaviour, and by allowing to quickly explore new design options. It is the basis of the commercial tool that is sold by the spin-off, SymtaVision.
The classic formal performance analysis approach is bottom-up: First, the individual task timing is derived in an isolated (and therefore controllable) environment. This can use simulation, tracing, emulation, or whatever is currently used in the design process. Secondly, this information is coupled with information about the local components (such as the scheduling behaviour and contextswitch times, caches) to derive the local execution behaviour. Finally, all system level influences (such as message delays, accesses to shared resources, or traffic shapers) are considered to produce the overall timing of the system.
This separation of concerns allows each level of abstraction to be investigated separately using more sophisticated methods than in unified approaches. The system level analysis step can quickly evaluate a given setup, identify corner cases and allow designers to optimize the system e.g. for performance or robustness.
In MpSoC, the mentioned system level is entangled with the task level, in the sense that a task’s access to the shared memory is subject to system level influences. Thus, a timing feedback exists.We solve this technical problem by introduction of an extended task model that explicitly expresses shared resource accesses. An automatic iterative analysis derives the joint timing.
The extended task model is depicted in Fig. 1. In addition to the classical task states “ready” and “finished”, such a task is in the “waiting” state when it has initiated a “transaction” to a shared resource that supplies data or services that must be finished before the task may continue its execution.The response time of a task is then a composition of local and remote effects: Locally, its core execution time, the amount of local scheduling interference and the context switch times need to be considered; remotely, the transactions will experience network delay and interference on the shared resource/memory.The timing of the individual transactions is highly dynamic. In the case of thousands of memory accesses per task invocation, not every memory access can experience the worst case timing. Therefore, previous approaches which relied on worst-case assumptions, implied an unacceptably high overestimation. We have proposed to consider the timing of all transactions jointly, thereby assuming worst case interference on the transactions distributed over the task’s invocation.
This is a short overview presentation recently held at an ArtistDesign project meeting in April 2009:
The listed material is protected by copyright. The corresponding copyright must be observed.
|
Simon Schliecker, Mircea Negrean and Rolf Ernst, "Bounding the Shared Resource Load for the Performance Analysis of Multiprocessor Systems" in Proc. of Design, Automation, and Test in Europe (DATE), (Dresden, Germany), März 2010. |
|
|
|
|
@inproceedings{SNE10:BoundShareResouPerfo, address = {Dresden, Germany}, |
|||
|
Maarten Wiggers, Lothar Thiele, Edward A. Lee, Simon Schliecker and Marco Bekooij, "Modeling and analyzing real-time multiprocessor systems" in Proc. 8th Intl. Conference on Hardware/Software Codesign and System Synthesis (CODES+ISSS), (Scottsdale, AZ), pp. 329-330, Oktober 2010. |
|
|
|
|
@inproceedings{WTL+11:Modelanalyrealtmulti, address = {Scottsdale, AZ}, |
|||
|
Mircea Negrean, Simon Schliecker and Rolf Ernst, "Response-Time Analysis of Arbitrarily Activated Tasks in Multiprocessor Systems with Shared Resources" in Proc. of Design, Automation, and Test in Europe (DATE), (Nice, France), April 2009. |
|
|
|
|
@inproceedings{NSE09:RespoAnalyArbitActiv, address = {Nice, France}, |
|||
|
Simon Schliecker and Rolf Ernst, "A Recursive Approach to End-To-End Path Latency Computation in Heterogeneous Multiprocessor Systems" in Proc. 7th International Conference on Hardware Software Codesign and System Synthesis (CODES-ISSS), (Grenoble, France), ACM, Oktober 2009. |
|
|
|
|
@inproceedings{SE09:RecurApproEndToLaten, address = {Grenoble, France}, |
|||
|
Simon Schliecker, Arne Hamann, Razvan Racu and Rolf Ernst, "Formal Methods for System Level Performance Analysis and Optimization" in Proc. of the Design Verification Conference (DVCon), (San José, CA), Februar 2008. |
|
|
|
|
@inproceedings{SHR+08:FormaMethoSysteLevel, address = {San José, CA}, |
|||
|
Simon Schliecker, Mircea Negrean, Gabriela Nicolescu, Pierre Paulin and Rolf Ernst, "Reliable Performance Analysis of a Multicore Multithreaded System-On-Chip" in Proc. 6th International Conference on Hardware Software Codesign and System Synthesis (CODES-ISSS), (Atlanta, GA), Oktober 2008. |
|
|
|
|
@inproceedings{SNN+08:ReliaPerfoAnalyMulti, address = {Atlanta, GA}, |
|||
|
Simon Schliecker, Jonas Rox, Matthias Ivers and Rolf Ernst, "Providing Accurate Event Models for the Analysis of Heterogeneous Multiprocessor Systems" in Proc. 6th International Conference on Hardware Software Codesign and System Synthesis (CODES-ISSS), (Atlanta, GA), Oktober 2008. |
|
|
|
|
@inproceedings{SRI+08:ProviAccurEventModel, address = {Atlanta, GA}, |
|||
|
Simon Perathoner, Ernesto Wandeler, Lothar Thiele, Arne Hamann, Simon Schliecker, Rafik Henia, Razvan Racu, Rolf Ernst and Michael González Harbour, "Influence of Different System Abstractions on the Performance Analysis of Distributed Real-Time Systems" in Proc. ACM Conference on Embedded Software (EMSOFT), (Salzburg, Austria), Oktober 2007. |
|
|
|
|
@inproceedings{PWT+07:InfluDiffeSysteAbstr, address = {Salzburg, Austria}, |
|||
|
Simon Schliecker, Matthias Ivers, Jan Staschulat and Rolf Ernst, "A Framework for the Busy Time Calculation of Multiple Correlated Events" in 6th Intl. Workshop on Worst-Case Execution Time (WCET) Analysis, No. 06902, (Dresden, Germany), Juli 2006. |
|
|
|
|
@inproceedings{SIS+06:FrameCalcuMultiCorre, address = {Dresden, Germany}, |
|||
|
Simon Schliecker, Matthias Ivers and Rolf Ernst, "Memory Access Patterns for the Analysis of MPSoCs" in North-East Workshop on Circuits and Systems, (Gatineau, Canada), IEEE, IEEE, Juni 2006. |
|
|
|
|
@inproceedings{SIE06:MemorAccesPatteAnaly, address = {Gatineau, Canada}, |
|||
|
Simon Schliecker, Matthias Ivers and Rolf Ernst, "Integrated Analysis of Communicating Tasks in MPSoCs" in Proc. 3rd International Conference on Hardware Software Codesign and System Synthesis (CODES-ISSS), (Seoul, Korea), Oktober 2006. |
|
|
|
|
@inproceedings{SIE06:IntegAnalyCommuTasks, address = {Seoul, Korea}, |
|||
|
Jan Staschulat, Simon Schliecker, Matthias Ivers and Rolf Ernst, "Analysis of Memory Latencies in Multi-Processor Systems" in 5th Intl. Workshop on Worst-Case Execution Time (WCET) Analysis, (Palma de Mallorca, Spain), Juli 2005. |
|
|
|
|
@inproceedings{SSI+05:AnalyMemorLatenMulti, address = {Palma de Mallorca, Spain}, |
|||
|
Jan Staschulat, Simon Schliecker and Rolf Ernst, "Scheduling Analysis of Real-time Systems with Precise Modeling of Cache Related Preemption Delay" in Euromicro Conference on Real-Time Systems (ECRTS), (Palma de Mallorca, Spain), Juli 2005. |
|
|
|
|
@inproceedings{SSE05:SchedAnalyRealtSyste, address = {Palma de Mallorca, Spain}, |
The listed material is protected by copyright. The corresponding copyright must be observed.
|
Simon Schliecker and Rolf Ernst, "Real-Time Performance Analysis of Multiprocessor Systems with Shared Memory", ACM Transactions on Embedded Computing Systems (Special Issue on Model Driven Embedded System Design), vol. 10-2, No. 22, Dezember 2010. |
|
|
|
|
@article{SE10:RealTPerfoAnalyMulti, author = {Simon Schliecker and Rolf Ernst}, |
|||
|
Simon Schliecker, Mircea Negrean and Rolf Ernst, "Response Time Analysis in Multicore ECUs with Shared Resources", IEEE Transactions on Industrial Informatics, vol. 5, No. 4, November 2009. |
|
|
|
|
@article{Sch09:RespoAnalyMultiShare, author = {Simon Schliecker and Mircea Negrean and Rolf Ernst}, |
|||
|
Simon Schliecker, Jonas Rox, Rafik Henia, Razvan Racu, Arne Hamann and Rolf Ernst, "Formal Performance Analysis for Real-Time Heterogeneous Embedded Systems", in Model-Based Design of Heterogeneous Embedded Systems (Gabriela Nicolescu and Pieter J Mosterman, Ed.), chapter 3, pp. 57-92, CRC Press, November 2009. |
|
|
|
|
@incollection{SRH+08:ModelDesigHeterEmbed, author = {Simon Schliecker and Jonas Rox and Rafik Henia and Razvan Racu and Arne Hamann and Rolf Ernst}, |
|||
|
Simon Schliecker, Jonas Rox, Mircea Negrean, Kai Richter, Marek Jersak and Rolf Ernst, "System Level Performance Analysis for Real-Time Automotive Multi-Core and Network Architectures", IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 28, No. 7, pp. 979-992, Juli 2009. |
|
|
|
|
@article{SRN+08:SysteLevelPerfoAnaly, author = {Simon Schliecker and Jonas Rox and Mircea Negrean and Kai Richter and Marek Jersak and Rolf Ernst}, |
|||
|
Simon Perathoner, Ernesto Wandeler, Lothar Thiele, Arne Hamann, Simon Schliecker, Rafik Henia, Razvan Racu, Rolf Ernst and Michael González Harbour, "Influence of different abstractions on the performance analysis of distributed hard real-time systems", Journal Design Automation for Embedded Systems (available as online first, April 2008), vol. 13, No. 1, pp. 27-49, Juni 2009. |
|
|
|
|
@article{PWT+08:Infludiffeabstrperfo, author = {Simon Perathoner and Ernesto Wandeler and Lothar Thiele and Arne Hamann and Simon Schliecker and Rafik Henia and Razvan Racu and Rolf Ernst and Michael González Harbour}, |
The listed material is protected by copyright. The corresponding copyright must be observed.
|
Daniel Thiele, "Empirische Untersuchung des Timings von Speicherzugriffen in Multiprozessorsystemen", Studienarbeit, Institute of Computer and Network Engineering, Technische Universität Braunschweig, November 2008. |
|
||
|
@masterthesis{Thi08:EmpirUnterTiminSpeic, author = {Daniel Thiele}, |
|||
|
Simon Schliecker, Mircea Negrean and Rolf Ernst, "Reliable Performance Analysis of a Multicore Multithreaded System-On-Chip (with appendix)", No. 22837, Technische Universität Braunschweig, 2008. |
|
|
|
|
@techreport{SNE08:ReliaPerfoAnalyMulti, author = {Simon Schliecker and Mircea Negrean and Rolf Ernst}, |
|||
|
Simon Schliecker and Rolf Ernst, "Compositional Path Latency Computation with Local Busy Times", No. IDA-08-01, Technical University Braunschweig, Braunschweig, Germany, Januar 2008. |
|
|
|
|
@techreport{SE08:CompoLatenCompuLocal, address = {Braunschweig, Germany}, |
|||
|
Mircea Negrean, "Analytical Performance Evaluation of an ST Microelectronics Multiprocessing Platform", Master Thesis, Technische Universität Braunschweig, Germany, Mai 2007. |
|
||
|
@masterthesis{Neg07:AnalyPerfoEvaluMicro, address = {Germany}, |
|||
|
Simon Schliecker, Matthias Ivers and Rolf Ernst, "A Proof for Memory Access Patterns for the Analysis of MPSoCs", No. IDA-2006-01, Institute for Computer and Communication Network Engineering, Braunschweig, Germany, April 2006, This TR contains a supplement proof for. |
|
|
|
|
@techreport{SIE06:ProofMemorAccesPatte, address = {Braunschweig, Germany}, |
Institute of Computer and Network Engineering
Hans-Sommer-Street 66
38106 Braunschweig
Phone: +49 (0)531 391-3734
Fax: +49 (0)531 391-4587
