Quasi-static Scheduling for Concurrent Architectures

• Autorzy: Cortadella J. , Kondratyev A. , Lavagno L. , Taubin A. , Watanabe Y.
• Konferencja: Third International Conference on Application of Concurrency to System Design (ACSD'03) (18-20 June, 2003, Guimaraes, Portugal)
• Języki publikacji: EN

Abstrakty

EN

This paper presents a synthesis approach for reactive systems that aims at minimizing the overhead introduced by the operating system and the interaction among the concurrent tasks, while considering multiple concurrent execution resources. A formal model based on the notion of scheduling of Petri nets is used to perform the synthesis. We show how the notion of projections of a schedule for the complete system onto the components implemented on separate resources is essential to define the correctness of the partitioned schedule.

Słowa kluczowe

EN

quasi-static scheduling; static scheduling; Petri net

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2004
• Tom: Vol. 62, nr 2
• Strony: 171--196
• Opis fizyczny: Bibliogr. 15 poz., rys., wykr.

Twórcy

autor

Cortadella J.

• Universitat Politècnica de Catalunya, Barcelona, Spain

autor

Kondratyev A.

• Cadence Berkeley Labs, Berkeley, USA

autor

Lavagno L.

• Politecnico di Torino, Torino, Italy

autor

Taubin A.

• Boston University, Boston, USA

autor

Watanabe Y.

• Cadence Berkeley Labs, Berkeley, USA

Bibliografia

• [1] J. Buck. Scheduling dynamic dataflow graphs with bounded memory using the token flow model. PhD thesis, U.C. Berkeley. 1993.
• [2] J. Cortadella, A. Kondratyev. L. Lavagno, M. Massot, S. Moral, C. Passerone. Y. Watanabe, and A. Sangiovanni-Vincentelli. Task Generation and Compile-Time Scheduling for Mixed Data-Control Embedded Software. In Proceedings of the 37th Design Automation Conference, June 2000.
• [3] J. Cortadella, A. Kondratyev, L. Lavagno, C. Passerone, and Y. Watanabe. Quasi-static scheduling of independent tasks for reactive systems. In Proceedings of the International Conference of Application and Theory of Petri Nets, 2m2.
• [4] E.A. de Kock, G. Essink, W.J.M. Smits, P. van der Wolf, J.-Y. Brunei, W.M. Kruijtzer, P. Lieverse, and K.A. Vissers. YAPI: Application Modeling for Singal Processing Systems. In Proceedings of the 37th Design Automation Conference., June 2000.
• [5] N. Halbwachs. Synchronous Programming of Reactive Systems. Kluwer Academic Publishers, 1993.
• [6] D. Har'el, H. Lachover, A. Naamad, A. Pnueli, et al. STATEMATE: a working environment for the development of complex reactive systems. IEEE Transactions on Software Engineering, 16(4). April 1990.
• [7] C. A. R. Hoare. Communicating Sequential Processes. International Series in Computer Science. Prentice-Hall, 66 Wood Lane End. Hemel Hempstead, Hertfordshire, HP2 4RG, UK, 1985.
• [8] G. Kahn. The semantics of a simple language for parallel programming. In Proceedings of IFIP Congress, August 1974.
• [9] H. Kopetz and G. Grunsteidl. TTP - A protocol for fault-tolerant real-time systems. IEEE Computer. 27(1). January 1994.
• [10] E. A. Lee and D. G. Messerschmitt. Static scheduling of synchronous data flow graphs for digital signal processing. IEEE Transactions on Computers, January 1987.
• [11] B. Lin. Software synthesis of process-based concurrent programs. In 35th ACM/IEEE Design Automation Conference, June 1998.
• [12] T. Murata. Petri Nets: Properties, analysis and applications. Proceedings of the IEEE, pages 541-580. April 1989.
• [13] M. Sgroi, L. Lavagno, Y. Watanabe, and A. Sangiovanni-Vincentelli. Synthesis of embedded software using free-choice Petri nets. In 36th ACM/IEEE Design Automation Conference, June 1999.
• [14] K. Strehl, L. Thiele, D. Ziegenbein, R. Ernst, and et al. Scheduling hardware/software systems using symbolic techniques. In International Workshop on Hardware/Software Codesign, 1999.
• [15] S. H. Unger. Asynchronous Sequential Switching Circuits. Wiley-Inter science, John Wiley & Sons, Inc., New York, 1969.