[병렬처리] 상호 연결망 구조 - 정적 상호 연결망의 종류

상호연결망(Interconnection Network)의 분류

1. 정적 상호 연결망 (Static interconnection network)

시스템 요소들 간에 직접 연결된 경로를 가지며, 연결 구조가 고정된 연결망

[예] ring, tree, mesh, torus 등

2. 동적 상호 연결망 (Dynamic interconnection network)

시스템 요소들 간의 연결 경로가 실행 시간 (run-time) 동안에 다양하게 변경될 수 있으며, 프로그램 실행중의 통신 패턴과 상황에 따라 필요한 경로를 설정하여 사용할 수 있는 연결망

[예] Omega network, Delta network 등

---

네트워크 성능 파라미터들

• 대역폭 (Bandwidth) : 네트워크를 통하여 전송될 수 있는 최대 데이터 전송률, [Mbytes/sec]
• 네트워크 지연 (Netsork latency) : 메시지 전송에 소요되는 시간
• 기능성 (Functionality) : 데이터 경로 설정, 동기화, 인터럽트 및 메시지 송수신의 지원 능력
• 확장 가능성 (Scalability) : 시스템에 새로운 하드웨어 자원들 (프로세서, 기억장치, I/O 장치 등)을 추가한 경우에 시스템 성능의 선형적 향상 가능성
• H/W 복잡성 : 네트워크 구현에 필요한 하드웨어 모듈 수와 비용

---

정적 상호 연결망

• 노드 (node: processing element) 들 사이를 직접 연결해주는 고정된 경로들로 구성
  • 링크 (link) : 노드 간의 통신 선로로서, 단방향 (undirectional) 혹은 양방향(bidirectinal) 통신 기능을 가진 연결선들의 집합
  • 경로 : 두 노드들 간을 연결해주는 링크들로 구성
  • 네트워크 지름 (Network diameter) : 네트워크 내에서 가장 멀리 떨어져 있는 두 노드들간에 설정되는 경로의 링크수
• 정적 상호연결망의 종류 : 선형배열구조, 원형 구조, 나무 구조, 매쉬 네트워크, 큐브 네트워크, Shuffle-exchange 네트워크, Barrel shifter 네트워크

1. 선형 배열 (Linear array) 구조

N개의 노드들이 N-1 개의 링크들에 의해 차례대로 연결되는 구조

네트워크 지름 = N-1

선형 배열 구조

2. 원형 (Ring) 구조

선형 배열에서 0번 노드와 (N-1)번 노드를 연결한 변형

네트워크 지름
- 단방향 = N-1
- 양방향 = N-2

코달 원형(Chordal ring) 구조

원형 구조의 변형으로서, 각 노드에 연결되는 링크 수를 d개로 증가시킨 구조. (d = dimension)

코달 원형 구조

3. Tree 구조

• Binary tree 구조
• Level 수를 k라고 한다면, 전체 노드의 수 \( N = (2^k -1) \)
• 네트워크 지름 = \( 2(k-1) \)

트리 구조

Fat Tree 구조

상위 레벨로 올라갈수록 노드 간의 링크수를 증가시켜 병목 현상을 완화시킨 트리 구조

[예] Thinking Machine 사의 CM-5, U.C. Berkeley 대학의 실험용 클러스터 컴퓨터인 NOW 시스템에서 사용

FAT TREE 구조

4. 매쉬(Mesh) 구조

각 노드를 주변의 4개의 노드들과 2차원 배열로 연결하는 구조.

Illiac-IV, MPP, DAP, CM-2, Intel Paragon 등에서 사용

MESH 구조

Illiac-IV Mesh

Illiac-MESH의 상호 연결 함수 (단, \( n = \sqrt{N} \) )

• \( M_{+1}(X) = (X+1)modN \)
• \( M_{-1}(X) = (X-1)modN \)
• \( M_{+n}(X) = (X+n)modN \)
• \( M_{-n}(X) = (X-n)modN \)

네트워크 지름 = \( \sqrt{N} - 1 \)

Illiac - IV Mesh

노드들 간에 여러 개의 개의 경로들이 존재함

토러스(Torus) 네트워크

같은 행 및 열에 위치한 노드들이 원형으로 연결되는 매쉬구조

\( k \times k \) 토러스의 경우, 네트워크 지름 = \( k \)

K-ary n-cube 구조의 전체 노드의 수 : \( N = K^n \)

(단, n : 차원)

[예] CRAY T3D supercomputer ; 3차원 토러스 네트워크 사용

5. 큐브(Cube) 네트워크

상호 연결 함수 (Interconnection function)

$$ C_{i}(b_{m-1}b_{m-2} ... b_{i} ... b_{1}b_{0}) = b_{m-1}b_{m-2} ... b{_{i}^{'}} ... b_{1}b_{0} $$

단, \(m = log_2N \), \(N\) : 전체 노드 수, \( 0\leq i < m \)

큐브 네트워크