Routing Algorithm for Symmetric Rearrangeable Networks and Emerging Applications
DOI:
https://doi.org/10.18486/ijcsnt/2.1.016Keywords:
Rearrangeable Networks, Permutation, Interconnection Networks, Routing Tags, ComplexityAbstract
Routing algorithms for symmetric rearrangeable networks have been discussed in greater detail in the literature. Major focus of these algorithms was on designing algorithms for full occupancy networks. One of the major issues with those algorithms was the required time to setup a switch of size N. Very little effort have been put to design algorithms which compromise between time complexity and switch throughput. In this paper we propose a new routing algorithm that uses two different routing methods in routing from input stage to output stage. One of the methods is called deterministic or optimal routing and other one is called adaptive routing. Deterministic method assures that each input request will have a definite path in the network and adaptive method makes sure that the path establishment takes place as fast as possible. This new algorithm works for both full and partial permutations without any modifications to the method. An optimal routing algorithm is used in the outermost stages of the network and in the innermost stages the decision making is based on the state of the switching elements. This new algorithm is called as hybrid routing algorithm. The required execution time of this new algorithm is much faster than optimal algorithm, and it has better scaling properties than suboptimal routing algorithms. This paper also addresses some of the emerging applications built using symmetric rearrangeable network class.
References
E. Benes. *Mathematical Theory of Connecting Networks and Telephone Traffic*. New York: Academic Press, 1965.
S.-W. Seo, T.-Y. Feng, and H.-I. Lee. "Permutation Realizability and Fault Tolerance Property of the Inside-Out Routing Algorithm." *IEEE Transactions on Parallel and Distributed Systems*, vol. 10, no. 9, pp. 946–957, 1999. DOI: https://doi.org/10.1109/71.798318
T.-Y. Feng and S.-W. Seo. "A New Routing Algorithm for a Class of Rearrangeable Networks." *IEEE Transactions on Computers*, vol. 43, no. 11, pp. 1270–1280, 1994. DOI: https://doi.org/10.1109/12.324560
K. Y. Lee. "On the Rearrangeability of 2(log₂N − 1) Stage Permutation Networks." *IEEE Transactions on Computers*, vol. C-34, no. 5, pp. 412–425, May 1985. DOI: https://doi.org/10.1109/TC.1985.1676581
K. Y. Lee. "A New Benes Network Control Algorithm and Parallel Permutation Algorithm." *IEEE Transactions on Computers*, vol. C-30, no. 5, pp. 157–161, May 1981.
A. Waksman. "A Permutation Network." *Journal of the ACM*, vol. 15, no. 1, pp. 159–163, Jan. 1968. DOI: https://doi.org/10.1145/321439.321449
M. K. Kim, H. Yoon, and S. R. Maeng. "On the Correctness of Inside-Out Routing Algorithm." *IEEE Transactions on Computers*, vol. 46, no. 7, pp. 820–823, July 1997. DOI: https://doi.org/10.1109/12.599903
D. Nassimi and S. Sahni. "A Self-Routing Benes Network and Parallel Permutation Algorithm." *IEEE Transactions on Computers*, vol. C-30, no. 5, pp. 332–340, May 1981. DOI: https://doi.org/10.1109/TC.1981.1675791
A. Chakrabarty, M. Collier, and S. Mukhopadhyay. "Adaptive Routing Strategy for Large Scale Rearrangeable Symmetric Networks." *International Journal of Grid and High Performance Computing (IJGHPC)*, vol. 2, no. 2, pp. 53–63, 2010. DOI: https://doi.org/10.4018/jghpc.2010040105
D. Nassimi and S. Sahni. "A Self-Routing Benes Network." *Proceedings of the 7th Annual Symposium on Computer Architecture*, La Baule, France, pp. 190–195, May 1980. DOI: https://doi.org/10.1145/800053.801925
D. Nassimi and S. Sahni. "Parallel Algorithms to Set Up the Benes Permutation Network." *IEEE Transactions on Computers*, vol. C-31, no. 2, Feb. 1982. DOI: https://doi.org/10.1109/TC.1982.1675960
D. C. Opferman and N. T. Tsao-Wu. "On a Class of Rearrangeable Switching Networks, Part I: Control Algorithm." *Bell System Technical Journal*, vol. 50, pp. 1579–1600, 1971. DOI: https://doi.org/10.1002/j.1538-7305.1971.tb02569.x
S. Andresen. "The Looping Algorithm Extended to Base 2ᵗ Rearrangeable Switching Networks." *IEEE Transactions on Communications*, vol. COM-25, no. 10, pp. 1057–1063, Oct. 1977. DOI: https://doi.org/10.1109/TCOM.1977.1093753
Steve Furber. *ARM System-on-Chip Architecture*. Addison-Wesley Longman Publishing Co., Inc., 2000.
Tobias Bjerregaard and Shankar Mahadevan. "A Survey of Research and Practices of Network-on-Chip." *ACM Computing Surveys*, vol. 38, June 2006. DOI: https://doi.org/10.1145/1132952.1132953
Drew Wingard. "MicroNetwork-Based Integration for SoCs." *Proceedings of the 38th Design Automation Conference*, pp. 673–677, 2001. DOI: https://doi.org/10.1145/378239.379046
Andreas Gerstlauer, Gunar Schirner, Dongwan Shin, Junyu Peng, Rainer Dömer, and Daniel D. Gajski. *System-on-Chip Component Models*. Technical Report, University of California, Irvine, 2006.
Pierre Guerrier Alain and Alain Greiner. "A Generic Architecture for On-Chip Packet-Switched Interconnections." *Proceedings of the Design, Automation and Test in Europe (DATE) Conference*, pp. 250–256, 2000. DOI: https://doi.org/10.1145/343647.343776
Hasan Çam and Jose A. B. Fortes. "Work-Efficient Routing Algorithms for Rearrangeable Symmetrical Networks." *IEEE Transactions on Parallel and Distributed Systems*, vol. 10, no. 7, July 1999. DOI: https://doi.org/10.1109/71.780867
R. Cypher, J. L. C. Sanz, and L. Snyder. "An EREW PRAM Algorithm for Image Component Labeling." *IEEE Transactions on Pattern Analysis and Machine Intelligence*, vol. 11, no. 3, Mar. 1989. DOI: https://doi.org/10.1109/34.21794
William J. Dally and Brian Towles. "Route Packets, Not Wires: On-Chip Interconnection Networks." *Proceedings of the 38th Annual Design Automation Conference*, pp. 684–689, 2001. DOI: https://doi.org/10.1145/378239.379048
L. Benini and G. De Micheli. "Networks on Chips: A New SoC Paradigm." *Computer*, vol. 35, pp. 70–78, 2002. DOI: https://doi.org/10.1109/2.976921
Jiang Xu, Wayne Wolf, Joerg Henkel, Srimat Chakradhar, and Tiehan Lv. "A Case Study in Networks-on-Chip Design for Embedded Video." *Proceedings of the Design, Automation and Test in Europe Conference*, vol. 2, 2004.
Downloads
Published
Issue
Section
License
Copyright (c) 2026 Amitabha Chakrabarty
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
