Zeah Engineering Factory

Flow control은 네트워크 자원, 즉 channel bandwidth, buffer capacity, control state를 네트워크를 통해 전달되는 패킷에 어떻게 할당할지를 결정한다. 효과적인 flow-control 방식은 이 자원들을 효율적으로 할당하여 네트워크가 이상적인 bandwidth의 높은 비율을 달성하고, 낮고 예측 가능한 latency로 패킷을 전달할 수 있도록 한다. 반면, 비효율적인 flow-control 방식은 일부 자원을 유휴 상태로 방치하거나 다른 자원으로 비생산적인 작업을 하여 bandwidth를 낭비한다. 이런 경우, 제2장에서 다룬 것처럼, 네트워크는 이상적인 bandwidth의 극히 일부분만을 활용하며, latency도 높고 변동성이 크다.

Flow control은 자원 할당 문제 또는 경쟁 해결 문제로 볼 수 있다. 자원 할당 관점에서 보면, 패킷이 source에서 destination으로 진행하면서 channel, buffer, state 등의 자원이 할당되어야 한다. 같은 과정을 경쟁 해결 관점에서 보면, 예를 들어 두 개의 패킷이 같은 시간에 라우터의 서로 다른 입력에서 도착하여 동일한 출력을 요구할 때, flow-control 메커니즘은 경쟁을 해결하고 해당 channel을 하나의 패킷에 할당하며, 나머지 차단된 패킷은 다른 방식으로 처리한다.

가장 단순한 flow-control 메커니즘은 bufferless이며, 차단된 패킷을 임시 저장하는 대신 드롭(drop)하거나 잘못된 경로로 전송(misroute)한다. 그보다 조금 더 복잡하고 효율적인 방식은 circuit switching으로, 여기서는 패킷 헤더만 buffering한다. circuit switching에서는 패킷의 헤더가 payload보다 먼저 네트워크를 통과하며, 경로 상의 자원을 예약한다. 특정 노드에서 자원이 즉시 할당되지 않으면, 헤더는 해당 자원이 사용 가능해질 때까지 대기한다. 전체 경로(회로)가 예약되면 데이터를 전송할 수 있고, 사용 후에는 채널을 해제하여 회로를 종료한다. 이들 flow-control 메커니즘은 상대적으로 저렴한 저장 공간 사용을 피하려다 비싼 channel bandwidth를 낭비하기 때문에 효율성이 떨어진다.

더 효율적인 flow control은 네트워크 자원이 사용 가능해질 때까지 데이터를 buffering하여 달성할 수 있다. buffering은 인접한 채널 간의 자원 할당을 시간적으로 분리(decouple)시켜 제약을 줄이고 효율성을 높인다. buffering은 store-and-forward나 cut-through flow control처럼 packet 단위로 이루어질 수도 있고, wormhole 또는 virtual-channel flow control처럼 더 미세한 단위인 flit 단위로 이루어질 수도 있다. 큰 크기의 가변 길이 패킷을 고정 크기의 작은 flit으로 나누면, 각 노드에서 필요한 저장 공간을 크게 줄일 수 있다. 또한 flit 단위로 자원을 할당하면, 하나의 physical channel 위에 여러 개의 virtual channel을 구현하기가 쉬워져 blocking을 줄이고 throughput을 향상시킬 수 있다.

이번 장에서는 flow-control 문제(섹션 12.1), bufferless flow control(섹션 12.2), circuit switching(섹션 12.3)을 순서대로 다룬다. 이어지는 13장에서는 buffered flow-control 방식들을 설명한다. 이 두 장에서는 네트워크 내 자원의 할당에만 초점을 맞춘다. 14장에서 보듯이, deadlock-free 네트워크를 유지하기 위한 추가적인 제약 조건이 있으며, 또한 endpoint에서의 buffer memory 관리와 같은 자원 관리 문제, 즉 end-to-end flow control도 존재한다. 이들은 유사한 원리를 따르지만 본 장에서는 다루지 않는다.

12.1 자원과 할당 단위

인터커넥션 네트워크를 통과하기 위해서는 message가 channel bandwidth, buffer capacity, control state와 같은 자원을 할당받아야 한다. 그림 12.1은 하나의 네트워크 노드 내에서 이러한 자원들을 보여준다. 패킷이 노드에 도착하면 우선 control state가 할당되어야 한다. flow control 방식에 따라, channel당 하나의 control state만 존재할 수도 있고, 입력이 여러 패킷에 공유될 수 있다면 여러 개의 state가 존재할 수도 있다. control state는 패킷이 해당 노드 내에서 할당받은 자원과 노드 내 이동 상태를 추적한다. 다음 노드로 이동하기 위해서는 해당 노드의 출력 채널(output channel)에서 bandwidth를 할당받아야 한다. 일부 네트워크에서는 forward channel과 함께 반대 방향으로 흐르는 reverse channel의 bandwidth도 함께 할당된다. reverse channel은 일반적으로 acknowledgment나 flow-control 정보를 전달하는 데 사용된다. 또한 패킷이 노드에 도착하면 channel bandwidth가 사용 가능해질 때까지 buffer에 임시로 저장된다. 모든 flow-control 방식은 control state와 channel bandwidth의 할당을 포함하며, 일부 방식에서는 buffer 할당은 포함하지 않는다(12.2절에서 다룸).

그림 12.1
네트워크 노드 내 자원 할당

• Control state: 패킷의 channel/buffer 할당과 노드 내 진행 상태를 기록
• Channel bandwidth: flit을 다음 노드로 전송
• Buffers: channel bandwidth를 기다리는 동안 flit을 보관

자원 할당의 효율성을 높이기 위해, message를 control state 할당 단위인 packet으로 나누고, channel bandwidth 및 buffer capacity 할당 단위인 flit으로 다시 나눈다.

그림 12.2는 네트워크 자원이 할당되는 단위를 보여준다. 가장 상위의 message는 source terminal에서 destination terminal로 전달되는 논리적으로 연속된 비트 그룹이다. message는 길이가 임의적이므로 직접 자원이 할당되지는 않으며, 대신 길이가 제한된 하나 이상의 packet으로 나뉜다. packet의 길이를 제한하면 자원 할당의 크기와 지속 시간도 제한되며, 이는 flow control 메커니즘의 성능과 기능성 측면에서 중요하다.

packet은 routing 및 순서 지정의 기본 단위이다. packet 단위로 control state가 할당된다. 그림 12.2에서 보이듯이 packet은 message의 일부에 packet header가 앞에 붙어 구성된다. packet header는 routing information(RI)과 필요 시 sequence number(SN)를 포함한다. RI는 source에서 destination까지 패킷의 경로를 결정하는 데 사용되며, 이는 목적지 필드나 source route 등 다양한 형태일 수 있다(8장에서 설명됨). 패킷이 순서를 잃을 수 있는 경우에는 SN이 필요하다. 예를 들어, 서로 다른 경로를 통해 전달되는 경우가 이에 해당한다. 순서가 보장된다면 SN은 필요하지 않다.

packet은 다시 flow control digit 또는 flit으로 나뉜다. flit은 대부분의 flow control 방식에서 bandwidth 및 storage 할당의 기본 단위이다. flit은 routing 및 sequencing 정보를 포함하지 않으며, 따라서 같은 경로를 따라 순서를 유지해야 한다. 하지만 여러 개의 패킷이 하나의 physical channel을 통해 동시에 전송될 수 있는 시스템에서는 flit이 virtual-channel identifier(VCID)를 포함할 수 있다. 이는 flit이 어떤 packet에 속하는지를 나타낸다.

flit의 위치에 따라 head flit, body flit, tail flit, 또는 이들의 조합이 될 수 있다. head flit은 packet의 첫 번째 flit이며 routing 정보를 포함한다. 이후에 0개 이상의 body flit과 tail flit이 뒤따른다. 매우 짧은 packet의 경우 body flit이 없을 수 있으며, 극단적으로는 단일 flit로 이루어진 packet의 경우 head flit이 tail flit 역할도 한다. 패킷이 네트워크를 통과할 때 head flit은 해당 패킷을 위한 channel state를 할당하며, tail flit은 이를 해제한다. body와 tail flit은 routing이나 sequencing 정보를 가지지 않기 때문에 head flit을 따라가며 순서를 유지해야 한다.

