Zeah Engineering Factory

이 토폴로지 섹션의 마지막 장에서는 토폴로지를 패키징하는 실용적인 방법 몇 가지를 간단히 살펴본다. 먼저 concentrator와 distributor를 살펴본다.

Concentrator는 여러 terminal node의 트래픽을 하나의 network channel로 결합한다. 단일 terminal의 트래픽이 network channel을 완전히 활용하기에 부족할 때 사용된다. 또한 bursty한 특성을 지닌 다수의 terminal 트래픽을 결합할 때에도 효과적이다. peak 대비 평균 트래픽의 비율이 클수록 concentrator를 사용하면 serialization latency가 줄고 더 비용 효율적인 네트워크가 된다.

Distributor는 concentrator의 반대 개념이다. 단일 node로부터 나오는 트래픽을 여러 network channel에 packet 단위로 분산시킨다. 단일 channel로는 처리하기 어려운 많은 양의 트래픽을 가진 node를 연결할 때 사용된다. serialization latency는 증가하고 부하 균형은 감소하지만, 어쨌든 연결이 필요한 node에 유용하게 사용될 수 있다.

하나의 network node를 여러 개의 chip이나 module에 분할하는 방법은 세 가지가 있다: bit slicing, dimension slicing, channel slicing.

• Bit slicing에서는 w-bit 너비의 node를 k개의 w/k-bit 너비의 slice로 나누어 각 slice를 개별 module에 배치한다. 각 slice는 router datapath의 w/k-bit 부분을 포함한다. 제어 정보는 모든 slice에 분산되어야 하므로 제어 정보 분산을 위한 추가 핀이 필요하고, 그만큼 latency도 증가한다.
• Dimension slicing에서는 한 dimension에 해당하는 channel 전체가 각 slice에 포함되도록 node를 나눈다. 이 방식에서는 하나의 slice에 들어온 트래픽이 다른 slice로 나가야 할 때를 대비해 추가적인 데이터 channel이 필요하다.
• Channel slicing에서는 w-bit 너비의 node를 w/k-bit channel을 가진 k개의 독립적인 node로 분할한다. bit slicing과 달리, 이들 sub-node 사이에는 연결이 없다. 전혀 별개의 네트워크를 형성한다. 이 경우 terminal마다 distributor를 사용하여 트래픽을 여러 network slice로 분산한다.

7.1 Concentrators and Distributors

7.1.1 Concentrators

일부 애플리케이션에서는 여러 (예: M개) network terminal에서 나오는 트래픽을 하나의 channel로 결합하는 것이 바람직하다. 이 경우 M개의 terminal은 하나의 큰 terminal처럼 보인다. 이 결합을 수행하는 장치를 concentrator라 부른다. 예를 들어 M=4일 때, concentrator는 terminal 측에서 M개의 양방향 channel을 받아서 network 측의 하나의 양방향 channel로 결합한다. 포트 수를 줄이는 효과 외에도 총 bandwidth도 감소시킬 수 있다.

Concentration factor는 terminal 측 bandwidth 대비 network 측 bandwidth의 비율로 정의되며 다음과 같다:
    kC = MbT / bN
여기서 bT는 terminal channel bandwidth, bN은 network 측 channel bandwidth이다.

예를 들어 8-node ring이 8개의 terminal을 직접 연결할 수 있다. 하지만 terminal과 network 사이에 2:1 concentrator를 배치하면 동일한 8개의 terminal을 4-node ring으로 연결할 수 있다.

Concentrator는 특히 bursty한 트래픽 특성을 가진 terminal들을 묶을 때 자주 사용된다. network 측 channel의 bandwidth를 공유함으로써 bursty source들의 부하를 완화하고 channel bandwidth를 효율적으로 사용할 수 있다.

예시로, 512-node multicomputer에서 각 node가 평균 100 Mbit/s 트래픽을 발생시키는 경우를 보자. 하지만 캐시 미스가 발생하면 128ns 동안 순간적으로 1 Gbit/s의 트래픽이 발생한다 (128bit 데이터 전송). 이 경우 serialization latency가 메모리 접근 시간을 증가시키는 것을 방지하려면, 각 processor에서 1 Gbit/s의 channel을 network으로 연결해야 한다.

이 경우 8-ary 3-cube를 1 Gbit/s channel로 구성하면 total pin bandwidth는 3Tbit/s가 된다. 평균 bandwidth만 처리할 수 있도록 network를 구성하고 worst-case 트래픽을 가정하면 200 Mbit/s channel이 필요하고, 이 경우 serialization latency는 128ns에서 640ns로 5배 증가한다.

더 효율적인 방법은 8개 node를 8:1 concentrator로 묶고, 64-node 4-ary 3-cube network를 구성하는 것이다. concentrator에서 network node로 2 Gbit/s channel을 연결하여 병목을 방지한다. 이 경우 각 concentrated node는 평균 800 Mbit/s를 제공한다. 최대 8 Gbit/s 트래픽이 발생할 수도 있지만, 실제로는 동시에 두 개 이상의 node가 전송하는 경우는 매우 드물다 (동시에 8개 node가 전송할 확률은 10⁻⁸). 따라서 평균적인 상황에서는 network diameter와 serialization latency가 줄어드는 이점이 더 크다.

network를 1 Gbit/s channel로 구성하면 total pin bandwidth는 384 Gbit/s로 감소하며 (기존 대비 8배 감소), 평균 bandwidth 기준으로 구성하면 800 Mbit/s channel로 충분하고, 이 경우 latency는 160ns로 4배 줄어든다.

또한 concentrator는 packaging 관점에서도 유리하다. 예를 들어 4개의 terminal이 하나의 module (예: chip)에 함께 배치되는 경우, 이들 terminal의 트래픽을 concentrator로 결합해 module 전체를 하나의 network terminal로 간주할 수 있다.

7.1.2 Distributors

Distributor는 concentrator의 반대이다. 예를 들어 1:4 distributor는 하나의 고속 channel에서 받은 트래픽을 여러 개의 저속 channel로 분산한다.

겉보기에는 distributor가 concentrator를 반대로 사용한 것처럼 보이지만, 기능은 다르다. concentrator를 통해 reverse 방향으로 이동하는 packet은 특정 terminal로 도달해야 한다. 반면 distributor는 packet을 어떤 network channel로 보낼지 자유롭게 정할 수 있다. 분산 방식은 random, round-robin, 또는 load balancing일 수 있다. 경우에 따라, 같은 class에 속한 packet은 항상 동일한 channel로 보내서 순서를 유지할 수도 있다.

Distributor는 다양한 상황에서 사용된다. 예를 들어 고속 processor나 고속 line card와 같은 고 bandwidth module을 저속의 network에 연결할 때, 여러 network port를 통해 분산시켜 사용된다. 또는 fault tolerance를 위해 distributor를 사용하는 경우도 있다. 전체 트래픽을 두 개의 half-speed channel로 분산시키면, 한 channel이 고장나더라도 network 성능은 절반으로 줄어드는 정도로 gracefully degrade된다.

Distributors는 channel의 bandwidth가 router가 처리하기에 너무 높은 경우에도 사용된다. 예를 들어, 클럭 주파수가 500MHz (2ns 주기)이고, packet이 8바이트이며 router가 4 클럭마다 1개 packet만 처리할 수 있다고 하자. 이 경우 해당 router가 처리할 수 있는 최대 bandwidth는 8바이트/8ns, 즉 1GByte/s이다. 만약 4GByte/s port를 network에 연결하고자 한다면, 1:4 distributor를 사용하여 이 트래픽을 router가 감당할 수 있는 낮은 bandwidth channel로 나눠야 한다. 이렇게 낮은 bandwidth channel로 나눈 후에는 여러 포트를 가진 단일 network에 삽입하거나, 병렬 network에 삽입할 수 있다. (이것은 channel slicing이라 불리며, Section 7.2.3에서 설명한다.)

하지만 network에 distributor를 추가하면 성능에 두 가지 측면에서 악영향을 미친다.
첫째, serialization latency가 증가한다. packet의 serialization latency는 병목이 되는 링크에서 L/b로 주어지며, 여기서 b는 bandwidth이다. 따라서 terminal 링크의 bandwidth가 bT, network channel의 bandwidth가 bN일 때 distributor는 latency를 bT/bN만큼 증가시킨다. serialization latency에 비례하는 queueing delay도 그만큼 늘어난다.

둘째, distributor는 load balance를 감소시킨다. distributor의 출력 채널 간 부하 분산은 완벽하지 않으며, 병렬 network에 분산된 경우 어느 시점에서는 하나의 링크가 과부하되고 다른 링크는 유휴 상태일 수 있다. 일반적으로 성능 관점에서는 자원을 공유하는 것이 더 낫다. 즉, distribution은 성능을 저해하지만, 구현 용이성이나 fault tolerance 측면에서는 도움이 된다.

7.2 Slicing and Dicing

가끔 network node가 하나의 module (chip 또는 board)에 모두 담기지 않는 경우가 있다. 이는 대부분 핀 수 제한 때문이지만, 면적 (특히 memory) 문제일 수도 있다. 이런 경우 router를 여러 개 chip에 나눠야 하며, 이를 slicing이라 한다. slicing에는 세 가지 방법이 있다: bit slicing, dimension slicing, channel slicing.

7.2.1 Bit Slicing

가장 단순한 slicing 방법은 bit slicing이다. 각 channel이 w비트일 때, node를 m개의 chip으로 나누려면 각 chip에 w/m비트씩 배치하면 된다. 예를 들어, Figure 7.4에서는 w=8비트인 2D node를 두 개의 4비트 module로 나눈다. 각 방향에 대한 channel은 4비트씩 분할되고, 몇 개의 제어선 (ctl)은 두 router bit slice 간 정보를 전달하는 데 사용된다.

Bit slicing의 어려움은 control 분산과 fault recovery에 있다. 하나의 flit은 반은 node[0:3], 나머지 반은 node[4:7]로 도착하지만, flit 전체는 하나의 단위로 스위칭되어야 한다. 이를 위해 두 slice는 완전하고 동일한 control 정보를 가져야 한다.

