Worst-Case Execution Time (WCET) Analysis

1. Overview

최악 실행 시간 분석(Worst-Case Execution Time Analysis, WCET)은 "내 코드가 아무리 느려져도 이 시간을 넘지 않는다"는 것을 수학적, 물리적으로 입증하는 실시간 시스템의 최후 보루입니다.

현대 CPU는 캐시, 분기 예측기, 파이프라인 등으로 인해 동일한 코드라도 데이터 상태에 따라 실행 시간이 천차만별입니다. 학습자는 평균 속도가 아닌, 모든 물리적 해저드와 미스가 동시에 터지는 최악의 시나리오를 산출하는 기법을 배웁니다. 프로그램 흐름을 분석하는 **정적 분석(Static Analysis)**과 실제 장비에서 시간을 재는 **측정 분석(Measurement)**의 원리를 익히며, 이를 통해 시스템의 마감 시간 엄수 가능성을 숫자로 증명하는 엔지니어링 역량을 갖춥니다.

2. Scope & Boundaries

In-Scope

• WCET Foundations: BCET(최단), ACET(평균), WCET(최악)의 물리적 분포와 의미
• Control Flow Analysis: 루프 바운드(Loop Bounds)와 실행 경로 분석
• Hardware Interaction Analysis: 캐시 히트/미스 및 파이프라인 지연이 시간에 미치는 물리적 영향
• Schedulability Test: WCET 수치를 기반으로 한 작업 집합의 실행 가능성 검증

Out-of-Scope

• 일반적인 소프트웨어 알고리즘의 점근적 복잡도($O(n)$) 분석 (04. Algorithms 영역으로 위임)
• 운영체제 문맥 교환 오버헤드 측정 (06-01 RKS 영역으로 위임)

Boundaries

• WCET vs. Average Latency: 일반 성능 측정은 '사용자 경험'을 위해 평균을 보지만, WCET는 '안전 보증'을 위해 단 1회의 예외적 지연 가능성도 용납하지 않습니다.

3. Counterexample

• 단순히 "코드를 여러 번 돌려보고 가장 긴 시간을 고른다"는 방식은 WCET 분석이 아닙니다. 왜 측정 기반의 방식이 실제 환경에서 한 번도 마주하지 못한 '진정한 최악의 케이스'를 놓칠 수 있는지 물리적 한계점을 지적할 수 있어야 하며, 하드웨어의 분기 예측 실패와 L2 캐시 미스가 결합되었을 때 발생하는 '지연 시간 산사태(Latency Avalanche)'를 수리적으로 모델링하지 못한다면 WCET의 본질을 이해하지 못한 것입니다.

4. Prerequisites

• ALU & Data Path Design (Basic): 파이프라인 스테이지 지연 기초 지식이 필수입니다. (02-01-03 ADP)
• Cache Design & Locality (Recommended): 캐시 계층별 지연 시간 물리 이해가 권장됩니다. (02-02-01 CDL)

5. Learning Map

1. Upper Bound Pursuit: 운이 아주 없을 때 코드가 얼마나 느려질 수 있는지 '시간의 천장'을 찾습니다.
2. Loop Bound Constraining: 무한 루프가 아니더라도 하드웨어가 멈추지 않도록 반복 횟수의 수리적 최대치를 확정합니다.
3. Hard-path Extraction: 가장 복잡하고 지연이 큰 코드 경로(Longest Path)를 찾아 집중 분석합니다.
4. Safety Margin Engineering: 하드웨어 불확실성을 고려하여 WCET 수치에 물리적 여유분을 더하는 실무 기술을 완성합니다.

6. Learning Topics

Basic

Core: WCET의 개념과 실행 시간 분포 (Timing Fundamentals)

• Why to Learn: 프로그램이 정해진 시간 안에 끝날 확률이 99.9%가 아닌 '100%'임을 입증하기 위함입니다.
• What to Learn:
  • Execution Time Distribution: 데이터와 하드웨어 상태에 따른 클록 주기의 변화
  • WCET vs Deadline: 실행 한계 수치와 시스템 요구 사항 간의 물리적 관계
  • 루프 바운드(Loop Bound): 모든 반복문에 반드시 존재해야 하는 수량 차단 막
• How to Learn:
  • if 문 하나가 있을 때와 없을 때, 그리고 분기 예측기가 틀렸을 때의 실행 시간 차이를 클록 단위로 계산 실습
  • 간단한 C 코드에서 반복문 횟수를 명시하지 않았을 때 왜 WCET 산출이 물리적으로 불가능해지는지 입증
• Implement: 특정 코드 블록의 명령어 개수를 세고, 각 명령어의 최대 사이클 수를 곱하여 이론적 최대 시간을 구하는 도구

Recommended

Core: 정적 분석 기법과 IPET (Static Timing Analysis)

• Why to Learn: 실제 실행 없이도 수학적 증명만으로 최악의 시간을 보장받기 위해서입니다.
• What to Learn:
  • CFG (Control Flow Graph): 프로그램이 나아갈 수 있는 모든 경로의 지도
  • IPET (Implicit Path Enumeration Technique): 각 경로의 실행 횟수를 변수로 하여 최대 시간을 찾는 목적 함수 모델링
  • 하드웨어 추상 모델: 캐시 상태를 고정된 시나리오로 가정하는 물리적 단순화
