Efficient buffer capacity and scheduler setting computation for soft real-time stream processing applications

ABSTRACT

Soft real-time applications that process data streams can often be intuitively described as dataflow process networks. In this paper we present a novel analysis technique to compute conservative estimates of the required buffer capacities in such process networks. With the same analysis technique scheduler settings can be verified. Unlike many other soft real-time analysis techniques, it is guaranteed that the desired throughput is obtained for the input stream that is used to characterize the application.

Experiments with artificial test-cases indicate that the computed FIFO capacities become more conservative if the desired throughput gets closer to the maximum throughput. The run-time of our algorithm for an H263 video decoder test-case was 14 seconds.

REFERENCES

• 1: Ravindra K. Ahuja , Thomas L. Magnanti , James B. Orlin, Network flows: theory, algorithms, and applications, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 2: Marco Bekooij , Sonali Parmar , Jef van Meerbergen, Performance guarantees by simulation of process, Proceedings of the 2005 workshop on Software and compilers for embedded systems, p.10-19, September 29-October 01, 2005, Dallas, Texas [doi>10.1145/1140389.1140391]
• 3: G. Bilsen, M. Engels, R. Lauwereins, and J. Peperstraete. Cyclo-Static Dataflow. IEEE Transactions on Signal Processing, 44(2):397--408, 1996.
• 4: Ali Dasdan, Experimental analysis of the fastest optimum cycle ratio and mean algorithms, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.9 n.4, p.385-418, October 2004 [doi>10.1145/1027084.1027085]
• 5: Adam Donlin, Transaction level modeling: flows and use models, Proceedings of the 2nd IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, September 08-10, 2004, Stockholm, Sweden [doi>10.1145/1016720.1016742]
• 6: Om Prakash Gangwal , André Nieuwland , Paul Lippens, A scalable and flexible data synchronization scheme for embedded HW-SW shared-memory systems, Proceedings of the 14th international symposium on Systems synthesis, September 30-October 03, 2001, Montréal, P.Q., Canada [doi>10.1145/500001.500003]
• 7: Kees Goossens , John Dielissen , Andrei Radulescu, Æthereal Network on Chip: Concepts, Architectures, and Implementations, IEEE Design & Test, v.22 n.5, p.414-421, September 2005 [doi>10.1109/MDT.2005.99]
• 8: E. A. de Kock , W. J. M. Smits , P. van der Wolf , J.-Y. Brunel , W. M. Kruijtzer , P. Lieverse , K. A. Vissers , G. Essink, YAPI: application modeling for signal processing systems, Proceedings of the 37th conference on Design automation, p.402-405, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337511]
• 9: Hermann Kopetz, Real-Time Systems: Design Principles for Distributed Embedded Applications, Kluwer Academic Publishers, Norwell, MA, 1997
• 10: E. A. Lee and T. M. Parks. Dataflow Process Networks. Proceedings of the IEEE, 83(5), May 1995.
• 11: Min (Leon) Li , Tanja Van Achteren , Erik Brockmeyer , Francky Catthoor, Statistical Performance Analysis and Estimation of Coarse Grain Parallel Multimedia Processing System, Proceedings of the 12th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS'06), p.277-288, April 04-07, 2006 [doi>10.1109/RTAS.2006.41]
• 12: Alexander Maxiaguine , Yongxin Zhu , Samarjit Chakraborty , Weng-Fai Wong, Tuning SoC platforms for multimedia processing: identifying limits and tradeoffs, Proceedings of the 2nd IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, September 08-10, 2004, Stockholm, Sweden [doi>10.1145/1016720.1016753]
• 13: Peggy B. McGee , Steven M. Nowick , E. G. Coffman, Jr., Efficient performance analysis of asynchronous systems based on periodicity, Proceedings of the 3rd IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, September 19-21, 2005, Jersey City, NJ, USA [doi>10.1145/1084834.1084892]
• 14: C. W. Mercer, S. Savage, and H. Tokuda. Processor Capacity Reserves: Operating System Support for Multimedia Systems. In Proc. IEEE International Conference of Multimedia Computing and Systems. IEEE Computer Society Press, 1994.
• 15: Thomas Martyn Parks, Bounded scheduling of process networks, University of California at Berkeley, Berkeley, CA, 1996
• 16: B. D. Theelen. Performance Modelling for System-Level Design. PhD thesis, Eindhoven University of Technology, 2004.
• 17: Maarten Wiggers , Marco Bekooij , Pierre Jansen , Gerard Smit, Efficient computation of buffer capacities for multi-rate real-time systems with back-pressure, Proceedings of the 4th international conference on Hardware/software codesign and system synthesis, October 22-25, 2006, Seoul, Korea [doi>10.1145/1176254.1176260]
• 18: Maarten H. Wiggers , Marco J. G. Bekooij , Pierre G. Jansen , Gerard J. M. Smit, Efficient Computation of Buffer Capacities for Cyclo-Static Real-Time Systems with Back-Pressure, Proceedings of the 13th IEEE Real Time and Embedded Technology and Applications Symposium, p.281-292, April 03-06, 2007 [doi>10.1109/RTAS.2007.12]
• 19: M. Wiggers, M. Bekooij, and G. Smit. Efficient Computation of Buffer Capacities for Cyclo-Static Dataflow Graphs. Technical Report TR-CTIT-06-70, University of Twente, November 2006.