가장 큰 문제는 header 정보의 분산이다. 경로, 목적지, virtual channel 등을 포함하는 header bit를 두 slice로 모두 전달해야 한다. 이 경우 control 채널을 통해 모든 header bit가 전달되어야 하며, 이는 pin overhead와 latency overhead를 야기한다. 작은 flit에서는 header 비트가 전체 flit의 25% 이상을 차지할 수 있다. header 전송은 일반적으로 두 개의 클럭을 latency로 추가한다.

Pin bandwidth overhead를 줄이기 위해, control은 한 slice에서만 수행하고 결정된 control 신호만 다른 slice에 전달할 수도 있다. 그러나 이 방법도 latency는 줄일 수 없다.

또한, CRC와 같은 오류 검출 기능을 모든 slice에서 나눠 수행해야 하므로 slice 간 중간 결과를 교환해야 한다. transient fault로 인해 두 slice 간 control state가 불일치할 경우, robust한 sliced router는 state를 항상 동기화하고 복구할 수 있어야 한다.

이런 복잡성에도 불구하고, flit이 큰 router에서는 overhead를 감당할 수 있어 bit slicing이 효과적이다. 특히 flit-reservation flow control 같은 방식에서는 control이 data보다 먼저 pipeline으로 전달되므로 유리하다.

7.2.2 Dimension Slicing

Bit slicing에서의 control 및 error 처리 복잡성을 피하기 위해, flit 전체를 한 slice에 유지하는 slicing 방법이 dimension slicing이다. router의 port 단위로 slicing을 하며, 각 port는 하나의 slice에 완전하게 포함된다. 이로 인해 degree가 d인 network node는 degree가 (d/m + p)인 m개의 node로 나뉘며, p는 slice 간 통신을 위한 포트 수이다.

예를 들어, Figure 7.5는 w=8-bit의 2D router를 두 개의 1D router로 나눈 것이다. 하나는 north-south 트래픽, 다른 하나는 east-west 트래픽을 담당한다. 더 세분화가 필요하면, 각 방향별로 별도의 1D unidirectional router로 나눌 수 있다.

이 두 router 간의 channel은 방향 전환 트래픽을 모두 수용할 수 있는 bandwidth를 가져야 한다. 방향 전환량은 routing algorithm에 따라 크게 달라진다. 예를 들어 dimension-ordered routing은 방향 전환을 피하므로 필요한 bandwidth가 적다.

7.2.3 Channel Slicing

앞선 두 방식은 partition 간 통신이 필요하다. bit slicing은 control 정보를, dimension slicing은 데이터 경로를 교환해야 한다. 반면, channel slicing은 이 모든 통신을 제거하고 network 전체를 완전히 독립적인 두 개의 네트워크로 나눈다. 유일한 연결은 terminal에서 distributor를 통해 트래픽을 나누고 목적지에서 다시 결합하는 부분뿐이다.

Figure 7.6은 channel slicing을 보여준다. w=8bit의 2D network node는 w=4bit의 두 개의 node로 완전히 분리된다. 두 network 간에는 어떠한 연결도 없으며, terminal 링크 (그림에는 표시되지 않음)만 연결된다.

7.3 Slicing Multistage Networks

Multistage network에서 slicing을 적용하면 **serialization latency (Ts)**와 head latency (Th) 간의 trade-off를 조절할 수 있다. 이는 네트워크 전체 latency를 두 구성 요소의 균형을 맞춰 최적화하는 방식이다. 이 기법은 5.2.2절에서 torus의 차원을 조정하여 Ts와 Th의 균형을 맞추는 것과 유사하다.

Multistage network에 channel slicing을 적용하면 routing component 수와 총 pin 수를 줄여서 전체 비용을 낮출 수 있다.

예를 들어, N = kⁿ개의 노드를 갖는 k-ary n-fly 구조에서, channel 너비가 w일 경우, 이를 x개의 xk-ary n′-fly 네트워크로 분할할 수 있으며, 각 네트워크의 channel 너비는 w/x가 된다.

Figure 7.7에서는 2비트 channel을 갖는 binary 2-fly network를, 직렬 전송(1비트 channel)의 4-ary 1-fly 두 개로 대체하여 비용과 diameter를 줄이는 예시를 보여준다. 두 방식 모두 같은 bandwidth를 제공하며, switch당 동일한 pin 수(8개 signal)를 사용한다. 그러나 channel-sliced 구조는 diameter가 작고 필요한 switch 수도 절반이다.

Slicing을 적용하면 network의 diameter는 기존 n+1에서 n′+1로 줄어들며,
    n′ = n / (1 + logₖx)
가 된다.

따라서 latency는 다음과 같이 주어진다:

• Serialization latency: Ts = xL / b
• Head latency: Th = tᵣ × (n / (1 + logₖx))
      (여기서 tᵣ은 wire delay, L은 message 길이, b는 bandwidth)

예제: N = 4096 노드, binary 12-fly, w = 32, b = 1 Gbit/s, tᵣ = 20ns, L = 256 bit
slicing factor x를 1부터 32까지 늘리며 latency 변화를 보면 다음과 같다:

xkn′wTsThT

1	2	12	32	8 ns	240 ns	248 ns
2	4	6	16	16 ns	120 ns	136 ns
4	8	4	8	32 ns	80 ns	112 ns
8	16	3	4	64 ns	60 ns	124 ns
16	32	3	2	128 ns	60 ns	188 ns
32	64	2	1	256 ns	40 ns	296 ns

Figure 7.8에서는 slicing factor(x)에 따른 전체 latency T와 Ts, Th의 변화를 그래프로 보여준다.
x = 4일 때 Ts와 Th가 균형을 이루며 최소 latency (112 ns)를 얻는다.
x가 더 커지면 Ts의 증가 폭이 Th의 감소 폭보다 커져 전체 latency가 다시 증가하게 된다.
극단적인 경우인 x = 32에서는 직렬 전송만으로 구성된 2-stage, radix-64 네트워크가 되어 Ts = 256ns로 가장 크며, pin 비용은 가장 작다.

이러한 channel slicing 기법은 butterfly network에 설명했지만, Clos network와 Batcher network 같은 다른 multistage network에도 적용 가능하다 (Exercise 7.5 참고). 또한 bit slicing으로도 multistage network를 나눌 수 있다 (Exercise 7.6 참고).

7.4 사례 연구: Tiny Tera에서의 Bit Slicing

Tiny Tera는 Stanford University에서 설계되고 Abrizio에서 상용화된 고속 packet switch이다. 이름처럼, 전체 aggregate bandwidth는 1Tbit/s이다. Figure 7.9는 Tiny Tera의 고수준 구조를 보여준다.

• 32×32, 8비트-wide crossbar를 중심으로 구성된다.
• 각 port card는 crossbar와 외부 네트워크 간의 input/output buffering을 제공한다.
• 중앙 scheduler는 crossbar 구성(config)을 계산하고 각 port card에 전달한다.

Scheduler가 계산한 구성 정보는 각 packet에 붙어서 crossbar로 전달된다.

Crossbar 구현의 어려움은 pin 수에서 나타난다.

• 각 포트는 송수신 16 Gbit/s를 다루며, 이는 16개 signal, 즉 32개 pin을 필요로 한다.
• 포트가 32개이므로 총 1024개의 고속 핀이 필요하다.
  (power/ground pin, 전력 소모까지 고려하면 이보다 훨씬 부담됨)

그래서 Tiny Tera의 설계자는 bit slicing을 선택했다.

Figure 7.10에 보이듯이,

• crossbar는 8개의 32×32 1비트-wide crossbar로 나뉘어 구성되었다.
• 이렇게 하면 chip당 128개 고속 pin으로 핀 수를 줄일 수 있고, 전력 소모도 각 chip에 분산된다.
• input/output queue도 bit 단위로 slicing 되어 여러 개의 SRAM에 나뉘어 저장된다.
  (그림에는 생략)

이러한 sliced 설계는 패키징 이슈를 줄일 뿐 아니라 유연성도 향상시킨다.
예를 들어, 필요한 경우 crossbar slice를 더 추가할 수 있다.

Figure 7.10 설명

Tiny Tera crossbar의 bit slicing 구현. 8비트 인터페이스는 8개의 slice로 분할되며, crossbar chip당 128개의 데이터 핀만 필요하다. 각 slice는 1비트 폭의 32×32 crossbar로 구성된다.

이러한 구조는 속도를 부분적으로 향상시키거나, 신뢰성을 높이기 위해 crossbar slice를 추가할 수 있다. 만약 단일 crossbar chip을 사용했다면, 속도 향상이나 redundancy 확보를 위해서는 전체 crossbar를 또 하나 추가해야 했을 것이다.

7.5 참고 문헌 노트

Slicing, concentration, distribution은 오래전부터 사용되어 왔다. 전화망에서는 대부분의 전화기가 사용되지 않고 있다는 점을 고려해 concentration이 오래전부터 활용되었다.

• J-Machine router는 dimension slicing이 적용되었으며, 세 개의 slice가 단일 chip에 탑재되었다 (5.5절 참고).
• Cray T3D는 각 slice를 개별 ECL gate array에 배치하는 유사한 구조를 사용했다.
• MARS accelerator와 Tiny Tera (7.4절 참조)는 bit sliced crossbar를 사용했다.
• Avici TSR는 6개의 4비트 slice로 구성된 bit sliced 3D torus를 사용했다.

7.6 연습문제

7.1 Torus에서의 concentration
4096개의 노드를 연결해야 하며, 각 노드는 peak bandwidth가 10 Gbit/s, 평균 500 Mbit/s를 가진다. bisection bandwidth는 2.56 Tbit/s로 고정된 torus network에서, concentrator, 차원 수, radix 측면에서 다양한 topology를 비교하라. 모든 concentrator와 router node는 별도의 chip에 패키징되며 chip당 최대 100 Gbit/s의 pin bandwidth를 가진다.

• 가장 낮은 pin bandwidth를 제공하는 topology는 무엇인가?
• serialization latency를 증가시키지 않고도 가장 낮은 pin bandwidth를 제공하는 topology는 무엇인가?

7.2 Line card에서의 traffic distribution
64개의 40 Gbit/s line card를, 10 Gbit/s를 초과하지 않는 channel로 구성된 torus network에 연결하려 한다. 모든 노드가 bisection을 통과하여 트래픽을 전송하는 worst-case traffic을 지원해야 한다.

