nach oben

The Journal of Supercomputing

Erschienen in:

26.03.2021

Routing algorithms for the shuffle-exchange permutation network

verfasst von: Behnam Khosravi, Behrooz Khosravi, Bahman Khosravi

Erschienen in: The Journal of Supercomputing | Ausgabe 10/2021

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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.

Vorheriger Artikel A novel multiclass priority algorithm for task scheduling in cloud computing

Nächster Artikel A frequency-aware and energy-saving strategy based on DVFS for Spark

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

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

Titel: Routing algorithms for the shuffle-exchange permutation network
verfasst von: Behnam Khosravi
Behrooz Khosravi
Bahman Khosravi
Publikationsdatum: 26.03.2021
Verlag: Springer US
Erschienen in: The Journal of Supercomputing / Ausgabe 10/2021
Print ISSN: 0920-8542
Elektronische ISSN: 1573-0484
DOI: https://doi.org/10.1007/s11227-021-03694-8

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Weitere Artikel der Ausgabe 10/2021

Improving the energy-efficiency of virtual machines by I/O compensation

Burst: real-time events burst detection in social text stream

Correction to: EDVWDD: Event‑Driven Virtual Wheel‑based Data Dissemination for Mobile Sink‑Enabled Wireless Sensor Networks

Multidimensional adaptative and deterministic integration in CUDA and OpenMP

A CPU-GPU-based parallel search algorithm for the best differential characteristics of block ciphers

Social collaborative filtering using local dynamic overlapping community detection