같은 평균 주입량이 네트워크를 다르게 막히게 하는 이유

평균 주입량이 같으면 네트워크도 비슷하게 바쁠까. 패킷의 목적지를 바꾸면 같은 총량이 몇 개의 링크에 몰릴 수 있고, 목적지를 그대로 두어도 한꺼번에 도착하면 버퍼가 차오른다. NoC traffic pattern은 입력 숫자에 붙는 장식이 아니라, 어떤 병목을 시험하는지 정하는 조건이다.

목적지를 바꾸면 필요한 용량이 달라진다

4×4 mesh에 각 라우터당 송신원과 수신기를 하나씩 둔 자체 모델을 사용하자. 모든 패킷은 한 flit이며, X 좌표를 먼저 맞추고 Y 좌표를 맞춘다. 방향별 링크와 각 수신 포트는 cycle당 한 flit을 받는다. 송신원마다 평균 λ flit/cycle을 생성하므로 네트워크 전체의 생성량은 16λ다.

첫 패턴은 모든 송신원이 16개 목적지를 같은 확률로 고르는 uniform이다. 자기 자신에게 보내는 경우도 포함하며 그 트래픽은 외부 링크를 거치지 않는다. 256개의 송신원-목적지 조합을 경로별로 세면 가장 많이 쓰는 방향 링크의 평균 부하는 λ이고, 각 수신기의 부하도 λ다.

두 번째 패턴에서는 (3,3)을 제외한 15개 송신원이 모두 (3,3)으로 보낸다. (3,3)의 송신원은 (0,0)으로 보내 총 생성량은 똑같이 유지한다. 이때 (3,3)의 수신 포트에는 15λ가 모인다. 마지막 수직 링크 (3,2)→(3,3)에는 아래쪽 세 행의 송신원 열두 개가 만든 12λ가 흐른다.

λ=0.1이면 uniform의 최대 링크 부하는 0.1이고 hotspot의 마지막 링크는 1.2다. 수신 포트에는 1.5가 모인다. 두 번째 경우는 cycle당 한 flit이라는 용량을 초과하므로 생성률을 그대로 계속 받아 처리할 수 없다. 수신 포트 기준의 필요 조건은 λ≤1/15, 해당 링크 기준은 λ≤1/12다. 이 부등식은 평균 용량의 필요 조건이며 그 이하에서 특정 지연이나 안정성을 보장하는 충분 조건은 아니다.

수신기가 균등해도 링크는 균등하지 않다

목적지를 (x,y)→(y,x)로 정하는 transpose도 생각해 보자. 이는 목적지가 한 번씩 나타나는 순열이라 각 수신 포트의 평균 부하는 λ다. 그러나 X 우선 경로를 전수 계산하면 가장 많이 쓰는 방향 링크의 부하는 3λ다. 예를 들어 (0,3), (1,3), (2,3)에서 각각 전치된 목적지로 가는 패킷들이 (2,3)→(3,3)을 공유한다.

같은 수신기 부하와 같은 전체 생성량만으로 링크의 혼잡을 판단하지 못하는 이유다. 패턴을 비교할 때는 생성량뿐 아니라 각 방향 링크의 부하와 가장 집중되는 출력도 함께 본다. 경로 선택을 바꿨다면 이 경로별 계산도 다시 해야 한다.

BookSim의 공식 traffic 구현에는 uniform과 transpose 등의 목적지 선택 규칙이 있다. uniform은 전체 노드에서 선택하므로 자기 자신도 후보에 포함된다. 이 글의 hotspot 목적지는 계산을 드러내기 위해 직접 정한 조건이며 특정 도구의 성능 측정 결과가 아니다. 공식 traffic.cpp

평균을 맞춰도 짧은 폭주가 남는다

목적지를 고정하고 하나의 출력 앞 대기열만 보자. 출력은 매 cycle 한 flit을 전송하고, 도착을 먼저 반영한 뒤 서비스한다고 정한다. 16cycle 동안 앞의 네 cycle에 각각 두 flit씩 도착하고 나머지 열두 cycle에는 도착하지 않으면 평균 도착률은 0.5다.

무한 대기열에서 서비스 뒤 남는 flit 수는 cycle 0부터 1, 2, 3, 4, 3, 2, 1, 0이 된다. cycle 3에 도착한 마지막 flit은 cycle 7에 전송돼 네 cycle을 기다린다. 같은 평균으로 두 cycle마다 한 flit씩 도착하면 이 서비스 규칙에서는 매번 즉시 처리되어 남는 대기가 없다.

세 flit까지 남겨 둘 수 있는 버퍼라면 첫 패턴의 최대 대기 네 개를 그대로 담지 못한다. 역압을 사용하는 네트워크에서는 이를 곧바로 패킷 손실이라고 부르지 않는다. 일부 flit의 도착이 상류에서 늦춰지고, 그곳에 대기와 지연이 생길 수 있다. 측정 지점을 수신 링크에만 두면 상류에서 기다린 시간을 놓친다.

시험 결과의 분모를 먼저 확인한다

BookSim은 기본 주입률을 packet/cycle로 해석하며 flit 기준으로 설정하는 옵션도 제공한다. 0.15packet/cycle에 패킷당 네 flit이면 제안한 데이터량은 0.6flit/cycle이다. 패킷 길이가 다른 시험에 0.15라는 숫자만 똑같이 넣으면 링크가 받아야 할 양은 같지 않다. burst를 만드는 on-off 과정도 목적지 패턴과 별도의 설정이다. 공식 매뉴얼의 Traffic와 Simulation parameters

생성한 양, 네트워크에 실제로 들어간 양, 전달된 양도 구별한다. 입력이 막혔는데 들어간 패킷만 세면 제안한 부하를 낮춰 읽을 수 있다. 지연을 입력 대기부터 셌는지, 네트워크 진입부터 셌는지 정하고, 초기 상태를 제외하는 warmup과 남은 패킷을 전달하는 구간도 명시한다.

NoC traffic pattern을 잘 고른다는 것은 원하는 수치가 나오는 입력을 찾는 일이 아니다. 실제로 겪을 목적지 집중, 경로 공유, 짧은 폭주를 시험에 담는 일이다. 평균 주입량과 함께 가장 바쁜 링크, 수신 포트, 상류 대기를 설명할 수 있으면 성능 결과가 어떤 작업에 적용되는지도 분명해진다.