Zeah Engineering Factory

Arbiter는 하나의 자원을 여러 요청자 중 하나에게 할당하는 반면, allocator는 여러 자원과 여러 요청자 간의 매칭을 수행한다. 각 요청자는 하나 이상의 자원을 요청할 수 있다. 예를 들어, 스위치의 다양한 출력 포트를 향해 여러 flit을 보유한 router 입력 유닛 집합을 생각해 보자. allocator에 대해서는 이미 17.2.2절에서 crossbar switch 할당을 설명할 때 소개한 바 있다. 매 cycle마다 switch allocator는 입력 유닛과 출력 포트 사이의 매칭을 수행해야 하며, 이때 각 입력 포트에서는 하나의 flit만 선택되고, 각 출력 포트로 향하는 flit도 하나만 선택되어야 한다.

19.1 표현 방식

n × m allocator는 n개의 m비트 벡터를 입력으로 받고, n개의 m비트 벡터를 출력으로 생성하는 유닛이다. 그림 19.1은 n = 4, m = 3인 allocator를 나타낸다. 입력 rij가 1로 설정되면 요청자 i가 자원 j를 요청하고 있음을 의미한다. 각 요청자는 동시에 여러 자원을 요청할 수 있다. router 설계에 사용되는 allocator에서는 요청자가 switch 입력이고 자원이 switch 출력인 경우가 많다. 따라서 일반적으로 요청자는 입력(input), 자원은 출력(output)이라 부른다.

allocator는 다음 세 가지 규칙에 따라 요청을 고려하고 grant 벡터를 생성한다.

1. gij가 1이면 반드시 rij도 1이어야 한다. 즉, 요청이 있어야만 grant가 주어진다.
2. gij가 1이면 같은 입력 i에 대해서는 다른 어떤 k ≠ j에 대해서도 gik는 0이어야 한다. 즉, 각 입력에 대해 최대 하나의 grant만 허용된다.
3. gij가 1이면 같은 출력 j에 대해서는 다른 어떤 k ≠ i에 대해서도 gkj는 0이어야 한다. 즉, 각 출력에 대해서도 최대 하나의 grant만 허용된다.

allocator는 요청 rij로 구성된 n × m 요청 행렬 R을 받아, grant gij로 구성된 grant 행렬 G를 생성한다고 볼 수 있다. R은 임의의 이진 값 행렬이고, G는 다음 조건을 만족하는 이진 값 행렬이다:

• 요청이 있는 곳에만 1이 있어야 하고 (규칙 1),
• 각 행에 1이 최대 한 개,
• 각 열에도 1이 최대 한 개 있어야 한다 (규칙 2, 3).

예를 들어 다음과 같은 요청 행렬 R과 두 개의 가능한 grant 행렬 G₁, G₂를 생각해 보자.

G₁과 G₂는 모두 위의 세 가지 규칙을 만족하기 때문에 유효한 grant 행렬이다. 그러나 G₂는 세 자원을 모두 입력에 할당했기 때문에 더 바람직한 grant 행렬이라 할 수 있다. G₂와 같이 가능한 최대 수의 할당을 포함하는 해를 maximum matching이라 부른다. G₁처럼 더 이상 요청을 수용할 수 없는 행렬은 maximum matching이 아닐 수 있다.

※ 주: 일부 응용에서는 요청 행렬 R이 정수값을 가질 수 있으며, 하나의 출력에 대해 다중 요청을 허용할 수 있다. 하지만 여기서는 그와 같은 경우는 고려하지 않는다.

매칭을 더 이상 추가할 수 없는 상태이면서도 현재의 grant를 제거하지 않고는 새로운 요청을 처리할 수 없는 경우, 이를 maximal matching이라고 한다.

G₁ 행렬은 좋은 매칭을 계산하기 어려운 예시를 보여준다. 예를 들어 첫 번째 행에서 g₀₀ grant를 설정하면, 더 이상 maximum matching은 불가능하다. 입력 2는 오직 자원 0만 요청하고 있기 때문에, 자원 0을 다른 입력에 할당하면 입력 2는 동작하지 못하게 된다. 또한 자원 1을 입력 0에 할당하면, 입력 1과 입력 2가 자원 0을 동시에 가질 수 없기 때문에 역시 maximum matching을 방해하게 된다. 이런 식으로, 하나의 잘못된 할당이 전체적으로 sub-optimal matching을 초래할 수 있다.

할당 문제는 bipartite graph 형태로도 표현할 수 있다. 그림 19.2(a)는 요청 행렬 R에 해당하는 bipartite graph를 보여준다. 이 방식에서는 할당 문제가 바로 bipartite matching 문제와 동일하다. 즉, 각 정점이 최대 하나의 엣지에만 연결되도록 하면서 가능한 많은 엣지를 선택하는 문제다. 그림 19.2(b)는 grant 행렬 G₂에 해당하는 그래프에서의 maximum matching을 나타낸다.

어떤 bipartite graph든지 maximum matching은 시간 복잡도 O(P²․⁵)로 계산할 수 있다 (P는 포트 수). 일반적으로 maximum-size match를 계산하려면 backtracking이 필요하다. 즉, 일시적으로 grant를 설정했다가 나중에 제거해야 할 수도 있다. 하지만 switch allocator나 virtual channel allocator는 이 정도의 복잡도를 감당할 수 없고, backtracking이 필요한 알고리즘은 pipeline 구현이 어렵다. 보통 할당을 수행할 수 있는 시간이 단 하나의 cycle, 또는 몇 개의 cycle에 불과하므로, 실제로는 maximal matching을 목표로 하는 것이 현실적이다. 그러나 maximal matching조차도 비용이 클 수 있기 때문에, 실제 하드웨어 allocator는 빠르지만 근사적인 해를 제공하는 단순한 heuristic을 사용하는 경우가 많다.

19.2 Exact Algorithms

정확한 maximum matching은 대부분의 router 응용에서는 시간 제약 때문에 현실적으로 불가능하지만, 오프라인 계산이 가능할 때도 있다. 또한 새로운 heuristic을 평가할 때 기준점으로 사용할 수 있도록 정확한 maximum matching이 필요할 수도 있다. 이런 경우에는 sub-maximum matching을 반복적으로 개선해 가는 방식으로 계산할 수 있다.

이때 사용하는 augmenting path algorithm은 Clos 네트워크의 스케줄링에 사용했던 반복 알고리즘과 유사하다 (6.11절 참조). 우선 초기에는 sub-optimal matching M으로 시작한다. 이 매칭을 기반으로 residual graph를 만든다. 이 residual graph는 원래의 bipartite graph와 노드와 엣지는 같지만 방향이 지정된다. 현재 매칭 M에 속한 엣지는 출력에서 입력 방향 (오른쪽 → 왼쪽)으로 향하고, 매칭되지 않은 엣지는 입력에서 출력 방향 (왼쪽 → 오른쪽)으로 향한다.

그 다음, augmenting path를 찾는다. augmenting path는 매칭되지 않은 입력에서 시작하여 매칭되지 않은 출력까지 이어지는 방향 있는 경로이다. 이 경로를 따라 입력→출력 방향의 엣지는 매칭에 추가되고, 출력→입력 방향의 엣지는 매칭에서 제거된다. 이렇게 하면 매칭의 엣지가 하나 더 늘어난다. 이 과정을 반복하면서 residual graph에 더 이상 augmenting path가 존재하지 않게 될 때까지 수행하면 된다.

예를 들어 다음 요청 행렬 R을 보자:

이 요청 행렬을 기반으로 하는 bipartite graph와 그 위에서의 maximum matching 계산 과정이 그림 19.3에 나와 있다.

• (a): 초기 매칭이 진하게 표시되어 있다. 회색으로 표시된 입력과 출력은 이미 매칭된 상태이다. 이 매칭은 maximal이긴 하지만 maximum은 아니다.
• (b): 위 매칭에 기반하여 residual graph를 구성한 모습이다.
• (c): 매칭되지 않은 입력 2에서 시작해 출력 0까지 이어지는 augmenting path를 찾은 모습이다. 경로는 (i2,o1) → (o1,i0) → (i0,o0) 이다.
• (d): 위 경로를 따라 (i2,o1), (i0,o0)은 매칭에 추가되고, (o1,i0)은 매칭에서 제거된다.
• (e): 입력 5에서 출력 5까지의 augmenting path가 발견된 모습.
• (f): 그 경로를 적용한 최종 매칭 상태. 더 이상 augmenting path가 존재하지 않으므로 알고리즘 종료.

Ford-Fulkerson 이론에 따르면 augmenting path가 존재하지 않으면 해당 매칭은 maximum이다.

입력 우선 separable allocator는 요청 행렬의 행 기준으로 먼저 arbitration을 수행하고, 이후 열 기준으로 처리한다. 반대로 출력 우선 separable allocator는 열을 먼저, 그 다음 행을 arbitration 한다. 정사각형 행렬의 경우 두 방식 모두 동등하게 작동하지만, 직사각형 행렬에서는 짧은 방향을 먼저 arbitration 하는 것이 유리하다. 예를 들어, 4 × 3 allocator에서는 입력 arbitration을 먼저 수행하는 것이 출력 단계로 더 많은 요청을 전달할 수 있어 유리하다. 따라서 입력 속도가 출력 속도보다 더 빠른 switch에서는 보통 입력 우선 방식이 효율적이다.

예를 들어 다음 요청 행렬 R을 보자:

이 요청 행렬에 대한 하나의 입력 우선 separable allocation 예시는 그림 19.6에 나와 있다. 이 예에서는 각 arbiter가 처음 발견한 요청을 선택한다. 이때 input arbitration 이후의 중간 요청 행렬 X는 다음과 같다:

X 행렬은 입력 충돌을 제거하여 각 행에 1이 최대 한 개만 남는다. 이후 출력 arbitration을 통해 출력 충돌도 제거하면 최종 grant 행렬 G는 다음과 같다:

만약 첫 번째나 마지막 input arbiter가 마지막 요청을 선택했더라면, 세 개의 출력 모두에 할당할 수 있었을 것이다.

같은 요청 행렬(식 19.2)을 출력 우선 방식으로 처리했을 때 (각 arbiter가 처음 요청된 입력을 선택한다고 가정), 중간 행렬 Y와 grant 행렬 G는 다음과 같다:

이 경우 세 개의 출력 arbiter가 모두 동일한 입력을 선택해버리는 바람에 grant는 하나밖에 생성되지 않았다. 실제 하드웨어에서는 이렇게 정렬이 정확히 일치하는 경우는 드물지만, input 우선과 output 우선 방식의 차이는 Exercise 19.6에서 더 자세히 다룬다.

Separable allocator의 매칭 품질을 개선하기 위해 자주 사용되는 두 가지 기술이 있다.

첫째, 각 단계의 arbiter에서 높은 우선순위를 주는 입력을 staggering하여 여러 arbiter가 같은 출력을 선택하지 않도록 한다. 예를 들어, wavefront allocator (19.4절 참고)는 완전한 separable allocator는 아니지만, 입력 arbiter의 우선순위를 한 포트씩 offset 하여 설정하고 각 cycle마다 이를 회전시킨다. PIM (19.3.1절), iSLIP (19.3.2절), LOA (19.3.3절)도 각기 다른 방식으로 입력 우선순위를 staggering한다.

둘째, 시간이 허용된다면 여러 번 반복 실행(iteration)을 통해 매칭 품질을 향상시킬 수 있다. 각 반복에서는 이전 iteration에서 grant된 요청과 행이나 열에서 충돌하는 요청을 제거하고, 남은 요청에 대해 다시 separable allocation을 수행한다. 각 iteration에서 생성된 grant는 누적되어 전체 누적 grant 행렬을 만든다.

예를 들어 위 예시에서 두 번째 반복을 수행하면 모든 요청 중 r₃₂만 남아 충돌 없이 처리되며, g₃₂가 생성된다. 이때 각 행렬은 다음과 같다:

iSLIP은 단일 반복으로도 uniform 트래픽에서 100% throughput을 달성하지만, 반복 횟수를 한 번만 늘려도 지연(latency)은 크게 줄어들며, wavefront와 유사한 성능을 갖게 된다. 두 번 이상 반복해도 성능 개선은 미미하다.

17.2.2절에서 언급했듯, allocator 성능을 향상시키는 또 다른 방법은 switch에 입력 속도 향상(input speedup), 출력 속도 향상(output speedup), 혹은 둘 다 적용하는 것이다. 그림 19.15는 입력과 출력 속도 향상이 적용된 LOA의 성능을 보여준다.

• 속도 향상 없음 (IS=1, OS=1): 약 69%에서 포화
• 입력 속도 향상 2배 (IS=2, OS=1): 포화점이 약 95%로 증가하고 지연도 감소
• 입력과 출력 속도 모두 2배 (IS=2, OS=2): throughput이 100%로 향상

또 다른 접근은 crossbar와 allocator의 동작 속도를 채널 속도보다 빠르게 설정하는 것이다. 채널 속도로 패킷이 도착할 때, speedup 비율 S에 따라 S개의 패킷이 crossbar를 통과할 수 있다.

그림 19.16은 LOA에 speedup을 적용했을 때의 성능을 보여준다.

• S = 1.25: 약 85%까지 포화 throughput 증가
• S = 1.5: 약 98% 도달
• S = 1.75: 이후에는 throughput 또는 지연에 큰 개선 없음

19.8 사례 연구: Tiny Tera Allocator

Tiny Tera는 Stanford 대학에서 개발된 고속 패킷 스위치이며, 후에 Abrizio에 의해 상용화되었다. 핵심은 32포트 crossbar이며, 매 51ns마다 재구성이 필요하다. 이 시스템의 allocator는 iSLIP 알고리즘을 기반으로 출력 우선(output-first) arbitration 및 3회 반복으로 구성되어 있으며, timing 목표를 만족시키기 위해 파이프라인화 및 고속 arbiter 설계가 요구되었다.

일반적으로 iSLIP을 여러 번 반복할 경우, 각 반복에서 두 개의 arbitration 단계가 모두 끝난 후 다음 반복이 시작되어야 한다. 이전 반복의 결과를 바탕으로 matched된 input/output에 대응하는 요청을 비활성화해야 하기 때문이다. 이 방식은 반복당 두 arbitration 시간이 소요된다.

그러나 Tiny Tera에서는 clever한 최적화를 통해 이 반복 시간을 절반 수준으로 줄였다.

핵심 아이디어:
만약 어떤 출력 arbiter가 특정 입력을 선택했다면, 해당 입력은 이후 input arbitration에서도 매칭될 것이므로, 이를 미리 알고 **입력 마스크(input mask)**를 계산할 수 있다. 즉, 출력 arbitration 결과를 OR 연산하여 입력 마스크 imᵢ를 만들고, 다음 단계에서 이를 적용하면 된다.

그림 19.17은 3×3 iSLIP allocator의 일부 구조를 보여준다. 각 출력 arbitration은 OR 연산을 통해 imᵢ를 생성하고, 이는 다음 cycle에서 input arbitration에 입력 마스크로 사용된다. 이 방법을 사용하면 반복 시간이 "arbitration 1회 + OR 연산 시간"으로 줄어든다. 특히 Tiny Tera처럼 arbiter가 클 경우 OR 연산 시간은 매우 짧기 때문에 큰 이점이 있다.

