Aspects of k-k routing in meshes and OTIS networks [Elektronische Ressource] / von Andre Osterloh

Aspects of k-k Routing in Meshes andOTIS Networks.Dissertation zur Erlangung des akademischen GradesDoctor rerum naturalium(Dr. rer. nat.)vorgelegt der Fakult at Informatik und Automatisierungder Technischen Universit at IlmenauvonDipl. Inform. Andre OsterlohGutacher:1. Univ.-Prof. Dr. Manfred Kunde, Technische Universit at Ilmenau2. Dr. Michael Kaufmann, Universit at Tubingen?3. Priv.-Doz. Dr. Peter Rossmanith, Technische Universit at Munc? henvorgelegt am:10. Juni 2002verteidigt am:19. September 20022AbstractEfficientdatatransportinparallelcomputersbuildonsparseinterconnectionnetworks is crucial for their performance. A basic transport problem insuch a computer is the k-k routing problem. In this thesis, aspects of thek-k routing problem on r-dimensional meshes and OTIS-G networks arediscussed. The first oblivious routing algorithms for these networks arepresented that solve the k-k routing problem in an asymptotically optimalrunning time and a constant buffer size. Furthermore, other aspects of thek-k routingproblemforOTIS-Gnetworksareanalysed. Inparticular, lowerboundsfortheproblembasedonthediameterandbisectionwidthofOTIS-G networks are given, and the k-k sorting problem on the OTIS-Mesh isconsidered. Based on OTIS-G networks, a new class of networks, calledExtended OTIS-G networks, is introduced, which have smaller diametersthan OTIS-G networks.2Contents1 Introduction. 11.1 Outline of the Thesis. . . . . . . . . . . . . . . . . . . . . . .