Zeah Engineering Factory

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

주:

1. 식 5.3~5.5는 모두 bidirectional 네트워크에 해당한다. Unidirectional torus의 경우는 Exercise 5.4 참고.
2. 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

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

위 표는 전체 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인 구조를 보여준다. 이 구조는 다음 방식으로 재귀적으로 구성된다:

1. i 노드마다 level-0 interchange 삽입
2. level-0 interchange 중 i개마다 하나씩 level-1 interchange로 승격
3. 이 과정을 l번 반복
4. 각 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를 다음 두 지연의 합의 근사값으로 줄여준다:

1. 두 노드 간 최소 거리 이동에 필요한 최소 channel 지연
2. 목적지를 선택하기 위한 라우팅 결정에 필요한 로그 지연

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% 수준이다. 이는 두 가지 주요 요인 때문이다:

1. 메시지가 4-word이지만, 이 중 2-word는 header로 사용되므로 50%의 header overhead가 발생한다.
2. 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 무시

수많은 토폴로지가 제안되어 왔지만, 실제로 구현된 대부분의 네트워크는 두 가지 주요 계열인 butterfly (k-ary n-fly) 또는 torus (k-ary n-cube)에서 파생된 토폴로지를 사용한다. 이 장에서는 butterfly network 계열의 정의와 특성을 살펴본다. torus network는 5장에서 다룬다.

butterfly network는 대표적인 간접 네트워크다. 이 토폴로지는 스위치의 차수가 δ = 2k일 때, N개의 노드를 가진 네트워크 중에서 최소 지름(diameter)을 갖는다. 이때 높이 H는 logk N + 1이다. 이러한 최적의 지름은 매우 매력적인 특성이지만, butterfly network에는 두 가지 주요 단점이 있다. 첫째, 기본 butterfly network는 경로 다양성이 없다. 즉, 각 source node에서 각 destination node까지 가는 경로가 정확히 하나뿐이다. 이 문제는 butterfly에 stage를 추가함으로써 해결할 수 있다. 이러한 추가 stage는 경로 다양성을 높여주며, 네트워크의 지름은 여전히 최적값의 두 배 이내로 유지된다.

둘째, butterfly network는 시스템 지름의 절반 이상을 가로질러야 하는 긴 배선을 필요로 하기 때문에 구현이 어렵다. 배선의 길이가 일정 임계 길이를 초과하면 그 속도가 거리의 제곱에 반비례하여 급격히 느려지므로, 이러한 긴 배선은 중간 크기 이상의 interconnection network에서 butterfly 구조를 덜 매력적으로 만든다. 그럼에도 불구하고, butterfly network는 로그형 지름과 간단한 라우팅 방식 덕분에 많은 응용 분야에서 널리 사용되고 있으며, 그 변형 구조들 또한 매우 인기가 많다.

4.1 Butterfly Network의 구조

우리는 이미 여러 k-ary n-fly 예제를 살펴본 바 있다. 예를 들어, 그림 2.2는 radix가 4인 스위치 세 단계를 가진 4-ary 3-fly이며, 그림 3.1(b)는 2-ary 3-fly, 그림 3.5는 2-ary 4-fly를 나타낸다. 이 외에도 다양한 “fly” 구조가 가능하며, k는 반드시 2의 거듭제곱일 필요는 없다.

k-ary n-fly network는 총 kn개의 source terminal node, n단계에 걸쳐 각 단계마다 kn−1개의 k×k crossbar switch node, 그리고 kn개의 destination terminal node로 구성된다. butterfly network는 일반적으로 왼쪽에 source node를, 오른쪽에 destination node를 배치한다. butterfly 내부의 모든 채널은 별도의 언급이 없는 한 단방향이며 왼쪽에서 오른쪽으로 흐른다. 대부분의 butterfly 구현에서는 source node와 destination node가 물리적으로 동일한 위치에 존재하지만, 논리적으로는 분리되어 그려진다. 우리는 이 source-destination node 쌍을 하나의 terminal node로 간주하여, 총 N = kn개의 terminal이 있다고 본다.

4.2 동형 Butterfly (Isomorphic Butterflies)

터미널 노드와 각 스위치 노드에서 나가는 채널에는 n자리 radix-k 숫자 {dn−1, dn−2, ..., d0}로 레이블을 붙인다. 앞의 n − 1자리 {dn−1, dn−2, ..., d1}는 스위치를 식별하고, 마지막 자리 d0는 해당 스위치 내 터미널을 식별한다. 각 stage 사이의 배선은 이 터미널 주소를 순열(permutation)로 재배열한다. stage i−1과 i 사이의 배선은 dn−i와 d0를 교환한다. 그림 4.1은 노드 및 일부 채널의 labeling을 보여준다. 각 stage에서 노드나 채널을 구분하기 위해 stage 번호를 마침표로 구분하여 덧붙인다. 예를 들어, stage 1의 노드 {1,0,1} = 5는 1.5로 레이블된다.

k-ary n-fly에서 라우팅은 이 순열의 관점에서 쉽게 이해할 수 있다. 스위치 stage i는 터미널 주소의 현재 최하위 자리인 d0를 임의의 값으로 설정한다. stage i−1과 i 사이의 배선은 이 값을 dn−i 위치에 놓는다. 따라서 첫 번째 stage는 dn−1을, 두 번째는 dn−2를 설정하고, 마지막 stage는 이미 올바른 위치에 있는 d0를 설정하므로 추가 배선이 필요 없다.

수년간 shuffle-exchange, butterfly, data manipulator, flip 등 다양한 multistage 네트워크가 제안되었지만, 이들은 모두 몇몇 스위치의 번호만 다를 뿐 동일한 네트워크이다. 즉, 서로 동형(isomorphic)이다.

네트워크 K는 노드와 채널 집합으로 정의되며, K = (N*, C)이다. 두 네트워크 K1 = (N1, C1), K2 = (N2, C2)가 있을 때, 정점에 대한 순열 π가 존재하여, {u, v} ∈ C1 이면 {π(u), π(v)} ∈ C2인 경우 이 둘은 동형이다. 그림 4.2는 이러한 예로, 동일한 2-ary 3-fly 네트워크를 shuffle-exchange와 butterfly 형태로 그린 것이다. shuffle-exchange에서는 각 stage 간의 배선이 동일하며 shuffle 순열을 수행한다. 이 순열은 stage i의 출력 터미널 {d2, d1, d0}를 다음 stage 입력 터미널 {d1, d0, d2}로 연결한다.

그림 4.2의 두 네트워크는 switch node 11과 12의 위치만 바꾸면 간단하게 동형이 된다. 라우팅 시 입력 터미널 {a2, a1, a0}에서 출력 터미널 {b2, b1, b0}로 가는 포트 순서를 비교해 보면, stage 1의 스위치 주소만 {b2, a1}(butterfly)과 {a1, b2}(shuffle exchange)로 다를 뿐 나머지는 동일하다.

4.3 성능 및 패키징 비용 (Performance and Packaging Cost)

Chapter 3에서 살펴본 바와 같이, 토폴로지는 throughput, latency, path diversity로 특성이 정의된다. 이 절에서는 butterfly의 throughput과 latency를 다루고, path diversity는 4.4절에서 설명한다. 모든 성능 비교는 3.4절의 two-level packaging model을 사용한다.

k-ary n-fly network는 kn개의 입력 터미널, kn개의 출력 터미널, n×kn−1개의 스위치 노드를 가진다. 각 스위치 노드의 차수는 다음과 같다:

  δfly = 2k

채널 bisection은 N이 짝수일 때 다음과 같다:

  BC,fly = N / 2

butterfly는 edge-symmetric network는 아니지만, 각 stage 간 채널은 대칭적이므로, 3.3.1절에서 정의한 최대 채널 부하 상한이 정확하게 적용된다 (즉, uniform traffic 하에서 모든 채널이 동일하게 부하된다). 따라서 채널 부하는 평균 hop 수만으로 정의할 수 있다.

butterfly에서 어떤 packet도 source와 destination에 관계없이 동일한 hop 수를 가진다. 즉, stage 수 + 1:

  Hmin,fly = n + 1

이 hop 수와 식 3.5를 이용하면 채널 부하는 다음과 같다:

  γU,fly = NHmin / C = kn(n+1) / kn(n+1) = 1

uniform traffic에서는 전체 트래픽의 절반이 bisection을 통과하므로 각 bisection 채널 부하는 γfly,uniform = 1이다. 반대로, node i가 node N−i−1로 보내는 reverse traffic에서는 모든 트래픽이 bisection을 통과하므로 부하는 γfly,rev = 2가 된다. 이는 butterfly에만 해당되는 것이 아니라 다른 네트워크도 마찬가지다. 그러나 path diversity가 부족한 butterfly는 전체 트래픽의 큰 비율이 단일 채널에 집중될 수 있어 γ가 최대 √N까지 증가할 수 있다.

two-level packaging model에서 butterfly의 채널 폭은 다음과 같이 구한다 (식 4.1, 4.2를 식 3.14에 대입):

  wfly ≤ min(Wn / 2k, 2Ws / N)

uniform traffic에서 γ = 1이므로, 이상적인 throughput은 다음과 같다:

  φideal,fly = f × wfly / γ = min(Bn / 2k, 2Bs / N)

여기서 Bn, Bs는 각각 node 및 bisection bandwidth이다.

대부분의 butterfly에서는 우선 throughput을 최대화하고, 그다음 latency를 최소화하는 것이 목표이다. 이를 위해 network가 bisection bandwidth에 의해 제한되는 가장 큰 k를 선택한다:

  k = ⌊(N × Bn) / (4 × Bs)⌋

이때 k는 가장 작은 diameter를 제공하고, H를 최소화하며 channel bandwidth를 극대화한다. 이보다 작은 k는 throughput을 개선하지 못하며 hop 수 증가로 인해 latency만 증가시킨다.

butterfly의 latency 구성 요소인 Ts, Tr, Tw는 모두 k와 n의 선택에 영향을 받는다. Serialization latency는 Ts = L / b이며, b는 식 4.3에 의해 결정된다. Tr = tr × Hmin = tr(n+1)이다. Tw는 butterfly의 배선 구조에 따라 달라진다. 모든 butterfly는 많은 긴 채널을 필요로 하며, stage 1의 절반 채널은 반대편으로, stage 2는 다른 사분면으로 이동한다. 이러한 채널은 종종 임계 길이를 초과하므로 full speed 작동을 위해 repeater를 삽입해야 한다.

이러한 성능을 예로 보여주기 위해 다음을 고려하자: N = 2¹², L = 512비트, Ws = 2¹⁴, Wn = 28, f = 1 GHz, tr = 10ns, Tw는 무시.

식 4.4에 의해:

  k = (2¹²×28)/(4×2¹⁴) = 16

따라서 최적 성능을 위한 구성은 16-ary 3-fly이다. δ = 2k = 32이고, w = Wn / δ = 8비트. hop 수는 H = 4, 이상 throughput은 8 Gbps, 평균 latency는 104 ns이다. Table 4.2는 다양한 k와 n에 따른 성능을 요약한다.

4.4 Path Diversity와 Extra Stages

k-ary n-fly 네트워크는 경로 다양성(path diversity)이 없다. 즉, 모든 x, y ∈ N에 대해 |Rxy| = 1이다. 이로 인해 트래픽 패턴이 비균일할 경우 채널 간 부하 불균형으로 인해 throughput이 크게 저하될 수 있다.

이러한 부하 불균형은 네트워크에 stage를 추가하여 완화할 수 있다. stage를 추가하면 문제가 어떻게 줄어드는지를 이해하기 위해, 먼저 트래픽이 병목 채널에 집중되는 방식을 살펴본다.

k = 2, n은 짝수, m = n/2라고 가정하자. Section 4.1에서 설명한 주소 형식을 사용하여, 모든 x ∈ Z(2^m)에 대해 {xm, ..., x2, am, ..., a1, x1}에서 {bm, ..., b1, ym, ..., y0}로 패킷이 전송된다고 하자. 여기서 y = π(x)는 Z(2^m)의 임의의 순열이다. 간편한 표기를 위해, m자리 주소는 하나의 문자로 나타낸다. 예를 들어 x = {xm, ..., x1}.

라우팅의 첫 번째 stage에서, node x로부터의 패킷은 switch {xm, ..., x2, a}를 통과한다. 다음 stage에서는 {bm, xm−1, ..., x2, a}, ... m번째 stage에서는 {bm, ..., b2, a}, m+1번째 stage에서는 {b, am−1, ..., a1}을 통과한다. 이때 m번째 stage의 switch는 x에 영향을 받지 않으므로, 이 트래픽 패턴의 모든 2^m = √N개의 패킷은 동일한 switch를 통과하게 된다. 마찬가지로 (m+1)번째 stage의 switch도 동일하다. 이 둘 사이에는 단 하나의 채널만 존재하므로 해당 채널에는 √N만큼의 부하가 집중된다.

