消息传递网络中的消息传递机制和路由算法

Message Passing Mechanism and Routing Algorithm in Message Passing Interconnection Networks

消息传递网络应用十分广泛,小到超大规模集成(VLSI)内部总线,大到计算机广域网.对其中一种消息传递网络———3D环型立方体结构中消息传递机制以及路由算法进行了深入研究,提出了无死锁和无活锁的确定性路由与自适应路由相结合的路由算法,考察了虚拟直通(cut-through)和存储转发(store-and-forward)两种消息传递机制下的性能表现.通过在3D环型立方体网络上的模拟运算,验证了所提出的算法在传输延时、吞吐率等方面的性能提高;也验证了不同的消息传递机制对网络传输效率的影响.

Message passing interconnection networks are widely used under various conditions, with the scales ranging from VLSI internal bus to WAN. In this paper, message passing mechanism and routing algorithm in a message passing interconnection network--3D-torus interconnection network are discussed. A combination of DOR and partial adaptive routing algorithm with deadlock-free and livelock-free characteristics are presented. Two typical message-passing mechanisms, virtual cut-through and store-and-forward, are investigated to evaluate the performance. Test and comparison between the message passing mechanisms and routing algorithms in a simulator of 3D-torus topology show that the proposed partial adaptive routing algorithm can improve the network performance in terms of transmission latency and throughput, and also show that different message passing mechanisms will definitively affect the network transmission efficiency.