Predicate-aware, makespan-preserving software pipelining of scheduling tables

Abstract

We propose a software pipelining technique adapted to specific hard real-time scheduling problems. Our technique optimizes both computation throughput and execution cycle makespan, with makespan being prioritary. It also takes advantage of the predicated execution mechanisms of our embedded execution platform. To do so, it uses a reservation table formalism allowing the manipulation of the execution conditions of operations. Our reservation tables allow the double reservation of a resource at the same dates by two different operations, if the operations have exclusive execution conditions. Our analyses can determine when double reservation is possible even for operations belonging to different iterations.

References

1. V. H. Allan, R. B. Jones, R. M. Lee, and S. J. Allan. 1995. Software pipelining. ACM Computing Surveys 27, 3, 367--432.
2. C. André, F. Mallet, and M.-A. Peraldi-Frati. 2007. A multiform time approach to real-time system modeling: Application to an automotive system. In Proceedings of the SIES. Lisbon, Portugal.
3. ARINC653. 2005. Avionics Application Software Standard Interface, volumes 1--3. http://www.arinc.org.
4. AUTOSAR. 2009. Automotive Open System Architecture, release 4. http://www.autosar.org/.
5. A. Benoît, V. Rehn-Sonigo, and Y. Robert. 2007. Multi-criteria scheduling of pipeline workflows. In Proceedings of the International Conference on Cluster Computing. Austin, TX.
6. P.-Y. Calland, A. Darte, and Y. Robert. 1998. Circuit retiming applied to decomposed software pipelining. IEEE Transactions on Parallel and Distributed Systems 9, 1, 24--35.
7. T. Carle, D. Potop-Butucaru, Y. Sorel, and D. Lesens. 2012. From dataflow specification to multiprocessor partitioned time-triggered real-time implementation. Technical Report. INRIA. http://hal.inria.fr/hal-00742908
8. P. Caspi, A. Curic, A. Magnan, C. Sofronis, S. Tripakis, and P. Niebert. 2003. From Simulink to SCADE/Lustre to TTA: A layered approach for distributed embedded applications. In Proceedings of the LCTES. San Diego, CA.
9. K. Chatha and R. Vemuri. 2002. Hardware-software partitioning and pipelined scheduling of transformative applications. IEEE Transactions on Very Large Scale Integration (VLSI) Systems 10, 3, 193--208.
10. Y.-S. Chiu, C.-S. Shih, and S.-H. Hung. 2011. Pipeline schedule synthesis for real-time streaming tasks with inter/intra-instance precedence constraints. In Proceedings of DATE. Grenoble, France.
11. P. Eles, A. Doboli, P. Pop, and Z. Peng. 2000. Scheduling with bus access optimization for distributed embedded systems. IEEE Transactions on VLSI Systems 8, 5, 472--491.
12. G. Fohler, A. Neundorf, K.-E. Årzén, C. Lucarz, M. Mattavelli, V. Noel, C. von Platen, G. Butazzo, E. Bini, and C. Scordino. 2008. EU FP7 ACTORS project. Ch 5: Resource reservation in real-time systems. In D7a: State of the Art Assessment. http://www3.control.lth.se/user/karlerik/Actors/d7a-rev.pdf.
13. M. R. Garey and D. S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company.
14. F. Gasperoni and U. Schwiegelshohn. 1994. Generating close to optimum loop schedules on parallel processors. Parallel Processing Letters 4, 4, 391--404.
15. R. Govindarajan, E. Altman, and G. Gao. 1994. Minimizing register requirements under resource-constrained rate-optimal software pipelining. In Proceedings of the 27th Annual International Symposium on Microarchitecture (MICRO 27).
16. T. Grandpierre and Y. Sorel. 2003. From algorithm and architecture specification to automatic generation of distributed real-time executives. In Proceedings of the MEMOCODE. Mont St. Michel, France.
17. J. L. Hennessy and D. A. Patterson. 2007. Computer Architecture: A Quantitative Approach (4th ed.). Morgan Kaufmann.
18. R. Huff. 1993. Lifetime-sensitive modulo scheduling. In Proceedings of the ACM SIGPLAN 93rd Conference on Programming Language Design and Implementation. 258--267.
19. W. Kim, D. Yoo, H. Park, and M. Ahn. 2012. SCC based modulo scheduling for coarse-grained reconfigurable processors. In Proceedings of the 2012 International Converence on Field-Programmable Technology (FPT). Seoul, Korea.
20. M. Lam. 1988. Software pipelining: An effective scheduling technique for VLIW machines. In Proceedings of the SIGPLAN 88 Conference on Programming Language Design and Implementation. 318--328.
21. C. Leiserson and J. Saxe. 1991. Retiming synchronous circuitry. Algorithmica 6, 1, 5--35.
22. A. Monot, N. Navet, F. Simonot, and B. Bavoux. 2010. Multicore scheduling in automotive ECUs. In Proceedings of the ERTSS. Toulouse, France.
23. L. Morel. 2005. Exploitation des structures régulières et des spécifications locales pour le developpement correct de systèmes réactifs de grande taille. Ph.D. Dissertation. Institut National Polytechnique de Grenoble.
24. S. Muchnick. 1997. Advanced Compiler Design and Implementation. Morgan Kaufman.
25. D.Potop-Butucaru, A. Azim, and S. Fischmeister. 2010. Semantics-preserving implementation of synchronous specifications over dynamic TDMA distributed architectures. In Proceedings of the EMSOFT. Scottsdale, AZ.
26. D. Potop-Butucaru, R. De Simone, Y. Sorel, and J.-P. Talpin. 2009. Clock-driven distributed real-time implementation of endochronous synchronous programs. In Proceedings of the 7th ACM International Conference on Embedded Software (EMSOFT’09). ACM, 147--156.
27. C. Pradalier, J. Hermosillo, C. Koike, C. Braillon, P. Bessière, and C. Laugier. 2005. The CyCab: A car-like robot navigating autonomously and safely among pedestrians. Robotics and Autonomous Systems 50, 1, 51--68.
28. B. R. Rau. 1996. Iterative modulo scheduling. International Journal of Parallel Programming 24, 1, 3--64.
29. B. R. Rau and C. D. Glaeser. 1981. Some scheduling techniques and an easily schedulable horizontal architecture for high performance scientific computing. In Proceedings of the 14th Annual Workshop on Microprogramming. IEEE.
30. B. R. Rau, M. Lee, P. P. Tirumalai, and M. S. Schlansker. 1992. Register allocation for software pipelined loops. In Proceedings of PLDI’92. San Francisco, CA.
31. J. Rushby. 2001. Bus architectures for safety-critical embedded systems. In Proceedings of EMSOFT’01 (LNCS), Vol. 2211. Tahoe City, CA.
32. M. Smelyanskyi, S. Mahlke, E. Davidson, and H.-H. Lee. 2003. Predicate-aware scheduling: A technique for reducing resource constraints. In Proceedings of the CGO. San Francisco, CA.
33. J. Wang and C. Eisenbeis. 1993. Decomposed software pipelining. http://hal.inria.fr/inria-00074834
34. N. J. Warter, D. M. Lavery, and W. W. Hwu. 1993. The benefit of predicated execution for software pipelining. In Proceedings of the HICSS-26 Conference. Houston, Texas.
35. H. Yang and S. Ha. 2009. Pipelined data parallel task mapping/scheduling technique for MPSoC. In Proceedings of the Design, Automation Test in Europe Conference Exhibition (DATE). Nice, France.
36. H.-S. Yun, J. Kim, and S.-M. Moon. 2003. Time optimal software pipelining of loops with control flows. International Journal of Parallel Programming 31, 5, 339--391.
37. J. Zalamea, J. Llosa, E. Ayguade, and M. Valero. 2004. Register constrained modulo scheduling. IEEE Transactions on Parallel and Distributed Systems 15, 5, 417--430.
38. W. Zheng, J. Chong, C. Pinello, S. Kanajan, and A. Sangiovanni-Vincentelli. 2005. Extensible and scalable time-triggered scheduling. In Proceedings of the ACSD. Saint-Malo, France.
39. Q. Zhuge, Z. Shao, and E. H. Sha. 2002. Optimal code size reduction for software-pipelined loops on DSP applications. In Proceedings of the International Conference on Parallel Processing.

Index Terms

• Computer systems organization

  • Embedded and cyber-physical systems

  • Real-time systems

• Software and its engineering

  • Software notations and tools

    • Compilers