• How to Learn:
  • 3중 중첩 루프 코드를 CFG로 그린 뒤, IPET 수식을 세워 가장 시간이 오래 걸리는 'Hot Path' 탐색 실습
  • 정적 분석 결과가 실제 측정치보다 항상 '크거나 같아야(Over-estimation)' 하는 보안적 이유 탐구
• Implement: 기본 경로별 가중치(시간)를 주었을 때 그래프 상에서 최장 경로를 탐색해주는 알고리즘

Practical

Core: 하드웨어 기능부전과 시간 불확실성 (Hardware Pathologies)

• Why to Learn: 하드웨어가 똑똑해질수록(Cache, Predictor) 시간 분석이 왜 기하급수적으로 어려워지는지 알기 위함입니다.
• What to Learn:
  • Timing Anomalies: 파이프라인에서 빠른 처리가 오히려 뒤쪽 연산을 늦추는 물리적 기현상
  • Cache State Analysis: 특정 메모리 주소 접근이 Always-Hit인지 Always-Miss인지 판별하는 물리 추론
  • 버스 경합(Bus Contention): 멀티코어 환경에서 램을 같이 쓰려 할 때 발생하는 예측 불가능한 지연
• How to Learn:
  • '캐시 히트'가 발생했을 때 오히려 뒤 명령어가 자원 경합으로 더 오래 멈추는 비결정론적 사례 분석 실습
  • 캐시 플러시(Flush) 후의 첫 실행 시간이 왜 WCET의 기준점이 되는지 물리적 근거 도출
• Implement: 캐시 상태(히트/미스/알 수 없음)에 따라 명령어 지연 시간을 가변적으로 적용하는 타임라인 시뮬레이터

Advanced

Core: 하이브리드 측정과 확률적 WCET (pWCET & Hybrid Analysis)

• Why to Learn: 복잡한 현대 프로세서에서 정적 분석의 한계를 극복하고 실전적인 시간 보증을 하기 위해서입니다.
• What to Learn:
  • Hybrid Analysis: 기본 블록은 측정하고 경로는 정적으로 조합하는 절충안
  • EVT (Extreme Value Theory): 측정 데이터를 바탕으로 아주 희박한 확률로 발생할 '최악의 시간'을 통계적 예측
  • 결정론적 하드웨어(Precision Timed Machines): 분석을 쉽게 하기 위해 의도적으로 기능을 제한한 하드웨어 설계
• How to Learn:
  • 수만 번의 실행 데이터를 받아 거대한 꼬리(Heavy Tail) 부분을 확률적으로 모델링해보는 분석 실습
  • 복잡한 AI 칩에서 WCET를 보증하기 위해 특정 기능을 끄거나 고정(Lock)하는 하드웨어 설정 사례 연구
• Implement: 실시간 측정 시계(Cycle Counter)를 활용하여 ISR 실행 시간의 분포 리포트를 생성하는 펌웨어 모듈

7. Terminology

8. References

Primary

• [P3] CyBOK v1.1 - Hardware Security / Real-time and Safety-critical Support — Timing predictability standards.
• [P2] SWEBOK v4.0 - Computing Foundations / Real-Time Systems — Performance analysis.

Secondary

• [Worst-case Execution Time Analysis for Real-time Systems] Wilhelm et al. — The fundamental survey/paper.
• [Real-Time Systems Design and Analysis] Laplante — Chapters on predictable timing.

Industry

• [ISO 26262: Road vehicles — Functional safety (Timing requirements)] — Automotive WCET practice.
• [DO-178C: Software Considerations in Airborne Systems (Verification)] — Aerospace execution time standards.

9. Final Checklist

Primary

• 캐시(Cache)와 파이프라인(Pipeline)이 있는 CPU에서 왜 '명령어 개수'만으로는 실행 시간을 물리적으로 산출할 수 없는지 이유를 설명 가능한가? (P3)
• WCET 분석 시 '재귀 함수(Recursion)' 사용을 임베디드 표준에서 왜 금기시하는지 분석 가능성 측면에서 입증할 수 있는 가? (P2)

Secondary

• '정적 분석'으로 산출된 WCET 수치가 실제 측정된 최댓값보다 작게 나왔을 때, 이 분석 결과가 왜 시스템 보안/안전에 무효한 것인지 소통 가능한가?
• 인터럽트가 중첩되는 시스템에서 순수 태스크의 WCET와 '인터럽트 지연'이 결합된 총 마감 시간을 수리적으로 도출할 수 있는 가?

Industry

• 항공기 비행 제어 소프트웨어 검증 시, 최신 CPU의 '비결정론적 기능(예: SMT)'을 비활성화했을 때 WCET 분석이 비약적으로 단순해지는 물리적 근거를 제안할 수 있는 가? (SFIA)
• 코드 변경 후 WCET가 마감 시간(Deadline)에 근접했을 때, 하드웨어 타이머의 해상도(Resolution)를 고려한 안전 마진(Safety Margin)을 재설정할 수 있는 가?