두 번째 pipeline 단계에서는 input arbiter가 작동하며, 이들이 생성한 grant 신호를 OR 연산하여 **출력 마스크(omᵢ)**를 만든다. 이 마스크는 다음 input arbitration 단계에 적용되며, 이미 매칭된 output으로의 요청이 다음 cycle에서 input arbiter에 영향을 미치지 않도록 한다. 다만, 이 마스크는 처음부터 요청을 차단하는 것이 아니라 input arbiter에만 적용되므로, 첫 번째 출력 arbitration 단계에서 불필요한 요청이 처리되는 것은 막지 못한다. 하지만 최종 grant에는 영향을 미치지 않는다.

이 마스크 동작의 예시는 다음 페이지 2×2 allocator에 대한 반복 예제로 설명된다.

그림 19.18은 2×2 allocator에 대해 iSLIP 파이프라인 알고리즘을 2회 반복한 예시를 보여준다.

• 첫 반복(iteration 1)에서는 두 출력 arbiter가 모두 입력 0을 선택하고, 이 정보는 이후 cycle에서 입력 0이 매칭되었다는 표시(gray)로 사용된다.
• 두 번째 cycle에서는 첫 번째 반복의 input arbitration에서 입력 0이 출력 0에 요청을 보내고 grant를 받는다.
• 동시에 두 번째 반복의 출력 arbitration에서는 입력 1을 선택한다.
• 세 번째 cycle 시작 시, 출력 마스크는 출력 0이 이미 매칭되었다는 것을 반영한다. 이로 인해 입력 1 → 출력 0의 잘못된 요청은 두 번째 반복의 grant 계산 전에 마스킹되어 제거된다.

19.9 참고 문헌

maximum matching 알고리즘은 Hall과 Ford & Fulkerson이 가장 먼저 제안했다. augmenting path 알고리즘의 복잡도는 O(|V||E|)이며, Hopcroft와 Karp는 O(√|V||E|) 알고리즘을 개발했다 [83]. McKeown 등은 maximum-size matching이 non-uniform 트래픽에서는 100% throughput을 보장하지 않으며, 더 복잡한 maximum weight matching이 필요함을 보여주었다 [126].

이후, 100% throughput을 유지하면서도 maximum weight matching을 근사하는 다양한 기법들이 제안되었다 [183, 71]. **Parallel Iterative Matching (PIM)**은 Anderson 등이 처음 제안했다 [11]. iSLIP은 McKeown이 처음 고안 및 기술하였고 [123], Tiny Tera packet switch에 적용되었다 [125, 79]. Wavefront allocator는 Tamir가 개발하였으며 [180], Incremental allocation은 Alpha 21364 라우터에 효과적으로 사용되었다 [130, 131].

19.10 연습문제

19.1 Separable allocator의 성능
다음 요청 행렬에 대해 single-pass separable allocator가 생성할 수 있는 최상의 grant 행렬과 최악의 grant 행렬을 찾아라.

19.2 Wavefront allocator에서의 randomization 및 history 효과
다음 요청 행렬 R을 갖는 4×4 wavefront allocator를 고려하자. 우선순위 그룹은 그림 19.10과 동일하게 구성된다.

(a) 우선순위 그룹이 매 cycle마다 증가(p0, p1, p2, p3, p0, …)하고 요청 행렬 R이 고정되었을 때, 각 요청에 대해 얼마나 자주 grant가 주어지는가? 이것이 switch의 throughput에 미치는 영향은?

(b) 매 cycle마다 우선순위 그룹을 무작위로 선택하면 성능이 개선되는가?

(c) 일반적으로, 우선순위 셀은 각 행과 열에 하나씩 있는 어떤 패턴(즉, 순열)으로도 설정할 수 있다. 각 cycle마다 무작위 순열을 우선순위로 사용할 경우, (a) 및 (b)와 비교해 성능은 어떻게 되는가?

19.3 Multicast allocation
separable allocator를 확장하여 unicast뿐만 아니라 multicast 요청도 처리하게 하려면 어떻게 해야 하는가? multicast allocator는 각 입력 포트당 두 개의 추가 입력을 받는다:

• multicast 요청 신호 rm (동시 다출력 요청 시 활성화)
• 출력 포트별 비트벡터 bm (multicast 대상 출력 지정)

19.4 Incremental multicast allocation
라우터에서 multicast 요청을 한 번에 처리할 수도 있고, 작은 단위로 나누어 처리할 수도 있다. 극단적으로는 각 출력에 대해 하나씩 unicast로 나눌 수도 있다. 가능한 출력만 매 cycle마다 할당하고 나머지는 다음 cycle로 미루는 greedy incremental multicast allocator는 어떻게 설계할 수 있을까?

19.5 PIM의 수렴성
Uniform traffic 하에서 PIM이 maximal matching에 수렴하는 데 필요한 평균 반복 횟수는? 가능한 모든 요청 패턴 중 최악의 경우 반복 횟수는?

19.6 입력 속도 향상 환경에서의 input-first vs. output-first allocation
SN 입력, N 출력 스위치에서 S는 입력 속도 향상 계수라 하자.

(a) 요청이 uniform하고 single-pass PIM allocator를 사용할 경우, input-first 방식의 throughput은? output-first 방식은?

(b) N이 큰 경우, input-first와 output-first 방식 간 throughput 차이를 가장 크게 만드는 S는 몇인가? 그 차이는?

19.7 시뮬레이션 과제
속도 향상 1의 스위치에서 4회 반복 PIM allocator와, 속도 향상 2의 스위치에서 1회 반복 PIM allocator의 성능을 비교하라.

라우터의 datapath는 buffer와 switch로 구성되는 반면, control path는 대부분 arbiter와 allocator로 이루어진다. 16장에서 논의한 것처럼 allocator는 packet에 virtual channel을 할당하거나 flit에 switch cycle을 할당할 때 사용된다. 이 장에서는 하나의 자원에 대해 여러 요청이 있을 경우 이를 해결하는 arbiter에 대해 설명한다. arbiter는 그 자체로도 유용하지만, 여러 요청자와 여러 자원을 매칭하는 allocator의 기본 구성 요소이기도 하다. allocator에 대한 설명은 19장에서 다룬다.

버퍼, 채널, 또는 스위치 포트와 같은 자원이 여러 agent에 의해 공유되는 경우, arbiter는 이 자원에 대한 접근 권한을 한 번에 한 agent에게만 할당해야 한다. 그림 18.1(a)는 crossbar switch의 입력 포트와 같은 자원에 대해 연결된 virtual channel들이 접근을 요청할 때 사용하는 n-input arbiter의 기호를 보여준다. 전송할 flit을 가진 각 virtual channel은 자신의 request line을 assert하여 입력 포트 접근을 요청한다. 예를 들어, n = 8개의 VC 중에서 VC 1, 3, 5가 각각 r1, r3, r5를 assert했다고 하자. 그러면 arbiter는 이들 중 하나, 예컨대 VC 3을 선택해 g3을 assert함으로써 입력 포트를 VC 3에게 grant한다. VC 1과 5는 arbitration에서 패배하여, 나중에 r1과 r5를 다시 assert해야 한다. 일반적으로 이들 line은 grant를 받을 때까지 계속 high 상태를 유지한다.

18.1 Arbitration Timing

grant의 지속 시간은 애플리케이션에 따라 다르다. 어떤 경우에는 요청자가 자원을 여러 사이클 동안 중단 없이 사용할 필요가 있다. 반면, 매 cycle마다 다시 arbitration을 수행해도 되는 경우도 있다. 이처럼 다양한 상황에 대응하기 위해, arbiter는 단일 cycle, 고정된 cycle 수, 또는 자원이 해제될 때까지 grant를 유지하는 방식으로 설계할 수 있다.

예를 들어, flit을 단일 cycle 동안 처리하는 스위치의 arbitration에서는 VC가 스위치 포트를 단 한 cycle만 사용할 수 있도록 grant된다. 이 경우, 매 cycle마다 새로운 arbitration이 수행되며, 대부분은 arbitration 직후 cycle에 grant가 적용된다. 그림 18.2(a)는 이 예를 보여준다. cycle 1에서 VC 0과 VC 1이 r0, r1을 assert하여 요청한다. VC 0이 arbitration에서 승리하여 cycle 2에 grant를 받고 같은 cycle에 요청을 drop한다. VC 1은 요청을 계속 유지하고, 경쟁자가 없으므로 cycle 3에 grant를 받는다. 두 VC가 request line을 계속 유지하고 arbiter가 공정하다면(18.2절 참고), cycle 6~9처럼 매 cycle마다 번갈아가며 스위치 포트를 할당받게 된다.

그림 18.2(b)는 각 grant가 4 cycle 동안 유지되는 경우이다. 예를 들어 flit 전송이 4 cycle 걸리며 중단할 수 없는 스위치가 있는 라우터에서 발생한다. 여기서 VC 0이 cycle 1에서 arbitration에 승리하여 cycle 2~5까지 스위치를 할당받는다. VC 1은 요청을 계속 유지하지만, cycle 6까지 대기해야 한다.

마지막으로, 그림 18.2(c)는 자원이 해제될 때까지 grant가 유지되는 경우이다. 이때 VC i는 arbiter와 request line ri 및 hold line hi로 연결된다(그림 18.1(b) 참조). arbitration에서 승리한 VC는 hold line이 high 상태인 한 자원을 독점한다. 예를 들어, VC 0이 cycle 24까지 3 cycle 동안 스위치를 유지하고, 이후 VC 1이 cycle 56 동안 2 cycle 사용한다.

일부 arbiter는 request line이 low 상태로 바뀔 때까지 자원을 유지함으로써 가변 길이 grant를 구현하지만, 이 방식은 같은 agent가 자원을 연속해서 사용할 때 반드시 1 cycle 이상의 idle gap이 필요하다. 그러나 hold line이 별도로 존재하면, 자원을 release하고 같은 cycle 내에 다시 request할 수 있다. VC 1은 cycle 6에서 정확히 이런 방식으로 동작하여 cycle 7에 다시 스위치를 grant받는다.

18.2 공정성 (Fairness)

arbiter의 핵심 특성 중 하나는 공정성(fairness)이다. 직관적으로 공정한 arbiter는 여러 요청자에게 동등한 서비스를 제공한다. 그러나 이 "동등함"의 의미는 애플리케이션에 따라 다를 수 있다. 공정성에 대한 유용한 세 가지 정의는 다음과 같다:

• 약한 공정성 (Weak fairness): 모든 요청은 결국 처리된다.
• 강한 공정성 (Strong fairness): 요청자는 동일한 횟수로 서비스받는다. N번의 arbitration 평균 기준으로, 어떤 요청자가 서비스받은 횟수와 다른 요청자가 받은 횟수의 차이는 ε 이내여야 한다. 종종 이 개념은 가중치 공정성(weighted fairness)으로 확장되어 요청자 i가 서비스받은 횟수는 그 가중치 wi에 비례해야 한다.
• FIFO 공정성: 요청자가 요청한 순서대로 서비스받는다. 빵집에서 번호표를 받아 순서대로 서비스받는 방식과 유사하다.

arbiter가 local하게는 공정하더라도, 그 arbiter를 사용하는 전체 시스템이 공정하지 않을 수 있다. 그림 18.3은 이러한 예를 보여준다. 네 개의 source r0~r3가 단일 destination으로 packet을 전송하는데, 이들은 세 개의 strongly fair한 2:1 arbiter를 통과한다. 각 arbiter는 두 입력에 대해 bandwidth를 반반씩 할당하지만, 최종적으로는 source들 간에 bandwidth가 공정하게 분배되지 않는다. r3는 한 번의 arbitration만 거쳐 전체 bandwidth의 절반을 얻지만, r0와 r1은 세 번의 arbitration을 거쳐야 하므로 각각 1/8만 얻는다. 이와 같은 문제와 해결 방안은 15.4.1절 및 본 장의 18.6절에서 더 자세히 설명된다.

18.3 고정 우선순위 Arbiter

우선순위를 선형적으로 정의하면, 이를 반복적(iterative) 회로로 구현할 수 있다. 그림 18.4의 고정 우선순위 arbiter가 그 예이다. 이 arbiter는 비트 셀(bit cell)들의 선형 배열로 구성된다. 각 비트 셀 i는 요청 입력 ri와 carry 입력 ci를 받아 grant 출력 gi와 carry 출력 ci+1을 생성한다.

carry 입력 ci는 더 높은 우선순위를 가진 요청이 자원을 아직 얻지 못했음을 나타내며, 이 셀에서 자원을 사용할 수 있음을 의미한다. 현재 요청 ri가 true이고 carry도 true이면, grant 라인을 assert하고 carry 출력을 deassert하여 자원이 이미 할당되었음을 나타낸다.

그림 18.4(a)와 같이 반복형 arbiter의 비트 셀을 구성할 수 있다. 이 비트 셀은 요청 입력 ri와 carry 입력 ci를 받아 grant 출력 gi와 carry 출력 ci+1을 생성한다. 이 논리를 식으로 표현하면 다음과 같다:

• gi = ri ∧ ci
• ci+1 = ¬ri ∧ ci

그림 18.4(b)는 이러한 방식으로 구성된 4비트 고정 우선순위 arbiter를 보여준다. 이 arbiter는 그림 18.4(a)의 비트 셀 4개로 구성된다. 단, 첫 번째와 마지막 비트 셀은 간소화되어 있다. 첫 번째 비트 셀은 c0이 항상 1이라는 점을 활용하며, 마지막 비트 셀은 c4를 생성할 필요가 없다는 점을 활용한다.

처음 보면, 반복형 arbiter의 지연 시간이 입력 개수에 비례해 선형적으로 증가할 것처럼 보인다. 실제로 그림 18.4처럼 구성된다면, 최악의 경우 carry가 한쪽 끝에서 다른 쪽 끝까지 전달되어야 하므로 선형 지연이 발생한다. 그러나 adder에서 사용되는 carry-lookahead 기법을 적용하면 지연 시간을 입력 개수에 대해 로그(logarithmic) 수준으로 줄일 수 있다 (Exercise 18.1 참고).

비록 반복형 구성 예시로는 유용하지만, 그림 18.4의 arbiter는 실제로는 전혀 공정하지 않다. 약한 공정성조차 만족하지 않는다. 예를 들어 요청 r0이 계속 assert되어 있으면, 다른 어떤 요청도 절대 서비스받지 못한다.

18.4 가변 우선순위 반복형 Arbiter

공정한 반복형 arbiter를 만들기 위해서는 매 cycle마다 우선순위를 바꾸면 된다. 그림 18.5는 이를 보여주는 예로, one-hot 우선순위 신호 p를 사용하여 가장 높은 우선순위 요청을 선택한다. p에서 한 비트만 1로 설정되며, 해당 위치의 요청이 가장 높은 우선순위를 가지며 이후 우선순위는 원형 carry chain을 따라 순환적으로 감소한다.

이 arbiter의 논리식은 다음과 같다:

• gi = ri ∧ (ci ∨ pi)
• ci+1 = ¬ri ∧ (ci ∨ pi)
• c0 = cn

18.4.1 Oblivious Arbiter