• distributor를 사용해 어떻게 연결할 수 있을까?
• 채널 속도가 40 Gbit/s인 경우와 비교해 bisection bandwidth는 어떻게 달라질까?

7.3 Butterfly slicing
Radix-4 butterfly node (w=2비트 channel)를 두 개의 module로 나누는 세 가지 slicing 방식 (bit, dimension(port), channel)을 고려하라.

• flit 크기는 64비트, 이 중 16비트는 header이다.
• 각 분할 방식을 스케치하고 channel width 및 chip당 필요한 signal 수를 표시하라.
• 각 경우의 latency 특성을 정성적으로 비교하라.

7.4 Sub-signal slicing
channel slicing factor를 채널이 1 signal보다 좁아지도록 설정할 수도 있다. 예를 들어, slicing 결과가 0.5 signal이면, 두 채널이 하나의 물리적 signal을 공유하게 된다.

• 이런 수준의 slicing이 zero-load latency를 줄이는 데 도움이 될 수 있을까?

7.5 Clos network의 channel slicing
N = 256인 rearrangeable Clos network (m = n)에서, switch는 32 signals, 각 노드는 8 Gbit/s bandwidth 필요, L = 128, tᵣ = 20 ns, f = 1 Gbit/s일 때,

• latency를 최소화하는 slicing factor x를 구하라.

7.6 Butterfly network의 bit slicing
Table 7.1 첫 번째 row의 network 조건에 기반한 4096 node butterfly network에서,

• zero-load latency를 최소화하는 bit slicing을 구하라.
• 각 bit slice마다 32-bit header가 반복되며, slice 간 control signal은 필요 없다.
• router latency tᵣ는 전체 header 수신 이후부터 적용된다.

7.7 Tiny Tera의 header 분배
Tiny Tera의 bit sliced switch에서 crossbar 구성은 centralized scheduler에 의해 계산된 뒤 input port로 분배된다. 각 packet slice에는 해당 header 정보가 덧붙는다.

• 포트 A를 기준으로, A에서 전송되는 packet은 목적지가 아니라 A로 전송한 포트의 주소를 담고 있다.
• 왜 이런 방식이 더 효율적인 encoding이 되는가?
  힌트: Tiny Tera는 multicast 트래픽을 지원한다.

지금까지는 packet-switched 네트워크에 초점을 맞추었지만, 이 장에서는 circuit-switched 네트워크로 관심을 전환한다. circuit-switched 네트워크에서는 특정 source와 destination 간의 연결을 먼저 설정한 다음, 데이터가 해당 연결을 통해 연속적으로 흐르도록 유지하고, 이후 연결을 해제한다.

역사적으로 non-blocking, circuit-switched 네트워크는 전화 시스템과 처음 연관되었다. 한 사람이 다른 사람에게 전화를 걸면 단일 연결 요청을 의미한다. 전화가 연결되기 위해서는 네트워크 내에서 사용되지 않은 경로를 찾아 해당 경로를 그 통화에 할당해야 했다. 만약 전화 시스템이 non-blocking이었다면, 수신자의 전화기가 사용 중이지만 않다면 항상 통화 연결이 성공했을 것이다.

좀 더 정확하게 말하면, 네트워크가 non-blocking이라는 것은 입력과 출력의 임의의 순열(permutation)에 대해 모든 회로 요청을 처리할 수 있다는 의미다. 즉, 각 입력에서 선택된 출력까지의 전용 경로가 충돌(shared channel) 없이 형성될 수 있다. 반대로, 네트워크가 blocking이라면 이러한 모든 회로 요청을 충돌 없이 처리할 수 없다.

이 장에서는 두 가지 유형의 non-blocking 네트워크를 살펴본다. 먼저, 네트워크가 strictly non-blocking이라는 것은 이미 설정된 회로들을 재배치(reroute 또는 rearrange)하지 않고도 순차적으로 회로를 하나씩 설정하여 어떤 permutation이든 구성할 수 있다는 의미다. 즉, 아직 사용되지 않은 입력을 아직 사용되지 않은 출력에 연결하더라도 기존 트래픽의 경로에 영향을 주지 않으면 strictly non-blocking이다.

반면, 네트워크가 rearrangeably non-blocking(또는 간단히 rearrangeable)이라는 것은 임의의 permutation에 대해 회로를 설정할 수는 있지만, 이후에 설정되는 회로들을 위해 먼저 설정된 회로들을 재배열해야 할 수도 있음을 의미한다. rearrangeable 네트워크는 어떤 미연결된 입력과 출력이라도 연결할 수 있지만, 그 연결을 위해 다른 트래픽을 우회시켜야 할 수 있다.

위 정의들은 모두 각 입력이 최대 한 개의 출력에만 연결되는 unicast 트래픽에 해당된다. 또한 한 입력이 여러 출력으로 퍼지는 multicast 트래픽도 고려한다. multicast 트래픽에 대해 네트워크가 strictly non-blocking이라는 것은 다른 트래픽에 영향을 주지 않고 어떤 미연결 출력이라도 어떤 입력(연결 여부 무관)과 연결할 수 있다는 의미다. 또한 rearrangeable한 multicast 네트워크는 어떤 미연결 출력이라도 어떤 입력과 연결할 수 있으나, 그 연결을 위해 다른 트래픽을 우회시켜야 할 수 있다.

Crossbar 스위치와 expansion이 2:1인 Clos 네트워크는 unicast 트래픽에 대해 strictly non-blocking 네트워크의 예시다. Crossbar 스위치와 더 큰 expansion을 가진 Clos 네트워크는 multicast 트래픽에 대해서도 strictly non-blocking하다. Beneš 네트워크와 expansion이 없는 Clos 네트워크는 unicast 트래픽에 대해 rearrangeable한 네트워크의 예시다.

6.1 Non-Blocking vs. Non-Interfering 네트워크

packet switching 응용에서는 non-blocking 네트워크의 개념은 대체로 무의미하거나 과도한 개념이다. packet switch는 연결 또는 세션 동안 회로를 고정하지 않기 때문에, 채널을 공유하더라도 두 가지 제약조건만 충족하면 간섭 없이 트래픽을 공유할 수 있다.

첫 번째는 채널 load γmax가 채널 대역폭보다 작아야 한다는 대역폭 제약이다. 두 번째는 buffer와 채널 대역폭 같은 자원을 할당할 때, 하나의 흐름이 다른 흐름의 서비스를 일정 시간 이상 방해하지 않도록 자원 할당이 이뤄져야 한다. 이러한 자원 할당 제약은 12장에서 설명하는 적절한 flow control 메커니즘을 통해 달성할 수 있다.

이러한 조건을 만족하는 packet-switched 네트워크를 non-interfering 네트워크라고 부른다. 이러한 네트워크는 임의의 packet 트래픽을 처리할 수 있으며, 패킷 지연에 대한 보장된 상한이 있다. 트래픽은 어떤 채널의 대역폭 용량도 초과하지 않으며, 흐름 간 자원 할당이 상호 간섭을 일으키지 않는다.

오늘날 대부분의 응용에서 사람들이 non-blocking 네트워크를 원한다고 말할 때, 실제로 필요한 것은 이런 non-interfering 네트워크이며, 이는 훨씬 적은 비용으로 실현할 수 있다. 그러나 역사적 이유와 진정한 non-blocking이 필요한 경우(예: 회로 전환을 지원해야 할 경우)를 위해, 이 장의 나머지 부분에서는 non-blocking 네트워크에 대해 간략히 살펴본다.

항목                                              non-blocking                                       non-interfering

6.2 Crossbar 네트워크

n × m crossbar 또는 crosspoint switch는 중간 단계 없이 n개의 입력을 m개의 출력에 직접 연결한다. 본질적으로 이러한 스위치는 m개의 n:1 multiplexer로 구성된다.

대부분의 crossbar 네트워크는 정사각형 형태(n = m)이지만, m > n 또는 m < n인 직사각형 형태도 있다.

 그림 6.1은 4×5 crossbar의 개념적 모델을 보여준다. 입력선 4개와 출력선 5개가 있으며, 입력선과 출력선이 교차하는 지점마다 입력선을 출력선에 선택적으로 연결하는 switch, 즉 crosspoint가 존재한다. 올바른 동작을 위해서는 각 출력이 최대 하나의 입력과만 연결되어야 한다. 그러나 입력은 여러 출력에 연결될 수 있다. 예를 들어, 그림 6.1에서는 입력 1이 출력 0과 3에 연결되어 있다.

한때 전화망 대부분은 그림 6.1과 같은 구조의 기계 릴레이로 구성된 crossbar switch를 사용하여 구현되었다. 이런 switch 기반 crossbar에서는 입력과 출력의 구분이 실질적으로 없으며, switch가 만들어내는 연결은 양방향이다.

그러나 현재 대부분의 crossbar는 디지털 로직으로 구현되며, 그림 6.2와 같은 구조를 가진다. 각 입력선은 m개의 n:1 multiplexer 중 하나의 입력으로 연결되고, multiplexer의 출력이 m개의 출력 포트를 구동한다. 이 multiplexer는 tri-state gate나 wired-OR gate로 구성될 수 있으며, 그림 6.1의 구조를 모방하거나 전통적인 로직 게이트 트리로 구성될 수 있다.

crossbar switch를 시스템 내에 그릴 때마다 전체 회로도를 그리지 않기 위해, 그림 6.3과 같은 crossbar 기호를 사용한다. 문맥상 상자 모양이 crossbar switch임이 명확할 경우에는 'X' 기호를 생략하고 단순한 입력과 출력이 있는 박스로 나타낸다.

crossbar switch는 unicast와 multicast 트래픽 모두에 대해 명백히 strictly non-blocking이다. 연결되지 않은 어떤 출력이라도 입력과 연결하기 위해 단순히 해당 입력과 출력 사이의 switch를 닫거나 multiplexer 설정을 조정하면 되기 때문이다. 많은 다른 네트워크들이 이러한 속성을 얻기 위해 복잡한 노력을 해야 하지만, crossbar는 이 특성을 매우 쉽게 만족시킨다.

