Dataflow models for shared memory access latency analysis

ABSTRACT

Performance analysis of applications in multi-core platforms is challenging because of temporal interference while accessing shared resources. Especially, memory arbiters introduce a non-constant delay which significantly influences the execution time of a task. In this paper, we selected a priority-based budget scheduler as memory arbiter which bounds temporal interference by construction and is well suited for bursty service provision. While existing performance analysis approaches assume a constant memory access latency leading to high overestimation, we propose in this paper a conservative data flow model for this scheduler, in which the history of memory accesses is considered.

In a case study with an MP3-decoder for an ARM7 processor, we show that using a constant memory access latency for the selected scheduler results in an overestimation of three order of magnitudes. Compared to simulation, the proposed data flow model shows an overestimation of less than 3% while in previous work the overestimation was up to 104%. Furthermore, the proposed approach improves the performance by about 20% compared to a time-division-multiplex scheduler.

REFERENCES

• 1: B. Akesson, L. Steffens, E. Strooisma, and K. Goossens. Real-Time Scheduling Using Credit-Controlled Static-Priority Arbitration. In RTCSA, Aug. 2008.
• 2: A. Andrei, P. Eles, Z. Peng, and J. Rosen. Predictable implementation of real-tim applications on multiprocessor system-on-chip. In Int' Conference on VLSI Design, pages 103--110, 2008.
• 3: M. Bekooij, R. Hoes, O. Moreira, P. Poplavko, M. Pastrnak, B. Mesman, J. D. Mol, S. Stuijk, V. Gheorghita, and J. v. Meerbergen. Dynamic and Robust Streaming in and between Connected Consumer-Electronic Devices, chapter 81, pages 81--108. Springer, 2005.
• 4: M. Bekooij, M. Wiggers, and J. v. Meerbergen. Efficient Buffer Capacity and Scheduler Setting Computation for Soft Real-Time Stream Processing Applications. In Proc. Int'l Workshop on Software and Compilers for Embedded Systems (SCOPES), April 2007.
• 5: G. C. Buttazzo. Hard Real-time Computing Systems: Predictable Scheduling Algorithms and Applications. Springer, 2004.
• 6: R. L. Cruz. A Calculus for Netork Delay, Part II: Network Analysis. IEEE Transactions on Information Theory, 37(1):132--141, January 1991.
• 7: F. Harmsze, A. Timmer, and J. van Meerbergen. Memory Arbitration can Cache Management in Stream-Based Systems. In DATE, pages 257--262, 2000.
• 8: J. L. Hennessy and D. A. Patterson. Computer Architecture - A Quantitative Approach. Morgan Kaufmann Publishers, 1996.
• 9: M. Jersak, K. Richter, and R. Ernst. Performance Analysis of Complex Embedded Systems. International Journal of Embedded Systems, 1(1-2):33--49, 2005.
• 10: E. A. Kock, G. Essink, W. J. M. Smits, P. van der Wolf, J.-Y. Brunel, W. M. Kruijtzer, P. Lieverse, and K. A. Vissers. YAPI: Application Modeling for Signal Processing Systems. In Proc. Design Automation Conference (DAC), pages 402--405, Los Angeles, June 2000.
• 11: P. Kolling, C. Osborne, and T. Henriksson. Heterogeneous multi-core platform for consumer multimedia applications. In DATE, 2009.
• 12: C. Liu and J. W. Layland. Scheduling algorithms for multiprogramming in a hard real-time environment. Journal of the ACM, 20(1):46--61, 1973.
• 13: A. Maxiaguine, Y. Zhu, S. Chakraborty, and W.-F. Wong. Tuning SoC Platforms for Multimedia Processing: Identifying Limits and Tradeoffs. In Proc. Int'l Conference on Hardware-Software Codesign and System Synthesis (CODES+ISSS), pages 128--133, September 2004.
• 14: S. Schliecker, M. Ivers, and R. Ernst. Integrated analysis of communicating tasks in MPSoCs. In CODES+ISSS, pages 288--293, 2006.
• 15: www.cl.cam.ac.uk/~mwd24/phd/swarm.html.
• 16: L. Steffens, M. Agarwal, and P. van der Wolf. Real-time analysis for memory access in media processing socs: A practical approach. In ECRTS, pages 255--265, 2008.
• 17: M. Steine and M. Bekooij. A priority-based budget scheduler with conservative data flow model. In Euromicro Conference on Digital System Design; accepted for publication, 2009.
• 18: D. Stiliadis and A. Varma. A General Model for Analysis of Traffic Scheduling Algorithms. IEEE/ACM Transactions on Networking, 6(5):611--624, October 1998.
• 19: V. Suhendra and T. Mitra. Exploring locking & partitioning for predictable shared. In Design Automation Conference, pages 300--303, 2008.
• 20: L. Thiele and R. Wilhelm. Design for timing predictability. Real-Time Systems, 28(2/3):157--177, 2004.
• 21: http://www.underbit.com/products/mad/.
• 22: M. Wiggers, M. Bekooij, and G. Smit. Modelling Run-Time Arbitration by Latency-Rate Servers in Data Flow Graphs. In Proc. Int'l Workshop on Software and Compilers for Embedded Systems (SCOPES), April 2007.
• 23: R. Wilhelm, J. Engblom, A. Ermedahl, N. Holsti, S. Thesing, D. Whalley, G. Bernat, C. Ferdinand, R. Heckmann, T. Mitra, F. Mueller, I. Puaut, P. Puschner, J. Staschulat, and P. Stenstrom. The Worst-Case Execution Time Problem - Overview of Methods and Survey of Tools. ACM Transactions on Embedded Computing Systems(TECS), 7(3):1--53, 2008.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

General Terms:
Performance, Reliability, Verification

Keywords:
dataflow model, memory accesses, multiprocessor performance analysis, real-time