그림 18.5의 회로에 입력되는 우선순위 p는 여러 방식으로 생성할 수 있으며, 이 방식에 따라 arbitration의 성질이 달라진다. 만약 p가 r이나 g에 대한 정보 없이 생성된다면, 이는 oblivious arbiter가 된다. 예를 들어 shift register를 사용하여 매 cycle마다 우선순위를 한 칸씩 회전시키는 방식이나, 난수 발생기의 출력을 디코딩하여 p를 생성하는 방식 등이 있다.

이러한 rotating arbiter나 random arbiter는 약한 공정성은 만족한다. 결국 모든 요청은 언젠가 높은 우선순위를 얻게 되어 서비스받을 수 있다. 그러나 이들은 강한 공정성은 제공하지 못한다.

예를 들어, n-input arbiter에서 두 인접 요청 ri와 ri+1만 지속적으로 요청하고 나머지 입력은 모두 low라고 하자. 이 경우 ri+1이 승리하는 경우는 pi+1이 true일 때뿐이며, ri는 나머지 n−1개의 p 입력에 대해 모두 승리한다. 따라서 ri는 ri+1보다 n−1배 더 자주 grant를 받는다. 이 불공정함은 round-robin arbiter를 사용하면 해결할 수 있다.

18.4.2 Round-Robin Arbiter

Round-robin arbiter는 방금 서비스받은 요청자가 다음 arbitration에서 가장 낮은 우선순위를 갖도록 동작한다. 이는 현재의 grant 벡터 g로부터 다음 우선순위 벡터 p를 생성함으로써 구현할 수 있다. Verilog로 표현하면 다음과 같다:

 assign next_p = |g ? {g[n-2:0],g[n-1]}:p;

그림 18.6은 4비트 round-robin arbiter를 도식화한 것이다. 현재 cycle에 grant가 발생하면, 해당 gi 라인 하나가 high가 되고, 다음 cycle에는 pi+1이 high가 되어 그 다음 요청이 가장 높은 우선순위를 갖게 된다. 이전에 grant를 받았던 요청은 다음 arbitration에서 가장 낮은 우선순위를 갖는다. 만약 현재 cycle에 어떤 grant도 발생하지 않으면, anyg가 low가 되어 우선순위 상태는 유지된다.

Round-robin arbiter는 강한 공정성을 제공한다. ri가 서비스받으면 가장 낮은 우선순위가 되며, 다른 pending 요청들이 먼저 서비스된 후 다시 ri가 서비스된다.

18.4.3 Grant-Hold Circuit

지금까지 살펴본 arbiter들은 자원을 한 cycle씩만 할당한다. grant를 받은 클라이언트는 단 한 cycle 동안만 자원을 사용할 수 있으며, 이후 다시 arbitration을 해야 한다. 이 방식은 많은 애플리케이션에서 충분하지만, 18.1절에서 설명했듯이 몇몇 상황에서는 자원을 여러 cycle 동안 연속으로 사용하는 것이 필요하다. 예를 들어, 클라이언트가 packet을 output buffer로 전송하기 위해 3 cycle 동안 switch에 uninterrupted access가 필요할 수 있다.

grant-hold circuit을 사용하면 grant의 지속 시간을 연장할 수 있다. 그림 18.7은 이를 보여준다. Verilog 코드로 표현하면 다음과 같다:

 assign g = anyhold ? hold : gc ; // n-bit grant vector
 assign hold = last&h; // n-bit hold vector
 assign anyhold = |hold ; // hold not zero
 always @(posedge clk) last=g; // last cycle’s grant vector

grant를 받은 bit가 이전 cycle에서도 grant를 받고 있었고(last가 true), hold 라인 h가 assert되어 있다면, 해당 bit는 계속해서 grant를 받는다(gi가 계속 high 상태를 유지). 이 동안에는 arbitration이 비활성화된다.

18.4.4 Weighted Round-Robin Arbiter

일부 애플리케이션에서는 하나의 요청자가 다른 요청자보다 더 많은 grant를 받도록 제어된 불공정성을 요구한다. Weighted round-robin arbiter는 이러한 동작을 수행한다. 각 요청자 i는 weight wi를 할당받으며, 이 값은 요청자가 받을 수 있는 최대 grant 비율 fi를 나타낸다:

  fi = wi / W  여기서 W = ∑(j=0~n−1) wj

즉, 큰 weight를 가진 요청자는 많은 grant를 받고, 작은 weight를 가진 요청자는 적은 grant를 받는다. 예를 들어, 입력 weight가 1, 3, 5, 7이라면, 각각 전체 grant의 1/16, 3/16, 5/16, 7/16을 받는다.

그림 18.8과 같이, weighted round-robin arbiter는 각 요청자가 자신에게 할당된 quota를 초과했는지를 판단하는 회로를 arbiter 앞단에 배치하여 구성할 수 있다. 이 그림은 1비트 슬라이스를 보여주며, 이 회로는 weight 레지스터, 카운터, AND 게이트, 일반 arbiter로 구성된다.

preset 신호가 assert되면, 각 슬라이스의 카운터는 해당 weight로 초기화된다. 카운터 값이 0이 아닌 동안에는 AND 게이트가 활성화되어 요청이 arbiter로 전달된다. 요청자가 grant를 받을 때마다 카운터는 감소한다. 카운터가 0이 되면 AND 게이트가 비활성화되어 요청이 차단되며, 다음 preset까지 이 요청자는 grant를 받을 수 없다.

preset 신호는 W cycle마다 활성화된다. 모든 요청자들이 자신의 quota를 요청했다면, preset 구간이 끝날 때쯤 모든 카운터는 0이 된다. 일부 요청자가 자신의 quota를 사용하지 않는 경우, 나머지 요청자의 카운터는 더 빨리 0에 도달하여 preset 구간이 끝날 때까지 자원이 idle 상태로 남게 된다.

이러한 idle을 줄이기 위해 multistage arbiter를 사용하여 quota를 다 쓴 요청자도 idle cycle을 놓치지 않고 경쟁할 수 있도록 할 수 있다.

weight 비트 수를 정하는 것은 precision과 burstiness 사이의 trade-off를 발생시킨다. weight 비트를 많이 사용하면 정밀한 비율을 설정할 수 있지만, 그만큼 burstiness가 커진다. 각 요청자는 preset 구간인 W cycle 동안 평균적으로 quota만큼 보장받기 때문에, 이 간격이 길어질수록 초기에는 low-weight 요청자가 많이 받고, 이후 high-weight 요청자가 따라잡는 식의 불균일한 사용 패턴이 나타난다. (Exercise 18.2 참고)

18.5 Matrix Arbiter

Matrix arbiter는 가장 최근에 서비스받은 요청자의 우선순위를 가장 낮게 만드는 우선순위 방식을 구현한다. 이를 위해 상태 비트 wij로 구성된 삼각형 배열을 유지하며, 여기서 i < j이다. wij는 요청 i가 요청 j보다 우선이라는 의미이다. 배열의 대각선 원소는 필요하지 않으며, wji = ¬wij 이므로 상삼각형 부분만 저장하면 된다.

어떤 요청 k가 grant를 받으면, 해당 row wk의 모든 bit를 clear하고, column wk의 모든 bit를 set하여 요청 k가 가장 최근에 서비스된 것으로 처리하고 가장 낮은 우선순위가 되도록 한다.

그림 18.9는 4-input matrix arbiter를 보여준다. 상태는 상삼각형의 6개의 flip-flop (실선 박스)에 저장되며, 하삼각형의 음영 박스는 대칭 위치의 상태 bit의 반전값을 나타낸다.

요청이 assert되면 해당 row의 상태 bit와 AND 연산을 수행하여 낮은 우선순위의 요청들을 비활성화한다. 각 column에 대해, AND 결과들은 OR 게이트로 모여 해당 요청에 대한 disable 신호를 생성한다. 예를 들어, w02가 set되고 r0이 assert되면, dis2가 assert되어 r2 요청을 disable시킨다.

disable되지 않은 요청은 AND 게이트를 통해 해당 grant 출력으로 전달된다. grant가 발생하면 해당 row의 상태 bit를 clear하고, column의 상태 bit를 set하여 이 요청자가 이후 arbitration에서 가장 낮은 우선순위가 되도록 한다. 이 상태 변화는 다음 클럭 상승 에지에서 반영된다 (그림 18.10 참고).

정상 동작을 위해서는 matrix arbiter가 올바른 초기 상태로 설정되어야 한다. n-input arbiter의 가능한 상태는 2^[n(n−1)/2]개이지만, 입력 순열은 n!개에 불과하다. 의미 없는 상태나 순환(cycle)이 발생하는 상태는 위험하며 deadlock을 유발할 수 있다. 예를 들어, w01 = w12 = 1이고 w02 = 0이며 r0, r1, r2가 모두 assert되면, 서로를 disable시켜 아무도 grant를 받지 못한다.

(비트 오류 등으로 인해 arbiter가 불법 상태로 들어갈 경우 이를 복구하는 메커니즘을 마련하는 것도 중요하다.)

18.6 Queueing Arbiter

Matrix arbiter가 가장 최근에 서비스된 요청을 낮은 우선순위로 설정하는 방식이라면, Queueing arbiter는 FIFO 방식으로 요청을 처리한다. 그림 18.11처럼, 각 요청에 대해 assert 시점을 기준으로 timestamp를 부여하고, 이후 comparator tree를 통해 가장 오래된 요청을 선택한다.

Timer 블록은 arrival interval(일반적으로 클럭 cycle)마다 timestamp를 증가시키는 카운터이다. 요청이 도착하면(새로운 요청이 0→1로 전이되거나 이전 cycle에서 grant를 받고 계속 high 상태를 유지하는 경우), 현재 timestamp가 latch되어 stamp 블록에 저장되며 요청의 index(예: r0 → index 0, r1 → 1 등)와 함께 기록된다. 이때 요청은 index와 timestamp 쌍 (i, ti)로 표현된다.

요청이 없는 입력은 특별한 큰 값의 timestamp와 grant로 디코딩되지 않는 index로 표현된다. 이후 comparator tree에서 pairwise 비교를 통해 가장 작은 timestamp를 갖는 index iw를 찾는다. 각 comparator 노드는 두 요청을 비교해 더 빠른 timestamp를 가진 요청을 다음 단계로 전달한다. 마지막으로, 이 winning index iw가 디코딩되어 하나의 radial grant 신호로 변환된다.

arbiter의 cost는 주로 timestamp를 표현하기 위한 비트 수에 의해 결정되며, 이는 stamp 블록의 레지스터 크기를 좌우한다.

Queueing arbiter의 cost는 stamp 블록에 사용되는 레지스터 크기와 comparator tree의 comparator 폭에 의해 결정된다. 두 시간 관련 파라미터의 비율은 필요한 timestamp의 비트 수 wt를 결정한다:

  wt = log₂(Δt / ta)

여기서 Δt는 timestamp의 범위이고, ta는 요청 도착 간격이다. 두 값 모두 일반적으로 clock cycle 단위로 표현된다.

Δt는 예상 가능한 최대 요청 도착 시간 차이를 커버할 수 있을 만큼 커야 하며, timer rollover도 감당할 수 있어야 한다. 다음과 같이 정의된다:

  Δt = 2nTmax  (식 18.1)

여기서 n은 arbiter 입력 수, Tmax는 최대 서비스 시간이다. 식에서 2를 곱한 이유는 뒤에 설명된다.

Δt가 너무 커서 wt가 부담스러워지는 경우, ta를 증가시켜 비트 수를 줄일 수 있지만, 이 경우 정확도는 떨어지게 된다. 즉, arbiter는 요청 도착 시점을 ta 단위로 반올림하여 처리하게 되며, ta가 클수록 순서가 어긋날 수 있다.

타이머가 최대값에서 0으로 롤오버될 때, 새 요청이 기존 요청보다 더 작은 timestamp를 받는 일이 생기면, 큐의 앞쪽으로 끼어드는 부당한 동작이 발생할 수 있다.

이러한 문제는 모든 timestamp의 MSB를 현재 timer의 MSB와 XNOR 연산하여 비교하기 전에 보정하면 해결할 수 있다. 예를 들어, Δt = 16 (따라서 wt = 4), ta = 1일 경우, 요청 간 최대 시간 차 nTmax = 8이다. 타이머가 15에서 0으로 롤오버될 때, 모든 timestamp는 [8,15] 범위에 있게 된다. 이때 timestamp의 MSB를 보정하면 [0,7]로 변환되고, 새 요청은 8이 되어 새로운 요청이 늦게 들어온 것처럼 판단된다.

이 방식은 Δt가 요청 시간 간 최대 차이의 두 배가 되도록 요구하므로, 식 18.1에서 계수 2가 필요하다. Exercise 18.7에서는 Δt를 nTmax보다 약간 더 큰 값으로 줄이기 위한 방법을 다룬다.

서비스 시간이 작을 경우에는 Δt 요구 범위도 작다. 예를 들어, 모든 서비스 시간이 1인 4-input arbiter에서는 nTmax = 4이고, MSB 보정 방식 사용 시 Δt = 8이므로 3비트 timestamp면 충분하다. ta를 4로 완화하면 1비트만으로도 동작은 가능하지만, 이 경우 queueing arbiter의 공정성은 round-robin 수준과 다를 바 없게 된다.

Queueing arbiter는 여러 단계에 걸친 arbitration에서 글로벌(system-level) 공정성을 확보하는 데 특히 유용하다. 이 문제는 18.2절과 그림 18.3에서 다루었다. 시스템 수준의 공정성을 확보하려면, 각 요청(예: 각 패킷)에 대해 시스템 진입 시 timestamp를 부여해야 하며, 이 시점은 실제 arbitration 대기 큐에 들어가기 직전이다.

이를 위해 시스템 전체에 동기화된 timestamp counter와, 각 진입 지점마다 stamp module을 배치한다. 이렇게 부여된 timestamp는 이후 모든 arbitration 단계에서 유지되며, 새로 갱신되지 않는다. 또한 시스템 내 모든 queue는 timestamp 순으로 정렬되어야 하며, 가장 오래된 timestamp가 우선적으로 처리되어야 한다. 이렇게 전체 시스템에서 가장 작은 timestamp를 선택하도록 설계된 arbiter는 강한 시스템 수준의 공정성을 제공하게 된다. 예를 들어, 그림 18.3의 예에서는 모든 요청자가 전체 bandwidth의 정확히 0.25를 받게 된다.

18.7 연습문제

18.1 Carry-lookahead arbiter. 입력 수에 비례하지 않고 로그 비례한 시간에 동작하는 64-input fixed-priority arbiter를 설계하라. 힌트: 4비트 그룹으로 나누고, 각 그룹에 대해 propagate 신호를 계산하라. 이 propagate 신호는 그룹 내 carry가 끝까지 전달되는지를 의미한다. 이후 4비트 그룹들의 propagate 신호를 이용하여 16비트 그룹 propagate 신호를 생성하라.

18.2 Weighted round-robin. 4-input weighted round-robin arbiter에서 가중치가 각각 5, 5, 5, 49일 때, 모든 입력이 항상 요청하는 상황을 고려하라. 이 경우 arbiter의 grant 시간 순서를 설명하고, 이상적인 순서와 어떤 차이가 있는지 설명하라. 필요하면 이상적인 순서를 제공하는 arbiter를 도식으로 그려도 좋다.

