Unidirectional point-to-point ring based networks are currently popular choices for high performance multiprocessors. Their simple hardware interfaces can make them run at very high clock rates and provide wider data paths. And their simple interconnections can make it easy to use the raw bandwidth of the links to the fullest extent. In addition, a ring construction allows easy addition and removal of extra nodes. However, the fixed bandwidth of a ring, independent of ring size, limits the size of a ring within small ranges.
To accommodate a large number of nodes, rings must be interconnected to a multiple ring network. There are two main approaches to interconnect rings; synthesizing general topologies such as k-ary n-cube and multistage networks, and connecting rings in a hierarchical form. Synthesizing general topologies can be constructed with switches having large fan-out. The switches having large fan-out can reduce the distance between nodes but their complex hardware architecture causes a performance bottleneck. This type of networks has no considerations for the communication locality, often exhibited in many parallel applications, and requires relatively high construction cost. The hierarchical ring networks as a natural extension of a single ring use simple hardware interfaces and thus retain the advantages of unidirectional ring connections. But the hierarchical ring networks have been suffered from the limited scalability because the bandwidth of the network decreases as one moves toward the top of the hierarchy.
In this thesis, we propose a new multiple ring interconnection scheme, called the Multistage Ring Network (MRN). The MRN has a 2-level hierarchy of register insertion rings. The interconnection of global rings forms a type of the multistage network. The architecture of the MRN can reduce network complexities and increases communication efficiency by supporting effectively the communication locality of many parallel programs. Moreover, the MRN can diffuse approximately evenly the global traffic on the network to all global rings, and the bandwidth of the network increases proportionally with increases in the system size. The MRN can be constructed with simple hardware interfaces and we show a prototype design of the interfaces, which can be implemented with simple logic gates. Thus the MRN retains the advantages of the ring-based designs without being subjected to scalability limitations. We also develop an efficient deadlock-free routing algorithm for the MRN.
Both analytical analysis and simulation study are used to evaluate the performance of the MRN. We derive some equations to show the performance bounds of the network. We use a detailed flit level simulator to study the performance of the MRN under practical traffic conditions. The synthetic workloads with communication locality are used in the simulation experiments.
Our results show that the MRN performs about seven times better than the hierarchical ring network in a peak throughput. The hardware complexities of the MRN are comparable to those of the hierarchical ring network. The MRN shows well-balanced maximum bandwidth requirements at each ring and thus increases network utilization. Because the bandwidth of the MRN increases proportionally when the system size increases, the MRN shows relatively small increase rate in latency with the system size. Moreover, the MRN can keep each ring size within certain ranges. Thus the MRN shows good scalability up-to a few thousands of processors at comparable costs.'
단방향 점-대-점 링 기반의 연결망들은 고성능 다중처리기를 위한 상호 연결망으로 주목받고 있다. 이와 같은 연결망은 단순한 구조의 하드웨어 인터페이스들을 사용하여 매우 높은 클럭 속도에서 동작시킬 수 있으며, 더 넓은 데이타 대역폭을 제공할 수 있다. 또한 인터페이스의 구조가 단순하므로 링크의 대역폭을 최대한 활용하기가 쉽다. 링 연결은 새로운 노드의 추가와 제거가 쉬운 유연한 구조를 갖고 있다. 그러나 단일 링은 제한된 대역폭 때문에 다수의 노드를 연결하는데 한계가 있다.
다수의 노드를 연결하기위해서는 작은 크기의 링들을 서로 연결한 다중 링 구조가 필요하다. 링들을 서로 연결하기위한 방법으로는 크게 두 가지가 제안되어 왔다. 첫째는 k-ary n-cube 또는 다단게 상호연결망 등의 전통적인 연결망들을 다수의 링으로 분할하고 이들을 다수의 fan-out을 가진 스위치들로 연결하는 방법이다. 다수의 fan-out을 가진 switch를 사용하는 경우 노드들간의 거리를 줄일 수 있으나, 스위치 구조가 복잡해지고 따라서 스위칭 지연이 커질 수 있으므로 병목 현상을 발생시킨다. 또한 이와 같은 형태의 다중 링 연결망은 대다수의 병렬처리 프로그램들이 보여주는 통신 지역화 특성을 이용하기가 어려우며, 연결망 구성의 비용이 많이 든다는 단점이 있다. 둘째로 계층링 구조는 단일 링의 자연스러운 확장으로써 단순한 인터페이스들을 사용하여 구성할 수 있어 단방향 링 연결의 장점을 활용할 수 있는 다중 링 연결망이다. 계층링 구조를 사용한 시스템의 예는 Hector, KSR-1등이 있다. 그러나 계층링 구조는 상위의 계층으로 올라갈수록 트래픽이 집중되므로 확장성에 제한이 있어 주로 중소 규모의 시스템에서 사용되고 있다.
본 논문에서는 대규모 다중처리기 시스템을 위한 새로운 다중 링 연결망으로 다단계 링 연결망을 제안한다. 제안된 다단계 링 연결망은 레지스터 삽입 링을 기반으로 하며 두 단계의 계층으로 구성된다. 전역 링들은 다단계 연결망의 한 형태를 구성하고 있으며 지역 링이라고 불리는 하위 계층의 링들은 프로세서 모듈들을 포함한다. 다단계 링 연결망은 상대적으로 적은 비용으로 상호 연결망을 구축할 수 있으며 또한 병렬 프로그램들의 통신 지역화 특성에 적합한 구조를 갖고 있어 통신 효율을 증대시킬 수 있다. 제안된 다단계 링 연결망은 전역 트래픽을 모든 전역 링들에 효과적으로 분산시킬 수 있으며, 또한 시스템 크기가 증가하면 비례적으로 연결망의 대역폭도 증가한다. 제안된 링 연결망은 간단한 논리 소자들로 구현이 가능한 단순한 구조의 인터페이스들을 사용하여 구축될 수 있으며 본 논문에서는 실제 구현을 위한 인터페이스 디자인의 한 예를 보여준다. 이와 같이 하여 제안된 다단계 링 연결망은 링 기반의 디자인들의 장점을 유지하면서 확장성의 문제를 해결하고 있다. 본 논문에서는 또한 다단계 링 연결망을 위한 효율적인 deadlock-free 라우팅 알고리즘도 개발하였다.
본 논문에서는 연결망 성능 한계를 얻기 위한 분석적 기법의 성능 평가와 실제 트래픽 상황하에서의 성능 평가를 위한 시뮬레이션 연구를 병행하였다. 다단계 링 연결망은 계층링 연결망과 유사한 정도의 연결망 구성 비용으로 약 7배정도의 최대 연결망 산출도를 얻을 수 있다. 또한 전역 트래픽이 전역 링들에 잘 분산되며, 시스템 크기가 증가함에 따라 연결망 대역폭도 비례적으로 증가함으로, 시스템 크기가 증가해도 상대적으로 적은 비율의 전송 지연 증가를 보여준다. 이와 같은 특성은 제안된 다단계 연결망이 대규모 시스템을 위한 상호 연결망으로 적합함을 보여준다.
