The Torus Exchange Structure Of Flow Balancing And Fault-tolerant Routing Algorithm

Along with the application of computer in every filed, computer plays a more and more important role in national economics. These fields which rely on the computer more seriously desiring the supercomputer that has higher processing speed, more network bandwidth and bigger storage capability. The parallel multiprocessor is a possible solution to realize the high computing performance. The correlation technology based on the parallel multiprocessor is also developing rapidly, such as the network topology structure, switching technology, routing algorithm. With the flexible scalability and larger capacity, Torus switching fabric is being widely used to construct high speed terabit routers.There are many factors affecting the performance of parallel multiprocessor according to the network technology, such as the degree of adaptiveness of routing algorithm, the uneven distributing of traffic. With the increasing of traffic patterns and switching nodes, the routing function which include fault-tolerant and Qos supporting also desire more and more attention. So in this paper, our attention is mainly focusing on the fault-tolerant routing and load-balanced adaptive routing.The contributions of our research mainly lie in that we firstly introduce the load-balanced adaptive routing algorithm in torus network based on the odd-even turn model, imposing the symmetric odd-even turn models into the two virtual networks, at the same time, packet can switch between the two virtual networks if abide by some restriction, our routing algorithm provide the equal adaptiveness for all packets and load the traffic distribute evenly, moreover the performance of the routing algorithm which may affected by the traffic model is less fluctuant and the utilization of virtual channel is increased at the most level, so it can provide the stable throughput and end to end delay. Secondly, we also propose the two level turn models fault-tolerant routing algorithm based on the convex and convex fault block. The algorithm is bring forward by exploring the self-characteristic of PFNF routing algorithm which can provide the flexible turn and mutul-switching property, it is very useful when apply in the fault-tolerant function, the algorithm has the good merit that it's cost complexity is very low and the response speed is prompt and can easily apply in different fault models, so it has the good maneuverability.This thesis is organized as follows:Chapter 1 introduces the topology structure of switching fabric ,the corresponding switching technology and the base requirement of routing algorithm, then analyses the deadlock ,live-lock and the starvation when the packet routing in the network.Chapter 2 mainly introduces the different routing schemes in the torus switch fabric and compares the advantage and disadvantage of the performance,then we deduct the research direction and correlation work.Chapter 3 give the key ideal of the traffic-balanced adaptiveness routing algorithm based on the odd-even turn model, analyses the adaptiveness and the traffic-balanced of the two level odd-even turn model; then we bring forward the whole algorithm flow and deduce the proof of the deadlock-free; at the end, we compare the performance with other adaptive algorithm in different flow models.In chapter 4, we firstly analyze the adaptiveness and load-balanced trait of the positive-first and negative-first routing algorithm, and do some research about its fault-tolerant property, then we do some restriction for the routing algorithm according to the specific fault models, so as to bypass the fault nodes. At the same time, we describe the fault-tolerant routing schemes .At the end, we evaluate the performance of the algorithm and analyze the factors about the declined performanceThe platform is described in detail in chapter 5 and the main models are given out, at the end of the dissertation, summaries are made.