Lec 21 part 2 & Lec 22 · credit flow control, routing, router microarchitecture

1.1Lec 21 의 buffer backpressure 를 이어 credit-based flow control 과 credit round-trip delay 로 buffer 크기를 정한다.

1.2Lec 22: routing algorithm 분류, routing deadlock 과 DOR, Valiant·minimal oblivious, adaptive, turn model.

1.3VC 를 이용한 deadlock avoidance(VC ordering, escape VC)와 protocol-level deadlock.

1.4VC router microarchitecture, pipeline 최적화(lookahead, speculation, bypass), arbiter·allocator. 과목 마지막 강의.

상황·문제마지막 강의. 지난 시간의 flow control(circuit, packet, flit, VC)을 정리하고 이후 VC 또는 wormhole flow control 을 쓴다고 가정한다.

원인flit 단위 flow control 은 downstream buffer 가 있을 때만 flit 을 보낼 수 있다.

해결buffer 가용성을 알리는 backpressure mechanism 을 먼저 다루고 routing·router microarchitecture 로 넘어간다.

상황·문제upstream router 는 downstream buffer 에 자리가 있는지 알아야 한다(overflow 방지).

원인이 알림 mechanism 이 부실하면 throughput 이 떨어진다.

해결credit-based(가장 널리 쓰임)와 on/off 중 credit-based 를 사용: VC 별 credit count 를 두고 전송 시 감소, buffer 해제 시 credit 반환.

상황·문제node 1 이 3-flit packet 을 credit 2 로 node 2 에 보내는 예를 cycle 별로 따라간다.

원인head·body 전송 후 credit 0 이라 tail 은 stall, node 2 의 RC·VA 가 끝나 flit 이 떠나야 credit 이 돌아온다.

해결credit 은 downstream VC 하나당 하나. on-chip 은 별도 wire(valid 1-bit + VC ID), off-chip 은 packet 에 piggyback 또는 별도 credit packet. on/off 는 전용 wire 1/0.

상황·문제buffer 가 1 entry 면 flit 하나 보낸 뒤 credit 이 돌아올 때까지 기다려야 한다.

원인flit 전송, router 처리, credit 전송, credit 처리를 합친 credit round-trip delay(t_crt) 동안 전송이 막힌다.

해결buffer ≥ t_crt flit 으로 설계. 예: propagation 1(×2) + credit 처리 1 + pipeline 3 → 최소 6 flit buffer.

상황·문제packet 이 hop 마다 어느 output port 로 갈지 정해야 한다. topology 비교는 ideal routing 을 가정했다.

원인실제 routing 은 먼 곳 정보가 부족하고, 복잡하면 router delay 가 커진다.

해결traffic 을 고르게 분산해 hotspot·contention 을 피한다. 분류: oblivious/adaptive, minimal/non-minimal, source/per-hop, table/circuit/randomized.

상황·문제flow 들이 buffer 자원에 cyclic dependency 를 만들면 어떤 packet 도 전진 못 한다.

원인routing 제한이 없으면 link 를 잡고 다른 link 를 기다리는 resource cycle 이 생긴다.

해결turn 을 제한하는 deadlock-free routing 또는 VC 를 쓰는 deadlock-free flow control. 대표: DOR(X-Y) 는 Y→X turn 4개를 금지.

상황·문제DOR 은 load balancing 이 약하다(예: mesh 중앙 contention).

원인deterministic 경로는 traffic pattern 에 따라 특정 channel 에 몰린다.

해결Valiant: random 중간 node 경유로 uniform random 화(대신 locality 파괴·경로 증가). minimal oblivious: 중간 node 를 minimal quadrant 로 제한.

상황·문제oblivious 는 network 상태를 보지 않아 path diversity 를 충분히 못 쓴다.

원인adaptive 는 credit count 같은 local 정보에 의존하고, global 정보는 전파 비용이 크며 금방 stale 해진다.

