Torus 및 mesh 네트워크, 즉 k-ary n-cube는 N = kⁿ 개의 노드를 정규적인 n차원 격자 구조에 배치하며, 각 차원에 k개의 노드와 이웃 노드 간의 채널을 가진다. 이 구조는 1차원의 ring부터 (n = 1), binary n-cube (k = 2, hypercube라고도 함)까지 다양한 네트워크를 포함한다.
이 네트워크들이 매력적인 이유는 다음과 같다. 이 정규적인 물리 구조는 패키징 제약에 잘 부합한다. 낮은 차원에서 torus는 균일하게 짧은 wire를 제공하여, repeater 없이 고속 동작이 가능하다. 논리적으로 최소인 경로는 거의 항상 물리적으로도 최소이므로, 통신 노드 간의 물리적 locality를 활용할 수 있다. 예를 들어, 각 노드가 첫 번째 차원의 이웃에게만 전송하는 패턴과 같은 지역적 통신에서는 random traffic보다 지연은 훨씬 낮고, 처리량은 훨씬 높다. 반면 butterfly 네트워크는 이러한 locality를 활용하지 못한다.
Torus는 경로 다양성이 우수하고, permutation traffic에서도 좋은 load balance를 가질 수 있다. 또한 torus나 mesh 네트워크의 모든 채널은 bidirectional이기 때문에, bidirectional signaling을 사용할 수 있어 pin과 wire를 효율적으로 사용할 수 있다.
단점은 hop count가 logarithmic 네트워크보다 크다는 점이다. 이로 인해 최소 지연보다 약간 높은 latency와 더 높은 pin 비용이 발생한다. 그러나 경로 다양성을 확보하기 위해서는 어느 정도 hop 수의 증가가 필요하다.
디자이너는 네트워크의 차원 n을 선택함으로써 torus의 특성을 결정할 수 있다. Section 5.2.1에서 보듯이, throughput은 차원이 증가함에 따라 monotonic하게 증가하지만, 네트워크가 bisection 제한에 도달하면 더 이상 throughput은 증가하지 않는다. Latency는 두 극단에서 모두 높다. 낮은 차원에서는 hop 수(H)가 많아 latency가 증가하고, 높은 차원에서는 serialization latency(Tₛ)가 우세하다. 일반적으로 latency를 최소화하려면 차원은 보통 2~4 정도가 적절하다. latency와 wire 길이를 모두 최소화하려면, 보통 네트워크가 bisection-limited가 되는 가장 작은 차원을 선택한다.
5.1 Torus 네트워크의 구조
n차원, radix-k torus, 또는 k-ary n-cube는 n차원 큐브에 N = kⁿ 개의 노드를 배치한 구조다. direct network이기 때문에 각 노드는 입력 터미널, 출력 터미널, switching node 역할을 동시에 수행한다. 각 노드는 n자리 radix-k 주소 {aₙ₋₁, ..., a₀}를 가지며, 주소의 한 자릿수가 ±1(mod k)만큼 차이나는 노드들과 각 차원당 두 개의 채널(양방향)로 연결된다. 각 노드당 2개의 채널 × 차원 수(n), 총 2nN 개의 채널이 필요하다. Torus는 정규 구조이며(edge-symmetric), channel load balance에 유리하다.
앞서 Figure 3.1(a)에서는 3-ary 2-cube(차원당 3개의 노드를 가지는 2-D torus)를, Figure 3.3에서는 8-ary 1-cube(8-node ring)를 보여주었다.
일반적인 k-ary n-cube는 차원을 하나씩 더하면서 구성할 수 있다 (Figure 5.1 참고).
- Figure 5.1(a): k-ary 1-cube는 단순한 k-node ring
- Figure 5.1(b): k개의 1-cube를 링으로 연결하여 2차원 k-ary 2-cube 생성
- Figure 5.1(c): k개의 (n–1)-cube를 연결하여 k-ary n-cube 생성
Mesh network는 각 차원에서 마지막 주소 ak−1과 처음 주소 a₀ 간 연결이 생략된 torus 네트워크이다. 예시로 Figure 5.2는 4-ary 2-cube(torus)와 4-ary 2-mesh를 비교한다. 두 구조는 노드 degree는 같지만, mesh는 bisection 채널 수가 torus의 절반이다. Mesh는 2D 레이아웃이 자연스럽고 channel 길이가 짧지만, torus의 edge symmetry가 없어져서 traffic pattern에 따라 중앙 채널에 load가 집중될 수 있다. Section 5.3에서는 folded layout을 통해 torus의 최대 채널 길이를 mesh의 2배 수준으로 줄일 수 있음을 다룬다.
Torus는 각 차원에서 한 방향만의 채널(ai → ai+1)로 구성된 unidirectional 구조일 수도 있고, 양방향 채널로 연결된 bidirectional 구조일 수도 있다. Mesh 역시 양쪽 모두 가능하나, unidirectional mesh는 연결성을 유지하기 위해 각 행마다 채널 방향을 바꾸어야 한다. Bidirectional signaling을 동시에 사용하지 않는 한, bidirectional 네트워크는 unidirectional보다 pin 수와 wire bisection이 두 배 필요하다. 그럼에도 hop 수 H가 줄고 경로 다양성이 커지기 때문에, 일반적으로 bidirectional 구조가 선호된다. 특별히 언급이 없는 한, torus나 mesh는 bidirectional로 간주한다.
각 차원은 서로 다른 radix를 가질 수 있다. Figure 5.3은 y 차원에 radix 2, z 차원에 radix 3, x 차원에 radix 4를 갖는 2,3,4-ary 3-mesh를 보여준다. Mixed-radix torus와 mesh는 패키징이나 모듈화 측면에서 실용적인 이유로 종종 사용된다. 하지만 mixed-radix torus는 edge-symmetric하지 않으며, mixed-radix mesh는 단일 radix mesh보다 더 많은 비대칭성을 가진다. 이러한 비대칭성은 load imbalance를 유발하며, uniform traffic일 경우에도 긴 차원에서 채널 load가 짧은 차원보다 커진다. 예를 들어 uniform traffic γₓ의 경우 Figure 5.3에서 x 차원의 load는 γ_z의 두 배가 된다.
5.2 성능
Torus 네트워크의 성능은 throughput, latency, path diversity로 특징지어진다.
5.2.1 Throughput
Two-level packaging 모델에서 throughput은 pin bandwidth나 bisection bandwidth 중 하나에 의해 제한된다. 우선 bisection 한계부터 살펴보자.
Torus와 Mesh의 bisection bandwidth는 다음과 같이 계산된다:
- Torus의 channel bisection:
BC,T = 4kⁿ⁻¹ = 4N / k (식 5.1) - Mesh의 channel bisection:
BC,M = 2kⁿ⁻¹ = 2N / k (식 5.2)
단, 여기서 k는 짝수여야 한다.
Equation 5.1의 최소 bisection은 Figure 5.1(c)를 통해 시각화할 수 있다. k가 짝수일 때, 가장 바깥 차원의 루프에는 짝수 개의 k-ary (n–1)-cube가 존재한다. 최소 bisection은 이 루프를 중앙에서 나누며, kn⁻¹ 양방향 채널 두 세트를 절단하므로 총 4kn⁻¹ 채널이 잘린다. Mesh의 경우 wraparound 채널이 없기 때문에 절단된 채널 수는 절반이 된다.
Torus는 node- 및 edge-symmetric이기 때문에, uniform traffic에 대한 채널 부하는 Equation 5.1을 Equation 3.3에 대입하여 계산할 수 있다.
γ_T,U = N / (2BC) = N / (2 × 4N / k) = k / 8 (식 5.3)
또한, torus의 edge symmetry 덕분에 Equation 5.10의 hop count를 Equation 3.5에 대입해도 같은 결과를 얻는다.
γ_T,U = NH_min / C = N(nk/4) / 2nN = k / 8 (식 5.4, k 짝수)
한편, mesh는 비대칭이기 때문에 torus와 같은 최소 hop 기반 하한에 도달하지 못한다. Mesh의 uniform traffic에 대한 채널 부하는 다음과 같다.
γ_M,U = k / 4 (식 5.5, k 짝수)
이 결과는 직관적으로, mesh가 uniform traffic 하에서 bisection 채널을 포화시킬 수 있다는 점에서 나온다. 전체 트래픽의 절반(N/2 패킷/사이클)이 bisection을 통과하고, 이를 BC_mesh = 2N/k 채널에 고르게 분산하면 평균 부하는 (N/2)/(2N/k) = k/4가 된다. 중앙에서 멀어질수록 부하는 더 감소한다.
Worst-case traffic에서는 전체 트래픽이 bisection을 통과하므로 채널 부하는 두 배가 된다.
- γ_T,W = N / BC = k / 4
- γ_M,W = N / (2BC) = k / 2
주:
- 식 5.3~5.5는 모두 bidirectional 네트워크에 해당한다. Unidirectional torus의 경우는 Exercise 5.4 참고.
- Bidirectional mesh 또는 torus에서는 경로 불균형으로 인해 한쪽 방향의 채널 부하가 4γ_uniform에 근접할 수 있으므로, non-minimal routing이 필요하다.
Pin Bandwidth 제한 고려
각 노드의 degree는 bidirectional cube에서는 차원당 4개 연결을 가진다.
δ_T = δ_M = 4n (식 5.6)
Equation 5.1과 5.6을 Equation 3.14에 대입하면 torus의 최대 채널 너비는 다음과 같다.
w_T ≤ min(W_n / 4n, kW_s / 4N) (식 5.7)
mesh의 경우:
w_M ≤ min(W_n / 4n, kW_s / 2N)
이제 채널 너비와 채널 부하로부터 uniform traffic 하에서의 throughput은 다음과 같이 계산된다.
Φ_ideal,T = f × w_T / γ = 8 / k × min(B_n / 4n, kB_s / 4N)
Φ_ideal,M = f × w_M / γ = 4 / k × min(B_n / 4n, kB_s / 2N)
Torus에서 throughput이 가장 높은 경우는 차원이 충분히 커서 bisection-limited가 되면서도 wire 길이가 임계값을 넘지 않게 유지되는 경우이다. wire 길이를 무시하면 최대 throughput 조건은 다음과 같다.
nk ≤ NB_n / B_s (식 5.8)
Wire 길이와 serialization latency를 최소화하려면, 이 조건을 만족하는 가장 작은 n을 선택한다.
예를 들어, N = 2¹² (4,096) 노드, W_s = 2¹⁴, W_n = 2⁸, f = 1GHz인 torus를 설계해야 한다면, Table 5.1은 다양한 torus 네트워크 옵션을 비교한 것이다.
Table 5.1: 4,096 노드 Torus의 Throughput
| 1 | 4096 | 4096 | 4096 | 64 | 64 | 0.125 |
| 2 | 64 | 128 | 64 | 32 | 32 | 4 |
| 3 | 16 | 48 | 16 | 21 | 16 | 8 |
| 4 | 8 | 32 | 8 | 16 | 8 | 8 |
| 6 | 4 | 24 | 4 | 10 | 4 | 8 |
| 12 | 2 | 24 | 2 | 5 | 2 | 8 |
Table 5.1은 throughput이 차원이 증가할수록 monotonically 증가하다가, n = 3에서 네트워크가 bisection-limited가 되어 더 이상 증가하지 않음을 보여준다. 따라서 n = 3, k = 16인 16-ary 3-cube 토폴로지를 선택하는 것이 가장 적절하며, 낮은 차원으로 인한 latency 및 wire 길이 이점도 있다.
5.2.2 Latency
Torus 네트워크의 latency는 차원에 따라 크게 좌우된다. 낮은 차원에서는 hop count가 latency를 지배하고, 높은 차원에서는 채널 너비가 작아져 serialization latency가 커진다. 일반적으로 latency는 중간 정도의 낮은 차원에서 최소가 된다.
Torus의 serialization latency는 Equation 5.7을 Equation 3.10에 대입하여 다음과 같이 표현된다:
T_s,T = L / b = L / (f × min(W_n / 4n, kW_s / 4N))
= 1/f × max(4nL / W_n, 4NL / kW_s)
Mesh의 경우:
T_s,M = 1/f × max(4nL / W_n, 2NL / kW_s) (식 5.9)
n이 클수록(k는 작아짐) 두 항 모두 커지지만 보통 bisection 항이 지배적이다. n이 작고 k가 크면 T_s는 작지만 hop count가 latency를 지배한다.
Torus에서의 평균 최소 hop count는 모든 노드 쌍 간의 최단 거리 평균으로 계산되며:
H_min,T =
- nk / 4 (k 짝수)
- n(k/4 – 1/4k) (k 홀수) (식 5.10)
Mesh의 경우:
H_min,M =
- nk / 3 (k 짝수)
- n(k/3 – 1/3k) (k 홀수) (식 5.11)
예제로 N = 2¹² (4,096) 노드 torus에서 L = 512 bits, tr = 8 ns, tc = 2 ns로 가정하면, hop당 지연은 10ns이다.
Table 5.2: 4,096 노드 Torus의 Latency
| 1 | 4096 | 64 | 0.125 | 10240 | 8 | 10248 |
| 2 | 64 | 32 | 4 | 320 | 16 | 336 |
| 3 | 16 | 16 | 8 | 120 | 32 | 152 |
| 4 | 8 | 8 | 8 | 80 | 64 | 144 |
| 6 | 4 | 4 | 8 | 60 | 128 | 188 |
| 12 | 2 | 2 | 8 | 60 | 256 | 316 |
위 표는 전체 latency가 n = 4일 때 144ns로 최소임을 보여준다. 그러나 n = 3일 때 latency가 152ns로 거의 동일하고, 더 낮은 차원이 packaging과 wire 길이에 유리하므로 실제 선택은 n = 3일 가능성이 높다.
5.2.3 Path Diversity
Torus 네트워크에는 모든 노드 쌍 사이에 다양한 경로가 존재한다. 트래픽을 이러한 다양한 경로로 분산시키면, 매우 불규칙한 트래픽 패턴에서도 채널 부하를 균형 있게 만들 수 있다. 또한 경로 다양성 덕분에 일부 채널에 문제가 발생하더라도, 다른 경로로 우회하여 네트워크를 빠르게 재구성할 수 있다.
소스 노드 a에서 목적지 노드 b까지 존재하는 경로 수는 얼마인가? 우선 모든 경로가 각 차원에서 동일한 방향으로 진행하며, minimal path만 고려하는 경우를 살펴보자. 차원이 증가할수록 가능한 경로 수는 급격히 증가한다. 1차원에서는 단일 경로만 존재한다. 2차원에서 x축 방향으로 Δx hop, y축 방향으로 Δy hop 차이날 때, 가능한 경로 수는 다음과 같다:
|R_ab| = (Δx + Δy)! / (Δx! × Δy!)
Δx + Δy개의 총 hop 중에서 Δx hop을 어디에 배치할지를 선택하는 경우의 수가 위 공식이다. 3차원의 경우, z 차원에 Δz hop이 추가되면 공식은 다음과 같다:
|R_ab| = (Δx + Δy + Δz)! / (Δx! × Δy! × Δz!)
첫 번째 항은 전체 hop 중에서 Δx를 선택하는 경우의 수, 두 번째 항은 남은 Δy + Δz 중에서 Δy를 선택하는 경우의 수다. 이 둘을 곱하면 전체 unique minimal 경로 수가 된다.
일반적으로 n개의 차원(i = 0 ~ n–1)에서, 각 차원의 hop 수가 Δi일 때, 전체 minimal one-way route 수는 다음과 같다:
|R_ab| = ∏(∑(j=i to n−1) Δj choose Δi) = (∑ Δi)! / ∏ Δi!
각 항은 남은 hop 중에서 해당 차원의 hop 위치를 선택하는 경우의 수다. 차원과 거리 증가에 따라 경로 수는 매우 빠르게 증가한다. 예를 들어 Δx = Δy = Δz = 3인 3D 네트워크에서는 경로 수가 1,680개에 달한다. 일부 라우팅 알고리즘은 non-minimal path도 사용하므로, path diversity는 거의 무한해질 수 있다.
5.3 Mesh와 Torus 네트워크 구축
네트워크를 구축하려면, 추상적인 노드들을 실제 물리 공간의 위치에 매핑해야 하며, 이를 통해 채널 길이 l 등의 물리적 특성을 결정할 수 있다. 사용되는 패키징 기술에 따라, 매핑 대상 공간은 1차원(예: linear backplane의 board), 2차원(예: PCB 상의 chip), 3차원(예: volume 내 arbitrary 위치의 module) 등일 수 있다.
Torus와 mesh 네트워크는 물리 공간에 짧고 균일한 wire로 매핑하기 쉬운 구조다. 가장 단순한 경우는 네트워크 차원 수와 물리적 차원이 같을 때이다. 이 경우, 노드 주소 {a₁, ..., aₙ}는 곧 해당 노드의 n차원 Cartesian 위치이며, pi = ai가 된다. 모든 채널은 인접 노드를 연결하고, 따라서 길이는 1이 된다.
Torus를 동일하게 매핑하면, 각 차원의 끝에서 끝으로 가는 wraparound 채널은 길이가 k가 된다. 이 긴 채널은 latency를 증가시키거나 signaling rate를 늦추는 원인이 될 수 있다. 이를 해결하기 위해 Figure 5.5, 5.6과 같이 torus를 folding하면 된다. Folded torus의 물리 공간 매핑은 다음과 같다:
pi =
- 2ai if ai < k/2
- 2k – 2ai – 1 if ai ≥ k/2
Folded torus는 긴 wraparound 채널을 제거하지만, 다른 채널의 길이는 두 배가 된다. Figure 5.5는 1D torus(ring)를 접는 과정을 보여주며, 0n/2–1 노드를 오름차순으로, n–1n/2 노드를 내림차순으로 interleaving한다. 일반적으로 folded k-ary n-cube는 k개의 folded k-ary (n–1)-cube를 결합하여 구성한다(Figure 5.6 참조).
논리 차원 수(n)가 물리적 차원 수(q)보다 많으면, 여러 논리 차원을 하나의 물리 차원에 매핑해야 한다. 이 경우의 간단한 매핑은 n/q개의 논리 차원을 각 물리 차원에 fold하여 할당하는 것이다:
pi = ∑(j=0 to n/q–1) kʲ × a_(i + jq)
Figure 5.7은 3-ary 2-mesh를 단일 물리 차원에 매핑한 예다. mesh의 세 개 row가 일렬로 배치되고, dimension 0(x)은 길이 1, dimension 1(y)은 길이 3의 채널을 갖는다.
이처럼 q차원 물리 공간에 매핑한 경우, mesh에서 각 차원의 채널 길이는 다음과 같다:
l_i = k^floor(i/q)
folded torus에 대해서도 동일한 매핑이 가능하며, 이때 채널 길이는 두 배가 된다:
l_i = 2k^floor(i/q)
5.4 Express Cubes
Torus 네트워크는 물리 채널이 짧기 때문에, 채널 지연(tc)보다 routing 지연(tr)이 지배적인 경우가 많다. 이로 인해 diameter가 작은 네트워크에 비해 header latency(Th)가 커진다. 차원을 증가시키면 diameter를 줄일 수 있지만(Figure 5.4 참고), 이는 채널 너비를 좁혀서 serialization latency(Ts)를 증가시키는 문제가 발생한다.
Express cube 네트워크는 k-ary n-cube에 여러 개의 긴 express 채널을 추가한 구조이다. 각 차원에서 먼 거리로 이동해야 하는 패킷은 이 express 채널을 이용해 전송되므로, header latency를 channel latency에 가까운 수준까지 줄일 수 있다. express 채널 수는 네트워크의 bisection bandwidth에 맞게 조정 가능하므로, serialization latency를 증가시키지 않고도 header latency를 줄일 수 있다.
Express cube는 각 차원마다 i 노드마다 interchange를 삽입하고, 이를 긴 express 채널로 연결함으로써 구성된다(Figure 5.8 참고). 만약 원래 네트워크에서 dimension j에서 hop 수가 H_j이고, H_j가 i로 나누어 떨어진다면, express 네트워크에서의 hop 수는...
Figure 5.8는 express cube 구조를 보여준다.
- (a): 16-ary n-cube의 한 차원
- (b): 각 i 노드마다 interchange를 삽입하고 이들을 긴 express 채널로 연결한 express cube
- (c): interchange 사이의 express 채널 수를 조절하여 channel bisection을 증가시킬 수 있음
Express cube에서 dimension j에서의 hop 수는 다음과 같이 계산된다:
Hjₑ = (Hj / i) + i
긴 dimension의 경우 첫 항이 지배적이므로, 채널 지연과 라우팅 지연의 균형을 위해 i = tr / tc로 설정하면 된다. 짧은 dimension에서는 두 항이 균형을 이루도록 i = √Hmin (Hmin은 express 채널 없이의 평균 hop 수)로 설정할 수 있다.
Hierarchical express cube는 torus의 locality와 Equation 3.1에 근접하는 로그형 diameter를 함께 제공하는 네트워크다. Figure 5.9는 i = 2, l = 3인 구조를 보여준다. 이 구조는 다음 방식으로 재귀적으로 구성된다:
- i 노드마다 level-0 interchange 삽입
- level-0 interchange 중 i개마다 하나씩 level-1 interchange로 승격
- 이 과정을 l번 반복
- 각 level j의 interchange는 i^j 간격으로 존재하고, level 0~j까지의 이웃 interchange와 연결됨
만약 Hj가 i^l로 나누어 떨어지면, hierarchical express cube에서의 hop 수는 다음과 같다:
Hjₕ = (Hj / i^l) + (i–1)l + 1
i = 2는 local node 지연을 최소화하고, l = logi(tr / tc)는 라우팅 지연과 채널 지연의 균형을 이룬다.
이러한 구조는 전체 latency를 다음 두 지연의 합의 근사값으로 줄여준다:
- 두 노드 간 최소 거리 이동에 필요한 최소 channel 지연
- 목적지를 선택하기 위한 라우팅 결정에 필요한 로그 지연
Express 채널 수를 조절하면 pin 제한과 bisection bandwidth 제한을 모두 활용할 수 있다.
그러나 express cube는 실제 시스템에서는 거의 사용되지 않았다. 그 이유는 대부분의 실용적인 네트워크는 radix가 작기 때문에 interchange 추가의 복잡성을 정당화하기 어렵기 때문이다. 또한 기술이 발전하면서 tr과 임계 wire 길이 lc가 감소하여 긴 채널을 사용할 필요성도 줄어들었다.
5.5 사례 연구: MIT J-Machine
MIT J-Machine은 torus 및 mesh 네트워크가 3차원 공간에 자연스럽게 매핑될 수 있음을 보여주는 사례다. 이 시스템은 1991년 MIT와 Intel의 협업으로 개발된 메시지 기반 병렬 컴퓨터로, 각 노드에는 message-driven processor(MDP) 칩과 세 개의 외부 DRAM이 탑재되었다. 당시에 이 시스템은 병렬 컴퓨터 중에서 가장 높은 bisection bandwidth와 가장 낮은 latency를 가진 네트워크를 탑재해 주목받았다.
J-Machine의 네트워크 인터페이스는 프로세서 레지스터에서 직접 메시지를 단일 명령어로 전송할 수 있게 설계되었으며, 이는 당시로서는 매우 혁신적이었다.
Figure 5.10은 J-Machine 두 대를 보여준다. 앞쪽 기계는 외피가 제거된 상태이며, 상단에는 최대 1,024개의 노드가 8 × 8 × 16 3D mesh로 연결되어 있다. 해당 시스템은 8개의 8 × 8 64-node 보드가 절반만 채워진 형태이다. 보드 하단에는 그래픽, 디스크 제어, LAN 인터페이스용 I/O 카드가 있으며, 맨 아래에는 80개의 디스크가 포함된 디스크 어레이가 배치되어 있다.
J-Machine의 노드들은 3차원 mesh로 연결되었다. 이 구조는 매우 밀도 높은 시스템 구현이 가능하게 했다. 각 보드는 64개의 노드가 8 × 8으로 연결되어 있으며, 각 노드는 2×3인치 크기였다. 인접 보드는 elastomeric 커넥터로 수직 연결되었고, 최대 16개의 보드가 하나의 섀시로 조립되어 1,024-node, 8 × 8 × 16 구조를 형성했다. 리본 케이블로 여러 섀시를 가로로 연결하여 더 큰 시스템으로 확장 가능했지만, 실제로는 1,024노드를 초과하는 시스템은 제작되지 않았다.
네트워크 채널은 총 15개의 신호선(9 data + 6 control)으로 구성되었고, 32 MHz로 동작했다. 이는 16 MHz 프로세서보다 두 배 빠른 속도였다. 따라서 채널 당 유효 payload bandwidth는 288 Mbit/s였다. 한 쌍의 노드 간 통신은 하나의 물리 채널을 공유하며, 각 노드가 flit 단위로 채널 사용을 조율했다. 채널은 다음 세 방식으로 구현되었다:
- 같은 보드 내 64개 노드 간 연결: PCB
- 인접 보드 간 수직 연결: elastomeric 커넥터
- 인접 보드 간 수평 연결: 리본 케이블
라우터는 MDP 칩 내에 통합되었으며, dimension-order routing(8.4.2절)과 wormhole flow control(13.2절)을 사용했다. 라우터는 X, Y, Z 축별로 깔끔하게 분할 설계되었으며, 한 hop당 지연은 32 MHz 기준 2사이클(=16 MHz 프로세서 1사이클)이었다.
지연 계산 예: 4-word 메시지를 uniform traffic 하에 전송할 경우, serialization latency는 16 사이클(31.25 ns × 16), 평균 hop 수는 32/3, hop당 2 사이클이므로 전체 지연은 약 37 사이클(1.16 μs), 즉 18.5 프로세서 사이클이 된다.
Throughput 계산 예:
- 가장 긴 dimension인 k = 16 방향에서, Equation 5.2 적용 시 bisection에는 128개 채널이 있지만, 물리 채널은 양방향 공유되므로 실제는 절반인 64개
- 전체 1,024 노드 중 절반인 512개가 bisection을 넘는 트래픽을 보내므로, 채널당 부하는 γ = 512/64 = 8
- 따라서 노드당 throughput은 Φ = b/γ = 288/8 = 36 Mbit/s
Figure 5.11은 MDP 칩의 구조를 보여준다. 이 칩은 1.2 μm CMOS 공정으로 구현되었으며, 32-bit RISC 프로세서, 3차원 dimension-order router, 네트워크 인터페이스, DRAM 인터페이스, 그리고 18KB 온칩 메모리를 포함한다. 라우터는 RAM 바로 아래에 있으며 X, Y, Z로 분리되어 있다.
Figure 5.12는 512-node J-Machine에서 processor clock이 12.5 MHz일 때, 제공되는 트래픽에 따른 측정된 latency를 나타낸 그래프다. 측정된 zero-load latency는 23 processor cycles로, 이론 계산값인 18.5 cycles보다 4.5 cycles 더 크다. 이는 네트워크 입출력 인터페이스에서 고정된 4 cycle의 지연과 반올림 오차 때문이다. bisection 트래픽 포화점에서의 실제 측정 throughput은 6 Gbit/s로, 이론상 14.4 Gbit/s(64 채널 × 9비트 × 25 MHz)의 42% 수준이다. 이는 두 가지 주요 요인 때문이다:
- 메시지가 4-word이지만, 이 중 2-word는 header로 사용되므로 50%의 header overhead가 발생한다.
- wormhole flow control은 채널 이용률을 100%까지 끌어올릴 수 없다.
5.6 참고 문헌 노트
Mesh와 torus는 오랫동안 인기 있는 네트워크 토폴로지였으며, 초기 병렬 컴퓨터인 Solomon과 Illiac-IV에서도 사용되었다. Binary n-cube 또는 hypercube 네트워크는 Sullivan과 Bashkow에 의해 대중화되었으며, Caltech의 Cosmic Cube에도 사용되었다. 이후 Intel iPSC 시리즈, NCUBE 시스템 등 상업용 병렬 컴퓨터도 이 구조를 채택했다.
1985년, Dally는 wire bisection과 pinout 등 물리적 제약을 기준으로 네트워크 토폴로지를 비교하는 개념을 도입하고, 낮은 차원의 torus 구조가 현실적 제약 하에서 유리하다는 점을 보여주었다. 이후 low-dimensional torus와 mesh는 병렬 컴퓨터의 표준이 되었으며, 최근에는 torus 구조가 인터넷 라우터 설계에도 적용되고 있다. Dally는 torus의 비대칭적인 라우팅 latency 문제를 해결하기 위해 express cube를 제안하기도 했다. 하지만 실용적인 네트워크는 asymptotic 특성이 중요해질 만큼 크지 않기 때문에 express cube는 실제로 널리 사용되지 않았다.
여러 연구에서는 torus의 end-around connection을 twist하거나, 차원 내 연결 순서를 바꾸는 다양한 변형을 제안했다. 일부는 diameter를 소폭 줄이는 효과가 있다. 이런 구조들을 실험해보는 과제는 Exercise 5.6에 있다.
5.7 연습 문제
5.1 Butterfly와 torus 토폴로지 비교
노드 수가 1,024개이고 노드당 대역폭이 300 Gbit/s, bisection 대역폭이 4 Tbit/s인 butterfly와 torus 네트워크를 비교하라. 각 네트워크에서 bisection 대역폭이 포화되도록 최소한의 k, n 조합을 선택하라 (단, kn = 1,024). 패킷 길이가 L = 1,280일 때 serialization latency는? 평균 hop 수 Hmin은? tr = 12 ns일 때 wire latency를 무시하고 zero-load latency는?
5.2 4,096-node torus의 trade-off
kn = 4,096인 torus에 대해 k와 n 조합별 이상적인 throughput과 평균 zero-load latency를 계산하라. 조건: 노드당 120 signal 핀, 시스템의 bisection 폭은 1,500 신호, f = 2.5 GHz, 패킷 길이 L = 512비트, hop당 지연 tr = 20 ns, wire 지연 무시(Tw = 0).
5.3 3단계 패키징 계층의 torus 구성
256-node torus를 3단계 계층 구조로 패키징해야 한다. 조건: 노드당 384 signal 핀, 보드 당 1,200 신호, 백플레인 중간단계에 6,000 signal 가능. 최대 bandwidth가 나오도록 k와 n을 선택하고, 최소 zero-load latency 조합을 택하라. 보드 수를 최소화하며 nodes, boards, backplane 구조를 설명하라.
5.4 Unidirectional torus의 채널 부하
Uniform traffic에서 unidirectional torus의 평균 채널 부하를 계산하라. 이 부하가 bidirectional torus에 비해 얼마나 큰가? 증가 원인은?
5.5 Non-minimal 경로 수
x, y 방향 최소 hop 수가 Δx, Δy일 때, 2-D torus에서 minimal보다 최대 1 hop 또는 2 hop 긴 경로 수는? (단, k는 홀수)
5.6 Doubly twisted torus 비교
Figure 5.13에 제시된 doubly-twisted torus의 평균 hop 수 Hmin을 4-ary 2-cube와 비교하라. twist가 hop 수에 어떤 영향을 미치는가?
5.7 Torus의 평균 wire 길이
2-D 평면에 배치된 k-ary 6-mesh에서 메시지가 이동하는 평균 wire 길이를 계산하라. 노드는 2D 격자에 10 cm 간격으로 배치된다. 3차원에 배치될 경우에는 어떤가? (세 번째 차원 간격도 10 cm, k는 짝수)
5.8 Cube connected cycles (CCC) 토폴로지
고차원 torus는 낮은 hop 수를 제공하지만, degree가 높아져 채널 폭이 좁아지고 serialization latency가 증가한다. CCC는 이를 해결한다. n차 CCC는 2-ary n-cube에서 각 노드를 n개의 노드로 이루어진 cycle로 대체하여 구성된다 (Figure 5.14 참조).
- n차 CCC의 노드 수와 평균 Hmin은? (근사치 허용)
- 64-node 시스템을 CCC와 k-ary n-cube로 구성할 경우, node당 120핀, 2.5 Gbit/s일 때 zero-load latency를 비교하라.
조건: L = 1,024 bits, tr = 20 ns, wire latency 무시
'System-on-Chip Design > NoC' 카테고리의 다른 글
| Slicing and Dicing (1) | 2025.06.02 |
|---|---|
| Non-Blocking Network (2) | 2025.06.02 |
| Butterfly Networks (1) | 2025.06.02 |
| Topology Basics (4) | 2025.06.01 |
| A Simple Interconnection Network (2) | 2025.06.01 |