Top

The Journal of Supercomputing

Published in:

26-03-2021

Routing algorithms for the shuffle-exchange permutation network

Authors: Behnam Khosravi, Behrooz Khosravi, Bahman Khosravi

Published in: The Journal of Supercomputing | Issue 10/2021

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

For a natural number n, let \(S_n\) denote the symmetric group on n letters. Let \(\textit{SEP}_n\) be the Cayley graph \(\text {Cay}(S_n,\{\sigma ,\sigma ^{-1},\tau \})\), where \(\tau =(12)\) and \(\sigma =(1,\ldots , n)\). In this note, we present an easy static routing algorithm for \(\textit{SEP}_n\) which gives us an exact formula for the path between every pair of nodes in \(\textit{SEP}_n\) and it does not need any calculations. Also, we show that an upper bound of this algorithm is \(\lfloor {(3n+1)^2/ 9}\rfloor\). Furthermore, we use our results to present a dynamic routing algorithm for \(\textit{SEP}_n\) which needs at most n calculations for routing and also it does not need large amount of memory for routing tables.

previous article A novel multiclass priority algorithm for task scheduling in cloud computing

next article A frequency-aware and energy-saving strategy based on DVFS for Spark

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Akers SB, Krishnamurth A (1989) A group-theoretic model for symmetric interconnection networks. IEEE Transactions on Computers 38(4):555–566MathSciNetCrossRef

Aguirre-Guerrero D, Ducoffe G, Fabrega F, Vil P, Coudert D (2019) Low time complexity algorithms for path computation in Cayley Graphs. Discrete Applied Mathematics 259:218–225MathSciNetCrossRef

Camelo M, Papadimitriou L, Fabrega L, Vil P (2014) Efficient routing in data center with underlying Cayley graphs, Complex Networks V, 189–197

Camelo M, Vil P, Fabrega L, Papadimitriou D (2014) Cayley-Graph-based Data Centers and Space Requirements of a Routing Scheme using Automata, IEEE 34th International Conference on Distributed Computing Systems Workshops, 63–69

Cameron P (1999) Permutation groups. Cambridge University Press, CambridgeCrossRef

Chen B, Xiao W (2005) Routing algorithm for the Rotation-Exchange network. Journal of Electronics (China) 22:255–260CrossRef

Chen B, Xiao W, Du N (2006) A New Routing Algorithm for the Shuffle-Exchange Permutation Network. Jrl Syst Sci & Complex 19:589–5916MathSciNetCrossRef

Coudert D, Ducoffe G (2016) Data center interconnection networks are not hyperbolic. Theoretical Computer Science 639:72–90MathSciNetCrossRef

Cunningham DW, “A Logical Introduction to Proof”, Springer, New York

10.

Dixon JD, Mortimer B (1996) Permutation groups. Springer-Verlag, New YorkCrossRef

11.

Fragapoulou P, Akl SG (1995) Optimal Communication Algorithms on Star Graphs Using Spanning Tree Constructions. Journal of Parallel and Distributed Computing 24(1):55–71CrossRef

12.

Ganesan A (2016) Cayley graphs and symmetric interconnection networks, In Proceedings of the Pre-Conference Workshop on Algebraic and Applied Combinatorics (31st Annual Conference of the Ramanujan Mathematical Society), Trichy, Tamilnadu, India, 118–170

13.

Heydemann MC (1997) Cayley graphs and interconnection networks. Springer, Netherlands, DordrechtCrossRef

14.

Iwasaki T, Kaneko K (2010) Fault-tolerant routing in burnt pancake graphs. Information Processing Letters 110:535–538MathSciNetCrossRef

15.

Konstantinova E (2008) Some problems on Cayley graphs. Linear Algebra and its Applications 429(11–12):2754–2769MathSciNetCrossRef

16.

Kuznetsov AA, Kishkan VV (2020) A routing algorithm for the Cayley graphs generated by permutation groups. Siberian Journal of Science and Technology 21(2):187–194CrossRef

17.

Latifi S, Srimani PK (1999) SEP: A fixed degree regular network for massively parallel systems. The Journal of Supercomputing 12:207–214MATH

18.

Bruce M, Maggs BM, Sitaraman RK (1998) Simple Algorithms for Routing on Butterfly Networks with Bounded Queues. SIAM Journal on Computing 28(3):984–1003MathSciNetCrossRef

19.

Ryu J, Noel E, Wendy Tang K (2012) Distributed and Fault-Tolerant Routing for Borel Cayley Graphs. International Journal of Distributed Sensor Networks 8(10):1–15CrossRef

20.

Sawada J, Williams A (2018) A Hamilton path for the sigma-tau problem, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 568–575. SIAM, Philadelphia, PA

21.

Schibell ST, Stafford RM (1992) Processor interconnection networks from Cayley graphs. Discrete Applied Mathematics 40:333–357MathSciNetCrossRef

22.

Seo J (2013) Three-dimensional Petersen-torus network: a fixed-degree network for massively parallel computers. The Journal of Supercomputing 64:987–1007CrossRef

23.

Tan YS, On the diameter of Cayley graphs of finite groups, (available at: https://www.math.uchicago.edu/~may/VIGRE/VIGRE2011/REUPapers/Tan.pdf)

24.

Williams A, Hamiltonicity of the Cayley digraph on the symmetric group generated by \((1 2)\) and \((1 2\cdots n)\), arXiv:1307.2549 [.org/abs], 2013, 14 pp

Title: Routing algorithms for the shuffle-exchange permutation network
Authors: Behnam Khosravi
Behrooz Khosravi
Bahman Khosravi
Publication date: 26-03-2021
Publisher: Springer US
Published in: The Journal of Supercomputing / Issue 10/2021
Print ISSN: 0920-8542
Electronic ISSN: 1573-0484
DOI: https://doi.org/10.1007/s11227-021-03694-8

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Other articles of this Issue 10/2021

An efficient parallel indexing structure for multi-dimensional big data using spark

Streaming techniques: revealing the natural concurrency of the lattice Boltzmann method

Multidimensional adaptative and deterministic integration in CUDA and OpenMP

An energy-efficient big data workflow scheduling algorithm under budget constraints for heterogeneous cloud environment

A method of progression detection for glaucoma using K-means and the GLCM algorithm toward smart medical prediction

Epidemic zone of COVID-19 from social media using hypergraph with weighting factor (HWF)

Premium Partner