번갈아 보내는 라우터가 송신원마다 다른 몫을 주는 이유

두 송신원이 번갈아 전송하도록 만들면 공평해 보인다. 그런데 같은 방식의 중재기를 두 번 지나면, 맨 처음의 송신원들은 서로 다른 몫을 받을 수 있다. NoC fairness를 평가하려면 어느 위치에서 누구의 기회를 같게 만드는지 먼저 정해야 한다. 라우터 입력별 공평성과 최종 송신원별 공평성은 측정 단위부터 다르다.

두 번의 번갈아 보내기가 만든 비대칭

설명용 네트워크를 그려 보자. L0와 L1의 트래픽이 R0에서 합쳐져 A라는 경로가 된다. R1에서는 A와 현지 송신원 B가 하나의 출력 링크를 공유한다. 각 송신원에는 보낼 flit이 계속 있으며, 출력은 매 cycle 한 flit을 받고, 중재와 버퍼는 충분히 파이프라인화되어 있다고 가정한다.

R0는 L0와 L1을, R1은 A와 B를 round robin으로 번갈아 선택한다. R0의 순서는 실제로 A의 flit을 전달했을 때만 바뀐다고 하자. 정상 상태에서 R1의 출력은 L0, B, L1, B, L0, B, L1, B가 된다. 여덟 번의 전송 중 L0와 L1은 각각 두 번, B는 네 번이다. 두 중재기는 각자의 두 입력에 똑같은 기회를 줬지만, 송신원별 몫은 1/4, 1/4, 1/2가 됐다.

문제는 라우터가 round robin을 잘못 구현했다는 데 있지 않다. R1의 A 입력 안에 송신원이 둘이라는 정보가 없기 때문이다. 경로가 합쳐지는 횟수가 다르면 이런 효과가 누적될 수 있다. ‘모든 포트를 공평하게 중재했다’는 결과만으로 모든 송신원의 대역폭이 같다고 결론 내릴 수 없다.

같은 몫이라는 목표를 어디에 둘까

이 예에서 세 송신원에 같은 전송 수를 주고 싶다면 R1이 A를 두 번, B를 한 번 선택하도록 바꿀 수 있다. R0의 번갈아 보내기가 유지되면 L0, L1, B가 반복돼 각각 1/3을 얻는다. 이는 이 경로와 지속적인 세 수요를 아는 가상 가중치 정책이다. 트래픽이 바뀌어 L1이 쉬거나 다른 송신원이 A에 합류하면 같은 가중치가 같은 결과를 보장하지 않는다.

송신원마다 서비스 목표가 같다는 전제도 필요하다. 어떤 흐름에는 짧은 응답 지연을, 다른 흐름에는 최소 대역폭을 줄 수 있다. 이때 모든 몫을 같게 하는 것만으로 원하는 공평성을 정의하기 어렵다. 예약한 몫의 보장과 남는 용량의 재분배를 구분하면 정책의 결과를 읽기 쉽다.

전송 횟수의 단위도 중요하다. 한 패킷이 끝날 때까지 출력을 붙잡는 정책에서 10-flit 패킷과 1-flit 패킷을 번갈아 보내면 패킷 수는 같아도 전달한 데이터의 양은 10:1이다. 반대로 flit마다 번갈아 보내면 바이트 수는 가까워지지만, 긴 패킷이 끝나는 시점은 달라진다. 측정한 ‘같음’이 패킷 수인지 데이터 양인지 명시해야 한다.

신청했다는 이유만으로 순서를 넘기면 생기는 일

입력 중재와 출력 중재를 나눈 구조에서는 첫 단계의 승리가 실제 전송을 뜻하지 않는다. 첫 단계에서 L0를 골랐는데 두 번째 단계의 출력이 다른 입력에 넘어갔다면, L0는 아무 데이터도 보내지 못했다. 이때 첫 단계의 우선순위를 매번 넘기면 실제로 전달된 기회와 내부 순서가 어긋날 수 있다.

Mullins 등의 라우터 원문은 첫 단계의 round robin 상태를 두 번째 단계의 승리까지 확인한 뒤 갱신하여 이 문제를 피한다고 설명한다. 이 글의 R0도 같은 이유로 요청 발생이나 임시 선택이 아닌 실제 전달을 기준으로 순서를 넘겼다. 원문 PDF 4쪽, 2.5절

고정 우선순위를 쓰는 경우에는 더 직접적인 반례가 있다. A가 항상 준비돼 있고 A를 먼저 고르면 B도 계속 준비돼 있어도 선택되지 않는다. 출력은 바쁘게 일하며 높은 처리율을 기록할 수 있지만 B의 전달은 끝나지 않는다. 전체 처리량만 보는 계측으로는 이 굶주림을 발견하기 어렵다.

기다림의 상한에는 출력의 진행 조건이 들어간다

두 입력이 계속 준비된 flit 단위 round robin에서는 자기 차례 사이에 다른 입력의 성공한 전송이 한 번 들어간다. 그러나 이는 무조건 한 cycle만 기다린다는 보장이 아니다. 수신 credit이 없거나 출력이 막히면 성공한 전송 자체가 멈춘다. 패킷이 출력을 잠그는 구성에서는 다른 패킷의 남은 길이도 기다림에 들어간다.

따라서 유한한 시간 상한을 말하려면 downstream이 얼마 안에 다시 받을 수 있는지, 패킷 길이를 제한하는지, 여러 단계에서 어떤 서비스 보장이 합쳐지는지까지 필요하다. 순환 대기가 없다는 사실과 모든 요청이 정해진 시간 안에 끝난다는 사실은 서로 다른 조건을 요구한다.

NoC fairness의 출발점은 중재기 이름을 고르는 일이 아니다. 같은 기회를 줄 대상과 단위, 기회가 실제 소비된 순간을 정하는 일이다. 포트별 몫과 송신원별 몫을 함께 세고 가장 오래 기다린 요청을 확인하면, 네트워크가 바쁜 상태에서도 어떤 흐름이 뒤로 밀리는지 구체적으로 설명할 수 있다.