flit은 다시 하나 이상의 phit(physical transfer digit)으로 나뉜다. phit은 한 클록 사이클 동안 channel을 통해 전송되는 정보의 최소 단위이다. 자원이 phit 단위로 할당되지는 않지만, link level protocol은 channel 상의 phit을 해석하여 flit의 경계를 파악해야 한다.

왜 flit으로 packet을 나누는가? 모든 자원 할당(channel state, buffer capacity, channel bandwidth)을 packet 단위로 할 수도 있다. 실제로 이 방식을 사용하는 flow control 정책들도 있다. 하지만 이들은 packet 크기 선택에 있어 상충되는 제약을 겪는다.

패킷 크기를 키우면 routing 및 sequencing에 드는 overhead를 분산할 수 있다. 반면, 패킷 크기를 작게 하면 자원을 더 세밀하게 효율적으로 할당할 수 있고 blocking latency를 줄일 수 있다. flit을 도입하면 이러한 상충을 제거할 수 있다. 패킷은 비교적 크게 유지하면서도 flit을 매우 작게 만들어 자원을 효율적으로 사용할 수 있다.

크기에 대한 명확한 규칙은 없지만, 일반적으로 phit은 1비트에서 64비트 사이이며, 보통 8비트이다. flit은 보통 16비트(2바이트)에서 512비트(64바이트) 사이이고, 일반적으로 64비트(8바이트)이다. packet은 보통 128비트(16바이트)에서 512킬로비트(64킬로바이트) 사이이며, 보통은 1킬로비트(128바이트)이다. 이러한 일반적인 크기를 기준으로 할 때, 하나의 64비트 flit은 8개의 8비트 phit으로 구성되고, 하나의 1킬로비트 packet은 16개의 64비트 flit으로 구성된다.

12.2 Bufferless Flow Control

가장 단순한 형태의 flow control은 buffering 없이 작동하며, channel state와 bandwidth만 경쟁하는 패킷에 할당한다. 이 경우 flow-control 방식은 arbitration을 수행하여 어떤 패킷이 요청한 채널을 사용할지를 결정해야 한다. arbitration 이후, 선택된 패킷이 해당 채널을 통해 전진한다. 이때 실패한 패킷은 buffering이 없기 때문에 보류할 수 없으며, 드롭(drop)하거나 잘못된 경로로 전송(misroute)해야 한다.

예를 들어, 그림 12.3(a)의 상황을 보자. 두 개의 패킷 A와 B가 bufferless 네트워크 노드에 도착하여 둘 다 출력 채널 0을 요청한다. 그림 12.3(b)는 드롭 방식의 flow control로 이 충돌을 처리하는 방식을 보여준다. 여기서는 A가 arbitration에서 승리하여 출력 링크를 통해 전진하고, B는 패배하여 폐기된다. 이때 B를 이 지점까지 전진시키는 데 사용된 channel bandwidth 등의 자원은 낭비된다. B는 source에서 다시 전송되어야 하며, 이 source는 B의 buffered 복사본을 갖고 있어야 한다고 가정한다. 또한, B가 성공적으로 수신되었는지 또는 재전송이 필요한지를 알려주는 acknowledgment 메커니즘도 필요하다. 대안으로, 그림 12.3(c)처럼 B를 다른 출력 채널로 misroute할 수도 있다. 이 경우에는 충분한 경로 다양성과 목적지까지 재경로 지정할 수 있는 라우팅 메커니즘이 필요하다.

그림 12.4는 그림 12.3(b)의 드롭 방식 flow control에 대해 explicit negative acknowledgment(NACK)를 사용하는 time-space 다이어그램이다. 이 도표는 Gantt 차트처럼 수직 축에는 자원(채널)의 사용을, 수평 축에는 시간을 나타낸다. 다이어그램에서는 5-flit 패킷이 4-hop 경로를 따라 전송되는 과정을 보여준다. 수직축에는 네 개 채널(03)의 forward(F) 및 reverse(R) 방향이 교차로 표시되고, 수평축은 flit cycle(017)을 나타낸다. 첫 번째 전송에서 패킷은 채널 3을 할당받지 못해 드롭되며, 이로 인해 NACK가 reverse 채널을 통해 source로 전달되고, 그에 따라 재전송이 시작된다.

패킷 전송은 cycle 0에서 head flit(H)이 채널 0을 통과하며 시작된다. body flit(B)은 cycle 1~3에서 따라오고, tail flit(T)은 cycle 4에서 따라온다. 이 경우 tail flit은 아직 acknowledgment를 받기 전이므로 채널 0을 해제하지 않는다. cycle 1과 2에서는 head flit이 채널 1과 2를 통과하지만, 채널 3에서 경쟁에 부딪혀 할당에 실패하고 드롭된다. 이 실패를 알리기 위해, 채널 2의 반대편 라우터가 cycle 3에서 NACK를 reverse 방향으로 보낸다. 이 NACK는 cycle 4와 5에 걸쳐 채널 1과 0의 reverse 방향을 통해 source에 도달하며, 경유하는 각 노드에서 자원을 해제시킨다.

source가 NACK를 받은 후, cycle 6에서 패킷을 재전송한다. 재전송된 패킷은 목적지까지 필요한 4개 채널을 모두 할당받아 전달된다. head flit은 cycle 9에 목적지에 도달하고, tail flit은 cycle 13에 도달한다. 이후 cycle 14에 acknowledgment(A)가 reverse 채널을 통해 전송되며, cycle 17에 source에 도착한다. acknowledgment가 도달할 때마다 해당 노드에서 자원이 해제된다.

2장에서 구현한 dropping flow control은 NACK를 사용하지 않는다. 대신 timeout을 통해 패킷이 드롭되었음을 감지한다.

그림 12.5는 이를 보여준다. 패킷은 처음 전송에서 채널 3 할당에 실패하지만, NACK 없이 채널 0~2까지는 계속 전송되고 tail flit이 통과할 때 자원을 해제한다. 따라서 채널 0, 1, 2는 각각 cycle 5, 6, 7에 해제된다.

timeout이 경과하고도 acknowledgment를 받지 못하면, source는 cycle 12에서 패킷을 재전송한다. 이 재전송은 cycle 15~19에 걸쳐 성공적으로 이루어지고, cycle 20에 acknowledgment가 전송되어 cycle 23에 도착한다. 이 방식에서는 tail flit 이후 자원이 해제되므로 acknowledgment도 reverse 채널에서 경쟁해야 하며, 경우에 따라 acknowledgment 자체가 드롭될 수도 있다. 이 경우, 비록 패킷이 정확히 수신되었더라도 재전송이 발생한다. 중복 패킷을 제거하고 정확히 한 번만 수신되도록 하기 위해 수신 측에서는 보통 sequence number 기반 메커니즘이 필요하다.

dropping flow control은 구조는 단순하지만, 나중에 드롭될 패킷에 bandwidth를 낭비하므로 매우 비효율적이다. explicit NACK 없이 dropping flow control의 throughput 계산 방법은 2장에서 다루었다.

한편, 그림 12.3(c)와 같은 misrouting은 패킷을 드롭하지는 않지만, 잘못된 방향으로 전송하여 bandwidth를 낭비한다. 어떤 경우에는 offered traffic이 임계점에 도달하면 네트워크 throughput이 오히려 감소하는 불안정성(instability)으로 이어질 수 있다. misrouting은 패킷이 잘못된 경로에서도 목적지까지 도달할 수 있도록 충분한 경로 다양성이 있는 네트워크에서만 가능하다. 예를 들어, butterfly 네트워크에서는 하나의 잘못된 hop만으로도 패킷이 도착할 수 없기 때문에 misrouting이 불가능하다. torus 같은 충분한 경로 다양성이 있는 네트워크에서는 misrouting이 가능하지만, 너무 자주 misroute되면 목적지에 가까워지지 않고 계속 순환하는 livelock 문제가 발생할 수 있다. 따라서 misrouting을 포함한 flow control 정책은 모든 패킷이 결국 전달된다는 forward progress 보장이 필수적이다.

12.3 Circuit Switching

Circuit switching은 bufferless flow control의 일종으로, 먼저 source에서 destination까지의 채널을 할당하여 circuit을 형성한 뒤, 하나 이상의 패킷을 그 위로 전송하는 방식이다. 더 이상 보낼 데이터가 없으면 circuit을 해제한다. 그림 12.6은 이 과정을 네 단계로 보여준다.

