Modular performance analysis of cyclic dataflow graphs

ABSTRACT

Applications for parallel and distributed embedded systems are often specified as dataflow graphs with dependency cycles. Examples of corresponding models of computation are marked graphs or synchronous dataflow (SDF) graphs. Performance analysis is often used in the exploration of different implementation alternatives or in order to provide guarantees on the timing behavior. This paper describes a new approach to the modular performance analysis of cyclic dataflow graphs such as SDF graphs as existing component-based analysis methods are not able to faithfully deal with cycles in the event flow. The new method results in tight bounds on essential quantities like buffer sizes, end-to-end delays and throughput. Because of the generality of the approach, one can analyze not only systems that can be modeled as marked graphs but also implementations that contain buffers with finite sizes, that produce system-wide back-pressure caused by blocking write semantics. The embedding of the novel approach into a modular performance analysis method allows the analysis of distributed implementations that use resource sharing mechanisms such as fixed-priority scheduling and time division multiple access (TDMA). The paper presents the new models and methods as well as experimental results.

REFERENCES

• 1: F.L. Baccelli, G.J. Olsder, J.P. Quadrat, and G. Cohen, Synchronization and Linearity: An Algebra for Discrete Event Systems, Wiley, 1992.
• 2: S. S. Bhattacharyya, P. K. Murthy, and E. A. Lee, Synthesis of embedded software from synchronous dataflow specifications, J. VLSI Signal Process. Syst. 21 (1999), no. 2, 151--166.
• 3: A. Bose, X. Jiang, B. Liu, and G. Li, Analysis of manufacturing blocking systems with network calculus, Perform. Eval. 63 (2006), no. 12, 1216--1234.
• 4: A. Bouillard, L.T.X. Phan, and S. Chakraborty, Lightweight modeling of complex state dependencies in stream processing systems, Real-Time and Embedded Technology and Applications Symposium, 2009. RTAS 2009. 15th IEEE, April 2009, pp. 195--204.
• 5: S. Chakraborty and D. L. Dill, Approximate algorithms for time separation of events, ICCAD '97: Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, 1997, pp. 190--194.
• 6: S. Chakraborty, S. Kunzli, and L. Thiele, A general framework for analysing system properties in platform-based embedded system designs, DATE '03: Proceedings of the conference on Design, Automation and Test in Europe, 2003, p. 10190.
• 7: C.S. Chang, Performance Guarantees in Communication Networks, Springer-Verlag, 2000.
• 8: G. Cohen, D. Dubois, J. Quadrat, and M. Viot, A linear-system-theoretic view of discrete-event processes and its use for performance evaluation in manufacturing, Automatic Control, IEEE Transactions on 30 (1985), no. 3, 210--220.
• 9: R.L. Cruz, A calculus for network delay. i. network elements in isolation, Information Theory, IEEE Transactions on 37 (1991), no. 1, 114--131.
• 10: B.A. Davey and H.A. Priestley, Introduction to lattices and order, 2nd ed., Cambridge University Press, 2002.
• 11: H. Hulgaard and S.M. Burns, Bounded delay timing analysis of a class of csp programs with choice, Advanced Research in Asynchronous Circuits and Systems, 1994., Proceedings of the International Symposium on, Nov 1994, pp. 2--11.
• 12: M. Jersak and R. Ernst, Enabling scheduling analysis of heterogeneous systems with multi-rate data dependencies and rate intervals, DAC '03: Proceedings of the 40th conference on Design automation, 2003, pp. 454--459.
• 13: M. Jersak, K. Richter, and R. Ernst, Performance analysis for complex embedded applications, International Journal of Embedded Systems 1 (2005), no. 1/2, 33--49.
• 14: B. Jonsson, S. Perathoner, L. Thiele, and W. Yi, Cyclic dependencies in modular performance analysis, EMSOFT '08: Proceedings of the 8th ACM international conference on Embedded software, 2008, pp. 179--188.
• 15: J.-Y. Le Boudec and P. Thiran, Network Calculus: A Theory of Deterministic Queuing Systems for the Internet, Springer, 2001.
• 16: E.A. Lee and D.G. Messerschmitt, Synchronous data flow, Proceedings of the IEEE 75 (1987), no. 9, 1235--1245.
• 17: E.A. Lee and T.M. Parks, Dataflow process networks, Proceedings of the IEEE 83 (1995), no. 5, 773--801.
• 18: R. Lu and C.-K. Koh, Performance analysis of latency-insensitive systems, Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on 25 (2006), no. 3, 469--483.
• 19: A. Maxiaguine, S. Kunzli, and L. Thiele, Workload characterization model for tasks with variable execution demand, DATE '04: Proceedings of the conference on Design, automation and test in Europe, 2004, p. 21040.
• 20: P. B. McGee, S. M. Nowick, and E. G. Coffman, Jr., Efficient performance analysis of asynchronous systems based on periodicity, CODES+ISSS '05: Proceedings of the 3rd IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, 2005, pp. 225--230.
• 21: O. Moreira, F. Valente, and M. Bekooij, Scheduling multiple independent hard-real-time jobs on a heterogeneous multiprocessor, EMSOFT '07: Proceedings of the 7th ACM & IEEE international conference on Embedded software, 2007, pp. 57--66.
• 22: T. Murata, Petri nets: Properties, analysis and applications, Proceedings of the IEEE 77 (1989), no. 4, 541--580.
• 23: C. D. Nielsen and M. Kishinevsky, Performance analysis based on timing simulation, DAC '94: Proceedings of the 31st annual Design Automation Conference, 1994, pp. 70--76.
• 24: T. Pop, P. Eles, and Z. Peng, Holistic scheduling and analysis of mixed time/event-triggered distributed embedded systems, CODES '02: Proceedings of the tenth international symposium on Hardware/software codesign, 2002, pp. 187--192.
• 25: P. Poplavko, T. Basten, M. Bekooij, J. van Meerbergen, and B. Mesman, Task-level timing models for guaranteed performance in multiprocessor networks-on-chip, CASES '03: Proceedings of the 2003 international conference on Compilers, architecture and synthesis for embedded systems, 2003, pp. 63--72.
• 26: R. Reiter, Scheduling parallel computations, J. ACM 15 (1968), no. 4, 590--599.
• 27: S. Schliecker, S. Stein, and R. Ernst, Performance analysis of complex systems by integration of dataflow graphs and compositional performance analysis, DATE '07: Proceedings of the conference on Design, automation and test in Europe, 2007, pp. 273--278.
• 28: S. Sriram and S. S. Bhattacharyya, Embedded multiprocessors: Scheduling and synchronization, CRC Press, 2000.
• 29: L. Thiele, S. Chakraborty, M. Gries, and S. Kunzli, A framework for evaluating design tradeoffs in packet processing architectures, DAC '02: Proceedings of the 39th conference on Design automation, 2002, pp. 880--885.
• 30: K. Tindell and J. Clark, Holistic schedulability analysis for distributed hard real-time systems, Microprocess. Microprogram. 40 (1994), no. 2-3, 117--134.
• 31: E. Wandeler, L. Thiele, M. Verhoef, and P. Lieverse, System architecture evaluation using modular performance analysis: a case study, Int. J. Softw. Tools Technol. Transf. 8 (2006), no. 6, 649--667.
• 32: M. Wiggers, M. Bekooij, P. Jansen, and G. Smit, Efficient computation of buffer capacities for multi-rate real-time systems with back-pressure, CODES+ISSS '06: Proceedings of the 4th international conference on Hardware/software codesign and system synthesis, 2006, pp. 10--15.
• 33: A. Xie, S. Kim, and P. A. Beerel, Bounding average time separations of events in stochastic timed petri nets with choice, ASYNC '99: Proceedings of the 5th International Symposium on Advanced Research in Asynchronous Circuits and Systems, 1999, p. 94.

INDEX TERMS

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

General Terms:
Design, Performance, Theory, Verification

Keywords:
dioid algebras, marked graphs, real-time calculus, real-time systems, synchronous dataflow