Usage of petri nets for high performance computing

ABSTRACT

Petri nets are a well established graphical and mathematical modelling language for a description of concurrent systems. The main scope of this paper is to present our approach how to use Petri nets for high-performance computing. They are rarely used in this area. As a proof of concept, we are developing a tool Kaira. The modelling language in the tool is based on our extension of Coloured Petri Nets. The basic concept is to use a visual language to model parallel behaviour and communication. Sequential parts of a program are written in C/C++. In contrast to other Petri Nets based tools, Kaira is not intended only for modelling and simulation, but it can also generate standalone parallel applications from models. Generated applications use MPI and threads. This paper also presents new Kaira's features including modules for computations on structured objects, more controllable semantics of mapping to MPI processes and a support for the hybrid computing.

References

1. CPN Tools: http://cpntools.org/.
2. Message Passing Interface Forum: http://www.mpi-forum.org/.
3. OpenMP: http://openmp.org/.
4. RENEW: http://renew.de/.
5. M. A. Adamski, A. Karatkevich, and M. Wegrzyn. Design of Embedded Control Systems. Springer Publishing Company, Incorporated, 1st edition, 2010. ISBN 1441936467, 9781441936462.
6. M. Aldinucci, M. Danelutto, P. Kilpatrick, and M. Torquati. Fastflow: high-level and efficient streaming on multi-core. In S. Pllana and F. Xhafa, editors, Programming Multi-core and Many-core Computing Systems, Parallel and Distributed Computing, chapter 13. Wiley, 2012. ISBN 0470936908.
7. S. Böhm and M. Běhálek. Kaira: Modelling and generation tool based on Petri nets for parallel applications. In UkSim 13th International Conference on Computer Modelling and Simulation, pages 403--408, 30 2011-april 1 2011. ISBN 978-1-61284-705-4.
8. S. Böhm, M. Běhálek, and O. Garncarz. Developing parallel applications using Kaira. In Digital Information Processing and Communications, volume 188 of Communications in Computer and Information Science, pages 237--251. Springer, 2011. ISBN 978-3-642-22388-4.
9. J. C. Browne, S. I. Hyder, J. Dongarra, K. Moore, and P. Newton. Visual programming and debugging for parallel computing. IEEE Parallel Distrib. Technol., 3 (1): 75--83, Mar. 1995. ISSN 1063-6552. 10.1109/88.384586. URL http://dx.doi.org/10.1109/88.384586.
10. M. Běhálek, S. Böhm, P. Krömer, M. Šurkovský, and O. Meca. Parallelization of ant colony optimization algorithm using Kaira. In 11th International Conference on Intelligent Systems Design and Applications (ISDA 2011), Cordoba, Spain, Nov. 2011. ISBN 978-1-4577-1675-1.
11. L. Cabac. Modeling Petri Net-Based Multi-Agent Applications. PhD thesis, Apr. 2010. URL http://www.sub.uni-hamburg.de/opus/volltexte/2010/4666/. http://www.sub.uni-hamburg.de/opus/volltexte/2010/4666/.
12. L. A. Cortés, P. Eles, and Z. Peng. Modeling and formal verification of embedded systems based on a petri net representation. J. Syst. Archit., 49 (12-15): 571--598, Dec. 2003. ISSN 1383-7621. 10.1016/S1383-7621(03)00096-1. URL http://dx.doi.org/10.1016/S1383-7621(03)00096-1.
13. I. Foster. Designing and Building Parallel Programs: Concepts and Tools for Parallel Software Engineering. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1995. ISBN 0201575949.
14. M. I. Gordon, W. Thies, and S. Amarasinghe. Exploiting coarse-grained task, data, and pipeline parallelism in stream programs. SIGPLAN Not., 41 (11): 151--162, Oct. 2006. ISSN 0362-1340. 10.1145/1168918.1168877.
15. K. Jensen and L. M. Kristensen. Coloured Petri Nets - Modelling and Validation of Concurrent Systems. Springer, 2009. ISBN 978-3-642-00283-0.
16. P. Kacsuk, J. Cunha, G. Dzsa, J. Loureno, T. Fadgyas, and T. Antao. A graphical development and debugging environment for parallel programs. Parallel Computing, 22 (13): 1747--1770, 1997. ISSN 0167-8191. 10.1016/S0167-8191(96)00075-0. URL http://www.sciencedirect.com/science/article/pii/S0167819196000750. Distributed and parellel systems: Environments and tools.
17. P. Newton and J. C. Browne. The code 2.0 graphical parallel programming language. In Proceedings of the 6th international conference on Supercomputing, ICS '92, pages 167--177, New York, NY, USA, 1992. ACM. ISBN 0-89791-485-6. 10.1145/143369.143405. URL http://doi.acm.org/10.1145/143369.143405.
18. P. Newton and S. Y. Khedekar. CODE 2.0 User and Reference Manual. http://www.cs.utexas.edu/~code/download/docs/CODE_2.0_Manual.ps.
19. R. Rabenseifner, G. Hager, and G. Jost. Hybrid mpi/openmp parallel programming on clusters of multi-core smp nodes. Parallel, Distributed, and Network-Based Processing, Euromicro Conference on, 0: 427--436, 2009. ISSN 1066-6192. http://doi.ieeecomputersociety.org/10.1109/PDP.2009.43.
20. W. Reisig and G. Rozenberg, editors. Lectures on Petri Nets I: Basic Models, Advances in Petri Nets, the volumes are based on the Advanced Course on Petri Nets, held in Dagstuhl, September 1996, volume 1491 of Lecture Notes in Computer Science, 1998. Springer. ISBN 3-540-65306-6.
21. M. Snir, S. Otto, S. Huss-Lederman, D. Walker, and J. Dongarra. MPI-The Complete Reference, Volume 1: The MPI Core. MIT Press, Cambridge, MA, USA, 2nd. (revised) edition, 1998. ISBN 0262692155.
22. W. Thies and S. Amarasinghe. An empirical characterization of stream programs and its implications for language and compiler design. In Proceedings of the 19th international conference on Parallel architectures and compilation techniques, PACT '10, pages 365--376, New York, NY, USA, 2010. ACM. ISBN 978-1-4503-0178-7. 10.1145/1854273.1854319.

Index Terms

• Computing methodologies

  • Concurrent computing methodologies

    • Concurrent programming languages

  • Modeling and simulation

    • Model development and analysis

• Software and its engineering

  • Software notations and tools

    • Context specific languages

      • Visual languages

    • General programming languages

      • Language types

        • Concurrent programming languages