Exploiting colored Petri nets to decide on permutation admissibility. (English) Zbl 1172.68042

Summary: In this work, we propose an innovative approach to investigate the admissibility of permutations to multistage interconnection networks – a challenging problem of switching theory. The proposed approach is centered upon modeling of multistage interconnection networks with colored Petri nets and use of Petri net analysis tools such as the unfolding technique and the invariants method. To assess the feasibility of the proposed approach we demonstrate that the complete unfoldings obtained in this work are polynomial in the problem size and employ an acyclic structure. The approach takes advantage of easy to use, yet extremely efficient, software tools.


68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
Full Text: DOI


[1] Bashirov, R.: Rearrangeability of 2 log stage networks employing an uniform connection pattern. Calcolo 38, 85–95 (2000) · Zbl 1168.94523
[2] Bashirov, R., Crespi, V.: Analyzing the permutation capability of multistage interconnection networks with colored Petri nets. Inform. Sci. 176, 3143–3165 (2006) · Zbl 1110.68004
[3] Chiola, G., Franceschinis, G., Gaeta, R., Ribaudo, M.: GreatSPN 1.7–graphical editor and analyzer for timed and stochastic Petri nets. Perform. Eval. 24, 47–68 (1995) · Zbl 0875.68663
[4] Das, R.K., Das, N.: GSE–a generalized full-access multistage interconnection network with minimum cost. In: Proceedings of HiPC’96, Trivandrum, India, IEEE Computer Society, pp. 176–181 (1996)
[5] Das, N., Bezrukov, S.L.: Permutation admissibility in shuffle-exchange networks with arbitrary number of stages. In: Proceedings of HiPC’98, Madras, India, IEEE Computer Society, pp. 270–276 (1998)
[6] Das N., Bhattacharya B.B., Bezrukov S., Menon R., Sarkar A.: Permutation routing in optical MINs with minimum number of stages. J. Syst. Archit. 48, 311–323 (2003) · Zbl 05432064
[7] Evangelista, S.: High level Petri nets analysis with Helena. In: Proceedings of ATPN’05. Miami, FL, LNCS 3536, pp. 455–464 (2005) · Zbl 1128.68377
[8] Grammatikakis M.D., Hsu D.F., Sibeyn J.F.: Packet routing in fixed-connection networks: a survey. J. Paral. Distrib. Comput. 54, 77–132 (1998) · Zbl 0911.68018
[9] Hsia, C.J.A., Chen, C.Y.R.: Permutation capability of multistage interconnection networks. In: Proceedings of ICPP’90, Urbana-Champaign, IL, pp. 1338–1346 (1990)
[10] Hu Q., Shen X., Liang W.: Optimally routing LC permutations on k-extra-stage cube-type networks. IEEE Trans. Comput. 45, 97–103 (1996) · Zbl 1058.68504
[11] Jensen K.: Coloured Petri Nets: Basic Concepts, Analysis Methods and Practical Use, vol. 1. Springer, Berlin (1997) · Zbl 0883.68098
[12] Jensen K.: Coloured Petri Nets: Basic Concepts, Analysis Methods and Practical Use, vol. 2. Springer, Berlin (1997) · Zbl 0883.68098
[13] Khomenko V., Kondratyev A., Koutny A., Vogler W.: Merged processes: a new condenced representation of Petri net behaviour. Acta Inf. 43, 307–330 (2006) · Zbl 1104.68072
[14] Hamez, A., Hillah, L., Kordon, F., Linard, A., Paviot-Adet, E., Renault, X., Thierry-Mieg, Y.: New features in CPN-AMI 3: focusing on the analysis of complex distributed systems. In: Proceeding of ACSD’06, June, Turku, Finland, IEEE Computer Society, pp. 273–275 (2006)
[15] Kordon, F., Linard, A., Paviot-Adet, E.: Optimized colored nets unfolding. In: Proceedings FORTE’06, LNCS 4229, pp. 339–355 (2006) · Zbl 1225.68126
[16] Lenfant J.: Parallel permutations of data: a Benes network control algorithm for frequently used permutations. IEEE Trans. Comput. 27, 637–647 (1978) · Zbl 0377.94049
[17] Murata T.: Petri nets: properties, analysis and applications. Proc. IEEE 77, 541–580 (1989)
[18] Raghavendra C.S., Boppana R.V.: On self-routing in Beneš and shuffle-exchange networks. IEEE Trans. Comput. 40, 1057–1064 (1991)
[19] Sahni S.: Matrix multiplication and data routing using a partitioned optical passive stars network. IEEE Trans. Paral. Distrib. Comput. 11, 720–728 (2000) · Zbl 05107345
[20] Shen X., Xu M., Wang X.: An optimal algorithm for permutation admissibility to multistage interconnection networks. IEEE Trans. Comput. 44, 604–608 (1995) · Zbl 1061.68504
[21] Shen X.: An optimal O(N log N) algorithm for permutation admissibility to extra-stage cube-type networks. IEEE Trans. Comput. 44, 1144–1149 (1995) · Zbl 1053.68510
[22] Shen X., Yang F., Pan Y.: Equivalent permutation capabilities between time-division optical omega networks and non-optical extra-stage omega networks. IEEE Trans. Network. 9, 518–524 (2001) · Zbl 05458888
[23] Veselovsky, G., Batovski, D.A.: A study of the permutation capability of a binary hypercube under deterministic dimension-order routing. In: Proceedings of PDPTA’03, Las Vegas, NV, SCREA Press, pp. 173–177 (2003)
[24] Wu C., Feng T.: On a class of multistage interconnection networks. IEEE Trans. Comput. 29, 694–702 (1980) · Zbl 0444.94048
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.