그렇다면 crossbar가 간단히 non-blocking 특성을 갖는다면 왜 다른 non-blocking 네트워크를 고민해야 할까? 그 이유는 비용과 확장성 때문이다. 작은 규모에서는 경제적이지만, n×n 정사각형 crossbar의 비용은 n²에 비례하여 증가한다. n이 커질수록, crossbar의 비용은 n log n에 비례하는 네트워크들에 비해 빠르게 증가하여 부담이 된다.

crossbar의 제곱 비용은 switch 자체의 구조와 여러 개의 작은 crossbar를 결합해 더 큰 crossbar를 구성할 때도 명확하게 드러난다. 그림 6.1과 6.2에서 볼 수 있듯이, 입력과 출력선의 그리드를 구성하는 데 n²의 면적이 필요하고, n²개의 crosspoint를 포함하기 위해 n²의 면적이 필요하며, n개의 multiplexer 각각이 n에 비례하는 면적을 차지하므로 총 n²의 면적이 요구된다.

그림 6.4에 보이듯이, 작은 crossbar를 사용해 큰 crossbar를 만들 때도 비용은 제곱적으로 증가한다. 2n×2n crossbar는 2×2 배열의 n×n crossbar 네 개로 구성할 수 있으며, 고속 신호를 지점 간으로 분배하기 위해 입력에 1:2 distributor가 필요하고, 출력에서는 2:1 multiplexer가 각 출력에 보낼 신호를 선택해야 한다. 일반적으로, jn×jn crossbar는 j×j 배열의 j²개의 n×n crossbar와 함께 n개의 1:j distributor 및 j:1 multiplexer로 구성할 수 있다.

현실적인 crossbar의 비용은 어떻게 패키징되는지에 따라 크게 달라진다. 시스템의 다른 구성 요소가 전혀 없는 단일 칩 안에 완전히 패키징된 crossbar는 pin 수(Wn)에 의해 크기가 제한되며, 칩에 crossbar를 구현하는 데 필요한 면적보다 pin 수가 더 중요한 제약이 된다. 이 경우 crossbar의 비용은 칩에 담을 수 있는 최대 크기까지는 선형적으로 증가한다. 그러나 crossbar가 칩에 들어가면서 다른 구성 요소들과 연결되어야 할 경우, 면적 제한이 중요해지며 이때는 제곱 비용이 문제가 된다. crossbar가 여러 칩에 걸쳐 구현되어야 할 경우(그림 6.4처럼), 크기에 따라 비용은 제곱적으로 증가한다.

6.3 Clos 네트워크

6.3.1 Clos 네트워크의 구조와 특성

Clos 네트워크는 세 개의 단계(stage)로 구성된 네트워크이며, 각 단계는 여러 개의 crossbar switch로 구성된다. 대칭 Clos 네트워크는 (m, n, r)의 세 개 숫자로 표현된다. 여기서 m은 중간 단계 switch의 수, n은 각 입력/출력 switch의 포트 수, r은 입력 및 출력 switch의 수를 의미한다.

Clos 네트워크에서 각 중간 단계 switch는 모든 입력 switch로부터 입력 링크를 하나씩 받고, 모든 출력 switch로 출력 링크를 하나씩 보낸다. 즉, r개의 입력 switch는 각각 n×m crossbar로, n개의 입력 포트를 m개의 중간 switch에 연결하며, m개의 중간 switch는 각각 r×r crossbar로, r개의 입력 switch를 r개의 출력 switch에 연결한다. 그리고 r개의 출력 switch는 각각 m×n crossbar로, m개의 중간 switch를 n개의 출력 포트에 연결한다. 예를 들어, (3,3,4) Clos 네트워크는 그림 6.5에, (5,3,4) Clos 네트워크는 그림 6.6에 나타나 있다. Clos 네트워크에서 입력과 출력 포트를 참조할 때는 switch 번호 s와 포트 번호 p를 사용해 s.p로 표기한다.

Clos 네트워크의 각 단계를 모두 연결하는 all-to-all 연결을 3차원 시각화로 표현하면(그림 6.7), 입력 및 출력 switch가 수평 방향으로 트래픽을 보내고 받고, 중간 switch는 수직 방향으로 트래픽을 전달하는 형태로 볼 수 있다. 이와 같은 교차 배열 구조는 소형 Clos 네트워크의 패키징에도 유용하며, 단계 간의 연결을 짧게 유지할 수 있게 한다.

(m, n, r) Clos 네트워크의 특성은 이 topology로부터 유도된다. Clos 네트워크는 세 단계로 구성되므로 hop 수 H = 4이다. 이 네트워크는 그림 6.7과 같이 수평 또는 수직으로 이등분할 수 있다. 중간 switch를 가로로 가르는 절단(bisection)의 경우 bisection bandwidth BC = mr이며, 입력과 출력 switch를 세로로 가르는 경우 BC = 2nr = 2N이다. 실제로는 대부분의 네트워크가 입력과 출력 switch를 함께 배치하고 switch 간의 모든 연결선을 절단한다.

그림 6.5
(m = 3, n = 3, r = 4)인 대칭 Clos 네트워크는 r = 4개의 n×m 입력 스위치, m = 3개의 r×r 중간 스위치, r = 4개의 m×n 출력 스위치로 구성된다. 모든 스위치는 crossbar이다.

그림 6.6
(5,3,4) Clos 네트워크. 이 네트워크는 unicast 트래픽에 대해 strictly non-blocking하다.

그림 6.7

Clos 네트워크의 각 단계 간 all-to-all 연결은 네트워크를 3차원으로 그리면 더 잘 이해할 수 있다. 입력 스위치는 수평 방향으로 트래픽을 이동시켜 중간 스위치를 선택하고, 중간 스위치는 수직 방향으로 트래픽을 이동시켜 출력 스위치를 선택하며, 출력 스위치는 다시 수평 방향으로 트래픽을 이동시켜 최종 출력 포트를 선택한다.

입력 및 출력 스위치의 degree는 δio = n + m이고, 중간 스위치의 degree는 δm = 2r이다.

Clos 네트워크의 가장 흥미로운 특성은 경로 다양성(path diversity)이며, 이 특성으로 인해 non-blocking 성질이 발생한다. m개의 중간 스위치를 가진 Clos 네트워크에서는 입력 a에서 출력 b까지 총 |Rab| = m개의 경로가 있으며, 각각은 서로 다른 중간 스위치를 경유한다.

Clos 네트워크에서 회로를 라우팅할 때 자유롭게 선택 가능한 유일한 지점은 입력 스위치이다. 여기서 사용 가능한 중간 스위치 중 하나를 선택할 수 있다. 중간 스위치는 출력 스위치로 가는 단일 링크만 선택해야 하며, 이 링크가 사용 중이면 해당 경로는 불가능하다. 마찬가지로 출력 스위치도 선택된 출력 포트를 선택해야 한다. 따라서 Clos 네트워크에서 라우팅 문제는 각 회로(또는 패킷)를 어느 중간 스위치에 할당할지를 결정하는 문제로 환원된다.

6.3.2 Unicast 라우팅 (Strictly Non-Blocking Clos 네트워크)

정리 6.1
Clos 네트워크는 m ≥ 2n − 1일 때, unicast 트래픽에 대해 strictly non-blocking이다.

증명
N − 1개의 통화가 설정되어 있고, 입력 a.i와 출력 b.j만 연결되지 않은 상황을 가정한다. 이전의 통화들은 입력 스위치 a와 출력 스위치 b에서 사용된 중간 스위치들이 서로 겹치지 않도록 설정되었다. 예를 들어, 스위치 a는 처음 n−1개의 중간 스위치를 사용하고, 스위치 b는 마지막 n−1개의 중간 스위치를 사용했다고 가정하자. a.i를 b.j에 연결하려면, a와 b 둘 다 사용하지 않은 중간 스위치가 최소한 하나는 존재해야 한다. 따라서 총 중간 스위치는 최소 2n − 1개가 필요하다.

예를 들어, 그림 6.6의 (5,3,4) Clos 네트워크는 m = 5 = 2n − 1 이므로 strictly non-blocking이다. 반면, 그림 6.5의 (3,3,4) 네트워크는 m = 3 < 5 이므로 strictly non-blocking하지 않다. 이 네트워크는 뒤의 6.3.3절에서 rearrangeable임을 보게 된다.

strictly non-blocking Clos 네트워크에서 unicast 통화를 라우팅하는 알고리즘은 그림 6.8과 같다. a.i에서 b.j로 unicast 통화를 라우팅할 때는, 입력 스위치 a와 출력 스위치 b가 사용하지 않은 중간 스위치들의 리스트를 교차하여 공통의 사용 가능한 중간 스위치를 선택하면 된다. 앞의 증명에서 본 바와 같이, 항상 최소 하나의 중간 스위치가 존재한다.

예를 들어, 입력 1.1 (1)에서 출력 3.3 (9)로 회선을 라우팅하는 경우를 보자 (그림 6.9). 입력 스위치 1은 이미 1.2 (2) → 4.1 (10) 및 1.3 (3) → 2.3 (6) 회선으로 인해 중간 스위치 1과 2 경로를 사용 중이다 (점선으로 표시). 한편, 출력 스위치 3도 3.1 (7)과 2.1 (4)에서 온 회선으로 인해 중간 스위치 4와 5 경로를 사용 중이다. 입력 및 출력 스위치는 각각 최대 n−1 = 2개의 중간 스위치만 차단할 수 있으므로, 최대 2n − 2 = 4개의 중간 스위치가 사용 중일 수 있다. m = 5 = 2n − 1이므로 항상 하나의 중간 스위치는 사용 가능하다. 이 경우, 중간 스위치 3이 사용 가능하여 굵은 선으로 나타난 경로를 통해 새로운 통화를 처리할 수 있다.

좀 더 포괄적인 라우팅 예제로, permutation {5, 7, 11, 6, 12, 1, 8, 10, 3, 2, 9, 4}를 고려하자. 즉, 입력 1 (1.1)은 출력 5 (2.2)로, 입력 2 (1.2)는 출력 7 (3.1)로, 등등으로 매핑된다. 이를 단순화하면 switch 단위 permutation {(2, 3, 4), (2, 4, 1), (3, 4, 1), (1, 3, 2)}가 된다. 중간 스위치 할당을 결정할 때는 switch만 고려하면 되고, 중간 스위치가 결정되면 입력과 출력 switch의 crossbar 설정은 non-blocking이므로 간단히 처리된다.