이 트래픽 집중 현상은 butterfly 네트워크를 2차원으로 그리면 쉽게 시각화할 수 있다. Figure 4.3은 k-ary n-fly를 y축 switching plane (2^m개)과 z축 switching plane (2^m개)으로 구성된 구조로 나타낸 것이다. 처음 m개의 stage는 상위 m비트만을 처리하여 패킷을 y축 방향으로 이동시키고, 나머지 m개의 stage는 하위 비트를 처리하여 z축 방향으로 이동시킨다.

예를 들어 첫 번째 y축 네트워크에 연결된 입력 포트들이 모두 첫 번째 z축 네트워크로 전송하고자 할 때, 이 모든 2^m개의 패킷은 두 네트워크를 연결하는 단일 채널을 통과해야 하며, 이는 앞서 언급한 트래픽 집중과 정확히 일치한다.

이제 네트워크 앞쪽에 m개의 stage를 추가하자. 이들은 네트워크 뒤쪽의 마지막 m개의 stage와 동일하게 배선되어 있으며, switch 주소의 하위 m비트를 설정한다. 이러한 추가 stage는 2^m의 경로 다양성을 제공하며, |Rxy| = 2^m이다. 예를 들어 {s, t}에서 {u, v}로 패킷을 보낼 때, 새로운 m개의 stage는 {s, t}를 {s, i}로 라우팅하며, 이때 i는 Z(2^m)의 임의 값이다. 적절한 라우팅 전략을 사용하면 i는 균등하게 선택되며, 트래픽은 stage m−1의 intermediate channel {s, i}로 균등하게 분산된다. 이후 원래 네트워크의 전반부(n/2 stage)는 {s, i}에서 {u, i}로, 후반부는 {u, i}에서 {u, v}로 라우팅된다. 이제 앞서 문제였던 트래픽 패턴이 단일 채널에 집중되지 않고 {xm, ..., x2, am, i}, {b, i} 등 여러 채널로 분산된다.

Figure 4.4는 2-ary 3-fly에 추가 stage를 한 개 넣어 경로 다양성을 2로 만든 모습을 보여준다. 수정 전에는 bit-reversal 트래픽(0→0, 4→1 등)이 stage 2 출력의 절반 링크에 집중된다. 그러나 입력 stage를 추가하면 이 문제는 사라지고, bit-reversal 트래픽에서도 채널 부하 γ = 1을 유지한다.

하지만 이것이 완전한 해결책은 아니다. 두 가지 문제가 남아 있다. 첫째, 네트워크의 채널 bisection BC,fly가 N보다 작기 때문에 모든 노드가 bisection을 가로지르는 트래픽 (예: node i → N−i−1)을 감당할 수 없다. 둘째, n > 3인 큰 네트워크에서는 트래픽 집중 문제가 여전히 존재하며, 집중률은 2^(n/2)가 아닌 2^(n/4) 수준으로 감소할 뿐이다.

이 집중 문제를 더 명확히 보기 위해, switch 주소를 r = n/4 비트 문자열로 표현하자 (n = 4r이라 가정). 예를 들어 {xr, ..., x2, a, x1, s, t}에서 {b, y, u, v}로의 경로를 고려하자. y = π(x)는 Z(2^r)의 순열이다. 추가된 입력 stage 이후 패킷은 {xr, ..., x2, a, x1, i, j} 채널에 도달하고, 중간 stage를 거쳐 {b, y, i, j}에 도달한다. 이 경우에도 하위 주소 비트가 고정되어 있으므로 이전과 같은 집중이 재현된다. 다만 이번에는 총 부하가 2^r = 2^(n/4)로 줄어든다. 이는 중간 stage가 각각 2^m 포트를 가지는 2^m개의 별도 네트워크로 나뉘며, 전체 네트워크가 아닌 이 중간 네트워크에 부하가 집중된다는 의미이다.

Figure 4.5는 m개의 extra stage를 가진 k-ary n-fly를 2D로 표현한 그림이다. extra stage는 2^m개의 z축 네트워크를 형성하며, 각 네트워크는 stage마다 2^(m−1)개의 switch를 가진다. 이 네트워크는 트래픽을 z축 방향으로 균등하게 분산시켜 y→z 축 전환 지점에서의 혼잡을 방지한다.

그러나 y축 내부에서의 혼잡은 여전히 발생할 수 있다. 예를 들어 각 y축 네트워크를 m/2 stage짜리 두 개의 네트워크로 나누고, 이 둘의 경계에서 트래픽을 집중시킬 수 있다.

이러한 load imbalance 문제는 전체 n개의 stage를 복제함으로써 해결할 수 있다. 그 결과로 생성되는 2n-stage 네트워크는 두 개의 n-stage butterfly를 백투백으로 연결한 것으로, Beneš (베네시) 네트워크라고 한다. 이 네트워크는 채널 bisection이 N이므로 bit-reversal 트래픽 같은 패턴을 처리할 수 있고, 모든 노드 쌍 사이에 N개의 대체 경로를 제공하여 트래픽을 완전히 분산시킨다. 실제로 Beneš 네트워크는 non-blocking이며, 이에 대해서는 6.4절에서 다룬다.

4.5 사례 연구: BBN Butterfly

Bolt, Beranek, and Neumann(BBN) Advanced Computer Systems는 k-ary n-fly 토폴로지를 사용한 공유 메모리 병렬 프로세서를 개발하였다. 그 첫 번째 제품은 1981년에 출시된 BBN Butterfly였다. 이 시스템은 최대 256개의 처리 노드를 연결했으며, 각 노드는 8 MHz Motorola 68000 마이크로프로세서와 512 Kbyte 메모리를 탑재하였다. 이후 1987년에는 Butterfly GP-1000에서 68020 프로세서로 업그레이드되었고, 노드당 메모리도 4 Mbyte로 증가했다. 1989년에는 TC-2000에서 Motorola 88100 RISC 프로세서, 88200 캐시 및 메모리 관리 칩이 사용되었으며, 노드당 최대 16 Mbyte 메모리를 탑재할 수 있었다.

Butterfly의 각 프로세서는 interconnection network를 통해 다른 모든 노드의 메모리에 읽기/쓰기 접근이 가능했다. 이는 cache-coherent 시스템이 아니었다. 초기 Butterfly와 GP-1000에는 캐시가 없었고, TC-2000은 local data에 대해서만 캐싱을 허용했다. Monarch (23.4절 참조)는 TC-2000의 후속으로 설계되었으나 완성되지는 못했다.

원격 메모리 접근은 Figure 4.6에 나타난 것처럼 64-node 구성에서 4-ary n-fly 구조와 추가 stage 하나를 사용하는 네트워크를 통해 수행되었다. 각 채널은 4비트 폭이며, 68000 프로세서의 클럭 속도인 8 MHz로 작동하여 채널 대역폭 b는 32 Mbps였다. 네트워크는 log₄(64) = 3이 아닌 4개의 4×4 스위치 stage로 구성되었는데, 이는 추가 stage를 포함했기 때문이다. 이 추가 stage는 path diversity를 제공하여 adversarial 트래픽에 대한 throughput을 개선하였다. radix-4 스위치를 사용할 경우, 추가 stage는 source-destination 사이에 edge-disjoint 경로 4개를 제공한다. 패킷 전송 시, 네트워크 인터페이스는 이 4개의 경로 중 하나를 무작위로 선택하였다. 또한, 4비트 마스크를 통해 문제가 발생한 경로를 선택적으로 비활성화할 수 있었다.

이 4×4 스위치는 각 채널이 4비트인 형태로 discrete TTL logic을 이용하여 12인치 높이의 단일 PC 보드에서 구현되었으며, 채널 인터페이스는 emitter-coupled logic을 사용하였다.

[그림 4.6 설명]
1981년의 BBN Butterfly는 processor와 memory를 연결하기 위해 하나의 extra stage를 포함한 4-ary n-fly 네트워크를 사용하였다. 각 채널은 32 Mbit/s의 대역폭을 가지며, contention을 해결하기 위해 메시지를 drop하는 방식의 스위치를 사용하였다. 그림은 64개의 노드를 연결하는 4개의 4×4 스위치 stage로 구성된 4-ary 3+1-fly를 보여준다.

계속: 4.5 사례 연구 - BBN Butterfly

채널 인터페이스에는 ECL(emitter-coupled logic) line driver와 receiver가 사용되었다. 스위치 카드와 프로세서/메모리 카드는 19인치 랙(rack)에 임의의 순서로 삽입되었고, 네트워크 배선은 카드 전면의 리본 케이블로 구성되었다.

스위치를 통과하는 지연은 125ns 클럭 3개이며, 그 중 하나는 출력 포트를 지정하는 routing nybble을 소비하는 데 사용된다. 따라서 그림 4.6의 4-stage 네트워크는 zero-load 조건에서 end-to-end latency가 125ns × 12 = 1.5μs이다. uniform traffic에서는 라우팅 overhead를 무시하면 노드당 throughput은 32 Mbit/s였다. 그러나 adversarial traffic pattern에서는 throughput이 매우 낮아질 수 있다.

이 네트워크는 Chapter 2에서 소개한 간단한 네트워크와 유사한 dropping flow control을 사용하였다. 여러 패킷이 동일한 출력 포트를 요청하면 하나의 패킷만이 포트를 할당받고 나머지는 drop된다. drop된 패킷은 짧은 시간 후 재전송되며, 매번 목적지까지의 4개의 경로 중 하나를 무작위로 선택한다. 이를 통해 동일한 패킷 집합 간의 충돌이 반복될 가능성을 줄인다.

4.6 참고문헌 주석

butterfly 토폴로지는 다양한 형태로 수년간 사용되어 왔다. 초기 예로는 Stone의 shuffle-exchange, Feng의 data manipulator, Lawrie의 omega, Batcher의 flip, Pease의 indirect binary cube topology가 있다. Wu와 Feng은 이들 네트워크가 모두 butterfly와 동형(isomorphic)임을 보여주었다. butterfly 및 유사 토폴로지에 대한 비교는 Kruskal과 Snir에 의해 제시되었다. 또한, NYU Ultracomputer, 본 절에서 소개한 BBN Butterfly, NEC의 Cenju-4 컴퓨터와 같이 butterfly를 기반으로 한 상용 및 학술 시스템도 존재한다.

4.7 연습문제

4.1 butterfly와 shuffle-exchange 네트워크의 동형성
radix-2 shuffle-exchange 네트워크는 n = log₂ N개의 switch stage로 구성되며, 각 stage는 perfect shuffle로 연결된다. perfect shuffle은 stage i의 출력 터미널 {aₙ₋₁, ..., a₀}를 stage i+1의 입력 터미널 {aₙ₋₂, ..., a₀, aₙ₋₁}에 연결한다. 동일한 노드를 가지는 radix-2 shuffle exchange 네트워크와 2-ary n-fly가 동형임을 보여라 (Figure 4.2 참조).

4.2 bit-reversal 하의 throughput
bit-reversal 트래픽 패턴을 라우팅할 때 4-ary 2-fly는 전체 용량의 몇 %를 달성하는가?

4.3 butterfly 토폴로지 패키징
Wₙ = 128, Wₛ = 1024인 패키징 기술을 이용해 2¹⁰개의 노드를 연결해야 한다. 네트워크의 throughput을 최대로 하고, 그다음 latency를 최소화하는 butterfly 토폴로지를 선택하라. throughput과 해당 latency는 얼마인가?
(L = 512 bits, f = 1 GHz, tr = 10 ns, wire latency 무시)

4.4 adversarial traffic에서의 과부하 채널
Section 4.4에서 permutation 트래픽은 특정 채널에 √N의 부하를 발생시킨다고 설명하였다. Section 4.1의 주소 표기법을 이용하여 이 과부하된 채널의 주소를 구하라.

4.5 동일한 extra stage 추가
Figure 4.4의 네트워크에서 첫 번째 stage와 동일하게 배선된 두 번째 redundant stage를 추가한다고 가정하자. path diversity는 증가하는가? 최대 채널 부하는 감소하는가?

4.6 BBN Butterfly에서의 최악 트래픽
Figure 4.6의 BBN Butterfly 네트워크에서 γmax를 최대화하는 최악의 트래픽 패턴을 설명하라. 일반적으로 stage 수가 홀수인 butterfly에서의 최악 throughput은 얼마인가?

4.7 홀수 radix butterfly의 패키징
3-ary 2-fly 네트워크에서 최소 bisection 채널 수 BC는 얼마인가? 이 경우 N = 9이므로 bisection에 의해 분리된 두 노드 집합의 크기는 1만큼 차이가 난다. 이 bisection이 네트워크의 효율적인 패키징을 의미하는가? 아니라면, 유사한 크기로 나누는 다른 cut 또는 cut 집합을 제안하라.