• 첫 번째 단계 (cycle 0~4): source에서 destination까지 request(R)가 전파되어 채널을 할당한다. 이 예시에서는 충돌 없이 바로 목적지까지 도달한다.
• 두 번째 단계 (cycle 6~10): circuit이 할당되면, acknowledgment(A)가 source로 되돌아온다.
• 세 번째 단계: acknowledgment가 도착하면 circuit이 완전히 설정되어 이후 별도의 제어 없이 임의 개수의 데이터를 보낼 수 있다. 예시에서는 4-flit 패킷 두 개가 전송되고, 그 사이에 idle cycle 3개씩 삽입되어 있다.
• 네 번째 단계 (cycle 26~30): 더 이상 보낼 데이터가 없으면 tail flit(T)을 전송하여 채널을 해제하고 circuit을 종료한다.

Circuit switching은 dropping flow control과 달리, request flit이 차단되면 드롭되는 것이 아니라 해당 위치에 유지된다. 그림 12.7은 그림 12.6과 동일하지만 request가 채널 3을 할당받기까지 4 cycle 동안 지연되는 예시를 보여준다. 이 기간 동안 head flit은 block되어 있으며, 채널 3의 근접 라우터에서 유지되면서 반복적으로 재-arbitrate를 수행한다.

그림 12.6 설명
5-hop 경로 상에서 두 개의 4-flit 패킷을 circuit switching으로 전송한 time-space 다이어그램이다. 경합은 없으며, tr = 1 cycle, D = 0이다. 전송은 네 단계로 이루어진다.
1단계: request(R)가 목적지까지 전파되며 각 hop에서 채널 상태를 확보한다.
2단계: request가 목적지에 도달하면, acknowledgment(A)가 reverse 채널을 따라 source로 되돌아온다.
3단계: acknowledgment가 source에 도착하면, data flit(D)이 예약된 채널을 따라 전송된다. 이 circuit이 열려 있는 동안에는 추가적인 패킷도 전송 가능하다.
4단계: tail flit(T)이 경로를 지나면서 채널을 해제한다.

channel 3에 대한 접근을 위해 head flit은 매 cycle마다 시도하며, 결국 cycle 7에서 채널 3을 획득하고 circuit 할당을 계속 진행한다. dropping flow control과 비교할 때, circuit switching의 장점은 패킷을 드롭하지 않고 자원을 낭비하지 않는다는 점이다. 각 hop에서 header를 버퍼링하기 때문에 항상 forward progress를 보장한다. 그러나 circuit switching은 latency가 크고 throughput이 낮은 단점이 있어, buffered flow control에 비해 덜 매력적일 수 있다.

그림 12.6과 12.7의 time-space diagram을 보면, circuit switching으로 하나의 패킷을 전송할 때의 zero-load latency는 다음과 같다:

(여기서 wire latency는 무시함)

• 첫 번째 항: 경로 설정 및 head flit 전송에 걸리는 시간 (경합 없음 가정)
• 두 번째 항: serialization latency
• 세 번째 항: 전파 시간(time of flight)
• 마지막 항: 경합 시간

이 식은 식 3.11에서 주어진 header latency의 3배가 되는데, 그 이유는 source에서 destination까지 경로를 세 번 통과해야 하기 때문이다. (회로 설정 요청, acknowledgment, 실제 데이터 전송)

그림 12.7 설명
경합이 존재하는 circuit switching의 time-space 다이어그램. 그림 12.6과 동일한 상황이지만, request가 cycle 3~6 동안 block되다가 cycle 7에서야 channel 3을 할당받는다.

이러한 세 번의 경로 통과는 짧은 패킷 하나만 전송하는 경우 latency에 큰 영향을 준다.
또한 throughput도 낮아지는데, 이유는 채널이 예약된 시간이 실제 데이터가 전송되는 시간보다 길기 때문이다. 예를 들어 단일 패킷이 전송될 경우, 각 채널은 다음과 같은 시간 동안 점유된다:

• setup 시간 2Htr 동안 채널은 유휴 상태이다.
• 이 시간 동안 다른 회로에 할당될 수도 없고, 현재 회로도 아직 데이터를 보내지 못하므로 bandwidth 낭비가 발생한다.
• 특히 단기간의 회로에서는 이 오버헤드가 상당히 크다.

Circuit switching의 장점은 매우 간단하게 구현 가능하다는 것이다.
라우터의 로직은 2장에서 설명한 dropping flow control 라우터와 거의 유사하며,

• 각 입력에 request를 유지하기 위한 레지스터와
• reverse 경로만 추가하면 된다.

12.4 참고 문헌 메모 (Bibliographic Notes)

• Circuit switching은 전화망에서 기원하였으나, 현대의 인터커넥션 네트워크에서는 흔히 사용되지 않는다.
• Dropping flow control은 비효율적이지만 단순하여, BBN Butterfly(섹션 4.5)와 그 후속 모델인 BBN Monarch(섹션 23.4)에서 사용되었다.
• Misrouting (deflection 또는 hot-potato routing이라고도 함)은 Baran[12]에 의해 소개되었고, HEP Multiprocessor[174]와 Tera Computer System[9]에서 사용되었다.

12.5 연습문제

12.1 Dropping flow control with explicit nacks
섹션 12.2 및 그림 12.4에서 설명한 explicit NACK을 사용하는 dropping flow control 방식에 대해, 네트워크 throughput의 최대 상한(용량의 비율로)을 구하라. 최대 패킷 길이는 F flits, 평균 hop 수는 H_avg, uniform 트래픽, 대칭 토폴로지를 가정하라.

12.2 Timeout interval for dropping flow control
섹션 12.2 및 그림 12.5에서 설명한 timeout을 사용하는 dropping flow control 방식에 대해, 최대 패킷 길이가 F flits이고 네트워크의 각 hop이 하나의 flit 시간(cycle)을 요구한다고 할 때, 최소 timeout 간격을 F, 네트워크 diameter를 이용하여 표현하라.

12.3 Livelock with dropping flow control and timeout
timeout 기반 dropping flow control에서는 acknowledgment를 위한 reverse 채널이 예약되지 않으므로, acknowledgment도 경합으로 인해 드롭될 수 있다. 이로 인해 발생할 수 있는 livelock 문제를 설명하고, 간단한 해결책을 제안하라.

12.4 Optimistic circuit switching
optimistic circuit switching 기법은 header와 함께 데이터를 speculative하게 전송함으로써 zero-load latency를 줄일 수 있다. 만약 header가 차단되면, 데이터는 드롭되고 NACK이 부분적으로 예약된 경로를 따라 되돌아간다. 반대로 header가 성공하면, 데이터는 회로가 설정되자마자 목적지에 도달한다. speculative 데이터가 드롭되는 경우와 그렇지 않은 경우 각각에 대해 time-space 다이어그램을 그려라. tr = 1 cycle, D = 0으로 가정한다. 이 방식이 idle 상태의 예약 채널을 줄일 수 있는가? 그렇다면 얼마나 줄일 수 있는가?

12.5 Reservation circuit switching
기존 circuit switching과 유사하지만, request 메시지가 각 채널을 미래의 일정 시간 동안 (예: 15 cycle 후부터 10 cycle 동안) 예약하는 방식의 flow control을 생각하자. 경로상의 각 라우터는 request가 수용 가능할 경우 예약을 수행한다. 만약 불가능하다면 NACK을 보내 연결을 위한 기존 예약을 모두 취소하고 다시 시도한다. request가 목적지까지 도달하면, acknowledgment가 source로 전송되어 모든 예약을 확정한다. reservation circuit switching이 기존 방식보다 유리함을 보여주는 상황의 time-space 다이어그램을 그려라.

Abstract

지속적인 기술 미세화는 높은 확장성, 모듈성, 성능을 갖춘 heterogeneous system-on-chip (SoC) 및 homogeneous chip-multiprocessor (CMP)를 networks-on-chip (NoCs) 패러다임 기반으로 구현할 수 있는 유망한 가능성을 제공한다. 이러한 시스템에서는 계산 자원보다 통신 자원의 스케줄링 및 관리가 주요 설계 및 구현상의 과제가 되는 경우가 많다. 또한 이와 같은 시스템의 adaptive packet routing은 routing deadlock에 취약하며, 이는 성능 저하 또는 시스템 실패로 이어질 수 있다. 지금까지의 연구는 주로 설계 시점(design-time)에서의 복잡한 데드락 회피 접근법 또는 run-time의 단순한 휴리스틱 기반 검출 및 복구 방법에 집중되어 왔다. 그러나 후자의 방식은 네트워크에 대한 국소적(local) 또는 부분적(partial) 정보만을 고려하기 때문에, 특히 네트워크가 포화 상태에 가까울 때 차단된 패킷을 데드락으로 잘못 판단하는 오탐(false detection)이 많이 발생할 수 있다.

