Q-StaR: A Quasi-Static Routing Scheme for NoCs

이 논문은 NoC 의 런타임 부하 분포를 인식하지 못하는 정적 라우팅의 한계를 극복하기 위해 토폴로지와 트래픽 분포를 기반으로 장기적 부하 추세를 추출하는 N-Rank 를 도입하여 BiDOR 의 라우팅을 안내함으로써 부하 균형을 개선하면서도 단순성과 예측 가능성을 유지하는 Q-StaR 을 제안하고, 이를 통해 기존 차순서 라우팅 대비 처리량과 지연 시간을 획기적으로 향상시켰음을 보여줍니다.

핵심

칩 속의 교통 체증 해결사: Q-StaR 이야기

현대 컴퓨터 칩 (SoC) 은 마치 거대한 도시처럼 수많은 부품들이 서로 데이터를 주고받습니다. 이 부품들을 연결하는 도로망이 바로 NoC(Network-on-Chip, 칩 내 네트워크)입니다. 하지만 이 도시에는 항상 교통 체증이라는 문제가 존재합니다.

이 논문은 이 교통 체증을 해결하기 위해, **"예측 가능한 미래"**를 활용하는 새로운 지능형 교통 시스템인 Q-StaR을 제안합니다.

---

1. 기존의 문제: "무조건 직진" vs "실시간 내비게이션"

지금까지 칩 설계자들은 데이터를 보낼 때 두 가지 방식 중 하나를 선택했습니다.

• 방식 A: 무조건 직진 (DOR, 정적 라우팅)

  • 비유: "동네 길은 항상 똑같으니, A 에서 B 로 가려면 무조건 '동쪽 → 남쪽'으로만 가라"라고 정해진 규칙만 따르는 것.
  • 장점: 매우 간단하고, 데이터가 순서대로 도착하며, 사고 (데드락) 가 날 확률이 거의 없습니다.
  • 단점: 만약 동쪽 길이 막혀있어도 모르고 계속 그쪽으로 보냅니다. 결국 특정 도로만 꽉 막히고 (부하 불균형), 전체 교통 흐름이 느려집니다.

• 방식 B: 실시간 내비게이션 (적응형 라우팅)

  • 비유: "지금 길이 막히니 우회하자"라고 실시간으로 교통 정보를 수집해서 경로를 바꿉니다.
  • 장점: 막힌 길을 피해서 효율이 좋습니다.
  • 단점: 실시간 정보를 수집하고 계산하는 데 너무 많은 전력이 들고, 복잡해집니다. 또, 경로를 자주 바꾸다 보니 데이터가 뒤죽박죽 섞여 도착하는 (순서 불일치) 문제가 생길 수 있습니다.

결국 딜레마: "간단하고 안전한가?" 아니면 "복잡하지만 효율적인가?" 사이에서 선택해야 했습니다.

---

2. Q-StaR 의 아이디어: "미래를 읽는 예지력"

Q-StaR 은 이 딜레마를 해결하기 위해 제 3 의 길을 찾았습니다.
"실시간으로 교통 상황을 보는 건 너무 비싸고 복잡하니까, '미래의 교통 흐름'을 미리 예측해서 경로를 정하자!"

그들은 교통 체증이 무작위로 발생하는 게 아니라, 두 가지 요인에 의해 결정된다는 사실을 발견했습니다.

1. 도시의 구조 (토폴로지): 중앙에 있는 교차로가 항상 붐비기 마련입니다.
2. 차량의 목적지 (트래픽 분포): 어떤 업무가 실행되면, 어떤 데이터가 어디로 가는지 패턴이 있습니다.

이 두 가지를 알면, **"어떤 길이 나중에 막힐지"**를 미리 알 수 있습니다.

---

3. Q-StaR 의 작동 원리: 두 명의 전문가

Q-StaR 은 두 명의 전문가 팀으로 구성되어 있습니다.

① N-Rank (예측 분석가)

• 역할: 칩의 구조와 데이터가 어디로 갈지 (업무 패턴) 를 분석합니다.
• 작동: 마치 **"진화 시뮬레이션"**을 돌리는 것처럼, 가상의 데이터를 칩 위에서 움직이게 합니다.
  • "이 교차로를 지나는 데이터가 많겠구나."
  • "저기 구석진 곳은 한적하겠구나."
• 결과: 각 교차로 (노드) 에 **'부하 점수 (wNR)'**를 매깁니다. 점수가 높으면 나중에 막힐 확률이 높은 '위험 구역'입니다.
• 특징: 이 분석은 칩이 작동하기 **전 (오프라인)**에 미리 끝냅니다. 그래서 실시간으로 계산할 필요가 없습니다.

② BiDOR (현실의 지휘자)

• 역할: 데이터를 보낼 때, N-Rank 가 미리 준 '부하 점수'를 보고 경로를 선택합니다.
• 작동: A 에서 B 로 가려면 보통 두 가지 길이 있습니다 (예: 동쪽→남쪽 vs 남쪽→동쪽).
  • "동쪽→남쪽 길의 총 부하 점수는 10 점."
  • "남쪽→동쪽 길의 총 부하 점수는 5 점."
  • 결정: "그럼 점수가 낮은 (막힐 확률이 낮은) '남쪽→동쪽' 길로 가자!"
