이 자료를 쓰는 강의: 31 credit flow control, routing, router microarchitecture

Lec22 - Interconnect II

한국어판 강의자료 · 38쪽

p.1

p.2routing algorithm(라우팅 알고리즘)

p.3라우팅 개요

네트워크 구조를 가정할 때 이상적인 라우팅을 논의한다.
실제로는…
routing algorithm(라우팅 알고리즘)이 이상적이지 않다.
목표: 경로들 사이에 트래픽을 균일하게 분산시킨다.
hot spots(핫스팟), contention(경쟁)을 피한다.
더 균형 잡힌 분산 → 이상적인 처리량에 더 가까워짐
복잡성을 고려해야 한다.
복잡한 라우팅은 라우팅 지연이 상당히 커질 수 있다.
기법

p.4routing algorithm(라우팅 알고리즘)의 분류

adaptivity(적응성): 네트워크 상태(예: 혼잡도)를 고려하는가?
oblivious(비적응형) – deterministic(결정론적) vs. non-deterministic(비결정론적)
adaptive(적응형)
hop count(호프 수): 허용되는 모든 경로가 minimal(최소 경로)인가?
minimal(최소 경로)
non-minimal(비최소 경로)
라우팅 결정은 어디에서 이루어지는가?
source routing(소스 라우팅)
per-hop routing(호프별 라우팅)
implementation(구현)
table(테이블)
circuit(회로)
randomized(랜덤화)

p.5routing deadlock(라우팅 데드락)

각 패킷은 링크를 점유하고 다른 링크를 기다리고 있다.
라우팅 제한이 없으면 resource cycle(자원 사이클)이 발생할 수 있다.
데드락으로 이어진다.
두 가지 일반적인 회피 방법:
deadlock-free routing(데드락 없는 라우팅): routing algorithm(라우팅 알고리즘)이 허용하는 턴의 집합을 제한한다.
deadlock-free flow control(데드락 없는 흐름 제어): virtual channels(가상 채널)을 현명하게 사용한다.
예: escape VCs(탈출 가상 채널) 사용

p.6dimension order routing(차원 순서 라우팅)

네트워크 차원을 하나씩 순차적으로 탐색한다.
2차원에서는 X-Y routing(X-Y 라우팅) 또는 Y-X routing(Y-X 라우팅)을 사용한다.
X-Y routing(X-Y 라우팅): X 차원을 완료한 후에야 Y 차원으로 전환할 수 있다.
Y-X routing(Y-X 라우팅): Y 차원을 완료한 후에야 X 차원으로 전환할 수 있다.
deterministic(결정론적)이고 minimal(최소 경로)이다.
X-Y routing(X-Y 라우팅)의 턴
Y-X routing(Y-X 라우팅)의 턴

p.7Valiant’s oblivious routing algorithm(Valiant의 비적응형 라우팅 알고리즘)

oblivious(비적응형) routing algorithm(라우팅 알고리즘)
s에서 d로 라우팅하기 위해
임의로 중간 노드 d’를 선택
s에서 d’로, 그리고 d’에서 d로 라우팅
모든 트래픽 패턴을 randomized(랜덤화)
모든 패턴이 균일한 랜덤처럼 보임
네트워크 부하를 균형 있게 분산
non-minimal(비최소 경로)
destroys locality(국소성 파괴)

p.8minimal oblivious routing(최소 비적응형 라우팅)

Valiant의 방법: load balancing(로드 밸런싱)은 하지만 hop count(호프 수)가 크게 증가
minimal oblivious routing(최소 비적응형 라우팅): 일부 load balancing(로드 밸런싱)은 있으나 최단 경로 사용
d’는 최소 사분면 내에 있어야 함
d’에 대해 6가지 선택지 존재
이 예시에서는 3가지 다른 경로만 존재

p.9oblivious(비적응형) 라우팅

