Butterfly Networks

수많은 토폴로지가 제안되어 왔지만, 실제로 구현된 대부분의 네트워크는 두 가지 주요 계열인 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은 짝수로 가정)