In a message-based multiprocessor system that consists of message-communicating processors, the interconnection network is really a crucial part for fast processor communication. Among various interconnection methods, using the high-speed asynchronous transfer mode (ATM) switch is an attractive approach to constructing large-scale multiprocessor systems with low latency and high throughput. The interconnection network for fast processor communication is proposed in this paper. For the efficient use of the ATM switch, a group of the cell interface modules (CIMs) called a cell router which performs cell multiplexing and demultiplexing, is located between the processor groups and the ATM switch. In this proposed system, an expanded internal cell format in which three bytes are added for the switch routing information, is used. The interconnection network uses three routing strategies: the ATM switch routing using the switch routing information, the cell router routing using the virtual path identifier (VPI), and the cell reassembly routing using the virtual channel identifier (VCI). The interconnection network consists of a N/spl times/N folded switch and N cell routers. Since each cell router has M processor interfaces, the maximum N/spl times/M processors can be interconnected. In terms of message-passing latency and scalability, the interconnection network using the ATM switch shows a significant improvement on the performance. The transmission overhead of the interconnection network using the ATM switch has also been evaluated. The overhead ratio of the message communication using ATM switch is almost 15%.

A multistage interconnection network is a suitable class of interconnection architecture for constructing large-scale multicomputers. Broadcast and multicast communication are fundamental in supporting collective communication operations such as reduction and barrier synchronization. In this paper, we propose a new multicast technique in wormhole-switched bidirectional multistage Banyan networks for constructing large-scale multicomputers. To efficiently support broadcast and multicast with simple additional hardware without deadlock, we propose a two-phase multicast algorithm which takes only two transmissions to perform a broadcast and a multicast to an arbitrary number of desired destinations. We encode a header as a cube and adopt the most upper input link first scheme with periodic priority rotation as arbitration mechanism on contented output links. We coalesce the desired destination addresses into multiple number of cubes. And then, we evaluate the performance of the proposed algorithm by simulation. The proposed two-phase multicast algorithm makes a significant improvement in terms of latency. It is noticeable that the two-phase algorithm keeps broadcast latency as efficient as the multicast latency of fanout 2m where m is the minimum integer satisfying 2/sup m//spl ges//spl radic/(N) (N is a network size).

We study wormhole routed networks and their suitability for real-time traffic in a priority-driven paradigm. A traditional blocking flow control in wormhole routing may lead to a priority inversion in the sense that high priority packets are blocked by low priority packets for unlimited time. This uncontrolled priority inversion causes the frequent deadline missing. This paper therefore proposes a new flow control called throttle and preempt flow control, where high priority packets can preempt network resources held by low priority packets, if necessary. As a result, this flow control does not cause priority inversion. Our simulations show that the throttle and preempt flow control dramatically reduces deadline miss ratio without extra virtual channels. It is also observed that the throttle and preempt flow control offers shorter delay for non-real-time traffic than existing real-time flow control does.

An ATM switch based on multistage interconnection networks with multiple paths can support higher bandwidth than that of buffered networks with single path by passing multiple packets to the same destination simultaneously. These multiple packets are buffered in the output buffer of the destination. The performance of output buffer in the switch with multiple paths is closely dependent on the output traffic distribution, which is the packet arrival rate at each output link destined to a given output port. As the nonuniformity of the output traffic distribution becomes higher, the performance of the output buffer as like delay and packet loss probability gets better. In this paper, we propose a new self-routing switch architecture with multiple paths called Fly network and analyze the performance of the switching network and the output buffer focusing on the output traffic distribution. It is shown that the Fly network supports best throughput and latency of the output buffer by producing a high degree of the nonuniform output traffic distribution.