4.8 mixed radix butterfly
12-node butterfly를 먼저 2개의 switch stage, 다음으로 3개의 switch stage를 사용하여 설계하라. 각 stage 내 switch는 동일한 radix를 가지되, stage 간 radix는 달라도 된다. 어떤 switch 포트도 비워두지 말 것 (예: 16-node butterfly에 4개의 unconnected terminal이 있으면 안 됨). 이 두 토폴로지는 12의 소인수 분해와 어떻게 관련되는가?

4.9 고장 허용 butterfly (Wounded Butterfly)
2-ary n-fly 네트워크에서 한 stage에 faulty switch가 하나 있다고 하자. 네트워크는 이 switch를 제거하고 해당 경로로의 라우팅을 금지한다. extra stage가 없다면 일부 노드 쌍 간 경로가 없어져 네트워크는 단절된다. x개의 extra stage가 있을 때 (0 ≤ x ≤ n), 하나의 switch 고장 후에도 네트워크가 연결 상태를 유지할 확률은 얼마인가? x = 1일 때, 두 개의 switch 고장 후에도 연결이 유지될 확률은?

4.10 butterfly 배치 시의 배선 길이
2-ary butterfly 네트워크를 평면에 배치할 때, 메시지가 통과하는 평균 배선 길이를 계산하라. 모든 노드는 2D grid에 정렬되어 있으며, 노드 간 간격은 10cm라고 가정한다. 예: 첫 번째 stage는 첫 번째 열에 위치하며 수직 공간은 10 × 2ⁿ⁻¹ cm가 필요하다. 다음 stage는 수평으로 10cm 떨어진 다음 열에 위치. 거리 측정은 각 switch 노드의 중심 간 거리로 하며, terminal 노드와의 연결은 무시한다. Figure 4.3과 같은 2D 배치와 비교하여, 얼마나 배선이 짧아지는가? (단, n은 짝수로 가정)

네트워크 topology는 interconnection network에서 channel과 node의 정적인 배치를 의미한다. 이는 packet이 이동하는 경로에 해당한다. 네트워크 설계의 첫 단계는 topology를 선택하는 것으로, routing 전략과 flow-control 방식이 topology에 크게 의존하기 때문이다. 경로를 선택하고 그 경로를 따라 이동을 계획하기 위해선 먼저 지도(topology)가 필요하다. Chapter 2에서 예시로 보여준 것처럼, topology는 네트워크의 종류(예: butterfly network)뿐 아니라, switch의 radix, stage의 수, 각 channel의 너비와 bit-rate 같은 세부 사항도 정의한다.

좋은 topology를 선택하는 일은 네트워크 요구사항을 사용 가능한 패키징 기술에 맞추는 작업이다. 한편으로는 포트 수, 포트당 bandwidth 및 duty factor가 설계를 이끌고, 다른 한편으로는 칩과 보드당 사용 가능한 핀 수, 배선 밀도, 가능한 signaling rate, 케이블 길이 요구사항이 제약 조건이 된다.

Topology는 비용과 성능에 기반하여 선택된다. 비용은 네트워크를 구현하기 위해 필요한 칩의 수와 복잡도, 이 칩들 간 보드 또는 케이블을 통한 interconnection의 밀도 및 길이에 의해 결정된다. 성능은 bandwidth와 latency 두 요소로 구성되며, 이 둘은 topology 외의 요소들 — 예: flow control, routing 전략, traffic 패턴 — 에 의해서도 영향을 받는다. 따라서 topology만을 평가하기 위해, bisection bandwidth, channel load, path delay 등의 지표를 사용하여 topology가 성능에 미치는 영향을 측정한다.

네트워크 설계자들이 흔히 저지르는 실수 중 하나는, 네트워크의 topology를 당면 문제의 데이터 통신 패턴에 맞추려는 것이다. 표면적으로는 좋은 생각처럼 보인다. 예를 들어, divide-and-conquer 알고리즘을 수행하며 tree-structured communication pattern을 사용하는 머신이라면, tree network가 최적의 선택처럼 보일 수 있다. 하지만 대부분의 경우, 이는 적절하지 않다. 여러 이유로, 특정 목적의 topology는 문제가 발생하기 쉽다. 예를 들어 문제의 동적 부하 불균형이나 문제 크기와 머신 크기 간 불일치로 인해 부하가 잘 분산되지 않을 수 있다. 데이터를 재배치해 부하를 조정하면, 네트워크와 문제 간의 매칭이 무너지게 된다. 또한 특정 문제에 특화된 네트워크는 사용 가능한 패키징 기술과 잘 맞지 않아 긴 배선이나 높은 node degree를 요구하는 경우가 많다. 마지막으로 이런 네트워크는 유연하지 않다. 알고리즘이 바뀌어 다른 통신 패턴을 요구할 경우, 네트워크는 쉽게 변경될 수 없다. 대부분의 경우, 특정 문제에 최적화된 네트워크보다, 일반적인 용도의 좋은 네트워크를 사용하는 것이 훨씬 낫다.

Figure 3.1은 세 가지 예시 topology를 보여준다. (a)는 2차원 torus 구조로 각 차원에 3개의 노드를 가지는 3-ary 2-cube, (b)는 radix-2 butterfly 네트워크로 3-stage 구조인 2-ary 3-fly, (c)는 irregular network다. cube 구조에서는 각 node가 terminal이자 switching node다. 반면 butterfly 구조는 terminal node와 switch node가 구분되며, 가운데에는 switch-only node가 위치한다. 불규칙한 구조도 별도로 제시되어 있다.

3.1 용어 정의

3.1.1 Channels와 Nodes

interconnection network의 topology는 node 집합 N과, 이를 연결하는 channel 집합 C로 정의된다. 메시지는 terminal node 집합 N (단, N ⊆ N)에서 생성되고 종료된다. 모든 node가 terminal인 네트워크에서는 단순히 node 집합을 N으로 표현한다.

각 channel c = (x, y) ∈ C는 source node x와 destination node y를 연결하며, x, y ∈ N이다. channel c의 source는 sc, destination은 dc로 표현한다. Figure 3.1의 각 edge는 양방향 channel 쌍을 의미한다. 이러한 topology 정의는 directed graph와 동일하며, 많은 용어가 graph theory에서 차용되었다. 편의상 node 수는 |N| 대신 N*, channel 수도 |C| 대신 C로 표현한다.

channel c = (x, y)는 다음으로 특징 지어진다:

• 너비 wc 또는 wxy: 병렬 신호의 개수
• 주파수 fc 또는 fxy: 각 신호에서 bit가 전송되는 속도
• 지연 tc 또는 txy: bit가 x에서 y로 도달하는 시간

대부분의 경우, 지연은 물리적 길이 lc와 전파 속도 v의 곱으로 표현된다: lc = vtc. bandwidth는 bc = wc * fc 로 계산된다. 모든 channel의 bandwidth가 동일한 경우, b로 통일해 표현한다.

각 switch node x는 다음과 같은 channel 집합을 가진다:

• 입력 채널 집합: CIx = {c ∈ C | dc = x}
• 출력 채널 집합: COx = {c ∈ C | sc = x}
• 전체 degree: δx = |Cx| = |CIx| + |COx|

모든 node가 같은 degree를 가진다면, δ로 간단히 표현한다.

3.1.2 Direct Network와 Indirect Network

네트워크 node는 packet을 생성하고 소모하는 terminal node, packet을 forwarding하는 switch node, 또는 둘 모두일 수 있다.

• Direct network: 예를 들어 Figure 3.1(a)의 torus에서는 모든 node가 terminal이자 switch이다.
• Indirect network: Figure 3.1(b)의 butterfly에서는 각 node가 terminal(원형) 또는 switch(사각형) 중 하나만 수행한다.

direct network는 terminal node 간에 직접 packet을 전달하고, indirect network는 전용 switch node를 통해 간접적으로 전달한다. Figure 3.1(c)처럼 direct도 indirect도 아닌 network도 존재한다. 모든 direct network는 각 node를 terminal과 switch로 분리하여 indirect 형태로 그릴 수 있다 (Figure 3.2 참조). 이 경우, direct와 indirect 간 구분은 학문적인 의미에 가깝다.

direct network의 장점 중 하나는, terminal의 자원(예: 컴퓨터)을 switch에서도 사용할 수 있다는 점이다. 초기 네트워크에서는 switch 기능이 terminal CPU에서 실행되는 소프트웨어로 구현되었으며, buffer도 terminal의 메모리를 사용했다. 하지만 소프트웨어 switching은 매우 느리고 terminal 자원을 많이 소모하므로, 현재는 거의 사용되지 않는다.

3.1.3 Cuts와 Bisections

 1. Cut (컷)

Cut은 네트워크를 두 부분으로 나누는 것입니다.

• 네트워크의 모든 노드를 두 그룹으로 나눈다고 생각해보세요:
  예를 들어 N1과 N2.
• 그리고 두 그룹(N1과 N2)을 연결하는 channel들을 모읍니다.
• 이 연결선들의 집합을 Cut이라고 부릅니다.

 즉, Cut = 한 쪽에서 다른 쪽으로 가는 channel들의 집합입니다.

 예시

• C와 D 사이에 연결된 선이 있다고 하면, C는 N1에, D는 N2에 있으니 이 선은 Cut에 해당합니다.
• Cut의 개수는 이렇게 두 그룹을 나눴을 때 두 그룹을 연결하는 channel의 수입니다.

2. Bisection (바이섹션)

Bisection은 특별한 종류의 Cut입니다.

• 네트워크의 모든 노드를 거의 반으로 나누는 Cut입니다.
• 그리고 그 반으로 나눈 구역 사이의 channel 수(또는 bandwidth)가 가장 적게 되도록 나눕니다.

즉, Bisection은 네트워크를 거의 반반으로 나누면서, 그 사이를 연결하는 channel 수가 가장 적은 Cut입니다.

왜 중요할까?

• 병목 구간(bottleneck)을 찾을 수 있기 때문입니다.
• 네트워크를 반으로 잘랐을 때, 이 중간 연결(channel) 수가 적으면, 많은 트래픽이 이 작은 연결을 통과해야 하므로 성능이 떨어질 수 있습니다.

3.1.4 Paths

3.1.5 대칭성 (Symmetry)

Topology의 대칭성은 부하 분산과 라우팅에 중요한 역할을 하며, 후속 절들에서 자세히 설명된다. 네트워크가 vertex-symmetric하다는 것은, 임의의 node a를 다른 node b로 mapping하는 automorphism이 존재한다는 뜻이다. 즉, 모든 node의 관점에서 네트워크 구조가 동일하게 보인다는 의미다. 이는 routing을 단순화할 수 있는데, 모든 node가 동일한 네트워크 지도를 공유하므로 동일한 방식으로 목적지로 라우팅할 수 있다.

Edge-symmetric 네트워크는 임의의 channel a를 다른 channel b로 mapping하는 automorphism이 존재한다. Edge symmetry는 모든 channel이 동일하게 취급되므로 channel 간 부하 분산을 개선하는 데 도움이 된다.

🔷 1. Vertex-symmetric (정점 대칭)

"모든 노드가 같은 역할을 하도록 생겼다."

• 네트워크의 어느 노드에서 보더라도 구조가 똑같이 생겼다는 뜻이에요.
• 즉, 한 노드에서 연결된 방향, 수, 거리 등이 다른 노드와 똑같이 생겼다면 vertex-symmetric입니다.
• 쉽게 말해, 노드 입장에서 네트워크가 전부 똑같이 보인다는 뜻이에요.

📌 예:

• 링 (Ring) topology
• Mesh나 Torus도 경우에 따라 vertex-symmetric이 될 수 있어요.

🔷 2. Edge-symmetric (간선 대칭)

"모든 채널이 동일한 역할을 한다."

• **모든 channel (link)**이 구조적으로 같은 위치, 역할을 한다는 뜻이에요.
• 즉, 채널마다 부하가 균등하게 나뉘어질 수 있는 구조라는 의미예요.
• 네트워크 입장에서 어느 channel이든 특별 대우가 없는, "채널 평등"인 셈이에요.

📌 예:

• Torus
• 링
• 어떤 경우엔 vertex-symmetric이 아니어도 edge-symmetric일 수 있어요.

🔷 핵심 차이점 요약

🔷 비유로 쉽게 이해하기

• vertex-symmetric: 모든 사람이 같은 위치, 같은 복장, 같은 키를 가진 군대 → "사람 입장에서 전부 똑같다"
• edge-symmetric: 그 사람들이 가진 총이 전부 똑같고 같은 위치에서 조준함 → "총(채널) 입장에서 전부 똑같다"

3.2 Traffic Patterns