Valiant의 방법과 minimal adaptive routing(최소 적응형 라우팅)은 X-Y routing(X-Y 라우팅)과 함께 사용 시 데드락 없음
X-Y 경로와 Y-X 경로 중에서 임의로 선택한다면?
oblivious(비적응형)이지만 데드락 없음은 아님!
어떻게 데드락 없이 만들 수 있나요?
적어도 두 개의 virtual channels(가상 채널) 필요

p.10adaptive(적응형)

path diversity(경로 다양성) 활용
network state(네트워크 상태)를 이용해 라우팅 결정
buffer occupancies(버퍼 점유율)이 자주 사용됨
flow control(흐름 제어) 메커니즘, 특히 back pressure(백프레셔)에 의존
local information(로컬 정보)는 쉽게 접근 가능
global information(글로벌 정보)는 얻는 데 비용이 큼
network state(네트워크 상태)는 빠르게 변화 가능
local information(로컬 정보) 사용 시 최적 선택이 아닐 수 있음
minimal(최소 경로) 또는 non-minimal(비최소 경로)일 수 있음

p.11minimal adaptive routing(최소 적응형 라우팅)

local information(로컬 정보)만 사용할 경우 하위 최적 선택이 발생할 수 있음

p.12non-minimal adaptive routing(비최소 적응형 라우팅)

완전히 adaptive(적응형)
최단 경로에 제한되지 않음
misrouting(오류 라우팅): 생산적인 채널이 아닌 경로로 패킷 유도
생산적인 출력에 우선순위 부여
일부 알고리즘은 u-turn(U턴) 금지
livelock(라이브락) 가능성: 목적지에 도달하지 않고 네트워크를 계속 순환
forward progress(전진 진행)을 보장하는 메커니즘 필요
misrouting(오류 라우팅) 횟수 제한

p.13non-minimal(비최소 경로) 라우팅 예시

더 긴 경로이지만 잠재적으로 낮은 지연 시간
s
d
s
livelock(라이브락): 사이클 내에서 계속 라우팅

p.14adaptive(적응형) 라우팅: turn model(턴 모델)

성공적인 adaptive(적응형) 라우팅을 위해서는 path diversity(경로 다양성)이 필요하다
너무 많은 턴을 제거하면 라우팅의 유연성이 제한된다
예: DOR은 4개의 턴을 제거한다
• 북쪽에서 동쪽, 북쪽에서 서쪽, 남쪽에서 동쪽, 남쪽에서 서쪽
질문: 가능한 최소한의 턴만 제거하면서 데드락 없음을 보장하려면 어떻게 해야 하는가?
유효한 turn model(턴 모델)의 예시:
west first(서쪽 우선)
north last(북쪽 마지막)
negative first(음수 우선)

p.15turn model(턴 모델) routing deadlock(라우팅 데드락)

NW와 WN 턴을 제거하는 것은 어떻게 되는가?
유효하지 않은 턴 제거이다
resource cycle(자원 사이클)이 발생한다
→ 모든 2개 제거가 유효한 turn model(턴 모델)을 만드는 것은 아니다

p.16virtual channels(가상 채널)을 이용한 deadlock avoidance(데드락 회피)

deadlock-free routing(데드락 없는 라우팅) flow control(흐름 제어)는 데드락 없음을 보장하여 더 유연한 라우팅을 가능하게 한다
라우팅이 데드락 없이 아니라면, 가상 채널(VCs)이 resource cycle(자원 사이클)을 깨뜨릴 수 있다
각 virtual channels(가상 채널)은 물리적 링크에 시간 분할로 할당된다
VC를 보유하는 것은 물리적 링크를 보유하는 것이 아니라, VC의 버퍼 큐를 보유하는 것이다
두 가지 옵션을 고려할 것이다:
VC 순서
escape VCs(탈출 가상 채널)

p.17옵션 1: VC 순서

dateline(데이트라인)을 넘기 전까지 모든 메시지는 VC 0을 통해 전송된다
dateline(데이트라인)을 넘은 후에는 VC 1에 할당된다
다시 VC 0에 할당될 수 없다
0
1
3
2

p.18옵션 2: escape VCs(탈출 가상 채널)