통화는 {9,6,7,8,3,12,10,5,1,11,2,4} 순서로 처리된다고 하자. 첫 번째 통화는 입력 9 (3.3)에서 출력 3 (1.3)으로 연결되고, 그 다음은 6 (2.2) → 1 (4.3) 순으로 진행된다.

그림 6.8
strictly non-blocking Clos 네트워크에서 unicast 통화를 라우팅하는 알고리즘:

For each call (a,b)
    freeab = free(a) ∧ free(b)     // a와 b 모두에서 사용 가능한 middle switch 목록
    middle = select(freeab)        // 그 중 하나 선택
    assign((a,b), middle)          // 라우팅 설정​

※ 이 증명 기법은 비둘기집 원리(pigeonhole principle)로, 다양한 스케줄링 문제에 유용하게 사용된다.

그림 6.9
(5,3,4) Clos 네트워크에서 입력 1.1 → 출력 3.3으로 라우팅. 입력 스위치 1은 중간 스위치 1과 2로의 경로가 이미 점유되어 있으며, 출력 스위치 3은 중간 스위치 4와 5로의 경로가 점유되어 있다. 유일하게 사용 가능한 경로는 중간 스위치 3을 경유하는 경로이며, 이는 굵은 선으로 표시된다.

표 6.1
Strictly non-blocking Clos 네트워크에서 call set {(2, 3, 4), (2, 4, 1), (3, 4, 1), (1, 3, 2)}를 {9,6,7,8,3,12,10,5,1,11,2,4} 순서로 라우팅한 예이다. 각 행은 하나의 call 설정을 나타낸다. 열에는 입력(In), 출력(Out), 중간 스위치(Middle), 그리고 각 입력 및 출력 스위치의 free 벡터가 표시되어 있다.

이러한 bit-vector 표현을 이용하면, 입력 스위치 a에서 출력 스위치 b로 새로운 call을 설정할 때 다음과 같이 처리한다. 입력 스위치 a의 free 벡터와 출력 스위치 b의 free 벡터를 AND 연산하여, 두 스위치에서 모두 사용 가능한 중간 스위치를 나타내는 벡터를 얻는다. 각 free 벡터는 최대 두 개의 0을 가질 수 있으므로, AND 결과에는 최대 4개의 0만 있고, 최소 하나의 1이 반드시 존재한다. 이 1 중 하나를 선택하여 새로운 call에 사용할 중간 스위치를 결정한다.

예를 들어, 표 6.1의 마지막 call은 입력 4 (2.1) → 출력 4 (2.1)로 연결된다. 이 call 이전에 입력 스위치 2의 free 벡터는 10101 (2번, 4번 중간 스위치 사용 중), 출력 스위치 2의 free 벡터는 00111 (1번, 2번 중간 스위치 사용 중)이었다. 이를 AND 연산하면 00101이 되어 중간 스위치 3과 5가 사용 가능함을 나타낸다. 여기서 중간 스위치 3이 선택된다.

Strictly non-blocking Clos 네트워크의 라우팅 절차는 매우 단순하다. 그러나 이 단순함에는 비용이 따른다. strictly non-blocking 네트워크는 해당 rearrangeable 네트워크보다 거의 두 배의 비용이 들며, 중간 스위치를 2n−1/n배 더 많이 필요로 한다. 따라서 대부분의 응용에서는 rearrangeable 네트워크가 선호된다.

6.3.3 Rearrangeable Clos 네트워크에서의 Unicast 라우팅

정리 6.2
m ≥ n인 Clos 네트워크는 rearrangeable하다.

Clos 네트워크 라우팅에 대한 이해를 돕기 위해, 회선 집합을 **이분 그래프(bipartite graph)**로 표현한다. 입력 스위치 집합과 출력 스위치 집합이 각기 그래프의 정점 집합을 이루며, 각 call은 그 사이의 간선으로 표현된다. 이때 라우팅 문제는 간선 색칠(edge coloring) 문제로 바뀐다. 각 중간 스위치가 하나의 색으로 간주되며, 동일한 정점에 같은 색이 두 번 이상 연결되지 않도록 각 간선에 색을 할당해야 한다. (즉, 하나의 입력 또는 출력 스위치에서 중간 스위치를 중복 사용하지 않아야 한다.)

예를 들어 Section 6.3.2에서의 회선 집합 {(2,3,4), (2,4,1), (3,4,1), (1,3,2)}를 생각해 보자. 입력 스위치 1은 출력 스위치 2,3,4에 연결되고, 스위치 2는 2,4,1에, 스위치 3은 4,1에, 스위치 4는 3에 연결된다. 이 call 집합을 표현하는 이분 그래프는 그림 6.10과 같다.

그림 6.11에는 rearrangeable non-blocking 네트워크에서 call 집합을 라우팅하는 알고리즘이 제시되어 있다. 이 알고리즘은 입력 스위치 a에서 출력 스위치 b로 call을 라우팅할 때, 우선 a와 b 모두에서 사용 가능한 중간 스위치가 있는지 확인한다. 존재하면 해당 스위치를 선택하여 바로 라우팅한다. 이 과정은 Figure 6.8에 나온 strictly non-blocking 라우팅 절차와 동일하다.

공통의 free 중간 스위치가 없다면, 다음과 같은 절차가 반복적으로 실행된다:

• 입력 스위치 a에서 사용 가능한 중간 스위치 mida를 선택한다.
• 출력 스위치 b에서 해당 mida를 사용하는 call (c,b)이 있다면,
  • 그 call을 midb (출력 b에서 사용 가능한 다른 중간 스위치)로 옮긴다.
  • 만약 midb가 이미 입력 c에서 사용 중이라면, 이 과정을 반복하면서 call (c,d)를 (a,b)로 바꾸어 재귀적으로 이동시킨다.

이 알고리즘의 적용은 Table 6.2에 나타나 있으며, Section 6.3.2에서의 call 순서에 따른 라우팅 결과를 보여준다. 첫 번째로 재배치가 필요한 시점은 8번째 row에서 입력 2 → 출력 4인 call (2,4)를 설정할 때이다. 이 상황은 그림 6.12(a)에 나타나 있으며, 알고리즘은 다음과 같이 작동한다:

• (2,4)는 스위치 mida = 1을 사용해 라우팅을 시도한다.
• 하지만 출력 스위치 4는 이미 1번과 3번 중간 스위치를 사용 중이다.
• 따라서 (1,4) call을 midb = 2로 옮기고, (2,4)는 mida = 1로 설정된다. 그림 6.12(b) 참조.

더 복잡한 rearrangement는 11번째 row에서 (4,3) call을 설정할 때 발생한다. 이 시점은 그림 6.13(a)에 나타나 있으며, 중간 스위치 충돌로 인해 여러 call들이 연쇄적으로 재배치된다. 이 chain은 다음과 같다: (I3,O3), (I3,O1), (I2,O1), (I2,O4), (I1,O4). 각 call은 mida와 midb를 교대로 사용하면서 반복적으로 위치를 바꾼다. 그림 6.13(d)는 모든 재배치가 끝난 후의 상태를 보여준다.

표 6.2
call 집합을 rearrangeable Clos 네트워크에 라우팅한 결과. 열에는 새로 설정된 call, 이전 call, 중간 스위치(Middle), 각 입력 및 출력 스위치의 free 벡터가 포함된다.

정리 6.3
Looping 알고리즘으로 하나의 call을 설정할 때, 최대 2r − 2개의 다른 call을 재배치하게 된다.

증명
이 알고리즘은 이분 그래프 내 동일 정점을 두 번 방문하지 않기 때문에, 최대 2r개의 정점을 방문한 후 반복을 종료한다. 세 번째 정점부터 call 재배치가 시작되므로, 최대 2r − 2개의 call이 재배치된다.

이 알고리즘의 경로가 **비순환(acyclic)**임을 확인하기 위해 그림 6.14에서 conflict chain을 펼쳐본다. a₁, b₁은 첫 iteration의 입력 및 출력 스위치를 나타내며, 이후 iteration에서는 호출을 mida와 midb 사이로 반복적으로 이동시킨다.

그림 6.12
Figure 6.10의 call set을 라우팅하는 각 단계를 보여준다. 중간 스테이지에 대한 할당은 간선의 점선으로 표시된다.
(a) (I2, O4)를 라우팅하기 전에는 I2와 O4 모두에서 사용 가능한 중간 스위치가 없다.
(b) (I1, O4)를 중간 스위치 2로 이동시키면, (I2, O4)는 중간 스위치 1을 사용하여 라우팅할 수 있게 된다.

이제 어떤 정점도 다시 방문되지 않는다는 것을 귀납법으로 증명할 수 있다. a₁과 b₁은 각각 입력과 출력 스위치이므로 서로 다르다. i < j일 때 정점 aᵢ와 bᵢ가 서로 다르다고 가정하면, j번째에 방문하는 정점 aⱼ도 이전과 다르다. 이는 bj−1에서 mida 링크를 따라 찾았고, 이 mida는 a₁부터 aⱼ₋₁까지에서 이미 사용되었기 때문이다. 비슷하게 bj는 aj에서 midb 링크를 따라 찾은 것이므로 역시 이전과 겹치지 않는다. 따라서 어떤 정점도 중복 방문하지 않으며, 전체 정점 수가 2r이므로 알고리즘은 최대 2r번의 방문 후 종료되며 최대 2r−2개의 call만 재배치된다. (a₂, b₁)부터 시작하여 rearrangement가 일어난다.

정리 6.2 증명
알고리즘이 rn개의 call을 성공적으로 라우팅하고 종료되었으므로, m ≥ n인 Clos 네트워크는 임의의 unicast 트래픽에 대해 rearrangeable함이 증명된다.

call (a, b)를 설정하기 위해 기존 call (c, d)를 재배치해야 할 경우, 트래픽 손실 없이 call (c, d)를 새로운 경로로 전환하는 것이 바람직하다. 이러한 **무손실 전환(hitless switching)**은 입력, 중간, 출력 스위치를 동기화하여 call (c, d)의 i번째 단위(unit)는 이전 경로로, i+1번째 단위는 새 경로로 전송하도록 하면 실현할 수 있다. 이 단위는 bit, byte, frame 등일 수 있으며, 중요한 것은 전환의 정밀도가 아니라 동기화 여부다.

