×

Analyzing permutation capability of multistage interconnection networks with colored Petri nets. (English) Zbl 1110.68004

Summary: In a Multistage Interconnection Network (MIN) the calculation of the number of permutations of the input terminals into the output terminals is a classic difficult problem. In this paper, we introduce an innovative technique based on Colored Petri Nets (known as CP-nets or CPNs) that will allow us to analyze the permutation capability of arbitrary MINs. We show how to verify whether a MIN is rearrangeable through the state space analysis of the associated CP-net and we measure the permutation capability of non-rearrangeable MINs in terms of the permutations that can be generated. The proposed approach takes advantage of powerful existing software tools, particularly, CPNTools, which is used to explore the occurrence graphs of CP-nets and determine the set of permutations performed by the modeled MINs. This new technique is easy to use and can be efficiently applied to MINs made of cross-bar switches.

MSC:

68M10 Network design and communication in computer systems
68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bashirov, R., On the rearrangeability of \((2s\)−1)-stage nonsymmetric interconnection networks, (Proceedings of the International Conference on Parallel and Distributed Computing Techniques and Applications (2000), CSREA Press: CSREA Press Las Vegas, NV), 907-910
[2] Bashirov, R., On the rearrangeability of multistage interconnection networks employing uniform connection pattern, Lecture Notes in Computer Science, 1909, 170-180 (2000) · Zbl 1051.68578
[3] Bashirov, R., Rearrangeablity of \((2log_2N\)−1)-stage networks employing uniform connection pattern, Calcolo, 38, 85-95 (2001) · Zbl 1168.94523
[4] Beneš, V., Mathematical Theory of Connecting Networks and Telephone Traffic (1965), Academic Press: Academic Press New York · Zbl 0138.40904
[5] Broomel, G.; Heath, J. R., Classification categories and historical development of circuit switching topologies, ACM Computing Surveys, 15, 95-133 (1983)
[6] Das, N., More on rearrangeability of combined \((2n\)−1)-stage networks, Journal of Systems Architecture, 51, 207-222 (2005)
[7] Das, N.; Mikhopadhyaya, K.; Dattagupta, J., \(O(n)\) routing in rearrangeable networks, Journal of Systems Architecture, 46, 529-542 (2000)
[8] Douglass, B. G., Rearrangeable three-stage interconnection networks and their routing properties, IEEE Transactions on Computers, 42, 559-567 (1993)
[9] L. Goke, G. Lipovski, Banyan networks for partitioning multiprocessor systems, in: Proc. 1st Annual Symposium on Computer Architecture, Miami, FL, 1973, pp. 21-28.; L. Goke, G. Lipovski, Banyan networks for partitioning multiprocessor systems, in: Proc. 1st Annual Symposium on Computer Architecture, Miami, FL, 1973, pp. 21-28.
[10] Hu, Q.; Shen, X.; Yang, J., Topologies of combined (2log \(N\)−1)-stage interconnection networks, IEEE Transactions on Computers, 46, 118-124 (1997)
[11] Jensen, K., Coloured Petri Nets: Basic Concepts, Analysis Methods and Practical Use, vol. 1 (1997), Springer Verlag: Springer Verlag Berlin · Zbl 0883.68098
[12] Jensen, K., Coloured Petri Nets: Basic Concepts, Analysis Methods and Practical Use, vol. 2 (1997), Springer Verlag: Springer Verlag Berlin · Zbl 0883.68098
[13] Jensen, K.; Christensen, S.; Kristensen, M., CPNTools: Occurrence Graph Manual (2002), University of Aarhus: University of Aarhus Åarhus, Denmark
[14] Kannan, R., The KB-Benes network: a control-optimal rearrangeable permutation network, IEEE Transactions on Computers, 54, 534-544 (2005)
[15] Kristensen, L. M.; Christensen, S.; Jensen, K., The practitioners guide to colored Petri nets, International Journal for Software Tools and Technology Transfer, 2, 98-132 (1998) · Zbl 1033.68590
[16] Lakshmivarahan, S.; Dhall, S. K., Analysis and Design of Parallel Algorithms (1990), McGraw-Hill: McGraw-Hill Singapore · Zbl 0593.68029
[17] Lawrie, D. H., Access and alignment data in an array processor, IEEE Transactions on Computers, 24, 1145-1155 (1975) · Zbl 0328.68034
[18] Leighton, F. T., Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes (1992), Morgan Kaufmann Publishers: Morgan Kaufmann Publishers San Mateo, CA · Zbl 0743.68007
[19] Nassimi, D.; Sahni, S., Parallel algorithms to set up the Beneš permutation network, IEEE Transactions on Computers, 31, 148-154 (1982) · Zbl 0501.94019
[20] Raghavendra, C. S.; Varma, A., Rearrangeability of the 5-stage shuffle-exchange network for \(N=8\), IEEE Transactions on Communications, 35, 808-812 (1987) · Zbl 0643.94040
[21] J. Sengupta, P.K. Bansal, A. Gupta, Permutation and reliability measures of regular and irregular MINs, in: Proceedings of the Trends in Electronics Conference, Kuala Lumpur, vol. 1, 2000, pp. 531-536.; J. Sengupta, P.K. Bansal, A. Gupta, Permutation and reliability measures of regular and irregular MINs, in: Proceedings of the Trends in Electronics Conference, Kuala Lumpur, vol. 1, 2000, pp. 531-536.
[22] Varma, A.; Raghavendra, C. S., Rearrangeability of multistage shuffle-exchange networks, IEEE Transactions on Communications, 36, 1138-1143 (1988) · Zbl 0657.94025
[23] Varma, A.; Raghavendra, C. S., Interconnection Networks for Multiprocessors and Multicomputers: Theory and Practice (1994), IEEE Computer Society Press: IEEE Computer Society Press Los Alamitos, CA · Zbl 0825.68185
[24] G. Veselovsky, D.A. Batovski, A study of the permutation capability of a binary hypercube under deterministic routing, in: Proc. 11th European Conference on Distributed and Network-Based Processing, Genova, 2003, pp. 173-177.; G. Veselovsky, D.A. Batovski, A study of the permutation capability of a binary hypercube under deterministic routing, in: Proc. 11th European Conference on Distributed and Network-Based Processing, Genova, 2003, pp. 173-177.
[25] Wu, C.; Feng, T., On a class of multistage interconnection networks, IEEE Transactions on Computers, 29, 694-702 (1980) · Zbl 0444.94048
[26] Yang, Y.; Wang, J.; Pan, Y., Permutation capability of optical multistage interconnection networks, Journal of Parallel and Distributed Computing, 60, 72-91 (2000) · Zbl 0958.68009
[27] Yeh, Y.; Feng, T., On a class of rearrangeable networks, IEEE Transactions on Computers, 41, 1361-1379 (1992)
[28] Yen, M. H.; Chen, S. J., A three-stage and one-sided rearrangeable polygonal switching network, IEEE Transactions on Computers, 50, 1291-1294 (2001)
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.