• 특징: 이 결정은 미리 계산해둔 **지도 (비트맵)**를 보고 1 초 만에 내립니다. 실시간으로 교통 상황을 확인하지 않아도, 미리 예측한 지도대로만 가면 됩니다.

---

4. 왜 Q-StaR 이 훌륭할까요?

Q-StaR 은 **"간단함"**과 **"효율"**이라는 두 마리 토끼를 모두 잡았습니다.

1. 간단함 (Static 의 장점): 실시간으로 교통 상황을 확인하는 복잡한 장치가 필요 없습니다. 미리 계산된 지도만 보면 되므로, 칩이 매우 가볍고 빠릅니다.
2. 효율 (Dynamic 의 장점): 막힐 길을 미리 피해가므로, 교통 체증이 심한 상황에서도 데이터를 원활하게 보냅니다.
3. 안전함: 데이터가 뒤죽박죽 섞여 도착하는 문제를 방지합니다. (경로를 자주 바꾸지 않기 때문)

5. 실제 성과: 얼마나 좋을까요?

실험 결과, Q-StaR 은 기존 방식보다 압도적으로 좋았습니다.

• 처리량 (Throughput): 기존 방식보다 42.9% 더 많은 데이터를 보낼 수 있었습니다. (도로가 더 넓어진 효과)
• 지연 시간 (Latency): 데이터가 도착하는 데 걸리는 시간이 최대 95% 이상 줄어들었습니다. (정체가 사라진 효과)

요약

Q-StaR 은 **"실시간 내비게이션의 복잡함 없이, 미리 예측한 지도의 효율성"**을 갖춘 혁신적인 시스템입니다.

마치 **"평소 출퇴근길에 어떤 길이 막히는지 알고 있는 베테랑 운전사"**가, 복잡한 실시간 교통 정보를 보지 않아도 미리 계산된 최적의 길로 운전하듯, 칩 안의 데이터도 막히기 전에 미리 피해서 보내는 것입니다. 이로 인해 칩은 더 빠르고, 더 안정적으로 작동하게 됩니다.

기술 요약

Q-StaR: NoC 를 위한 준정적 (Quasi-Static) 라우팅 scheme

1. 문제 정의 (Problem)

시스템 온 칩 (SoC) 의 내부 통신 백본인 네트워크 온 칩 (NoC) 에서 라우팅 알고리즘 설계는 다음과 같은 딜레마에 직면해 있습니다.

• 정적 라우팅 (Deterministic Routing, 예: DOR/XY 라우팅): 하드웨어 비용이 낮고, 예측 가능하며, 데드락 (Deadlock) 이 없으며 순차적 전송을 보장한다는 장점이 있습니다. 하지만 런타임의 트래픽 부하 분포를 인지하지 못하여, 특정 노드에 부하가 집중되는 부하 불균형 (Load Imbalance) 을 초래하고 성능이 저하될 수 있습니다.
• 동적 라우팅 (Adaptive Routing): 런타임 부하 정보를 모니터링하여 경로를 동적으로 변경하므로 부하 분산에 효과적입니다. 하지만 런타임 정보 수집의 복잡성, 제어 로직의 과부하, 데드락 해결을 위한 추가 메커니즘 필요, 그리고 순서 외 전송 (Out-of-order) 으로 인한 재정렬 오버헤드 등의 단점이 있어 온칩 환경에서의 배포가 어렵습니다.

핵심 문제: NoC 라우팅은 단순성과 예측 가능성 (정적) 을 유지하면서도, 런타임 부하 분산 (동적) 을 효과적으로 수행할 수 있는 중간 지점이 필요합니다.

2. 방법론 (Methodology)

저자들은 NoC 의 부하 분산이 완전히 예측 불가능한 것이 아니라, 토폴로지 (Topology) 와 트래픽 분포 (Traffic Distribution) 라는 두 가지 요인에 의해 장기적인 추세가 결정된다는 통찰을 바탕으로 Q-StaR을 제안했습니다. 이 두 요소는 런타임에 실시간으로 수집할 필요 없이 설계 단계나 워크로드 패턴 분석을 통해 미리 알 수 있는 '준동적 (Quasi-dynamic)' 정보입니다.

Q-StaR 은 크게 두 가지 구성 요소로 이루어집니다.

A. N-Rank (Load Trend Extraction)

