Fault tolerant adaptive routing for two-dimensional mesh topologies /
Wormhole routing is widely regarded as the best routing technique for message passing within a parallel computer. Wormhole routing is implemented by dividing a message into a sequence of flow control digits (flits) that travel through the interconnection network in a pipelined fashion with the heade...
| Main Author: | |
|---|---|
| Format: | Thesis Book |
| Language: | English |
| Published: |
[Place of publication not identified] :
[publisher not identified] ;
1996.
|
| Subjects: | |
| Online Access: | http://proxy.library.tamu.edu/login?url=http://proquest.umi.com/pqdweb?did=739668421&sid=1&Fmt=2&clientId=2945&RQT=309&VName=PQD |
| Summary: | Wormhole routing is widely regarded as the best routing technique for message passing within a parallel computer. Wormhole routing is implemented by dividing a message into a sequence of flow control digits (flits) that travel through the interconnection network in a pipelined fashion with the header flit reserving the necessary communication resources. The communication resources are not released until the last flit of the message passes through the router. Most wormhole switched parallel computers having a two-dimensional mesh interconnection network have sacrificed fault-tolerance for routing simplicity in an effort to increase performance. Therefore, this research develops new high performance fault-tolerant unicast and broadcast message passing environments for parallel computers having an N x N two-dimensional mesh interconnection network with, at most, N - 1 faulty routers. This research can be summarized as follows: Development of a new adaptive unicast routing algorithm for fault-free N x N two-dimensional meshes and proof of the algorithm's correctness. Development of a new fault-tolerant unicast routing algorithm for N x N twodimensional meshes with up to N - I static or dynamic faults and correctness proofs for the algorithm. Development and implementation of a simulation tool that can be used to evaluate the performance of the new unicast routing algorithms by comparing them with routing algorithms proposed by other researchers. Performance evaluation of the fault-tolerant unicast routing algorithm in the presence of static router and link faults using the simulation tool. Development of a new fault-tolerant single source broadcasting algorithm for N x N two-dimensional meshes with, at most, N - 1 static faults and correctness proofs for the algorithm. Simulation studies indicate that the new adaptive routing algorithm (NARA) provides a 20% increase in system throughput over the popular X-Y routing scheme. Furthermore, the fault-tolerant algorithm is shown to provide performance that is identical to that of X-Y routing for up to 3 faults. Subsequent network faults only slightly reduce the throughput of the network. This research provides an efficient solution to the problem of fault-tolerant unicast and single source broadcast message passing within parallel computers having an N x N two-dimensional mesh interconnection topology. The extended mean time between system failures provided by the proposed solution will allow researches to use parallel computers to solve problems that require long periods of uninterruptable computation time. |
|---|---|
| Item Description: | Vita. "Major Subject: Computer Science". |
| Physical Description: | xiii, 92 leaves : illustrations ; 28 cm. Issued also on microfiche from University Microfilms Inc. |
| Bibliography: | Includes bibliographical references: pages 81-90. |