Topology 성능 지표를 도입하기 전에, interconnection network에서 메시지의 공간 분포를 이해하는 것이 유용하다. 이러한 메시지 분포는 traffic matrix λ로 나타내며, λs,d는 node s에서 node d로 전송되는 traffic의 비율을 나타낸다.

Table 3.1은 interconnection network 평가에 사용되는 일반적인 정적 traffic pattern을 나열한다. 이들 중 일부는 실제 애플리케이션에서 나타나는 통신 패턴에 기반하고 있다. 예를 들어, matrix transpose 또는 corner-turn 연산은 transpose pattern을 유도하고, FFT나 sorting 응용은 shuffle pattern, 유체역학 시뮬레이션은 neighbor pattern을 나타낸다.

• Random traffic: source가 모든 destination에 동일 확률로 전송. 가장 일반적으로 사용됨. traffic을 균등하게 분산시켜 부하를 고르게 하므로, load balance가 좋지 않은 topology나 routing 알고리즘도 이 패턴 하에서는 성능이 좋아 보일 수 있다.
• Permutation traffic: 각 source가 하나의 destination에만 전송하며, d = π(s)로 표현된다. traffic matrix λ는 permutation matrix가 되며, 각 행과 열에 단 하나의 값만 존재한다. 특정 source-destination 쌍에 load가 집중되므로, topology와 routing 알고리즘의 부하 분산 능력을 테스트하는 데 적합하다.

Bit permutation은 source 주소의 bit들을 permutation 및 보완하여 destination 주소를 생성하는 방식이다. 예를 들어 source 주소가 {s3, s2, s1, s0}라면:

• bit-reverse: {s0, s1, s2, s3}
• bit-complement: {¬s3, ¬s2, ¬s1, ¬s0}
• shuffle: {s2, s1, s0, s3}

Digit permutation은 radix-k 표현의 digit 단위로 주소를 변형하는 permutation이다. 이 방식은 terminal 주소가 k진수의 n-digit 표현인 경우 (예: k-ary n-cube, k-ary n-fly)에서 사용된다. 예시:

• Tornado pattern: torus topology를 가장 불리하게 만드는 pattern
• Neighbor pattern: locality를 얼마나 잘 활용하는지 측정

3.3 성능 (Performance)

Topology는 비용과 성능을 기준으로 선택된다. 이 절에서는 성능을 결정짓는 세 가지 주요 지표 — throughput, latency, path diversity — 를 설명한다. 3.4절에서는 이 성능 지표들을 네트워크 구현 비용과 연결하여 다시 다룬다.

3.3.1 Throughput과 최대 channel 부하

네트워크가 얼마나 많은 데이터를 처리할 수 있는지, 그리고 가장 부하가 많이 걸리는 채널이 어디인지를 분석하는 내용이다.

Throughput은 네트워크가 input port당 받아들일 수 있는 데이터 속도 (bit/sec)를 말한다. throughput은 routing 및 flow control에 크게 의존하며 topology만으로 결정되지 않는다. 하지만 routing이 부하를 완벽히 분산하고, flow control이 병목 channel에서 idle cycle이 전혀 없다고 가정하면, topology의 이론적 최대 throughput을 계산할 수 있다.

이 절에서는 모든 channel bandwidth가 동일하게 b일 때의 throughput 및 부하 공식만을 다룬다 (Ex.3.5에서는 이 제한을 해제한다).

네트워크의 어떤 channel이 포화(saturated) 상태에 도달할 때가 최대 throughput이다. 포화된 channel이 없다면, 더 많은 traffic을 수용할 수 있으므로 최대 throughput이 아님. 따라서 throughput을 계산하려면 channel load를 고려해야 한다.

channel c의 load γc는, 해당 channel이 감당해야 하는 bandwidth가 input port bandwidth에 비해 얼마나 되는지를 나타내며, 다음과 같이 정의된다. 이는 모든 input이 1 unit의 traffic을 주입할 때 channel c를 통해 지나야 하는 traffic 양으로 해석할 수 있다. 단위가 없고, 일반적으로는 uniform traffic 하에서 계산한다.

​

✅ 핵심 목적

“네트워크가 얼마나 빠르게 데이터를 흘릴 수 있을까?”
→ 이걸 **throughput (처리량)**이라고 하고,
→ **그걸 방해하는 가장 붐비는 통로(channel)**를 bottleneck이라 해요.

🔷 1. Throughput이란?

• Throughput은 각 input port가 초당 얼마나 많은 데이터를 네트워크로 보낼 수 있는지를 의미해요.
• 예를 들어, 모든 노드가 1 Gbit/s로 데이터를 보낸다면, 네트워크는 그 속도를 견뎌야 해요.

🔷 2. 왜 "최대 channel 부하"가 중요할까?

• 네트워크는 여러 channel (통로)로 이루어져 있어요.
• 그런데 일부 channel은 다른 것보다 더 많은 traffic을 받게 돼요.
• 이때 가장 바쁜 channel의 부하를 γmax라고 해요.

📌 이 γmax가 너무 크면 → 그 channel이 병목(bottleneck)이 돼요.
→ 그럼 전체 네트워크 throughput이 그만큼 줄어들어요.

🔷 3. 이상적인 Throughput 계산 공식

책에서 소개하는 공식:

λideal=bγmaxλ_{ideal} = \frac{b}{γ_{max}}λideal​=γmax​b​

• b: 각 channel의 bandwidth (예: 1 Gbit/s)
• γmax: 가장 많이 사용되는 channel의 부하 비율 (무차원값, 단위 없음)

🧠 이 공식이 말하는 것:

"최대 부하 channel이 완전히 포화될 때까지 input에서 데이터를 넣을 수 있다."

🔷 4. 예를 들어 볼게요

• 8-node ring이 있고,
• 각 channel은 1 Gbit/s,
• 모든 노드가 동일하게 데이터를 주고받을 때,
• 가장 많이 사용되는 channel이 1 Gbit/s까지 도달하는 순간이 throughput의 한계예요.

🔷 5. γmax는 어떻게 구하나?

책에서는 몇 가지 방식으로 γmax를 추정하거나 계산하는 방법도 알려줘요:

1. bisection-based 하한:γB=N2BCγ_B = \frac{N}{2BC}γB​=2BCN​(N = 노드 수, BC = channel bisection 수)
2. 전체 채널에 균등 부하 분산하는 상한 공식 (Equation 3.6):γc=1N∑x,y∑P∈Rxy1∣Rxy∣(c가 포함된 경로에 대해서만)γ_{c} = \frac{1}{N} \sum_{x,y} \sum_{P ∈ R_{xy}} \frac{1}{|R_{xy}|} \quad \text{(c가 포함된 경로에 대해서만)}γc​=N1​x,y∑​P∈Rxy​∑​∣Rxy​∣1​(c가 포함된 경로에 대해서만)

✅ 정리하자면

💡 요약 한 줄

3.3.1에서는 "네트워크에서 가장 바쁜 통로가 얼마나 빠르게 꽉 차느냐"를 기준으로 전체 데이터 처리 능력(throughput)을 계산하는 방법을 설명하고 있어요.

3.3.2 지연 (Latency)

이 세 항목은 topology와 물리적 패키징(mapping)에 의해 결정된다:

• Hmin: topology만의 특성
• Dmin: topology 및 패키징 둘 다의 영향을 받음
• b: topology의 node degree와 패키징 제한에 따라 결정

Figure 3.4는 node x에서 z까지 2-hop 경로를 따라 packet이 전달되는 과정을 Gantt 차트로 보여준다:

1. node x에 도착
2. tr 만큼 지연 후 channel x→y로 전송
3. txy 시간 동안 전파
4. y에서 다시 tr 지연 후 y→z로 전송
5. tyz 전파 시간
6. 마지막으로 tail이 도착할 때까지 L/b 시간 직렬화 지연

이 과정을 통해 Equation 3.11의 세 지연 요소가 시각적으로 설명된다.

Figure 3.4의 Gantt 차트에서 latency의 구성 요소가 요약된다. 단일 해치 부분은 routing 지연, 연한 회색 부분은 link latency, 이중 해치 부분은 serialization latency에 해당한다.

예를 들어, 64-node 네트워크에서 평균 hop 수 Havg가 4이고, channel 너비가 16비트인 경우를 생각해 보자. 각 channel c는 1GHz에서 동작하며, 해당 channel을 통과하는 데 tc = 5ns가 걸린다. 단일 router의 지연이 tr = 8ns (2ns clock × 4)일 때, 전체 routing 지연은 8 × 4 = 32ns (16 clocks)이다. wire 지연은 5ns씩 4개로 총 Tw = 20ns (10 clocks)다. packet 길이가 L = 64바이트이고, channel bandwidth가 2GB/s이면 serialization 지연은 64 / 2 = 32ns (16 clocks)이다. 따라서 전체 T₀는 32 + 20 + 32 = 84ns가 된다.

3.3.3 경로 다양성 (Path Diversity)

대부분의 노드 쌍에 대해 minimal path가 여러 개인 네트워크, 즉 |Rxy| > 1인 경우는 |Rxy| = 1인 단일 경로 네트워크보다 더 견고하다. 이러한 path diversity는 채널 간 부하를 분산하고, 고장난 채널이나 노드에도 견딜 수 있도록 하여 네트워크의 신뢰성을 높여준다.

지금까지는 각 노드가 다른 모든 노드로 균등하게 메시지를 보내는 random traffic에 대해 주로 다루었다. 많은 네트워크에서 random traffic은 이상적인 부하이며, 이는 채널 부하를 균등하게 분산시켜주기 때문이다. 그러나 permutation traffic처럼 각 노드가 정확히 하나의 다른 노드로만 메시지를 보낼 때는 상황이 더 까다롭다. 이 경우 path diversity가 부족하면 일부 permutation은 특정 채널에 traffic을 집중시켜 throughput을 심각하게 떨어뜨릴 수 있다.

예를 들어, bit-rotation traffic을 두 가지 topology에서 전송한다고 가정하자:

• 2-ary 4-fly (unit bandwidth)
• 4-ary 2-cube (half-unit bandwidth)

두 네트워크 모두 random traffic에서는 γmax = 1이다. bit-rotation (BR) traffic에서 주소가 {b3, b2, b1, b0}인 노드는 {b2, b1, b0, b3}로 packet을 보낸다. 이는 다음과 같은 shuffle permutation과 같다:

{0, 2, 4, 6, 8, 10, 12, 14, 1, 3, 5, 7, 9, 11, 13, 15}

즉, node 0은 자기 자신에게, node 1은 node 2로, 이런 식이다. Figure 3.5에서처럼, 이 permutation이 2-ary 4-fly에 적용되면 모든 traffic이 네트워크 중앙의 몇 개 채널에 집중된다. 예를 들어:

• node 0, 1, 8, 9 → channel (10, 20)
• node 2, 3, 10, 11 → channel (11, 23)
• node 4, 5, 12, 13 → channel (16, 24)
• node 6, 7, 14, 15 → channel (17, 27)

이 경우 γmax,BR = 4가 되고, throughput은 전체 용량의 25%로 떨어진다.

반면 Figure 3.6에서와 같이, 같은 permutation을 4-ary 2-cube에 적용하면 다음과 같은 결과가 나온다:

• 2개 경로는 채널을 사용하지 않음
• 4개 경로는 채널 1개 사용
• 4개 경로는 채널 2개 사용 (예: H(5,10) = 2, |R5,10| = 2)
• 4개 경로는 채널 3개 사용 (경로 수: 3개)
• 4개 경로는 채널 4개 사용 (경로 수: 24개)

minimal routing만을 사용할 경우, 1-hop 경로가 병목이 된다. 대체 minimal route가 없기 때문이다. 이 경우 γmax,BR = 1이며, uniform traffic에서 γmax = 0.5이므로 throughput은 전체 용량의 50%다.

그러나, 1-hop 경로의 절반을 non-minimal routing으로 우회시키면 부하가 균등해진다. 예를 들어, node 1 → 2 traffic의 절반은 (1,2)로 가고, 나머지 절반은 (1,0)-(0,3)-(3,2) 경로를 사용한다. 이 경우 throughput은 용량의 89%까지 증가하며, 11%의 감소는 non-minimal 경로에서의 hop 수 증가 때문이라 볼 수 있다.

이 예시는 non-minimal routing이 부하 분산에 필수적일 수 있음을 보여준다. 비록 전체적으로 더 많은 경로를 사용하더라도, 네트워크 전체의 성능은 오히려 향상될 수 있다. 그러나 non-minimal routing은 deadlock 방지 등 구현 복잡성을 높이는 단점도 있다 (Chapter 14에서 다룸).

