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 벡터를 생성한다.
- gij가 1이면 반드시 rij도 1이어야 한다. 즉, 요청이 있어야만 grant가 주어진다.
- gij가 1이면 같은 입력 i에 대해서는 다른 어떤 k ≠ j에 대해서도 gik는 0이어야 한다. 즉, 각 입력에 대해 최대 하나의 grant만 허용된다.
- 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₃₂가 생성된다. 이때 각 행렬은 다음과 같다:
다음 예시는 Lonely Output Allocator가 작동하는 방식을 보여준다. 요청 행렬 R과 이에 대응하는 카운트 행렬 C, 중간 요청 행렬 X, 최종 grant 행렬 G는 다음과 같다:
출력 포트 1은 총 4개의 요청을 받았으므로, 이 열의 모든 요청은 4로 표시되었다. 반면 출력 0과 2는 각각 2개의 요청만 받았다. 이 카운트 정보를 바탕으로, 입력 arbiter는 더 적은 요청을 받은 출력으로 향하는 요청에 우선순위를 준다. 그 결과, X는 더 많은 열에 걸쳐 요청을 포함하게 되어 출력 arbiter 단계에서 충돌이 줄어든다. 예를 들어, 입력 3의 arbiter는 x₃₂를 선택함으로써 출력 2의 유일한 요청을 선택하게 된다.
19.4 Wavefront Allocator
Wavefront Allocator는 위에서 설명한 separable allocator들과 달리, 입력과 출력에 대한 arbitration을 동시에 수행한다. 그림 19.8은 wavefront allocator의 구조를, 그림 19.9는 각 allocator cell의 논리 회로를 보여준다.
Wavefront Allocator는 대각선 방향의 cell 그룹에 row token과 column token을 부여하는 방식으로 동작하며, 해당 그룹에 우선순위를 부여한다. 어떤 cell이 token을 가지고 있지만 요청이 없거나 grant를 할 수 없는 경우, 그 token은 오른쪽 또는 아래쪽으로 전달된다. 이 token들은 우선 그룹에서 시작하여 wave처럼 퍼져나가며, 이 때문에 wavefront allocator라는 이름이 붙었다. 어떤 cell이 요청을 받고 동시에 row token과 column token을 받으면, 요청을 승인하고 token 전달을 멈춘다. 이 우선 대각선 그룹은 매 cycle마다 회전하며, 이를 통해 약한 수준의 공정성이 확보된다.
n×n arbiter에서 대각선 그룹 k는 (i+j) mod n = k 를 만족하는 cell xᵢⱼ로 구성된다. 예를 들어, 그림 19.8의 3×3 allocator에서 p₀는 x₀₀, x₂₁, x₁₂ cell을 포함한다. 각 대각선 그룹은 각 행과 열마다 하나씩의 cell만을 포함해야 하므로 wavefront allocator는 반드시 정사각형이어야 한다. 비정사각형 구조는 dummy 행이나 열을 추가하여 정사각형으로 만들어 해결할 수 있다. 예를 들어, 4×3 allocator는 4×4로 확장하여 구현할 수 있다.
각 allocator cell의 동작은 다음과 같다 (그림 19.9):
- pri가 활성화된 cell은 우선 그룹에 포함되며 xpri (row token)와 ypri (column token)를 생성한다.
- 그 외의 cell은 이웃으로부터 xin (왼쪽에서 받은 row token), yin (위에서 받은 column token)을 입력받는다.
- 요청 reqᵢⱼ이 있고 xpri, ypri가 모두 존재하면 grantᵢⱼ가 생성된다.
- grant가 생성되면 이후 token 전달을 멈춘다.
- grant가 생성되지 않으면 token은 xout (오른쪽), yout (아래쪽) 방향으로 계속 전달된다.
이 구조는 18.5절의 iterative arbiter cell의 2D 확장판이다. 이 경우, 요청이 아니라 grant가 token의 전달을 막는다. 이 방식은 두 token 중 하나만 받은 경우에 token 전달이 불필요하게 차단되는 상황을 방지한다. 전체 회로는 겉보기엔 combinational cycle을 포함하는 것처럼 보이지만, 항상 pri 입력 중 하나는 활성화되어 있으므로 실질적으로는 OR 게이트에 의해 cycle이 끊어진다. 그러나 이러한 구조는 최신 CAD 툴의 timing analysis에 문제를 일으킬 수 있다.
그림 19.10은 wavefront allocator가 4×3 요청 행렬에 대해 동작하는 모습을 보여준다. 여기서는 4×4 wavefront 구조를 사용하여 column 3은 요청이 없지만 dummy로 포함되어 있다.
이 예시에서:
- p₃가 활성화되어, x₃₀, x₂₁, x₁₂, x₀₃가 token을 받는다.
- x₂₁은 요청이 있으므로 grant를 생성한다.
- 나머지 셀은 token을 오른쪽 또는 아래로 전달한다.
- 예: x₃₀ → x₃₁ → x₃₂로 row token 전달, x₃₂는 row token과 column token을 받아서 grant 수행
- x₀₀도 x₃₀으로부터 column token, x₀₃으로부터 row token을 받아 grant를 생성
- row 1과 column 3의 token은 사용되지 않아 전체를 순환하게 된다.
19.5 Incremental vs. Batch Allocation
많은 라우터에서는 할당이 매 i 사이클마다 한 번씩만 필요하다. 예를 들어, 각 flit이 내부 데이터 경로보다 4배 넓어 switch를 통과하는 데 4 사이클이 걸리는 경우, 할당은 i = 4마다 한 번만 수행하면 된다. 이때, 하나의 batch에서 i = 4번의 PIM 또는 iSLIP 반복을 수행하여 더 많은 수의 매칭을 생성할 수 있다.
또는 이처럼 batch 방식으로 수행하는 대신, 할당을 점진적으로 수행하는 incremental 방식도 가능하다. 이 경우, 매 사이클마다 가장 좋은 할당을 수행하는 간단한 one-cycle allocator를 사용한다. grant를 받은 flit은 즉시 switch를 통과하기 시작하며, 이와 관련된 행과 열은 그 이후부터는 고려 대상에서 제외된다. 이는 iterative allocator와 유사하지만, iterative 방식에서는 모든 할당이 끝날 때까지 flit이 전송을 시작하지 않는 반면, incremental 방식에서는 grant 직후 바로 전송을 시작한다. 그 결과, flit들은 서로 다른 사이클에 전송을 시작하고, 종료도 서로 다른 사이클에 이루어진다.
그림 19.11은 요청 행렬 R (식 19.1)에 대한 incremental 및 batch allocation의 동작을 보여준다. 이 예에서 g₂₁과 g₄₄는 사이클 1에서 grant되며, g₁₃은 사이클 2, g₀₀과 g₃₅는 사이클 3에서 grant된다.
- Incremental allocation (그림 19.11[a]): 각 flit은 grant를 받은 다음 cycle에 바로 switch를 통과하기 시작한다.
- Batch allocation (그림 19.11[b]): allocator가 4번 반복된 후인 사이클 5까지 flit 전송이 지연된다.
Incremental allocation은 지연(latency)을 줄이고, flit으로 나뉘지 않은 가변 길이 패킷도 처리할 수 있게 해 준다. 하지만 대역폭 감소와 공정성 저하라는 단점이 있다.
- 지연 감소: grant 즉시 flit 전송이 시작되므로, batch 시간 전체를 기다릴 필요가 없다. 가볍게 부하된 네트워크에서는 대부분 flit이 한 번의 allocation cycle 후에 전송된다.
- 대역폭 감소: flit의 전송 시작 시간이 서로 달라지면 batch allocator에서는 채워졌을 idle cycle이 생겨 손실이 발생할 수 있다.
Incremental 방식은 flit이 아닌 패킷 단위 전송을 처리할 수 있다는 점에서 유리하다. 패킷이 switch 자원을 점유하는 동안에는 입력과 출력 자원이 모두 묶여 있어야 하며, batch 방식에서는 각 패킷 길이를 다음 batch size로 올림 처리해야 한다. 반면, flit 분할 없이 패킷을 바로 전송하면 segmentation overhead는 줄어들지만, 긴 패킷으로 인한 경쟁 지연은 늘어난다.
妥협안으로는 일정 길이(X) 이상인 패킷만 segmentation하고, 이보다 짧은 패킷은 분할 없이 전송하는 방식이 있다. 예를 들어, 2 flit 이상의 패킷만 분할하면 segmentation overhead는 최대 X/(X+1) (예: 2/3)으로 제한되며, 경쟁 지연도 2 flit 시간 이내로 제한된다.
공정성(fairness) 확보에는 별도 조치가 필요하다. 예를 들어, 그림 19.11에서 r₂₁과 r₀₀이 계속 asserted 되고, r₂₀은 단발성 요청이라면 r₂₀은 input 2와 output 0을 동시에 확보해야 서비스가 가능하다. 하지만 input 2가 비었을 때 output 0은 여전히 g₀₀ 처리 중이어서 r₂₀은 서비스되지 못하고, greedy scheduler는 계속 r₂₁에 input 2를, r₀₀에 output 0을 할당하게 된다.
해결 방법: 일정 시간 이상 대기한 요청은 입력과 출력을 개별적으로 확보할 수 있도록 우선순위를 높인다. 예를 들어 r₂₀이 16 사이클 이상 대기한 경우, input 2를 먼저 확보한 후 output 0을 확보할 때까지 기다린다.
19.6 Multistage Allocation
일부 응용에서는 다단계(allocation stages)가 필요하다. 예를 들어:
- 우선순위가 높은 패킷을 먼저 할당하고, 남은 자원을 우선순위 낮은 패킷에 할당
- multicast 트래픽을 먼저 처리하고, 그 이후에 unicast 요청 처리
그림 19.12는 이 과정을 보여준다.
- 첫 번째 요청 행렬 Ra에 대해 첫 번째 allocation 수행 → grant 행렬 Ga 생성
- Ga를 바탕으로 마스크 행렬 Ma 생성 → Ga에서 grant된 행(row)과 열(column)은 차단
- 두 번째 요청 행렬 Rb에 대해 Ma를 AND 연산하여 충돌 제거 → Rb' 생성
- Rb'에 대해 두 번째 allocation 수행 → Gb 생성
이 방식은 추가 단계에서도 적용 가능하며, 각 단계의 요청은 앞 단계에서 마스킹된 결과로 제한된다.
예시 (식 19.3):
19.7 Performance of Allocators
allocator의 성능은 crossbar switch에서 flit 전송을 스케줄할 때 측정할 수 있다. 정확한 평가를 위해 다음 이상적 조건을 가정한다:
- 각 입력은 무한 크기 버퍼를 가진다
- 각 입력은 Virtual Output Queue로 나뉘며, 출력 포트마다 하나의 virtual channel이 존재
- flit이 도착하면 즉시 해당 출력에 해당하는 virtual output queue에 저장
- routing 및 switch traversal latency는 무시
- flit의 지연은 입력 버퍼에서 보낸 시간만 고려
기준 환경: 8×8 스위치, uniform 트래픽
그림 19.13:
- PIM: 약 66% offered traffic에서 포화
- LOA: 약 69%에서 포화, 하지만 포화 이전까지는 좋은 평균 지연 제공
- wavefront, iSLIP: 100% throughput에 접근하지만 지연은 다름
→ wavefront가 iSLIP보다 훨씬 낮은 지연 제공
반복 횟수 증가 효과:
그림 19.14에서 PIM의 반복 횟수 증가에 따른 성능 변화:
- PIM1: 66%에서 포화
- PIM2: 약 90%까지 향상
- PIM3: 거의 100% 도달
- PIM3 이상에서는 성능 향상 크지 않음
iSLIP도 반복 횟수 증가 시 성능 향상이 있으며, 100% throughput에 도달함.
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의 성능을 비교하라.
'System-on-Chip Design > NoC' 카테고리의 다른 글
| Error Control (0) | 2025.06.16 |
|---|---|
| Network Interfaces (0) | 2025.06.16 |
| Arbitration (1) | 2025.06.16 |
| Router Datapath Components (0) | 2025.06.16 |
| Router Architecture (2) | 2025.06.05 |