순서를 강제하는 것은 VC 이용률을 낮춘다
이전 예시: VC 1이 과도하게 미사용된다
escape VCs(탈출 가상 채널):
하나의 virtual channel(가상 채널)은 deadlock-free routing(데드락 없는 라우팅)을 사용한다
예: VC 0은 DOR을 사용하고, 다른 virtual channels(가상 채널)들은 임의의 라우팅 함수를 사용한다
virtual channels(가상 채널) 접근은 공정하게 조정된다: 패킷은 항상 escape VCs(탈출 가상 채널)에 도착할 기회를 가진다

p.19protocol level deadlock(프로토콜 레벨 데드락)

Request-Reply dependency(요청-응답 의존성)
네트워크가 요청으로 가득 차서 네트워크 인터페이스가 응답을 생성하기 전까지는 소비될 수 없음
다중 메시지 클래스 간의 데드락 의존성
해결책: 가상 채널(VCs)의 집합을 통해 여러 개의 logical networks(논리적 네트워크) 생성
예: VC0는 요청용, VC1은 응답용
coherence protocols(코히어런스 프로토콜)로부터 추가 의존성을 처리하기 위해 더 많은 VCs가 필요함
요청 큐(RequestQ)
응답 큐(ReplyQ)
메모리 / 캐시
컨트롤러
상호연결 네트워크
network end node(네트워크 종단 노드)

p.20router microarchitecture(라우터 마이크로아키텍처)

p.21router microarchitecture(라우터 마이크로아키텍처) 개요

virtual channel router(가상 채널 라우터)의 마이크로아키텍처에 초점
대역폭 요구 증가에 따라 라우터 복잡도 증가
고대역폭이 필요하지 않을 때 간단한 라우터 설계
wormhole flow control(웜홀 흐름 제어), virtual channels(가상 채널) 없음, DOR 라우팅, 파이프라인 없음 등

p.22virtual channel router(가상 채널 라우터)

route computation(경로 계산)
VC allocator(가상 채널 할당기)
switch allocator(스위치 할당기)
input buffers(입력 버퍼)
virtual channels(가상 채널) VC1, VC2, VC3, VC4
crossbar switch(크로스바 스위치)
input(입력) 5, input(입력) 1, output(출력) 5, output(출력) 1
credits in(크레딧 입력), credits out(크레딧 출력)
input buffers(입력 버퍼), route computation(경로 계산) 논리, VC allocator(가상 채널 할당기), switch allocator(스위치 할당기), crossbar switch(크로스바 스위치)
대부분의 NoC 라우터는 input buffers(입력 버퍼) 기반
버퍼는 라우터 내부에 플릿을 저장

p.23baseline router pipeline(기본 라우터 파이프라인)

표준적인 논리적 라우터 파이프라인
목표 주파수와 스테이지 지연에 따라 물리적 스테이지에 맞춤
BW (버퍼 쓰기): 입력 VC를 디코딩하고 버퍼에 쓰기
RC (경로 계산): 출력 포트 결정
VA (가상 채널 할당): 출력 포트에서 사용할 VC 결정
SA (Switch Allocation)(스위치 할당): 크로스바의 입력 및 출력 포트에 대해 중재
ST (스위치 통과): 출력 포트 승인 후 스위치 통과
LT (링크 통과): 안전한 여정!
contention(경쟁)이 발생하여 VA 또는 SA가 실패하면 패킷이 정지

p.24기본 라우터 파이프라인 (2)

head flit(헤드 플릿)은 모든 6개 스테이지 통과
body flit(바디 플릿)과 tail flit(테일 플릿)은 RC 및 VA 스킵
route computation(경로 계산)과 VA (VC Allocation)(가상 채널 할당)은 패킷당 한 번만 수행
바디 및 tail flit(테일 플릿)은 head flit(헤드 플릿)으로부터 이 정보 inherit(상속)
tail flit(테일 플릿)은 virtual channel(가상 채널)을 해제

p.25라우터의 모듈과 의존성