path diversity의 또 다른 중요한 장점은 고장 허용 능력이다. 예를 들어 Figure 3.5의 butterfly network에서 switch 07→17 link가 고장 나면, source 14에서 destination 15로 가는 경로는 존재하지 않는다. 시스템이 커질수록 고장 가능성도 커지므로, 대규모 네트워크는 하나 이상의 노드 또는 link 고장에도 견딜 수 있어야 한다.

한 네트워크의 고장 허용 능력은 edge-disjoint 또는 node-disjoint 경로 수로 측정된다:

• edge-disjoint paths: 공통 link 없이 구성된 경로 집합. 하나의 link 고장이 해당 경로 중 최대 하나에만 영향을 준다.
• 모든 노드 쌍 간 최소 edge-disjoint path 수가 j개라면, j개 미만의 link 고장에는 연결이 보장된다.
• node-disjoint paths: 출발지와 목적지를 제외하고, 공통 노드 없이 구성된 경로 집합. 하나의 노드 고장은 하나의 경로에만 영향을 미친다.
• node-disjoint는 edge-disjoint도 만족하므로, j개 node-disjoint 경로가 있다면 j개 이하의 link 및 node 고장을 견딜 수 있다.

운이 나쁘면, 특정 노드의 이웃 노드, 모든 입력 link, 출력 link가 동시에 고장날 수 있다. 이 경우 해당 노드는 다른 노드로부터 도달도, 전송도 불가능해지며, 이와 같은 고장 수는 다음과 같다:

min⁡x[min⁡{∣CIx∣, ∣COx∣}]\min_x \left[ \min \left\{ |CI_x|,\ |CO_x| \right\} \right]xmin​[min{∣CIx​∣, ∣COx​∣}]

3.4 패키징 비용 (Packaging Cost)

네트워크를 구축할 때, topology의 node들은 물리적 시스템의 packaging 모듈, 칩, 보드, 섀시 등에 매핑된다. topology와 packaging 기술, node 배치는 channel bandwidth 제약을 결정하며, 이 제약 없이는 topology를 평가하거나 비교할 수 없다.

이 절에서는 channel width w가 노드당 핀 수와 전체 global wiring 양에 의해 제한되는 2단계 packaging 계층 모델을 통해 간단한 비용 모델을 정립한다. 또한 bandwidth의 또 다른 구성 요소인 주파수 f가 packaging 선택에 어떻게 영향을 받는지도 다룬다.

첫 번째 계층: router 간 local wiring

• local wiring은 global wiring보다 저렴하고 풍부하므로, topology는 공간적 locality를 활용해 노드 간 거리를 가깝게 유지해야 한다.
• 예: 4×4 배열로 16개의 노드를 하나의 PC 보드에 배치하면, 전체 pin 중 75%가 로컬 연결로 사용 가능하며, 단지 32개 채널만 module 경계를 넘게 된다 (Figure 3.7 참조).

이러한 로컬 배치를 결정한 후, channel width의 주된 제약은 노드당 사용 가능한 핀 수가 된다. 노드당 최대 핀 수를 Wn이라 하면, degree가 δ인 node에서 channel width w는 다음을 만족해야 한다:

w≤Wnδ(3.12)w ≤ \frac{W_n}{δ} \quad (3.12)w≤δWn​​(3.12)

두 번째 계층: global wiring (예: 백플레인)

• 여러 보드를 연결하는 wiring 구조로 구성되며, global signal은 보드 → 커넥터 → 백플레인 → 커넥터 → 다른 보드 순으로 이동한다.
• 이때 사용 가능한 전체 global wires 수 Ws가 각 channel width의 제약이 된다.
• 예: 백플레인을 사용할 경우, 배선 밀도가 제한 요소다.
  • through-hole vias 공간 고려 시, 일반 PC 보드는 신호층당 1 wire/mm 또는 differential signal 기준 0.5 signal/mm 수준
  • 중간 비용 보드는 x, y 방향 각각 4층 → 총 8층 → 방향당 2 signal/mm 가능

Figure 3.7은 4×4 배열의 노드를 하나의 PC 보드에 패키징한 예를 보여준다. 이 구성에서는 전체 노드 핀 중 약 4분의 3이 local wiring으로 연결되어 있다.

bisection은 네트워크를 거의 절반으로 나누면서, 가능한 적은 수의 wire를 절단하는 방식이다. 따라서 bisection으로 나뉜 두 노드 집합은 패키징 시 local group으로 나누기에 좋은 기준이 된다. 이 모델은 일부 네트워크에서는 두 개 이상의 local group으로 나눠야 하는 제약이 있긴 하지만, 대부분의 경우 좋은 근사치를 제공한다.

minimum bisection을 활용하면, 사용 가능한 global wiring에 따라 channel width는 다음 제약을 받는다:

w≤WsBC(3.13)w ≤ \frac{W_s}{BC} \quad (3.13)w≤BCWs​​(3.13)

여기서는 2단계 packaging 계층을 중심으로 설명했지만, 더 큰 시스템에서 필요한 추가 packaging 계층에도 Equation 3.13을 적용할 수 있다.

Equation 3.12와 3.13을 결합하면 channel width에 대한 전체 제약은 다음과 같다:

w≤min⁡(Wnδ, WsBC)(3.14)w ≤ \min \left( \frac{W_n}{δ},\ \frac{W_s}{BC} \right) \quad (3.14)w≤min(δWn​​, BCWs​​)(3.14)

• 첫 번째 항 (Wn/δ)은 degree가 낮은 네트워크 (예: ring)에서 지배적이다. → 이 경우 핀 수 제한형
• 두 번째 항 (Ws/BC)은 degree가 높은 네트워크 (예: binary n-cube)에서 지배적이다. → 이 경우 bisection 제한형

channel width가 아닌 bandwidth 관점에서 제약을 다시 정리할 수도 있다:

• 노드당 최대 bandwidth: Bn=fWnB_n = f W_nBn​=fWn​
• 시스템 bisection 최대 bandwidth: Bs=fWsB_s = f W_sBs​=fWs​

이를 이용하면 channel당 최대 bandwidth b는 다음과 같이 표현된다:

b≤min⁡(Bnδ, BsBC)b ≤ \min \left( \frac{B_n}{δ},\ \frac{B_s}{BC} \right)b≤min(δBn​​, BCBs​​)

패키징 계층에서 고려해야 할 또 다른 중요한 요소는 배선 길이다.

채널 길이는 짧을수록 좋다. 일정 길이 이상이 되면, 신호 주파수가 길이의 제곱에 반비례하여 급격히 감소하기 때문이다:

f=min⁡(f0, f0(lwlc)−2)f = \min \left( f_0,\ f_0 \left( \frac{l_w}{l_c} \right)^{-2} \right)f=min(f0​, f0​(lc​lw​​)−2)

여기서 lc는 주어진 신호율 f₀에서 허용 가능한 감쇠를 기준으로 한 임계 길이(critical length)다.

Table 3.2는 신호율 2GHz에서 다양한 배선 종류에 대한 임계 길이 lc를 나타낸다 (1dB 감쇠 한도 기준):

대부분의 네트워크는 stripguide, fine wire cable 등을 사용한다. 이들은 약 1m 내외의 짧은 거리까지만 지원 가능하며, 이를 넘으면 데이터 속도가 급격히 떨어진다.

Repeater를 삽입하면 긴 채널에서도 고속 동작이 가능하지만, repeater 하나의 비용은 switch 하나와 비슷하다. 따라서 repeater 대신 switch를 삽입하여 channel을 분할하는 것이 더 효율적이다.

즉, 긴 channel이 필요한 topology는 고속 전기식 네트워크에 적합하지 않다.

대안으로 광 신호(optical signaling)를 사용할 수 있다. 광섬유는 전기 배선보다 감쇠와 신호 왜곡이 적어 훨씬 긴 거리(수십~수백 km)를 커버할 수 있다. 단점은 비용이다. 2003년 기준 동일 bandwidth에서 광 채널은 전기 채널보다 10배 이상 비쌌다.

Topology 비교 예시: Figure 3.9는 두 가지 6-node topology의 예를 보여준다.

• (a) 6-node ring: δ = 4, BC = 4
• (b) Cayley graph: δ = 6, BC = 10

패키징 조건:

• Wn = 140핀 / 노드
• Ws = 200 신호 / backplane

패키징 제약을 만족하기 위한 channel width w를 각각 계산:

1. Ring:

w≤min⁡(1404, 2004)=min⁡(35,50)=35(3.15)w ≤ \min \left( \frac{140}{4},\ \frac{200}{4} \right) = \min (35, 50) = 35 \quad (3.15)w≤min(4140​, 4200​)=min(35,50)=35(3.15)

1. Cayley graph:

w≤min⁡(1406, 20010)=min⁡(23.3,20)=20(3.16)w ≤ \min \left( \frac{140}{6},\ \frac{200}{10} \right) = \min (23.3, 20) = 20 \quad (3.16)w≤min(6140​, 10200​)=min(23.3,20)=20(3.16)

신호 주파수 f = 1GHz 기준으로, channel bandwidth는 다음과 같다:

• Ring: 35 Gbit/s
• Cayley graph: 20 Gbit/s

메시지 길이 L = 1024비트, router delay tr = 20ns일 때, 각 topology의 이상적 throughput과 무부하 지연은 Table 3.3에 비교되어 있다.

→ Cayley graph는 higher throughput, Ring은 낮은 지연 시간을 가진다.

왜 이런 결과가 나올까?

• Ring은 pin 수에 의해 channel width가 제한됨 (35)
• Cayley는 bisection 제약으로 제한됨 (20)

따라서:

• Cayley는 bisection 활용이 더 효율적이라 throughput이 높음
• 하지만 channel이 좁아져서 serialization 지연이 커지고, 평균 hop 수 감소 효과를 상쇄함

결론: 단순히 topology만 보면 Cayley가 더 나아 보이지만, 실제 latency는 packaging 제약에 의해 Ring이 더 낮다.

✅ 요약 판단

🔍 NoC에 의미 있는 부분만 요약

1. 채널 수 vs node degree (Wₙ/δ)

• NoC에서도 한 라우터에 몇 개의 입출력 포트를 가질 수 있느냐는 매우 중요한 설계 제약입니다.
• 예: 5-port (N/S/E/W/Local) mesh 라우터 구조 등
• NoC에서는 이것이 cell 면적, 전력, 배선 자원과 직결되므로 Wₙ/δ 제약은 유효합니다.

2. bisection bandwidth

• NoC에서도 mesh, torus, ring 등 다양한 topology의 bisection bandwidth는 network의 bottleneck을 결정합니다.
• 따라서 Chapter 3.4 후반부에서 설명한 "bisection bandwidth가 throughput에 미치는 영향"은 그대로 적용할 수 있습니다.

3. 배선 길이에 따른 주파수 저하 (f ∝ 1/l²)

• chip 내부 배선에서도 long wire delay, insertion buffer, repeater, clock skew, crosstalk 등과 관련된 문제가 있습니다.
• 따라서 완전히 무시할 수는 없지만, NoC 설계자는 H-tree, buffered link 등으로 해결할 수 있습니다.
• → 실제 설계 시 wire pipelining, serialization, 또는 CDN 기술 등을 통해 보완합니다.

✅ 결론

Chapter 3.4 "Packaging Cost"의 전부를 NoC에 적용할 필요는 없지만,
핀 수 제약(Wₙ/δ), bisection bandwidth, 배선 길이와 delay의 관계는
NoC 설계 시에도 반드시 고려할 요소입니다.

3.5 사례 연구: SGI Origin 2000

Figure 3.10은 SGI Origin 서버를 보여준다. 왼쪽은 16-프로세서가 들어간 캐비닛이며, 오른쪽은 8-프로세서 데스크사이드 모델이다.

이 시스템의 네트워크를 살펴보면, interconnection network를 packaging 계층에 매핑하는 데 필요한 여러 문제를 이해할 수 있다. 또한, 소수의 노드에서 수백 개의 노드까지 확장 가능한 시스템을 고정된 구성 요소로 구축할 때 발생하는 이슈들도 알 수 있다.

Origin 2000 네트워크는 SGI의 SPIDER routing chip에 기반한다. 이 칩은 양방향 네트워크 채널 6개를 제공하며, 각 채널은 20비트 폭이고 400 MHz에서 동작한다. 따라서 channel bandwidth는 6.4 Gbit/s가 되고, 하나의 node는 총 6개 채널을 가지므로 노드당 38.4 Gbit/s의 bandwidth를 가진다. 이 모든 채널은 backplane을 통해 구동될 수 있으며, 이 중 3개 채널은 최대 5미터 길이의 케이블을 직접 구동할 수 있다.

Figure 3.11은 Origin 2000 네트워크 topology가 노드 수에 따라 어떻게 변화하는지를 보여준다. 모든 구성에서 각 terminal router는 2개의 processing node(총 4개 프로세서)에 연결된다. 이 terminal 연결은 router의 6개 채널 중 2개를 사용하며, 나머지 4개는 다른 router들과 연결된다.