해결minimal adaptive 는 최단 경로 안에서, non-minimal 은 misrouting 도 허용(productive 우선, misroute 횟수 제한으로 livelock 방지).

상황·문제adaptive routing 은 path diversity 가 필요한데 DOR 은 turn 4개를 없앤다.

원인deadlock 을 막으려면 cycle 을 만드는 turn 은 금지해야 한다.

해결8개 turn 중 2개만 제거: west first, north last, negative first. NW·WN 제거처럼 cycle 이 남는 조합은 invalid.

상황·문제routing 을 제한하지 않고도 deadlock freedom 을 얻고 싶다.

원인VC 는 physical link 를 time-multiplex 하므로 VC 점유는 buffer queue 점유일 뿐이다.

해결VC ordering(dateline 넘으면 VC 1, 되돌아가기 금지) 또는 escape VC(VC 0 은 DOR, 나머지 임의 routing).

상황·문제routing deadlock 을 없애도 문제의 절반만 해결된다.

원인request 와 reply 같은 message class 가 end node 의 두 queue 사이 dependency 를 만든다.

해결request/reply 용 physical network 분리 또는 VC 로 logical network 분리(VC0 request, VC1 reply). directory coherence 처럼 3종이면 VC 최소 3개.

상황·문제router 를 실제로 어떻게 설계하는가(VC router 중심).

원인bandwidth 요구가 커질수록 VC·adaptive routing 등으로 복잡도가 증가한다.

해결구성: input buffer(VC), RC, VC allocator, switch allocator, crossbar. pipeline BW→RC→VA→SA→ST→LT, allocation 실패 시 stall.

상황·문제zero-load delay = (5 cycles + link delay) × hops + t_serialization.

원인router delay 는 latency 를 늘리고 credit round-trip 을 늘려 buffer 가 더 필요하다.

해결lookahead routing(4 stage) → speculative VA·SA 병렬(3 stage) → bypassing(setup, ST 의 2 stage). setup 을 미리 보내면 1 stage 도 가능.

상황·문제VA 와 SA 는 여러 요청과 자원을 matching 해야 한다.

원인matching 이 좋아야 bandwidth 가 높고, 동시에 clock cycle 안에 끝나거나 pipeline 되어야 한다.

해결round-robin arbiter(마지막 서비스 최저 priority), arbiter 조합의 separable allocator(input 단계 → output 단계). speculative router 는 non-spec 요청 우선.

상황·문제참고 도서 안내(빌려줄 수 있음). 기말고사 월요일, 최종 발표 수요일, project report 금요일 마감.

upstream 이 downstream VC 별 빈 buffer 수를 credit 으로 추적, 0 이면 전송 중단.

flit 전송부터 credit 이 돌아와 처리될 때까지. buffer ≥ t_crt flit 이어야 throughput 유지.

network 상태를 보지 않는 routing. random 이어도 됨(deterministic 과 구분).

dimension 순서대로 이동(X-Y). turn 4개 금지로 deadlock-free, deterministic·minimal.

random 중간 node 경유로 load balance, 대신 locality 파괴·경로 증가.

cycle 을 만드는 turn 만 최소로 금지(west first, north last, negative first).

한 VC 는 deadlock-free routing(예: DOR), 나머지는 임의 routing.

request/reply 등 message class 간 dependency 로 생기는 deadlock. logical network(VC) 분리로 해결.

VA 가 성공한다고 보고 SA 를 병렬 수행. 실패 시 재시도, non-speculative 요청 우선.

input 단계 arbiter 와 output 단계 arbiter 를 이어 만든 allocator, pipelining 쉬움.

4.1propagation 1, credit 처리 1, router pipeline 3 cycle 일 때 필요한 최소 buffer 는?

4.2X-Y 와 Y-X 를 random 으로 고르는 routing 은 deadlock-free 인가?

4.3VC ordering 과 escape VC 의 차이는?

4.4lookahead routing 이 줄이는 stage 는?

4.5speculative SA 에서 non-speculative 요청을 우선하는 이유는?