모듈 간 출력과 입력 사이의 의존성
라우터를 통과하는 핵심 경로를 결정
라우팅 수행 전에는 스위치 포트를 contention(경쟁)할 수 없음
Decode + Routing
Switch Arbitration
Crossbar Traversal
Wormhole Router
Decode + Routing
Switch Arbitration
Crossbar Traversal
Virtual Channel Router
VC Allocation
Decode + Routing
Speculative
Switch Arbitration
Crossbar Traversal
Speculative Virtual Channel Router
VC Allocation
→ speculation(추측)이 실패할 경우는 어떻게 되는가?

p.26라우터 파이프라인 성능

기본(부하 없음) 상태에서 네트워크를 통과하는 지연
라우팅 지연이 추가되어 메시지 지연에 영향
이상적으로는 링크 지연만 지불
또한 buffer turnaround time(버퍼 전환 시간)을 증가시킴
더 많은 버퍼가 필요
클럭 주기 시간에 영향
파이프라인 단계를 줄이는 기법
(5 사이클 + 링크 지연) × hop count(호프 수) + t_serialization

p.27최적화: lookahead routing(미리 라우팅)

현재 라우터에서 다음 라우터에 대한 라우팅 계산 수행
버퍼 쓰기(BW)와 겹침
경로 사전 계산을 통해 플릿이 BW 이후 즉시 가상 채널(VCs) contention(경쟁) 가능
BW
RC
VA
SA
ST
LT
BW
RC
SA
ST
LT
헤드
바디/테일

p.28헤드 / 바디/테일

파이프라인 최적화: speculation(추측)
virtual channels(가상 채널) 할당(VA)이 성공할 것이라고 가정
저~중간 부하에서 유효
VA와 SA를 병렬로 수행
VA 실패 시(가상 채널이 반환되지 않음)
다음 사이클에서 VA/SA를 다시 수행
비추측 요청 우선순위 부여
바디/tail flit(테일 플릿)은 이미 VC 정보를 가지고 있으므로 speculation(추측)이 아님
BW
RC
VA
SA
ST
LT
BW
RC
VA
SA
ST
LT

p.29파이프라인 최적화: bypassing(바이패스)

input buffers(입력 버퍼)에 플릿이 없을 경우
스위치 통과(ST)를 speculation(추측)적으로 수행
포트 충돌 시 speculation(추측) 중단
첫 번째 단계(설정 단계)
• lookahead routing(미리 라우팅) → head flit(헤드 플릿)만 디코딩
• VA와 SA를 병렬로 수행
• BW 생략: speculation(추측) 실패하지 않으면 버퍼에 쓰지 않음
Setup
ST
LT
Setup
ST
LT
헤드
바디/테일

p.30arbiter(중재기)와 allocator(할당기)

allocator(할당기): N개의 요청을 M개의 자원에 매칭
arbiter(중재기): N개의 요청을 1개의 자원에 매칭
VC allocator(가상 채널 할당기) (VA)
출력 virtual channels(가상 채널)에 대한 contention(경쟁) 해결
입력 virtual channels(가상 채널)에 할당
switch allocator(스위치 할당기) (SA)
입력 virtual channels(가상 채널)에 crossbar switch(크로스바 스위치) 포트 할당
매칭 확률이 높은 arbiter(중재기)/allocator(할당기)는 네트워크 대역폭 증가로 이어짐
또한 빠르거나 pipelined(파이프라인화) 가능해야 함

p.31round robin arbiter(라운드 로빈 중재기)

마지막으로 서비스된 요청은 가장 낮은 우선순위를 가짐
현재 grant vector(승인 벡터)에서 다음 priority vector(우선순위 벡터)를 생성함
fairness(공정성)을 보여줌
Gi가 승인되면 다음 사이클에 Pi+1이 높아짐

p.32separable allocator(분리형 할당기)