• 최대 16개 router (32개 노드, 64개 프로세서)로 구성된 시스템은 binary n-cube로 구성되며, 각 router는 최대 4차원 이웃 router에 연결된다 (Figure 3.11(a) 참조).
• 만약 4차원 전체를 사용하지 않는 경우(예: 8-router 시스템), 남은 채널은 머신 전체에 걸쳐 연결되어 네트워크 지름을 줄인다.

주석: 이와 같은 terminal에 여러 processor를 연결하는 방식은 concentration이라 하며, 이는 Section 7.1.1에서 다룬다.

Figure 3.12는 router 수가 16개를 초과하는 시스템에 대해 hierarchical topology를 사용하는 방식을 보여준다.

• 큰 시스템은 8-router (16-node, 32-processor)로 구성된 local subnetwork를 사용하며, 이 subnetwork는 binary 3-cube로 구성된다. 각 node는 채널 하나를 남겨둔다.
• 8개의 router-only global subnetwork가 local subnetwork들 간을 연결한다.
• router가 2ⁿ개인 시스템에서, 각 global network는 m = n − 3 차원의 binary cube로 구성된다.

예시:

• 최대 규모인 256-router (512-node, 1024-processor) 시스템은 32-node binary 5-cube 8개를 global subnetwork로 사용한다.
• local subnetwork j에 있는 router i의 남은 채널은 global subnetwork i의 router j에 연결된다.

특수한 경우:

• 32-node 시스템(n = 5)에서는 각 4포트 global subnetwork가 하나의 router chip으로 구현된다.
• 이 구조는 결과적으로 Clos network 구조이며 (Section 6.3 참조), 각 switch는 binary n-cube로 구성된다.

Figure 3.13은 Origin 2000 시스템의 packaging 구조를 보여준다.

• 각 노드(2프로세서)는 16인치 × 11인치 회로 보드 하나에 패키징된다.
• 각 router chip도 별도의 보드에 패키징된다.
• 노드 보드 4개(= 8프로세서)와 router 보드 2개가 하나의 chassis에 들어가며, 이들은 midplane으로 연결된다.
• chassis 내의 남은 공간은 I/O 서브시스템에 사용된다.
• chassis 2개(= router 4개)가 1개의 캐비닛에 들어간다.
• 시스템은 최대 64개 캐비닛(256 routers)까지 구성될 수 있으며, 대형 시스템의 경우 router 전용 캐비닛이 global subnetwork를 위해 추가된다.

router board의 6개 채널 중:

• 2개: midplane의 노드 보드 2개에 연결
• 1개: midplane 상의 다른 router에 연결
• 3개: back-panel connector를 통해 다른 chassis로 연결됨
  • 1개: 동일 캐비닛 내 다른 chassis에 연결
  • 1개: local subnet 내 두 번째 캐비닛에 연결
  • 1개: global subnetwork 또는 4-cabinet 시스템의 두 번째 캐비닛 쌍에 연결

Table 3.4는 이 hierarchical topology가 shared-memory multiprocessor 시스템의 요구사항을 어떻게 충족하는지를 보여준다. 이 시스템은 모든 router가 6포트라는 제약 하에서 구성된다.

• Equation 3.11에 따라, zero-load latency는 hop 수와 거리(지름)에 비례해 증가한다.
• Equation 3.10의 serialization latency는 채널 너비(20비트)로 고정된다.

Origin 2000은 시스템 크기에 따라 지름(diameter)이 로그 증가하도록 구성된 topology를 사용하여 latency를 낮춘다.

degree-4 binary n-cube 이상의 구조가 필요한 경우, hierarchical network 구조로 확장함으로써 로그 증가 특성을 유지할 수 있다.

또한 이 topology는 shared-memory multiprocessor에 필요한 bandwidth 조건도 만족한다.

• 모든 구성에서 bisection은 총 N개의 채널을 절단한다 (방향당 N/2개, 총 N개).
• 작은 시스템: binary n-cube에서 router 수 2ⁿ개 → bisection을 통과하는 채널 수 = 2ⁿ개 (방향당 2ⁿ⁻¹)
• 큰 시스템: 각 노드는 global subnetwork에 채널 1개를 가지고 있으며, 각 global subnetwork는 그 입력 대역폭만큼의 bisection bandwidth를 가진다.

Table 3.4 Origin 2000 네트워크의 노드 수에 따른 구성 및 성능:

3.6 참고 문헌 노트

이 책의 다음 장에서는 가장 널리 사용되는 두 가지 interconnection network에 중점을 두지만, 주목할 만한 다른 topology들도 존재한다.

• Cube-connected cycles는 hypercube와 동일한 hop 수(diameter)를 유지하면서도 node degree는 고정시킨다【153】.
• Fat tree는 모든 topology를 다항 로그 시간(polylogarithmic time) 안에 모방할 수 있는 보편적(universal) topology로 입증되었다【113】. 예: CM-5 시스템의 네트워크는 4-ary fat tree를 사용【114】.
• Cayley graphs는 cube-connected cycles을 포함하는 topology 집합으로, 간단한 routing과 동일한 크기의 hypercube보다 낮은 degree를 제공한다【7】.

3.7 연습문제

3.1 Tornado traffic in the ring
8-node ring에서 각 노드는 ring을 따라 3 hop 떨어진 노드로 트래픽을 보낸다 (즉, node i는 (i+3 mod 8)로 전송). 각 channel의 bandwidth는 1 Gbit/s이고, 각 input은 512 Mbit/s를 전송한다.

• minimal routing을 사용할 경우 channel load, 이상적 throughput, speedup은?
• non-minimal routing을 허용하고, 거리 기반 확률 분포 (3-hop 경로 5/8, 5-hop 경로 3/8)를 적용했을 때 재계산하라.

3.2 최악의 channel load 하한
최악의 트래픽 조건에서, bisection channel이 가장 높은 부하를 가진다고 가정할 때, 최대 channel load의 하한을 도출하라 (모든 channel의 bandwidth는 b로 동일).

3.3 channel load 상한의 한계
Equation 3.6이 타이트하지 않은 topology를 찾아라. 해당 topology가 부하를 최적으로 분산하기 위해 non-minimal routing이 필요한가? 이유를 설명하라.

3.4 대칭 topology의 channel load 상한의 타당성
edge-symmetric topology에 대해, Equation 3.5 및 3.6의 최대 channel load 상한이 실제 최적 부하와 동일함을 증명하라.

3.5 비대칭 bandwidth에서의 throughput
channel bandwidth가 동일하지 않을 때의 이상적 throughput 식을 도출하라. 필요하다면 γc와 γmax의 정의를 수정하라.

3.6 serialization latency가 topology 선택에 미치는 영향
64개의 processor node를 최소 latency로 연결해야 한다. 각 router는 processor와 동일한 chip에 위치하며 (direct network), processor chip당 네트워크용 pin은 128개다. 각 pin bandwidth는 2 Gbit/s, 평균 packet 길이는 512bit, router의 hop latency는 15ns이다. (wire latency Tw는 0으로 가정)

• (a) fully connected topology의 경우, average router latency Trmin, serialization latency Ts, zero-load latency T₀는?
• (b) ring topology의 경우 (Hmin = 16), latency들을 다시 계산하라.

3.7 non-random 트래픽에서의 latency
Section 1.3.1에서 torus와 ring의 latency는 random traffic 가정 하에 분석되었다. 이 결과로 ring이 더 낮은 latency를 가지는 것으로 나타났다. torus가 더 낮은 latency를 가지는 트래픽 패턴이 존재하는가? 존재하지 않는다면 그 이유는? (torus의 node (i,j)는 ring의 node 4i + j로 매핑된다고 가정)

3.8 Origin 2000에서의 latency
각 Origin 2000 rack은 19인치 너비, 72인치 높이이다. rack 내부 케이블은 48인치, rack 간 케이블은 플로어 아래로 라우팅되며, 케이블의 전파 속도는 2×10⁸ m/s이다. 메시지는 512비트 길이(32비트 word 16개).

• node 수가 16개 및 512개인 Origin 2000에 대해 wire delay Tw를 포함한 평균 zero-load latency를 계산하라 (uniform traffic 가정).

3.9 partially random wiring의 diameter 개선
random topology는 low diameter 등 좋은 특성을 가지나, 포장 및 routing 정규성 측면에서 비실용적일 수 있다.
Figure 3.14(a)의 mesh 네트워크에서, 좌우는 서로 다른 cabinet에 포장되어 있고, coaxial cable로 대응 node가 연결되어 있다.

• (a) 이 mesh network의 diameter는?
• (b) 케이블 연결을 무작위로 섞으면 diameter는 어떻게 변화하는가? (Figure 3.14(b) 참조). 모든 permutation 중 최소/최대 diameter는? 최소 diameter를 실현하는 permutation은?

3.10 fat tree 네트워크 성능
Figure 3.15는 16-node, radix-2 fat tree를 보여준다.

• (a) 모든 channel bandwidth가 terminal node의 injection/ejection rate와 같다면, 네트워크의 capacity는?
• (b) 다음과 같은 random routing을 사용할 경우: 패킷은 source에서 “위쪽”으로 올라가면서 두 개의 up 채널 중 임의 선택, 이후 “아래쪽” 경로로 destination까지 라우팅. 어떤 트래픽 패턴에서든 최대 channel load는 얼마까지 가능한가?

3.11 cube-connected cycles topology의 성능과 패키징
Figure 3.16은 3차 order cube-connected cycles이다.

• (a) channel bisection BC는?
• (b) minimal routing을 사용할 경우, 최대 hop 수 Hmax와 평균 hop 수 Hmin은?
• (c) 다음 제약 하에 이 topology를 패키징하라: Wn = 128 signals/node, Ws = 180 signals/backplane. packet 길이 L = 200bit, 주파수 f = 800 MHz, wire 길이는 무시. channel width w의 최대값은? pin 제한인가 bisection 제한인가? zero-load latency를 75ns로 맞추기 위한 router latency tr 값은?

3.12 성능의 물리적 한계
단순한 가정을 통해, 패키징된 네트워크의 diameter와 노드 간 거리의 실현 가능한 하한을 계산할 수 있다.

• (a) radix k switch를 사용할 경우, N-node 네트워크의 최소 diameter는?
• (b) 노드가 부피 V를 가질 때, 3차원에서 노드 간 최대 거리를 최소화하는 packaging 형태는? 많은 수의 노드를 가정할 때 이 거리는 얼마인가?

이 장에서는 간단한 interconnection network의 구조와 설계를 살펴보며 전체적인 개요를 제공한다. 가장 단순한 형태의 네트워크인 butterfly network with dropping flow control을 다룬다. 이 네트워크는 비용이 많이 들지만, interconnection network 설계의 주요 개념을 강조하는 데 유용하다. 이후 장에서는 더 효율적이고 실용적인 네트워크를 만드는 방법을 다룰 것이다.

2.1 Network Specifications and Constraints

모든 공학적 설계 문제와 마찬가지로, 네트워크 설계는 무엇을 만들고 싶은지를 정의하는 사양(specifications)과 가능한 해법의 범위를 제한하는 제약조건(constraints)에서 출발한다. 이 장에서의 예제 네트워크 사양은 아래의 Table 2.1에 요약되어 있다. 네트워크의 크기(64개의 포트)와 포트당 요구되는 bandwidth가 포함된다. 테이블에서 보이듯, peak bandwidth와 average bandwidth가 같으며, 이는 입력이 0.25 Gbyte/s의 속도로 지속적으로 메시지를 inject한다는 것을 의미한다. 각 입력이 각 출력을 동일한 확률로 선택하는 random traffic이 예상되며, 메시지 크기는 4~64 bytes이다. 또한 QoS와 신뢰성 사양은 packet drop을 허용한다. 즉, 모든 packet이 목적지에 반드시 전달될 필요는 없다. 이는 flow control 구현을 단순하게 만들어준다. 실제 시스템에서는 dropped packet의 비율과 조건 등을 명시한 더 상세한 QoS 사양이 포함되겠지만, 여기서는 설계 개념을 설명하는 데 이 정도면 충분하다.

예제 네트워크 설계의 제약조건은 Table 2.2에 정리되어 있다. 이 제약은 각 수준의 패키징(capacity and cost)을 정의한다. 네트워크는 chip들로 구성되고, chip은 circuit board에 실장되며, board는 cable로 연결된다. 제약조건은 각 계층에서 module interface를 통해 전송할 수 있는 signal 수와 각 module의 비용을 지정한다. cable의 경우, bandwidth 감소 없이 도달할 수 있는 최대 거리도 명시되어 있다.

