X 좌표를 먼저 맞추는 경로가 대기 고리를 끊는 방법

4×4 mesh에서 (0,0)의 패킷을 (3,2)로 보내는 최단 경로는 하나가 아니다. 동쪽 세 번과 북쪽 두 번을 섞는 순서가 열 가지다. XY routing은 그중 X 방향을 먼저 끝내고 Y 방향을 이동하는 경로만 고른다. 이 단순한 제한이 왜 유용한지 보려면, 짧은 경로라는 사실과 자원 대기의 순서를 구별해야 한다.

목적 좌표 하나를 먼저 맞춘다

좌표의 X를 가로, Y를 세로로 정하고 래핑 없는 mesh를 사용하자. 현재 X가 목적 X보다 작으면 동쪽으로, 크면 서쪽으로 간다. X가 같아진 뒤에만 Y를 비교하여 북쪽이나 남쪽으로 이동한다. 한 패킷이 Y 단계에 들어간 뒤 X 단계로 되돌아가지는 않는다.

따라서 (0,0)→(3,2)의 경로는 (0,0)→(1,0)→(2,0)→(3,0)→(3,1)→(3,2)다. 반대 방향인 (3,2)→(0,0)은 서쪽 세 번 다음 남쪽 두 번이다. (1,3)→(1,0)은 X가 이미 같으므로 처음부터 남쪽으로만 간다. X 우선은 반드시 동쪽 우선이라는 뜻이 아니다.

BookSim의 dor_next_mesh 구현은 먼저 다른 낮은 차원 좌표를 찾고 그 좌표의 대소관계로 출력 방향을 결정한다. 2차원에서 낮은 차원을 X로 놓으면 위 규칙이 된다. 공식 구현의 dor_next_mesh와 dim_order_mesh

같은 차원에서도 자원 순위를 만든다

X를 먼저 끝낸다는 사실만으로 모든 네트워크의 고리가 없어지는 것은 아니다. 래핑 없는 mesh에서는 한 차원 안의 이동도 한 방향으로만 진행한다. 목적 X가 고정되어 있어 동쪽으로 갔다가 서쪽으로 돌아오지 않고, Y에서도 같은 조건이 성립한다.

4×4의 방향 있는 링크에 순위를 직접 붙여 보자. 출발 좌표가 (x,y)인 동쪽 링크의 순위는 x, 서쪽은 3−x로 정한다. 동쪽 링크를 연속해서 쓰면 0, 1, 2처럼 증가한다. 서쪽도 x가 3, 2, 1로 줄어드는 동안 순위는 0, 1, 2로 증가한다.

북쪽 링크에는 4+y, 남쪽 링크에는 4+(3−y)를 준다. 같은 방향의 Y 이동에서도 순위가 증가하고, 어떤 X 링크의 순위 0–2에서 어떤 Y 링크의 순위 4–6으로 전환할 때도 증가한다. 서로 다른 위치의 링크가 같은 순위여도 괜찮다. 한 패킷의 허용된 연속 자원 전이에서 순위가 엄격히 증가하는지가 중요하다.

이 예의 경로 의존 관계는 작은 순위에서 큰 순위로만 이어진다. 원래 자원으로 되돌아오는 대기 고리를 만들려면 순위도 돌아와야 하므로 불가능하다. 결정적인 경로에서 이러한 자원 순서를 쓰는 근거는 Dally와 Seitz의 원문에 제시된다. 원문 PDF 2–3쪽

최단 경로여도 병목은 공유한다

첫 예의 이동 횟수는 |3−0|+|2−0| = 5다. 동쪽 세 번과 북쪽 두 번을 섞는 최단 경로의 수는 5!/(3!·2!) = 10이지만 XY는 그중 하나로 제한한다. 홉 수를 늘리지 않으면서 경로 선택의 자유를 줄인 것이다.

두 송신지가 같은 목적지 (3,2)로 데이터를 보낸다고 하자. (0,0)에서 온 흐름은 X를 마친 뒤 (3,0)에서 북쪽으로 이동한다. (0,1)에서 온 흐름은 (3,1)에서 북쪽으로 이동한다. 둘은 (3,1)→(3,2) 링크를 공유한다.

그 링크가 한 flit/cycle을 보내고 두 흐름이 각각 평균 0.7 flit/cycle을 계속 요구한다면 합계 1.4다. 병목의 용량보다 0.4 flit/cycle 많다. 유한 버퍼는 차고 송신은 결국 압력을 받는다. 대기 고리가 없는 경로라도 지속적인 과부하를 모두 처리할 수는 없다. 경로의 안전성과 처리량은 서로 다른 계산이다.

경로 제한의 전제는 실제 배선이다

맨 오른쪽에서 왼쪽으로 연결되는 래핑 링크를 추가하면 한 방향의 이동만으로도 원을 만들 수 있다. 같은 X 우선 규칙을 torus에 그대로 쓰고 위의 순위 증명을 가져오지 못한다. 순위를 끊는 추가 자원이나 다른 경로 규칙이 필요하다.

고장 링크를 피해 돌아가는 기능도 허용 전이를 바꾼다. Y 이동 후 X로 돌아오는 우회를 새로 허용하면 본래 XY의 증명을 다시 검토해야 한다. 목적지가 계속 수신을 거절하거나 특정 입력이 중재에서 영원히 선택되지 않는 문제도 이 순위만으로 해결하지 않는다.

XY routing을 고를 이유는 단순한 좌표 비교로 최단 경로를 정하면서, 래핑 없는 mesh의 자원 전이에 일관된 순서를 부여할 수 있다는 데 있다. 경로 추적과 순위 검증으로 그 성질을 확인한 뒤에는 실제 트래픽이 어디에 몰리는지 따로 계산한다. 단순한 경로가 제공하는 보장과 포기한 경로 선택을 함께 보면 이 규칙을 적용할 위치를 판단할 수 있다.