18.3 Matrix arbiter 동작. 그림 18.9와 같은 4-input matrix arbiter가 있다고 하자. arbiter는 모든 상태 비트를 0으로 초기화한 후, 다음과 같은 요청 벡터를 매 cycle마다 받는다: r3...r0 = 1111, 1111, 1010, 1001. 각 cycle마다 어떤 grant가 발생하는지, 마지막에 matrix 상태는 어떻게 되는지를 서술하라.

18.4 Queueing arbiter 설계. 입력이 8개인 queueing arbiter를 설계하라. 각 입력의 최대 서비스 시간은 8 cycle이며, 어떤 8개의 서비스 시간 합도 32 cycle을 넘지 않는다. timing precision은 ta = 4 cycle 허용한다. timer rollover 처리를 위해 MSB 보정 기법을 사용할 경우, timestamp는 몇 비트가 필요한가?

18.5 Timer rollover. Figure 18.11과 같은 queueing arbiter에서 Δt = nTmax + 1일 때 timer rollover를 어떻게 처리할 수 있는지 설명하라.

18.6 Matrix arbiter 상태 오류. 어떤 i > j에 대해 wij의 상태 값이 illegal일 경우, 여러 요청이 동시에 grant를 받을 수 있는 상태가 존재하는가? 또한 arbiter 상태 오류를 탐지하고 수정하는 간단한 방법을 제안하라.

이 장에서는 라우터의 datapath를 구성하는 component들, 즉 input buffer, switch, output unit의 설계를 살펴본다. Input buffer는 flit들이 virtual channel, switch bandwidth, channel bandwidth를 기다리는 동안 저장된다. Input buffer는 중앙 집중식으로 구성하거나, physical channel 단위로 나누거나, virtual channel 단위로 나눌 수 있다. 중앙 buffer는 physical/virtual channel 간에 저장 공간을 유연하게 할당할 수 있지만, 대역폭 부족 때문에 실용적이지 않은 경우가 많다. 각 buffer partition 안에서 저장 공간은 circular buffer를 이용한 정적 할당, 또는 linked list를 이용한 동적 할당으로 관리할 수 있다.

Switch는 라우터의 핵심으로 flit이 input port에서 output port로 전환(switching)되는 곳이다. 중앙 buffer 자체도 input multiplexer와 output demultiplexer를 통해 switch 기능을 수행할 수 있다. 공유 bus 또한 switch 역할을 할 수 있는데, 이 경우 복잡한 switch 할당이 필요 없다는 장점이 있다. 입력이 버스를 획득하면 모든 출력으로 broadcast하기 때문이다. 그러나 내부 대역폭 활용이 비효율적이다. 대부분의 고성능 라우터는 crosspoint switch를 사용하며, switch 할당 문제를 단순화하고 고가의 channel bandwidth가 idle 상태가 되지 않도록 speedup을 적용하기도 한다.

17.1 Input Buffer Organization

Input buffer는 현대 라우터에서 가장 중요한 구조 중 하나다. Flow control protocol은 flit들이 라우터를 빠져나갈 때까지 대기할 공간을 이 buffer에 할당한다. 이 buffer들은 도착한 flit을 저장하여, pipeline stall이나 virtual/physical channel 경합으로 인해 패킷이 일시적으로 지연될 때 incoming channel의 속도를 늦추지 않아도 된다.

17.1.1 Buffer Partitioning

Input buffer의 partition 방식은 switch 설계와 밀접하게 연관된다. Input buffer는 전체 라우터에 걸쳐 하나로 묶거나, physical input channel 단위 또는 virtual channel 단위로 분할할 수 있다 (그림 17.1 참조).

• 중앙 메모리를 사용하는 경우(그림 17.1(a)), 모든 input buffer를 하나의 메모리에 저장할 수 있어 switch가 필요 없다. 그러나 실제로는 입력을 메모리로 multiplex하고 출력을 demultiplex하는 두 개의 switch가 필요한 셈이다. 이 구조의 장점은 메모리를 input port 간에 유연하게 할당할 수 있다는 점이다. 하지만 두 가지 단점이 있다:
  1. 중앙 메모리의 대역폭이 병목이 될 수 있다. 예를 들어 input port가 8개라면, 메모리는 한 클럭에 8개를 쓰고 8개를 읽어야 하므로 16배의 대역폭이 필요하다.
  2. flit을 write하기 위해 wide word로 만들기 위한 serialization/deserialization 작업 때문에 latency가 증가한다.
• 이러한 문제를 피하기 위해 input port마다 개별 메모리를 제공하는 방식(그림 17.1(b))이 있다. 총 메모리 대역폭은 동일하지만, 각 메모리는 input port의 2배만 되면 되므로 구현이 수월하고 latency도 낮다. 단, virtual channel 간 메모리 공유는 불가능하다.
• 각 virtual channel에 대해 개별 메모리를 제공하는 방식(그림 17.1(c))도 있다. 이 경우 하나의 physical channel에서 여러 virtual channel을 동시에 switch에서 접근할 수 있으므로 input speedup을 제공할 수 있다. 예를 들어 input port가 8개이고 각 port에 4개의 virtual channel이 있다면, 32개의 입력을 갖는 32×8 switch를 구성할 수 있다. 그러나 이런 방식은 idle 상태인 virtual channel의 메모리를 busy한 채널이 사용할 수 없어 buffer fragmentation 문제가 생긴다. 또한 작은 메모리들을 많이 사용해야 하므로 오버헤드가 크다.
• 절충안으로는 각 physical channel마다 소수의 output port를 가진 buffer를 제공하는 방식(그림 17.2(a))이 있다. Per-virtual-channel buffer를 두지 않고도 switch speedup을 얻을 수 있다. 이보다 저렴한 방식은 physical channel buffer를 다중 port 대신 partitioned buffer로 구성하는 것이다(그림 17.2(b)). 예를 들어 virtual channel이 4개이고 buffer를 2개로 나눈다면, 짝수 채널은 하나의 buffer에, 홀수 채널은 다른 buffer에 저장한다. 이 방식은 일부 유연성을 희생하지만 성능은 거의 비슷하고 면적 비용은 훨씬 낮다.

17.1.2 Input Buffer Data Structures

어떤 buffer 조직이든 flit과 packet이 메모리의 어디에 있는지 추적하고 free memory를 관리하기 위한 data structure가 필요하다. 여러 virtual channel이 하나의 메모리를 공유하는 경우라면, 공정하게 공간을 분배하는 메커니즘도 필요하다.

일반적으로 circular buffer와 linked list 두 가지 구조가 사용된다.

• Circular buffer는 관리가 간단하지만 buffer 공간이 고정적으로 partition되어야 한다.
• Linked list는 오버헤드는 크지만 다양한 buffer 간에 공간을 유연하게 공유할 수 있다.

여기서 buffer 또는 flit buffer는 특정 virtual channel 전체를 저장하는 구조를 뜻하고, cell 또는 flit cell은 개별 flit을 저장하는 단위를 뜻한다.

Circular buffer의 예는 그림 17.3에 있다. 고정된 FIRST와 LAST 포인터는 메모리 내에서 buffer의 경계를 나타내며, 이 포인터는 register를 통해 설정할 수 있지만, buffer 사용 중에는 변경할 수 없다. buffer의 내용은 Head 포인터 아래, Tail 포인터 위에 위치하며, 끝을 기준으로 wrap-around 될 수 있다.

새로운 요소를 추가하려면 tail 포인터가 가리키는 cell에 저장한 후, tail 포인터를 원형으로 증가시키면 된다. 이 연산은 C 코드로 다음과 같이 표현된다:

 mem[Tail] = new_flit ;
 Tail = Tail + 1 ;
 if(Tail > LAST) Tail = FIRST ;
 if(Tail == Head) Full=1;

그림 17.3
(a) flit a부터 f까지 총 여섯 개의 flit이 들어 있는 buffer
(b) flit a부터 d를 제거하고, flit g부터 j를 추가한 상태로 tail 포인터가 buffer 끝을 넘어 wrap-around된 모습
Circular buffer는 고정된 FIRST와 LAST 포인터로 메모리 내 영역이 정의되고, Head와 Tail 포인터로 현재 buffer의 내용을 나타낸다. 데이터는 tail 포인터 위치에 삽입되며, tail은 순환적으로 증가한다. 데이터는 head 포인터에서 제거되며, head 또한 순환적으로 증가한다.

마찬가지로 데이터를 제거할 때는 다음과 같다:

flit = mem[Head] ;
 Head = Head + 1 ;
 if(Head > LAST) Head = FIRST;
 if(Head == Tail) Empty=1;

두 코드 블록의 마지막 줄은 각각 buffer가 가득 찼는지 또는 비었는지를 감지한다. Head와 Tail 포인터가 같을 때 발생하며, 삽입에 의해 같아지면 Full 상태, 제거에 의해 같아지면 Empty 상태이다. 이 상태들은 외부 논리가 buffer가 Full일 때 삽입 요청을 막고, Empty일 때 제거 요청을 막기 위해 사용된다.

일반적인 구현에서는 위의 네 줄을 하나의 클럭 사이클 내에서 실행하는 logic으로 circular buffer를 구성한다. 많은 구현에서는 하나의 클럭에서 동시에 삽입과 제거가 가능하도록 설계되기도 한다.

buffer 크기가 2의 거듭제곱이고 해당 크기의 배수로 정렬되어 있으면(예: 16-flit buffer가 16의 배수 주소에 시작됨) 포인터의 wrap-around를 비교 연산 없이 구현할 수 있다. 이때 포인터의 하위 비트는 buffer 내부의 cell을, 상위 비트는 buffer 자체를 식별하는 데 사용된다. 예를 들어 flit buffer가 16 cell일 경우 포인터의 0~3비트는 cell을, 4비트 이상은 buffer를 나타낸다. 이때 3비트에서 4비트로의 carry를 막으면 포인터가 buffer의 끝에서 시작 위치로 wrap된다.

Linked list data structure는 그림 17.4에 나타나 있으며, buffer에 대한 free storage 할당의 유연성이 높지만 오버헤드와 복잡성이 증가한다. Linked list memory를 관리하려면 각 cell에 다음 cell을 가리키는 포인터가 있어야 하며, 이를 위해 포인터는 종종 flit cell과는 다른 다중 포트 메모리에 저장된다. 각 buffer는 head와 tail 포인터로 구성되며, free 상태인 cell들은 free list로 연결된다.

초기에는 모든 cell이 free list에 있고, 모든 buffer의 head/tail 포인터는 NULL이다. buffer마다 현재 저장된 cell 수를 나타내는 count register와 free list에 있는 cell 수를 나타내는 count register도 유지된다.

다음은 flit을 삽입하는 연산이다:

 if(Free != NULL) {
 mem[Free] = new_flit ;// store flit into head of free list
 if(Tail != NULL)
 ptr[Tail] = Free ; // link onto buffer list- if
 Tail = Free ; // it exists
 Free = ptr[Free] ;	// unlink free cell
 ptr[Tail] = NULL ;	// optional- clear link to free list
 if(Head == NULL)	 // if buffer was empty
 Head = Tail ;		// head and tail both point at this cell
 } else ERROR ;		 // no cells left on free list

이러한 삽입은 단일 cycle 내에서도 가능하나, dual-ported buffer가 필요하다. 이전 tail cell의 포인터를 쓰고, free list의 head를 읽는 작업이 동시에 필요하기 때문이다. 새로운 tail cell의 포인터를 NULL로 초기화하는 것은 consistency check를 위한 좋은 방법이지만 필수는 아니다.

그림 17.4

• (a) linked list로 연결된 4개의 flit cell로 구성된 buffer. Head는 첫 번째 cell을, Tail은 마지막 cell을 가리킨다. Free는 5개의 free cell로 구성된 list를 가리킨다.
• (b) flit e를 추가하면서 free list에서 cell을 제거하고 buffer list에 연결한 상태
• (c) flit a를 제거하고 해당 cell을 free list에 다시 반환한 상태

flit 제거는 다음과 같은 절차를 따른다:

if(Head != NULL) {
 flit = mem[Head] ; // get the flit
 Next = ptr[Head] ; // save pointer to next flit in buffer
 ptr[Head] = Free ; // put old head cell on the free list
 Free = Head ;		 //
 if(Head == Tail) { // if this was the last cell- empty list
 Head = NULL ;
 Tail = NULL ;
 } else { 		// otherwise, follow the link to the
 Head = Next ;	// next cell
 }
 } else ERROR ; // attempt to remove from empty buffer

flit 제거는 단일 포트 pointer memory만으로도 한 cycle 내에서 가능하며, head cell의 link를 읽고 free list에 연결하는 read-modify-write 연산만 있으면 된다.

linked list의 단점은 포인터 memory 조작의 복잡성이다. 삽입/제거 시 포인터 메모리에 대한 다수의 연산이 필요하며, 에러 처리도 복잡해진다. 단순 저장 공간 측면에서의 오버헤드는 작다. 예를 들어, 8바이트 flit에 8비트 포인터를 붙이는 경우 12.5%의 오버헤드만 추가된다.

그러나 linked list 구조에서 발생한 비트 오류는 circular buffer보다 훨씬 심각한 영향을 끼칠 수 있다. circular buffer에서는 단순히 flit 데이터가 손상되거나 head/tail 포인터 오류로 일부 flit만 누락될 수 있지만, 상태 초기화(Head = Tail = FIRST)를 통해 오류를 국한시킬 수 있다.

반면, linked list에서는 pointer field에 비트 오류가 생기면 free list 전체가 끊기거나, 두 buffer가 동일한 cell을 공유하게 되는 등 심각한 문제가 발생한다. 이는 단일 오류가 전체 buffer 시스템에 걸쳐 영향을 미친다는 것을 의미하며, 조기 탐지와 격리가 중요하다.

이를 위한 에러 제어 방식으로는 방어적 코딩(defensive coding)과 백그라운드 모니터링이 있다. 방어적 코딩은 포인터에 패리티 비트를 추가하여 1비트 오류를 조기 탐지하고, flit cell에 free/allocated 상태를 나타내는 type field를 추가하여 일관성 체크에 활용한다. 또한 buffer 번호 또는 그 해시값을 함께 저장하여 오류 감지를 용이하게 할 수 있다.

할당된 cell에 buffer 번호나 그 해시 값을 저장하면, cell이 다른 buffer로 잘못 옮겨졌는지 확인할 수 있다. 마지막으로, 각 cell에 시퀀스 번호나 하위 몇 비트만이라도 저장하면, 입력 유닛이 flit 순서가 바뀌지 않았는지 확인할 수 있다. 삽입 및 제거 연산은 포인터의 유효성, 읽은 cell의 type 및 buffer 번호가 예상과 일치하는지, 제거되는 cell의 시퀀스 번호가 순서대로인지 검증한다. 예외가 감지되면 해당 buffer를 비활성화하고, 일반적으로 소프트웨어로 구현된 오류 처리 루틴이 호출된다.