앞선 예제들은 이분 그래프에서 하나의 노드 쌍 사이에 하나의 간선만 존재하는 경우만 다루었으나, **중복 간선(multigraph)**도 고려해야 한다. 예를 들어, 입력 1.1에서 출력 3.3으로 가는 회로와 입력 1.2에서 출력 3.1로 가는 회로가 동시에 존재한다면, 스위치 관점에서는 I1에서 O3로 가는 두 개의 회선이 존재하게 된다. 이는 I1과 O3 사이에 두 개의 간선이 있는 multigraph가 된다. 다행히도 이러한 복잡성은 알고리즘의 성능에 영향을 주지 않으며, looping 알고리즘은 multigraph에도 잘 작동한다.

6.3.4 행렬 분해를 이용한 Clos 네트워크 라우팅

Rearrangeable Clos 네트워크는 **행렬 분해(matrix decomposition)**를 통해 라우팅할 수도 있다. 라우팅할 call 집합은 입력 스위치 i에서 출력 스위치 j로 가는 call의 수를 xᵢⱼ로 나타낸 요청 행렬 R로 표현된다. 예를 들어 다음과 같은 행렬이 있다고 하자:

이 요청 행렬은 각 행과 열의 합이 1 이하인 양의 행렬들의 합으로 분해될 수 있으며, 각 행렬은 중간 스위치의 하나의 설정에 대응된다. 예컨대 Table 6.2의 라우팅 결과는 다음과 같은 행렬 분해에 해당한다:

여기서 M₁, M₂, M₃는 permutation matrix로, Figure 6.5의 세 중간 스위치 설정에 대응된다. 앞서 언급했듯이, 하나의 입력-출력 스위치 쌍 사이에 여러 회로 요청이 있는 경우도 있으며, 이는 요청 행렬의 원소가 1보다 클 수 있음을 의미한다.

행렬 분해는 unicast, multicast 모두에 사용할 수 있으며, rearrangeable 또는 strictly non-blocking Clos 네트워크 모두에 적용할 수 있다. 구체적인 분해 알고리즘 유도는 독자 연습 문제로 남겨둔다.

6.3.5 Clos 네트워크에서의 Multicast 라우팅

Multicast call 집합 C = {c₁, ..., cₙ}에서 각 multicast call cᵢ = (aᵢ, {bᵢ₁, ..., bᵢf})는 입력 포트 aᵢ에서 f개의 출력 포트로의 연결을 의미한다. 여기서 fanout f는 연결된 출력 포트의 개수다. 각 입력 포트 및 출력 포트는 최대 하나의 call에만 포함되어야 한다. 다시 말해, 스위치 기준으로 표현할 경우 각 입력 및 출력 스위치는 최대 n개의 call에만 포함될 수 있다.

Clos 네트워크에서의 multicast 트래픽 라우팅은 unicast에 비해 더 어렵다. 그 이유는 다음 세 가지다:

1. 더 많은 중간 스위치 필요: 최대 fanout이 f인 multicast call 집합을 라우팅하려면, 식 (6.5)에서 정의된 m(f)개의 중간 스위치가 필요하다.
2. Looping 알고리즘이 적용 불가: fanout이 입력 스위치에서만 발생하는 경우가 아니라면, 중간 스위치에서의 fanout은 conflict graph에 cycle을 유발하여 알고리즘이 실패한다.
3. fanout 위치 선택의 자유도: call이 fanout을 어디서 할지 — 입력 스위치, 중간 스위치, 또는 그 조합 — 를 선택할 수 있다. 이 추가적인 자유도를 잘 활용하는 것이 Clos 네트워크에서 multicast를 효율적으로 라우팅하는 핵심이다.

예를 들어, n = 3, r = 4인 Clos 네트워크에서 다음과 같은 fanout-2 call 집합을 라우팅한다고 하자:

C = {
(1, {1, 2}),
(1, {3, 4}),
(1, {1, 3}),
(2, {1, 4}),
(2, {2, 4}),
(2, {2, 3})
}

여기서도 회선은 포트가 아닌 스위치 번호로만 표현한다.

표 6.3은 이 call 집합의 conflict 벡터 표현을 나타낸다. 이 표는 각 입력 스위치와 출력 스위치에 해당하는 열을 가지며, 행 i는 call cᵢ = (aᵢ, {bᵢ₁, bᵢ₂})에 대해, aᵢ와 bᵢ₁, bᵢ₂ 위치에 1을 표시한다.

표 6.3의 첫 번째 행은 입력 스위치 1과 출력 스위치 1, 2 열에 1이 있는 것으로, call (1, {1, 2})를 나타낸다.

두 call cᵢ와 cⱼ는 그들의 벡터가 같은 열에 1을 공유하지 않을 때만 같은 middle switch를 공유할 수 있다. 다시 말해, cᵢ ∧ cⱼ = 0일 때만 동일한 중간 스테이지에 배치할 수 있다. 표 6.3을 보면, 모든 행 쌍이 non-zero 교집합을 가지므로, 입력 스위치에서 fanout을 수행하지 않는다면 이 여섯 개의 call을 라우팅하기 위해서는 여섯 개의 중간 스테이지 스위치가 필요하다.

입력 스위치에서 fanout을 수행하면, 출력 집합을 여러 middle stage로 분산할 수 있다. k-way 입력 fanout은 call cᵢ = (a, B)를 다음처럼 분할한다:

ci₁ = (a, B₁), ..., ciₖ = (a, Bₖ) 단, B₁ ∪ ... ∪ Bₖ = B 이고 각 Bⱼ는 서로 disjoint.

예를 들어, 표 6.3의 call 집합에서 c₃와 c₆에 대해 입력 fanout을 적용한 결과가 표 6.4에 나타나 있다. 이처럼 call을 분할하면 많은 pairwise conflict가 제거되고, 이 call 집합은 네 개의 middle-stage switch만으로도 라우팅할 수 있다 (표 6.5 및 그림 6.15 참조).

표 6.4
c₃와 c₆에 입력 fanout을 적용한 결과. 이 분할된 call 집합은 여섯 개가 아닌 네 개의 중간 스위치로 라우팅 가능.

표 6.5
표 6.4의 call 집합을 네 개의 middle switch에 배치한 결과.

그림 6.15
표 6.5에 따라 라우팅된 예시. c₃와 c₆의 fanout은 각각 입력 스위치 1과 2에서 수행되며, 나머지는 중간 스위치에서 fanout된다. 총 6개의 dual-cast call이 네 개의 middle stage switch에 라우팅되었다.

middle switch가 m개일 때, speedup은 S = m / n 이다. 일반적인 multicast call set을 라우팅하려면, 입력 스테이지에서 fanout을 S만큼 수행할 수 있다. 그러면 최대 fanout f는 중간 스테이지에서 g = ⌈f / S⌉ 만큼 수행해야 한다.

이때, 분할된 call은 벡터상 입력 스위치 1개와 출력 스위치 g개에 1이 존재하므로 총 g+1개의 열에서 1을 가진다. 각각의 열에는 최대 (n−1)개의 다른 call과 충돌할 수 있으므로, 하나의 call은 최대 (g+1)(n−1)개의 call과 충돌 가능하다. 따라서 다음 조건이 충족되면 모든 call은 충돌 없이 라우팅될 수 있다:

m ≥ (g + 1)(n − 1) + 1    (식 6.2)

f가 S로 나누어 떨어질 경우 다음과 같이 정리할 수 있다:

S = f / g ≥ ((g + 1)(n − 1) + 1) / n    (식 6.3)

call을 입력 스테이지에서 분할한 후, 입력 열(column)은 최대 Sn개의 1을 가질 수 있지만, 하나의 call은 해당 열에서 최대 n개 call과만 충돌할 수 있다. 이는 동일한 main call에서 유도된 sub-call들끼리는 충돌하지 않기 때문이다.

표 6.6
중간 스위치 수에 따른 최대 fanout 값.

식 6.3에 따라, middle switch 수 m이 주어졌을 때, 지원 가능한 최대 fanout은 다음과 같다:

f ≤ m(m − n) / (n(n − 1))    (식 6.4)

표 6.6은 다양한 n과 S 값에 대해 처리 가능한 최대 fanout 값을 보여준다. 특히, n이 커질수록 (n−1 항 때문에) 같은 speedup에서도 지원 가능한 fanout이 급격히 감소함을 알 수 있다. 예: S = 2일 때 n=2면 f=4이나, n=48일 경우 f는 2.0 수준으로 감소한다.

식 6.4를 m에 대해 정리하면 다음과 같은 중간 스위치 수의 하한을 구할 수 있다:

m ≥ n + √(n² + 4n(n − 1)f)/2 = n + √((4f + 1)n² − 4fn)/2    (식 6.5)

단, 이 계산은 g가 정수일 때만 유효하며, 그렇지 않은 경우에는 **g = ⌈f / S⌉**로 올림해야 한다.

그림 6.16
Clos 네트워크에서 multicast call을 라우팅하는 greedy 알고리즘.

1. call 집합 C에서 각 call을 분할하여, fanout이 최대 g가 되도록 Cs에 저장한다.
2. 각 call cᵢ ∈ Cs에 대해
   • 각 middle switch mⱼ에 대해
     • 충돌이 없는 경우 mⱼ에 할당하고 다음 call로 진행.

**할당 행렬 A (m×2r 크기)**를 사용해 충돌 여부를 확인한다. 각 행은 middle switch에 해당하며, 열은 입력 또는 출력 스위치에 해당한다. A의 원소는 φ 또는 ck의 부모 call p(ck) 중 하나다. ck가 할당되면 관련 A의 항목들을 p(ck)로 채운다. 새로운 call ci = (ai, {bi₁,...,big})를 체크할 때, ai 및 biₖ들에 대한 A 항목이 모두 φ이거나 동일한 부모 p(cj)일 경우에만 충돌이 없는 것으로 판단한다.

정리 6.4
Greedy 알고리즘은 식 6.2에서 주어진 middle switch 수의 조건을 만족하며 multicast 트래픽을 라우팅할 수 있다.

