돌아가는 포인터도 불공평할 수 있다: 라운드로빈 중재

우선순위 포인터가 매 사이클 돌아가니 요청도 공평하게 처리될 것 같다. 그런데 하류가 두 사이클에 한 번만 받자 한 요청자가 영원히 기다린다. 라운드로빈 중재의 공정성은 포인터가 돌아가는 모습이 아니라, 실제 수락된 거래 뒤에 다음 기회를 누구에게 주는가로 결정된다.

라운드로빈은 요청자들을 순환 순서로 살펴보는 중재 방식이다. 여기서는 요청자가 0, 1, 2이고 각 거래가 한 항목이라고 정한다. 요청을 제시한 쪽은 수락 전까지 요청과 데이터를 유지한다. 출력은 valid와 ready가 함께 높은 에지에 하나의 항목을 받는다. 아래는 이 규칙을 분석하기 위한 가상의 알고리즘과 추적이다.

선택한 것과 처리한 것은 다르다

현재 시작 인덱스가 p라면 p, p+1, p+2의 순환 순서에서 첫 번째 활성 요청을 winner로 선택하자. winner가 실제로 수락되었을 때만 시작점을 그 다음 요청자로 옮긴다.

always_ff @(posedge clk or negedge rst_n) begin
  if (!rst_n)
    start_index <= 2'd0;
  else if (fire) begin
    if (winner == 2'd2)
      start_index <= 2'd0;
    else
      start_index <= winner + 2'd1;
  end
end

여기서 fire는 선택한 요청이 존재하고 하류가 수락한 사건이다. winner를 계산하는 선택 회로는 생략했다. 모두 계속 요청하고 매 에지 수락된다면 0→1→2→0의 순서가 반복된다. 하류가 막히면 아직 아무도 처리하지 않았으므로 start_index도 그 자리에서 기다린다.

그 대신 매 클록에 포인터를 움직이는 두 요청자 버전을 생각하자. p는 에지 0에 0, 에지 1에 1, 에지 2에 0으로 번갈아 바뀐다. 하류가 짝수 에지에만 ready=1이라면 실제로 수락되는 것은 계속 요청자 0이다. 요청자 1은 선택되는 에지가 있지만 항상 ready=0이어서 수락되지 않는다.

포인터의 회전 횟수는 같아도 서비스 횟수는 같지 않다. 올바른 두 요청자 버전은 에지 0에 0을 수락한 뒤 p=1로 옮기고, 에지 1이 막히면 그대로 유지한다. 에지 2에는 1을 수락한다. 기회의 갱신을 클록과 연결할지 수락과 연결할지가 공정성의 차이를 만든다.

대기 시간의 상한은 어떤 단위인가

세 요청자가 모두 계속 요청하고, 위 순환 탐색과 수락 뒤 갱신을 지킨다면 어떤 요청자는 자기 수락 전에 다른 요청자의 성공한 거래를 최대 두 번 기다린다. 요청이 계속 유지되는 동안 세 번째 다른 거래가 먼저 지나갈 수는 없다. 순환 순서가 그 요청을 만나기 때문이다.

이 상한은 클록 사이클 수가 아니다. 하류가 100사이클 멈추면 해당 요청도 100사이클 더 기다린다. 하류가 영원히 멈추면 누구도 완료되지 않는다. 중재기의 공정성과 환경의 진행 보장을 합쳐야 시간의 상한을 말할 수 있다.

요청이 수락 전에 사라지는 경우도 다르다. 계속 기다린다는 전제가 깨졌으므로 “언젠가 반드시 수락된다”는 결론을 그대로 적용할 수 없다. 짧은 펄스 요청을 쓰는 인터페이스라면 중재기 앞에 저장이 필요하거나, 놓쳤을 때 재시도한다는 계약이 있어야 한다.

비어 있는 요청자를 넘기는 방식도 영향을 준다

일부 요청자만 활성인 경우에는 시작 인덱스를 무조건 하나씩 증가시키는 방식과, 다음 활성 요청으로 이동하는 방식의 처리 비율이 달라질 수 있다. 같은 라운드로빈이라는 이름 아래에서도 빈 요청자를 어떻게 넘기는지와 선택 구조가 구현마다 다르다.

PULP의 라운드로빈 중재기는 활성 요청이 일부일 때 처리 비율을 고르게 하는 FairArb 옵션과, 수락이 지연될 때 선택을 유지하는 LockIn 옵션을 따로 둔다. 실제 코드에서 내부 우선순위 갱신도 출력의 요청과 수락 조건을 사용한다. 이름만 보고 기본 설정의 모든 공정성·안정성 규칙을 추측해서는 안 되는 이유다.

이 글의 순환 탐색 알고리즘은 원문의 트리 회로를 그대로 복사한 것이 아니다. 공정성을 설명하기 위해 시작점 다음의 첫 활성 요청을 선택하도록 명시한 모델이다. 다른 선택 규칙을 쓰는 중재기에는 그 규칙에 맞는 상한과 비율 분석이 필요하다.

거래가 같아도 사용한 자원은 다를 수 있다

0과 1이 번갈아 한 거래씩 처리된다고 하자. 0의 거래는 64바이트이고 1은 8바이트라면 거래 횟수는 같아도 byte 단위 사용량은 8배 다르다. 라운드로빈의 공정성 단위가 “거래 한 번”이었기 때문이다. 같은 원리로 하나의 요청이 긴 burst를 독점하면 다른 요청자의 시간 대기가 길어질 수 있다.

원하는 기준이 byte 수, 점유 시간 또는 서비스 비율이라면 단순 거래 순환만으로 충분하지 않을 수 있다. 우선 어떤 사건이 한 번의 서비스를 끝내는지 정해야 한다. 여러 beat로 구성된 거래 전체를 하나로 세는 중재와, beat마다 다시 선택하는 중재는 다른 인터페이스다.

출력의 데이터 유지도 공정성과 따로 확인해야 한다. 아직 수락되지 않은 winner를 새 요청 때문에 바꾸면, 지속 제시를 기대하는 소비자에게 payload가 바뀔 수 있다. 그런 계약에서는 winner를 잠가 수락까지 유지해야 한다. 포인터만 유지하는 것이 선택 데이터의 안정성을 항상 보장하지는 않는다.

증명할 때 환경을 편하게 만들면 놓치는 것

형식 검증으로 starvation 부재를 확인한다면 요청이 지속되는 조건과 하류가 언젠가 수락한다는 조건을 분리해야 한다. 하류 ready를 항상 1로 가정하면 앞의 짝수 에지 반례를 볼 수 없다. 너무 강한 가정은 검사하려는 현상을 없앤다.

SymbiYosys의 빠른 시작 문서는 assume과 assert, 반례 추적을 사용하는 기본 흐름을 설명한다. 중재기에 적용할 때에는 “한 번에 한 요청만 수락한다”는 안전성부터, “지속 요청이 다른 성공한 거래를 몇 번 기다리는가”라는 진행 조건까지 구분해 표현하는 편이 좋다.

처음의 회전 포인터는 시각적으로 공평했지만, 서비스 기회가 오는 에지와 잘못 맞물렸다. 라운드로빈 중재를 평가할 때에는 수락 이후 갱신, 지속 요청, 하류 진행, 서비스 단위를 함께 확인해야 한다. 이 네 조건이 명확해야 순환이라는 이름이 실제로 기다림의 끝을 보장할 수 있다.