백그라운드 모니터링 프로세스는 방어적 코딩을 보완하며, 접근되지 않은 cell의 일관성을 확인한다. 이는 linked list 중간에서 발생한 오류를 조기에 감지할 수 있게 한다. 이 모니터링 프로세스는 각 buffer의 head부터 tail까지 리스트를 순회하며, buffer의 cell 수가 count와 일치하는지, 모든 cell이 할당 상태인지, 각 cell이 올바른 buffer에 속해 있는지, parity 오류가 없는지 등을 확인한다. free list도 유사하게 확인한다. 이 리스트 순회는 마치 mark-and-sweep 방식의 garbage collection처럼, 어떠한 리스트에도 연결되지 않은 cell을 탐지할 수 있다. 대부분의 구현에서 이 모니터는 buffer memory의 idle cycle을 활용하는 하드웨어 프로세스로 구성되며, 오류가 감지되면 buffer는 비활성화되고 소프트웨어 오류 처리 루틴이 실행된다.

17.1.3 Input Buffer Allocation

Input buffer를 linked list 구조로 구현하면, 하나의 메모리를 공유하는 여러 buffer 간에 저장 공간을 동적으로 할당할 수 있다. 이 동적 메모리 할당은 busy한 virtual channel에 더 많은 메모리를, idle한 채널에는 적은 메모리를 배정할 수 있어 메모리 활용 효율을 높인다. 연구에 따르면 많은 수의 virtual channel이 있을 경우 부하가 고르게 분산되지 않고 일부는 idle 상태이고 일부는 과부하 상태가 되기 쉽다. 따라서 busy한 채널에 더 많은 메모리를 할당하는 것이 유리하다.

하지만 이를 신중하게 하지 않으면 virtual channel의 이점을 오히려 해칠 수 있다. 예를 들어 한 greedy한 virtual channel이 모든 메모리를 점유한 뒤 block 상태가 된다면, 다른 채널은 진전을 전혀 하지 못하게 된다. 이로 인해 virtual channel 간에 의존성이 생기고 deadlock이 발생할 수 있다.

이를 방지하기 위해 각 virtual channel buffer에는 해당 채널의 flit 개수를 추적하는 count register를 추가한다. free list에 남은 cell 개수를 추적하는 register도 하나 추가한다. 이 두 count 값을 활용해 다양한 buffer 할당 정책을 구현할 수 있다. 정책의 입력은 현재 count 상태이며, 출력은 각 virtual channel이 buffer를 하나 더 할당받을 수 있는지 여부이다.

예를 들어 가장 간단한 정책은 각 virtual channel buffer에 하나의 flit 저장 공간을 예약하는 것이다. 이는 특정 channel이 전체 메모리를 독점한 후 block됨으로써 다른 channel의 진전을 막는 상황을 방지한다. 최소한 각 채널이 하나의 flit은 처리할 수 있게 보장하는 방식이다.

이 정책을 구현하기 위해 다음 두 조건 중 하나를 만족하면 virtual channel이 buffer에 flit을 삽입할 수 있다:
(a) 현재 buffer가 비어 있는 경우 (모든 채널이 최소한 하나의 flit을 보장받음)
(b) free buffer의 수가 count가 0인 virtual channel buffer의 수보다 많을 경우

이 정책을 쉽게 관리하기 위해 free cell을 reserved cell과 floating cell로 나누어 추적한다. Reserved cell은 각 virtual channel 단위로 관리되며, buffer가 비어 있거나 첫 flit이 삽입될 때 증가하거나 감소한다. 한편, flit이 1개 이상 존재하는 buffer에서의 삽입/제거는 floating cell count를 조정한다. 조건 (b)는 floating cell count가 0인지 여부를 확인하는 것으로 처리할 수 있다.

이 단순한 정책은 deadlock을 방지하지만 buffer 할당의 불균형을 초래할 수 있다. 이 문제를 해결하는 방법 중 하나는 sliding limit allocator를 사용하는 것이다. 이 방식은 두 개의 파라미터 r과 f로 정의된다.

• r: 각 buffer에 예약된 cell 수 (deadlock 방지를 위해 최소 1 이상)
• f: 예약된 cell을 제외하고 남은 cell 중 어느 하나의 buffer에 할당할 수 있는 최대 비율

이 sliding limit allocator를 구현하기 위해, 두 개의 free cell counter를 유지한다:

• reserved cell용 Nr
• floating cell용 Nf

buffer b에 flit을 삽입하려면, 다음 조건 중 하나를 만족해야 한다:

• Nb < r: reserved pool에서 할당하며 Nr 감소
• r ≤ Nb < f×Nf + r: floating pool에서 할당하며 Nf 감소

이 정책의 aggressiveness는 f 값으로 조절된다.

• f = 1일 경우, 하나의 buffer가 모든 free pool을 사용할 수 있으며, 이는 고정 예약 정책과 동일하다.
• f = 1/B일 경우 (B는 buffer 개수), 각 buffer는 전체 pool의 1/B만 사용 가능하며, 고정 partition 정책과 같다.
• 일반적으로는 이 두 극단 사이의 값이 유용하다.
  예:
  • f = 0.5 → 어떤 buffer도 전체 floating pool의 절반 이상 사용 불가
  • f = 2/B → 어떤 buffer도 고정 partition보다 두 배 이상 공간을 사용하지 못함

17.2 Switches

Switch는 라우터의 핵심이다. 패킷과 flit이 원하는 output port로 실제로 전달되는 곳이 바로 switch이다. 설계에서 가장 중요한 요소는 speedup이다. 이는 switch가 제공하는 bandwidth와 full throughput을 지원하는 데 필요한 최소 bandwidth의 비율이다. Speedup이 있으면 switch 할당을 단순화하고 throughput을 높이며 latency를 줄일 수 있다. 이 speedup은 switch의 입력측과 출력측에 각각 독립적으로 설정할 수 있다.

같은 speedup을 갖는 switch도 여러 방식으로 구현 가능하다. flit 하나를 처리하는 시간이 여러 clock cycle에 걸쳐 있을 경우, 공간적 switching 외에 time-domain switching(bus처럼)을 사용할 수 있다. 또는 여러 작은 switch를 직렬로 구성하여 하나의 소형 네트워크로 구성할 수도 있다. 다만, 이와 같은 multistage switch는 복잡한 할당 및 flow control 문제를 야기하므로 간단한 경우에만 적합하다.

17.2.1 Bus Switches

Bus를 switch로 사용하는 경우는, flit 하나의 시간(flit time)이 내부 clock cycle(phit time)보다 길고 port 수보다 많을 때이다. 그림 17.5는 이를 나타낸다. 각 input deserializer는 phit들을 모아 일정 수(P)에 도달하면 버스를 arbitration하고, 버스를 획득하면 P개의 phit을 병렬로 출력 serializer에 전송한다. 출력 serializer는 이 phit들을 순차적으로 전송한다.

이 구조가 bandwidth 낭비 없이 동작하려면 flit의 길이가 P의 배수여야 한다. 예시는 input/output port가 각각 4개이며, flit은 4개의 phit로 구성된다. 모든 flit은 같은 시점에 첫 번째 phit을 가지며 정렬된다.

버스 arbitration은 매우 간단한 고정 스케줄 방식으로,

• input port 0 → phit cycle 0
• input port 1 → phit cycle 1
• input port 2 → phit cycle 2
• input port 3 → phit cycle 3
  으로 순차적으로 버스를 할당받는다.

bus switch에서는 speedup이 1이면 충분하다. 각 input은 자신의 cycle에 원하는 출력을 항상 사용할 수 있기 때문이다. 더 높은 speedup은 비용만 증가시키고 성능 향상은 없다.

그림 17.6은 4×4 bus switch의 타이밍 다이어그램을 보여준다.

• 첫 번째 flit time 동안 flit a, f, k, p가 input port에 도착
• 두 번째 flit time에는 b, g, l, q
• 세 번째 flit time에는 c, h, m, r
• i번째 flit이 도착하는 동안, i−1번째 flit이 bus로 전송되고, i−2번째 flit이 output port에서 재직렬화된다.

버스 구조는 매우 단순하지만, 그 단순성은 port bandwidth 낭비와 latency 증가를 대가로 한다.

• bus bandwidth = P × b
• 그러나 각 input/output serializer는 P × b의 대역폭이 필요하므로, 총 I/O 대역폭은 P² × b이다.
• 단, 실제 사용되는 대역폭은 P분의 1 수준이므로 비효율적이다.

칩 내부 구현에서는 이 초과 대역폭이 치명적이지 않다. 그림 17.7에서처럼 버스 라인을 deserializer 및 serializer 위로 직접 배치하면 배선 비용은 크지 않다. 실제로 이 구조는 동일 bandwidth의 crossbar switch에 비해 배선 복잡도가 2배 수준이다(2P×P vs P×P). 또한 bus switch의 serializer/deserializer는 2P phit의 저장 공간이 필요하며, crossbar는 상태가 없는 구조(stateless)이다.

그림 17.7은 4×4 bus switch의 floorplan 및 배선 구조를 보여준다. 입력/출력 라인은 phit 단위로 수평 방향으로 흐르며, 각 입력 라인은 input deserializer(음영처리된 박스)로 연결되고, 각 출력 라인은 output serializer(해칭 처리된 박스)가 구동한다. 4-phit-wide bus는 수직 방향으로 serializer 및 deserializer 위를 가로지른다.

bus switch의 latency와 coarse granularity는 초과 대역폭보다 더 심각한 제약이 된다. 그림 17.6에서처럼, bus switch는 최소 P phit 단위로 동작해야 한다. flit 크기가 이보다 작다면 bus switch는 적합하지 않다. 또한 bus switch의 latency는 2P phit 시간이다. 이는 input을 deserialize하고 output을 정렬하는 데 필요한 시간 때문이다. 반면, crossbar는 단 1 phit 시간만의 지연만 갖는다.

bus switch와 crossbar 사이의 중간 방식으로 multiple-bus switch가 있다. 그림 17.8은 출력 분할 방식의 switch 예시로, 두 개의 버스를 사용한다. Output 0과 1은 Bus 1을, Output 2와 3은 Bus 2를 공유한다. 각 bus가 제공하는 output 수를 절반으로 줄이면, 출력을 유지하기 위해 매 cycle 운반해야 하는 phit 수도 절반이 되므로 serialization latency가 절반으로 줄어든다. 하지만 이는 allocation을 더 복잡하게 만든다. 더 이상 고정된 할당 방식은 사용할 수 없고, cycle마다 input과 output port를 매칭하는 문제를 해결해야 한다.

그림 17.8의 multiple-bus 구조는 2-phit wide 4×2 crosspoint switch와 동일한 구성이다. 각 4×2 switch 출력은 두 개의 output serializer를 구동하며, 이 serializer는 bus로부터 2 phit 폭의 데이터를 받아 한 번에 1 phit씩 출력한다. 극단적으로는, 각 출력을 독립된 bus에 연결하면 이 구조는 P×P crosspoint switch와 동일하게 된다.

17.2.2 Crossbar Switches

6.2절에서 설명한 것처럼, n×m crossbar (crosspoint) switch는 n개의 입력을 m개의 출력에 각각 연결할 수 있다. 그림 17.9는 crossbar를 나타내는 기호이며, 구조에 대한 상세한 설명은 6.2절에서 다루었으므로 여기서는 생략한다.

라우터 datapath의 switch로 crossbar를 사용할 때 주요 고려 사항은 speedup이다. 이는 제공되는 bandwidth와 필요한 bandwidth의 비율을 의미한다. crossbar의 입력, 출력, 또는 양쪽 모두에 대해 speedup을 제공할 수 있다. 이 speedup은 공간적 방법(추가 입력선) 또는

flit = mem[Head] ;
 Head = Head + 1 ;
 if(Head > LAST) Head = FIRST;
 if(Head == Tail) Empty=1;

시간적 방법(더 높은 대역폭 입력)으로 구현할 수 있다.

• 그림 17.10(b): 입력 측에 speedup이 있는 예
• 그림 17.11(a): 출력 측에 speedup이 있는 예
• 그림 17.11(b): 양쪽에 speedup이 있는 예

crossbar에 speedup을 적용하면 switch allocation을 간소화하거나 단순한 allocator를 사용하더라도 더 좋은 성능을 낼 수 있다. 특히 flit 크기가 작고 latency 요구가 낮을수록, 복잡한 allocator 대신 speedup을 통해 switch를 구성하는 것이 더 저렴하다.

switch allocation은 crossbar의 입력과 출력을 충돌 없이 flit 간에 연결하는 작업이며, 이 주제는 19장에서 자세히 다룬다. 여기서는 random separable allocator를 사용해 다양한 speedup 수준에서 switch 성능을 비교한다.

random separable allocator는 다음과 같이 작동한다:

1. 각 input buffer는 기다리는 flit 중 하나를 무작위로 선택해 crossbar의 각 입력에 할당한다.
2. uniform traffic이라고 가정할 때, 각 출력은 선택된 입력 flit이 해당 출력으로 향할 확률이 동일하다.
3. 각 출력은 자신을 요청하는 입력들 중에서 하나의 flit을 무작위로 선택해 수신한다.

예를 들어 입력과 출력이 k개씩 있는 라우터에서 입력 측 speedup이 s이고 출력 측 speedup은 없다면, crossbar는 총 sk개의 입력을 가진다. 이 경우, 할당의 첫 단계에서 선택된 sk개의 flit 중 하나라도 특정 출력으로 향할 확률이 switch의 throughput 𝜌가 된다. 이는 다음과 같은 수식으로 주어진다:

𝜌=1−(k−1k)sk𝜌 = 1 - \left( \frac{k - 1}{k} \right)^{sk}𝜌=1−(kk−1​)sk

이 수식은, k개의 입력이 있고 그중 s개의 입력이 각 출력에 무작위로 선택될 확률을 바탕으로, 적어도 하나가 특정 출력을 향할 확률을 나타낸다.

그림 17.10

• (a) 4×4 switch로, 입력 speedup이 1이다. 입력 수와 출력 수가 같고, 모든 포트는 단위 대역폭을 가진다.
• (b) 입력 speedup이 2인 구조로, 출력 수의 두 배만큼 입력이 존재한다. 이는 더 간단한 할당 문제를 만든다.

그림 17.12에서는 4개의 출력을 가진 switch에 대해 throughput과 input speedup의 관계를 보여준다.

• speedup이 없는 경우 → 68% capacity
• speedup이 2일 경우 → 90% capacity
• speedup이 3일 경우 → 97% capacity

입력 speedup이 4에 도달하면 (일반적으로 k에 해당), 더 이상 allocator가 필요 없다. 이때, 각 input buffer의 crossbar 입력을 특정 출력 포트에 고정할 수 있으며, 이는 17.2.1절에서 설명한 bus switch와 동일한 상황이 된다. 즉, 100% throughput을 trivial arbitration으로 달성할 수 있다. 따라서 speedup이 k 이상인 switch를 만드는 것은 불필요하다.

출력 측에 speedup을 적용한 switch도, 동일한 수준의 input speedup을 가진 switch와 동일한 throughput을 separable allocator를 통해 달성할 수 있다.

그림 17.11 설명 – Crossbar Output Speedup

• (a) 출력 speedup이 2인 4×4 switch. 각 output port에 2개의 output buffer가 연결되어 있음.
• (b) 입력과 출력 양쪽에 speedup이 2인 switch. 입력은 2배로 늘어난 buffer를 통해 들어오고, 출력도 2배의 속도로 처리됨.