• 목적: 토폴로지 구조와 트래픽 매트릭스를 기반으로 각 노드가 런타임에 고부하를 겪을 확률을 예측합니다.
• 작동 원리:
  • 진화 모델 (Evolutionary Model): 네트워크 트래픽의 수명 주기를 모방합니다. 각 노드에 초기 트래픽을 주입하고, 토폴로지를 따라 트래픽이 이동 (Transfer) 하거나 네트워크에서 배출 (Drain) 되는 과정을 시뮬레이션합니다.
  • 확률 계산: 트래픽이 특정 링크를 통과할 확률 ($p_{u,n}$) 과 해당 링크를 통과한 후 목적지에 도달하여 배출될 확률 ($p^{drn}_{u,n}$) 을 계산합니다. 이때 '우회 (Detour) 하지 않는다'는 가정을 기반으로 최소 직사각형 (Minimum Rectangle) 내의 경로만 고려합니다.
  • N-Rank 가중치 ($w^{NR}$): 시뮬레이션이 수렴할 때까지 각 노드가 누적한 트래픽 양을 기반으로 $w^{NR}$ 값을 산출합니다. 이 값은 해당 노드가 런타임에 얼마나 많은 부하를 받을지 나타내는 지표가 됩니다.

B. BiDOR (Bi-directional Dimension-Order Routing)

• 목적: N-Rank 가 제공하는 $w^{NR}$ 정보를 활용하여 라우팅 경로를 선택합니다.
• 작동 원리:
  • 각 소스 - 목적지 쌍에 대해 두 가지 차수 순서 라우팅 (XY 라우팅과 YX 라우팅) 을 비교합니다.
  • 두 경로 상의 모든 노드의 $w^{NR}$ 합을 계산하여, 누적 가중치가 더 낮은 경로를 선택합니다.
  • 오프라인 계산 및 비트맵 (Bitmap) 저장: $w^{NR}$ 값은 오프라인에서 계산되므로, 런타임에 경로를 결정하기 위해 각 노드마다 목적지별 경로 선택 (XY 또는 YX) 을 나타내는 비트맵을 하드코딩합니다.
  • 가상 채널 (VC) 분리: XY 라우팅 패킷과 YX 라우팅 패킷을 별도의 가상 채널 (VC0, VC1) 로 분리하여 데드락을 방지하고, 순차적 전송을 보장합니다.

3. 주요 기여 (Key Contributions)

1. 준정적 (Quasi-Static) 패러다임 제안: 런타임 동적 정보 수집 없이, 토폴로지와 트래픽 패턴이라는 '준동적' 정보를 활용하여 정적 라우팅의 장점 (단순성, 예측 가능성) 과 동적 라우팅의 장점 (부하 분산) 을 결합했습니다.
2. N-Rank 알고리즘: 진화 모델을 통해 토폴로지와 트래픽 매트릭스에서 장기적인 부하 추세를 정밀하게 추출하는 새로운 메커니즘을 고안했습니다.
3. BiDOR 구현: N-Rank 정보를 기반으로 XY/YX 중 최적 경로를 선택하는 경량 라우팅 알고리즘을 설계하여, 오프라인 비트맵을 통해 런타임 오버헤드를 최소화했습니다.
4. 순차적 전송 보장: 동적 라우팅의 단점인 순서 외 전송 (Out-of-order) 문제를 해결하여 재정렬 오버헤드를 제거했습니다.

4. 실험 결과 (Results)

BookSim2 시뮬레이터에서 5x5 2DMesh 토폴로지를 기반으로 다양한 트래픽 패턴 (균일, 셔플, 순열, 뒤집기 등) 과 실제 워크로드 (Blackscholes 등) 를 사용하여 평가했습니다.

• 부하 균형 (Load Balance):
  • N-Rank 는 런타임 부하 추세를 정확하게 예측하여 BiDOR 이 부하를 효과적으로 분산하도록 유도했습니다.
  • 부하 불균형 계수 (LCV) 가 기존 결정적 라우팅 (XY) 및 무관심 라우팅 (Oblivious) 보다 현저히 낮았습니다.
• 처리량 (Throughput):
  • 균일 트래픽 (Uniform Traffic) 조건에서 기존 XY 라우팅 대비 42.9% 높은 처리량을 달성했습니다.
• 지연 시간 (Latency):
  • 실제 워크로드 조건에서 평균 지연 시간은 86.4%, 최대 지연 시간은 95.3% 감소했습니다.
• 오버헤드:
  • 동적 라우팅 (Odd-Even 등) 은 부하가 높은 환경에서 순서 외 전송으로 인한 재정렬 오버헤드가 발생했으나, Q-StaR 은 이를 완전히 제거했습니다.
  • 하드웨어 오버헤드는 XY 라우팅 대비 가상 채널 1 개 추가와 비트맵 조회만 필요하여 매우 경량화되었습니다.

5. 의의 및 결론 (Significance)

Q-StaR 은 NoC 라우팅 설계에서 오랫동안 존재해 온 '단순성 vs 부하 분산'의 딜레마를 해결하는 획기적인 접근법입니다. 런타임의 복잡한 상태 모니터링 없이도, 시스템의 구조적 특성과 워크로드 패턴을 사전에 분석하여 라우팅을 최적화함으로써, 동적 라우팅에 버금가는 성능을 유지하면서도 정적 라우팅의 예측 가능성과 낮은 오버헤드를 유지할 수 있음을 입증했습니다. 이는 고성능 컴퓨팅, 데이터센터 스위치, 그리고 다양한 SoC 환경에서 효율적인 NoC 설계를 위한 강력한 대안이 될 것입니다.