zbMATH — the first resource for mathematics

Rearrangeability of bit permutation networks. (English) Zbl 1086.68010
Summary: We introduce the concept of routing grid as a tool for analyzing realizability of permutations on Bit Permutation Networks (BPNs). We extend a result by Linial and Tarsi which characterizes permutations realizable on shuffle-exchange networks to any BPNs. A necessary condition for a BPN to be rearrangeable is given, and the rearrangeability of two families of BPNs are explored. Finally, we present a method which may help to tackle one kind of balanced matrix problems whose solution implies an answer to Benes conjecture. Hopefully, our treatment brings some new insight into the problem of permutation routing.
MSC:
 68M10 Network design and communication in computer systems
Full Text:
References:
 [1] Agrawal, D.P., Graph theoretical analysis and design of multistage interconnection networks, IEEE trans. comput., 32, 637-648, (1983) [2] Andresen, S., The looping algorithm extended to base $$2^t$$ rearrangeable switching networks, IEEE trans. comm., 25, 1057-1063, (1977) [3] X. Bao, F.K. Hwang, On a proof of the shuffle-exchange conjecture, submitted for publication. [4] Benes, V.E., Proving the rearrangeability of connecting networks by group calculations, Bell system tech. J., 45, 421-434, (1975) · Zbl 0319.94016 [5] Berge, C., Graphs and hypergraphs, (1976), North Holland Amsterdam · Zbl 0483.05029 [6] Bermond, J.C.; Fourneau, J.M.; Jean-Marie, A., Equivalence of multistage interconnection networks, Inform. process lett., 26, 45-50, (1987) [7] T. Calamoneri, A. Massini, Efficiently checking the equivalence of multistage interconnection networks, Proc. Parallel and Distributed Computing and Systems (PDCS’99), Cambridge, MA, 1999, pp. 23-30. · Zbl 1072.68002 [8] T. Calamoneri, A. Massini, A new approach to the rearrangeability of ($$2 \log N$$-1) stage MINs, Proc. IASTED Internat. Symp. Applied Informatics (AI 2001), 2001, pp. 365-370. [9] Cam, H., Rearrangeability of ($$2 n$$-1)-stage shuffle-exchange networks, SIAM J. comput., 32, 557-585, (2003) · Zbl 1046.68017 [10] Cam, H.; Fortes, J.A.B., Frames: a simple characterization of permutations realized by frequently used networks, IEEE trans. comput., 44, 695-697, (1995) · Zbl 1068.68533 [11] Chang, G.J.; Hwang, F.K.; Tong, L.-D., Characterizing bit permutation networks, Networks, 33, 261-267, (1999) · Zbl 0948.94023 [12] Even, S.; Litman, A., Layered cross product—a technique to construct interconnection networks, Networks, 29, 219-223, (1997) · Zbl 0882.90042 [13] Feng, T.-Y.; Seo, S.-W., A new routing algorithm for a class of rearrangeable networks, IEEE trans. comput., 43, 1270-1280, (1994) · Zbl 1061.68589 [14] N. Golbandi, A. Litman, Characterizations of generalized butterfly networks, preprint, 2002. [15] Hu, Q.; Shen, X.; Yang, J., Topologies of combined ($$2 \log N$$-1)-stage interconnection networks, IEEE trans. comput., 46, 118-124, (1997) [16] Hwang, F.K.; Yen, C.-H., Characterizing the bit permutation networks obtained from the line digraphs of bit permutation networks, Networks, 38, 1-5, (2001) · Zbl 1014.90008 [17] Kim, M.K.; Yoon, H.; Maeng, S.R., On the correctness of inside-out routing algorithm, IEEE trans. comput., 46, 820-823, (1997) [18] Linial, N.; Tarsi, M., Interpolation between bases and the shuffle-exchange network, European J. combin., 10, 29-39, (1989) · Zbl 0662.94026 [19] H.Q. Ngo, D. Du, On the rearrangeability of shuffle-exchange networks, Proc. Fourth Internat. Conf. on Algorithms and Architectures for Parallel Processing, 2000. · Zbl 0985.68002 [20] Opferman, D.C.; Tsao-Wu, N.T., On a class of rearrangeable switching networks—part I: control algorithm, Bell system tech. J., 50, 1579-1600, (1971) · Zbl 0226.94025 [21] C.S. Raghavendra, On the rearrangeability conjecture of $$(2 \log_2 N - 1)$$-stage shuffle/exchange network, position paper, Computer Architecture Technical Committee Newsletter, Winter 1994-1995, pp. 10-12. [22] Raghavendra, C.S.; Varma, A., Rearrangeability of the five stage shuffle-exchange network for $$N = 8$$, IEEE trans. comm., 35, 808-812, (1987) · Zbl 0643.94040 [23] Y. Wu, X. Bao, X. Jia, Q. Li, Graph theoretical characterizations of bit permutation networks, manuscript, 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. 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.