이 장에서는 데드락 회피가 아닌 데드락 검출 및 복구 전략을 다룬다. 특히 deadlock-equivalence set이라는 개념을 기반으로 런타임 transitive-closure (TC) 계산을 이용해 데드락 존재 여부를 판별하는 기법을 제안한다. 이 방법은 기존의 근사 및 휴리스틱 방법과는 달리 오탐 없이 모든 실제 데드락을 탐지할 수 있다.

또한 제안된 방법을 효율적으로 구현하기 위한 분산형 TC-network 아키텍처를 소개하며, 해당 하드웨어 구조 및 회로도도 자세히 설명한다. cycle-accurate 시뮬레이터를 기반으로 한 결과는 이 기법의 높은 효과성을 보여준다. 기존의 타이밍 기반 데드락 검출 방식에 비해 오탐을 제거함으로써 재전송으로 인한 에너지 낭비를 줄이고, 실제 응용 시나리오에서도 뛰어난 성능을 보인다.

3.1 Introduction

Networks-on-Chip (NoCs)은 on-chip 통신 구조 아키텍처로서, 네트워크 이론 및 기법을 단일 칩에 통합된 VLSI 시스템에 적용한 것이다. 이 아키텍처는 라우터(router)와 포인트-투-포인트 데이터 링크(channel)들로 구성된 네트워크이며, 라우터는 각기 다른 IP 코어들과 연결된다. 이 IP 코어는 프로세서, 메모리 모듈, DSP 블록 등을 포함할 수 있다.

이러한 분산된 IP 코어 간의 통신은 일반적으로 packet-switching 방식으로 수행되며, 메시지는 일정 크기의 packet 또는 flit으로 분할되어 라우터에서 라우터로 전달된다. NoCs는 기존의 버스 기반 인터커넥션에 비해 성능, 유연성, 확장성, 전력 효율 면에서 큰 이점을 제공한다. 그러나 라우터 네트워크 내에서의 deadlock은 통신 병목을 일으켜 성능 저하나 시스템 실패를 초래할 수 있다.

Deadlock은 두 개 이상의 packet(agent)이 서로의 자원(channel)을 기다리며 교착 상태에 빠지는 상황이다. 만약 패킷들 간의 의존성 순환(dependency cycle)이 형성되면 네트워크는 deadlock 상태가 된다. 예를 들어, Fig. 3.1과 같은 네 개의 패킷이 각각 어떤 채널은 점유하고 있으나, 다음 진행을 위해 다른 패킷이 점유한 채널을 요청하고 있는 상황을 생각해 보자. 이러한 경우 어느 누구도 필요한 채널을 얻지 못하고 교착 상태에 빠지게 되며, 이 순환을 외부에서 끊어주기 전까지는 해당 채널 모두 정지 상태로 유지된다.

deadlock은 네트워크의 자원을 정지시키고 다른 패킷들의 block 확률을 증가시키므로 반드시 제거되어야 한다. 이를 해결하는 전략은 크게 두 가지가 있다:

• deadlock avoidance (회피)
• deadlock recovery (복구)

deadlock avoidance에서는 네트워크 전체가 deadlock-free 상태를 유지하도록 패킷에 자원을 부여한다. 이 방식은 turn model을 기반으로 하여 특정 방향 전환을 제한하거나, virtual channels (VCs)의 엄격한 순서를 기반으로 deadlock을 방지한다. 하지만 일반적으로 avoidance 기법은 routing function에 제약을 두거나 추가 자원(예: VCs)을 필요로 한다. turn model은 단순하기 때문에 NoC에서 자주 사용되지만, routing 선택의 다양성을 제한하고 fault tolerance 능력을 떨어뜨린다. 더불어 이 방식은 임의의 네트워크 토폴로지에는 적용하기 어렵다.

한편, deadlock recovery 방식은 routing에 제한 없이 패킷에 채널을 할당하므로, 성능 면에서 avoidance 기법보다 우수할 수 있다. 이 경우 deadlock이 실제로 발생할 수 있기 때문에, 이를 효과적으로 검출하고 복구하는 메커니즘이 필요하다. 그러나 deadlock은 분산된 방식으로 발생하므로, 네트워크 전체에서 이를 검출하는 것은 매우 어려운 과제다. 일반적으로 timeout 기반 heuristic이 사용되며, 각 채널의 활동을 감시하여 일정 시간 이상 변화가 없으면 deadlock으로 추정한다. 하지만 이러한 방식은 네트워크가 포화 상태에 가까울 때 차단된 패킷을 잘못 탐지할 가능성이 크다.

기존의 일반 컴퓨터 네트워크에서는 timeout 방식의 한계를 줄이기 위한 다양한 기법이 제안되어 왔으나, threshold 값을 적절히 설정하는 것은 네트워크 설정에 따라 매우 어려운 일이다.

하지만 on-chip 네트워크에서는 노드 간 제어 신호를 패킷 외 별도의 전용선(dedicated wires)으로 전달할 수 있는 장점이 있다. 본 장에서는 이 NoC 특성을 활용하여 오탐 없는 정확한 deadlock 검출 기법을 제안한다. 이 방식은 runtime transitive-closure (TC) 계산을 통해 deadlock-equivalence set의 존재를 탐지하며, 제안된 구조는 NoC 인프라와 긴밀하게 연동되는 분산형 구조로 구현 가능하다. 이로 인해 추가적인 통신 트래픽 없이도 빠르게 계산을 수행할 수 있다. 본 연구의 초기 결과와 아키텍처 스케치는 [1]에 제시되었고, [2]에서는 TC 계산 기반의 이론적 프레임워크와 하드웨어 구조, 실생활 응용 사례에 대한 실험 결과가 포함되어 있다.

3.2 Related Work

NoC에서의 deadlock recovery에 관한 연구는 드물며, 대부분의 관련 정보는 일반 컴퓨터 네트워크 분야에서 차용되었다. [27, 33]에서는 라우팅의 자유도가 충분히 보장되고 이를 알고리즘이 충분히 활용하는 경우, deadlock이 발생할 가능성이 매우 낮다고 보고하였다. 따라서 드문 경우의 이벤트인 deadlock을 방지하기 위해 turn model을 사용하여 routing의 유연성을 제한하거나【9,10, deadlock 방지를 위한 VC 전용 구조를 설계하는 것은 바람직하지 않다는 결론을 내렸다【14,15】. 이후부터는 효율적인 검출 및 복구 메커니즘이 존재한다는 가정 하에, deadlock recovery가 avoidance보다 성능 면에서 유리하다는 점이 주목받게 되었다【22, 24, 25, 30】.

deadlock recovery는 두 단계로 구성된다:

1. 검출 (Detection)
2. 복구 (Recovery)

검출 단계에서는 runtime 동안 deadlock dependency cycle을 탐지해야 한다. 그러나 deadlock은 분산적으로 발생하기 때문에 runtime 탐지는 매우 어려우며, 대개 timeout 메커니즘을 사용한 분산 방식으로 구현된다【3,4,18,21,22,24,25,30】. 간단한 예로, 어떤 채널이 일정 시간 동안 비활성 상태라면 deadlock 상태일 가능성이 있다고 간주하여 recovery 절차를 시작한다【3】. 이를 구현하기 위한 최소 하드웨어 구성은 카운터, 비교기(comparator), 래치(latch), threshold 값을 저장하는 레지스터이다. 이 방식에서의 정확도는 네트워크 부하와 메시지 길이에 민감하다. threshold 시간이 길면 정확도가 높지만 deadlock 탐지에 시간이 오래 걸리고, 반대로 짧으면 빠른 탐지는 가능하지만 오탐율이 올라간다【25】. 오탐이 많아지면 recovery 전용 채널이 포화되어 네트워크 성능이 오히려 저하될 수 있다【25】.