증명
Cs 내에 어떤 call이 m개의 middle switch 모두와 충돌한다고 가정해 보자. 이는 해당 call이 m개의 call과 충돌해야 함을 의미한다. 하지만 한 call이 충돌할 수 있는 call 수는 (g+1)(n−1)를 초과할 수 없으므로, **m > (g+1)(n−1)**이면 반드시 하나의 switch가 남아 있다. 따라서 모순이다.

정리 6.5
(m, n, r) Clos 네트워크는 fanout이 f인 multicast 트래픽에 대해, 식 6.4가 성립하면 strictly non-blocking하다.

6.3.6 세 단계 이상의 Clos 네트워크

n×n crossbar switch를 구성 요소로 사용하면, n² 포트를 가진 rearrangeable한 (n, n, n) 3단계 Clos 네트워크를 만들 수 있다. 만약 n² 포트보다 더 많은 포트가 필요하다면, 이 n²×n² Clos 네트워크를 각 중간 스위치로 사용하고, 입력 및 출력 스위치는 n×n crossbar로 구성하면 된다. 이는 n³ 포트를 가진 5단계 Clos 네트워크를 형성하게 된다.

일반적으로, 정수 i에 대해, 다음과 같은 구조를 만들 수 있다:

• 첫 단계: nⁱ 개의 n×n crossbar
• 중간 단계: n개의 (2i−1)-단계 Clos 네트워크
• 마지막 단계: nⁱ 개의 n×n crossbar

이 구조는 총 2i+1단계로 구성되며, nⁱ⁺¹개의 포트를 가진 rearrangeable Clos 네트워크가 된다.

비슷한 방식으로, strictly non-blocking Clos 네트워크도 만들 수 있다. 이 경우에는 입력단에 expansion이 추가되어야 하며, 중간 스위치는 (2n−1)개의 nⁱ 포트를 갖는 (2i−1)단계 Clos 네트워크로 구성된다.

예를 들어, Figure 6.17은 (2,2,4) Clos 네트워크로, 이 네트워크는 2×2 crossbar로 구성되어 있으며, 중간 스테이지는 각각 (2,2,2) Clos 네트워크다.

5단계 Clos 네트워크에서의 라우팅은 Figure 6.11 또는 6.16의 알고리즘을 바탕으로 바깥에서 안쪽으로 진행된다. 각 call을 n개의 middle switch 중 하나에 할당함으로써, 하나의 (2i+1)-단계 스케줄링 문제를 n개의 (2i−1)-단계 문제로 분할한다. 이 과정을 i번 반복하여 최종적으로 ni개의 n×n crossbar 스케줄링으로 귀결된다.

예를 들어, i = 2인 5단계 Clos 네트워크에서 unicast call을 스케줄링할 경우:

1. 첫 단계: call을 n개의 중간 스위치에 할당 (Figure 6.11 사용)
2. 다음 단계: 각 중간 Clos 네트워크 (3단계)를 Figure 6.11로 처리
3. 각 call은 중간 Clos 내의 하나의 crossbar로 다시 배정된다

Figure 6.17의 네트워크는 rearrangeably non-blocking 하며, 외부의 (2,2,4) Clos 네트워크도, 내부의 (2,2,2) 네트워크도 모두 rearrangeable하다.

반면, 동일한 구조에서 strictly non-blocking 성질을 만족하려면 각 입력 단계마다 expansion이 필요하다. 예: Figure 6.17과 같은 네트워크를 strictly non-blocking으로 만들려면 (3,2,4) Clos가 필요하며, 여기엔 다음이 포함된다:

• 입력: 네 개의 2×3 스위치
• 출력: 네 개의 3×2 스위치
• 중간: 세 개의 (3,2,2) Clos 네트워크 (각각은 2×3 입력, 3×2 출력, 2×2 middle switch 3개)

Strictly non-blocking 구조는 가운데 단계에 2×2 스위치가 9개 필요하며, 이는 rearrangeable 구조의 4개보다 많다. Expansion이 입력 및 중간 단계 양쪽 모두에서 요구되기 때문이다.

Multicast 라우팅을 위해서는 fanout을 어디에서 수행할지 결정해야 한다. 이 fanout은 네트워크의 어느 단계에서든 수행 가능하지만, 세부 사항은 이 책의 범위를 넘는다. 일반적인 휴리스틱은 2n+1단계 Clos 네트워크에서 fanout f를 각 첫 n+1단계마다 f^(1/(n+1))씩 분배하는 것이다.

6.4 Beneš 네트워크

Figure 6.17처럼 2×2 switch로만 구성된 Clos 네트워크는 Beneš 네트워크라고 불린다. 이 네트워크는 N = 2ⁱ 포트를 rearrangeable하게 연결할 수 있는 최소 crosspoint 수를 가진 네트워크이다.

N = 2ⁱ 포트를 2×2 스위치로 연결하려면, 2ⁱ−1단계가 필요하며, 각 단계마다 2ⁱ⁻¹개의 2×2 스위치가 필요하다. 총 스위치 수는 (2ⁱ−1)×2ⁱ⁻¹ = (2ⁱ−1)2ⁱ⁻¹이고, 각 스위치에 crosspoint 4개가 있으므로 총 crosspoint 수는 (2ⁱ−1)×2ⁱ⁺¹이다.

주의 깊은 독자라면, Beneš 네트워크는 두 개의 2-ary i-fly 네트워크를 중간에서 결합(fuse)한 구조와 동일함을 눈치챘을 것이다. 실제로는 Beneš 및 다른 다단 Clos 네트워크는 **중간 스테이지를 기준으로 folding(접기)**하여 구현되는 경우가 많다. 이때 스테이지 j와 2i−j는 동일한 패키지에 배치되어 배선 복잡도를 줄일 수 있다.

6.5 Sorting 네트워크

Sorting network는 N개의 입력에 unique key가 부착된 레코드를 받아, 정렬된 순서로 N개의 출력으로 내보낸다. Sorting network는 각 레코드의 목적지 주소를 정렬 key로 사용함으로써 non-blocking 네트워크로 사용할 수 있다.

Figure 6.18은 Batcher bitonic sorting network를 보여준다. 이 정렬 알고리즘은 bitonic sequence의 특성을 이용한다. Bitonic sequence는 순환적으로 봤을 때 최대 한 번씩 오름차순과 내림차순 구간만을 가지는 시퀀스이다.

예를 들어 Figure 6.18(a)에서는 8개의 key가 왼쪽에서 입력되고, 오른쪽에서 정렬된 결과로 출력된다. 각 화살표는 두 개의 key를 비교하여 필요한 경우 서로 교환한다. 첫 단계에서는 짝수/홀수 index별로 방향을 다르게 정렬하여 0–3번, 4–7번 구간이 각각 bitonic sequence가 되도록 만든다. 이후 단계에서는 각 bitonic 시퀀스를 monotonic sequence로 합친다.

총 6단계 후, 정렬이 완료된다. Table 6.7은 숫자 8개로 된 시퀀스에 bitonic 정렬을 적용한 예시를 보여준다.

N = 2ⁿ일 때, bitonic sort는 다음과 같은 단계 수를 갖는다:

S(N) = (log₂ N)(1 + log₂ N) / 2

즉, 2ⁿ의 길이를 갖는 bitonic 시퀀스를 만들기 위해 S(N/2) 단계, 그 후 정렬을 위해 log₂ N 단계가 필요하다.

Figure 6.18(b)의 sorting network는 이 알고리즘을 직접 하드웨어로 구현한 형태이며, 각 비교 연산은 key를 비교하여 라우팅하는 2×2 스위치로 구성된다.

6.6 사례 연구: Velio VC2002 (Zeus) Grooming Switch

일부 ATM 스위치에서는 Batcher 정렬 네트워크와 butterfly를 조합한 구조(Batcher-banyan 네트워크)를 사용한다. Batcher 네트워크는 입력 셀들을 목적지 주소로 정렬한다. 정렬된 출력에서는 trap stage가 동일한 출력을 가지는 셀을 감지하고 하나를 제외한 나머지를 제거한다. 남은 셀들은 서로 다른 출력을 가지며, 정렬된 상태로 butterfly 네트워크에 입력된다. 이 구조는 butterfly가 셀들을 충돌 없이 라우팅할 수 있게 한다.

Velio VC2002는 단일 칩으로 구현된 TDM(Time-Domain Multiplexing) 회로 스위치이다 (그림 6.19). VC2002는 총 72개의 SONET STS-48 2.488Gbps 직렬 입력 스트림을 받아, 동일한 수의 출력 스트림으로 출력한다. 각 STS-48 스트림은 48개의 STS-1 스트림(각 51.83Mbps)을 byte 단위로 멀티플렉싱하여 포함한다.

즉, 각 3.2ns의 byte time 또는 time slot마다 서로 다른 STS-1의 byte가 하나씩 전달된다. channel 0의 byte, channel 1의 byte, ..., channel 47의 byte 순으로 전송되고, 48개의 time slot 이후 동일한 패턴이 반복된다.

TDM switch, 또는 cross connect 혹은 grooming switch라 불리는 장치는 시간과 공간 두 차원에서 스위칭을 수행하여, 입력 STS-1의 time slot을 출력 STS-1의 time slot에 매핑한다.

그림 6.20은 입력 2개, 출력 2개, time slot 4개로 구성된 단순화된 TDM 스위칭 예시를 보여준다. 예를 들어 입력 0의 time slot 1에 있는 B는 출력 1의 time slot 0으로 라우팅된다 (unicast). 반면, 입력 0의 time slot 0에 있는 A는 출력 0의 time slot 3과 출력 1의 time slot 1로 동시에 전송된다 (multicast).

VC2002는 이와 유사한 기능을 72개의 입력과 48개의 time slot에 대해 수행한다.

TDM grooming switch는 대부분의 광역 및 도시 기반 음성/데이터 통신 네트워크에서 핵심적인 역할을 한다. 이러한 네트워크는 일반적으로 SONET ring을 기반으로 구성되며, grooming switch는 여러 ring을 연결하는 cross-connect 또는 느린 전송 채널을 ring에 추가/삭제하는 add-drop multiplexer 역할을 한다.

TDM switch는 일반적으로 보호 이벤트 외에는 구성 변경이 느리다. 새로운 STS-1 회선은 보통 분당 몇 개의 속도로만 설정된다. 하지만 장애(예: 굴착기로 광케이블 절단 등)가 발생하면, VC2002 내의 3,456개 연결 중 많은 수가 수 밀리초 내에 재설정되어야 서비스 중단을 피할 수 있다.