1. signal은 반드시 pin을 의미하지는 않는다. 예를 들어, differential signaling에서는 signal당 두 개의 핀이 필요하다.
2. bandwidth × distance² (Bd²)가 일정한 케이블의 특성상, 2배 길이로 전송할 경우 bandwidth는 4분의 1로 줄어든다.

Table 2.1 Example Network Specifications

Table 2.2 Example Network Constraints

2.2 Topology

예제 네트워크는 단순화를 위하여 butterfly topology를 갖는다. 하나의 입력 포트 입장에서 보면, butterfly는 tree처럼 보인다(Figure 2.1 참고). 각 단계(level)는 switching node로 구성되며, 이들은 terminal node와 달리 packet을 보내거나 받지 않고 전달만 한다. 또한 channel은 unidirectional로, 화살표 방향(입력에서 출력, 왼쪽에서 오른쪽)으로 흐른다. topology로 butterfly를 선택했지만, 이는 아직 설계의 절반이다. network의 speedup, butterfly의 radix, 그리고 topology의 패키징 맵핑을 결정해야 한다.

speedup은 network의 총 입력 bandwidth와 이상적인 network capacity의 비율이다. 여기서 capacity는 이상적인 라우팅과 flow control이 있다고 가정했을 때 가능한 최대 throughput이다. speedup이 1이면, 입력 요구량과 네트워크가 제공할 수 있는 용량이 일치한다는 의미이다. 더 큰 speedup을 제공하면 여유(margin)가 생기며 비이상적 상황에 대응할 수 있다. 이는 건축의 안전계수(safety factor) 개념과 유사하다.

butterfly에서 각 channel의 bandwidth를 입력 포트와 동일하게 설계하면 speedup은 1이 된다. random traffic에서는 각 입력이 모든 출력에 균등하게 보내기 때문에, 모든 channel은 동일한 수요를 받는다. 본 예제에서는 각 channel이 0.25 Gbyte/s의 bandwidth를 갖는다. 하지만, 단순성을 위해 speedup 8을 선택한다. 이는 매우 큰 수치지만(브루클린 브리지는 safety factor 6), 이후에는 이 수치를 줄이는 법을 배운다.

speedup과 패키징 제약조건을 고려하여, 각 switch node의 입력/출력 수(radix)가 결정된다. 예를 들어, Figure 2.1의 butterfly는 radix 2이다. 하나의 switch node는 chip 하나에 구현되며, chip당 총 signal 수는 150을 넘지 않아야 한다. speedup 8을 구현하려면 8 × 0.25 = 2 Gbyte/s의 channel bandwidth가 필요하고, 이는 1 Gbit/s의 signal 16개를 사용하여 구성된다. 여기에 overhead signal 2개를 더하면, channel은 18 signal로 구성되며, chip당 150/18 ≈ 8개의 channel만 탑재 가능하다. 따라서 radix-4 butterfly, 즉 입력/출력 4개씩을 가지는 switch node를 선택한다.

64개의 출력 포트에 연결하려면 log₄64 = 3 단계의 switch node가 필요하다. 따라서 이 네트워크는 radix-4, 3-stage butterfly, 즉 4-ary 3-fly이다. 전체 topology는 Figure 2.2에 나와 있다. Figure 2.1의 확장판이며, input 1에서 시작해 64개의 출력으로 향하는 경로는 여전히 tree 형태이며, tree의 degree는 radix인 4이다.

topology 설계의 마지막 단계는 패키징이다. 이미 각 switch node를 chip 하나로 배치하기로 결정했다. radix를 chip 제약조건에 맞춰 정했기 때문에, chip은 설계 제약을 충족한다. 이제 이 chip을 board에 실장해야 하며, 비용을 최소화하기 위해 한 board에 가능한 많은 chip을 넣고 싶다. 하지만 board당 signal 수는 750을 초과할 수 없다. 이는 커넥터 한쪽 면을 통해 보낼 수 있는 최대 signal 수, 즉 connector density × 길이에 의해 결정된다.

유효한 board 간 partitioning은 Figure 2.2에 표시되어 있으며, 각 board의 경계는 점선 상자로 나타나 있다. 첫 번째 stage는 4개의 board에, board당 4개의 chip으로 배치된다. 다음 두 stage는 4개의 board에, board당 8개의 chip으로 배치된다. 각 board에는 18 signal로 구성된 channel이 32개 입출력되며, 총 32 × 18 = 576 signals로 제약을 만족한다.

각 board에는 총 32개의 channel이 존재하며, 각 channel은 18개의 signal을 사용하므로 총 576 signal이 필요하다. 이는 750 signal 제한 내에 충분히 들어간다. 날카로운 독자는 첫 번째 stage의 board에 router chip 5개를 실을 수도 있다고 생각할 수 있다(40개 channel, 즉 720 signals). 하지만 그렇게 하더라도 여전히 4개의 첫 번째 stage board가 필요하므로 비효율적이다. 또한 두 번째 stage의 board에 router chip 10개를 실을 수는 없다. 필요한 46개 채널은 총 828 signal이 되며, board의 pinout을 초과하기 때문이다.

마지막으로, board 간 연결은 Figure 2.3에서 보듯이 cable을 통해 이루어진다. 그림의 굵은 회색 선 하나는 하나의 cable을 나타내며, 이는 하나의 circuit board에서 다른 board로 18-bit channel 4개를 전달한다. 8개의 circuit board는 이런 cable 16개로 연결된다. 즉, 각 첫 번째 stage board에서 두 번째 및 세 번째 stage board로 각각 cable을 연결한다. 이 8개의 board가 하나의 chassis 내에 배치되므로 cable의 길이는 제약 내에 있다.

한 걸음 물러서서 보면, 이 topology에서 어떻게 모든 입력을 모든 출력에 연결할 수 있는지 확인할 수 있다. 첫 번째 stage의 switch는 나머지 stage가 있는 4개의 circuit board 중 하나를 선택한다. 두 번째 stage는 선택된 board 내의 4개의 chip 중 하나를 선택한다. 마지막 stage는 원하는 출력 포트를 선택한다. 이러한 분할 정복(divide-and-conquer) 구조는 패킷을 라우팅할 때 효율적으로 사용된다.

2.3 Routing

우리의 단순한 butterfly network는 destination-tag routing을 사용한다. 이는 destination address의 비트를 이용해 네트워크의 각 단계에서 출력 포트를 선택하는 방식이다.

64개의 노드를 갖는 이 네트워크에서 destination address는 6비트이다. 각 switch는 이 중 2비트(dibit)를 사용하여 4개의 출력 중 하나를 선택하고, 이는 남은 노드 집합의 1/4로 라우팅된다.

예를 들어, 입력 포트 12에서 출력 노드 35 (= 100011₂)로 패킷을 보내는 경우를 보자. 가장 상위 dibit인 10은 switch 0.3의 세 번째 출력 포트를 선택하여 패킷을 switch 1.11로 보낸다. 그 다음 중간 dibit 00은 switch 1.11의 첫 번째 출력 포트를 선택하여 패킷을 switch 2.8로 보낸다. 마지막으로 가장 하위 dibit 11은 switch 2.8의 마지막 출력 포트를 선택하여 출력 포트 35로 패킷을 전달한다.

이러한 출력 포트 선택 순서는 입력 포트와 무관하다. 예를 들어, 입력 포트 51에서 출력 포트 35로 보내도 같은 선택 순서를 따른다. 즉, 라우팅 알고리즘은 패킷과 함께 destination address만 저장하면 된다.

일관성을 위해, 모든 switch node는 destination address의 가장 상위 dibit만 참조한다. 그런 다음, 패킷이 node를 떠나기 전에 address는 왼쪽으로 2비트 shift되어 방금 사용한 bit는 제거되고 다음 dibit이 상위 위치로 올라온다. 예를 들어, node 35로 라우팅을 시작할 때 address 100011₂는 shift 되어 001100₂이 된다.

이러한 convention 덕분에 모든 switch node가 동일한 방식으로 동작할 수 있고, 특별한 설정 없이도 사용 가능하다. 또한, address field의 크기만 확장하면 더 많은 노드를 가지는 네트워크로 확장할 수 있다.

2.4 Flow Control

이 네트워크의 각 채널은 한 cycle당 16-bit의 physical digit, 즉 phit을 전달한다. 그러나 네트워크는 32~512bit 크기의 전체 패킷을 전달해야 하므로, Figure 2.4에 제시된 간단한 프로토콜을 사용하여 여러 phit을 packet으로 조립한다.

각 packet은 header phit으로 시작하고, 그 뒤에 0개 이상의 payload phit가 따라온다. header phit은 새로운 packet의 시작을 나타내며, 라우팅 알고리즘에 사용될 destination address도 포함한다. payload phit은 실제 데이터를 담고 있으며, 16-bit 단위로 나뉜다.

하나의 packet을 구성하는 phit은 연속적이어야 하며, 중간에 끊기지 않아야 한다. 단, packet 사이에는 얼마든지 null phit이 있을 수 있다. 각 16-bit word가 header인지 payload인지 또는 null인지 구별하기 위해, 각 채널에 2-bit type field를 추가로 붙인다.

이 field는 다음과 같은 역할을 한다:

• H: Header
• P: Payload
• N: Null

따라서 각 packet은 하나의 H word와 그 뒤를 따르는 0개 이상의 P word, 그리고 0개 이상의 N word로 구성된다. 이를 정규 표현식으로 표현하면 (HP*N*)* 형식이다. 즉, link 위에는 여러 개의 packet이 흐를 수 있으며, 각 packet은 위의 구조를 갖는다.

이제 phit을 packet으로 조립했으니, flow control의 핵심, 즉 packet에 자원을 할당하는 과정으로 넘어간다. 단순화를 위해, 우리의 butterfly network는 dropping flow control을 사용한다. 패킷이 switch에 도달했을 때 필요한 output port가 사용 중이면, 해당 packet은 drop (폐기)된다. 이러한 flow control은 end-to-end error control protocol이 존재함을 가정하고 있다.

Figure 2.4는 네트워크에서 사용되는 packet format을 보여준다. 세로 방향은 시간(cycle)을, 가로 방향은 채널의 18개 signal을 나타낸다. 왼쪽 2개 signal은 phit type (H, P, N)을 담고, 나머지 16개 signal은 destination address 또는 data를 담거나 null일 경우 비워진다.

Table 2.3은 이 네트워크에서 사용하는 phit type의 encoding을 보여준다:

패킷을 재전송하는 역할은 상위의 end-to-end error control protocol이 담당할 것으로 가정한다. 패킷을 drop하는 것은 가장 비효율적인 flow control 방식 중 하나이다. 패킷 손실률이 높고, 결국 drop되는 패킷에 채널 bandwidth를 낭비하게 된다. 이보다 훨씬 나은 flow control 기법들이 있으며, Chapter 12에서 다룬다. 그러나 이 장에서는 개념과 구현이 매우 단순하기 때문에 dropping flow control이 적합하다.

2.5 Router Design

butterfly network의 각 switching node는 router로, 입력으로부터 패킷을 받고, 라우팅 알고리즘에 따라 목적지를 결정한 후, 적절한 출력으로 패킷을 전달한다. 지금까지의 설계 결정은 매우 단순한 router를 가능하게 한다.

Figure 2.5는 router의 block diagram이다. 이 router의 datapath는 다음으로 구성된다:

• 18-bit input register 4개
• 18-bit 4:1 multiplexer 4개
• routing field를 shift하는 shifter 4개
• 18-bit output register 4개

총 144-bit의 register와 약 650개의 2-input NAND gate에 해당하는 회로가 사용된다.

phit은 매 cycle마다 input register에 도착하며, 모든 multiplexer로 전달된다. 각 multiplexer에서 연결된 allocator는 각 phit의 type과 header phit의 next hop field를 검사하고 switch를 설정한다.

선택된 입력의 phit은 이후 shifter로 전달된다. allocator의 제어 하에, header phit은 routing field를 왼쪽으로 2비트 shift하여 현재 field를 제거하고 다음 field를 노출한다. payload phit은 변경 없이 그대로 전달된다.

router의 제어는 전적으로 4개의 allocator에 의해 이루어진다. 이들은 각 출력 포트를 제어하며 multiplexer와 shifter를 조작한다. allocator는 4개의 입력 중 하나에 출력 포트를 할당한다.

Allocator 구성 (Figure 2.6)

각 allocator는 거의 동일한 구조의 bit slice 4개로 구성되며, 각 slice는 다음 세 영역으로 나뉜다:

1. Decode
   • 각 입력 phit의 상위 4비트를 해독한다.
   • request_i: 입력 i의 phit이 header이고, route field의 상위 2비트가 현재 출력 포트 번호와 일치하면 true
   • payload_i: 입력 i의 phit이 payload이면 true
