이 장에서는 라우터의 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 간에 유연하게 할당할 수 있다는 점이다. 하지만 두 가지 단점이 있다:
- 중앙 메모리의 대역폭이 병목이 될 수 있다. 예를 들어 input port가 8개라면, 메모리는 한 클럭에 8개를 쓰고 8개를 읽어야 하므로 16배의 대역폭이 필요하다.
- 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는 다음과 같이 작동한다:
- 각 input buffer는 기다리는 flit 중 하나를 무작위로 선택해 crossbar의 각 입력에 할당한다.
- uniform traffic이라고 가정할 때, 각 출력은 선택된 입력 flit이 해당 출력으로 향할 확률이 동일하다.
- 각 출력은 자신을 요청하는 입력들 중에서 하나의 flit을 무작위로 선택해 수신한다.
예를 들어 입력과 출력이 k개씩 있는 라우터에서 입력 측 speedup이 s이고 출력 측 speedup은 없다면, crossbar는 총 sk개의 입력을 가진다. 이 경우, 할당의 첫 단계에서 선택된 sk개의 flit 중 하나라도 특정 출력으로 향할 확률이 switch의 throughput 𝜌가 된다. 이는 다음과 같은 수식으로 주어진다:
𝜌=1−(k−1k)sk𝜌 = 1 - \left( \frac{k - 1}{k} \right)^{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)
그림 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)를 사용하라.
'System-on-Chip Design > NoC' 카테고리의 다른 글
| Allocation (1) | 2025.06.16 |
|---|---|
| Arbitration (1) | 2025.06.16 |
| Router Architecture (2) | 2025.06.05 |
| Quality of Service (1) | 2025.06.05 |
| Deadlock and Livelock (2) | 2025.06.05 |
