Copyright and Licensing
Articles accepted for publication will be licensed under the Creative Commons BY-NC-SA. Authors must sign a non-exclusive distribution agreement after article acceptance.
The PN-PEM framework: a Petri Net based parallel execution model
Keywords:
Parallel Programming, Asynchronous Parallel Execution, Petri Nets, FrameworkAbstract
This paper introduces the PN-PEM framework. It is based on the representation of an algorithm with Petri Nets. Frequently, a real algorithm needs a large Petri Net to be represented. We present a way to model an algorithm with Colored Petri Nets that simplify the model. After that, this high level model is transformed into a low level but executable model, preserving its semantics. The execution also needs other components of the framework, as the involved processors, data used and executable kernels. The combination of these elements is described in order to obtain a parallel execution. Some tests are also presented as a testbed of the framework in symmetric multiprocessors. Usability, as well as good performance, confirm the quality of the framework.
Downloads
Download data is not yet available.
References
[1] Basic Linear Algebra Subprograms Technical Forum Standard. Technical report, University of Tennessee, 2001.
[2] E. Anderson, Z. Bai, C. Bischof, L. S. Blackford, J. Demmel, J. J. Dongarra, J. Du Croz, S. Hammarling, A. Greenbaum, A. McKenney, and D. Sorensen. LAPACK Users’ guide (third ed.). Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 1999.
[3] C. Augonnet, S. Thibault, and R. Namyst. Starpu: a runtime system for scheduling tasks over accelerator-based multicore machines. Technical Report 7240, INRIA, Mar. 2010.
[4] A. Buttari, J. Langou, J. Kurzak, and J. J. Dongarra. A class of parallel tiled linear algebra algorithms for multicore architectures. Technical Report 191, LAPACK Working Note, Sept. 2007.
[5] M. Diaz. Petri Nets: Fundamental Models, Verification and Applications. ISTE Ltd - John Wiley & Sons, Inc., London, Hoboken, 2009.
[6] Z. Ding, H. Shen, and J. Cao. Parallel computation of continuous petri nets based on hypergraph partitioning. The Journal of Supercomputing, 62(1):345–377, 2012.
[7] M. E. Fayad, D. C. Schmidt, and R. E. Johnson. Building Application Frameworks: Object-oriented Foundations of Framework Design. John Wiley & Sons, Inc., New York, NY, USA, 1999.
[8] T. Gautier, J. V. Ferreira Lima, N. Maillard, and B. Raffin. XKaapi: A Runtime System for Data-Flow Task Programming on Heterogeneous Architectures. In 27th IEEE International Parallel & Distributed Processing Symposium (IPDPS), Boston, Massachusetts, États-Unis, May 2013.
[9] A. D. Giusti, M. R. Naiouf, F. Chichizola, and L. C. D. Giusti. Dynamic load balance in parallel merge sorting over homogeneous clusters. In 19th International Conference on Advanced Information Networking and Applications (AINA 2005), 28-30 March 2005, Taipei, Taiwan, pages 219–222, 2005.
[10] S. Haddad and J. Pradat-Peyre. New efficient petri nets reductions for parallel programs verification. Parallel Processing Letters, 16(1):101–116, 2006.
[11] A. Haidar, H. Ltaief, A. YarKhan, and J. Dongarra. Analysis of dynamically scheduled tile algorithms for dense linear algebra on multicore architectures. Technical Report 243, LAPACK Working Note, Mar. 2011.
[12] M. Iordache and P. Antsaklis. Petri nets and programming: A survey. In American Control Conference, 2009. ACC ’09., June 2009.
[13] V. Kumar, A. Grama, A. Gupta, and G. Karypis. Introduction to Parallel Computing: Design and Analysis of Algorithms. Benjamin-Cummings Publishing Co., Inc., Redwood City, CA, USA, 1994.
[14] J. Kurzak and J. J. Dongarra. Implementing linear algebra routines on multi-core processors with pipelining and a look ahead. Technical Report 178, LAPACK Working Note, Sept. 2006.
[15] H. Ltaief, S. Tomov, R. Nath, P. Du, , and J. Dongarra. A scalable high performant cholesky factorization for multicore with gpu accelerators. Technical Report 223, LAPACK Working Note, Nov. 2009.
[16] R. Sedgewick and K. Wayne. Algorithms, 4th Edition. Addison-Wesley, 2011.
[17] K. R. Shetti, S. A. Fahmy, and T. Bretschneider. Optimization of the heft algorithm for a cpu-gpu environment. In Proceedings of the 2013 International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT ’13, pages 212–218, Washington, DC, USA, 2013. IEEE Computer Society.
[18] S. Tomov, J. Dongarra, and M. Baboulin. Towards dense linear algebra for hybrid gpu accelerated manycore systems. Parallel Computing, 36(5-6):232–240, 2010.
[19] J. Wang. Timed Petri Nets: Theory and Application. The International Series on Discrete Event Dynamic Systems. Springer US, 1998.
[20] A. G. H. Wolfmann. PEM - Modelo de Ejecución Paralela Basado en Redes de Petri. PhD thesis, Fac. de Informática - Universidad Nacional de La Plata, Apr 2015.
[21] A. YarKhan, J. Kurzak, and J. Dongarra. Quark users’ guide: Queueing and runtime for kernels. Technical report, Innovative Computing Laboratory, University of Tennessee, 2011.
[2] E. Anderson, Z. Bai, C. Bischof, L. S. Blackford, J. Demmel, J. J. Dongarra, J. Du Croz, S. Hammarling, A. Greenbaum, A. McKenney, and D. Sorensen. LAPACK Users’ guide (third ed.). Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 1999.
[3] C. Augonnet, S. Thibault, and R. Namyst. Starpu: a runtime system for scheduling tasks over accelerator-based multicore machines. Technical Report 7240, INRIA, Mar. 2010.
[4] A. Buttari, J. Langou, J. Kurzak, and J. J. Dongarra. A class of parallel tiled linear algebra algorithms for multicore architectures. Technical Report 191, LAPACK Working Note, Sept. 2007.
[5] M. Diaz. Petri Nets: Fundamental Models, Verification and Applications. ISTE Ltd - John Wiley & Sons, Inc., London, Hoboken, 2009.
[6] Z. Ding, H. Shen, and J. Cao. Parallel computation of continuous petri nets based on hypergraph partitioning. The Journal of Supercomputing, 62(1):345–377, 2012.
[7] M. E. Fayad, D. C. Schmidt, and R. E. Johnson. Building Application Frameworks: Object-oriented Foundations of Framework Design. John Wiley & Sons, Inc., New York, NY, USA, 1999.
[8] T. Gautier, J. V. Ferreira Lima, N. Maillard, and B. Raffin. XKaapi: A Runtime System for Data-Flow Task Programming on Heterogeneous Architectures. In 27th IEEE International Parallel & Distributed Processing Symposium (IPDPS), Boston, Massachusetts, États-Unis, May 2013.
[9] A. D. Giusti, M. R. Naiouf, F. Chichizola, and L. C. D. Giusti. Dynamic load balance in parallel merge sorting over homogeneous clusters. In 19th International Conference on Advanced Information Networking and Applications (AINA 2005), 28-30 March 2005, Taipei, Taiwan, pages 219–222, 2005.
[10] S. Haddad and J. Pradat-Peyre. New efficient petri nets reductions for parallel programs verification. Parallel Processing Letters, 16(1):101–116, 2006.
[11] A. Haidar, H. Ltaief, A. YarKhan, and J. Dongarra. Analysis of dynamically scheduled tile algorithms for dense linear algebra on multicore architectures. Technical Report 243, LAPACK Working Note, Mar. 2011.
[12] M. Iordache and P. Antsaklis. Petri nets and programming: A survey. In American Control Conference, 2009. ACC ’09., June 2009.
[13] V. Kumar, A. Grama, A. Gupta, and G. Karypis. Introduction to Parallel Computing: Design and Analysis of Algorithms. Benjamin-Cummings Publishing Co., Inc., Redwood City, CA, USA, 1994.
[14] J. Kurzak and J. J. Dongarra. Implementing linear algebra routines on multi-core processors with pipelining and a look ahead. Technical Report 178, LAPACK Working Note, Sept. 2006.
[15] H. Ltaief, S. Tomov, R. Nath, P. Du, , and J. Dongarra. A scalable high performant cholesky factorization for multicore with gpu accelerators. Technical Report 223, LAPACK Working Note, Nov. 2009.
[16] R. Sedgewick and K. Wayne. Algorithms, 4th Edition. Addison-Wesley, 2011.
[17] K. R. Shetti, S. A. Fahmy, and T. Bretschneider. Optimization of the heft algorithm for a cpu-gpu environment. In Proceedings of the 2013 International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT ’13, pages 212–218, Washington, DC, USA, 2013. IEEE Computer Society.
[18] S. Tomov, J. Dongarra, and M. Baboulin. Towards dense linear algebra for hybrid gpu accelerated manycore systems. Parallel Computing, 36(5-6):232–240, 2010.
[19] J. Wang. Timed Petri Nets: Theory and Application. The International Series on Discrete Event Dynamic Systems. Springer US, 1998.
[20] A. G. H. Wolfmann. PEM - Modelo de Ejecución Paralela Basado en Redes de Petri. PhD thesis, Fac. de Informática - Universidad Nacional de La Plata, Apr 2015.
[21] A. YarKhan, J. Kurzak, and J. Dongarra. Quark users’ guide: Queueing and runtime for kernels. Technical report, Innovative Computing Laboratory, University of Tennessee, 2011.
Downloads
Published
2015-11-01
How to Cite
Wolfmann, A. G. H., & De Giusti, A. E. (2015). The PN-PEM framework: a Petri Net based parallel execution model. Journal of Computer Science and Technology, 15(02), p. 129–136. Retrieved from https://journal.info.unlp.edu.ar/JCST/article/view/543
Issue
Section
Original Articles