TDM switch는 입력 및 출력 스트림이 시간에 따라 멀티플렉싱된다는 점을 활용하여, Clos 네트워크의 첫 번째 및 세 번째 단계를 시간 도메인에서 구현할 수 있다 (그림 6.21). 이로써 8×8 crossbar의 복잡성을 피하면서 Figure 6.20의 2입력, 4-time slot 예제를 구현할 수 있다.

그림 6.21에서:

• 입력 및 출력 스위치는 4×4 time switch (TSI: Time-Slot Interchanger)로 구현된다.
• 중간 단계의 4개의 2×2 switch는 실제로는 time-multiplexed된 단일 2×2 switch로 구현된다.

TSI는 2n 엔트리의 메모리이다. 입력 스트림이 절반(n개의 엔트리)을 순차적으로 채우는 동안, 다른 절반은 출력 스트림이 임의 순서로 읽는다. 이후 입출력 역할을 바꾸며 반복된다. 이 방식 덕분에 각 time slot에서 middle switch 역할을 하는 단일 2×2 switch로 네 개의 switch를 구현할 수 있다.

그림 6.22는 VC2002의 블록 다이어그램이다. 이 스위치는 다음 구성으로 이루어져 있다:

• 72개의 48×96 입력 TSI
• 72×72 공간 스위치 (96개의 논리적 time slot마다 재구성됨)
• 72개의 96×48 출력 TSI

구성은 현재 time slot 주소를 통해 접근되는 configuration RAM에 의해 제어된다. 각 time slot마다 다음이 정의된다:

• 입력 TSI에서 읽을 위치
• 스위치에서 각 출력 포트에 연결할 입력 포트
• 출력 TSI에서 읽을 위치

이 스위치는 (m, n, r) = (96, 48, 72)의 3단계 TST Clos 네트워크 구조를 따른다. 총 72개의 입력 스트림에 대해 각각 48 time slot이 있으며, 각 입력 스위치에는 96개의 중간 스테이지가 존재하므로 speedup은 2이다. 이로 인해 VC2002는 unicast에 대해 strictly non-blocking, dual-cast(fanout=2)에 대해 rearrangeably non-blocking 특성을 갖는다.

스케줄링 방법은 다음과 같다:

• unicast 트래픽: Figure 6.8의 교집합 방법 또는 Figure 6.11의 looping 알고리즘 사용
• dual-cast 트래픽: Figure 6.16의 greedy 알고리즘 또는 looping 알고리즘을 사용하되, call을 분할하여 라우팅

VC2002는 입력/출력에 SONET framer를 내장하고 있다. 입력 framer는 스트림 정렬과 SONET 오버헤드 처리를 수행하며, 출력 framer는 전송 오버헤드를 생성한다.

또한, 96 time slot을 지원하는 72×72 스위치를 구현하기 위해, 실제로는 두 개의 48-time-slot 스위치를 사용하여 STS-48 byte rate (311MHz)에서 동작하도록 구현된다.

dual-cast call을 두 개의 unicast call로 나누고, 중간 스위치를 두 개의 동일한 부분 집합으로 분할하면, 각 unicast call을 해당 부분 집합에 할당하여 라우팅할 수 있다. 각 부분 집합은 m/2 = n개의 스위치를 가지며, 이 부분 집합 내에서는 unicast call에 대해 rearrangeable 하다.

실제로 VC2002는 Section 6.3.5에서 설명한 방식으로 call을 분할함으로써, 임의의 fanout을 가진 multicast call도 매우 낮은 blocking 확률로 처리할 수 있다. 높은 fanout을 가진 call에 대한 blocking 확률 계산은 연습문제 6.5로 남겨 둔다.

VC2002 하나는 180Gbps의 STS-1 grooming 대역폭을 제공하며, 이는 3,456개의 STS-1 회선을 스위칭할 수 있는 수준이다. 더 큰 grooming switch가 필요할 경우, 여러 개의 VC2002를 Clos 네트워크로 연결할 수 있으며, 그 예가 그림 6.23에 나와 있다.

이 그림은 총 120개의 VC2002를 사용하여 최대 4.3Tbps(1,728 STS-48 또는 82,944 STS-1)를 처리할 수 있는 folded Clos 네트워크를 보여준다.

• 첫 번째 랭크의 72개 칩은 각각 24×48 STS-48 입력 스위치 및 48×24 STS-48 출력 스위치로 동작한다.
• 두 번째 랭크의 48개 칩은 각각 72×72 STS-48 중간 스위치를 구성한다.

이 시스템은 논리적으로 5단계 Clos 네트워크이다. 각 VC2002가 내부적으로 3단계 Clos 구조를 가지므로, 외형상 9단계 네트워크처럼 보일 수 있다. 그러나 실제로는 외부의 TSI만을 고려하여 다음과 같은 TSSST 구조로 해석할 수 있다:

• 48×48 TSI
• 24×48 공간 스위치
• 72×72 공간 스위치
• 48×24 공간 스위치
• 48×48 TSI

경로상의 나머지 네 개의 TSI는 직통(straight-through) 모드로 동작한다. 연습문제 6.6에서는 이 구조를 7단계 TSTSTST 구조로 해석할 수 있는 가능성을 탐색하도록 되어 있다.

이 5단계 논리 네트워크를 스케줄링하려면 다음과 같은 절차를 따른다:

1. 중간의 3개 space switch 단계를 48개의 3,456×3,456 space switch로 간주한다 (각 time slot마다 하나).
2. (m,n,r) = (48,24,3456) Clos로서, 각 call을 48개 time slot 중 하나에 할당한다.
3. 각 time slot에 대해 48개의 물리적 중간 스위치 중 하나에 call을 할당하는 48개의 하위 문제로 나뉜다.
4. 각 하위 문제는 (m,n,r) = (48,24,72) Clos로 스케줄링할 수 있다.

6.7 참고문헌 노트

• Clos (1953): non-blocking 네트워크에 대한 최초의 논문 발표, Clos 네트워크 및 strictly non-blocking 조건 제시
• Beneš, Slepian, Duguid: 작은 Clos 네트워크도 rearrangeable 하다는 것을 발견
• König: 이분 그래프의 최대 차수 Δ에 대해 Δ 색으로 간선 색칠(edge coloring)이 가능함을 증명
• Cole: 더 효율적인 간선 색칠 알고리즘 개발
• Waksman: 행렬 분해(matrix decomposition) 관련 연구
• Beneš (1965): rearrangeable non-blocking 네트워크 구현 시 필요한 최소 crosspoint 수의 경계 도출, Beneš 네트워크 소개
• Batcher (1968): 비토닉(bitonic) 정렬 및 Batcher 정렬 네트워크 제안
• Knuth: 정렬 네트워크에 대한 상세한 설명
• Masson and Jordan: Clos 네트워크에서의 multicast 문제 최초 연구
• Yang and Masson: 거의 최적의 multicast 스케줄링 알고리즘 제안

6.8 연습문제

6.1
27포트 Clos. 3×3 crossbar switch를 사용하여 정확히 27개의 포트를 가지는 rearrangeable Clos 네트워크를 설계하시오.

6.2
최대 크기의 Clos 네트워크. n×n crossbar switch를 사용하여 k단계 (k는 홀수)로 구성되는 Clos 네트워크를 만들 때, unicast traffic에 대해 rearrangeable하기 위해 만들 수 있는 최대 포트 수는?

6.3
Looping 알고리즘의 성능. Figure 6.11의 looping 알고리즘을 구현하여 (5,5,5) Clos 네트워크에 대해 실험하시오. 포트가 모두 사용될 때까지 무작위로 connection을 하나씩 추가하며, 각 connection당 평균 몇 번의 재배치가 필요한지 계산하시오. 알고리즘을 수정하여 재배치 횟수를 줄이는 방법도 시도하고, 두 경우의 결과를 비교하여 설명하시오.

6.4
Batcher-banyan 네트워크. Batcher-banyan은 Batcher로 정렬된 call을 banyan(=butterfly)에 전달하는 구조이다. 포트 번호 {aₙ₋₁, ..., a₀}가 Batcher에서 {aₙ₋₂, ..., a₀, aₙ₋₁}로 shuffle 되어 banyan에 전달될 때, 모든 permutation이 blocking 없이 라우팅될 수 있음을 증명하시오.

6.5
확률적 non-blocking multicast. fanout=4인 call이 VC2002 (Section 6.6) 상에서 greedy 알고리즘으로 라우팅될 때, blocking 확률을 추정하시오.

6.6
7단계 time-space switch. Figure 6.23의 120-chip 네트워크를 처음에는 5단계 TSSST로 보았지만, 내부 speedup을 고려하지 않았다. 이제 이 네트워크를 7단계 TSTSTST 구조로 보았을 때, 어떤 트래픽 패턴이 라우팅 가능해지며, 스케줄링에 어떤 영향을 주는지 설명하시오.

6.7
rearrangeability 증명. Hall의 정리를 사용하여 m ≥ n인 Clos 네트워크가 rearrangeable함을 증명하시오.

Hall의 정리
집합 A와 A₁, A₂, ..., Aᵣ가 있을 때, ai ∈ Ai 이며 ai ≠ aj (i ≠ j)를 만족하는 대표자 집합 {a₁, ..., aᵣ}가 존재하려면, 임의의 k개 부분 집합의 합집합 크기가 최소 k 이상이어야 한다.

6.8
Euler 분할을 이용한 그래프 색칠. Euler 분할 기법을 통해 bipartite graph를 edge coloring할 수 있다. 그래프의 모든 간선을 정확히 한 번씩 방문하는 Euler 경로를 찾아, 이를 따라 alternate edge를 서로 다른 두 그래프로 나눈다. 이 과정을 반복하여 차수가 1인 그래프들로 나눈다.

(a) 모든 노드 차수가 2ⁱ일 때, Euler 경로가 항상 존재함을 증명하고, 경로를 찾는 알고리즘을 기술하시오.
(b) 노드 수 V, 차수 2ⁱ인 그래프에서 Euler 분할 기반 색칠 알고리즘의 점근적 수행 시간을 구하고, looping 알고리즘과 비교하시오.

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은 짝수로 가정)