---
title: "X 좌표를 먼저 맞추는 경로가 대기 고리를 끊는 방법"
author: "브레이브브라우저쓰자"
published_at: "2026-10-29T01:47:04.257Z"
updated_at: "2026-10-06T02:58:03.792Z"
tags: ["xy routing"]
canonical_url: "https://ariser.io/@writer_a9817d5a8de0/x-%EC%A2%8C%ED%91%9C%EB%A5%BC-%EB%A8%BC%EC%A0%80-%EB%A7%9E%EC%B6%94%EB%8A%94-%EA%B2%BD%EB%A1%9C%EA%B0%80-%EB%8C%80%EA%B8%B0-%EA%B3%A0%EB%A6%AC%EB%A5%BC-%EB%81%8A%EB%8A%94-%EB%B0%A9%EB%B2%95"
ai_assisted: true
---

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

이 글은 AI가 활용됐습니다.

[원문](https://ariser.io/@writer_a9817d5a8de0/x-%EC%A2%8C%ED%91%9C%EB%A5%BC-%EB%A8%BC%EC%A0%80-%EB%A7%9E%EC%B6%94%EB%8A%94-%EA%B2%BD%EB%A1%9C%EA%B0%80-%EB%8C%80%EA%B8%B0-%EA%B3%A0%EB%A6%AC%EB%A5%BC-%EB%81%8A%EB%8A%94-%EB%B0%A9%EB%B2%95)

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](https://github.com/booksim/booksim2/blob/master/src/routefunc.cpp)

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

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쪽](https://comp.anu.edu.au/courses/comp4300/assets/lectures/refs/dallyDeadlockAvoid87.pdf)

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

첫 예의 이동 횟수는 |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의 자원 전이에 일관된 순서를 부여할 수 있다는 데 있다. 경로 추적과 순위 검증으로 그 성질을 확인한 뒤에는 실제 트래픽이 어디에 몰리는지 따로 계산한다. 단순한 경로가 제공하는 보장과 포기한 경로 선택을 함께 보면 이 규칙을 적용할 위치를 판단할 수 있다.