In this paper, we propose a new multicast technique in wormhole-switched bidirectional multistage interconnection network(B-MIN) for constructing large-scale multicomputer. In addition to point-to-point communication among processing nodes, multicast communication is an important issue for the performance of multicomputers. Multicast communication in which the same packet is delivered from a source node to an arbitrary number of destination nodes, is fundamental in supporting collective communication such as broadcast, reduction, and barrier synchronization. In wormhole-switched B-MIN, to support multicast efficiently without deadlock, we propose a two-phase multicast algorithm which takes only two transmissions to perform a multicast to the desired destinations. We encode a header as a cube and adopt the rotated-upper-input-port-first scheme as arbitration mechanism at output ports. And then, we show the blocking-freedom and deadlock -freedom of the proposed algorithm and evaluate the performance by simulation. The proposed multicast algorithm makes a significant improvement in terms of multicast latency.
본 눈문은 멀티컴퓨터 시스템(multicomputer system)의 통신망을 구성하는 웜홀(Wormhole)스위칭하는 양방향 다단계 상호 연결망(bidirectional multistage interconnection network)에서 동작하는 새로운 멀티캐스트(multicast)알고리즘(algorithm)울 제안한다. 본 논문에서의 멀티캐스트 통신은 하나의 소스(source)에서 여러개의 목적지(destination)로 패킷(packet)을 전송하는 방식이다. 멀티캐스트 통신은 방송 (broadcast), 복제(replication), 그리고 배리어 동기(barrier synchronization)등과 같이 멀키컴퓨터 시스템에서 빈번히 일어나는 통신 형태를 제공하는 기본이 되기 때문에, 유니캐스트(unicast)통신뿐만 아니라 통신망의 성능은 두 단계(two-phase)로 구성되며 웜홀 스위칭하는 양방향 다단계 큐브(cube)연결망에서 효과적으오 제공될 수 있다. 두 단계 멀티캐스트 알고리즘의 각 단계에서는 1회의 패킷 큐브(cube)로 인코딩(encoding)된다. 출력 포트(output port)에서의 중재(arbitration) 기법으로 우선 순위 입력 포트 우선 방식 (rotated-upper-input-port-first scheme)을 채택함으로써 교착상태(deadlock)를 방지한다. 본 논문은 제안된 알고리즘이 블라킹(blocking)과 교착상태를 발생시키지 않는다는 것을 증명하고, 시뮬레이션(simulation)을 통해 통신망의 지연 시간 관점에서 제안한 알고리즘이 높은 성능 향상을 가져온다는 것을 보인다.