간단하고 pipelined(파이프라인화) 가능한 allocator(할당기)의 필요성
allocator(할당기)는 arbiter(중재기)들로 구성됨
arbiter(중재기)는 단일 자원에 대한 N개의 요청 중 하나를 선택함
separable switch allocator(분리형 스위치 할당기)
첫 번째 단계: 각 입력 포트에서 단일 요청을 선택함
두 번째 단계: 각 출력 포트에 대해 단일 요청을 선택함

p.33separable allocator(분리형 할당기)

3:4 allocator(할당기)
첫 번째 단계: 3:1 – 각 입력에 대해 단일 승인을 보장함
두 번째 단계: 4:1 – 각 출력에 대해 단일 승인만 설정함
요청자 1이 자원 A를 요청함
요청자 1이 자원 C를 요청함
요청자 4가 자원 A를 요청함
자원 A가 요청자 1에게 승인됨
자원 A가 요청자 2에게 승인됨
자원 A가 요청자 3에게 승인됨
자원 A가 요청자 4에게 승인됨
자원 C가 요청자 1에게 승인됨
자원 C가 요청자 2에게 승인됨
자원 C가 요청자 3에게 승인됨
자원 C가 요청자 4에게 승인됨

p.34separable allocator(분리형 할당기) 예시

4개의 요청자, 3개의 자원
요청들 사이에서 로컬로 할당함
로컬 승자들을 두 번째 단계로 전달함
요청자 1이 A를 승리함
요청자 4가 C를 승리함

p.35VC allocator(가상 채널 할당기) 구성

라우팅 함수에 따라 달라짐
라우팅 함수가 단일 virtual channel(가상 채널)을 반환하는 경우
VCA는 동일한 출력 virtual channels(가상 채널)을 contention(경쟁)하는 입력 가상 채널들 사이에서 할당해야 함
라우팅 함수가 동일한 물리적 채널에 대해 다수의 후보 virtual channels(가상 채널)을 반환하는 경우
승자 요청을 두 번째 단계로 전달하기 전에 첫 번째 단계 요청들 사이에서 할당이 필요함

p.36adaptive(적응형) 라우팅 및 allocator(할당기) 설계

deterministic(결정론적) 라우팅
단일 출력 포트
switch allocator(스위치 할당기)가 출력 포트를 입찰함
adaptive(적응형) 라우팅
옵션 1: 다수의 후보 출력 포트를 반환함
• switch allocator(스위치 할당기)가 모든 포트에 대해 입찰할 수 있음
• 승인된 포트는 승인된 virtual channels(가상 채널)과 일치해야 함
옵션 2: 단일 출력 포트를 반환함
• VA (VC Allocation)(가상 채널 할당)에 실패하면 패킷을 다시 라우팅함

p.37speculative virtual channel router(추측형 가상 채널 라우터)

non-speculative(비추측형) 스위치 요청은 speculative(추측형) 요청보다 높은 우선순위를 가져야 한다.
두 개의 병렬 switch allocator(스위치 할당기) — speculative(추측형)용 1개, non-speculative(비추측형)용 1개 — 존재
출력에서 non-speculative(비추측형) 요청을 speculative(추측형) 요청보다 우선시한다.
플릿이 speculative switch allocation(추측형 스위치 할당)에서는 성공할 수 있지만, VA (VC Allocation)(가상 채널 할당)에서는 실패할 수 있다.
이 두 과정은 병렬로 수행된다.
speculation(추측)이 잘못되었을 경우 → switch reservation(스위치 예약)이 낭비된다.
body flit(바디 플릿)과 tail flit(테일 플릿): non-speculative(비추측형) 스위치 요청
VA (VC Allocation)(가상 채널 할당)을 수행하지 않음 → head flit(헤드 플릿)에서 inherit(상속)한다.

p.38질문?

더 깊이 있는 인터커넥션 네트워크에 대해 알고 싶다면 다음 책들을 참고하세요.

`Ctrl K · s`	자료 검색
`[ ]`	이전·다음 강의
`Space`	영상 재생·정지
`j k`	다음·이전 section
`n p`	다음·이전 slide
`b`	강의 목록 접기·펴기
`t`	맨 위
`/`	강의 검색
`Esc`	닫기