이 경우, separable allocator는 반대 방향으로 동작한다. 즉, 각 출력 포트는 자신에게 도착해야 하는 flit을 기다리며, 해당 flit을 가진 입력 포트에 요청을 보낸다. 하지만 이 방식은 입력 포트의 정보를 출력 포트까지 전달해야 하므로 실제 구현이 어렵다. 또한 출력 버퍼링이 필요하기 때문에, 일반적으로는 출력 speedup보다는 입력 speedup이 선호된다.

입출력 모두에 speedup이 있는 switch는 throughput이 1을 초과할 수도 있다. 물론 input/output buffer가 유한하므로 지속적인 처리에는 한계가 있다. 입력 speedup을 si, 출력 speedup을 so라고 하고, si ≥ so라면, 전체 speedup은 so이며, 상대적인 입력 speedup은 si/so로 간주할 수 있다. 이때 throughput 𝜌는 다음과 같이 주어진다:

𝜌=so(1−(k−1k)(si⋅k)/so)𝜌 = so \left(1 - \left( \frac{k-1}{k} \right)^{(si \cdot k)/so} \right)𝜌=so(1−(kk−1​)(si⋅k)/so)

그림 17.12 – Throughput vs Input Speedup

이 그림은 출력 포트 수 k = 4인 crossbar switch에 대해 input speedup에 따른 throughput을 보여준다. random separable allocator를 1회 적용한 경우:

• speedup = 1 → throughput 약 68%
• speedup = 2 → throughput 약 90%
• speedup = 3 → throughput 약 97%
• speedup = 4 → throughput 약 100% 도달

대부분의 경우 crossbar는 전체 speedup이 1.2~1.5 사이일 때 100% throughput을 비교적 간단한 할당기와 낮은 latency로 달성할 수 있다. 이후 input 포트를 두 배로 늘려 할당기를 더 단순화하는 것이 일반적이다.

17.2.3 Network Switches

switch는 여러 개의 작은 switch로 구성된 network 형태로도 구현할 수 있다. 예를 들어, 3D torus network에서 dimension-order router를 구현하기 위해 필요한 7×7 switch는 3개의 3×3 switch로 구성할 수 있다(그림 17.13 참조). 이 구조는 crosspoint 수를 49개에서 27개로 줄여준다.

또한, 각 dimension을 +/- 방향으로 분리하여 더 세분화할 수도 있다(그림 17.14 참조). 이때 전체 crosspoint 수는 33개로 증가하지만, 각 switch는 2×2 크기로 작아진다.

이러한 partitioning은 전체 crosspoint 수를 줄이고 logic의 locality를 개선하여 배선 길이를 줄이는 효과가 있다. 그러나 전체 경로를 동시에 할당하려면 제어가 복잡해지며, 각 partition 사이에 flit buffer가 필요하다. 또한 traffic 패턴이나 routing 방식에 따라 내부 링크의 부하가 외부 채널보다 더 커질 수 있다.

따라서 특별한 이유가 없다면 switch를 여러 개의 작은 switch로 나누는 것은 피하는 것이 바람직하다. 단, 패키징 계층 구조에 따라 switch를 나눠야 하는 경우는 예외다.

17.3 Output Organization

그림 16.1에서 본 것처럼, output unit의 datapath는 주로 FIFO buffer로 구성되며, switch의 속도를 output channel의 속도에 맞추기 위한 역할을 한다. 출력 speedup이 없는 switch에서는 datapath가 필요 없으며, flit은 switch를 통과하자마자 직접 output channel로 전송된다.

반면 출력 speedup이 있는 switch에서는 switch와 채널 사이에 flit을 임시 저장할 수 있는 FIFO buffer가 필요하다.

이 output buffer는 virtual channel 별로 분할할 필요가 없다. 하나의 공용 FIFO buffer를 사용해도, 각 virtual channel 간의 의존성이 생기지 않는다. 그 이유는 output FIFO가 절대 block되지 않기 때문이다. 매 flit 시간마다, FIFO의 head에 flit이 있으면 이를 channel로 전송하고, downstream buffer 상태와 무관하게 동작한다. 따라서 backpressure는 output buffer에는 전달되지 않고, 대신 switch pipeline의 SA 단계에서 입력 측 traffic을 조절하게 된다.

하지만 output buffer가 overflow되지 않도록 하기 위해, switch allocator에 backpressure를 제공해야 한다. buffer 점유량이 특정 임계치를 초과하면, output buffer는 switch allocator에 해당 출력 포트로의 전송을 일시 중단하라고 알린다.

output buffer는 일반적으로 2~4 flit 정도면 충분하다. switch와 채널 간 속도 차이를 맞추는 데 이 정도면 충분하고, 그 이상 buffer를 늘려도 성능 향상 없이 면적만 낭비된다.

17.4 사례 연구: IBM Colony Router의 Datapath

IBM Colony router는 IBM SP 상호연결 네트워크 계열의 3세대 라우터로, 이전 세대인 Vulcan router에 대한 설명은 11.3절에서 다루었으며 Colony는 유사한 내부 구조와 동일한 다단계 네트워크 토폴로지를 채택하고 있다. Colony에는 여러 향상된 기능이 추가되었는데, 대표적으로는 더 높은 신호 속도, 더 빠른 내부 클럭 사이클, adaptive 및 multicast routing 지원이 포함된다. 이 결과, 대규모 상호연결 네트워크에까지 확장 가능한 router가 되었고, 예로는 8,192개의 프로세서를 가진 IBM SP 슈퍼컴퓨터인 ASCI White가 있으며, 이는 2000년부터 2001년까지 세계에서 가장 빠른 컴퓨터였다.

그림 17.15는 Colony 내부 구조를 보여준다. 8×8 switch는 hybrid datapath 구조를 채택하며, 이는 shared central memory와 input-queued bypass crossbar를 함께 사용하여 packet을 저장하고 전송한다. 어떤 packet이 switch의 input port에 도착하면, 먼저 bypass crossbar에 접근 요청을 한다. 요청한 output port가 사용 가능하면, packet은 즉시 router를 통과하며 pipeline 처리되어 지연이 최소화된다. 네트워크 부하가 낮을 때는 대부분의 packet이 bypass crossbar 접근에 성공하므로, 전체 지연은 일반적인 input-queued router와 거의 비슷해진다.

만약 bypass crossbar 접근에 실패하고, 8개의 flit으로 구성된 chunk 하나가 input port에 도착하면, 해당 packet은 central memory 접근을 요청한다. 이 요청은 결국 반드시 처리된다. 8개의 input port가 모두 block되고 central memory 접근이 동시에 필요한 경우도 있으므로, memory의 대역폭은 router의 총 입력 대역폭과 같아야 한다. 이론적으로는 16포트 SRAM (각 input/output port용)으로 구현 가능하지만, 실제로는 고포트 SRAM은 느리고 고가이기 때문에 부적절하다.

대신 Colony router는 8-flit 너비의 2-port SRAM으로 central memory를 구성하였다. SRAM의 read/write 포트를 시간 분할 방식으로 다루어, 각 input/output port가 8-flit chunk 전체를 한 번에 전송하도록 하였다. 동일 cycle에 여러 포트가 memory 접근을 요청하면, least recently used (LRU) 방식으로 순서를 정해 접근하게 된다. 이처럼 time-multiplex된 wide banked SRAM은 현실적인 구현을 가능하게 하지만, granularity가 8-flit 단위로 커져서, packet 길이가 8의 배수가 아닐 경우 bandwidth 낭비가 발생한다.

이를 최적화하기 위해, wide SRAM은 2-flit 너비의 4개 bank로 나뉜다. 각 포트는 한 cycle에 1 flit씩 순차적으로 전송하며, access가 staggered 방식으로 이루어진다. 예를 들어 input 1은 첫 cycle에 첫 flit, 다음 cycle에 두 번째 flit을 전송한다. 이 구조는 각 포트가 1-flit 너비의 채널로 SRAM에 연결될 수 있도록 하며, input/output 포트에서 central memory 접근을 위해 각각 하나의 crossbar가 필요하다. 만약 bank 접근이 동시에 이뤄진다면, 포트마다 8배 폭의 채널이 필요하므로 배선이 매우 복잡해졌을 것이다.

Colony의 central memory는 linked list 구조를 통해 관리된다. 각 chunk는 두 개의 필드를 추가로 가지고 있으며:

• 첫 번째 필드는 next packet pointer, 각 output은 FirstP / LastP 포인터로 자신에게 도착할 packet 리스트를 유지함.
• 두 번째 필드는 next chunk pointer, 각 packet은 여러 chunk로 구성될 수 있으므로 chunk 단위 리스트는 FirstC / LastC로 관리됨.
• 또한 사용 가능한 chunk들은 free list로 관리되며, head 포인터는 Free, 두 번째 엔트리는 FreeList로 관리되어 read/write를 동시에 지원함.

그림 17.16은 이러한 linked list 구조의 예시이다.

• (a)에서는 두 개의 packet이 central buffer에 저장되어 있으며,
• (b)에서는 packet A의 첫 chunk가 읽히고, packet B의 chunk가 새로 기록된다.

읽기는 FirstC가 NULL인지 확인하여 새로운 packet이 필요한지 판단하고, 그에 따라 FirstP를 따라 첫 chunk를 읽고, FirstC 및 FirstP를 갱신한다. freed chunk는 free list로 이동된다. 쓰기는 free list에서 chunk를 꺼내 데이터를 저장하고, 기존 packet에 이어지는 chunk이면 LastC를 따라 next chunk pointer를 설정한다.

17.5 참고 문헌

• Tamir & Frazier, Stunkel 등은 동적 buffer 관리 기법을 자세히 설명하였다.
• J-Machine, Cray T3D 등은 dimension 단위로 switch를 분할하여 구현을 단순화하였다.
• Nojima 등은 최대 분할 설계를 제시하였고,
• Torus Routing Chip, SGI SPIDER, Cray T3E는 crossbar 기반 switch에 speedup을 적용하였다.
• Shared memory 기반 접근은 Katevenis 및 이 장의 Colony 설계에서 볼 수 있다.
• HIPIQS 아키텍처는 input-queued 방식에 speedup 및 동적 buffer 관리를 결합하였다.
• Ahmadi & Denzel, Tobagi는 다양한 datapath 구조에 대한 훌륭한 서베이를 제공하였다.

17.6 연습문제

17.1 Circular buffer 관리 하드웨어
→ 삽입 및 제거를 동시에 수행하는 register-transfer-level 다이어그램을 그리라. full/empty 상태 판단 로직을 포함하라. Verilog로 구현해도 좋다.

17.2 Linked-list buffer 관리 하드웨어
→ 단일 cycle 내에 삽입 또는 제거가 가능한 linked-list 구조도 또는 Verilog 코드를 그리라.

17.3 Bus 기반 switch 설계
→ P=7의 입력/출력 포트를 가진 router와 8 phit 크기의 flit이 있다. 효율적인 bus switch 설계를 설명하라. 매 cycle bus가 운반해야 할 phit 수는?

17.4 입력 분할 bus 기반 switch
→ 두 개의 bus에 각각 두 개의 입력이 연결되고, 각 출력은 두 bus 중 하나에서 읽을 수 있는 구조를 그려라. allocation 방법을 설명하라. 출력이 두 bus에서 동시에 읽을 수 있는 경우 방법이 어떻게 달라지는가?

17.5 이중 분할된 bus 기반 switch
→ 입력과 출력을 두 그룹으로 분할한 8포트 switch 구조를 그리고, 네 개의 독립적인 bus를 사용하는 구조를 설명하라.

17.6 Memory switch 분할
→ 그림 17.1(a)의 memory switch 구조에서 출력이 두 그룹으로 나뉘었을 때 필요한 메모리 수와 너비를 일반화하라.

17.7 Buffered crossbar
→ 위의 memory switch 구조에 대해 입력과 출력을 P개 그룹으로 나누고, 메모리 수와 너비를 계산하라.

17.8 두 개의 free list entry 추적의 장점
→ IBM Colony linked list 구조에서 첫 번째 및 두 번째 free entry를 추적할 때, 삽입/삭제/simultaneous 수행을 위한 pseudocode를 작성하라. 각각 단일 read/write 포트를 가진 3개의 메모리(data, packet pointer, chunk pointer)를 사용하라.

라우터는 register, switch, function unit, control logic으로 구성되며, 목적지로 향하는 flit을 버퍼링하고 전달하는 데 필요한 라우팅 및 흐름 제어 기능을 함께 구현한다. 다양한 라우터 구성 방식이 있지만, 이 장에서는 일반적인 virtual-channel router의 아키텍처를 살펴보고 라우터 설계에서 고려되는 주요 이슈와 트레이드오프에 대해 논의한다.

현대 라우터는 flit 단위로 파이프라인화되어 있다. head flit은 라우팅과 virtual channel 할당을 수행하는 파이프라인 단계를 거치고, 모든 flit은 switch 할당 및 switch traversal 단계를 거친다. 특정 파이프라인 단계가 현재 사이클에서 완료되지 않으면 pipeline stall이 발생한다. 이 경우 flit의 순서를 유지해야 하므로 해당 stall 이전의 모든 파이프라인 단계의 동작이 중단된다.

대부분의 라우터는 buffer 공간을 할당하기 위해 credit 방식을 사용한다. flit이 채널을 따라 downstream으로 이동하면서, upstream 방향으로는 방금 비워진 버퍼에 접근할 수 있도록 credit이 전달된다. 버퍼 수가 제한된 라우터에서는 credit 처리 지연이 성능에 큰 영향을 줄 수 있다. 또한 credit은 deadlock 속성에도 영향을 미친다. 모든 credit이 반환되기 전에 virtual channel이 할당되면, 현재 채널을 할당받은 패킷과 downstream 버퍼에 아직 남아있는 다른 패킷 사이에 의존성이 생긴다.

16.1 기본 라우터 아키텍처

16.1.1 블록 다이어그램

그림 16.1은 일반적인 virtual-channel router의 블록 다이어그램을 보여준다. 이 블록들은 기능에 따라 datapath와 control plane의 두 그룹으로 구분할 수 있다. datapath는 패킷의 payload 저장 및 이동을 처리하며, 입력 버퍼 집합, 스위치, 출력 버퍼 집합으로 구성된다.

control plane은 datapath 자원 내에서 패킷의 이동을 조정하는 역할을 하며, 라우터에서는 route computation, virtual-channel allocation, switch allocation을 수행한다. 입력 버퍼에는 입력 제어 상태가 포함되어 input unit을 구성하며, 출력도 마찬가지 방식이다.

각 패킷의 flit은 라우터의 input unit에 도착한다. input unit은 도착한 flit을 저장하기 위한 flit buffer와 해당 입력 링크에 연결된 각 virtual channel의 상태를 유지한다. 일반적으로 각 virtual channel의 상태는 Table 16.1에 제시된 다섯 개의 필드로 구성된다.

