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

Sujets

• Informatik

Informations

• Publié par: technische_universitat_ilmenau
• Publié le: 01 janvier 2002
• Nombre de lectures: 4
• Langue: English

Extrait

Aspects of k-k Routing in Meshes and
OTIS Networks.
Dissertation zur Erlangung des akademischen Grades
Doctor rerum naturalium
(Dr. rer. nat.)
vorgelegt der Fakult at Informatik und Automatisierung
der Technischen Universit at Ilmenau
von
Dipl. Inform. Andre Osterloh
Gutacher:
1. Univ.-Prof. Dr. Manfred Kunde, Technische Universit at Ilmenau
2. Dr. Michael Kaufmann, Universit at Tubingen?
3. Priv.-Doz. Dr. Peter Rossmanith, Technische Universit at Munc? hen
vorgelegt am:
10. Juni 2002
verteidigt am:
19. September 20022Abstract
Efficientdatatransportinparallelcomputersbuildonsparseinterconnection
networks is crucial for their performance. A basic transport problem in
such a computer is the k-k routing problem. In this thesis, aspects of the
k-k routing problem on r-dimensional meshes and OTIS-G networks are
discussed. The first oblivious routing algorithms for these networks are
presented that solve the k-k routing problem in an asymptotically optimal
running time and a constant buffer size. Furthermore, other aspects of the
k-k routingproblemforOTIS-Gnetworksareanalysed. Inparticular, lower
boundsfortheproblembasedonthediameterandbisectionwidthofOTIS-
G networks are given, and the k-k sorting problem on the OTIS-Mesh is
considered. Based on OTIS-G networks, a new class of networks, called
Extended OTIS-G networks, is introduced, which have smaller diameters
than OTIS-G networks.2Contents
1 Introduction. 1
1.1 Outline of the Thesis. . . . . . . . . . . . . . . . . . . . . . . 3
2 Basic Definitions. 7
2.1 Basic Definitions in Graph Theory. . . . . . . . . . . . . . . . 7
2.2 Definition of the Model. . . . . . . . . . . . . . . . . . . . . . 9
2.2.1 Model of Computation. . . . . . . . . . . . . . . . . . 9
2.2.2 Routing Problems, Packets and Algorithms. . . . . . . 10
2.3 Embeddings and Emulations. . . . . . . . . . . . . . . . . . . 14
3 Meshes and Basic Problems. 16
3.1 Definitions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.2 Routing in One-Dimensional Meshes. . . . . . . . . . . . . . . 18
3.2.1 Embedding into Networks.. . . . . . . . . . . . . . . . 19
3.2.2 Routing with Bounds on Arrival Times. . . . . . . . . 19
3.2.3 Dynamic Routing. . . . . . . . . . . . . . . . . . . . . 27
3.3 Conclusion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4 Oblivious Routing. 46
iii CONTENTS
4.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.2 Discussion of Previous Results. . . . . . . . . . . . . . . . . . 50
4.2.1 The Algorithm Presented in [11, 14]. . . . . . . . . . . 50
4.2.2 The Presented in [32]. . . . . . . . . . . . . 53
4.3 High Level Structure of the Algorithm. . . . . . . . . . . . . . 55
4.4 Oblivious k-k Routing. . . . . . . . . . . . . . . . . . . . . . . 56
4.4.1 Oblivious k-k Routing on Networks. . . . . . . . . . . 56
4.4.2 k-k Routing on r-Dimensional Meshes. . . . 67
4.5 Conclusion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
5 OTIS Networks. 80
5.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
5.2 Definition of OTIS-G Networks. . . . . . . . . . . . . . . . . . 82
5.3 A Lower Bound for Routing on OTIS-G Networks. . . . . . . 83
5.4 Sorting on the OTIS-Mesh. . . . . . . . . . . . . . . . . . . . 85
5.4.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . 86
5.4.2 Sorting with All-to-All Mappings. . . . . . . . . . . . 87
5.4.3 Emulation of M by OTIS-M . . . . . . . . . . . . 904;n 2;n
5.4.4 Substructures in the OTIS-Mesh. . . . . . . . . . . . . 93
5.4.5 All-to-All Mapping. . . . . . . . . . . . . . . . . . . . 95
5.4.6 The Sorting Algorithm. . . . . . . . . . . . . . . . . . 101
5.4.7 A Lower Bound for Sorting on the OTIS-Mesh. . . . . 103
5.4.8 A Comparison with Mesh Algorithms. . . . . . . . . . 104
5.5 Oblivious Routing on OTIS-G Networks. . . . . . . . . . . . . 105
5.6 Diameter of OTIS-G Networks. . . . . . . . . . . . . . . . . . 107CONTENTS iii
5.7 Extended OTIS-G Networks. . . . . . . . . . . . . . . . . . . 115
5.7.1 Basic Definitions and Properties. . . . . . . . . . . . . 115
5.7.2 Shortest Paths in Extended OTIS-G Networks. . . . . 116
5.7.3 Diameter of Extended OTIS-G Networks. . . . . . . . 122
5.7.3.1 Hypercubes. . . . . . . . . . . . . . . . . . . 123
5.7.3.2 Rings. . . . . . . . . . . . . . . . . . . . . . . 126
5.7.3.3 One-dimensional Meshes. . . . . . . . . . . . 136
5.7.3.4 Two-dimensional Meshes. . . . . . . . . . . . 140
5.8 Conclusion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
Appendix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
Theses of the dissertation. . . . . . . . . . . . . . . . . . . 157
Zusammenfassung. . . . . . . . . . . . . . . . . . . . . . . 159
Erklarung.? . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160List of Figures
2.1 A packet used in routing. . . . . . . . . . . . . . . . . . . . . 11
3.1 The structure of M . . . . . . . . . . . . . . . . . . . . . . . 171;5
3.2 The structure of M . . . . . . . . . . . . . . . . . . . . . . . 172;4
3.3 An example for the problem considered in Section 3.2.3. . . . 27
3.4 A one-dimensional mesh of size m with m injectors. . . . . . 27
4.1 A (4;4)-partition of size (4;4;3) of M . . . . . . . . . . . . . 692;4
4.2 Path of a packet in oblivious routing. . . . . . . . . . . . . . . 70
4.3 Source and destination blocks in M . . . . . . . . . . . . . 743;15
4.4 Source blocks and exit nodes. . . . . . . . . . . . . . . . . . . 75
4.5 Connection paths from exit to entry nodes. . . . . . . . . 76(i;2)
4.6 Trees in a partitioning of M . . . . . . . . . . . . . . . . . . 763;16
5.1 The structure of OTIS-M .. . . . . . . . . . . . . . . . . . . 842;2
5.2 An OTIS-G network divided in two areas. . . . . . . . . . . . 85
5.3 Superblocks, blocks, and bricks in an OTIS-Mesh network. . . 94
5.4 An OTIS-Mesh divided in two areas X and Y. . . . . . . . . 103
5.5 Extended OTIS-G networks,jV j=2. . . . . . . . . . . . . . 123G
ivLIST OF FIGURES v
5.6 HCN(2,2). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
5.7 The structure of X . . . . . . . . . . . . . . . . . . . . . . 127R ;f3
5.8 The structure of X . . . . . . . . . . . . . . . . . . . . . . 128R ;f4 4
5.9 Mirror property of f . . . . . . . . . . . . . . . . . . . . . . . 129n
5.10 Cases for the proof of Lemma 5.38. . . . . . . . . . . . . . . . 132
5.11 Cases for the proof of Lemma 5.39. . . . . . . . . . . . . . . . 134
5.12 The structure of X . . . . . . . . . . . . . . . . . . . . . 137M ;f1;4 4
5.13 The structure of X . . . . . . . . . . . . . . . . . . . . . 137M ;f1;5 5
5.14 The structure of X (without optical links). . . . . . . . 141M ;f2;3 3Chapter 1
Introduction.
Parallel computers consist of (two or more) processors. To solve problems
efficiently these processors have to communicate with each other. There are
different communication methods possible, e.g.
† Communication via shared-memory. A theoretical parallel computer
model,inwhichcommunicationisbasedonshared-memory,isreferred
to as PRAM (parallel random access machine). A PRAM consists of
a global memory that is uniformly accessible to all processors. There
exists a global clock, enabling the processors to execute instructions
in a synchronous way. Communication among the processors is done
using the global memory.
† Communication via links. A parallel computer is modeled by a syn-
chronizednetworkofprocessorsconnectedbylinks. Insuchanetwork,
adirectcommunicationbetweentwoprocessorsisonlypossibleifthey
are connected by a link. For the communication of two non-connected
processors, datahastobetransportedthroughthenetworkviaapath
of directly connected processors.
1