Study On Routing Algorithm Of Communication In Parallel System With Irregular Topology

Parallel distributed system is widely used in many fields such as automation control, aviation, military affairs and business affairs. It is significant to increase its usability, reliability, applicability for realizing such a crucial distributed system. Networks of Workstations (NOWs) are rapidly emerging as a cost-effective alternative to parallel computers. In a real-time system, finite response time restriction must be fulfilled or it will lead to catastrophic effect. Effective communication mechanisms between processes are indispensable to a distributed system, and are vital to its performance. The distributed parallel system before usually uses network with regular topology. This link method between processors makes routing more fixed and relatively easy, but results in being lack of fault tolerance. Only a little error happening in one node will bring to that the whole network is not available. Switch-based interconnects with irregular topology allow the wiring flexibility, scalability, and expansion capability required in this environment. However, the irregularity also makes routing and deadlock avoidance on such systems quite complicated. So destination of designing routing algorithm is clearly to boot efficiency, on the base of deadlock avoidance and adaptive routing. A distributed routing algorithm-UP*/DOWN* algorithm was implemented in some commercial networks, like Myrinet or Autonet. But it has some shortcomings, for example, inflexible and non-minimal paths. Meanwhile, wormhole switch and virtual channel are proposed respectively for the same purpose that is increase its performance. This paper integrates several message passing methods, takes advantage of wormhole switch and virtual channel technologies, and combined with routing algorithms existing, put forward a routing algorithm scheme whose name is "three subdivision". At the close of this paper, an emulation software was employed to test our algorithm scheme. Then we compared the results with performance value under UP*/DOWN* routing algorithm to testify the rightness of our hypothesis about routing scheme.