패킷 전송을 시작하려면 우선 route computation을 수행해 어떤 출력 포트로 보낼지 결정해야 한다. 출력 포트가 정해지면, virtual-channel allocator에게 출력 virtual channel을 요청한다. 라우팅과 virtual channel 할당이 완료되면, switch allocator가 switch와 출력 채널에 대해 시간 슬롯을 할당해 flit을 해당 출력 unit으로 전송한다. 마지막으로, 출력 unit은 flit을 다음 라우터로 전달한다. 입력 unit과 마찬가지로, 출력 virtual channel 상태도 Table 16.2에 제시된 여러 상태 필드를 포함한다.

라우터의 제어는 packet 단위와 flit 단위라는 두 가지 다른 주기로 동작한다. route computation과 virtual-channel allocation은 packet당 한 번 수행되며, 이에 따라 virtual channel의 R, O, I 필드가 한 번만 갱신된다. 반면 switch allocation은 flit마다 수행되므로, P와 C 필드는 flit 주기로 갱신된다.

Table 16.1: 입력 virtual channel 상태 필드 (5-vector: GROPC)

Table 16.2: 출력 virtual channel 상태 필드 (3-vector: GIC)

16.1.2 라우터 파이프라인

그림 16.2는 일반적인 virtual-channel router의 파이프라인 동작을 Gantt 차트 형식으로 보여준다. 각 head flit은 라우팅 계산(RC), virtual channel 할당(VA), switch 할당(SA), switch 전송(ST)의 단계를 거쳐야 한다. 그림에서는 각 단계가 1 클럭 사이클씩 걸리는 파이프라인을 나타낸다. 도표에서는 stall 없이 패킷이 각 파이프라인 단계를 통과하는 이상적인 상황을 보여준다. 실제로는 어느 단계에서든 stall이 발생할 수 있다.

라우팅 과정은 head flit이 cycle 0에 라우터에 도착하면서 시작된다. 이때 flit의 헤더에는 도착한 입력 포트의 virtual channel 정보가 포함되어 있다. 이 virtual channel의 초기 global 상태(G)는 idle이다. head flit의 도착으로 인해 cycle 1 시작 시 해당 virtual channel은 routing 상태(G = R)로 전이된다.

cycle 1 동안 head flit의 정보를 이용해 라우터 블록은 출력 포트를 선택한다. 이 결과는 virtual channel 상태의 route 필드(R)에 반영되며, virtual channel 상태는 cycle 2 시작 시 output VC 대기 상태(G = V)로 전이된다. 이와 동시에 첫 번째 body flit이 라우터에 도착한다.

cycle 2에서는 head flit이 VA 단계로 진입하고, 첫 번째 body flit은 RC 단계를 통과하며, 두 번째 body flit이 도착한다. VA 단계에서는 R 필드의 값을 이용해 출력 포트를 지정하고, 해당 포트에서 사용할 수 있는 output virtual channel을 할당받는다. VA 결과는 virtual channel 상태의 O 필드에 반영된다.

그림 16.2에서 보는 바와 같이 RC와 VA는 head flit에만 적용되며, SA와 ST는 모든 flit에 대해 적용된다. stall이 없는 경우 각 flit은 앞선 flit보다 한 사이클씩 늦게 파이프라인에 진입하고 각 단계마다 한 사이클씩 진행된다.

virtual-channel allocator가 성공적으로 할당되면, 해당 입력 virtual channel의 상태는 active(G = A)로 전환된다. 동시에 할당된 출력 virtual channel의 상태 벡터도 active(G = A)로 설정되며, 해당 입력 virtual channel을 식별하기 위해 출력 virtual channel의 입력 필드(I)가 업데이트된다. tail flit이 채널을 해제할 때까지, 출력 virtual channel의 credit(C) 필드는 입력 virtual channel의 C 필드와 동일한 값을 유지한다.

deadlock 분석 관점에서 보면, VA 단계에서 입력 virtual channel에서 출력 virtual channel로의 의존성이 생긴다. 하나의 출력 virtual channel이 패킷에 할당되면, 해당 패킷이 전부 다음 노드의 출력 virtual channel buffer로 이동할 때까지 입력 virtual channel은 해제되지 않는다.

cycle 3이 시작되면 패킷 단위의 모든 제어 처리는 완료되고, 그 이후로는 flit 단위의 switch allocation(SA) 처리만 남는다. 이 시점에서 head flit이 시작하지만 다른 flit들과 동일하게 처리된다. 이 단계에서는, 활성 상태(G = A)이고 buffer에 flit이 있으며(P), downstream buffer가 비어 있는(C > 0) 모든 virtual channel이 switch를 통해 출력 unit으로 flit을 전송하기 위한 시간 슬롯을 요청한다. switch 구성에 따라, 이 할당은 switch의 출력 포트뿐 아니라 동일한 입력 unit 내 다른 virtual channel들과 입력 포트에 대해서도 경합할 수 있다. switch 할당 요청이 성공하면, 입력 버퍼의 포인터 필드(P)가 갱신되고, 해당 flit이 차지했던 buffer가 해제되었음을 반영해 credit count가 감소되며, 이전 라우터로 credit이 전송된다.

그림 16.2에서 cycle 3에 switch allocation이 성공하고, cycle 4에 head flit이 switch를 통과(ST)한다. switch가 비어 있는 상황이라면, cycle 5에 다음 라우터로 flit을 전송할 수 있다.

head flit이 virtual channel 할당을 받고 있는 동안 첫 번째 body flit은 RC 단계에 있으며, head flit이 SA 단계에 있을 때 첫 번째 body flit은 VA 단계, 두 번째 body flit은 RC 단계에 있다. 하지만 routing과 virtual-channel allocation은 패킷 단위로 처리되므로, body flit은 해당 단계에서 수행할 작업이 없다. body flit은 해당 단계를 우회할 수 없고 순서를 유지해야 하므로, SA 단계에 도달할 때까지 input buffer에 저장되어야 한다. stall이 없다면, 파이프라인에 동시에 세 개의 body flit이 존재하므로 최소 세 개의 입력 buffer 위치가 필요하다. 이후 credit stall을 방지하기 위해 더 큰 buffer가 필요함을 설명할 것이다.

각 body flit이 SA 단계에 도달하면 head flit과 동일하게 switch 시간 슬롯을 요청한다. 이 처리 과정은 flit 단위로 수행되며, head flit과 동일하게 취급된다. 각 flit에 대해 switch 슬롯이 할당되면 virtual channel의 P와 C 필드가 갱신되고 credit이 생성되어 이전 라우터로 전달된다.

마지막으로 cycle 6에서는 tail flit이 SA 단계에 도달한다. tail flit의 switch 할당도 head 및 body flit과 동일하게 처리된다. cycle 6에서 tail flit의 할당이 성공하면, cycle 7 시작 시 해당 virtual channel은 해제되며 출력 virtual channel 상태와 입력 virtual channel 상태는 idle(G = I)로 전환된다. 단, 입력 버퍼가 비어 있지 않다면 다음 패킷의 head flit이 이미 대기 중일 수 있으며, 이 경우 상태는 바로 routing(G = R)으로 전환된다.

16.2 Stall

앞서 설명에서는 flit과 packet이 파이프라인을 따라 지연 없이 진행된다는 이상적인 상황을 가정했다. 즉, 할당은 항상 성공하고 채널, flit, credit이 필요할 때 항상 사용 가능하다고 가정했다. 이 절에서는 이상적인 동작을 방해하는 6가지 stall 사례를 Table 16.3을 기준으로 설명한다.

처음 세 가지는 packet stall로, 라우터의 packet 처리 단계에서 발생한다. 이들은 virtual channel이 R, V, A 상태로 진입하지 못하게 한다. 반면 virtual channel이 active(A) 상태에 들어간 후에는 packet 처리가 완료되었으며, 이후에는 flit stall만 발생할 수 있다. flit stall은 switch allocation이 실패하여 flit이 진행하지 못하는 경우로, 그 원인은 flit 없음, credit 없음, switch 슬롯 경쟁 실패 등이 있다.

Table 16.3: 라우터 파이프라인 stall의 종류

Stall 종류P/F상태설명

VC Busy	P	¬I	연속된 packet으로 인해 발생. 이전 패킷의 tail flit이 switch allocation을 마치기 전 다음 packet의 head flit이 도착해 buffer에 대기함
Route	P	R	라우팅 실패로 R 상태에서 재시도 필요
VC Allocation	P	V	VA 실패로 V 상태에서 재시도 필요
Credit	F	A	credit 없음. downstream에서 credit이 도착해야 진행 가능
Buffer Empty	F	A	flit 없음. upstream에서 stall 발생 가능성
Switch	F	A	switch 할당 실패. 다음 사이클에 재시도

Figure 16.3: Virtual-channel allocation stall 예시

패킷 A의 head flit은 cycle 1에서 라우팅을 마치고 cycle 2부터 출력 virtual channel을 요청하지만, 모두 사용 중이라 할당 실패. 이 요청은 tail flit이 cycle 4에 switch allocation을 마친 패킷 B가 virtual channel을 해제할 때까지 실패한다. cycle 5에 패킷 A가 virtual channel을 할당받고, cycle 6에 switch allocation, cycle 7에 switch traversal을 수행한다. 이때 A의 body flit도 head flit이 SA 단계를 마치기 전까지 stall된다. 단, 충분한 입력 버퍼(예: 6개 flit)가 있다면 입력 채널의 전달 속도는 느려지지 않는다.

Figure 16.4: Switch allocation stall 예시

head flit과 첫 번째 body flit은 stall 없이 통과하지만, 두 번째 body flit은 cycle 5에 switch 할당 실패. cycle 6에 재시도 성공. 이후 flit도 모두 1 사이클씩 지연됨. credit stall도 동일한 타이밍을 가지지만, switch 슬롯 부족이 아닌 credit 부족으로 인해 요청 자체를 못 하는 상황이다.

Figure 16.5: Buffer empty stall 예시

head flit과 body flit 1은 정상 처리되지만 body flit 2는 cycle 6에 도착. 이 flit은 도착 직후인 cycle 7에 SA 단계를 거치고, RC와 VA는 비워진 pipeline 단계를 그대로 우회한다. 이후 flit들도 마찬가지로 SA 단계로 바로 이동한다.

16.3 Credit을 이용한 루프 닫기

SA 단계에서 flit이 링크의 upstream 측을 떠나면 buffer가 할당된다. 이 buffer는 동일한 flit이 downstream의 SA 단계를 통과한 뒤 reverse 채널을 통해 credit이 반환되어야 재사용할 수 있다. 이 credit이 upstream 측의 입력 unit에 도달해야 buffer를 재사용할 수 있다. 따라서 buffer 하나를 나타내는 token은 하나의 루프를 따라 움직인다고 볼 수 있다: upstream의 SA → flit과 함께 downstream으로 이동 → downstream SA → credit으로 upstream으로 복귀. 이 동안 flit은 upstream 측의 RC, VA, SA 세 단계에서만 buffer를 점유하며, 루프의 나머지 시간은 buffer가 비어 있는 idle 시간이다.

credit 루프 지연 시간 tcrtt_{crt}tcrt​는 flit 시간 단위로 표현되며, credit stall 없이 채널이 최대 대역폭으로 동작하려면 upstream 측에 필요한 최소 flit buffer 수의 하한을 제공한다. 각 flit이 하나의 buffer를 필요로 하므로...

token이 credit 루프를 완전히 한 바퀴 돌아야만 buffer를 재사용할 수 있기 때문에, flit buffer 수가 tcrtt_{crt}tcrt​보다 적으면 첫 번째 credit이 돌아오기 전에 buffer가 모두 소진된다. credit 루프 지연 시간은 flit 시간 단위로 다음과 같이 정의된다.

즉, 충분한 buffer가 있으면 duty factor는 1이 되어 전체 대역폭을 사용할 수 있지만, buffer 수가 부족하면 credit stall로 인해 duty factor가 감소하고, 그에 따라 전송률도 비례하여 감소한다. 이때 남은 물리 채널 대역폭은 다른 virtual channel이 사용할 수 있다.

Figure 16.6: credit stall 예시
6개의 flit으로 구성된 패킷이 4개의 flit buffer만 있는 채널을 통과하는 경우를 보여준다. upstream은 흰색, downstream은 회색으로 표시했다. 링크 한 방향 이동 시간은 2 cycle이며, credit 전송은 CT, credit count 갱신은 CU 파이프라인 단계에서 수행된다.

이 예에서

• tf=4t_f = 4tf​=4 (RC, VA, SA, ST)
• tc=2t_c = 2tc​=2 (CT, CU)
• Tw=2T_w = 2Tw​=2

이를 식 (16.1)에 대입하면 tcrt=11t_{crt} = 11tcrt​=11 사이클이 된다. 실제로 body flit 4는 head flit의 credit을 재사용하여 cycle 12에서 SA 단계에 진입한다. buffer가 4개이므로, 식 (16.2)의 duty factor는 4/114/114/11로 계산된다.

16.4 채널 재할당

credit이 flit buffer의 재사용을 가능하게 하듯, tail flit의 통과는 출력 virtual channel을 재할당할 수 있도록 한다. 하지만 이 재할당은 네트워크의 deadlock 특성에 큰 영향을 줄 수 있다.

패킷 A의 tail flit이 ST 단계에 진입하면, A에 할당된 출력 virtual channel xxx를 다른 패킷 B에 할당할 수 있다. B는 같은 입력 포트, 같은 입력 virtual channel, 다른 포트의 virtual channel 등 어디에서든 올 수 있다.

그러나 이 시점에 xxx를 B에 할당하면 B → A의 의존성이 생긴다. downstream 라우터의 입력 버퍼에서 A가 차지하고 있다면, B는 그 공간이 비워질 때까지 대기해야 한다. 이를 방지하려면, upstream 라우터의 ST 단계가 아니라 downstream 라우터의 ST 단계에서 tail flit이 빠져나가는 시점까지 기다려야 한다. 실제로는 upstream 라우터가 downstream의 ST 상태를 알 수 없으므로, tail flit의 credit이 돌아와 credit count가 최대치가 되는 시점까지 기다린다. 그러나 이 방식은 많은 short packet이 연이어 전송되는 상황에서는 물리 채널의 대역폭 낭비로 이어질 수 있다.

Figure 16.7: 출력 virtual channel 재할당의 세 가지 방식

• (a) 보수적 방식: tail flit의 credit이 돌아올 때까지 기다림. B의 head flit은 cycle 3에 RC를 완료한 뒤 cycle 15까지 VA 단계로 진입하지 못하고 12 cycle 동안 stall됨. 이 경우 지연은 tcrt+1t_{crt} + 1tcrt​+1.
• (b) 공격적 방식: tail flit이 SA 단계를 마치자마자 VA 수행. B는 cycle 5에 VA 완료, 단 한 번만 stall됨. 단, downstream 라우터의 RC는 tail flit이 해당 라우터의 ST 단계를 끝낸 cycle 11까지 지연됨. 논리 단순.
• (c) 더욱 공격적 방식: tail flit이 아직 ST를 끝내기 전에도 B가 RC를 수행함. 이때 virtual channel은 동시에 두 패킷의 상태를 관리해야 하므로 제어 논리가 복잡해짐. 예를 들어 B는 RC를 완료했지만, A가 SA 할당에 실패하면 R 필드는 B의 것이고 O, P, C 필드는 A의 것이 되어 몇 cycle 동안 혼재된다. 이 경우 VA 단계에서 busy stall 발생 가능.

