Schedulability Analysis of Petri Nets Based on Structural Properties

• Autorzy: Liu C. , Kondratyev A. , Watanabe Y. , Desel J. , Sangiovanni-Vincentelli A.
• Języki publikacji: EN

Abstrakty

EN

A schedule of a Petri Net (PN) represents a set of firing sequences that can be infinitely repeated within a bounded state space, regardless of the outcomes of the nondeterministic choices. Schedulability analysis for a given PN answers the question whether a schedule exists in the reachability space of this net. This paper suggests a novel approach for schedulability analysis based solely on PN structure. It shows that unschedulability can be caused by a structural relation among transitions modelling nondeterministic choices. A method based on linear programming for checking this relation is proposed. This paper also presents a necessary condition for schedulability based on the rank of the incidence matrix of the underlying PN. These results shed a light on the sources of unschedulability often found in PN models of embedded multimedia systems.

Słowa kluczowe

EN

Petri net; structural property; quasi-static scheduling

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2008
• Tom: Vol. 86, nr 3
• Strony: 325--341
• Opis fizyczny: bibliogr. 17 poz., tab., wykr.

Twórcy

autor

Liu C.

autor

Kondratyev A.

autor

Watanabe Y.

autor

Desel J.

autor

Sangiovanni-Vincentelli A.

• Department of Electrical Engineering and Computer Sciences, University of California, Berkeley, 253 Cory Hall#1772, Berkeley, CA 94720-1772, USA,

Bibliografia

• [1] The SESAME Software Project, URL: http://sesamesim.sourceforge.net.
• [2] Stanford PVRG JPEG codec, URL: http://www.dclunie.com/jpegge.html.
• [3] XviD MPEG-4 video codec, URL: http://www.xvid.org.
• [4] Arrigoni, G., Duchini, L., Lavagno, L., Passerone, C., Watanabe, Y.: False Path Elimination in Quasi-Static Scheduling, Proceedings of the Design Automation and Test in Europe Conference, March 2002.
• [5] Broekhof, P., Roosen, N., Verhoef, J., Jun, W.: Modeling XviD as a Kahn Process Network, a SESAME Application Design Document, URL: http://staff.science.uva.nl/_andy/apps/xvid.pdf.
• [6] Cortadella, J., Kondratyev,A., Lavagno, L.,Massot,M.,Moral, S., Passerone, C.,Watanabe, Y., Sangiovanni-Vincentelli, A.: Task generation and compile-time scheduling for mixed data-control embedded software, DAC '00: Proceedings of the 37th Conference on Design Automation, 2000.
• [7] Cortadella, J., Kondratyev, A., Lavagno, L., Passerone, C.,Watanabe, Y.: Quasi-static scheduling of independent tasks for reactive systems, IEEE Transactions on Computer-Aided Design, 24(10), 2005, 1492-1514.
• [8] Desel, J., Esparza, J.: Free choice Petri nets, vol. 40 of Cambridge Tracts In Theoretical Computer Science, Cambridge University Press, New York, NY, USA, 1995.
• [9] Kahn, G.: The semantics of a simple language for parallel programming, Information Processing, Aug 1974.
• [10] Kahn, G., MacQueen, D. B.: Coroutines and networks of parallel processes, Information Processing, Aug 1977.
• [11] de Kock, E. A., Smits, W. J. M., van der Wolf, P., Brunel, J.-Y., Kruijtzer,W. M., Lieverse, P., Vissers, K. A., Essink, G.: YAPI: Application Modeling for Signal Processing Systems, DAC '00: Proceedings of the 37th Conference on Design Automation, 2000.
• [12] Lee, E. A., Messerschmitt, D. G.: Static scheduling of synchronous data flow programs for digital signal processing, IEEE Trans. Comput., 36(1), 1987, 24-35.
• [13] Lieverse, P., Stefanov, T., van der Wolf, P., Deprettere, E.: System level design with SPADE: an M-JPEG case study, Proceedings of IEEE/ACM International Conference on Computer Aided Design, Nov 2001.
• [14] Lin, B.: Software synthesis of process-based concurrent programs, DAC '98: Proceedings of the 35th ACM/IEEE Conference on Design Automation, 1998.
• [15] Memmi, G., Roucairol, G.: Linear Algebra in Net Theory., Lecture Notes in Computer Science: Net Theory and Applications, Proc. of the Advanced Course on General Net Theory of Processes and Systems, Hamburg, 1979 (Brauer,W., Ed.), 84, Springer-Verlag, Berlin, Heidelberg, New York, 1980.
• [16] Sgroi, M., Lavagno, L., Watanabe, Y., Sangiovanni-Vincentelli, A.: Synthesis of embedded software using free-choice Petri nets, DAC '99: Proceedings of the 36th ACM/IEEE Conference on Design Automation, 1999.
• [17] van der Wolf, P., Lieverse, P., Goel, M., Hei, D. L., Vissers, K.: An MPEG-2 decoder case study as a driver for a system level design methodology, CODES '99: Proceedings of the 7th International Workshop on Hardware/Software Codesign, 1999.