Postadresse: 80290 München; Hausadresse: Arcisstr.21, 80333
München
Effiziente Einbettungen baumartiger Graphen in den Hyperwürfel
Abbildungen von Kommunikationsstrukturen in Algorithmen auf Topologien von
massiven Parallelrechnern lassen sich bekanntermaßen sehr gut durch
Grapheinbettungen mathematisch modellieren.
Da solche Abbildungen eine effiziente Ausführung paralleler
Algorithmen erlauben, wird vielfach nach Einbettungen hoher Güte
gesucht.
Bislang waren Einbettungen hoher Güte fast nur für regulär
strukturierte Gastgraphen bekannt.
In dieser Arbeit wird ein flexibles, allgemeines zweistufiges Schema
vorgestellt, das sich insbesondere für Einbettungen von
irregulär strukturierten Graphen hervorragend eignet.
Außerdem hat das Verfahren durch seine Zweistufigkeit ein
großes Maä an Flexibilität gezeigt und erlaubt
Einbettungen hoher Güte sowohl für zahlreiche Graphklassen als
Gastgraphen als auch für viele verschiedene Klassen von
hyperwürfelähnlichen Topologien als Wirtsgraphen.
Darüber hinaus lassen sich die so gewonnen Einbettungen sehr
effizient auf diesen Zieltopologien berechnen.
Mit Hilfe dieses Schemas können außerdem dynamische
Einbettungen realisiert werden, die naturgemäß von sehr
großem Interesse in der Praxis sind.