이 문제를 해결하기 위한 여러 기법이 제안되었다. 예를 들어 [24]에서는 block된 패킷이 요청하는 모든 채널이 일정 시간 비활성 상태일 때만 deadlock으로 간주하며, [25]에서는 block된 패킷 중 단 하나만을 deadlock으로 식별하는 방법으로 오탐률을 줄이고자 한다. 그러나 이 방식은 추가 하드웨어(비교기 2개, 래치 2개, threshold 2개)가 필요하다. [30]에서는 probe 패킷을 통해 비활성 채널을 탐색하여 보다 정확한 검출을 시도했다. 그러나 이들 모두 timeout 기반이며, traffic 및 network load에 따라 적절한 threshold 값을 조정하기 어렵다는 공통의 한계가 있다.

따라서 오탐 없이 deadlock을 정확히 검출할 수 있고, 네트워크 상태와 무관하게 빠르게 작동할 수 있는 새로운 방식이 요구된다.

3.3 Methodology for Deadlock Detection

이 절에서는 본 장에서 제안하는 deadlock-equivalence set(DES) 개념과 전체적인 deadlock 검출 방법론을 제시한다.

3.3.1 Background and Assumptions

본 연구는 minimal path를 사용하는 fully adaptive routing algorithm을 가정한다. 여기서 minimal은 송신자와 수신자 간의 최단 경로만을 선택함을 의미한다. 또한 wormhole flow control 방식을 사용하며, 이는 NoC에서 널리 사용되는 기법이다【12, 29】. wormhole 방식에서는 packet이 더 작은 단위인 flit으로 나뉘며, header flit이 먼저 경로를 설정하고 나머지 flit들이 그 경로를 따라 파이프라인 방식으로 이동한다. 이 방식은 각 라우터의 버퍼 수요를 줄이는 장점이 있으나, 네트워크를 block과 deadlock에 더 취약하게 만든다【26, 33】.

본 연구에서는 deadlock avoidance 기법을 사용하지 않고, 정확한 deadlock detection을 전제로 한 deadlock recovery 전략을 채택하였다. 기존 연구들【3, 22, 24, 25, 30】과 동일하게, 본 연구에서는 하나의 채널 버퍼에는 서로 다른 packet의 flit이 공존하지 않는다고 가정한다. 또한 목적지에 도달한 packet은 즉시 소비된다고 간주하여, NoC와 IP core 간의 프로토콜 상호작용 수준에서는 deadlock이 없다고 본다.

이 연구의 초점은 라우팅 수준에서 발생하는 deadlock이며, 향후 과제로는 IP core 간 프로토콜 상호작용으로 인해 발생할 수 있는 deadlock까지 검출 대상을 확장하는 것을 계획하고 있다. 이 장에서는 channel 자원을 소유하거나 요청하는 agent를 flit으로 정의하지만, 이는 message 또는 packet으로 간주해도 무방하다.

3.3.2 Deadlock에 대한 Equivalence Set 기준

정의 및 차이

흐름 예시 (패킷 흐름)

1. Injection:
   • IP 코어(예: CPU)가 flit/packet을 생성
   • 이 flit은 injection channel을 통해 해당 라우터에 주입됨
   • 라우터는 이를 네트워크 내부로 전파
2. Delivery:
   • 패킷이 목적지 라우터에 도착
   • 라우터는 패킷을 delivery channel을 통해 해당 IP 코어(예: 메모리)에 전달

그림으로 요약하면:

3.3.3 Equivalence Set 계산 복잡도

앞 절에서 살펴본 바와 같이 (자세한 내용은 [2] 참조), deadlock-equivalence set (DES)은 deadlock을 검출하는 데 있어 간단한 기준을 제공한다. 이 기법은 네트워크에서 CWG(Channel Wait-for Graph)를 생성하고, 그로부터 transitive-closure (TC)를 도출한 후, DES 조건(Eq. 3.1)을 만족하는 채널들을 식별하는 방식이다.

Fig. 3.3은 이 개념을 시각적으로 설명한다.

어떤 특정 상태의 네트워크(Fig. 3.3a)가 주어졌을 때, 해당 CWG(Fig. 3.3b)를 쉽게 도출할 수 있다. 이어서 얻은 TC 그래프(Fig. 3.3c)는 self-reflexive 경로를 가진 네 개의 채널(vertex)를 명확히 보여주며, 이들은 모두 DES 조건을 만족한다.

Algorithm 1 설명

DES 존재 여부를 TC 계산을 통해 확인하는 소프트웨어 알고리즘

• 입력
  • CCC: CWG의 vertex(채널) 집합
  • EEE: CWG의 edge 집합
• 출력
  • self-reflexive path를 갖는 DES가 존재하면 True, 그렇지 않으면 False

이 알고리즘은 세 개의 중첩 루프를 포함하며, 내부 루프는 O(n) 연산을 수행한다.

• 2–10행에서는 방향 그래프(CWG)를 **Boolean Adjacency Matrix AAA**로 변환한다.
• 12–18행에서는 **transitive-closure TTT**를 계산한다. 이때 Tk[i][j]T^k[i][j]Tk[i][j]는 다음 중 하나일 경우에 True가 된다:
  1. Tk−1[i][j]T^{k-1}[i][j]Tk−1[i][j]가 이미 참인 경우 (즉, 이전에 경로가 존재했던 경우)
  2. i→ki \to ki→k 경로와 k→jk \to jk→j 경로가 동시에 존재하는 경우
• 19–23행에서는 TC 행렬 내에서 **자기 자신을 가리키는 self-reflexive path T[i][i]=TrueT[i][i] = TrueT[i][i]=True**가 하나라도 존재하는지 확인한다. 있다면 True를 반환하여 DES 존재를 알린다.

계산 비용 분석

• 소프트웨어 상 계산 복잡도:
  • 시간 복잡도: O(n3)O(n^3)O(n3) (CWG의 vertex 수인 nnn은 네트워크 채널 수와 동일함)
  • 공간 복잡도: O(n2)O(n^2)O(n2)
• 하드웨어 가속 가능성:
  • 기존 연구에서는 O(n2)O(n^2)O(n2)개의 processing element를 갖는 systolic array 구조를 통해 O(n)O(n)O(n) 시간에 TC 계산이 가능하다고 보고되었다【19】.
• 본 연구에서는:
  • 이러한 복잡도를 간소화하기 위해 NoC의 분산 아키텍처를 활용하여 TC 계산을 구현함

이러한 분산형 접근은 복잡도 저감, 하드웨어 병렬성 활용, 네트워크 오버헤드 최소화라는 장점을 제공한다.

3.4 Transitive Closure (TC) 네트워크 아키텍처

3.4.1 TC-Network 기반의 TC 계산

동적 프로그래밍(Dynamic Programming, DP)은 TC(Transitive Closure) 계산 문제에 대한 해를 제공할 수 있으며【11】, 병렬 아키텍처를 활용한 계산에 적합하다. 이 TC 계산을 병렬 처리 플랫폼에 매핑하는 방법으로 TC-network 개념을 도입한다. 이 네트워크는 병렬 아키텍처를 가지며, 연쇄적인 추론 전파를 동시에 수행함으로써 TC를 계산할 수 있다.

Lam과 Tong은 DP-network 구조를 제안하여, 비동기적이며 연속 시간 기반 계산 문맥에서 다양한 그래프 최적화 문제를 해결하였다【20】. 이러한 추론 네트워크는 항상 안정적인 동작을 보이며, 본 연구에서는 해당 네트워크 개념을 NoC의 런타임 DES 탐지에 적용하였다. 제안된 TC-network는 기존 DP-network처럼 분산 아키텍처로 구현 가능하며, NoC 인프라와 밀접하게 결합되어 작동할 수 있다.

TC-network는 자율 연산 유닛(computational unit)들을 상호 연결하여 구성되며, Fig. 3.4는 이러한 일반적인 inference 네트워크 내 유닛 구조 및 링크 구성을 보여준다. 각 유닛은 두 객체 간 이진 관계 (i,j)(i, j)(i,j)를 표현하고, 주변의 hhh개의 이웃 유닛들로부터 값을 받아 site function을 통해 추론 연산을 수행한다. 이때 Sk(i,j)S_k(i, j)Sk​(i,j)는 kkk번째 site의 출력이며, g(i,j)g(i, j)g(i,j)는 유닛 (i,j)(i, j)(i,j)의 출력이다. TC 계산은 다음과 같이 정의된다:

여기서 ∧(AND)는 site function의 추론 연산자이며, ∨(OR)는 unit function의 충돌 해소 연산자이다. 각 유닛은 라우터 노드를, 링크는 통신 채널을 나타내며, NoC 구조와 동일한 방식으로 유닛들이 상호 연결된다.

