Abstract
Predicting timing behavior is key to reliable real-time system design and verification, but becomes increasingly difficult for current multiprocessor systems on chip. The integration of formerly separate functionality into a single multicore system introduces new intercore timing dependencies resulting from the common use of the now shared resources. This feedback of system timing on local timing makes traditional performance analysis approaches inappropriate.
This article presents a general methodology to model the shared resource traffic and consider its effect on the local task execution. The aggregate busy time captures the timing of multiple accesses to a shared memory far better than the traditional models that focus on the timing of individual events. An iterative approach is proposed to tackle the analysis dependencies that exist in systems with event-driven task activation and dynamic resource arbitration.
- Adiletta, M., Rosenbluth, M., Bernstein, D., Wolrich, G., and Wilkinson, H. 2002. The next generation of Intel IXP network processors. Network Process. 6, 3.Google Scholar
- Albers, K., Bodmann, F., and Slomka, F. 2006. Hierarchical event streams and event dependency graphs: A new computational model for embedded real-time systems. In Proceedings of the 18th Euromicro Conference on Real-Time Systems. IEEE, Los Alamitos, CA, 97--106. Google ScholarDigital Library
- Altmeyer, S. and Burguiére, C. 2009. A new notion of useful cache block to improve the bounds of cache-related preemption delay. In Proceedings of the 21st Euromicro Conference on Real-Time Systems. IEEE, Los Alamitos, CA, 109--118. Google ScholarDigital Library
- Andrei, A., Eles, P., Peng, Z., and Rosen, J. 2008. Predictable implementation of real-time applications on multiprocessor systems-on-chip. In Proceedings of the 21st International Conference on VLSI Design. IEEE, Los Alamitos, CA. Google ScholarDigital Library
- Barre, J., Rochange, C., and Sainrat, P. 2008. A predictable simultaneous multithreading scheme for hard real-time. In Proceedings of the Conference on Architecture of Computing Systems. Springer-Verlag, Berlin, 161. Google ScholarDigital Library
- Bekooij, M., Moreira, O., Poplavko, P., Mesman, B., Pastrnak, M., and van Meerbergen, J. 2004. Predictable embedded multiprocessor system design. In Proceedings of the SCOPES Workshop. Springer-Verlag, Berlin.Google ScholarCross Ref
- Bertogna, M. and Cirinei, M. 2007. Response-time analysis for globally scheduled symmetric multiprocessor platforms. In Proceedings of the 28th Real-Time Systems Symposium. IEEE, Los Alamitos, CA, 149--160. Google ScholarDigital Library
- Bletsas, K. and Audsley, N. 2005. Extended analysis with reduced pessimism for systems with limited parallelism. In Proceedings of the 11th International Conference on Embedded and Real-Time Computing Systems and Applications. IEEE, Los Alamitos, CA, 525--531. Google ScholarDigital Library
- Brandenburg, B., Calandrino, J., Block, A., Leontyev, H., and Anderson, J. 2008. Realtime synchronization on multiprocessors: to block or not to block, to suspend or spin? In Proceedings of the Real-Time and Embedded Technology and Applications Symposium. IEEE, Los Alamitos, CA, 342--353. Google ScholarDigital Library
- Busquets-Mataix, J., Serrano, J., Ors, R., Gil, P., and Wellings, A. 1996. Adding instruction cache effect to schedulability analysis of preemptive real-time systems. In Proceedings of the 2nd Real-Time Technology and Applications Symposium. IEEE, Los Alamitos, CA. Google ScholarDigital Library
- Chakraborty, S., Kunzli, S., and Thiele, L. 2003. A general framework for analyzing system properties in platform-based embedded system designs. In Proceedings of the Design, Automation and Test in Europe. IEEE, Los Alamitos, CA, 190--195. Google ScholarDigital Library
- Crowley, P. and Baer, J. 2003. Worst-case execution time estimation for hardware-assisted multithreaded processors. In Proceedings of the 2nd Workshop on Network Processors. IEEE, Los Alamitos, CA, 36--47.Google Scholar
- Ericsson, C., Wall, A., and Yi, W. 1998. Timed automata as task models for event-driven systems. In Proceedings of Nordic Workshop on Programming Theory. vol. 63.Google Scholar
- Gary, S., Ippolito, P., Gerosa, G., Dietz, C., Eno, J., and Sanchez, H. 1994. PowerPC 603, a microprocessor for portable computers. IEEE Des. Test Comput. 11, 4, 14--23. Google ScholarDigital Library
- González Harbour, M., Gutiérrez García, J. J., Palencia Gutiérrez, J. C., and Drake Moyano, J. M. 2001. Mast: Modeling and analysis suite for real-time applications. In Proceedings of 13th Euromicro Conference on Real-Time Systems. IEEE, Los Alamitos, CA, 125--134. Google ScholarDigital Library
- Gresser, K. 1993. An event model for deadline verification of hard real-time systems. In Proceedings of the 5th Euromicro Workshop on Real-Time Systems. IEEE, Los Alamitos, CA, 118--123.Google ScholarCross Ref
- Gutiérrez, J., García, J., and Harbour, M. 1997. On the schedulability analysis for distributed hard real-time systems. In Proceedings of the 9th Euromicro Workshop on Real-Time Systems. IEEE, Los Alamitos, CA, 136--143.Google Scholar
- Hendriks, M. and Verhoef, M. 2006. Timed automata based analysis of embedded system architectures. In Proceedings of the Workshop on Parallel and Distributed Real-Time Systems. IEEE, Los Alamitos, CA. Google ScholarDigital Library
- Henriksson, T., van der Wolf, P., Jantsch, A., and Bruce, A. 2007. Network calculus applied to verification of memory access pin SoCs. In Proceedings of the Workshop on Embedded Systems for Real-Time Multimedia. IEEE, Los Alamitos, CA.Google Scholar
- Henzinger, T. and Matic, S. 2006. An interface algebra for real-time components. In Proceedings of the Real-Time and Embedded Technology and Applications Symposium. IEEE, Los Alamitos, CA. Google ScholarDigital Library
- Ivers, M., Janarthanan, B., and Ernst, R. 2007. Predictable performance on multithreaded architectures for streaming protocol processing. In Proceedings of the 15th International Conference on Real-Time and Network Systems. http://rtns07.irisa.fr/fichiers/actes.pdf.Google Scholar
- Joseph, M. and Pandya, P. 1986. Finding response times in a real-time system. Comput. J. 29, 5, 390.Google ScholarCross Ref
- Kirner, R. and Puschner, P. 2008. Obstacles in worst-case execution time analysis. In Proceedings of the 11th International Symposium on Object Oriented Real-Time Distributed Computing. IEEE, Los Alamitos, CA, 333--339. Google ScholarDigital Library
- Lee, C., Lee, K., Hahn, J., Seo, Y., Min, S., Ha, R., Hong, S., Park, C., Lee, M., and Kim, C. 2001. Bounding cache-related preemption delay for real-time systems. IEEE Trans. Software Eng. 27, 9, 805--826. Google ScholarDigital Library
- Lee, E., Neuendorffer, S., and Wirthlin, M. 2003. Actor-oriented design of embedded hardware and software systems. J. Circuits Syst. Comput. 12, 3, 231--260.Google ScholarCross Ref
- Lehoczky, J. 1990. Fixed priority scheduling of periodic task sets with arbitrary deadlines. In Proceedings of the 11th Real-Time Systems Symposium. IEEE, Los Alamitos, CA, 201--209.Google ScholarCross Ref
- Mok, A. and Chen, D. 1997. A multi-frame model for real-time tasks. IEEE Trans. Software Eng. 23, 10, 635--645. Google ScholarDigital Library
- Palencia, J. and Harbour, M. 1998. Schedulability analysis for tasks with static and dynamic offsets. In Proceedings of the 19th Real-Time Systems Symposium. IEEE, Los Alamitos, CA. Google ScholarDigital Library
- Paulin, P., Pilkington, C., and Bensoudane, E. 2002. StepNP: A system-level exploration platform for network processors. IEEE Des. Test Comput. 19, 6, 17--26. Google ScholarDigital Library
- Petters, S. and Farber, G. 2001. Scheduling analysis with respect to hardware related preemption delay. In Proceedings of the Workshop on Real-Time Embedded Systems. IEEE, Los Alamitos, CA.Google Scholar
- Pop, P., Eles, P., and Peng, Z. 2003. Schedulability analysis and optimization for the synthesis of multi-cluster distributed embedded systems. In Proceedings of the Design, Automation and Test in Europe Conference and Exhibition. IEEE, Los Alamitos, CA, 184--189. Google ScholarDigital Library
- Pop, T., Pop, P., Eles, P., Peng, Z., and Andrei, A. 2006. Timing analysis of the FlexRay communication protocol. In Proceedings of 18th EuroMicro Conference on Real-Time Systems. IEEE, Los Alamitos, CA, 203--213. Google ScholarDigital Library
- Richter, K., Racu, R., and Ernst, R. 2003. Scheduling analysis integration for heterogeneous multiprocessor SoC. In Proceedings of the 24th Real-Time Systems Symposium. IEEE, Los Alamitos, CA. Google ScholarDigital Library
- Schliecker, S., Ivers, M., and Ernst, R. 2006a. Integrated analysis of communicating tasks in MPSoCs. In Proceedings of the 4th International Conference on Hardware/Software Co-Design and System Synthesis. ACM, New York, 288--293. Google ScholarDigital Library
- Schliecker, S., Ivers, M., and Ernst, R. 2006b. Memory access patterns for the analysis of MPSoCs. In Proceedings of the North-East Workshop on Circuits and Systems. IEEE, Los Alamitos, CA, 249--252.Google Scholar
- Schliecker, S., Negrean, M., and Ernst, R. 2009. Response-time analysis in multicore ecus with shared resources. IEEE Trans. Ind. Inf. 5, 4.Google ScholarCross Ref
- Schliecker, S., Negrean, M., and Ernst, R. 2010. Bounding the shared resource load for the performance analysis of multiprocessor systems. In Proceedings of the Design, Automation and Test in Europe. IEEE, Los Alamitos, CA. Google ScholarDigital Library
- Schliecker, S., Negrean, M., Nicolescu, G., Paulin, P., and Ernst, R. 2008. Reliable performance analysis of a multicore multithreaded system-on-chip. In Proceedings of the 6th International Conference on Hardware/Software Co-Design and System Synthesis. ACM, New York. Google ScholarDigital Library
- Schliecker, S., Rox, J., Ivers, M., and Ernst, R. 2008. Providing accurate event models for the analysis of heterogeneous multiprocessor systems. In Proceedings of the 6th International Conference on Hardware/Software Co-Design and System Synthesis. ACM, New York. Google ScholarDigital Library
- Schoeberl, M. and Puschner, P. 2009. Is chip-multiprocessing the end of real-time scheduling? In Proceedings of the 9th International Workshop on Worst-Case Execution Time Analysis. http://www.jopdesign.com/doc/cmp_wcet2009.pdf.Google Scholar
- Segars, S. 1998. The ARM9 family-high performance microprocessors for embedded applications. In Proceedings of the International Conference on Computer Design: VLSI in Computers and Processors. IEEE, Los Alamitos, CA, 230--235. Google ScholarDigital Library
- Staschulat, J. 2005. Symta/p - Performance Verification for Complex Embedded Systems v1.2. http://sourceforge.net/projects/symtap/.Google Scholar
- Staschulat, J. and Ernst, R. 2007. Scalable precision cache analysis for real-time software. ACM Trans. Embedded Comput. Syst. 6, 4. Google ScholarDigital Library
- Staschulat, J., Schliecker, S., and Ernst, R. 2005. Scheduling analysis of real-time systems with precise modeling of cache related preemption delay. In Proceedings of the Euromicro Conference on Real-Time Systems. IEEE, Los Alamitos, CA, 41--48. Google ScholarDigital Library
- Stein, S., Diemer, J., Ivers, M., Schliecker, S., and Ernst, R. 2008. On the Convergence of the SymTA/S Analysis. TU Braunschweig, Braunschweig, Germany.Google Scholar
- Stohr, J., Bulow, A., and Farber, G. 2005. Bounding worst-case access times in modern multiprocessor systems. In Proceedings of the 17th Euromicro Conference on Real-Time Systems. IEEE, Los Alamitos, CA. Google ScholarDigital Library
- Tindell, K., Burns, A., and Wellings, A. 1994. An extendible approach for analyzing fixed priority hard real-time tasks. Real-Time Syst. 6, 2, 133--151. Google ScholarDigital Library
- Tindell, K. and Clark, J. 1994. Holistic schedulability analysis for distributed hard real-time systems. Microprocess. Microprogram. 40, 2-3, 117--134. Google ScholarDigital Library
- Wilhelm, R., Engblom, J., Ermedahl, A., Holsti, N., Thesing, S., Whalley, D., Bernat, G., Ferdinand, C., Heckmann, R., et al. 2008. The worst-case execution time problem—overview of methods and survey of tools. ACM Trans. Embed. Comput. Syst. 7, 36, 1--53. Google ScholarDigital Library
- Wilhelm, R., Grund, D., Reineke, J., Schlickling, M., Pister, M., and Ferdinand, C. 2009. Memory hierarchies, pipelines, and buses for future architectures in time-critical embedded systems. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 28, 7, 966--978. Google ScholarDigital Library
Index Terms
- Real-time performance analysis of multiprocessor systems with shared memory
Recommendations
A real-time Java chip-multiprocessor
Chip-multiprocessors are an emerging trend for embedded systems. In this article, we introduce a real-time Java multiprocessor called JopCMP. It is a symmetric shared-memory multiprocessor, and consists of up to eight Java Optimized Processor (JOP) ...
Performance of Multistage Bus Networks for a Distributed Shared Memory Multiprocessor
A Multistage Bus Network (MBN) is proposed in this paper to overcome some of the shortcomings of the conventional multistage interconnection networks (MINs), single bus, and hierarchical bus interconnection networks. The MBN consists of multiple stages ...
Communication-aware task assignment algorithm for MPSoC using shared memory
In a Multi-Processor System-on-a-Chip (MPSoC) based on Network-on-Chip (NoC), which processes massive data in a distributed fashion, communication is concentrated on shared memory. This paper proposes an assignment algorithm that can minimize the total ...
Comments