NoC 설계를 위한 Queuing Theory
Queuing Theory for Network-on-Chip Design
작성일: 2026-03-14 | 출처: Principles and Practices of Interconnection Networks
1. 왜 Queuing Theory이 필요한가?
NoC에서 Packet은 대부분의 시간을 Queue에서 대기합니다:
Queuing Theory으로 Packet이 각 Queue에서 대기하는 평균 시간을 예측할 수 있습니다.
2. 기본 Queuing 시스템 Model
핵심 변수 정의
| 기호 | 의미 | NoC에서의 대응 | 단위 |
|---|---|---|---|
| λ (lambda) | 도착률 | 입력 터미널 트래픽, Channel 트래픽 | packets/sec |
| μ (mu) | 처리율 (= 1/T) | Channel 대역폭 / Packet 길이 | packets/sec |
| T | 서비스 시간 (Service Time) | Packet 전송 시간 = L/b | seconds |
| ρ (rho) | 이용률/부하 | ρ = λ/μ = λT | 0 ~ 1 |
| L | Packet 길이 | bits per packet | bits |
| b | 대역폭 | Channel bandwidth | bits/sec |
T = L/b (Packet 길이 / 대역폭)
μ = 1/T = bL
3. Littles Law (리틀의 법칙)
Queue의 평균 대기 Packet 수와 대기 시간 (Waiting Time)의 관계를 나타냅니다.
L = λ × W
또는 NoC 표기로: E(N_Q) = λ × E(T_W)
| 기호 | 의미 | 설명 |
|---|---|---|
| L 또는 E(N_Q) | 시스템 내 평균 Packet 수 | 큐에 대기 중인 평균 Packet 개수 |
| λ | 도착률 | 초당 도착하는 Packet 수 |
| W 또는 E(T_W) | 평균 대기 시간 (Waiting Time) | Packet이 시스템에서 보내는 평균 시간 |
직관적 이해
도착률이 높으면
큐에 더 많은 Packet이 쌓임
️ 서비스 시간 (Service Time)이 길면
큐에 더 많은 Packet이 쌓임
E(T_W) = E(T) × E(N_Q) = (T × ρ)/(1-ρ)
4. M/M/1 Queue Model
Kendall 표기법
M/M/1 Queue의 핵심 공식들
p_i = (1-ρ) × ρ^i
E(N_Q) = ρ/(1-ρ)
E(T_W) = (T × ρ)/(1-ρ) = ρ/[μ(1-ρ)]
E(^2_N_Q) = ρ(1-ρ)^2
그래프 특성
ρ 1 (포화점)에 가까워지면 대기 시간 (Waiting Time)이 급격히 증가합니다!
ρ ≥ 1이면 공식이 무효가 됩니다 (무한 지연).
5. M/D/1 Queue Model
D = Deterministic (결정적 서비스 시간 (Service Time))
Packet 길이가 고정인 경우 (NoC에서 일반적인 상황)
E(N_Q) = ρ/[2(1-ρ)]
M/M/1 vs M/D/1 비교
M/M/1
서비스 시간 (Service Time): 지수분포 (가변)
평균 Queue 길이: ρ/(1-ρ)
M/D/1
서비스 시간 (Service Time): 결정적 (고정)
평균 Queue 길이: ρ/[2(1-ρ)]
Packet 길이가 일정하면 Queue 대기가 절반으로 줄어듭니다!
NoC에서는 보통 Packet 길이가 고정이므로 M/D/1 Model을 선호합니다.
6. M/G/1 Queue Model (일반화)
G = General (임의 분포)
일반적인 서비스 시간 (Service Time) 분포를 가정
E(N_Q) = λ^2 X^22(1-ρ)
여기서 X^2 는 서비스 시간 (Service Time)의 2차 모멘트 (second moment)
| Model | 서비스 시간 (Service Time) 분포 | 평균 Queue 길이 | 사용 상황 |
|---|---|---|---|
| M/M/1 | 지수분포 | ρ/(1-ρ) | 가변 Packet 길이 |
| M/D/1 | 결정적 | ρ/[2(1-ρ)] | 고정 Packet 길이 (NoC) |
| M/G/1 | 일반 분포 | λ^2 X^22(1-ρ) | 임의의 Packet 분포 |
7. NoC 성능 분석에 적용
7.1 Network를 Queuing 시스템으로 Model링
7.2 Switch Model링
7.3 다단계 Network 지연 계산
Tc = λ2μc(μc λ) + λ2μ(μ λ)
1단계 Queue 대기 + 2단계 Queue 대기
8. 주요 성능 지표
8.1 Throughput (Throughput)
- 용량 대비 비율로 표현 (0 ~ 1)
- 포화점 (Saturation): Throughput이 더 이상 증가하지 않는 지점
8.2 지연 (Latency)
| 구성요소 | 설명 |
|---|---|
| Zero-load Latency | 트래픽 없을 때 기본 지연 |
| Contention Latency | 경합으로 인한 추가 지연 |
8.3 이용률 (Utilization)
9. 포아송 프로세스의 특성
분할 (Splitting)
λ rate 스트림 λ₁ + λ₂ (합 = λ)
결합 (Combining)
λ₁ + λ₂ 스트림 λ (= λ₁ + λ₂)
포아송 프로세스는 분할/결합해도 포아송 유지! 해석이 쉬움
10. 확률적 분석 (Probabilistic Analysis)
Buffer 없는 Switch의 대기 시간 (Waiting Time)
| 항목 | 공식 | 설명 |
|---|---|---|
| 충돌 확률 | P_w = λ T_o2 = ρ_o2 | 출력 포트가 사용 중일 확률 |
| 충돌 시 대기 시간 (Waiting Time) (결정적) | T_wc = T_o2 | 평균 절반 대기 |
| 평균 대기 시간 (Waiting Time) | T_w = P_w × T_wc = λ T_o^24 | 확률 × 대기 시간 (Waiting Time) |
서비스 시간 (Service Time) 분산의 영향
| 서비스 시간 (Service Time) 분포 | 충돌 시 대기 시간 (Waiting Time) | 비고 |
|---|---|---|
| 결정적 (Deterministic) | T_o / 2 | NoC에서 일반적 |
| 지수분포 (Exponential) | T_o | 2배 더 길어짐 |
분산이 클수록 대기 시간 (Waiting Time)이 증가합니다 (긴 서비스에 더 자주 충돌)
11. NoC vs Queuing Theory 용어 비교
| Queuing Theory | NoC 용어 | 설명 |
|---|---|---|
| Arrival rate (λ) | Injection rate, Traffic rate | Packet 도착률 |
| Service rate (μ) | Channel bandwidth / Packet length | 처리 속도 |
| Utilization (ρ) | Channel load, Link utilization | Channel 사용률 |
| Queue | Input buffer, FIFO | 대기열 |
| Server | Channel, Link | 처리 주체 |
| Service time (T) | Transmission time, Serialization delay | 서비스 시간 (Service Time) |
| Waiting time | Contention delay, Queuing delay | 대기 시간 (Waiting Time) |
12. 트래픽 패턴 분포 Model
확률 분포 (NoC 트래픽 Model링)
| 분포 | 설명 | 용도 |
|---|---|---|
| Gaussian | 정규분포 | 집계된 Throughput |
| Exponential | 지수분포, 빠른 감쇠 | 지연 시퀀스, 도착 간격 |
| Gamma | 지수~가우시안 중간 | 일반적 분포 |
| Lognormal | 비대칭 분포 | 버스트 트래픽 |
| Pareto | Heavy-tailed, 느린 감쇠 | 자기유사 트래픽 |
공분산 함수 (시간 상관관계)
| Model | 설명 | 특성 |
|---|---|---|
| IID | 독립 동일 분포 | 메모리 없음 |
| ARMA | Auto-Regressive Moving Average | 단거리 종속성 |
| FGN | Fractional Gaussian Noise | 장거리 종속성 (LRD) |
| FARIMA | Fractional Integrated ARMA | 단거리 + 장거리 종속성 |
13. 핵심 공식 요약
| 법칙/Model | 공식 | 의미 |
|---|---|---|
| Littles Law | L = λ W | Queue 길이 = 도착률 × 대기 시간 (Waiting Time) |
| 이용률 | ρ = λ/μ = λ T | 부하 비율 (0~1) |
| M/M/1 Queue 길이 | ρ/(1-ρ) | 지수 서비스 시 평균 Queue 길이 |
| M/D/1 Queue 길이 | ρ/[2(1-ρ)] | 고정 서비스 시 평균 Queue 길이 |
| M/M/1 대기 시간 (Waiting Time) | Tρ1-ρ | 평균 대기 시간 (Waiting Time) |
| 서비스 시간 (Service Time) | T = L/b | Packet길이 / 대역폭 |
️ 14. 서비스 시간 (Service Time) vs Latency (중요!)
서비스 시간 (Service Time)(Service Time)은 Latency의 일부입니다! 전체 Latency가 아닙니다.
14.1 Latency의 구성요소
T_total = Th + Ts + Tc
= Head Latency + Serialization Latency + Contention Latency
| 구성요소 | 기호 | 공식 | 설명 |
|---|---|---|---|
| Head Latency | Th | Hmin × tr + Dmin/v | 헤더가 Network 통과하는 시간 |
| Serialization Latency | Ts | L/b | Packet 꼬리가 헤더 따라잡는 시간 |
| Contention Latency | Tc | Queuing Theory으로 계산 | 경합으로 인한 대기 시간 (Waiting Time) |
14.2 Zero-Load Latency (경합 없을 때)
T_0 = Hmin × tr + Dminv + Lb
| 항 | 의미 | 변수 설명 |
|---|---|---|
| Hmin × tr | Router 지연 | H = Hop 수, tr = Router당 지연 |
| Dmin/v | 전파 지연 (Time of Flight) | D = 거리, v = 전파 속도 |
| L/b | 직렬화 지연 = 서비스 시간 (Service Time)! | L = Packet 길이, b = 대역폭 |
14.3 서비스 시간 (Service Time) = Serialization Latency
T = Ts = Lb
Queuing Theory의 서비스 시간 (Service Time) T는 전체 Latency가 아니라,
Packet이 Channel을 점유하는 시간 (= 직렬화 시간)입니다!
14.4 Gantt 차트로 이해하기
id=”buffer”>
15. Buffer Size (Buffer Size)
15.1 왜 Buffer가 필요한가?
- 송신 속도 > 수신 처리 속도일 때 데이터 손실 방지
- 경합 시 Packet 임시 저장
- 플로우 컨트롤의 핵심 요소
15.2 최소 Buffer Size 공식 (Go & Stop Control)
Min Buffer = FlitSize × (R_overhead + S_overhead + 2 × Link Delay)
| 변수 | 의미 |
|---|---|
| FlitSize | Flit 크기 (bits) |
| R_overhead | 수신측에서 Stop 신호 발생까지 시간 |
| S_overhead | 송신측에서 Stop 신호 처리까지 시간 |
| Link Delay | Link 전파 지연 (왕복이므로 2배) |
15.3 Credit-Based Control
장점
- Buffer 최적 활용
- Link 길이와 무관하게 동작
단점
- 더 많은 제어 신호 필요
- 구현 복잡도 증가
15.4 Buffer Size와 성능 관계
| Buffer 크기 | Throughput | Latency | 문제점 |
|---|---|---|---|
| 작음 | 낮음 | HOL Blocking 증가 | Packet 손실/대기 |
| 큼 | 높음 | Queuing 지연 증가 가능 | 면적/전력 증가 |
15.5 실험 결과 (책에서 인용)
입력 Buffer 크기가 throughput과 latency에 큰 영향!
Wormhole(1-flit)은 VCT(8-flit) 대비 52% 낮은 throughput
15.6 HOL Blocking (Head-of-Line Blocking)
- Virtual Channel (VC): 물리 Channel을 논리적으로 분리
- Virtual Output Queue (VOQ): 출력 포트별 별도 Queue
15.7 Buffer vs Queuing Theory
| Queuing Theory | NoC Buffer | 주의점 |
|---|---|---|
| Queue (무한 가정) | Input Buffer (유한 크기) | Queuing Theory은 무한 Buffer 가정. 실제 NoC Buffer는 유한하므로 오버플로우 고려 필요! |
| Queue length N_Q | Buffer depth (flits) | |
| ρ/(1-ρ) 공식 | Buffer 오버플로우 가능! |
16. 실무 적용 시 주의사항
ρ ≥ 1이면 모든 공식이 무효 (무한 지연)
여러 Queue 중 가장 혼잡한 Queue가 전체 성능 결정
NoC는 Packet 길이가 고정인 경우가 많음
해석적 Model은 Simulation으로 검증해야 함
Uniform random traffic은 최선의 경우, adversarial 패턴 테스트 필요
Queuing Theory 무한 Buffer 가정 vs 실제 유한 Buffer
T = L/b는 직렬화 시간만!
- □ 이용률(ρ)이 1 미만인지 확인
- □ M/D/1 vs M/M/1 적절한 Model 선택
- □ Buffer 오버플로우 가능성 검토
- □ 다양한 트래픽 패턴으로 테스트
- □ Simulation으로 이론 Model 검증