WCET Analysis

Why analytical methods?

• Measurement
  • WCET 보장 불가: Branch, Loop Count, Cache hit/miss에 따라 시간 변동 -> 모든 경로 실측 불가능
  • 시간과 비용소모: 반복 실행과 시뮬레이션이 매우 비싸고 오래걸림
  • Design Phase 적용 불가: 실행 가능한 코드 & 환경 준비 후에 측정 가능
• Analysis(정적 분석 기법)의 장점
  • WCET 보장: 최악의 실행시간을 안전하게 상한으로 계산 가능 (Safe Bound 제공)
  • 자동화 가능: 대부분 분석은 자동화 도구 수행 가능
  • Design Phase  적용 가능: 코드 작성 초기에 분석 가능

WCET Analyser는 IDE의 중요한 구성 요소 중 하나이다

 

Basic Analysis Method

• Basic Construct: 단순 대입문 Ex. i=0, a=b+c
• Sequential Construct: 순차적으로 이어지는 블록
• While Construct: 반복문 Loop 처리
• If Construct: 조건문 분기 처리 

Timing Schema Basic Rules

1. 연속 블록

$$T(S_1;S_2) = T(S_1)+T(S_2)$$

2. if문

$$T(if)=T(exp)+max(T(S_1),T(S_2))$$

3. while문 (N회 반복)

$$T(while) = N \cdot (T(exp)+T(body))+T(exp)$$

따라서 위의 예제를 Bottom-up으로 계산해보면, 

1. 첫번째 If 문: $T = 1 + max(2,6) = 7$

2. 두번째 If 문: $T = 1 + max(4,3) = 5$

3. While문 Body: $T = 4 + 7 + 5 = 16$

4. While 문 반복 5회: $T = 5 \cdot (1 + 16) + 1 = 86$

5. 전체: $T = 1(init) + 86 = 87$

 

Pipelined Processor

우리가 흔히 사용하는 프로세서들은 파이프라인 구조를 가지고 있다. 

따라서 Instruction을 항상 하나씩 처리하는게 아니라 병렬 구조로 처리할 수 있다. 

Reservation Table

파이프라인 명령어들의 실행 타이밍을 단계별 파이프라인 스테이지(IF, RD, ALU, MD, DIV, MEM, WB)로 나눈 시간표처럼 표현한 것을 Reservation Table이라고 부른다. 

• Row: 파이프라인 Stage
• Column: Clock Cycle
• X: 해당 스테이지가 점유되고 있음

 

Bottom-up Concatenation 개념

우리가 분석하려는 프로그램은 Construct의 조합 ($S_1,S_2...$)인데, 단순히 시간 $T(S_1), T(S_2)$를 더하지 않고, 각 Construct의 Reservation Table $W(S)$를 Concatenate하는 방식 사용

$$w(S)=w(S_1)\oplus  w(S_2)$$

즉, 파이프라인 자원 충돌이 없도록 $w(S_1)$을 $w(S_2)$ 뒤에 잘 붙이는 방식

 $S_1$과 $S_2$는 각각 9 cycle동안 실행되지만, Reservation Table을 직렬로 붙이면, 15 cycle에 완료된다. 

$S_1$ 쪽이 더 높은 clock cyle을 보인다.

이때 $SS_2$ 구문에 $SS_1$구문을 합치는 경우를 생각해보자

이 경우에는 $S_2$쪽이 전체 Clock Cycle이 더 높은 걸 볼 수 있다.

Revised Timing Schema

1. 순차 구성 ($S_1$, $S_2$)

$$w(S)=w(S_1)\oplus  w(S_2)$$

• $S_1$의 실행 후 충돌이 없도록 $S_2$를 붙인다. 

2. 조건문 (if-else)

$$W(S)=(W(exp)\oplus W(S_1))\cup (W(exp)\oplus W(S_2))$$

• 조건 exp 평가 후에 $S_1$ 또는 $S_2$ 중 하나 실행됨
• 둘 중 하나만 실행되지만, WCET에서는 둘 중 더 긴 경우를 고려해야 하므로 합집합 사용

3. 반복문 (While)

$$W(S)=(\bigoplus _i^N(W(exp)\oplus W(S_1)))\oplus W(exp)$$

• 반복문은 N번 실행된
  • 각 반복마다 조건 평가 후 본문 실행
• 마지막에는 반복을 빠져나오기 위한 조건 평가가 한 번 더 있음

What are problems?

1. Reservation Table이 점점 길어짐

2. Reservation Table의 수가 지수적으로 증가

Abstracted Reservation Table

Abstracted Reservation Table

전체 테이블을 유지하는게 아니라, 앞/ 뒤 부분만 유지 -> 연산/비교를 단순화할 수 있음

연산결과는 19 Cycle이지만, 우리는 전체 Resevation Table 내용을 알 필요가 없고, head, tail 정보만 알면 된다

Pruning

불필요한 reservation table은 제거하자

• 모든 reservation table을 다 유지하려면 메모리/시간 낭비
• 어떤 table $w_1$이 아무리 나쁘게 동작해도, 다른 table $w_2$보다 항상 더 나은 결과를 내면 $w_1$은 더이상 필요없다.

$$\exists w_2\in W,\,\,\,\, w_1.time < w_2.time-\delta _{head}-\delta _{tail}$$

만약 $w_1$의 전체 실행 시간이, $w_2$의 연결 가능한 유효 시간보다도 작다면, $w_1$은 더 나은 후보니까 $w_1$을 제거할 수 있다.

왜 그러면 우리는 $w_1$은 head, tail시간을 빼지 않고, $w_2$는 빼는가?

• $w_1$은 지금 "쓸모가 있는지 없는지 판단받는 입장"
• 즉, 전체 시간을 기준으로 쓸모 없음이 확실해야 제거할 수 있음
• 아무리 좋게 봐줘도 (full time 기준으로 봐도) $w_1$이 $w_2$보다 안 좋으면 버릴 수 있다는 의미

 

Instruction Cache Effects

• 우리가 사용하는 대부분의 프로세서는 Instruction Cache를 가지고 있으며, WCET 분석에 있어서 이를 고려하지 않는다면, 너무 보수적인 분석이 될 수 있다. 
• Cache hit/miss는 이전 실행 경로에 의존적이다. 

Local 구간에서 Cache분석을 할 때, 확실한 부분을 위주로 정리하면 된다.

앞 선 실행 경로가 어떻게 되어 있는지 모르므로, 우선 ?로 표기하고, 특정 명령 요청 이후에는 Cache에 해당 명령이 있을 테니 Cache Block에 채운다. 그리고 새로운 명령이 들어오면, 다시 업데이트한다.

1. 확실할 때는 정확히 분석
2. 불확실할 때는 cache miss 처리
3. 나중에 합칠 때 hit 여부가 명확해지면 갱신