Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
The Journal of Supercomputing
Erschienen in: The Journal of Supercomputing 2/2019

20.09.2018

An efficient algorithm for embedding exchanged hypercubes into grids

verfasst von: Weibei Fan, Jianxi Fan, Cheng-Kuan Lin, Guijuan Wang, Baolei Cheng, Ruchuan Wang

Erschienen in: The Journal of Supercomputing | Ausgabe 2/2019

Einloggen

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

search-config
loading …

Abstract

Graph embedding is an important technology in simulating parallel structures and designing VLSI layout. Hypercube is one of the most significant interconnection networks in parallel computing systems. The exchanged hypercube is an important variant of the hypercube, which is obtained by systematically deleting edges from a hypercube. It not only retains several valuable and desirable properties of the hypercube, but also has lower hardware cost. In this paper, we first give an exact formula of minimum wirelength of exchanged hypercube layout into a grid. Furthermore, we propose an O(N) algorithm for embedding exchanged hypercube into a gird with load 1, expansion 1 and minimum wirelength and derive a linear layout of exchanged hypercube with minimum number of tracks and efficient layout areas. Finally, we present simulation experiments of our embedding algorithm on network overhead and total wirelength, which conduce to estimate the total wirelength and chip area.
Vorheriger Artikel A novel and fast nonlocal means denoising algorithm using a structure tensor
Nächster Artikel Virtualization and consolidation: a systematic review of the past 10 years of research on energy and performance

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
Literatur
1.
Arabnia HR, Oliver MA (1986) Fast operations on raster images with SIMD machine architectures. Int J Eurographics Assoc (Comput Graph Forum) 5(3):179–189CrossRef
2.
Valafar H, Arabnia HR, Williams G (2004) Distributed global optimization and its development on the multiring network. Int J Neural Parallel Sci Comput (Dynamic Publishers) 12(4):465–490MathSciNetMATH
3.
Hamid R, Arabnia A (1990) Parallel algorithm for the arbitrary rotation of digitized images using process-and-data-decomposition approach. J Parallel Distrib Comput 10(2):188–193CrossRef
4.
Hamid R Arabnia (1995) A distributed stereocorrelation algorithm. In: Proceedings of Fourth International Conference on IEEE Computer Communications and Networks, INSPEC Accession Number 5557991, pp 479–482
5.
Arabnia Hamid R, Bhandarkar SM (1996) Parallel stereocorrelation on a reconfigurable multi-ring network. J Supercomput 10(3):243–270 (Special Issue on Parallel and Distributed Processing) CrossRefMATH
6.
Arabnia HR, Taha TR (1998) A parallel numerical algorithm on a reconfigurable multi-ring network. J Telecommun Syst 10:185–203CrossRef
7.
Bhandarkar SM (1997) Parallel computer vision on a reconfigurable multiprocessor network. IEEE Trans Parallel Distrib Syst 8(3):292–310CrossRef
8.
9.
Yeh C-H, Varvarigos EA, Parhami B (2000) Multilayer VLSI layout for interconnection networks. In: Proceedings of the International Conference on Parallel Processing, pp 33–40
10.
Singh SP, Sharma RRK (2006) A review of different approaches to the facility layout problems. Int J Adv Manuf Technol 30(5–6):425–433CrossRef
11.
Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. Freeman, San Francisco
12.
13.
14.
Liu YL (2015) Routing and wavelength assignment for exchanged hypercubes in linear array optical networks. Inf Process Lett 115(2):203–208MathSciNetCrossRefMATH
15.
Yu C, Yang X (2012) Routing and wavelength assignment for 3-ary \(n\)-cube in array-based optical network. Inf Process Lett 112(6):252–256MathSciNetCrossRefMATH
16.
Bezrukov SL, Chavez JD, Harper LH, Röttger M, Schroeder UP (1998) Embedding of hypercubes into grids. In: Brim L, Gruska J, Zlatuška J (eds) International Symposium on Mathematical Foundations of Computer Science, vol 1450. Springer, Berlin, Heidelberg, pp 693–701
17.
Bezrukov SL, Chavez JD, Harper LH (2000) The congestion of \(n\)-cube layout on a rectangular grid. Discrete Math 213(1–3):13–19MathSciNetCrossRefMATH
18.
Abraham J, Arockiaraj M (2017) Optimal embedding of locally twisted cubes into grids. In: Proceedings of International Conference on Springer Algorithms and Discrete Applied Mathematics, pp 1–11
19.
Han Z, Li Y, Li J (2018) A novel routing algorithm for IoT cloud based on hash offset tree. Future Gener Comput Syst 86:456–463CrossRef
20.
Xiang D, Chakrabarty K, Fujiwara H (2016) Multicast-based testing and thermal-aware test scheduling for 3D ICs with a stacked network-on-chip. IEEE Trans Comput 65(9):2767–2779MathSciNetCrossRefMATH
21.
22.
23.
Lv YL, Lin C-K, Fan JX (2017) Hamiltonian cycle and path embeddings in \(k\)-ary \(n\)-cubes based on structure faults. Comput J 60(2):159–179MathSciNet
24.
25.
Zhou DF, Fan JX, Lin C-K, Cheng BL, Zhou JY, Liu Z (2017) Optimal path embedding in the exchanged crossed cube. J Comput Sci Technol 32(3):618–629MathSciNetCrossRef
26.
27.
28.
29.
Loh PKK, Hsu WJ, Pan Y (2005) The exchanged hypercube. IEEE Trans Parallel Distrib Syst 16(9):866–874CrossRef
30.
31.
32.
Zhang Z, Deng Y, Min G, Xie J, Huang S (2017) ExCCC-DCN: a highly scalable, cost-effective and energy-efficient data center structure. IEEE Trans Parallel Distrib Syst 28(4):1046–1060CrossRef
33.
Thompson CD (1980 Aug) A complexity theory for VLSI. Ph.D. thesis, Carnegie-Mellon University
34.
Bezrukov SL, Das SK, Elsasser R (2000) An edge-isoperimetric problem for powers of the Petersen graph. Ann Comb 4(2):153–169MathSciNetCrossRefMATH
35.
Tsai T-H, Chen Y-C, Tan JJM (2016) Optimal edge congestion of exchanged hypercubes. IEEE Trans Parallel Distrib Syst 27(1):250–262CrossRef
36.
Katseff H (1988) Incomplete hypercubes. IEEE Trans Comput 37:604–608CrossRef
37.
Harper LH (2004) Global methods for combinatorial isoperimetric problems. Cambridge University Press, CambridgeCrossRefMATH
38.
Boals AJ, Gupta AK, Sherwani NA (1994) Incomplete hypercubes: algorithms and embeddings. J Supercomput 8(3):263–294CrossRef
39.
40.
Aroca JA, Anta AF (2014) Bisection (band) width of product networks with application to data centers. IEEE Trans Parallel Distrib Syst 25(3):570–580CrossRef
41.
Massie ML, Chun BN, Culler DE (2004) The ganglia distributed monitoring system: design, implementation, and experience. Parallel Comput 30(7):817–840CrossRef
42.
Zhang J, Yang X, Yu C, Li H, Yang L (2013) Implementing duplex crossed cube communication patterns on optical linear arrays. Optik Int J Light Electron Opt 124(24):6496–6500CrossRef
43.
Glantz R, Meyerhenke H (2015) Algorithms for mapping parallel processes onto grid and torus architectures. In: proceedings of International Conference on IEEE 23rd Euromicro Parallel, Distributed and Network-Based Processing (PDP), pp 236–243
Metadaten
Titel
An efficient algorithm for embedding exchanged hypercubes into grids
verfasst von
Weibei Fan
Jianxi Fan
Cheng-Kuan Lin
Guijuan Wang
Baolei Cheng
Ruchuan Wang
Publikationsdatum
20.09.2018
Verlag
Springer US
Erschienen in
The Journal of Supercomputing / Ausgabe 2/2019
Print ISSN: 0920-8542
Elektronische ISSN: 1573-0484
DOI
https://doi.org/10.1007/s11227-018-2612-2

Weitere Artikel der Ausgabe 2/2019

The Journal of Supercomputing 2/2019 Zur Ausgabe

OriginalPaper

A statistical downscaling framework for environmental mapping

OriginalPaper

On the modelling of optimal coordinated checkpoint period in supercomputers

OriginalPaper

Dynamic DAG scheduling for many-task computing of distributed eco-hydrological model

OriginalPaper

Fair multiple-workflow scheduling with different quality-of-service goals

OriginalPaper

A cognitive learning model in distance education of higher education institutions based on chaos optimization in big data environment

OriginalPaper

Binary executable file similarity calculation using function matching

Premium Partner

    Bildnachweise