다단계 상호 접속 네트워크
Multistage interconnection networksMIN(Multistage Interconnect Network)은 보통 네트워크 한쪽 끝의 처리 요소(PE)와 다른 쪽 끝의 메모리 요소(ME)로 구성되며, 전환 요소(SE)로 연결된다. 개폐 요소 자체는 보통 단계별로 서로 연결되어 있기 때문에 명칭이 붙는다.
MIN은 일반적으로 패킷 교환 네트워크 위에서 구현될 수 있지만 낮은 지연 시간 상호 접속(기존 패킷 교환 네트워크와는 반대로)으로서 고성능 또는 병렬 컴퓨팅에 사용된다. 네트워크는 일반적으로 라우팅 용도로 사용되지만, 정렬, 완벽한 셔플 네트워크와 같이 주기적 이동, 비트론 정렬과 같은 용도의 실제 프로세서에 대한 공동 프로세서로도 사용될 수 있다.
배경
인터커넥션 네트워크는 노드가 단일 프로세서 또는 프로세서 그룹이 될 수 있는 노드를 다른 노드에 연결하는 데 사용된다.
상호연결 네트워크는 그 위상에 기초하여 분류할 수 있다. 토폴로지는 한 노드가 다른 노드에 연결되는 패턴이다.
위상에는 두 가지 주요 유형이 있다: 정적과 동적이다.
정적 인터커넥트 네트워크는 유선 연결되어 있어 구성을 변경할 수 없다. 일반적인 정적 상호 연결은 주로 느슨하게 커플링된 노드로 구성된 작은 네트워크에 사용된다. 정규 구조는 노드가 특정 형태로 배열되고 그 모양이 네트워크 전체에 걸쳐 유지된다는 것을 의미한다.
정적 정기적 상호연결의 몇 가지 예는 다음과 같다.[1][2]
- 완전히 연결된 네트워크 메쉬 네트워크에서는 여러 개의 노드가 서로 연결되어 있다. 네트워크의 각 노드는 네트워크의 다른 모든 노드에 연결된다. 이 배열은 노드들 간의 적절한 데이터 통신을 가능하게 한다. 그러나 노드 연결 수가 증가하여 통신 오버헤드가 많다.
- 공유 버스이 네트워크 토폴로지는 버스를 통해 서로 노드 연결을 포함한다. 모든 노드는 버스를 이용하여 다른 모든 노드와 통신한다. 버스 유틸리티는 데이터가 잘못된 노드로 전송되지 않도록 보장한다. 그러나 버스 교통은 시스템에 영향을 줄 수 있는 중요한 매개 변수다.
- 울리다이것은 노드를 서로 연결하는 가장 간단한 방법 중 하나이다. 그 노드들은 서로 연결되어 고리를 형성한다. 노드가 일부 다른 노드와 통신하려면 인접 노드로 메시지를 전송해야 한다. 따라서 데이터 메시지는 대상에 도달하기 전에 일련의 다른 노드를 통과한다. 이것은 시스템의 지연 시간을 증가시키는 것을 포함한다.
- 나무이 위상에는 트리를 형성하기 위한 노드의 연결이 포함된다. 노드는 클러스터를 형성하도록 연결되고 클러스터는 트리를 형성하기 위해 차례대로 연결된다. 이 방법론은 네트워크의 복잡성을 증가시킨다.
- 하이퍼큐브 이 위상은 큐브를 형성하는 노드의 연결로 구성된다. 노드는 다른 큐브의 노드에도 연결된다.
- 나비이것은 노드의 가장 복잡한 연결 중 하나이다. 그림에서 알 수 있듯이, 연결되고 배열되는 노드가 있다. 그것들은 행렬의 형태로 배열되어 있다.
다이내믹 인터커넥트 네트워크에서, 노드는 일련의 간단한 스위칭 요소를 통해 상호 연결된다.[3] 이 상호연결은 한 노드에서 다른 노드로의 경로를 변경할 수 있도록 라우팅 알고리즘을 사용하여 변경할 수 있다. 동적 상호연결은 다음과 같이 분류할 수 있다.
- IMT-2000 3GPP-단일 인터커넥트 네트워크
- 멀티에이지 인터커넥트 네트워크
- 크로스바 스위치 연결부
크로스바 스위치 연결부
크로스바 스위치에는 한 프로세서에서 다른 프로세서로 전용 경로가 있다. 따라서 입력과 m 출력이 n개라면 크로스바를 실현하기 위해 n*m 스위치가 필요할 것이다.
출력 수가 증가하면 스위치 수는 n배수로 증가한다. 대형 네트워크에서는 이것이 문제가 될 것이다.
이 계획의 대안은 단계적 전환이다.
IMT2000 3GPP - 단일단계 상호연결망
1단계 인터커넥트 네트워크에서 입력 노드는 단일 단계의 스위치를 통해 출력에 연결된다.
그림에는 셔플 교환을 사용하는 8*8 싱글 스테이지 스위치가 나와 있다.
보다시피, 단일 셔플에서 모든 입력이 모든 출력에 도달할 수 있는 것은 아니다. 모든 입력이 모든 출력에 연결되려면 복수의 슈플이 필요하다.
멀티에이지 인터커넥트 네트워크
다단계 상호 연결 네트워크는 다중 단일 단계 스위치를 계단식으로 형성한다. 그러면 스위치는 자체 라우팅 알고리즘을 사용하거나 중앙집중식 라우터에 의해 제어되어 완전히 상호 연결된 네트워크를 형성할 수 있다.
멀티에이지 인터커넥트 네트워크는 다음 세 가지 유형으로 분류할 수 있다.[4]
- 비차단: 비차단 네트워크는 네트워크를 통해 이미 설정된 연결에 관계없이 유휴 입력을 모든 유휴 출력에 연결할 수 있다. 크로스바(Crossbar)는 이러한 유형의 네트워크의 한 예다.
- 다시 정렬 가능한 비차단: 이러한 유형의 네트워크는 기존 연결을 재배열하여 입력과 출력 사이의 가능한 모든 연결을 설정할 수 있다.
- 차단: 이러한 유형의 네트워크는 입력과 출력 사이의 모든 가능한 연결을 실현할 수 없다. 이것은 다른 자유 출력에 대한 자유 입력 간의 연결이 네트워크의 기존 연결에 의해 차단되기 때문이다.
비차단 네트워크를 가장 많이 실현하는 데 필요한 전환 요소 수, 그 다음으로 비차단 가능 요소 수. 차단 네트워크는 최소한의 전환 요소를 사용한다.
예
다단계 상호접속망의 여러 유형이 존재한다.
오메가 네트워크
오메가 네트워크는 2*2 전환 요소의 여러 단계로 구성된다. 각 입력은 출력에 대한 전용 연결을 가지고 있다. N*N 오메가 네트워크는 각 스테이지의 로그(N) 수와 각 스테이지의 N/2 개수의 스위칭 요소를 가지고 있어 스테이지 간 완벽한 셔플을 제공한다. 그러므로 네트워크는 0(N log(N))의 복잡성을 가진다. 각 스위칭 요소는 자체 스위칭 알고리즘을 사용할 수 있다. 8*8 오메가 네트워크를 고려해 보십시오. 입력에서 출력까지 8! = 40320 일대일 매핑이 있다. 2^12 = 4096의 총 순열에는 12개의 전환 요소가 있다. 따라서 차단망이다.
클로징 네트워크
클로징 네트워크는 3단계를 사용하여 N 입력에서 N 출력으로 전환한다. 첫 번째 단계에는 r= N/n 크로스바 스위치가 있으며 각 스위치의 크기는 n*m이다. 2단계에서는 r*r 크기의 m 스위치가 있고, 마지막으로 m*n 크기의 r 스위치가 있는 1단계의 거울이 된다. 폐쇄 네트워크는 m >= 2n-1일 경우 완전히 차단되지 않는다. 오메가 네트워크보다 더 많은 연결 수는 크로스바 네트워크의 연결 수보다 훨씬 적다.
베네시 네트워크
베네시 네트워크는 n = m = 2를 초기화하여 클로징 네트워크에서 파생된 재정렬 비차단 네트워크다. (2log(N) - 1) 스테이지가 있으며, 각 스테이지에는 N/2 2*2 크로스바 스위치가 포함되어 있다. 8*8 베네시 네트워크는 5단계 전환 요소를 가지며, 각 단계에는 4단계 전환 요소가 있다. 센터 3단계는 2개의 4*4개의 벤 네트워크를 가지고 있다. 4*4 Benesh 네트워크는 모든 입력을 모든 출력에 반복적으로 연결할 수 있다.
참조
- ^ Nielsen, Frank (2016). "3. Topology of Interconnection Networks". Introduction to HPC with MPI for Data Science. Springer. pp. 63–97. ISBN 978-3-319-21903-5.
- ^ Solihin, Yan (2009). Fundamentals of Parallel Computer Architecture. USA: OmniPress. ISBN 978-0-9841630-0-7.
- ^ Blake, J. T.; Trivedi, K. S. (1989-11-01). "Multistage interconnection network reliability". IEEE Transactions on Computers. 38 (11): 1600–1604. doi:10.1109/12.42134. ISSN 0018-9340.
- ^ "Multistage interconnection networks" (PDF).
