라우팅은 주어진 topology 내에서 source node에서 destination node로 가는 경로를 선택하는 과정이다. 네트워크의 topology, 즉 지도와 같은 구조가 정해지면, 그다음은 그 지도에서 목적지까지 가는 길을 고르는 것이 라우팅이다. Topology가 네트워크의 이상적인 성능을 결정한다면, 라우팅은 이 성능 중 얼마나 실제로 구현되는지를 결정하는 두 가지 핵심 요소 중 하나이다. 나머지 하나는 12장과 13장에서 다룰 flow control이다.
라우팅 알고리즘은 여러 이유에서 중요하다. 좋은 라우팅 알고리즘은 permutation traffic과 같은 비균일 트래픽 패턴이 있어도 네트워크의 채널들 간 부하를 고르게 분산시킨다. 채널 부하가 균형을 이룰수록 네트워크의 throughput은 이상적인 값에 가까워진다. 하지만 의외로, 현재 사용 중인 많은 router들이 부하를 고르게 분산하는 데 실패하고 있다. 대부분의 경우, 각 노드 쌍 사이의 트래픽은 단일하고 미리 정해진 경로를 따른다. 이런 라우팅 알고리즘은 비균일 트래픽 상황에서 큰 부하 불균형을 유발할 수 있으며, 이로 인해 throughput이 떨어진다. 그럼에도 불구하고 이런 라우팅 방식이 사용되는 이유는 또 다른 중요한 라우팅 알고리즘의 특성인 짧은 경로 길이를 최적화하기 위함이다.
잘 설계된 라우팅 알고리즘은 경로 길이를 가능한 짧게 유지하여 hop 수를 줄이고, 메시지의 전체 latency를 낮춘다. 하지만 때로는 minimal routing(항상 최단 경로를 선택하는 방식)이 부하 균형과 throughput 향상과 충돌할 수 있다. 특히 oblivious routing 알고리즘에서는 모든 트래픽 패턴에 대해 부하 균형을 맞추려면 전체 메시지의 평균 경로 길이를 늘릴 수밖에 없다. 반대로 평균 경로 길이를 줄이면 부하 균형이 무너진다. Oblivious 알고리즘은 현재 트래픽 패턴을 고려하지 않기 때문에 이런 tradeoff가 생긴다. 이 알고리즘들은 9장에서 자세히 다룬다.
1. Greedy Routing
방법: 목적지까지의 최단 거리 방향으로 항상 라우팅함.
예: 노드 0에서 노드 3은 시계방향, 노드 0에서 노드 5는 반시계방향.
거리가 같을 경우 무작위로 선택.
특징: 경로는 짧지만, 부하 분산이 되지 않아 특정 방향에 트래픽이 몰릴 수 있음.
Tornado traffic에서 throughput: 0.33
2. Uniform Random Routing
방법: 패킷마다 양방향 중 무작위로 한 방향을 동일 확률(50%)로 선택.
특징: 균등 확률로 방향을 선택하므로, 부하 분산이 일부 이루어짐.
Tornado traffic에서 throughput: 0.40
3. Weighted Random Routing
방법: 짧은 방향을 높은 확률(1−d/8), 긴 방향을 낮은 확률(d/8)로 선택.
여기서 d는 source와 destination 간의 최소 거리.
특징: 트래픽을 짧은 경로에 집중하되, 일부는 긴 경로로 분산시켜 부하 분산 효과 향상.
Tornado traffic에서 throughput: 0.53
4. Adaptive Routing
방법: 현재 로컬 채널 부하를 고려하여 트래픽이 덜 혼잡한 방향으로 선택.
큐 길이나 과거의 패킷 수로 채널 부하를 추정.
backtracking은 허용되지 않음 → source에서 한 번만 결정.
특징: 실시간 네트워크 상태를 반영하여 경로 결정.
Tornado traffic에서 throughput: 0.53 (weighted random과 동일 수준)
최악의 경우 throughput을 가장 잘 보장하는 알고리즘은 무엇일까? 대부분의 사람들은 greedy 알고리즘을 선택한다. 실제로 2002년 박사 자격 시험에서 이 문제가 출제되었고, 응시자의 90% 이상이 greedy 알고리즘을 선택했다. 하지만 이 알고리즘은 최악의 경우에 최선의 throughput을 제공하지 않는다.
예를 들어, 각 노드 i가 i+3 mod 8로 패킷을 보내는 tornado traffic pattern을 보자. 이때 greedy routing을 사용하면 모든 트래픽이 ring을 시계방향으로만 이동하고, 반시계 방향 채널은 사용되지 않아 부하 불균형이 심해진다. 이로 인해 각 terminal의 throughput은 b/3으로 떨어진다. 반면, random routing에서는 반시계방향 링크에 5/2의 부하가 걸려 throughput은 2b/5가 된다. Weighted random은 전체 트래픽 중 5/8이 3 링크를, 3/8이 5 링크를 지나므로 부하는 각 방향에 대해 15/8이 되고, throughput은 8b/15가 된다. Adaptive routing도 잘 구현된다면 이와 같은 부하 균형을 달성하여 동일한 throughput을 낼 수 있다.
이 예시는 라우팅 선택이 부하 균형에 얼마나 큰 영향을 미치는지를 보여준다. 물론 throughput은 최적화할 수 있는 여러 지표 중 하나일 뿐이고, 어떤 지표를 중시하느냐에 따라 적절한 알고리즘 선택은 달라질 수 있다.
8.2 라우팅 알고리즘의 분류
라우팅 알고리즘은 source node x에서 destination node y까지 가능한 경로 집합 Rxy 중에서 어떻게 선택하는지를 기준으로 분류할 수 있다.
Deterministic routing: 항상 동일한 경로를 선택한다 (Rxy의 크기가 1 이상이라도 항상 같은 경로 선택). topology의 경로 다양성을 무시하므로 부하 분산에는 매우 취약하다. 그럼에도 구현이 쉽고 deadlock-free로 만들기 쉬워서 널리 사용된다.
Oblivious routing: deterministic 알고리즘을 포함하는 개념으로, 현재 네트워크의 상태를 전혀 고려하지 않고 경로를 선택한다. 예를 들어, 가능한 모든 경로에 대해 트래픽을 균등 분산하는 random 알고리즘이 이에 해당한다.
Adaptive routing: 네트워크의 상태에 따라 동적으로 경로를 선택한다. 상태 정보는 노드나 링크의 사용 여부, 큐 길이, 채널 부하 이력 등을 포함할 수 있다.
앞서 소개한 tornado 예제는 이 세 가지 유형의 예시를 모두 포함한다. Ring에서 greedy는 deterministic routing, random과 weighted random은 oblivious routing, adaptive는 초기 hop의 채널 부하를 고려하므로 adaptive routing이다.
이때 언급된 알고리즘들은 Rxy, 즉 최소 경로 집합을 기준으로 한 것이며, 이를 minimal routing이라고 한다. 반면, minimal이 아닌 경로도 포함하는 경우 R′xy에서 선택하며 이를 non-minimal routing이라고 한다. Ring 예제에서 greedy는 minimal, random과 adaptive는 non-minimal로 분류된다.
8.3 라우팅 관계 (Routing Relation)
라우팅 알고리즘을 라우팅 관계 R과 선택 함수 ρ로 나누어 표현하면 유용하다. R은 경로(또는 incremental routing에서는 채널)들의 집합을 반환하고, ρ는 그 중 하나를 선택하는 역할을 한다.
라우팅 알고리즘이 incremental인지, node 기반인지 channel 기반인지에 따라 R은 세 가지 방식으로 정의된다.
R: N × N → P(P) 두 노드 간 가능한 전체 경로의 집합을 반환한다. 이를 all-at-once routing이라 부른다.
R: N × N → P(C) 현재 노드와 목적지를 입력으로 받아 가능한 채널들의 집합을 반환한다.
R: C × N → P(C) 현재 채널과 목적지를 입력으로 받아 가능한 채널들의 집합을 반환한다.
첫 번째 방식은 라우팅 결정을 source에서 한 번에 수행하고 패킷과 함께 경로 정보를 저장한다. 계산은 단순하지만, 패킷마다 경로 정보를 함께 보내야 하므로 오버헤드가 있다.
두 번째, 세 번째 방식은 incremental routing으로, hop마다 라우팅 결정을 반복 수행한다. 패킷마다 경로 정보를 들고 다닐 필요는 없지만, hop마다 R을 계산해야 하므로 latency가 증가할 수 있다. 또한, 일부 라우팅 전략은 incremental 방식으로는 구현할 수 없다.
특히 Relation 8.2 방식은 수직에서 수평, 혹은 그 반대 방향으로 들어오는지를 구분하지 못하므로 2-D mesh에서 특정 노드에서만 방향 전환을 제한하는 전략은 구현 불가하다. Relation 8.3은 이를 어느 정도 해결할 수 있다. 이전 채널 정보를 활용해 deadlock 방지에도 효과적이다.
라우팅이 deterministic이 아니라면, R은 여러 경로/채널을 반환하므로, 선택 함수 ρ가 최종 선택을 담당한다. ρ가 네트워크 상태를 고려하지 않으면 oblivious, 고려하면 adaptive가 된다.
8.4 Deterministic Routing
가장 단순한 형태인 deterministic routing은 모든 source-destination 쌍에 대해 항상 같은 경로를 선택한다. 예: R: N × N → P. 이는 경로 다양성이 없기 때문에 부하 불균형을 유발한다. 어떤 트래픽 패턴에서는 모든 deterministic routing이 심한 부하 불균형을 일으킨다.
그럼에도 불구하고, 구현이 간단하고 비용이 낮아 과거 네트워크에서 널리 사용되었고, 지금도 irregular topology에서는 자주 쓰인다. 이는 randomized나 adaptive 라우팅을 설계하기 어렵기 때문이다.
대부분의 topology에서는 minimal deterministic routing function을 선택하는 것이 합리적이다. 최소한 경로 길이는 짧게 유지된다. 일부 topology에서는 간단한 deterministic 접근 방식이 adaptive를 포함한 다른 어떤 minimal routing algorithm보다도 부하 분산이 잘 되는 경우도 있다 (Exercise 9.2 참고). 또한 특정 source-destination 쌍 사이에서 메시지 순서를 유지해야 하는 경우, deterministic routing이 이를 단순하게 보장하는 방법이 될 수 있다. 이는 예를 들어 특정 cache coherence protocol에서 중요하다.
이 절에서는 가장 널리 쓰이는 deterministic routing algorithm 두 가지, 즉 butterfly에서의 destination-tag routing과 torus/mesh에서의 dimension-order routing을 설명한다.
k-ary n-fly network에서 (4.1절 참고) 목적지 주소는 radix-k 숫자 n자리로 해석되며, 이것이 경로 선택에 직접 사용된다. 주소의 각 자릿수는 네트워크 각 단계에서 출력 포트를 선택하는 데 사용된다. 이는 마치 source-routing table에서 미리 정해진 routing header처럼 동작한다. 2장에서 설명한 단순 router에서 사용된 방식이다.
Figure 8.3(a)는 source 3에서 destination 5까지 가는 경로를 예시로 보여준다. 5의 이진수는 101이고, 각 비트는 네트워크의 각 단계에서 출력 포트를 결정한다. 첫 번째 비트 1은 아래쪽 출력 포트를, 두 번째 비트 0은 위쪽 포트를, 세 번째 비트 1은 다시 아래쪽 포트를 선택한다.
이 예에서 출발 노드 3의 주소는 실제로 사용되지 않았다. 다시 말해, 어떤 노드에서 출발하더라도 101 패턴을 따라가면 목적지 5에 도달한다. 이는 모든 목적지 주소에 대해 동일하게 적용된다. 즉, destination-tag routing은 목적지 주소에만 의존하며 source와는 무관하다.
Figure 8.3(b)는 4-ary 2-fly network에서 7번 노드에서 11번 노드로 가는 경로를 보여준다. 여기서 목적지 주소 11은 234(4진수)로 해석되며, 첫 번째 router에서 포트 2(위에서 세 번째), 두 번째 router에서 포트 3(맨 아래)을 선택한다. 이 역시 출발 노드에 상관없이 목적지를 정확히 선택할 수 있다.
8.4.2 Cube Network에서의 Dimension-Order Routing
dimension-order 또는 e-cube routing은 torus 및 mesh와 같은 direct k-ary n-cube network에서 destination-tag routing과 유사한 방식이다. 목적지 주소를 radix-k 숫자로 해석하고, 각 자릿수를 하나씩 사용하여 경로를 결정한다. 하지만 butterfly network와 달리 cube network에서는 한 자릿수를 해결하기 위해 여러 hop이 필요할 수 있다.
예를 들어 Figure 8.4의 6-ary 2-cube에서 node 03에서 node 22로 이동하는 패킷을 보자. torus에서는 각 차원을 시계방향 또는 반시계방향으로 이동할 수 있으므로, 먼저 각 차원에서의 최단 방향을 계산해야 한다.
source s = (0, 3), destination d = (2, 2)일 때:
m = (2 − 0, 2 − 3) mod 6 = (2, 5)
Δ = (2, 5) − (0, 6) = (2, -1)
D = (+1, -1) → x 차원은 +1 방향(시계방향), y 차원은 -1 방향(반시계방향)
이 정보를 기반으로 패킷은 먼저 x 차원에서 이동하고, 목적지 좌표에 도달하면 y 차원으로 전환한다. Figure 8.4에서 node 03에서 시작하여 x 차원으로 한 hop(03 → 02), y 차원으로 두 hop(02 → 12 → 22) 이동한다.
목적지를 32로 변경하면 Δ = (3 − 0, 2 − 3) = (3, 5) → D = (0, -1). y 방향의 preferred direction이 0이 된다. 이는 양방향 모두 3 hop이 필요하다는 뜻이며, 이 경우 부하를 균형 있게 분산하기 위해 deterministic routing 대신 무작위로 양방향으로 패킷을 나누는 것이 효과적이다. Equation 8.4를 보면, preferred direction이 0이 되는 경우는 k가 짝수일 때만 발생한다.
mesh에서는 wraparound channel이 없으므로 방향 선택이 단순해진다:
DM,i = +1 if di > si, -1 otherwise
Dimension-order routing은 부하 분산 성능은 좋지 않지만, 다음 두 가지 이유로 널리 사용된다:
구현이 매우 간단하다. 특히 각 차원별로 router를 분할하여 dimension-slicing이 가능하다.
각 차원 간의 채널 dependency에 cycle이 생기지 않도록 하여 deadlock 방지를 단순화한다. 다만, 차원 내에서는 여전히 deadlock이 발생할 수 있다 (14장 참고).
8.5 사례 연구: Cray T3D에서의 Dimension-Order Routing
Figure 8.5는 최대 2,048개의 DEC Alpha processing element를 3-D torus로 연결한 Cray T3D를 보여준다. T3D는 shared-memory multiprocessor이며, 각 PE는 로컬 메모리를 가지며 다른 PE의 메모리에도 접근 가능하다. 각 PE 쌍은 하나의 router를 공유하고, 이 router는 네트워크 인터페이스를 통해 연결된다.
T3D는 dimension-order routing을 사용하며, Figure 8.6에 보이듯 각 차원(x, y, z)을 위한 동일한 ECL gate array로 구현된 dimension-sliced router를 사용한다. 이는 J-Machine router(5.5절)와 유사한 구조이다. 이러한 분할은 dimension-order routing 덕분에 가능하다.
패킷이 network interface로부터 들어오면, x router가 이를 받아 x 좌표가 목적지인지 판단한다. 목적지에 도달하지 않았다면 +x 또는 −x 방향으로 전달하고, x 좌표가 일치하면 다음 y router로 넘긴다.
패킷은 +x 방향(xpOut 채널)을 따라 전달된다. 이후 각 x router에서는 현재 위치가 목적지의 x 좌표와 일치하는지 확인한다. 일치하면 y router로 전달하고, 그렇지 않으면 계속 +x 방향으로 이동한다.
Cray T3D의 각 router 채널은 300 MBytes/s의 대역폭을 가지며, 모듈 간 wire mat을 통해 연결된다. 각 채널은 16비트 data와 8비트 control 신호로 구성되어 있으며, 150 MHz에서 동작한다. 이는 원래 Alpha 21064 프로세서와 동일한 클럭이다. Wire mat은 torus topology를 구성하기 위해 보드 엣지 커넥터에 수작업으로 연결된 여러 개의 wire들을 엮은 구조로, 불규칙하게 짜인 직물처럼 보여서 'mat'이라고 불린다. 각 data/control 신호는 wire mat 내에서 differential ECL 신호로 twisted pair를 통해 전달된다.
그림 8.6은 T3D router가 x, y, z 세 개의 차원에 대해 동일한 ECL gate array 칩 세 개로 분할되어 구성됨을 보여준다.
Cray T3D에는 I/O 노드가 포함되어 있으며, 이들은 x 및 z 차원으로만 네트워크에 연결된다. 이로 인해 torus topology는 다소 불규칙해진다. 일반적으로 메시지는 x에서 시작해서 z에서 끝나므로 문제가 없어 보이지만, 메시지를 보내는 노드가 I/O 노드와 y 차원만 다를 경우 문제가 발생할 수 있다. 이를 해결하기 위해 해당 노드에는 두 개의 주소가 부여된다. 이 문제는 Exercise 8.8에서 더 자세히 다룬다.
8.6 참고 문헌
Tornado traffic 문제와 weighted random 해법은 Singh 외 [168]에서 설명되었다. 라우팅 관계의 여러 형태와 이들이 deadlock 분석에서 가지는 중요성은 Dally [57]와 Duato [60, 61, 62]에 의해 다루어졌다. Butterfly network에서의 destination-tag routing은 Lawrie [110]가 처음 설명했으며, torus network에서의 e-cube routing은 Sullivan과 Bashkow [179]가 제안했다. Degree δ를 가진 네트워크에 대해 Borodin과 Hopcroft [28], Kaklamanis 외 [91]는 특정 트래픽 패턴이 deterministic routing 알고리즘에서 최소 √(N/δ) 이상의 채널 부하를 유도할 수 있음을 보여주었다.
8.7 연습문제
8.1 Section 8.1의 라우팅 알고리즘과 네트워크를 다시 고려하라. 다음 조건에서 최적의 알고리즘은 무엇인가?
(a) 최소 메시지 지연 (b) 균일 트래픽에서 최고의 throughput (c) 다양한 permutation 트래픽 패턴에서 평균 throughput 최대화
각 조건당 하나의 알고리즘만 선택하고 그 이유를 설명하라.
8.2 Incremental routing의 한계 관계식 8.1(path-based relation)으로는 표현할 수 있지만, 관계식 8.2 및 8.3(incremental form)으로는 표현할 수 없는 라우팅 알고리즘을 설명하라.
8.3 Incremental 및 all-at-once routing의 header bit Destination-tag routing을 incremental 또는 all-at-once 방식으로 구현할 수 있다. 각 방식에 대해 패킷에 저장되어야 할 비트 수를 계산하라. 어느 방식이 비트 수가 적은가? 이 관계는 일반 topology의 minimal routing에서도 성립하는가? Topology의 path diversity와 어떤 관련이 있는가?
8.4 Ring에서 backtracking 허용 Section 8.1에서 다룬 라우팅 예에서 backtracking을 허용한다면, weighted random 알고리즘보다 더 나은 최악의 경우 throughput을 제공하는 알고리즘을 개발할 수 있는가? 있다면 제시하고, 없다면 그 이유를 설명하라.
8.5 Stage가 추가된 butterfly에서의 라우팅 k-ary n-fly에서 하나 이상의 stage가 추가된 구조를 위한 deterministic 방식의 destination-tag routing 확장 방법을 설명하라. 부하 분산을 개선하기 위한 간단한 randomization 방법도 제안하라.
8.6 Cray T3D에서의 방향-우선 라우팅 Figure 8.6의 Cray T3D router 채널 레이블을 재배열하여 첫 번째 router는 +x와 +y, 두 번째는 +z와 −x, 세 번째는 −y와 −z를 처리하게 만든다고 하자. 이 분할 방식에서도 동작 가능한 라우팅 알고리즘을 설명하라. 한 번 router에 도달한 패킷은 이전 router로 돌아갈 수 없음을 명심하라.
8.8 T3D에서 I/O 노드 라우팅 T3D 네트워크에서 I/O 노드는 x 및 z 차원에만 추가된다. 예를 들어, (0,0,0)부터 (3,3,3)까지 주소를 갖는 64-node 4-ary 3-cube가 있다고 하자. 이때 (4,0,0) 또는 (0,0,4)와 같은 주소로 I/O 노드를 추가할 수 있다. 모든 내부 노드에서 I/O 노드로, 그리고 그 반대로 dimension-order routing으로 라우팅이 가능하도록 하기 위해 I/O 노드에 두 개의 주소를 어떻게 부여할 수 있는지 설명하라.
8.9 Torus에서 “정확히 반대 방향” 트래픽 부하 균형 Dimension-order routing에서는 torus에서 노드가 정확히 반대 방향에 있을 때 부하 균형 문제가 발생할 수 있다. 이때 항상 positive 방향만 선택한다면 균일 트래픽에서의 throughput은 어떻게 되는가? 최악의 경우 throughput은 얼마인가? capacity의 분수로 표현하라. deterministic 알고리즘을 유지하면서도 이러한 반대 방향 부하 균형 문제를 개선할 수 있는 방법을 제안하고, 균일 및 최악의 throughput을 다시 계산하라.
8.10 CCC에서의 minimal routing Exercise 5.8에서 설명한 일반 CCC topology에 대해 near minimal routing 알고리즘을 설계하라. 항상 정확한 최소 경로를 찾기보다 단순함을 우선하되, 생성되는 경로가 [128]에서 보여준 최대 직경 Hmax = 2n + ⌈n/2⌉ − 2를 초과하지 않도록 하라. 균일 트래픽에서의 부하 분산 특성도 논의하라.
디지털 시스템은 현대 사회에 만연해 있다. 디지털 컴퓨터는 물리 시스템의 시뮬레이션, 대규모 데이터베이스 관리, 문서 작성 등 다양한 작업에 사용된다. 디지털 통신 시스템은 전화 통화, 비디오 신호, 인터넷 데이터를 전달한다. 오디오와 비디오 엔터테인먼트 역시 점점 디지털 형태로 전달되고 처리된다. 마지막으로, 자동차부터 가전제품까지 거의 모든 제품이 디지털 방식으로 제어된다.
디지털 시스템은 세 가지 기본 구성 요소로 이루어진다: logic, memory, communication.
Logic은 데이터를 변형하거나 조합한다. 예를 들어 산술 연산을 하거나 결정을 내리는 기능이다.
Memory는 데이터를 나중에 사용할 수 있도록 저장하며, 시간적으로 이동시킨다.
Communication은 데이터를 한 위치에서 다른 위치로 이동시킨다.
이 책은 디지털 시스템의 communication 구성 요소를 다룬다. 특히, 디지털 시스템의 서브시스템 간 데이터 전송에 사용되는 interconnection network를 다룬다.
오늘날 대부분의 디지털 시스템에서 성능의 병목은 logic이나 memory가 아니라 communication 또는 interconnection에서 발생한다. 고급 시스템에서는 전력의 대부분이 배선을 구동하는 데 사용되며, 클럭 주기의 대부분은 gate delay가 아니라 wire delay에 소모된다. 기술이 발전함에 따라 메모리와 프로세서는 더 작고, 빠르고, 저렴해지지만 빛의 속도는 변하지 않는다. 시스템 구성 요소 간 interconnection을 결정짓는 핀 밀도와 배선 밀도는 구성 요소 자체보다 느리게 스케일링되고 있다. 또한 구성 요소 간 통신 빈도는 최신 프로세서의 클럭 속도에 비해 현저히 뒤처지고 있다. 이러한 요인이 결합되어 interconnection은 향후 디지털 시스템의 성공을 좌우하는 핵심 요소가 되었다.
설계자들이 제한된 interconnection bandwidth를 보다 효율적으로 활용하려고 노력하면서, interconnection network는 현대 디지털 시스템의 시스템 수준 통신 문제를 해결하는 거의 범용적인 솔루션으로 자리 잡고 있다. 이들은 원래 다중 컴퓨터(multicomputer)의 까다로운 통신 요구 사항을 해결하기 위해 개발되었지만, 현재는 버스를 대체하는 시스템 수준 표준 interconnection으로 자리잡고 있다. 또한 특수 목적 시스템에서의 전용 배선 역시, routing wires보다 routing packets이 더 빠르고 경제적이라는 사실이 알려지면서 interconnection network로 대체되고 있다.
1.1 Interconnection Networks에 대한 세 가지 질문
본격적으로 들어가기 전에, interconnection network에 대한 몇 가지 기본적인 질문을 살펴본다:
Interconnection network란 무엇인가?
어디에서 사용되는가?
왜 중요한가?
Interconnection network란 무엇인가?
그림 1.1에서 볼 수 있듯, interconnection network는 단말들 사이의 데이터를 전송하는 programmable system이다. 그림에서는 T1부터 T6까지 여섯 개의 단말이 네트워크에 연결되어 있다. 예를 들어, T3이 T5로 데이터를 전송하려고 하면, 네트워크에 메시지를 보내고 네트워크가 그 메시지를 T5로 전달한다. 이 네트워크는 특정 시점마다 다른 연결을 수행하는 programmable한 특성을 갖는다. 예를 들어, 한 클럭 주기에는 T3에서 T5로 메시지를 전송하고, 다음 클럭 주기에는 동일한 자원을 사용해 T3에서 T1로 메시지를 전송할 수 있다. 이 네트워크는 여러 구성 요소 — buffers, channels, switches, controls — 로 이루어진 system이다.
이러한 정의를 만족하는 네트워크는 다양한 스케일에서 등장한다.
On-chip network는 단일 프로세서 내의 메모리 어레이, 레지스터, 연산 유닛 사이의 데이터를 전달한다.
Board-level, System-level 네트워크는 프로세서와 메모리, 또는 입력 포트와 출력 포트를 연결한다.
Local-area network (LAN), Wide-area network (WAN)는 서로 떨어진 시스템을 하나의 기업 또는 전 세계적으로 연결한다.
이 책에서는 chip-level에서 system-level까지의 작은 스케일만을 다룬다. 더 큰 스케일의 네트워크는 이미 우수한 참고서들이 존재하기 때문이다. 시스템 수준 이하에서는 채널 길이가 짧고 데이터 전송 속도가 매우 높기 때문에, 대규모 네트워크와는 근본적으로 다른 해결책이 요구된다.
그림 1.1: Interconnection network의 기능적 개요. T1~T6의 단말이 양방향 채널로 네트워크에 연결되어 있다. 각 채널의 양 끝에 있는 화살표는 데이터가 양방향으로 이동할 수 있음을 나타낸다.
Interconnection network는 어디에서 사용되는가? 서로 연결해야 할 두 개 이상의 구성 요소가 있는 거의 모든 디지털 시스템에서 사용된다. 가장 일반적인 응용처는 컴퓨터 시스템과 통신 스위치이다.
컴퓨터 시스템에서는 프로세서와 메모리, I/O 장치와 I/O 컨트롤러를 연결한다.
통신 스위치 및 네트워크 라우터에서는 입력 포트를 출력 포트에 연결한다.
제어 시스템에서는 센서와 액추에이터를 프로세서에 연결한다.
즉, 시스템의 두 구성 요소 간에 비트를 전송하는 곳이라면 어디든 interconnection network가 존재할 가능성이 높다.
1980년대 후반까지만 해도 이러한 많은 응용은 매우 단순한 interconnection인 multi-drop bus로 구현되었다. 만약 이 책이 그 시기에 쓰였다면, 아마도 버스 설계에 관한 책이 되었을 것이다. 현재도 버스는 많은 응용에서 중요하므로, 이 책의 Chapter 22에서 별도로 다룬다.
하지만 오늘날의 고성능 시스템에서는 point-to-point interconnection network가 대부분의 연결을 담당한다. 또한 전통적으로 버스를 사용해왔던 시스템들도 매년 네트워크 방식으로 전환되고 있다. 이러한 전환은 비균등한 성능 스케일링에 기인한다. 프로세서 성능과 함께 interconnection 성능 요구도 매년 약 50%씩 증가하는 반면, 배선(wire)은 더 빨라지지 않는다. 빛의 속도나 24 게이지 구리선의 감쇠 특성은 반도체 기술이 개선되어도 나아지지 않는다. 결과적으로 버스는 요구되는 bandwidth를 따라가지 못하고 있으며, 병렬성과 더 높은 속도를 제공하는 point-to-point interconnection network가 이를 대체하고 있다.
Interconnection network가 중요한 이유는 무엇인가? 이는 많은 시스템에서 성능의 제한 요소이기 때문이다.
프로세서와 메모리 사이의 interconnection network는 memory latency와 memory bandwidth를 결정하며, 이는 시스템 성능의 핵심 요소이다.
통신 스위치에서의 interconnection network (이 문맥에서는 fabric이라 부르기도 함)는 용량(capacity) — 즉 데이터 전송률과 포트 수 — 을 결정한다.
Interconnection 요구는 배선의 물리적 한계를 훨씬 앞질러 성장하고 있기 때문에, 대부분의 시스템에서 interconnection은 치명적인 병목 요소가 되었다.
또한 interconnection network는 전용 배선(dedicated wiring)에 비해 매력적인 대안이다. 이는 낮은 duty factor를 가지는 여러 신호들이 제한된 배선 자원을 공유할 수 있게 하기 때문이다. 예를 들어, Figure 1.1에서 각 단말이 100 클럭마다 다른 모든 단말에 1워드씩 통신한다고 하자. 모든 단말쌍 사이에 전용 채널을 제공하면 30개의 단방향 채널이 필요하며, 이 채널들은 99%의 시간 동안 유휴 상태일 것이다. 대신 여섯 개의 단말을 ring network로 연결하면 6개의 채널만 필요하다 (T1→T2, T2→T3, ..., T6→T1). 이 경우 채널 수는 5배 줄고, duty factor는 1%에서 12.5%로 증가한다.
1.2 Interconnection Networks의 용도
Interconnection network 설계에 요구되는 조건을 이해하려면, 디지털 시스템에서 이것이 어떻게 사용되는지를 살펴보는 것이 유용하다. 이 섹션에서는 세 가지 일반적인 용도를 살펴보며, 각각의 응용이 네트워크 설계에 어떤 요구를 가하는지 살펴본다. 특히 다음과 같은 네트워크 파라미터를 응용에 따라 분석한다:
단말의 수
각 단말의 최대 대역폭 (peak bandwidth)
각 단말의 평균 대역폭 (average bandwidth)
요구되는 지연 시간 (latency)
메시지 크기 혹은 메시지 크기의 분포
예상되는 트래픽 패턴
요구되는 Quality of Service
요구되는 신뢰도 및 가용성
단말 수 (또는 포트 수)는 네트워크에 연결해야 할 구성 요소의 수에 해당한다. 하지만 단말 수만 아는 것으로는 부족하고, 각 단말이 네트워크와 어떻게 상호작용하는지도 알아야 한다.
각 단말은 네트워크에서 일정량의 대역폭을 요구하며, 이는 보통 bit/s로 표현된다. 특별한 언급이 없으면 단말의 입출력 대역폭은 대칭(symmetric)하다고 가정한다.
Peak bandwidth는 단기간에 단말이 요구할 수 있는 최대 데이터율이고,
Average bandwidth는 장기적으로 요구되는 평균 데이터율이다.
다음 섹션에서 processor-memory interconnect 설계를 통해 보여주듯, peak와 average bandwidth 모두를 아는 것이 네트워크의 구현 비용을 최소화하는 데 중요하다.
또한 네트워크가 메시지를 수신하고 전달하는 속도 외에도, 개별 메시지를 전달하는 데 걸리는 시간, 즉 메시지 지연 시간(latency) 역시 명시되어야 한다. 이상적인 네트워크는 고대역폭과 저지연을 모두 지원하지만, 이 두 가지 특성 사이에는 종종 트레이드오프가 존재한다. 예를 들어, 고대역폭을 지원하는 네트워크는 네트워크 자원을 계속 바쁘게 유지하므로, resource contention이 자주 발생한다. 즉, 여러 메시지가 동시에 동일한 공유 자원을 사용하려 하면, 하나를 제외한 나머지는 해당 자원이 사용 가능해질 때까지 기다려야 하므로 latency가 증가한다. 반대로, 대역폭 요구를 줄이면 자원 사용률이 낮아지므로 latency도 감소할 수 있다.
Message size, 즉 메시지의 비트 길이도 중요한 설계 고려 요소이다. 메시지가 작을 경우, 네트워크 오버헤드가 성능에 더 큰 영향을 미치게 된다. 반면 메시지가 크면 오버헤드를 메시지 길이에 걸쳐 분산시켜 감쇠시킬 수 있다. 많은 시스템에서는 여러 가지 가능한 메시지 크기가 존재한다.
각 단말에서 보낸 메시지가 가능한 목적지 단말 전체에 어떻게 분포되는가를 트래픽 패턴(traffic pattern)이라 한다. 예를 들어, 각 단말이 모든 다른 단말에 동일한 확률로 메시지를 보내는 경우를 무작위 트래픽 패턴(random traffic pattern)이라 한다. 반대로 단말들이 주로 가까운 단말에만 메시지를 보내는 경향이 있다면, underlying network는 이러한 공간적 지역성(spatial locality)을 활용하여 비용을 줄일 수 있다. 그러나 어떤 네트워크에서는 임의의 트래픽 패턴에서도 사양이 유지되는 것이 중요하다.
일부 네트워크에서는 QoS (Quality of Service) 요구사항도 있다. 대략적으로 QoS란 특정 서비스 정책 하에서 자원을 공정하게 분배하는 것이다. 예를 들어, 여러 메시지가 동일한 네트워크 자원을 놓고 경쟁할 때, 이를 해결하는 방식은 여러 가지다. 메시지가 해당 자원을 기다린 시간에 따라 선착순(First-Come, First-Served) 방식으로 처리할 수도 있고, 네트워크 내에서 가장 오래 있었던 메시지에 우선순위(priority)를 줄 수도 있다. 어떤 자원 할당 정책을 선택할지는 네트워크에서 요구하는 서비스에 따라 달라진다.
마지막으로, 신뢰도(reliability)와 가용성(availability)도 interconnection network의 설계에 영향을 준다.
신뢰도란 메시지를 올바르게 전달하는 네트워크의 능력을 말한다. 대부분의 경우 메시지는 100% 전달되어야 하며 손실이 없어야 한다. 이를 실현하기 위해 에러 검출 및 수정 하드웨어, 상위 소프트웨어 프로토콜, 또는 이들의 조합을 사용할 수 있다.
일부 경우, 이후에 설명할 packet switching fabric에서는 극소수의 메시지가 손실되는 것을 허용할 수도 있다.
네트워크의 가용성은 전체 시간 중 네트워크가 정상적으로 작동한 비율을 의미한다. 인터넷 라우터의 경우, 일반적으로 99.999% (5 nines) 가용성이 요구되며, 이는 연간 총 다운타임이 5분 미만임을 의미한다. 그러나 네트워크를 구성하는 부품은 종종 분당 여러 번 고장나기도 하므로, 이러한 수준의 가용성을 달성하려면 네트워크는 장애를 감지하고 신속하게 복구하면서도 동작을 지속해야 한다.
1.2.1 Processor-Memory Interconnect
그림 1.2는 processor와 memory를 연결하기 위한 interconnection network의 두 가지 구조를 보여준다.
(a) Dance-hall 구조는 P개의 프로세서와 M개의 메모리 뱅크를 interconnection network로 연결한다.
(b) Integrated-node 구조는 processor와 memory를 하나의 노드에 통합하고, 이 로컬 메모리에는 switch C를 통해 직접 접근할 수 있게 한다.
Dance-hall이라는 이름은 구식 댄스홀처럼, 프로세서들이 네트워크 한쪽에 줄지어 서고, 메모리들이 반대쪽에 줄지어 서는 배치를 닮았기 때문이다.
Table 1.1은 이 두 구성에서 네트워크에 요구되는 파라미터를 요약한 것이다.
ParameterValue
Processor ports
1–2,048
Memory ports
0–4,096
Peak bandwidth
8 Gbytes/s
Average bandwidth
400 Mbytes/s
Message latency
100 ns
Message size
64 또는 576 bits
Traffic patterns
arbitrary (임의)
Quality of service
없음
Reliability
메시지 손실 없음
Availability
0.999 ~ 0.99999
예를 들어 Cray T3E와 같이 최대 구성 시 2,176개의 processor ports를 가진 경우도 있으며, 단일 프로세서 시스템에서는 1개의 포트만 필요하다. 64~128개의 프로세서를 가진 구성은 고급 서버에서 흔하며, 이 수는 시간이 갈수록 증가하는 추세다.
Integrated-node 구성에서는 각 processor port가 memory port 역할도 한다.
반면 dance-hall 구성에서는 memory port 수가 processor port보다 훨씬 많다. 예: 어떤 벡터 프로세서는 32개의 processor port가 4,096개의 memory bank에 접근한다. 이는 memory bandwidth를 극대화하고 bank conflict(동일한 bank에 여러 프로세서가 동시에 접근하는 경우)를 줄이기 위한 것이다.
현대의 마이크로프로세서는 초당 약 10억 개의 명령어를 실행하며, 각 명령어는 memory에서 64비트 word 두 개를 요구할 수 있다 (하나는 명령어 자체, 다른 하나는 데이터). 이 중 하나가 캐시에 없으면 일반적으로 8-word block을 memory에서 가져온다. 만약 매 cycle마다 2 word를 memory에서 가져와야 한다면 16GB/s의 bandwidth가 필요하다.
다행히도:
모든 명령어가 메모리 참조를 하는 것은 아니며 (약 1/3),
cache hit ratio가 높아서 실제 memory 접근 수는 줄어든다.
따라서 평균 bandwidth는 훨씬 낮아져 보통 400MB/s 수준이 된다. 하지만 burst traffic을 처리하기 위해서는 8GB/s의 peak bandwidth가 여전히 필요하다. 만약 peak bandwidth를 너무 제한하면 갑작스러운 요청이 발생했을 때 네트워크 포트가 막혀 serialization이 발생하고, 이는 지연(latency)을 증가시킨다. 이 현상은 막힌 싱크대가 천천히 물을 빼내는 것에 비유할 수 있다.
또한, memory latency는 processor 성능에 민감한 영향을 미친다. Table 1.1에서는 기본 메모리 시스템의 latency를 100ns로 보고 있는데, 네트워크가 추가로 100ns를 더한다면 실효 메모리 지연이 2배가 된다.
캐시에 없는 load/store 명령어는 read-request 또는 write-request packet으로 변환되어 네트워크를 통해 해당 memory bank로 전송된다.
Read-request packet: 읽을 memory address 포함
Write-request packet: 주소 + 데이터 word 또는 캐시라인 포함
memory bank는 요청을 수행한 후, 응답 packet을 다시 보낸다 (read-reply 또는 write-reply).
이 시점에서, message와 packet을 구분하기 시작한다.
Message는 processor 또는 memory와 네트워크 간의 전송 단위이고,
Packet은 그 message가 네트워크 내부에서 분할되거나 고정 길이로 변환된 형태이다.
Processor-memory interconnect에서는 message와 packet이 1:1 대응한다고 가정할 수 있다.
그림 1.3: 두 개의 packet format
Read-request / Write-reply: 64비트 헤더 + 주소
Read-reply / Write-request: 위의 64비트 정보 + 512비트 데이터 (캐시라인) = 576비트
이러한 interconnect는 QoS를 요구하지 않는다. 그 이유는 시스템이 자체 조절(self-throttling) 메커니즘을 갖기 때문이다. 네트워크 혼잡이 발생하면 요청 지연이 늘어나고, processor는 응답을 기다리며 유휴 상태가 된다. 이로 인해 새로운 요청이 줄어들고 혼잡이 완화된다. 이런 안정화 특성 덕분에 QoS는 필요하지 않다.
하지만 신뢰성(reliability)은 필수이다.
memory request/reply packet이 절대 손실되면 안 된다.
손실되면 해당 memory operation이 무한히 대기 상태가 되어, 최소한 사용자 프로그램이 crash되고, 심하면 시스템 전체가 다운될 수 있다.
신뢰성을 갖추기 위해, 일부 시스템은 acknowledgment 기반 재전송 프로토콜을 쓸 수 있다 (자세한 내용은 Chapter 21 참조). 하지만 이는 latency를 증가시켜 processor-memory interconnect에는 적합하지 않다.
이러한 시스템은 보통 가용성 99.9% ~ 99.999% 수준을 요구한다.
1.2.2 I/O Interconnect
그림 1.4: 일반적인 I/O 네트워크는 여러 개의 host adapter(HA)를 더 많은 수의 I/O 디바이스(예: 디스크 드라이브)에 연결한다.
I/O 네트워크는 granularity와 timing 면에서 processor-memory 네트워크와 다르다. 특히 latency에 대한 관용성 증가는 네트워크 설계를 완전히 다른 방향으로 이끈다.
디스크 작업은 일반적으로 4Kbyte 이상의 sector 단위로 수행된다. 디스크의 회전 지연(rotational latency)과 헤드 이동 시간 때문에, 섹터 하나를 접근하는 데 걸리는 latency는 수 밀리초에 달할 수 있다. 디스크 읽기 작업은 host adapter에서 디스크 주소(device, sector)와 메모리 블록 주소를 지정한 control packet을 전송하면서 시작된다. 디스크는 이 요청을 수신하고 헤드를 해당 섹터로 이동시킨 뒤, 해당 sector를 읽고, 지정된 메모리 블록으로의 response packet을 host adapter에 보낸다.
표 1.2 I/O interconnection network의 파라미터
ParameterValue
Device ports
1–4,096
Host ports
1–64
Peak bandwidth
200 Mbytes/s
Average bandwidth
1 Mbytes/s (devices)
64 Mbytes/s (hosts)
Message latency
10 μs
Message size
32 bytes 또는 4 Kbytes
Traffic patterns
arbitrary
Reliability
no message loss (소량은 허용)a
Availability
0.999 ~ 0.99999
a) 일부 메시지 손실은 허용된다. 실패한 메모리 접근보다 실패한 I/O 작업의 복구가 더 유연하게 처리되기 때문이다.
디스크 포트의 peak-to-average bandwidth ratio는 매우 크다. 디스크가 연속된 sector를 전송할 때는 200MB/s의 속도로 데이터를 읽을 수 있지만, 실제로는 각 sector 간에 헤드 이동 시간이 평균 5ms 이상 걸려서, 평균 데이터 속도는 1MB/s 이하로 낮아진다. Host 포트는 64개의 디스크 포트 트래픽을 집계하므로 이보다는 안정적인 대역폭을 가진다.
이처럼 peak과 average bandwidth 차이가 큰 경우, 모든 디바이스의 최대 대역폭을 동시에 지원하는 네트워크를 설계하면 비용이 매우 높아진다. 반대로 평균 대역폭만 지원하도록 설계하면, processor-memory 예시처럼 serialization latency 문제가 생긴다. 따라서 여러 디바이스의 요청을 집계 포트(aggregate port)로 concentration하는 방식이 효과적이다. 이로 인해 평균 bandwidth 수요는 커지지만, 실제로 동시에 최고 대역폭을 요구하는 디바이스는 극소수에 불과하므로 과도한 serialization 없이 저비용 구현이 가능하다.
메시지의 payload는 이중 분포(bimodal)를 가지며, 두 가지 크기 간의 차이가 크다.
짧은 32바이트 메시지: read 요청, write 완료 ack, 디스크 제어용
긴 메시지 (예: 4Kbyte, 실제는 8Kbyte 포함됨): read-reply, write-request 등
디스크 작업은 본질적으로 latency가 크고, 전송 단위가 크기 때문에, 이 네트워크는 latency에 민감하지 않다. 예를 들어, latency가 10μs로 증가해도 성능 저하는 무시할 수 있는 수준이다. 이러한 관용성 덕분에 processor-memory에 비해 효율적인 네트워크를 훨씬 쉽게 구축할 수 있다.
한편, 클러스터 기반 병렬 컴퓨터에서 사용하는 inter-processor 통신 네트워크는 bandwidth와 granularity 면에서 I/O 네트워크와 유사하므로 따로 다루지 않는다. 이러한 네트워크는 system-area network (SAN)라고 불리며, I/O 네트워크와의 주요 차이는 latency에 더 민감하다는 점이다 (보통 몇 마이크로초 이하 요구).
한편, 디스크 스토리지를 기업의 핵심 데이터를 저장하는 데 사용하는 경우, 매우 높은 가용성이 요구된다. 스토리지 네트워크가 멈추면 곧 비즈니스 전체가 중단되기 때문이다. 이 때문에 0.99999 (five nines) 수준 — 연간 다운타임 5분 이하 — 이 일반적이다.
1.2.3 Packet Switching Fabric
Packet switching fabric은 통신 네트워크 스위치 및 라우터에서 버스와 크로스바를 대체하는 역할을 한다. 이 경우 interconnection network는 보다 큰 네트워크(IP 기반의 LAN 또는 WAN)의 라우터 내부 요소로 동작한다.
그림 1.5: 스위칭 패브릭으로 interconnection network를 사용하는 네트워크 라우터. 여러 line card 간의 패킷 전송을 담당한다.
대규모 네트워크 채널 (보통 2.5Gbps 또는 10Gbps 광섬유)을 종료하는 여러 line card들이 있고, 각 라인카드는:
패킷을 받아서 목적지를 파악하고,
QoS 정책 준수 여부를 검사하고,
패킷의 특정 필드를 재작성하고,
통계 정보를 업데이트한 후,
해당 패킷을 fabric으로 전달한다.
fabric은 이 패킷을 출발지 line card에서 목적지 line card로 전송하는 역할을 수행한다. 목적지 line card는 해당 패킷을 큐에 저장하고, 이후 출력 채널로 송신하도록 스케줄링한다.
표 1.3 Packet switching fabric의 파라미터
ParameterValue
Ports
4–512
Peak Bandwidth
10 Gbits/s
Average Bandwidth
7 Gbits/s
Message Latency
10 μs
Packet Payload Size
40–64 Kbytes
Traffic Patterns
arbitrary
Reliability
10⁻¹⁵ 이하의 손실률
Quality of Service
필요함
Availability
0.999 ~ 0.99999
라우터에서 사용하는 프로토콜에 따라 패킷 크기가 달라지지만, 예를 들어 IP의 경우 40바이트~64Kbytes까지 다양하며, 일반적으로는 40, 100, 1,500바이트 패킷이 많다. 이처럼 다른 예시들과 마찬가지로, 이 네트워크도 짧은 제어 메시지와 큰 데이터 전송 간의 분리가 있다.
스위칭 패브릭은 processor-memory나 I/O 네트워크처럼 self-throttling 하지 않다. 각 line card는 네트워크 혼잡과 무관하게 계속 패킷을 전송하며, 동시에 일부 패킷 클래스에는 보장된 bandwidth를 제공해야 한다. 이를 위해 fabric은 non-interfering해야 한다. 즉:
a로 가는 트래픽이 많더라도,
b로 가는 트래픽의 bandwidth를 침해하지 않아야 한다.
이는 a와 b 간 트래픽이 자원을 공유하더라도 마찬가지다.
이런 비간섭성 요구는 fabric 구현에 특별한 제약 조건을 부과한다.
흥미로운 점은, 일부 경우 극히 낮은 확률의 패킷 손실은 허용 가능하다는 것이다. 예를 들어:
입력 광섬유에서의 비트 오류 (10⁻¹² ~ 10⁻¹⁵ 확률),
line card 큐 오버플로우 등, 이미 다른 이유로 인해 패킷이 손실될 수 있기 때문에, 내부 네트워크 bit error와 같은 매우 드문 상황에서는 패킷을 드롭해도 무방하다. 단, 이 손실률은 다른 원인보다 훨씬 낮아야 한다.
이는 processor-memory interconnect와는 대조된다. 이 경우 패킷 1개라도 손실되면 시스템 전체가 정지될 수 있기 때문이다.
1.3 Network Basics
특정 응용 분야(앞에서 설명한 바와 같은)의 성능 사양을 충족시키기 위해, 네트워크 설계자는 topology, routing, flow control을 구현함에 있어 기술적 제약 내에서 작업해야 한다. 앞에서 언급했듯, interconnection network의 효율성의 핵심은 통신 자원이 공유된다는 점이다. 각 terminal 쌍마다 전용 채널을 만드는 대신, interconnection network는 공유 채널로 연결된 공유 router node 집합으로 구현된다. 이 노드들의 연결 패턴이 곧 topology를 정의한다.
메시지는 출발 terminal에서 목적지 terminal까지 여러 shared channel과 node를 거쳐 전달된다. 좋은 topology는 패키징 기술의 특성 — 예: 칩의 핀 수, 캐비닛 간 연결 가능한 케이블 수 — 을 잘 활용하여 network bandwidth를 극대화할 수 있어야 한다.
Toplogy가 정해지면, 메시지가 목적지에 도달하기까지의 가능한 경로(노드와 채널의 시퀀스)는 여러 가지가 될 수 있다. Routing은 메시지가 어떤 경로를 실제로 따를지를 결정한다. 좋은 경로 선택은 경로 길이(보통 노드 수나 채널 수로 측정)를 최소화하고, 동시에 공유 자원에 걸리는 부하(load)를 고르게 분산시켜야 한다.
경로가 길수록 latency가 늘어나고,
자원 중 어떤 것은 과하게 사용되고, 다른 것은 유휴 상태인 load imbalance가 발생하면 network의 총 bandwidth는 줄어든다.
Flow control은 시간 흐름에 따라 어떤 메시지가 어떤 network 자원을 사용할지를 결정한다. 자원 사용률이 증가할수록 flow control의 중요성은 커진다. 좋은 flow control은 최소 지연으로 packet을 전달하면서, 높은 부하 상태에서도 자원을 놀리지 않는다.
1.3.1 Topology
Interconnection networks는 router node들과 channel들로 구성되며, topology는 이들의 배치 방식을 의미한다. Topology는 도로 지도에 비유할 수 있다. Channel은 자동차가 다니는 도로처럼 packet을 한 router node에서 다른 router node로 운반한다. 예를 들어 Figure 1.6에 나온 network는 16개의 노드로 구성되며, 각 노드는 4개의 이웃과 양방향 연결(총 8개의 채널)되어 있다. 이 네트워크는 torus topology이다. 각 노드는 terminal과 직접 연결된 direct network 구성이다.
좋은 topology는 사용 가능한 패키징 기술의 특성을 활용하여 최소 비용으로 응용의 bandwidth와 latency 요구를 충족시킨다. Topology는 시스템 중간(bisection)을 가로지르는 bisection bandwidth를 최대한 활용해야 한다.
Figure 1.6: 4×4 torus (또는 4-ary 2-cube) topology. 각 노드는 4개의 이웃과 각각 송수신 채널로 연결되어 총 8개의 채널을 가진다.
Figure 1.7은 Figure 1.6의 네트워크를 실제로 어떻게 패키징할 수 있는지를 보여준다.
4개의 노드를 하나의 printed circuit board (PCB)에 배치하고,
4개의 보드를 backplane 보드로 연결한다 (PC에서 PCI 카드가 motherboard에 꽂히듯).
이 시스템에서 bisection bandwidth는 backplane을 통해 전달될 수 있는 최대 bandwidth이다.
backplane이 256개의 신호선(signal)을 가진다고 가정하고,
각 signal이 1Gbps 속도로 동작한다면, 전체 bisection bandwidth는 256Gbps이다.
Figure 1.7: 16-node torus topology의 패키징. 4개의 PCB가 backplane을 통해 연결된다. backplane의 너비를 가로지르는 256개 신호선이 이 시스템의 bisection bandwidth를 결정한다.
다시 Figure 1.6을 보면, 중간을 가로지르는 unidirectional channel이 총 16개이다. (그림상의 선 하나는 양방향 채널 2개를 의미함) 따라서 bisection bandwidth를 포화시키려면 각 채널은 256/16 = 16 signals를 가져야 한다. 한편, 각 노드는 단일 IC 칩에 패키징되며, 칩은 최대 128개의 핀만 사용할 수 있다. 이 topology는 노드당 8개 채널이므로, 각 채널당 할당 가능한 핀 수는 128/8 = 16 signals이다. → 핀 제한과 포화 조건이 일치하는 이상적인 구성이다.
반면, Figure 1.8과 같이 16-node ring topology를 고려해보자.
노드당 4개 채널만 존재하므로 핀 제한은 128/4 = 32 signals/channel이 된다.
bisection을 통과하는 채널은 4개이므로 이상적인 설계는 채널당 256/4 = 64 signals/channel이지만,
핀 제한으로 인해 실제 채널 폭은 32 signal로 제한된다. → 결국, ring topology는 torus topology의 절반 bandwidth만 제공한다.
Figure 1.8: 동일한 기술 제약 조건 하에서 ring topology는 torus보다 낮은 throughput을 가지지만 latency는 더 낮을 수 있다.
그러나 bandwidth만이 topology 선택의 기준은 아니다. 다른 응용에서 필요한 bandwidth가 16Gbps 수준으로 낮지만 latency가 중요하다면, 4096-bit의 긴 packet을 사용하고 있다면, → 작은 hop 수와 낮은 serialization latency의 균형을 맞추는 topology가 필요하다.
Hop count: 메시지가 목적지까지 평균적으로 거치는 노드/채널 수
Node degree를 높이면 hop count는 줄지만,
채널 수가 늘어나면 채널 폭은 좁아지고, 긴 패킷은 serialization latency가 커진다.
예를 들어,
random traffic을 가정하면, torus의 평균 거리 = 2 hops, ring = 4 hops
→ ring의 총 latency: 80 + 128 = 208ns → torus의 총 latency: 40 + 256 = 296ns
결론: 긴 패킷에서는 오히려 ring topology가 latency 면에서 우수할 수 있다.
요약: 모든 응용에 적합한 최적의 topology는 없다. 제약 조건과 요구사항에 따라 적절한 topology가 달라진다.
1.3.2 Routing
Routing은 source terminal node에서 destination terminal node까지의 경로를 결정한다. 경로는 channel들의 순서 집합 P = {c₁, c₂, ..., cₖ} 로 정의되며,
cᵢ의 출력 노드 = cᵢ₊₁의 입력 노드
c₁의 입력 = source
cₖ의 출력 = destination
어떤 네트워크에서는 source→destination 경로가 유일할 수도 있지만, Figure 1.6의 torus network처럼 경로가 여러 개 존재할 수도 있다. 이럴 경우, 좋은 routing 알고리즘은 어떤 traffic pattern에서도 채널 간 부하를 고르게 분산해야 한다.
topology는 roadmap,
routing은 네트워크 교차로에서 방향을 정하는 운전자의 turning decision이다.
부하 균형을 위해, 일부 경로에 트래픽이 몰리지 않도록 해야 한다.
Figure 1.9(a): node 01에서 node 22로 가는 dimension-order routing → x방향으로 먼저 이동 후, y방향으로 이동 (01 → 21 → 22). → 최소 경로 (min-hop). 이 경우 가능한 최소 경로가 총 6개 존재한다.
Dimension-order routing은 간단하고 minimal하지만, 일부 traffic pattern에서는 심각한 load imbalance를 유발할 수 있다. 예를 들어, Figure 1.9(a)에서 node 11에서 node 20으로 가는 또 다른 dimension-order 경로를 추가한다고 하자. 이 경로 역시 node 11에서 node 21로 가는 채널을 사용하므로, 해당 채널의 부하(load)가 2배가 된다.
Channel load는 terminal node들이 해당 채널을 통해 보내려고 하는 평균 bandwidth를 의미한다. 이 load를 terminal이 네트워크에 주입할 수 있는 최대 rate로 정규화하면, 해당 채널의 load는 2가 된다. 더 나은 routing 알고리즘을 사용하면 이 값을 1로 줄일 수 있다. Dimension-order routing은 특정 채널에 불필요한 중복 부하를 발생시키므로, 이 traffic pattern 하에서 네트워크의 전체 bandwidth는 최대의 절반에 불과하다.
일반적으로 deterministic routing algorithm — 즉 source-destination 쌍마다 고정된 단일 경로를 선택하는 알고리즘 — 은 이러한 load imbalance로 인해 낮은 bandwidth를 보이는 경향이 있다. Routing 알고리즘 설계와 관련된 이와 같은 이슈는 Chapters 8–10에서 더 자세히 다룬다.
1.3.3 Flow Control
Flow control은 packet이 경로를 따라 진행함에 따라 자원의 할당을 관리한다. 대부분의 interconnection network에서 핵심 자원은 channel과 buffer이다. Channel은 노드 간에 packet을 운반하는 역할을 하며, Buffer는 각 노드 내에 구현된 저장 공간(레지스터나 메모리 등)으로, packet이 다음 자원을 기다리는 동안 임시로 저장된다.
이전의 아날로지를 이어서 보면:
Topology는 지도,
Routing은 교차로에서의 steering 결정,
Flow control은 신호등이다. → 즉, 차(=packet)가 다음 도로(channel)로 진행해도 되는지, 혹은 다른 차를 위해 parking lot(buffer)으로 비켜야 하는지를 결정한다.
Figure 1.9: (a) Dimension-order routing: x 방향 → y 방향 (b) Non-minimal route: 최소 경로보다 더 많은 hop을 거친다
Topology와 Routing의 잠재적 성능을 실현하려면, Flow control 전략은 자원 충돌(resource conflict)을 피해야 한다. 예: 어떤 packet이 비어 있는 채널을 사용할 수 있음에도, 혼잡한 채널 때문에 막힌 다른 packet이 점유 중인 buffer를 기다리느라 진행하지 못하는 상황은 피해야 한다. → 이 상황은, 좌회전 하려는 차 때문에 직진하려는 차가 막히는 것과 같다. → 해결책은 도로에 좌회전 전용 차선을 추가하는 것처럼, 자원 의존을 분리해주는 것이다.
좋은 flow control은 공정하고(fair), deadlock을 피해야 한다.
공정하지 않으면 어떤 packet은 무한정 대기할 수 있으며,
Deadlock은 여러 packet이 서로 자원을 기다리며 순환적으로 막혀 있는 상태를 의미한다. → 도로에서의 gridlock에 해당한다.
Flow control 방식은 종종 시간-공간 다이어그램(time-space diagram)으로 표현된다.
Figure 1.10: Flow control 비교
(a) Store-and-forward: 각 채널마다 packet 전체(5 flits)가 전달되어야 다음 채널로 진행 가능
(b) Cut-through: 각 flit이 도착하는 대로 다음 채널로 바로 진행, pipelining
수평축: 시간(cycle)
수직축: 공간(channel ID)
Flit (flow control digit): flow control 수준에서 가장 작은 단위 → flit을 고정된 크기로 정하면 router 설계가 간단해지고, 길이가 일정하지 않은 packet도 처리할 수 있다.
→ Flow control 방식은 latency에 큰 영향을 미친다.
Flow control의 자세한 내용은 Chapters 12–13, 관련 문제들 (deadlock, livelock, tree saturation, QoS 등)은 Chapters 14–15에서 다룬다.
1.3.4 Router Architecture
Figure 1.11: router의 block diagram
입력 채널마다 buffer
crossbar switch
allocator
Figure 1.6에 나온 16개의 노드 중 하나의 내부를 단순화하여 나타낸 그림이다.
각 입력 채널에는 buffer가 연결되어 있고,
buffer에 들어온 flit은 경로 상 다음 노드(router)의 buffer 공간이 확보되면 → crossbar switch에 대한 접근 권한을 요청한다.
Crossbar switch는 어느 입력 buffer든지 어느 출력 채널로든 연결할 수 있으나,
입력 하나는 출력 하나에만, 출력 하나도 입력 하나에만 연결 가능하다.
Allocator는 crossbar와 공유 자원에 대한 요청을 처리한다. → flit이 다음 router로 진행하려면,
다음 노드의 buffer 공간 확보
다음 채널의 bandwidth 확보
crossbar 통과 권한 확보
Router architecture는 Chapters 16–21에서 상세히 다룬다.
1.3.5 Performance of Interconnection Networks
Interconnection network의 성능은 보통 latency vs. offered traffic curve로 설명된다.
Figure 1.12: offered traffic(수평축)에 따른 평균 latency(수직축)
Latency: packet의 첫 비트가 source terminal에 도착한 시점부터, 마지막 비트가 destination terminal에 도착한 시점까지 걸린 시간
Offered traffic: 각 source terminal이 생성하는 평균 트래픽 (bits/s)
이 곡선을 정확히 얻기 위해선 트래픽 패턴 (예: random traffic)도 명시해야 한다. → 이 곡선은 정확하긴 하나, 폐쇄형 수식이 없으며 discrete-event simulation으로 계산된다.
설계 초기 단계에서는 topology, routing, flow control 관점에서 점진적으로 성능을 이해하는 방식이 유용하다.
Zero-load latency는 네트워크에서 경쟁 없이 packet이 전달될 때의 최소 평균 지연 시간이다.
구성 요소: serialization latency + hop latency
예:
topology = torus (Figure 1.6)
L = 512 bits,
channel bandwidth = b = 16 Gbps
routing: minimal, random traffic → serialization latency = L/b = 32ns → 평균 hop 수 = Hₘᵢₙ = 2 → router latency tᵣ = 10ns → hop latency = 2 × 10 = 20ns → 최소 latency = 32 + 20 = 52ns
Routing 알고리즘이 실제로 사용하는 hop 수 Hₐᵥg를 고려하면, 이보다 큰 latency가 된다 (Hₐᵥg ≥ Hₘᵢₙ). 또한 flow control이 추가로 성능을 저하시킬 수 있다.
앞서 설명한 Figure 1.12에서, 실제 zero-load latency T₀는 topology, routing, flow control에 의해 결정되는 제약을 모두 포함한다. 이러한 점진적으로 정밀해지는 latency의 상한들은 Figure 1.12에서 수평 비대칭선(horizontal asymptote)으로 표시된다.
비슷한 방식으로 throughput(처리율)에 대해서도 상한을 설정할 수 있다.
Source는 일정량의 traffic을 network에 제공하지만,
Throughput, 또는 accepted traffic은 destination terminal에 성공적으로 전달된 데이터율(bits/s)이다.
예를 들어, random traffic을 가정하면 전체 traffic의 절반이 network의 bisection을 통과해야 한다.
bisection은 16개 채널, 총 bandwidth B_c = 256 Gbps
node당 traffic 한계 = 2B_c / N = 32 Gbps (N=16)
이는 traffic이 bisection을 균등하게 분산시킨다는 이상적인 가정 하에서만 성립한다.
→ 실제 routing 알고리즘 R의 효과를 고려한 throughput Θ_R은 불균형이 존재하면 이보다 낮을 수 있다 (Θ_R ≤ 2B_c / N) → Flow control이 자원 의존성 때문에 채널을 유휴 상태로 만든다면, 실제 saturation throughput λ_s는 Θ_R보다도 훨씬 낮을 수 있다.
이러한 throughput의 3단계 상한은 Figure 1.12에서 수직 비대칭선(vertical asymptote)으로 표시된다.
이렇게 topology → routing → flow control로 점진적으로 성능을 분석하는 방식은 각 설계 요소가 성능에 어떻게 영향을 미치는지 불필요한 복잡성 없이 확인할 수 있게 해준다. 예: topology 선택이 latency에 미치는 영향은, routing과 flow control을 따로 고려하지 않고도 파악 가능하다.
반면, 성능 분석을 한 번에 모두 고려하려 하면 개별 설계 선택이 끼치는 영향이 흐려진다.
이러한 성능 모델링의 점진적 접근법을 수립한 후, 전체적인 관점에서의 성능 분석은 Chapters 23–25에서 다룬다. 이들 챕터에서는:
성능 측정에서의 미묘한 문제
queueing theory 및 probability theory 기반의 분석 기법
simulation을 통한 성능 측정 방법
예시 측정 결과들을 설명한다.
1.4 History
Interconnection network는 수십 년에 걸쳐 발전해 온 풍부한 역사를 가지고 있다. 발전 경로는 크게 세 가지 병렬적 흐름으로 진행되었다:
Telephone switching networks
Inter-processor communication
Processor-memory interconnect
Telephone switching networks
전화가 등장한 이래로 존재해온 시스템이다. 초기 telephone network는 전기기계식 crossbar 또는 step-by-step switch로 구축되었으며, 1980년대까지도 많은 지역 전화 교환기는 여전히 electro-mechanical relay로 구성되어 있었다. 반면, 장거리 통화용(toll) switch는 이미 전자식, 디지털화가 완료되었다.
주요 발전 사례:
1953년: Clos network (non-blocking multistage)
1962년: Beneš network → 현재도 많은 대형 telephone switch는 Clos 또는 Clos 기반 네트워크로 구현된다.
Inter-processor interconnection networks
초기의 processor 간 연결은 2D 배열 내 이웃한 processor의 레지스터를 직접 연결하는 방식이었다. 예: 1962년 Solomon machine [172] — 이들 초기 네트워크는 routing 기능이 없었기 때문에, 이웃이 아닌 processor와 통신하려면 중간 processor가 명시적으로 relay해야 했다. → 이는 성능 저하와 프로그래밍 복잡성 증가로 이어졌다.
1980년대 중반부터는 processor 개입 없이 메시지를 forwarding할 수 있는 router chip이 등장했다. 예: torus routing chip [56]
Topology 측면에서는 시간 흐름에 따라 다양한 유행이 있었다:
초기 (Solomon, Illiac, MPP 등): 2D mesh 또는 torus → 물리적 규칙성 때문
1970년대 후반부터: binary n-cube (hypercube) → low diameter → 대표 기기: Ametek S14, Cosmic Cube, nCUBE, Intel iPSC 시리즈
하지만 1980년대 중반 이후 실제 패키징 제약 하에서는 low-dimensional network가 hypercube보다 우수하다는 사실이 밝혀졌고, → 다시 대부분의 시스템이 2D 또는 3D mesh/torus로 회귀하였다.
대표 기기:
J-machine [138]
Cray T3D, T3E
Intel DELTA
Alpha 21364
최근에는 message 길이에 비해 router chip의 핀 대역폭(pin bandwidth)이 높아지면서, node degree가 높은 topology인 butterfly, Clos network 사용이 다시 증가하고 있다.
Processor-memory interconnect
1960년대 말부터 등장. → 병렬 프로세서 시스템에서 어떤 processor든지 어떤 memory bank에 접근할 수 있도록 하기 위해 alignment network를 도입함.
소형 시스템: crossbar 사용
대형 시스템: butterfly topology, dance-hall 구성
이러한 방식은 1980년대에도 많은 shared-memory parallel processor에서 활용되었다.
세 흐름의 통합
1990년대 초 이후, processor-memory와 inter-processor network 설계의 차이는 거의 사라졌다. → 동일한 router chip이 양쪽에 사용되고 있음 → telephone에서 사용되던 Clos 및 Beneš network도 fat-tree topology 형태로 multiprocessor network에 적용되고 있다 [113]
이 역사에서는 주로 topology에 초점을 맞췄지만, routing과 flow control도 동시에 발전해왔다.
초기 routing chip: deterministic routing, circuit-switching 또는 store-and-forward packet switching 사용
이후: adaptive routing, deadlock avoidance, virtual-channel flow control 등장
1.5 Organization of this Book
다음 장에서는 먼저 하나의 완전한 interconnection network를 topology부터 logic gate 수준까지 설명한다. → 전체적인 구조를 먼저 보여주고, 이후에 세부로 들어가는 방식이다.
본 장에서는 응용 프로그램 집합에 맞춤화된 minimal deterministic routing algorithm을 설계하기 위한 system-level framework를 제시한다. 이를 위해 먼저 네트워크의 평균 패킷 지연(latency)을 최소화하는 최적화 문제를 공식화하고, 이를 해결하기 위해 simulated annealing heuristic을 사용한다. 평균 패킷 지연을 추정하기 위해 트래픽의 burstiness을 반영할 수 있는 queueing 기반의 분석 모델을 사용한다. 제안된 프레임워크는 deadlock freedom을 보장하기 위해 virtual channel을 필요로 하지 않으며, 이는 acyclic channel dependency graph에서 route를 추출함으로써 달성된다. synthetic workload와 realistic workload를 이용한 실험을 통해 본 접근 방식의 효과가 입증되었다. 다양한 응용 및 아키텍처에서 network의 최대 지속 가능한 처리량(maximum sustainable throughput)이 향상됨을 확인하였다.
2.1 Introduction
ASIC(Application Specific Integrated Circuit)은 높은 성능과 낮은 전력 소모 덕분에 embedded system-on-chip 설계에 흔히 사용되어 왔다. 반도체 기술의 발전으로 인해 reconfigurable logic과 ASIC 모듈의 통합이 가능해졌으며, 이는 DSP, 멀티미디어, 컴퓨터 비전과 같은 계산량이 많은 응용 프로그램을 구현하는 데 있어 새로운 대안으로 사용되고 있다.
2000년대 초, Network-on-Chip (NoC)은 on-chip architecture에서의 표준 솔루션으로 등장하였다.
2.2 Related Work
Turn model은 mesh 및 hypercube 네트워크에서 부분적으로 adaptive routing algorithm을 설계하기 위해 제안되었다 [9]. 최소한의 turn만을 금지함으로써 모든 cycle을 제거하고 deadlock-free routing을 생성할 수 있다. 이 모델은 이후 Odd-Even adaptive routing algorithm 개발에 사용되었다. 이 방식은 특정 위치에서만 turn을 허용함으로써 deadlock을 방지한다. Turn model에 비해 Odd-Even routing은 다양한 source-destination pair에 대해 보다 균등한 라우팅 적응성을 제공한다.
DyAD routing scheme은 deterministic과 adaptive 라우팅을 결합한 방식으로, 네트워크가 혼잡하지 않을 때는 deterministic 모드로, 혼잡할 때는 adaptive 모드로 동작한다. 각 라우터가 자신의 부하를 측정하여 이웃에게 전달하고, 이 정보를 바탕으로 hot-spot을 회피하는 경로를 결정하는 방식을 제안하였다. APSRA라는 방법론도 제시되었는데, 이는 애플리케이션별 통신 쌍 및 통신하지 않는 쌍 정보를 활용해 적응성(adaptivity)과 성능을 극대화하도록 설계되었다.
이러한 방식들은 모두 adaptive routing 기반이므로 packet 순서가 어긋나는 문제를 겪는다. 본 장에서 제안하는 방식은 이러한 문제를 피하면서도 네트워크 평균 지연을 최소화한다. application-aware oblivious routing이 제안되었고, 이는 정적으로 deadlock-free route를 설정한다. 여기서는 mixed integer-linear programming 및 heuristic 방법을 사용하여 채널 부하를 최소화하였다. 그러나 task mapping의 영향은 분석하지 않았으며, 이에 우리는 혼잡 인식 라우팅(congestion-aware routing)을 제안하였다. 하지만 이 프레임워크는 트래픽의 burstiness를 반영하지 못하므로, 본 연구에서는 [14]에서 제안된 분석 모델을 이용하여 이를 처리한다.
2.3 LAR Framework
Latency-Aware Routing (LAR) 프레임워크는 Fig. 2.1의 flowchart와 같이 총 5단계로 구성된다.
Topology Graph (TG) 및 Communication Graph (CG)를 통해 아키텍처 및 애플리케이션을 모델링한다.
TG와 CG를 기반으로 Channel Dependency Graph (CDG)를 구성한다.
Deadlock을 방지하기 위해 CDG에서 일부 edge를 삭제하여 acyclic CDG를 추출한다.
각 흐름(flow)에 대해 가능한 모든 최단 경로를 찾고 routing space를 생성한다.
routing space 상에서 최적화 문제를 정의하고 해결한다.
2.3.1 Model Architecture and Application
Topology Graph (TG)는 NoC 아키텍처의 topology를 표현하는 유향 그래프로, node는 core 및 wormhole-switched router를 나타내며, link는 edge로 표현된다. 각 core는 processor, DSP, reconfigurable HW, I/O controller 또는 memory block일 수 있으며, Resource Network Interface (RNI)를 통해 router와 연결된다.
RNI는 패킷을 포장 및 해제하고 injection channel을 통해 네트워크에 주입하거나 ejection channel을 통해 네트워크에서 제거한다. Fig. 2.2는 4×4 mesh network의 TG를 나타낸다.
Communication Graph (CG)는 애플리케이션을 모델링한 유향 그래프로, 각 노드는 task를, 각 edge는 task 간의 통신량을 나타낸다. 예를 들어, Fig. 2.3은 VOPD(Video Object Plane Decoder) 애플리케이션의 CG를 보여주며, 각 edge 근처의 숫자는 bandwidth(MBytes/s)를 나타낸다.
2.3.2 Construct Channel Dependency Graph
Dally와 Seitz는 deadlock-free routing 알고리즘 설계를 단순화하기 위해 acyclic CDG가 deadlock-free를 보장함을 증명하였다. CDG의 각 vertex는 TG 내의 channel이며, 두 channel 간 direct한 연속 사용이 가능할 경우 edge를 둔다. Dijkstra 알고리즘을 사용하여 TG에서 가능한 모든 source-destination pair 간 최단 경로를 구하고 이를 기반으로 CDG의 edge를 생성한다. Fig. 2.4a는 minimal fully adaptive routing 하에서 4×4 mesh network의 CDG를 보여준다.
2.3.3 Remove Cycles from CDG
전통적인 routing algorithm은, 예를 들어 dimension-order routing (DOR)과 turn model처럼, 트래픽 패턴에 관계없이 CDG에서 일부 edge를 체계적으로 제거하여 acyclic CDG를 생성한다. 하지만 이는 종종 불필요한 turn을 금지함으로써 routing algorithm의 성능을 저하시킬 수 있다. 예를 들어, Fig. 2.4b에서 보는 바와 같이 transpose traffic pattern 하의 4×4 mesh network의 CDG에는 cycle이 없다. 이 패턴은 행 i, 열 j에 있는 노드가 행 j, 열 i에 있는 노드로 패킷을 전송하는 구조다. 그러나 기존의 알고리즘들은 이러한 상황에서도 보수적으로 edge들을 제거한다.
우리는 CDG에서 cycle을 찾기 위해 depth-first-search (dfs) 알고리즘을 수정하였다. 최소한의 edge만 제거하기 위해, 여러 cycle에 공유되어 있는 edge를 우선적으로 삭제한다. 단, 모든 flow의 reachability가 보장되는 경우에만 해당 edge를 제거한다. 예를 들어 Fig. 2.4a의 4×4 mesh network의 CDG에는 총 6,982,870개의 cycle이 존재하며, 이 중 vertex 40에서 vertex 01로 가는 edge는 5,041,173개의 cycle에 공유된다. 따라서 이 edge를 제거하면 cycle 수는 1,941,697로 크게 줄어든다. 이 과정을 반복하여 CDG에 cycle이 더 이상 없을 때까지 수행한다.
Table 2.1은 다양한 mesh network에서 LAR이 찾아낸 cycle의 수를 보여준다. TG의 크기가 증가함에 따라 CDG의 cycle 수는 기하급수적으로 증가하며, 모든 cycle을 찾는 데 매우 긴 시간이 소요된다. 따라서 우리는 CDG 내에서 일정 수 이상의 cycle이 존재할 경우, 가장 많은 cycle에 공유된 edge를 찾아 제거하는 방식으로 진행한다.
2.3.4 Create Routing Space (RS)
이 단계에서는 acyclic CDG에 대해 Dijkstra 알고리즘을 적용하여 TG 내 모든 flow의 source와 destination 간 모든 최단 경로를 찾는다. 이를 통해 flow 수 f에 대한 routing space RS = {F₁, F₂, ..., F_f}를 생성한다.
각 flow Fᵢ는 다음과 같이 정의된다: Fᵢ = (λᵢ, CAᵢ, nᵢ, Pᵢ)
λᵢ: flow i의 평균 패킷 생성율
CAᵢ: 패킷 도착 간격의 coefficient of variation (CV)
CV는 확률변수 X에 대해 C²_X = x² / x̄² − 1로 정의됨
[14]에서는 CV가 burstiness intensity를 잘 반영한다고 설명
nᵢ: flow i에 대해 가능한 최단 경로의 수
Pᵢ: flow i의 모든 nᵢ개의 route 집합
일반적으로 두 노드 사이에는 1개 이상의 최단 경로(nᵢ > 1)가 존재하므로, 평균 패킷 지연(latency)을 최소화하는 경로를 선택하는 것이 합리적이다. 다음 절에서는 RS 내에서 각 flow에 적합한 route를 찾기 위한 최적화 문제를 정의하고, 이를 해결하기 위해 simulated annealing heuristic을 사용하는 방법을 제시한다.
2.3.5 Routing Space Exploration
2.3.5.1 Define Optimization Problem
이 절에서는 RS 내의 routing space를 탐색하기 위한 최적화 문제를 정의한다. 이를 위해 먼저 결정 변수(decision variables)와 목적 함수(objective function)를 정의해야 한다.
목표는 각 flow i (1 ≤ i ≤ f)에 대해 가능한 nᵢ개의 경로 중 하나를 선택하여 평균 패킷 지연(latency)을 최소화하는 것이다. 이를 위해, X = {x₁, x₂, ..., x_f} 라는 결정 변수 집합을 정의하고, 여기서 xᵢ는 flow i에 대해 선택된 경로의 번호이며, 1 ≤ xᵢ ≤ nᵢ이다. 목적 함수는 네트워크의 평균 패킷 지연이다.
이러한 문제를 시뮬레이션을 통해 해결하려면 연산량이 매우 커지며, 네트워크 크기 증가에 따라 exploration space가 폭발적으로 증가하므로 최적화 루프 내에서 시뮬레이션 사용은 비현실적이다. 따라서 다음 절에서는 효율적인 분석 모델(analytical model)을 통해 근사 최적 해를 빠르게 구하는 방법을 설명한다.
2.3.5.2 Analytical Latency Model
다른 output channel들에 대해서는 일반적인 수식으로 직접적으로 계산할 수 없으며, 더 복잡한 접근 방식이 필요하다. 이제 우리는 OCi<sup>M</sup>의 average service time (first moment)을 다음과 같이 추정할 수 있다:
2.3.5.3 Simulated Annealing
Simulated Annealing은 매우 큰 탐색 공간에서 global optimization problem을 해결하기 위한 확률 기반 계산 기법이다. 주로 탐색 공간이 이산적일(discrete) 경우에 사용된다. 예를 들어, module placement나 packet routing과 같은 CAD 문제에서 사용된 바 있다. 이러한 문제에 대해 simulated annealing은 전수 검색(exhaustive enumeration)보다 더 효율적일 수 있다.
Simulated annealing은 최적 해를 반드시 찾는 것은 아니지만, 제한된 시간 내에 충분히 양호한 해를 찾을 수 있는 장점이 있다. 이 방법은 1983년, 1985년에 독립적으로 제안되었다. 이 기법은 금속 열처리 과정(annealing)에서 유래한 것으로, 물질을 가열한 후 서서히 냉각시켜 결정 크기를 키우고 결함을 줄이는 원리를 따른다.
이 물리적 annealing 과정을 모사하기 위해, 알고리즘은 초기 해에서 시작해 매 반복마다 무작위로 trial solution을 생성한다. 이 trial solution이 objective function 값을 낮추면(더 나은 해이면) 무조건 수용하며, 그렇지 않더라도 일정 확률로 수용한다. 일반적으로 Metropolis algorithm을 acceptance criterion으로 사용하며, 이는 다음과 같다:
e−ΔE/T>R(0,1)(2.9)e^{- \Delta E / T} > R(0,1) \tag{2.9}e−ΔE/T>R(0,1)(2.9)
여기서
ΔE는 현재 해와 trial solution 간의 objective function 값의 차이 (더 나은 경우 음수, 더 나쁜 경우 양수),
T는 synthetic temperature,
R(0,1)은 [0,1] 범위의 난수이다.
이 과정은 시스템이 충분히 좋은 상태에 도달하거나, 지정된 계산량이 소진될 때까지 반복된다. 이처럼 나쁜 해도 수용함으로써, 알고리즘이 초기 local minimum에 갇히는 것을 피하고, global 탐색을 수행할 수 있게 된다. 보다 자세한 내용은 [17] 참고.
앞서 2.3.5.1절에서 설명한 것처럼, objective function은 average packet latency, 결정 변수는 routing set X = {x₁, x₂, ..., x_f}이다. 여기서 xᵢ는 flow i에 대해 선택된 경로 번호이다 (1 ≤ xᵢ ≤ nᵢ).
초기 routing set X = {x₁, x₂, ..., x_r, ..., x_f}에서, trial routing set X<sub>new</sub> = {x₁, x₂, ..., x_r<sup>new</sup>, ..., x_f}를 만들기 위해 다음 단계를 따른다:
1 ≤ r ≤ f 범위에서 랜덤 숫자 r을 선택해 flow를 고르고,
1 ≤ x<sub>r</sub><sup>new</sup> ≤ n<sub>r</sub> 범위에서 다른 경로 번호 x<sub>r</sub><sup>new</sup>를 선택한다 (단, x<sub>r</sub><sup>new</sup> ≠ x<sub>r</sub>).
그리고 2.3.5.2절의 analytical model을 사용해, 현재 routing set과 trial routing set에 대한 평균 패킷 지연을 계산한다.
2.4 Experimental Results
제안된 프레임워크의 성능을 평가하기 위해, 우리는 flit level에서 routing algorithm의 동작을 모사하는 discrete-event simulator를 개발하였다. NoC 분야에서 mesh network의 인기가 높기 때문에, 본 실험에서는 mesh topology를 중심으로 분석하였으나, LAR 프레임워크는 다른 topology에도 변경 없이 동일하게 적용될 수 있다. 모든 실험에서, simulated annealing 알고리즘의 초기 해로는 DOR routing을 사용하였다. LAR의 성능은 2D mesh network에서 XY routing이 되는 DOR과 비교하였다.
시뮬레이션 결과의 정확도를 높이기 위해, 우리는 batch means method를 사용하였다. 전체 실험은 10개의 batch로 구성되었으며, 각 batch는 workload 유형, 패킷 주입률, network 크기에 따라 1,000개에서 최대 1,000,000개의 패킷을 포함하였다. 시뮬레이션 시작 단계의 편향을 피하기 위해 첫 번째 batch에서는 통계 수집을 하지 않았다. 지연 시간(latency) 측정의 표준편차는 평균값의 1.8% 이하였으며, 그 결과 시뮬레이션 결과의 신뢰수준(confidence level)은 0.99, 신뢰구간(confidence interval)은 0.02로 설정되었다.
보다 포괄적인 연구를 위해, 다양한 workload 유형과 network 크기 조합에 대해 여러 검증 실험을 수행하였다. 이후에서는 synthetic traffic과 realistic traffic 모두에 대해 LAR의 성능을 평가한다. 이 두 traffic 유형은 응용 목적이 매우 다르므로, 그에 따른 트래픽 패턴 또한 크게 상이하다.
2.4.1 Synthetic Traffic
본 연구에서 사용된 synthetic traffic pattern은 uniform, transpose, shuffle, bit-complement, bit-reversal이다 [5]. spatial traffic distribution을 설명하는 모델을 설계한 후, 우리는 temporal traffic distribution을 설명할 수 있는 적절한 모델을 사용해야 한다. synthetic traffic의 경우, 우리는 Poisson process를 사용하여 시간 축 방향의 트래픽 변동을 모델링하였다. 이는 하나의 core에서 연속된 두 패킷 사이의 시간 간격이 지수 분포를 따른다는 의미이다. Poisson 모델은 다양한 성능 분석 연구에서 광범위하게 사용되며, 이 확률적 가정을 기반으로 한 수많은 논문들이 존재한다.
Fig. 2.5와 Fig. 2.6에서는 각각 4×4, 8×8 mesh network에서 network의 offered load에 따라 average packet latency가 어떻게 변화하는지를 보여준다.
Uniform과 bit-complement traffic pattern 하에서는, LAR의 결과가 DOR와 수렴한다. 이는 해당 트래픽에서는 DOR이 이미 평균 지연이 최소이기 때문이며, simulated annealing이 더 나은 경로를 찾지 못했음을 의미한다. 즉, 최종 해가 초기 해와 동일하다. 이러한 결과는 [4, 9, 12, 19]의 기존 결과와도 일치한다. 그 이유는 DOR이 장기적으로 균일하게 트래픽을 분산시키기 때문이다 [9]. 기존의 Odd-Even [4], Turn Model [9], DyAD [12], APSRA [19] 등의 연구도 uniform traffic에서는 DOR보다 성능이 낮았음을 보여준다. Fig. 2.5a, Fig. 2.6a에서도 확인되듯이, 우리 프레임워크는 다양한 트래픽 부하에서도 DOR과 동일한 성능을 보인다.
Fig. 2.5b, c에서는 transpose와 bit-reversal workload 하에서 4×4 mesh network에서의 DOR과 LAR의 latency를 비교한다. 여기서는 LAR이 DOR보다 명확히 더 나은 성능을 보인다. 8×8 mesh network의 경우에도 Fig. 2.6b, c에서처럼 LAR이 DOR을 능가한다.
Fig. 2.5d, Fig. 2.6d에서는 shuffle traffic pattern 하에서 LAR이 DOR보다 조금 더 좋은 성능을 보인다.
Table 2.3은 각각의 workload에 대해, 4×4 및 8×8 mesh network에서 DOR과 LAR의 maximum sustainable throughput과 그 개선율(%)을 보여준다. 평균적으로 LAR이 DOR을 능가함을 확인할 수 있으며, LAR을 사용한 경우 network가 감당할 수 있는 최대 트래픽 부하는 최대 205%까지 개선되었다.
또한 우리는 LAR 프레임워크의 성능을 DyAD routing scheme과 비교하였다. DyAD는 deterministic routing과 adaptive routing을 결합한 구조다. 우리는 동일한 구조(6×6 mesh network)에서 uniform과 transpose workload를 시뮬레이션하고, 이들의 DOR 대비 성능 개선률을 비교하였다.
Table 2.4는 DOR 대비 DyAD와 LAR의 개선률(%)을 보여준다.
Uniform traffic의 경우, DyAD는 오히려 DOR보다 낮은 성능을 보였고, LAR은 DOR과 동일한 성능을 보였다.
Transpose traffic의 경우, DyAD와 LAR은 각각 62%, 60% 개선을 보였다.
이 결과는, 우리의 deterministic routing 방식이 adaptive routing 방식과 경쟁 가능하며, 동시에 in-order packet delivery를 보장함을 보여준다.
2.4.2 Realistic Traffic
Realistic traffic의 경우, 우리는 multiple virtual channel routing과의 호환성을 보여주기 위해 각 link에 대해 2개의 virtual channel을 고려한다. 실제 통신 시나리오로는 generic multimedia system (MMS)과 video object plane decoder (VOPD) 애플리케이션을 다룬다. MMS는 H.263 video encoder, H.263 video decoder, MP3 audio encoder, MP3 audio decoder로 구성된다. 이 애플리케이션의 통신량 요구사항은 Table 2.5에 요약되어 있다. VOPD는 MPEG-4 비디오 디코딩을 위한 애플리케이션으로, 그 communication graph는 Fig. 2.3에 나타나 있다. 다수의 연구들에서는, multimedia traffic에서의 on-chip interconnection networks에 bursty packet injection이 존재함을 보고한 바 있다.
Poisson process는 bursty traffic의 경우 적절한 모델이 아니므로, 우리는 Markov-modulated Poisson process (MMPP)를 사용하여 애플리케이션 트래픽의 bursty 특성을 모델링하였다 [5, 8]. MMPP는 temporal domain에서 트래픽 burstiness를 모델링하기 위해 널리 사용되고 있다 [8]. Fig. 2.7은 두 상태(two-state)의 MMPP 모델을 보여주며, 여기서 각 상태에서의 패킷 도착은 각각 Poisson rate λ₀, λ₁을 따른다. 상태 0에서 1로의 전이율은 r₀, 상태 1에서 0으로의 전이율은 r₁이다.
이러한 시스템에서는 core의 종류가 다양하고 요구 대역폭도 다르기 때문에, task의 배치(mapping)가 system performance에 강한 영향을 미친다. 우리는 이 애플리케이션들에 대해 적절한 매핑을 찾기 위해 design space를 단시간 내에 줄이기 위한 또 다른 최적화 문제를 수립하고, 다시 simulated annealing heuristic을 사용하여 적절한 mapping vector를 찾는다.
초기에는 task i를 node i에 매핑하고, 이후 simulated annealing을 통해 average packet latency를 최소화하려 한다. Fig. 2.8a에서, MMS 애플리케이션과 DOR 하에서 초기 mapping인 M1의 average packet latency는 87이며, 여러 번의 시도 후 mapping M4로 수렴, 그때의 latency는 41이다. 또한, simulated annealing 과정 중 발생하는 local minimum 지점인 M2와 M3의 latency 값도 함께 도식화되어 있다.
mapping 단계가 끝난 후, 우리는 이 4개의 mapping vector에 대해 LAR framework를 적용한다. Fig. 2.8a는 M1 매핑에 대해 LAR이 average packet latency를 87에서 67로 유의미하게 줄임을 보여준다. 그러나 M2, M3, M4처럼 효율적인 매핑의 경우, 개선 효과는 상대적으로 작다. 특히, 최적의 매핑(M4)의 경우 latency는 41에서 40으로만 감소한다. 이는 당연한 결과인데, mapping 문제를 푸는 과정에서 routing policy를 DOR로 고정하고 이 DOR 하에서 average latency를 최소화하도록 설계했기 때문이다. 마찬가지로, VOPD 애플리케이션의 경우에도 Fig. 2.8b에서 유사한 분석 결과를 보인다.
Fig. 2.8은 application-specific traffic pattern 하에서는, routing scheme의 성능 개선 정도가 task를 topology에 어떻게 매핑하느냐에 크게 의존함을 보여준다. 이러한 사실은 [16] 같은 관련 연구들에서는 고려되지 않았다.
오늘날의 embedded systems-on-chip에는 DSP, embedded DRAM, ASIC, generic processor 등 다양한 core들이 있으며, 이들의 물리적 위치는 고정되어 있다. 한편, 이러한 시스템은 서로 다른 workload를 가진 여러 개의 애플리케이션을 동시에 수행하고, 최근의 embedded 장치는 런타임에 사용자 애플리케이션을 설치할 수도 있으므로, design phase에서 이러한 시스템을 완전히 분석하는 것은 불가능하다.
결과적으로, 모든 애플리케이션을 고정된 routing algorithm 하에서 균일하게 load balance 하도록 mapping하는 것은 실현 불가능하며, 대신 routing phase에서 load를 balancing 해야 한다.
이 섹션에서는 LAR framework를 사용하여 mesh network 내에서 low latency 경로를 찾았다. 2D mesh topology는 구조적 단순함, 규칙성, 저비용 등의 장점 때문에 NoC 분야에서 가장 널리 사용된다. 하지만 미래에 보편화될 대형 및 3D NoC에서는, mesh 아키텍처 내의 통신이 매우 오래 걸린다. 다음 절에서는, 임의의 topology에서 deadlock-free 경로를 찾기 위해 LAR을 활용한다.
2.4.3 Find Routes in an Arbitrary Topology
LAR framework가 임의의 topology에서도 deadlock-free 경로를 찾을 수 있는 능력을 보여주기 위해, Fig. 2.9a에 나타난 topology를 고려한다. LAR은 uniform traffic pattern 하에서 해당 topology의 CDG에 두 개의 cycle이 존재함을 보고하고, turn 52–21과 87–73(Fig. 2.9b에 표시됨)을 금지함으로써(deadlock-prevention) deadlock-free 상태를 보장한다.
Table 2.6은 Fig. 2.9a에 나타난 topology의 node 0에 대한 routing table을 보여준다. 각 경로는 node 0에서 특정 목적지로 가는 경로를 채널 이름을 사용하여 지정한다.
SE: South-East
SW: South-West
EJ: Ejection channel
패킷을 라우팅할 때, destination address로 routing table을 인덱싱하여 LAR이 미리 계산한 경로를 조회한다. 해당 경로는 패킷 헤더에 삽입된다.
이 network에는 총 7개의 채널이 존재하며 (E, S, NE, NW, SE, SW, EJ), 이들은 3-bit binary 값으로 인코딩할 수 있다. 또한, routing table의 크기를 줄이기 위한 기술들도 존재한다 [5, 19].
2.5 Conclusion
On-chip packet routing은 system의 성능과 전력 소비에 큰 영향을 미치기 때문에 매우 중요하다. 이는 routing 최적화의 필요성을 강하게 요구한다. 그러나 network가 제공하는 다양한 연결성과, buffer 및 link 공유에서 발생하는 간섭 때문에, minimal하고 deadlock-free한 경로를 트래픽 flow마다 찾는 것은 간단하지 않다.
이 장에서는 latency-aware routing 문제를 다루었다. 우리는 먼저 analytical model을 사용하여 평균 패킷 지연을 추정하였고, 이를 기반으로 simulated annealing heuristic을 통해 routing space를 탐색하여 deadlock-free하고 효율적인 routing 경로를 도출하였다.
이 논문(LAR framework)은 다음과 같은 과정을 수행합니다:
1. RS (Routing Space) 생성
모든 flow에 대해 가능한 최단 경로 집합을 생성함
2. 각 RS 조합 평가
각 flow마다 하나의 경로를 선택한 조합(RS의 한 인스턴스)에 대해 → analytical model을 사용하여 전체 평균 패킷 지연 L을 계산
3. Simulated Annealing
다양한 RS 조합을 시도하면서 가장 L이 작은 조합을 탐색
4. 최종 경로 선택 후 Routing Table 생성
선택된 경로를 바탕으로 → 각 router가 목적지 주소를 보고 어느 output port로 보낼지를 미리 정리한 → routing table을 생성 → 이 테이블은 run-time에 lookup만 수행