2. Arbitrate
   • 4-input fixed-priority arbiter를 사용한다.
   • 요청 신호 중 첫 번째(위쪽부터)의 입력에 grant를 부여한다.
   • grant 시, 해당 입력을 multiplexer에서 선택하도록 select 신호를 활성화
   • header가 통과하면 shift 신호도 활성화되어 routing field를 shift함
3. Hold
   • 동일한 packet의 payload가 따라오는 동안, 출력을 해당 입력에 고정
   • last_i는 이전 cycle에 선택된 입력을 기억
   • 이번 cycle에도 payload가 입력되면, hold_i를 활성화하고 avail을 비활성화하여 새로운 header의 할당을 막는다

Note: 실제 시스템에서는 fixed-priority arbiter는 사용하지 않는다. 불공정성과 livelock 또는 starvation 문제를 유발하기 때문이다. Chapter 18과 19에서 더 나은 arbitration 방법들을 다룬다.

Verilog RTL 모델 (Figure 2.7)

아래는 Figure 2.6의 allocator를 Verilog로 구현한 것이다.

• 각 입력 phit에서 routing 정보와 type 정보를 해석
• 현재 출력 포트(thisPort)에 맞는 입력을 선택
• payload가 이어질 경우 hold 상태 유지
• shift 제어 신호를 통해 header field를 업데이트
• 고정 우선순위 방식으로 grant 결정

Verilog는 텍스트 기반으로 하드웨어를 기술할 수 있는 편리한 방법이며, simulation 및 synthesis input 언어로도 사용 가능하다. 따라서 이 방식으로 기술한 후 simulation으로 동작을 검증하고, ASIC 또는 FPGA를 위한 gate-level 디자인으로 synthesis할 수 있다.

// simple four-input four output router with dropping flow control
module simple_router(clk,i0,i1,i2,i3,o0,o1,o2,o3) ;

input clk ; // chip clock
input [17:0] i0,i1,i2,i3 ; // input phits
output [17:0] o0,o1,o2,o3 ; // output phits

reg [17:0] r0,r1,r2,r3 ; // outputs of input registers
reg [17:0] o0,o1,o2,o3 ; // output registers
wire [17:0] s0,s1,s2,s3 ; // output of shifters
wire [17:0] m0,m1,m2,m3 ; // output of multiplexers
wire [3:0] sel0, sel1, sel2, sel3 ; // multiplexer control
wire shift0, shift1, shift2, shift3 ; // shifter control

// the four allocators
alloc a0(clk, 2’b00, r0[17:14], r1[17:14], r2[17:14], r3[17:14], sel0, shift0) ;
alloc a1(clk, 2’b01, r0[17:14], r1[17:14], r2[17:14], r3[17:14], sel1, shift1) ;
alloc a2(clk, 2’b10, r0[17:14], r1[17:14], r2[17:14], r3[17:14], sel2, shift2) ;
alloc a3(clk, 2’b11, r0[17:14], r1[17:14], r2[17:14], r3[17:14], sel3, shift3) ;

// multiplexers
mux4_18 mx0(sel0, r0, r1, r2, r3, m0) ;
mux4_18 mx1(sel1, r0, r1, r2, r3, m1) ;
mux4_18 mx2(sel2, r0, r1, r2, r3, m2) ;
mux4_18 mx3(sel3, r0, r1, r2, r3, m3) ;

// shifters
shiftp sh0(shift0, m0, s0) ;
shiftp sh1(shift1, m1, s1) ;
shiftp sh2(shift2, m2, s2) ;
shiftp sh3(shift3, m3, s3) ;

// flip flops
always @(posedge clk)
begin
r0=i0 ; r1=i1 ; r2=i2 ; r3=i3 ;
o0=s0 ; o1=s1 ; o2=s2 ; o3=s3 ;
end
endmodule

2.6 Performance Analysis

dropping flow control에서는 성능 지표들이 패킷이 drop될 확률에 크게 영향을 받는다.

네트워크 모델 (Figure 2.9)

Dropped packet을 재전송한다고 가정하고, 간단한 모델로 분석을 시작한다.
입력과 출력 사이의 대칭성, random traffic 패턴 때문에, 하나의 입력만 고려하면 충분하다.

• 패킷은 λ의 비율로 네트워크에 주입된다.
• λ는 2 Gbyte/s 채널 대역폭으로 정규화되어 있으며, λ = 1은 최대 속도 의미.
• 재전송되는 패킷도 합쳐져서 p₀라는 총 주입률이 된다.

각 단계에서:

• 일부 패킷은 충돌로 drop됨.
• 다음 단계로 통과하는 비율은 p₁, p₂, p₃.
• drop된 패킷은 입력으로 다시 돌아가며 재전송됨.

수식 (Equation 2.2)
네트워크의 각 stage i에서 다음 stage의 출력률 pᵢ₊₁은 다음과 같다:

pi+1=1−(1−pi4)4p_{i+1} = 1 - \left(1 - \frac{p_i}{4} \right)^4pi+1​=1−(1−4pi​​)4

입력 λ = 0.125 (speedup = 8)일 때, 각 stage 출력은:

• p₁ = 0.119
• p₂ = 0.114
• p₃ = 0.109

즉, 입력이 0.125일 때 실제 throughput은 0.109이며, 0.016(=12.6%)는 drop된다.

재전송의 피드백

drop된 패킷의 재전송은 전체 입력률 p₀를 증가시키고, 이는 또 drop률을 높인다. 이 과정이 안정되면, 다음 조건이 성립한다:

• 안정 조건: p₀ ≤ 1
• 최종적으로 p₃ = λ 이면 수렴

Throughput 곡선 (Figure 2.10)

Figure 2.10은 injection rate에 따른 throughput을 보여준다.

• 낮은 부하: throughput ≈ injection rate
• 높은 부하: drop이 심해져 throughput 감소
• 포화(saturation): 최대 throughput은 0.432 (43.2%)
• 재전송을 하든 안 하든, 이 이상은 낼 수 없다.

따라서 이 네트워크는 speedup 2.5 이상이면 충분하지만, latency 개선을 위해 speedup 8을 선택한 것이다.

dropping flow control이 실제 사용되지 않는 이유는 바로 이 throughput의 비효율성 때문이다.
Chapter 12에서는 채널 대역폭의 90% 이상을 효율적으로 사용하는 flow control 기법들을 소개한다.

Latency 모델

latency도 channel capacity 기준으로 정규화한다.
패킷이 drop 없이 네트워크를 통과할 때는 6-cycle의 지연이 있다. 이를 relative latency = 1.0으로 정의.

하지만 drop되는 패킷은 다시 전송되며, latency가 누적된다.

• drop 비율 pᴰ:PD=p0−p3p0P_D = \frac{p_0 - p_3}{p_0}PD​=p0​p0​−p3​​
• 평균 latency T는 다음 수식으로 계산:

T=∑i=0∞(i+1)PDi(1−PD)=11−PD=p0p3T = \sum_{i=0}^\infty (i+1) P_D^i (1 - P_D) = \frac{1}{1 - P_D} = \frac{p_0}{p_3}T=i=0∑∞​(i+1)PDi​(1−PD​)=1−PD​1​=p3​p0​​

(Figure 2.11에 그래프 있음)

• throughput이 0.39일 때 latency는 2배가 된다.
• throughput이 0.43에서 포화, 그 이상은 latency 증가만 발생

실제 시스템에서는 drop을 즉시 감지하고 6 cycle 내에 재전송하는 것은 비현실적이다.
재전송 패킷과 신규 패킷이 충돌할 가능성이 증가하므로, queueing delay도 고려해야 한다.
Figure 2.11은 queueing이 포함된 latency 곡선도 함께 보여준다. 이 곡선은 포화에 가까워질수록 무한대로 증가하는 전형적인 interconnection network의 형태를 갖는다.

Figure 2.11은 offered traffic (injection rate)에 따른 relative latency를 나타낸다.
실선은 본문에서 제시한 단순 모델을, 점선은 queueing delay를 고려한 모델을 나타낸다.

Equation 2.3과 Figure 2.11은 평균 latency만을 보여준다.
하지만 많은 응용에서는 평균뿐만 아니라 latency의 분포, 특히 최악의 latency나 **latency의 변동성(jitter)**이 중요하다.
예를 들어, 비디오 재생 시스템에서는 패킷을 재생 전에 저장하는 버퍼 크기는 평균 latency가 아니라 jitter에 의해 결정된다.

우리 예제 네트워크에서는, relative latency가 정확히 i가 될 확률은 다음과 같다:

P(T=i)=PDi−1(1−PD)P(T = i) = P_D^{i - 1} (1 - P_D)P(T=i)=PDi−1​(1−PD​)

이러한 지수 분포는 이론상 무한한 최대 latency와 무한한 jitter를 의미한다.
현실적으로는 전체 패킷 중 일정 비율(예: 99%)이 도달하는 데 걸리는 최대 지연 시간으로 jitter를 정의할 수 있다.

지금까지 논의된 성능 측정은 모두 uniform random traffic을 기준으로 한다.
butterfly network에서는 이것이 최상의 경우이다.
그러나, 예를 들어 bit-reversal과 같은 특정 traffic pattern에서는 성능이 훨씬 나빠질 수 있다.

bit-reversal traffic pattern:
이진 주소 {bₙ₋₁, bₙ₋₂, ..., b₀}를 가진 노드가 {b₀, b₁, ..., bₙ₋₁}를 목적지로 패킷을 보낸다.

이처럼 성능이 나빠지는 주요 원인은 각 입력에서 출력까지 경로가 단 하나이기 때문이다.
경로 다양성(path diversity)이 있는 네트워크는 이러한 부하 조건에서도 훨씬 좋은 성능을 보인다.

2.7 Exercises

2.1 Simple Network의 비용
Table 2.1과 2.2의 데이터를 이용하여 이 단순 네트워크의 비용을 계산하라.

2.2 전력 제한 조건 추가
board당 chip 개수를 6개로 제한하자. 이는 chip에 충분한 전력을 공급하고 열을 적절히 분산시키기 위함이다.
이 새로운 제약 조건을 포함하면서 기존 조건도 만족하는 packaging을 설계하라. 해당 packaging의 비용은?

2.3 공정한 allocator
Figure 2.7에 제시된 Verilog allocator 코드를 수정하여 더 공정한 arbitration을 구현하라.
시뮬레이션을 통해 새 allocator를 검증하고 설계를 설명하라.

2.4 router의 degree 확장
simple router를 4×4가 아닌 5×5 switch로 확장한다면, 이를 2-D mesh 또는 torus network 구현에 사용할 수 있다.
router와 packet format을 어떻게 확장해야 할지 설명하라.

2.5 재전송 우선 처리
Verilog 코드를 수정하여 재전송 패킷에 우선권을 부여하라.
예를 들어, 동일한 switch에서 두 개의 head phit이 동일한 출력을 요청할 경우,
항상 재전송된 패킷이 우선권을 갖도록 한다.
이를 위해 phit header에 priority field를 추가하고, 패킷이 재주입될 때 이 필드가 적절히 설정된다고 가정한다.

2.6 여러 번 drop되는 것 줄이기
2.5에서 제안한 것처럼 동일한 패킷이 여러 번 drop되는 것을 줄이면,
평균 latency는 감소하는가? 그 이유를 설명하라.

2.7 butterfly 확장에 따른 drop률 변화
예제 butterfly network에 stage를 추가하여 노드 수를 늘리면, drop되는 패킷의 비율은 어떻게 될까?
반대로, switch의 degree를 증가시키면 어떻게 될까?
drop 확률만을 고려할 때, 노드를 늘릴 경우 stage를 늘리는 것과 switch degree를 키우는 것 중 무엇이 더 효율적인가?

2.8 현실적인 drop delay
실제 네트워크에서는 drop된 패킷을 다시 전송하기까지 상당한 지연이 존재한다.
예를 들어, acknowledgment가 source에 도달하고, timeout까지 기다려야 한다.
이러한 delay를 반영하여 Equation 2.3을 수정하라.

2.9 시뮬레이션
우리 예제 네트워크를 시뮬레이션하는 간단한 프로그램을 작성하라.
이를 통해 injection rate에 따른 latency를 실험적으로 측정하라.
결과를 Equation 2.3과 Figure 2.11의 분석 결과, 그리고 queueing 모델과 비교하라:

T=T02+p0p3(T02+p02(1−p0))T = \frac{T_0}{2} + \frac{p_0}{p_3} \left( \frac{T_0}{2} + \frac{p_0}{2(1 - p_0)} \right)T=2T0​​+p3​p0​​(2T0​​+2(1−p0​)p0​​)

여기서 T0T_0T0​는 zero-load latency, 즉 drop되지 않은 패킷의 latency이다.

2.10 timeout 메커니즘 추가
Exercise 2.9의 시뮬레이터에 timeout 기능을 추가하라.
Exercise 2.8에서 제시된 모델과 비교하고, 주요 차이점을 설명하라.