대기열을 나누면 비어 있던 전송 시간을 되찾을 수 있다
물리 링크는 비어 있는데 다음 패킷이 움직이지 못하는 장면이 있다. 앞선 패킷이 더 먼 곳에서 막혀서, 뒤의 패킷이 사용할 대기열을 붙잡고 있기 때문이다. virtual channel은 이런 결합을 느슨하게 만드는 방법이다. 다만 논리 채널 두 개를 만들었다고 같은 전선이 두 배의 데이터를 보내는 것은 아니다.
기다리는 공간과 전송 기회를 나눈다
virtual channel, 줄여서 VC는 물리 링크에 연결된 독립적인 flit 대기열과 그 상태를 말한다. 상태에는 어떤 패킷이 사용하는지, 다음 경로가 무엇인지, 수신 측에 공간이 있는지 등이 들어간다. 패킷은 한 VC의 순서를 따라가고, 여러 VC가 물리 링크의 전송 기회를 놓고 중재한다.
원문의 핵심은 버퍼를 배정받는 일과 물리 전송 대역폭을 배정받는 일을 분리하는 것이다. 막힌 패킷이 한 대기열을 점유해도 다른 대기열의 준비된 패킷이 링크를 사용할 수 있다. Dally 원문 PDF 4–5쪽, III절
한 대기열 안에서 막힌 head를 건너뛰어 뒤의 body를 보내지는 않는다. body는 같은 패킷의 경로 상태를 따르므로 그것만 전진시켜도 별개의 요청을 처리한 것이 아니다. 서로 다른 패킷을 독립된 대기열에 두어야 우회할 전송 후보가 생긴다.
여덟 슬롯을 두 방식으로 쓰는 계산
어떤 입력에 세 flit짜리 패킷 P와 Q가 이미 대기하고 있다고 하자. P는 다음 북쪽 자원이 cycle 0–5 동안 막혀 있고, Q의 동쪽 경로는 계속 비어 있다. 스위치는 서로 다른 출력으로 갈 수 있지만 이 입력에서는 한 cycle에 한 flit만 읽을 수 있다. 다른 입력의 경쟁과 후속 홉의 지연은 제외한다.
첫 구성은 깊이 8인 하나의 FIFO에 P 다음 Q를 넣는다. P가 앞에 있으므로 cycle 0–5에 Q를 선택할 수 없다. P가 cycle 6–8에 나간 뒤 Q가 9–11에 나가고, 두 패킷의 전송은 cycle 11에 끝난다. 동쪽 출력에 여유가 있어도 입력 FIFO의 순서가 Q를 가린다.
두 번째 구성은 같은 총 여덟 슬롯을 깊이 4의 VC 두 개로 나누고 P와 Q를 각각 배정한다. Q는 준비된 VC이므로 cycle 0–2에 나갈 수 있다. P는 여전히 북쪽이 열리는 cycle 6을 기다리고 6–8에 나간다. 두 패킷의 완료가 cycle 8로 앞당겨진다. P의 막힘 자체를 없앤 것이 아니라, P를 기다릴 이유가 없는 Q를 먼저 처리한 결과다.
이 계산은 Q가 이미 별도 VC에 들어 있고, 필요한 출력·다운스트림 공간을 얻는다는 조건에서 성립한다. Q가 상류의 동일한 단일 대기열 뒤에 갇혀 있다면 현재 라우터에 VC를 추가하는 것만으로 즉시 꺼내 올 수 없다. 경로 전체에서 어느 지점의 결합을 풀었는지 확인해야 한다.
같은 출력으로 몰리면 전선의 한계는 남는다
이번에는 P와 Q가 모두 같은 출력 링크로 가며 그 수신기가 매 cycle 한 flit을 받아 준다고 하자. 링크의 한계가 한 flit/cycle이면 두 VC를 번갈아 선택해도 합계는 한 flit/cycle이다. 여섯 flit을 세 cycle에 보내지 못한다. VC는 사용하지 못했던 시간을 줄일 수 있지만 이미 계속 사용 중인 전선의 용량을 늘리지는 않는다.
출력의 수신기가 모두 멈췄거나, 각 VC의 head가 모두 공간 부족으로 막혔다면 우회 후보도 없다. 반대로 한 패킷이 막히고 다른 패킷이 진행 가능한 상황이 자주 나타나면 분리된 대기열의 가치가 커진다. 평균 처리율뿐 아니라 어떤 패킷의 대기시간이 줄었는지 보는 이유다.
같은 저장량이어도 깊이가 바뀐다
여덟 슬롯을 두 VC로 나누면 각 VC의 깊이는 네 슬롯이다. 긴 지연 동안 한 패킷만 계속 보내야 한다면, 분리 전보다 작은 대기열이 먼저 차서 송신이 멈출 수 있다. 네 슬롯이 다른 VC에 남아 있다고 반드시 빌려 쓸 수 있는 것도 아니다. 고정 분할인지 공유 저장 공간인지에 따라 다르다.
VC 수가 늘면 점유 상태와 흐름 제어 상태, 선택 후보도 늘어난다. 중재가 복잡해지거나 파이프라인 지연이 커지면 대기열 분리의 이득을 일부 잃을 수 있다. BookSim은 VC 개수와 VC당 깊이를 각각 설정하도록 한다. 공식 Flow control 설정
또한 VC가 여러 개라는 사실만으로 영구 대기를 막았다고 증명하지는 않는다. 어떤 VC에서 어떤 VC로 이동할 수 있는지에 따라 자원 대기의 순환이 다시 생길 수 있다. 처리율을 위한 분리와 경로의 안전성은 적용한 배정 규칙으로 각각 확인해야 한다.
virtual channel을 넣을 때 먼저 묻고 싶은 것은 ‘막힌 패킷 옆에 준비된 패킷이 실제로 있는가’다. 그 패킷이 독립된 공간과 전송 후보를 얻을 수 있다면 비어 있던 링크 시간을 되찾는다. 모든 트래픽이 같은 병목으로 몰리거나 한 VC의 깊이가 부족하다면 개수만 늘린 효과는 작다. 논리적인 대기열의 수와 물리적인 전송 능력을 나누어 보면 필요한 구성이 보인다.