TC-network의 수렴 시간(convergence time)은 DES 크기와 네트워크 토폴로지에 따라 달라진다. 이는 NoC 내부의 정보 전파 지연 및 각 유닛의 연산 지연에 영향을 미친다. 각 유닛은 인접 edge 수를 |A|라 할 때, O(|A|)개의 AND 연산과 1개의 OR 연산을 수행한다. 따라서 연산 시간은 O(k|A|)이고, 여기서 k는 각 유닛이 반복적으로 갱신되는 횟수이다. 소프트웨어에서는 보통 k = 노드 수로 설정되어 모든 노드가 업데이트되도록 보장한다. 하지만 하드웨어 병렬 구현에서는 k가 네트워크 구조에 따라 결정되며, |A|개의 AND 연산은 병렬로 실행된다.

표 3.1: 다양한 네트워크 토폴로지에서의 DES 분석

네트워크 토폴로지노드 수채널 수최소 DES 크기최대 DES 크기

k-ary 1-cube	k	2k	k	k
k-ary 2-cube	k2k^2k2	4k24k^24k2	4	3k2−83k^2 - 83k2−8
k-ary 2-mesh	k2k^2k2	4k2−4k4k^2 - 4k4k2−4k	4	3k2−3k−23k^2 - 3k - 23k2−3k−2

 

 

• 예) k-ary 1-cube(ring)는 최대 채널 수 2k이며, 유일한 DES는 길이 k의 종속 순환
• 2D mesh에서는 최소 DES는 4개 노드, 최대 DES는 3k2−3k−23k^2 - 3k - 23k2−3k−2

DES 크기 및 분포는 검출 시간에 큰 영향을 미친다.

3.4.2 TC-Network와 NoC의 결합

TC-network는 on-chip 네트워크 구조에서 각 노드에 TC-unit을 배치하여 구현된다. 일반적인 컴퓨터 네트워크와 달리, NoC에서는 전용 제어선(wires)을 통해 라우터 간 제어 정보를 직접 교환할 수 있다.

Fig. 3.5는 제안된 TC-network 구조를 보여주며, 각 노드에 TC-unit과 TC-interconnect가 구성되어 있다. 예시로는 2D mesh를 들고 있으나, 이는 Definition 2 조건만 만족하면 임의의 토폴로지에도 적용 가능하다. 각 TC-unit은 각 채널에 대해 Eq. 3.2와 3.3을 수행하고, 그 출력은 이웃 유닛으로 전달된다. 이러한 TC-unit은 NoC 라우터와 런타임 정보(채널 점유 상태, 요청 상태 등)를 교환하며 밀접하게 동작한다.

deadlock 검출의 목적은 recovery 메커니즘을 트리거하는 것이다. 각 DES에서 하나의 패킷만 복구해도 deadlock 순환을 깰 수 있다. 하지만 네트워크 전체에 대해 TC 계산을 수행하면, 동일 DES에 속하는 모든 채널이 동시에 검출되며, 이로 인해 recovery 오버헤드가 증가할 수 있다.

예를 들어 Fig. 3.3c에서는 ch1, ch5, ch7, ch9에 self-reflexive 경로가 존재하며 모두 동일한 DES에 속한다. 이를 줄이기 위해 경량화된 계산 방식으로 각 채널에 대해 self-reflexive path가 존재하는지 여부만 검사할 수 있다. 이 경우, 상호 배제 회로(mutual exclusion circuit) 기반으로 몇 개의 logic gate와 wires만으로 TC-network를 구현할 수 있다.

• TC-network 내에서 오직 하나의 채널만 동시에 검사
• 채널은 token-ring 프로토콜을 사용해 순차적으로 검사
• mesh 및 torus 네트워크의 경우, Hamiltonian cycle 기반 경로 사용 가능【2, 3】
• 토큰 링은 **비동기 회로(asynchronous circuit)**로 구현되며, 라우터 클록을 공유하는 동기식은 권장되지 않음

이러한 비동기 방식은 TC-unit과의 동기화 회로를 요구하며, 이는 3.4.3에서 설명됨.

토큰이 순환하면, 이는 목적지를 바꾸면서 여러 source에서 하나의 목적지를 찾는 문제와 동일하다. TC-unit이 토큰을 획득하면, 해당 라우터의 채널들을 검사하기 시작하고, 다른 유닛들은 채널 종속 관계에 따라 test 신호를 이웃으로 전달한다. 이 방식은 TC-network를 self-pruning 구조로 만들어 전력 소모를 줄일 수 있다.

Algorithm 2는 TC-unit의 동작을 요약한 의사코드(pseudocode)이다.

Algorithm 2: TC-unit 연산의 의사코드

• 정의
  • par: 병렬 연산
  • n: 이웃 라우터에서 오는 채널 수
  • m: 이웃 라우터로 나가는 채널 수
  • tp[m]: 임시 버퍼
• 입력
  • tc_rx[n]: 이웃 라우터로부터의 TC-network 신호
  • ch_oc[n]: 로컬 라우터의 채널 점유 상태
  • ch_req[n][m]: 로컬 라우터의 채널 요청 상태
  • ch_sel[m]: self-reflexive 검사를 위한 채널 선택
• 출력
  • tc_tx[m]: 이웃 라우터로 전달되는 TC-network 신호
  • dd_flags[m]: 로컬 라우터용 deadlock 검출 플래그

deadlock detection/recovery 전략의 궁극적인 목적은 deadlock 발생 시 recovery 메커니즘을 작동시키는 것이다. 각 DES마다 하나의 패킷만 복구하면 dependency cycle을 깨뜨릴 수 있다. 그러나 전체 네트워크에 대해 TC 계산을 수행하면, 동일한 DES에 속한 모든 채널을 한꺼번에 검출하게 되어 오히려 복구 오버헤드가 증가할 수 있다.

예를 들어 Fig. 3.3c에서 TC 그래프는 ch1, ch5, ch7, ch9 주변에 self-reflexive path가 형성되어 있으며, 이들은 모두 같은 DES에 속한다(Eq. 3.1 만족). 하드웨어 복잡도를 줄이기 위해, TC 알고리즘은 multi-source → single-destination 네트워크에서 경로를 탐색하는 방식으로 대체할 수 있다.

이 경우, 다음과 같은 방식으로 간단한 TC-network를 구현할 수 있다:

• mutual exclusion unit 기반의 경량 네트워크
• 단순한 logic gate 및 적은 수의 wire 사용
• 각 채널에 대해 self-reflexive path 존재 여부만 확인 (i.e., TC 행렬에서 Ti,i=TrueT_{i,i} = \text{True}Ti,i​=True인지 여부)

이러한 구조에서 하나의 채널만 동시에 TC-network 사용 가능하며, token-ring protocol을 통해 채널을 순차적으로 검사한다. 이 프로토콜은 mesh나 torus 네트워크의 경우 Hamiltonian cycle 기반으로 구성할 수 있으며【2,3】, 토큰 링은 비동기 회로로 구현되거나, 라우터 클록으로 동기화할 수도 있다. 다만 전체 칩에 걸친 동기식 클록은 비현실적이므로, 본 연구에서는 비동기 토큰 링 회로를 구현하였다. 이를 위해 각 라우터 노드의 TC-unit과 **동기화 회로(synchronizer)**가 필요하다(3.4.3절에서 설명).

토큰이 네트워크를 순환하는 것은 목적지를 바꾸며 경로를 찾는 것과 동일하다. 토큰을 획득한 TC-unit은 해당 라우터의 채널들을 검사하며, 나머지 유닛들은 자신의 입력과 출력 사이에 종속 체인이 존재할 경우에만 test 신호를 전달한다. 이런 방식은 TC-network를 self-pruning 구조로 만들어, 불필요한 switching power를 줄인다.

토큰을 획득한 TC-unit의 동작은 Algorithm 2에 기술되어 있으며, 이 유닛은 검사 결과에 따라 해당 채널의 deadlock 플래그를 설정하고, 검사 완료 후 다음 유닛에게 토큰을 넘긴다.
TC-network의 수렴 시간은 DES의 크기에 비례하지만, deadlock은 지속적인 현상이기 때문에 반드시 한 사이클 내에 수렴하지 않아도 유효한 출력을 생성할 수 있다【14】.

3.4.3 하드웨어 구현 (Hardware Implementation)

