라우터를 덜 거치는 길에 더 긴 전선이 필요한 이유

멀리 있는 라우터까지 여러 번 거치는 대신 한 번에 연결하면 패킷은 빨리 도착할까. flattened butterfly는 이 질문을 연결 구조로 풀어낸다. 라우터를 거치는 횟수는 줄일 수 있지만, 생략한 중간 구간의 배선 길이까지 사라지는 것은 아니다. 연결의 비용을 함께 세면 낮은 hop 수가 유리한 조건이 드러난다.

같은 행과 열을 직접 연결한다

2차원 구성에서는 같은 행의 라우터끼리, 같은 열의 라우터끼리 직접 연결한다. 4×4 라우터를 놓으면 각 라우터에는 같은 행의 다른 세 곳과 같은 열의 다른 세 곳으로 가는 네트워크 포트가 필요하다. 라우터당 하나의 로컬 노드를 붙인 자체 예에서는 네트워크 포트가 여섯, 로컬 포트까지 합친 radix가 일곱이다.

이 radix는 원문의 특정 구성과 구별해야 한다. Kim의 학위논문에 나온 16-router 예는 라우터마다 로컬 노드 네 개를 모아 64개 노드를 연결하므로 radix가 열이다. 직접 연결하는 차원별 포트 여섯 개에 로컬 포트 네 개가 더해진다. 원문 PDF 124–125쪽, 본문 104–105쪽

BookSim 구현도 차원마다 다른 좌표로 연결하고 radix를 로컬 포트 수에 (차원 크기−1)×차원 수를 더해 계산한다. 이 숫자를 일반 mesh의 네 방향 포트 수와 혼동하면 버퍼와 스위치 비용을 빠뜨린다. 공식 flatfly_onchip 구현

두 hop이지만 다섯 칸의 거리를 지나간다

라우터 사이의 간격을 한 단위로 두자. (0,0)에서 (3,2)까지 X 우선으로 가는 mesh 경로는 동쪽 세 번, 북쪽 두 번으로 다섯 hop이다. 같은 좌표의 flattened butterfly에서는 (0,0)→(3,0)→(3,2)로 두 hop이면 된다. 그런데 첫 배선 길이는 세 단위, 다음 배선 길이는 두 단위이므로 이동한 배선의 합은 여전히 다섯 단위다.

간단한 가상 지연 모델을 붙일 수 있다. 네트워크 hop마다 라우터 처리에 두 cycle, 배선 한 단위마다 한 cycle이 걸린다고 하자. mesh는 5×2+5=15cycle, 직접 연결 구조는 2×2+5=9cycle이다. 중간 라우터의 처리 비용을 줄이는 것이 이득이다.

높은 radix 때문에 직접 연결 라우터의 처리가 hop마다 다섯 cycle로 늘었다고 바꾸면 2×5+5=15cycle로 같아진다. 이 계산은 입력·출력 인터페이스, 직렬화, 혼잡을 제외한 자체 모델이며 실제 합성이나 배치 결과가 아니다. 긴 전선에 파이프라인을 넣으면 대역폭을 유지할 수 있어도 그 단계의 지연은 남는다. 원문도 배선과 라우터 hop을 구별하여 이 점을 설명한다.

짧은 경로를 만들기 위해 얼마나 연결했나

4×4 mesh의 수평 인접 쌍은 열두 개, 수직 인접 쌍도 열두 개다. 양방향을 각각 별도 채널로 세면 48개다. 직접 연결 구조에서는 16개 라우터마다 다른 라우터로 향하는 포트가 여섯 개라 96개의 방향 채널이 생긴다. 여기서는 로컬 노드의 연결을 제외했다.

배선의 길이까지 합쳐 보자. 한 행의 네 좌표 사이를 모두 연결하면 서로 다른 쌍의 거리 합은 1+2+3+1+2+1=10이다. 네 행과 네 열을 합치면 총 80단위다. mesh의 24개 인접 연결은 총 24단위다. 각 연결의 양방향을 한 쌍으로 세고 동일한 배선 폭을 가정한 기하학적 비교다. 실제 배선 층, 우회, 반복기와 대역폭 예산을 반영한 면적 추정은 아니다.

포트 증가도 무료가 아니다. 일곱 입력과 일곱 출력의 완전 crossbar에는 가능한 입력-출력 조합이 49개다. 로컬 포트를 포함한 mesh 내부 라우터의 다섯 포트에서는 25개다. 조합 수만으로 면적을 두 배라고 단정할 수는 없지만, 스위치와 중재기를 작은 radix와 같은 비용으로 취급하기 어렵다는 근거는 된다.

가까운 경로와 덜 막힌 경로를 구분한다

두 차원을 차례로 직접 연결하면 최소 hop 경로는 간결하다. 그러나 많은 송신원이 같은 연결을 요구하면 그 출력은 여전히 공유 자원이다. 다른 라우터를 거치는 우회가 부하를 나눌 수도 있고, 대신 hop과 이동 거리를 늘릴 수도 있다. 연결 구조가 풍부하다는 것과 라우팅이 그 자원을 잘 분배한다는 것은 별도로 확인한다.

flattened butterfly를 검토할 때는 줄인 라우터 통과 수, 늘어난 포트와 전체 배선 길이, 실제 혼잡을 같은 좌표계에서 비교하면 된다. 중간 라우터의 비용이 큰 환경에서는 직접 연결이 매력적이다. 높은 radix나 장거리 배선의 비용이 커지는 환경에서는 그 이득이 줄어든다. hop 수를 세는 데서 시작하되, 생략한 라우터 대신 무엇을 설치했는지까지 세어야 답을 얻을 수 있다.