16.5 추측과 Lookahead

interconnection network의 지연(latency)은 파이프라인의 깊이와 직접적으로 연관되므로, 각 단계의 지연을 늘리지 않는 범위 내에서 파이프라인 단계를 줄이는 것이 이득이다. 이를 위해 다음 두 가지 방법을 사용할 수 있다:

1. Speculation (추측 실행): 원래 순차적으로 수행되던 작업을 병렬로 수행
2. Lookahead (선제 계산): 미리 계산을 수행하여 critical path에서 제거

예를 들어, virtual channel 할당이 성공할 것이라고 가정하고, VA와 SA를 동시에 수행하면 head flit은 세 단계만 거치게 되고, body flit은 RC에서 1 cycle 동안만 idle 상태가 된다.

RC 단계에서 가능한 virtual channel 집합을 얻은 뒤, 이 중 하나에 대한 VA와 해당 물리 채널의 switch 슬롯에 대한 SA를 동시에 요청할 수 있다. virtual channel 할당이 실패하면 다음 사이클에 VA와 SA를 다시 시도하며, switch 할당이 실패하면 다음 사이클에는 SA만 다시 시도하면 된다. 이 경우 이미 output virtual channel은 할당된 상태이므로 더 이상 추측이 아니다.

주: RC 결과가 여러 물리 채널에 걸쳐 있는 경우, 어떤 채널을 선택할지에 대해서도 추측할 수 있다.

Figure 16.8은 virtual-channel allocation(VA)과 switch allocation(SA)을 동시에 수행하는 speculative router pipeline을 보여준다. 이 경우 head flit에 대한 switch allocation은 추측(speculative)이며, VA가 성공할 때만 유효하다. VA가 실패하면 SA가 성공하더라도 무시된다.

성능에 부정적인 영향을 주지 않기 위해, switch allocation에서는 추측 요청보다 비추측(non-speculative) 요청에 우선권을 주는 보수적 추측 방식을 사용할 수 있다. 이렇게 하면 비추측 요청에 사용될 수 있는 switch 사이클이 잘못된 추측 요청에 낭비되는 일이 없다.

실제로는, 추측 실행은 파이프라인 지연이 중요한 상황에서 매우 잘 작동한다. 파이프라인 지연은 라우터가 적게 로드되었을 때 중요하며, 이 경우 대부분의 virtual channel이 비어 있어 추측이 거의 항상 성공한다. 반면 라우터가 무겁게 로드되면 대기열 지연(queueing latency)이 지배적이므로, 추측의 성공 여부가 전체 성능에 큰 영향을 미치지 않는다.

한 단계 더 나아가 switch traversal(ST)도 VA 및 SA와 병렬로 추측 수행할 수 있다. Figure 16.9는 VA, SA, ST를 모두 병렬로 수행하는 doubly speculative pipeline을 보여준다. 이 경우 flit은 switch allocation 결과를 기다리지 않고 출력으로 먼저 전송된다. 이를 위해 switch는 충분한 속도향상(speedup), 또는 최소한 입력 속도향상(input speedup)을 가져야 한다. flit이 switch를 통과하는 동안 switch allocation은 병렬로 수행되며, 결과적으로 선택된 flit이 출력된다.

이중 추측이 클럭 사이클 시간을 늘리지 않고 가능한지는 switch와 allocator의 구현 세부 사항에 따라 다르다. 많은 라우터에서는 virtual-channel allocator가 크리티컬 패스이고, switch allocation과 출력 선택은 직렬로 처리해도 클럭 시간을 증가시키지 않는다.

파이프라인 단계를 2사이클까지 줄였지만, 1사이클로 줄이는 것도 가능할까? routing computation도 VA, SA, ST와 병렬로 추측해 수행하는 세 번째 추측을 생각해볼 수 있다. 그러나 이는 비효율적이다. flit이 어디로 갈지를 모르고 채널이나 switch 슬롯을 할당하거나 전송을 시도하는 것은 불가능하기 때문이다.

대신, routing 결과를 lookahead 방식으로 미리 계산할 수 있다. hop i에서 라우터를 통과할 때, 현재 라우터에 대한 라우팅이 아니라, 다음 hop (i+1)의 라우터에 대한 라우팅을 미리 계산하고 그 결과를 head flit에 함께 전달하는 방식이다. 그러면 각 라우터에 도착할 때 이미 출력 경로가 정해져 있어 VA와 SA가 즉시 시작될 수 있다. 다음 hop 라우팅 계산(NRC)은 파이프라인 어느 단계와도 병행 수행 가능하다.

Figure 16.10은 이러한 1-hop route lookahead 방식을 두 가지 파이프라인에 적용한 예다.

• 왼쪽: 기존 4단계 파이프라인에서 NRC를 VA에 병합해 3단계로 줄임
• 오른쪽: Figure 16.9의 이중 추측 파이프라인에 적용하여 단일 단계로 축소

latency가 중요한 응용에서는 이보다 더 줄이기 어렵다.

16.6 Flit 및 Credit 인코딩

지금까지 flit과 credit이 라우터 사이를 오간다고 했지만, 실제로 어떻게 구분하고, 어디서 시작하는지, 어떤 방식으로 인코딩되는지는 설명하지 않았다. 이 절에서는 그 구체적인 방식을 간략히 설명한다.

Flit과 Credit의 분리

가장 단순한 방법은 flit과 credit을 별도의 채널로 전송하는 것이다 (Figure 16.11(a)). 일반적으로 flit 채널은 더 많은 정보를 담아야 하므로 credit 채널보다 훨씬 넓다. 그러나 이 방식은 비효율적이다. credit 채널에 대역폭이 남는 일이 많고, 채널이 좁으면 credit을 serialize하여 latency가 증가한다.

더 일반적이고 효율적인 방식은 flit과 credit을 하나의 물리 채널로 통합하는 것이다 (Figure 16.11(b)). 이 경우 각 flit에 credit을 포함시키는 방식(piggybacking)을 사용할 수 있다. 이는 credit이 flit에 '태워져' 같이 전송되는 형태다. 두 객체의 크기는 다르지만, 평균적으로는 flit 하나당 credit 하나가 필요하므로 이 방식은 적절하다.

다른 방법으로는 flit과 credit을 phit 단위로 멀티플렉싱하는 것도 있다. 이 방법은 flit과 credit 비율이 일시적으로 달라질 때, 전체 대역폭을 flit 또는 credit에 집중할 수 있는 장점이 있다. 단, credit이 phit 단위에 딱 맞지 않으면 단편화(fragmentation) 손실이 발생할 수 있다.

Phit-level 멀티플렉싱과 인코딩

phit 단위 멀티플렉싱을 위해서는 각 phit이 무엇의 시작인지(flit/credit/idle), 어디서 시작되는지 알아야 한다. 이 정보는 phit-level 프로토콜로 인코딩된다. Figure 16.12(a)에서 각 phit은 타입 필드(type field)와 payload 필드를 가진다. 타입 필드는 다음과 같이 정의될 수 있다:

• 10: credit 시작
• 11: flit 시작
• 0X: idle

credit과 flit의 길이는 고정되어 있으므로, 중간에 있는 phit은 별도 표시 없이 길이로 추론 가능하다. 중간 phit의 type 필드는 추가 payload 정보에 사용할 수 있다. 만약 credit을 flit에 piggyback한다면 credit 시작 인코딩은 필요 없고, type 필드는 1비트로 줄일 수 있다.

Flit과 Credit의 내용

Figure 16.13에서 각 flit은 다음 필드를 포함한다:

• VC 식별자: 해당 flit이 속한 virtual channel
• Type: head flit인지 아닌지, tail 여부도 포함 가능
• Payload: 실제 데이터
• Check: 오류 검사용 필드
• Route 정보: head flit에만 존재, routing 함수가 출력 virtual channel 선택 시 사용
• Credit 필드: piggyback 방식인 경우 head 및 non-head flit 모두에 포함

Credit은 다음 필드를 포함한다:

• VC 식별자: credit을 받을 virtual channel
• Check: 오류 검사용
• Type (선택): on/off flow control 등의 back-channel 정보 포함 가능

16.7 사례 분석: Alpha 21364 라우터

Alpha 21364는 Alpha 마이크로프로세서 아키텍처 계열의 최신 버전이다. 이 1.2GHz, 1억 5200만 개의 트랜지스터로 이루어진 칩은 Alpha 21264 프로세서 코어에 cache coherence 하드웨어, 두 개의 메모리 컨트롤러, 그리고 네트워크 라우터를 단일 다이에 통합했다. 이를 통해 Alpha 21364는 대규모 공유 메모리 시스템의 단일 칩 구성 블록으로 활용될 수 있다.

이 라우터는 4개의 외부 포트를 가지며 총 22.4GB/s의 네트워크 대역폭을 제공하고, 최대 128개의 프로세서를 2D torus 네트워크로 연결할 수 있다. 21364 라우터의 아키텍처는 본 장에서 소개한 기본 virtual-channel 라우터 구조와 매우 유사하다. 높은 1.2GHz 작동 주파수를 만족시키기 위해 라우터 내부에서 패킷은 깊은 파이프라인을 거치며, 이로 인한 지연을 회복하기 위해 speculation도 사용된다.

Figure 16.14는 21364 라우터 아키텍처의 단순화된 구조를 보여준다. 실제 구현은 8개의 입력 포트와 7개의 출력 포트를 가지지만, 그림에서는 단순화를 위해 3×3 라우터만 표시되어 있다. crossbar는 각 출력 포트에 대한 mux로 구현되어 있으며, switch allocator는 local arbiter와 global arbiter 두 부분으로 나뉘어 있다.

이 설계는 wormhole flow control이 아닌 cut-through flow control을 사용한다. 이로 인해 각 입력 unit은 전체 패킷을 저장할 수 있어야 하지만, coherence 프로토콜에서 최대 패킷 크기가 76바이트에 불과하기 때문에 실용적인 접근이다. 각 입력 unit은 여러 개의 최대 크기 패킷을 저장할 수 있는 버퍼를 포함하고 있으며, 전체 라우터는 316개의 패킷 버퍼를 가진다. 이 정도의 버퍼 수는 deadlock 회피와 adaptive routing을 위한 여러 개의 virtual channel 운용에 충분하다.

Figure 16.15는 라우터의 파이프라인 단계를 보여준다. cut-through 방식이므로 phit 기준으로 파이프라인이 정의된다. 첫 번째 phit은 RC 단계에서 라우팅되고, 이후 wire 지연(T) 단계를 거친다. header decode 및 입력 unit 상태 갱신(DW)을 수행한 후, payload는 input queue에 저장(WrQ)된다. 이 과정과 병행하여 첫 번째 phit이 입력 버퍼에 저장되는 동안 switch allocation이 시작된다.

cut-through flow control을 사용하므로 일반 virtual-channel 라우터에서 분리되었던 virtual-channel allocation과 switch allocation 단계를 하나의 단일 allocation(SA) 단계로 병합할 수 있다. 일반적으로 virtual channel은 출력 포트당 여러 개가 활성화될 수 있지만, cut-through 라우터는 각 출력 포트당 하나의 virtual channel만 활성화되도록 단순화할 수 있다. 이로 인해 virtual channel이 할당되면, 그 자체가 switch allocation도 유효함을 보장한다.

이 구조는 wormhole flow control에서는 virtual channel이 막힐 수 있어 부적합하지만, cut-through 방식에서는 downstream 라우터가 전체 패킷을 수용할 수 있는 충분한 buffer를 가지므로 blocking 없이 전달이 가능하다.

정밀한 타이밍 요구사항을 만족시키기 위해, switch allocation은 local arbiter와 global arbiter로 나뉘며 2단계로 구성된다.

• SA1 단계: 각 입력 unit에서 local arbiter가 준비된 패킷 중 하나를 선택. 출력 포트가 사용 가능하고 downstream에 빈 패킷 버퍼가 있을 때 준비 상태로 간주된다.
• RE 단계: 선택된 패킷의 header 정보가 읽혀서 해당 출력으로 전송된다.
• SA2 단계: 여러 패킷이 하나의 출력 포트를 요청할 수 있으므로, global arbiter가 최종적으로 출력당 하나의 패킷을 선택해 할당한다.
• ST1 단계: local arbiter에 의해 선택된 모든 패킷의 데이터는 speculative하게 출력으로 전송된다. 나중에 global arbiter 결과에 따라 승자만 유효하게 처리된다.
• ST2 단계: 실제 전송이 완료됨
• ECC 단계: 7비트의 오류 정정 코드가 phit에 추가되어 downstream 라우터로 전송됨

스펙 실행 결과는 backchannel을 통해 입력 unit으로 피드백되며, 성공하면 이후 phit은 계속 전송되고 실패 시 switch 내에서 폐기되며 재전송된다. 이와 같은 deep pipeline 설계와 speculative transfer 덕분에 Alpha 21364 라우터는 10.8ns의 매우 낮은 per-hop latency와 70~90%의 피크 처리량을 달성할 수 있다.

16.8 참고 문헌 비고

이 장에서 설명한 기본 virtual-channel router 구조는 Torus Routing Chip에서 유래되었다. 이후 Reliable Router, Cray T3D/T3E, IBM SP 시리즈, SGI SPIDER chip 등에서 개선되었으며, 특히 SPIDER는 한 단계 앞서 라우팅을 수행한 최초의 라우터였다. 라우터 latency를 줄이기 위한 speculation 기법은 Peh와 Dally가 처음 제안하였다.

16.9 연습문제

16.1 단일 virtual channel 사용 시의 단순화
물리 채널당 하나의 virtual channel만 있을 경우, 파이프라인과 global state는 어떻게 변하는가? 각 파이프라인 단계와 global state의 각 필드를 설명하라.

16.2 circuit switching 라우터의 아키텍처
Figure 12.6과 같은 circuit switching 라우터를 설계하라. global state는 무엇인가? 파이프라인은 어떻게 구성되는가? 각 circuit과 flit을 처리하는 단계는 무엇인가?

16.3 ack/nack 흐름 제어가 파이프라인에 미치는 영향
credit 기반 흐름 제어 대신 ack/nack 흐름 제어를 사용할 경우, 라우터 파이프라인은 어떻게 변하는가? credit stall은 어떻게 처리되는가?

16.4 공격적인 virtual-channel 재할당으로 인한 의존성
Duato의 프로토콜을 기반으로 한 2D mesh 네트워크의 최소 adaptive routing 알고리즘을 고려하자. VC 0은 dimension-order routing에, VC 1은 adaptive routing에 사용된다. Figure 16.7에 나온 재할당 전략 중 어떤 것이 이 알고리즘에서 deadlock-free한가?

16.5 좁은 채널에서의 flit 포맷 구성
Figure 16.13의 필드 요구사항이 다음과 같다고 하자: VC 필드 4비트, type 정보 2비트, credit 필드 8비트, route 정보 6비트. 입력 채널이 클럭 사이클당 8비트를 수신할 경우, 라우팅을 시작하기까지 몇 사이클이 필요한가? 필요한 경우 해당 flit 포맷을 제시하라. route lookahead를 사용할 경우, virtual-channel allocation은 첫 사이클에 시작할 수 있는가?