Buffer minimization in earliest-deadline first scheduling of dataflow graphs

ABSTRACT

Symbolic schedulability analysis of dataflow graphs is the process of synthesizing the timing parameters (i.e. periods, phases, and deadlines) of actors so that the task system is schedulable and achieves a high throughput when using a specific scheduling policy. Furthermore, the resulted schedule must ensure that communication buffers are underflow- and overflow-free. This paper describes a (partitioned) earliest-deadline first symbolic schedulability analysis of dataflow graphs that minimizes the buffering requirements.

Our scheduling analysis consists of three major steps. (1) The construction of an abstract affine schedule of the graph that excludes overflow and underflow exceptions and minimizes the buffering requirements assuming some precedences between jobs. (2) Symbolic deadlines adjustment that guarantees precedences without the need for lock-based synchronizations. (3) The concretization of the affine schedule using a symbolic, fast-converging, processor-demand analysis for both uniprocessor and multiprocessor systems. Experimental results show that our technique improves the buffering requirements in many cases.

References

1. M. Bamakhrama and T. Stefanov. Hard-real-time scheduling of data-dependent tasks in embedded streaming applications. In Proceedings of the 9th ACM International Conference on Embedded Software, pages 195--204, 2011.
2. M. A. Bamakhrama and T. Stefanov. Managing latency in embedded streaming applications under hard-real-time scheduling. In Proceedings of the 8th IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis, pages 83--92, 2012.
3. S. Baruah, V. Bonifaci, A. Marchetti-Spaccamela, and S. Stiller. Implementation of speedup-optimal global EDF schedulability test. In Proceedings of the 21st Euromicro Conference on Real-Time Systems, pages 259--268, 2009.
4. S. K. Baruah and N. W. Fisher. The partitioned dynamic-priority scheduling of sporadic task systems. Real-Time Syst., 36(3):199--226, 2007.
5. M. Bertogna and S. Baruah. Tests for global EDF schedulability analysis. J. Syst. Archit., 57(5):487--497, 2011.
6. G. Bilsen, M. Engels, R. Lauwereins, and J. Peperstraete. Cycle-static dataflow. IEEE Transactions on Signal Processing, 44:397--408, 1996.
7. A. Bouakaz and J.-P. Talpin. Design of safety-critical Java Level 1 applications using affine abstract clocks. In Proceedings of the 16th International Workshop on Software and Compilers for Embedded Systems, 2013.
8. A. Bouakaz, J.-P. Talpin, and J. Vitek. Affine data-flow graphs for the synthesis of hard real-time applications. In Proceedings of the 12th International Conference on Application of Concurrency to System Design, 2012.
9. C. Chevalier and F. Pellegrini. PT-Scotch: a tool for efficient parallel graph ordering. Parallel Comput., 34(6--8):318--331, 2008.
10. A. Cimatti, L. Palopoli, and Y. Ramadian. Symbolic computation of schedulability regions using parametric automata. In the 29th IEEE Real-Time Systems Symposium, pages 80--89, 2008.
11. R. I. Davis and A. Burns. A survey of hard real-time scheduling for multiprocessor systems. ACM Comput. Surv., 43(4):35:1--35:44, 2001.
12. J. Forget, F. Boniol, E. Grolleau, D. Lesens, and C. Pagetti. Scheduling dependent periodic tasks without synchronization mechanisms. In Proceedings of the 16th IEEE Real-Time and Embedded Technology and Applications Symposium, pages 301--310, 2010.
13. L. Fribourg, R. Soulat, D. Lesens, and P. Moro. Robustness analysis for scheduling problems using the inverse method. In 19th International Symposium on Temporal Representation and Reasoning, pages 73--80, 2012.
14. A. Gamatié. Design of streaming applications on MPSoCs using abstract clocks. In Design, Automation and Test in Europe Conference, pages 763--768, 2012.
15. E. A. Lee and D. G. Messerchmitt. Static scheduling of synchronous dataflow programs for digital signal processing. IEEE Trans. Comput., 36:24--35, 1987.
16. C. Pagetti, J. Forget, F. Boniol, M. Cordovilla, and D. Lesens. Multi-task implementation of multi-periodic synchronous programs. Discrete event dynamic systems, 21(3):307--338, 2011.
17. I. Ripoll, A. Crespo, and A. K. Mok. Improvement in feasibility testing for real-time tasks. Real-Time Syst., 11(1):19--39, 1996.
18. L. Sha, T. Abdelzaher, K.-E. Arzén, A. Cervin, T. Baker, A. Burns, G. Buttazzo, M. Caccamo, J. Lehoczky, and A. K. Mok. Real time scheduling theory: a historical perspective. Real-Time Syst., 28(2--3):101--155, 2004.
19. I. M. Smarandache, T. Gautier, and P. L. Guernic. Validation of mixed signal-alpha real-time systems through affine calculus on clock synchronisation constraints. In Proceedings of the World Congress on Formal Methods in the Development of Computing Systems, volume 2, pages 1364--1383, 1999.
20. S. Stuijk, M. Geilen, and T. Basten. Exploring trade-offs in buffer requirements and throughput constraints for synchronous dataflow graphs. In Proceedings of the 43rd annual Design Automation Conference, pages 899--904, 2006.
21. S. Stuijk, M. Geilen, and T. Basten. Sdf$^\mbox3$: Sdf for free. In Proceedings of the 6th International Conference on Application of Concurrency to System Design, pages 276--278, 2006.
22. S. Stuijk, M. Geilen, and T. Basten. Throughput-buffering trade-off exploration for cyclo-static and synchronous dataflow graphs. IEEE Trans. Comput., 57:1331--1345, 2008.
23. M. H. Wiggers, M. J. G. Bekooij, and G. J. M. Smit. Efficient computation of buffer capacities for cyclo-static datatflow graphs. In Proceedings of the 44th annual Design Automation Conference, pages 658--663, 2007.
24. F. Zhang and A. Burns. improvement to quick processor-demand analysis for EDF-scheduled real-time systems. In Proceedings of the 21st Euromicro Conference on Real-Time Systems, pages 76--86, 2009.
25. F. Zhang and A. Burns. Schedulability analysis for real-time systems with EDF scheduling. IEEE Transactions on Computers, 58:1250--1258, 2009.

Index Terms

• Computer systems organization

  • Embedded and cyber-physical systems

  • Real-time systems

• Theory of computation

  • Logic

  • Models of computation