Fig. 3.6은 최신 라우터 구조에 TC-unit과 TC-interconnect를 추가한 하드웨어 구조도를 보여준다.

• 왼쪽: 라우터의 top-level 구조
• 중앙: TC-unit 블록 구현
• 오른쪽: TC-computation 블록 상세 회로

이 구조는 n개의 입력 채널, m개의 출력 채널을 가지는 라우터에 TC 기능을 추가한 것이다.

중앙의 TC-unit 블록은 세 개의 하위 모듈로 구성된다:

1. TC-computation unit
   • Eq. 3.2와 3.3을 구현
2. 채널 선택 회로(channel selection circuit)
   • 라우터의 채널을 순차적으로 선택
   • 최악의 지연 상황을 고려한 시간 지연 포함 (3.5.2.4절 참조)
3. 토큰 링 프로토콜(token-ring protocol)
   • 해당 라우터 노드의 채널 검사를 시작

TC-computation 블록은 다음 입력을 사용한다:

• tc_rx[]: 이웃 라우터로부터 받은 TC 신호
• ch_oc[]: 로컬 채널 점유 상태
• ch_req[][]: 로컬 채널 요청 상태
• ch_sel[]: 채널 선택 회로의 출력

출력으로는 다음을 생성한다:

• tc_tx[]: 이웃에게 보내는 TC 신호
• dd_flags[]: 로컬 라우터에 보내는 deadlock 검출 플래그

신호 수는 네트워크 토폴로지에 따라 달라진다. 예를 들어, 2D mesh의 경우에는 n, m이 각각 {North, East, South, West}가 된다. 해당 회로는 Fig. 3.6 (오른쪽)에 제시된 회로도이며, 동작은 Algorithm 2에 기술되어 있다.

토큰 링 프로토콜은 검사 시작 노드를 바꾸기 위한 메커니즘이다. 비동기 토큰 링의 구현은 David Cell 회로를 사용할 수 있으며【32】, 자세한 구현은 [2]에서 설명된다.

• 하드웨어 연결:
  • 전 라우터로부터 입력 2선, 다음 라우터로 출력 2선을 필요로 함
• 동작 절차:
  • TC-unit이 토큰 획득 → 채널 선택 회로에 start 신호 전송
  • 모든 채널 검사 완료 후 done 신호 발생 → 다음 라우터로 토큰 전달

Fig. 3.6의 구조는 이러한 동작을 수행하기 위해 필요한 회로 및 배선을 시각적으로 보여준다.

설계 확장성

Fig. 3.6의 아키텍처는 가능한 구현 방식 중 하나일 뿐이며, 상황에 따라 다양한 최적화가 가능하다. 예를 들어, 라우터 채널을 동시에 여러 개 검사하도록 확장할 수도 있다. 이 경우 토큰을 복수로 배치하여 동시에 여러 라우터를 활성화시킬 수 있다.

단, 이 방식은 TC-unit과 TC-interconnect의 복제가 필요하므로 **면적(area)**과 **전력(power)**이 증가할 수 있다. 그러나 실험된 traffic 패턴 및 네트워크 토폴로지에서는 큰 성능 차이는 관찰되지 않았다.

3.5 결과 및 고찰 (Results and Discussion)

3.5.1 평가 방법론 (Evaluation Methodology)

본 절에서는 제안된 TC-network 기법과 기존의 heuristic timeout mechanism【3】을 비교하여, 다양한 네트워크 트래픽 조건과 flit 주입률(injection rate)에 따른 deadlock 검출률을 평가한다.

• Deadlock 검출률은 다음과 같이 정의된다:
  → 전체 패킷 수(수신 + 검출) 중에서 deadlock으로 검출된 패킷 수의 비율

deadlock으로 추정된 패킷은 네트워크에서 제거된다.
검출된 패킷을 드롭(drop)할 때 발생하는 에너지 소모도 함께 측정하였다.

네트워크에서 소모되는 에너지는 다음 다섯 가지 범주로 구분된다:

1. Routing energy – 라우팅 방식에 따라 다름
2. Selection energy – 라우팅이 여러 옵션을 반환할 경우 선택 과정에서 발생
3. Forwarding energy – flit 전송 시 발생
4. Receiving energy – flit 수신 시 발생
5. Waiting energy – header flit이 라우팅 성공을 기다리는 동안의 에너지

검출된 패킷을 제거하는 데 드는 총 에너지는 다음과 같이 계산된다:

Edd_resolving=h×(Eforward+Ereceiving)+Flitage×[Ewait+f×(Erouting+Eselection)](3.4)E_{dd\_resolving} = h \times (E_{forward} + E_{receiving}) + Flitage \times [E_{wait} + f \times (E_{routing} + E_{selection})] \tag{3.4}Edd_resolving​=h×(Eforward​+Ereceiving​)+Flitage×[Ewait​+f×(Erouting​+Eselection​)](3.4)

여기서:

• hhh: 해당 flit이 제거되기 전까지 이동한 홉 수
• FlitageFlitageFlitage: flit이 NoC에 존재한 clock cycle 수 (이동 및 대기 포함)
• fff: head flit 여부를 나타내는 Boolean 플래그
  • head flit일 경우, 매 cycle마다 출력 채널을 점유하려 시도하면서 에너지를 소모하게 됨

3.5.2 평가 결과 (Evaluation Results)

3.5.2.1 Synthetic Traffic

Fig. 3.7은 4×4 2D mesh NoC에서 uniform traffic 패턴을 사용하여, 서로 다른 injection rate 조건에서 성능을 비교한 결과이다.

• 패킷 길이는 2~16 flit 사이에서 임의로 생성됨

Fig. 3.7a – Deadlock 검출률 (%):

• timeout 기법의 경우 대부분이 false alarm임
• 예) threshold = 32일 때, injection rate가 높은 경우 전체 패킷의 22%가 deadlock으로 잘못 검출
• 반면, TC-network는 실제 deadlock에 해당하는 패킷만 검출하며, 이는 1% 미만
  • 이는 deadlock이 매우 드문 이벤트라는 기존 문헌【33】의 결과와 일치함

Fig. 3.7b – Throughput vs Average Delay:

• timeout threshold가 작을수록 throughput과 delay가 개선됨
• 이유: false deadlock 패킷을 빠르게 제거하여 네트워크 혼잡 완화
• 단, 단순히 패킷을 제거만 하므로 성능 자체에 큰 의미는 없음

→ 종합적으로 보면, threshold = 256이 적절한 설정

• 검출률: 2.7% (최소값)
• 성능: 양호한 throughput과 delay 제공

하지만 다양한 network 설정(패킷 길이, 버퍼 크기, 트래픽 유형)에 따라 최적 threshold 값이 달라짐

• 따라서 threshold 조정이 필요한 timeout 방식은 튜닝 부담이 큼
• 반면, TC-network는 파라미터 조정 없이도 정확한 deadlock 검출 가능

Fig. 3.7c – deadlock 해소에 소모된 에너지 비율:

• 에너지 소비율은 Fig. 3.7a의 deadlock 검출률과 유사하지만, 선형적 비례는 아님
• timeout 방식은 head flit이 timeout까지 계속 시도하면서 에너지를 소비하기 때문

예:

• timeout-128:
  • 검출률 5.3%
  • 에너지 낭비 8.8%
• timeout-512:
  • 검출률 2.6%
  • 에너지 낭비 9.1%

그 이유는:

1. threshold가 큰 경우, 시뮬레이션 시간 내에 전달되는 flit 수가 더 적음 (Fig. 3.7b 참조)
2. Eq. 3.4의 Flitage 항은 threshold 값에 비례함

3.5.2.2 실제 응용 트래픽 (Real Application Traffic)

보다 현실적인 통신 시나리오로, MMS 시스템【17】이 평가에 사용되었다. 이 시스템은 다음의 모듈들로 구성된다:

• h263 비디오 인코더
• h263 비디오 디코더
• MP3 오디오 인코더
• MP3 오디오 디코더

[17]에서는 이 MMS를 40개의 개별 태스크로 분할하고, 이를 25개의 IP 코어에 할당 및 스케줄링하였다. IP 코어들은 [5]에서 제안된 방식에 따라, 5×5 mesh 기반 NoC 구조의 tile에 매핑되었다.

