[Real Time] Worst Case Execution Time

지금까지 계속 다룬 걸 보면 계속 Scheduling에 대한 내용에는 항상 Timing Value에 관한 것이 포함되어 있다. 우리가 이 값들을 미리 알고 해당 Task에 대한 Scheduling을 할 수 있다면 그보다 더 나은 System은 없을 것이다. 그런데 이걸 매 Timing 때마다 고려를 하자니 여기에 소모되는 Resource가 낭비된다고 생각할 수 있다. 그래서 해 볼 수 있는 생각이 한계를 정해두고 한계를 넘지 않는 한은 계속 용인하고 한계를 넘는 것에 대해서만 다른 처리를 할 수 있는 구조를 택하자는 것이고, 그 한계를 Worst Case일 때의 한계로 정해보자는 것이다. 이번 포스트에서 소개하는 Worst Case Execution Time은 말 그대로 Execution Time 중에서 가장 Worst Case 만 고려해서 들어오는 입력에 대한 analyze를 하는 것이다. 

그래서 위와 같이 Module 형식으로 구현한다면 우리는 이 모듈로부터 앞에서 언급한 WCET나 WCET가 나올 때 수행 과정과 같은 정보를 얻을 수 있고, 이에 대한 대처를 미리 지정할 수 있다.  간단한 예는 다음과 같다. 

위와 같은 C 로 된 코드가 존재한다. 당연히 system이 이걸 바로 읽는 것이 아니고 중간에 compiler가 assembly로 바꿔주는 중간단계를 거치게 된다. 이때 flow chart가 형성될 것이다. 

물론 프로그램의 결과만 고려한다면 위의 flow chart는 의미가 없겠지만 그 내부구조를 이해하는 사람이라면 각각의 분기점에서 소요되는 시간이 다르다는 것을 알고 있을 것이다. 예를 들어 i < 5라는 조건문을 수행할 때 걸리는 시간과 그 다음 case인 i++ ; a = b+c 를 수행하는 시간 자체가 다르다는 것이다. 그러면 어떤 분기를 거쳤냐에 따라서 최종적으로 얻는 time 또한 달라질텐데, 그 중에서 가장 오래 걸린 시간을 측정하는 것이 바로 앞에서 언급한 Worst Case Execution Time Analysis가 되겠다. 그럼 이 값을 바탕으로 system의 한계를 정해놓는다면 그 한계 내에 있는 값들은 적절히 처리할 수 있을 것이다. 

 자 그럼 조금더 프로세서 입장에서 바라보는 Worst Case Execution Time Analysis를 보겠다. Processor의 Execution 방법중 pipeline Execution 에 대한 이야기를 들어봤을 것이고, 간단히 말하면 같은 Cycle에 여러 모듈이 동시에 수행하게 함으로써 Execution Time을 조금이라도 줄여보자는 것이 취지였다. 그러면 다음과 같은 time Table도 그려볼 수 있을 것이다.

그런데 지금 위의 Time Table은 실제로 동작한 후의 Table이 아니라 미리 Process과정을 분석해서 그려놓은 것이다. 그래서 해당 cycle에 정해진 stage가 수행되도록 한 것이다. 이 같은 것을 보통 Reservation Table이라고 한다. 위의 Table에서는 Worst Case Execution Time이 21 Cycle 인 것이다. 

 자 그럼 다음과 같은 Case를 보겠다. 

지금 위와 같이 S(1)에서 S(2)로 진행되는 코드가 존재한다. 당연히 앞에서 언급한 pipeline 구조라면 S(1)에 대한 pipeline reservation Table이 있을 것이고, S(2)에 대한 reservation Table이 있을 것이다. 

만약 위에 대한 Worst Case Execution Time을 구하라면 어떻게 할 것인가? 제일 쉽게 해볼 수 있는 것은 그냥 S(1)이 수행된 다음 S(2)가 수행되게 하는 것이므로 WCET 는 18이라고 할 수 있는 것이다. 그런데 그렇게 따지다 보면 S(1)이 끝나는 시점과 S(2)가 시작하는 시점 사이에 약간의 idle이 존재하는 것을 확인할 수 있다. pipeline의 구조상 그런 걸 배제하는 게 원칙이므로 조금씩 overlap를 시켜서 Execution Time을 줄일 수 있다. 당연히 하나의 stage에서는 한개의 작업만 수행할 수 있다는 원칙은 지켜져야 한다. 그러면 다음과 같이 reservation Table을 그릴 수 있게 된다. 

이렇게 따지니 time이 18에서 15로 줄었다. 이런 접근 방식을 Bottom up concatenation 이라고 한다. 

그런데 이건 가장 기본적인 idea일 뿐 main Idea가 될 수 없다.  이렇게 concatenation을 통해서 구한 WCET가 항상 정답이라는 것을 보장하지 못하기 때문이다. 

위와 같이 exp라는 분기에서 S1과 S2의 execution Time이 다르다. 여기서 WCET를 정하면 당연히 exp - > S(1)로 가는 방향이 될 것이다. 여기까지는 별 문제가 없다. 문제는 이런 조건 분기가 하나의 모듈화가 되서 다른 분기가 붙었을 때의 WCET가 계속 유지되냐는 것이다. 

 분명히 SS(2)에서는 exp - > S(1)으로 가는 방향이 WCET라고 생각했었다. 하지만 SS(1)이 있는 상태에서 WCET를 구해보면

재미있게도 기존에 WCET로 고려되지 않았던 exp -> S(2) 쪽의 Execution Time이 더 긴 것을 확인할 수 있다. 그래서 결국 무작정 concatenation을 통한 WCET가 항상 정답이라고 할 수 없다는 것이다.

그래서 전체 reservation table이 있으면 각 경우에 따른 분석을 쭉해봐야 한다. 위처럼 한가지 경우에 대한 WCET 를 구하는게 답이 아니다. 

 그런데 문제는 분기가 늘어날 때마다 이 Reservation Table도 기하급수적으로 늘어난다는 것이다. 위의 Bottom up Concatenation을 취한다 하더라도 overlap이 되지 않는 범위 내에서 수행되기 때문에 잘리는 부분이 얼마 없다. 여기서 생각해보면 괜히 WCET에 포함되지 않는데 불구하고 고려해야 되는 케이스들도 존재한다. 위의 예를 보면 최종적으로 얻은 결과만 보더라도 일정부분을 제외하고는 모양이 비슷하다. 그래서 잘 보면 reservation table내에서 head와 tail 부분이 유사하고 중간부분이 WCET를 결정짓는 요소라는 것을 알 수 있다. 

 결과적으로 중간 부분만 고려하고 중간 부분이 긴 것만을 따지면 WCET를 구하는데 도움이 될 것이다.

아무튼 이런식으로 Execution Time을 측정한 후 analyze하는 것이 RTOS에서 가장 기본적인 요소이다. 이걸 해결하는 방법에 대해서 궁금한 사람은 다음 논문을 참고하면 좋을 거 같다.

http://www.cs.fsu.edu/~whalley/papers/tecs07.pdf