• Fig. 3.9a, 3.9c를 보면, TC-network 기법은 다양한 timeout threshold 값을 사용한 기존의 방식들보다 우수한 성능을 보였다.
• 특히, TC-network는 deadlock을 전혀 검출하지 않았으며, 이에 따라 **재전송으로 인한 에너지 소비가 0%**였다.
• 반면, 기존 crude timeout 방식【3】은 상당량의 false deadlock을 검출하였으며, 그만큼의 불필요한 에너지 낭비가 발생하였다.

예:

• threshold = 64 일 때, MMS traffic 중 최대 27%가 deadlock으로 잘못 검출
• [24], [25] 방식은 crude timeout 방식보다 false alarm을 줄였으나, 완전히 제거하지는 못함

Fig. 3.9b – Throughput vs Average Delay:

• timeout 방식에서 threshold 값을 작게 설정하면, throughput과 delay는 개선되었음
• 이는 false deadlock을 더 많이 검출하고 패킷을 제거함으로써 네트워크 혼잡을 완화했기 때문
• 그러나 이러한 방식은 결국 불필요한 에너지 소비로 이어짐

이에 따라 다음과 같은 실험이 추가 수행됨:

• 고정된 데이터량 (2MB MMS 트래픽)을 다양한 네트워크 부하 조건에서 전송
• 이때 소모되는 총 에너지(전송 + 복구 포함) 측정
• Table 3.3에 그 결과가 제시됨

결과적으로, TC-network 방식은 timeout 방식(예: threshold=64)과 비교했을 때, 최대 5% 에너지 절감 효과를 보였다.

3.5.2.3 면적 및 전력 소모 추정 (Area and Power Estimation)

NoC를 설계할 때는 라우터가 전체 실리콘 면적에서 너무 큰 비중을 차지하지 않도록 해야 한다. 이를 위해 본 연구에서는 다음 두 가지 라우터를 Verilog로 설계하고 비교하였다:

1. timeout 기반 fully adaptive 라우터
2. TC-network 기반 fully adaptive 라우터

두 설계 모두 Synopsys Design Compiler를 사용하여 합성되었고, UMC 90nm 공정 라이브러리에 매핑되었다.

• FIFO 버퍼 영역이 라우터 로직에서 가장 많은 면적을 차지함은 기존 연구【6】와 동일하게 확인되었다.
• FIFO 면적은 주로 flit 크기에 따라 결정되며,

예) flit 크기 = 64bit, 버퍼 용량 = 4 flits일 때:

• **TC 회로가 전체 라우터 면적에서 차지하는 비율은 단 0.71%**에 불과함

이는 deadlock 검출 기능 추가에 따른 오버헤드가 매우 작다는 점을 보여준다.

3.5.2.4 Delay 분석 (Delay Analysis)

비동기 회로에서의 지연은 다양한 요소들에 의해 결정되며, 특히 회로 내에서 사용되는 게이트 수 및 그 게이트들의 연결 구조에 따라 크게 달라질 수 있다.

TC-unit의 지연 시간은 다음 세 가지 요소로 구성된다:

1. AND 연산 지연:
   • nnn개의 이웃 채널로부터 수신된 TC 신호들과
   • 해당 채널의 점유 상태(ch_oc[j])
   • 그리고 요청 상태(ch_req[j][i])
     를 이용해 수행되는 연산이다. 이 연산은 게이트 지연 하나 또는 둘 정도가 걸린다.
2. OR 연산 지연:
   • 모든 AND 결과를 집계하는 연산으로, 병렬로 계산된다.
   • 채널 수가 많지 않기 때문에, 지연은 작으며 실제로는 **log₂(m)**에 비례하는 OR 게이트 딜레이에 해당한다.
3. 선택 및 제어 회로의 지연:
   • 채널 선택 로직은 worst-case 경로 지연을 고려하여 설계됨
   • 예를 들어, channel 1부터 channel m까지 순차적으로 확인하는 방식으로, 각 채널에 일정 시간(예: 하나의 clock cycle)을 배정함

총합적으로 보면, 하나의 라우터에 대한 deadlock 검출은 단지 m개의 채널을 순차적으로 확인하는 시간에 해당하며,
각 확인은 gate-level delay 수준이므로, 전체 지연은 매우 작다.

토큰링 구조에서는 다음 조건이 적용된다:

• 하나의 TC-unit만 토큰을 가지고 있고,
• 순차적으로 인접한 TC-unit에게 토큰을 전달함

따라서 TC-network가 전체적으로 deadlock 정보를 수렴(converge)하는 데 걸리는 총 시간은:

• TC-unit의 지연
•  
• DES의 크기 (토큰이 이동해야 하는 라우터 수)

이렇게 구성된다. 다시 말해, **deadlock 검출까지의 최악 지연 시간(worst-case delay)**은 DES가 형성된 채널 수와 동일하며,
이는 시스템의 deadlock 전파 경로와도 동일하다.

하지만 중요한 점은:

deadlock은 순간적인 이벤트가 아니라 지속되는 현상이기 때문에,
TC-network가 한 사이클 내에 수렴하지 않아도 검출 정확도에는 영향이 없다.

3.6 요약 및 결론 (Summary and Conclusions)

adaptive routing을 사용하는 NoC는 deadlock에 취약하며, 이는 성능 저하나 시스템 실패로 이어질 수 있다. 본 장에서는 **deadlock 회피(avoidance)**가 아닌, **deadlock 검출(detection)**과 **복구(recovery)**에 초점을 맞추어 연구를 진행하였다.

런타임에서의 deadlock 검출은 분산 특성 때문에 매우 어렵다. 본 연구는 런타임 transitive closure (TC) 계산을 활용하여 NoC 내의 deadlock-equivalence set (DES) 존재 여부를 찾아내는 deadlock 검출 방법을 제안하였다. DES는 NoC 내에서 패킷 요청 간 순환 루프(loop)를 의미한다. 본 기법은 기존의 근사 또는 휴리스틱 방식들과 달리, false alarm 없이 모든 실제 deadlock을 정확하게 검출할 수 있다.

또한, 이 검출 메커니즘을 효율적으로 구현하기 위한 분산형 TC-network 아키텍처도 함께 제안되었다. 이 아키텍처는 NoC 구조와 밀접하게 결합되어 동작한다.

제안된 방법은 cycle-accurate 시뮬레이터와 합성 도구를 통해 철저히 평가되었다. 그 결과는 다음과 같은 장점을 명확히 입증하였다:

• 다양한 트래픽 시나리오(실제 응용 포함)에서 기존 타이밍 기반 deadlock 검출 방식보다 현저히 우수
• false detection을 제거함으로써, false alarm으로 인한 에너지 낭비를 줄임
• time-out 메커니즘이 전혀 필요 없음
• 네트워크 부하나 메시지 길이와 무관하게 정확한 deadlock 검출 가능
• 기존 방식이 혼잡도 기반 추정(congestion estimation)에 의존하는 반면, 본 방법은 명확한 논리 기반 검출 수행
• TC-network 방식은 기존 방식 대비 최대 두 자릿수(10배 이상) false detection 감소 효과를 보임

하드웨어 구현에 있어서도 다음과 같은 결과를 얻었다:

• TC-network의 하드웨어 오버헤드는 매우 작음
• 본 장에서 제시한 구현 결과는 면적 및 전력 소비 측면에서도 부담이 적음을 보여줌

핵심은 deadlock을 회피(avoidance)하기보다는, 런타임에서 정확하게 검출하고 빠르게 복구(recovery)하는 데 있다.

deadlock 검출을 위해서는 채널 간의 의존 관계(CWG: Channel Wait-for Graph)를 기반으로 한 transitive closure (TC) 계산이 필요하다.
하지만 이 계산은 O(n³)의 시간 복잡도를 가지므로, 실시간 검출에는 부적합하다.

이를 해결하기 위해 저자는 하드웨어 병렬화를 활용한 TC-network 구조를 제안한다.
이 구조는 분산형 계산 유닛(distributed computation units)을 각 라우터 노드에 삽입하여 병렬적으로 TC를 계산함으로써 deadlock-equivalence set(DES)을 빠르고 정확하게 검출할 수 있게 한다.

결론적으로, 이 논문은:

• deadlock의 빠른 검출
• 정확한 복구 트리거
• 하드웨어 기반 병렬 아키텍처로 구현 가능
• false alarm 제거 및 에너지 낭비 감소

를 통해 고신뢰성 NoC 설계에 적합한 솔루션을 제시한다는 점에서 의의가 있습니다.