페이퍼요약 - UML 기반 실시간 임베디드 애플리케이션의 최고실행시간 분석 by Mraidha

제목: UML 기반 실시간 임베디드 애플리케이션의 최고실행시간 분석(Worst-Case Execution Time Analysis from UML-based RT/E Applications)

저자: Chokri Mraidha 외 3인, 프랑스 CEA

문서유형: 연구소 페이퍼(총 15페이지)

 

실시간 임베디드 애플리케이션의 UML 모델로부터 최고실행시간(WCET)을 추정하는 정적 분석 방법과 동적 분석 방법을 제안한 자료

---

CEA(Commissariat à l’Energie Atomique)

• 1945년 설립된 프랑스의 공공 연구 기관으로 원자력, 국방, 기타 과학 기술 분야를 연구
• 파리를 포함 프랑스 전역에 10개의 연구 센터가 있음(군 연구소 5개, 민간 연구소 5개)
• 대학 및 기업체와의 인적 자원 지원과 협업이 활발하며 EU의 다른 국가들과도 다양한 프로젝트 진행

MDA(Model Driven Architecture)

• 기존의 코드 중심 개발(code-centric development)에서 모델 중심 개발(model-centric development)로의 전환
• 점점 증가하는 실시간 임베디드 시스템의 복잡성에 대응할 수 있는 방법으로 OMG(Object Management Group)가 권장
• 반복적(iterative) 설계 프로세스에서 애플리케이션의 UML 모델링과 코드 변환(즉, 명세된 모델로부터 코드를 자동 생성)에 의존

스케쥴가능성 분석(Schedulability Analysis)

• 임베디드 실시간 시스템 개발의 핵심 활동 중 하나가 '벨리데이션(validation)'이며, 특히 스케쥴가능성 분석(schedulability analysis)은 애플리케이션의 실시간 요구사항(예, 데드라인, 준비시간 등) 충족 여부를 검증하는데 주로 사용됨
• 스케쥴가능성 분석 방법 대부분이 시스템 태스크의 최고실행시간(Worst-Case Execution Time: WCET)에 대한 정보에 의존함
• 프로그램 실행 시간은 여러 요인에 따라 달라지는데, 예를 들어 프로그램 입력 데이터의 여러 다른 값들은 프로그램 실행 경로가 달라지게 만들고 그에 따른 실행 시간도 달라지게 된다. 이런 여러 가능한 실행 시간 중 가장 높은 것을 WCET라 함(멀티 태스크 실행에서 발생 가능한 preemption은 고려하지 않은 시간)
• 스케쥴러는 추정된 WCET을 기반으로 시스템의 태스크들을 스케쥴링 한다.

WCET 분석 기존 연구

최고실행시간(WCET) 분석 방법은 크게 아래 두 그룹으로 나뉜다. 

1) 정적 방법(Static methods)

• 입력 데이터 값에 독립적이며 프로그램을 실행하지 않고 정적으로 분석함
• 정적 분석 기법들은 대개 2단계로 수행됨.
  - 1단계: 프로그램의 모든 실행 경로를 결정하는 상위 레벨 분석,
  - 2단계: 식별된 경로들의 실행 시간을 추정하는 하위 레벨 분석
• 정적 방법이 극복해야 할 주요 과제는 WCET 과대 평가(overestimate)를 피해야 하는 점이다(시스템의 과도한 하드웨어 설계를 요구하는 문제를 낳게 됨).
• 일반적으로 정적 분석 도구는 WCET 분석 수행에 있어 마이크로프로세서 자체보다는 마이크로프로세서의 시뮬레이터에 의존(시뮬레이터의 유효성 및 정확성이 중요함)

2) 동적 방법(Dynamic methods)

• 테스팅 기법을 통한 시간 측정에 의존함. 즉, 실제 시스템 또는 시뮬레이터 상에서 모든 가능한 입력 데이터 값에 대한 프로그램 실행 시간을 측정함
• 동적 방법으로 WCET를 결정하기 위해서는 i) 애플리케이션의 실행 시간을 측정하는 기법과 ii) 가장 높은 실행 시간을 보이는 입력 데이터 집합을 찾는 기법이 필요하다.
• 실제 시스템에서 애플리케이션의 실행 시간을 측정하는 경우 마이크로프로세서에서 제공되는 내부 카운터(예, 펜티엄 마이크로프로세서의 Time Stamp Counter 레지스터)를 활용 가능. 실제 시스템의 타겟 플랫폼이 없는 경우는 해당 하드웨어를 모델링한 시뮬레이터에서 애플리케이션을 실행하고 실행 시간을 계산해 주는 기능(facility) 활용
• 모든 가능한 입력 값에 대한 실행 시간 측정은 입력 값이 제한된 간단한 시스템에서는 가능해도 대규모 시스템이나 무한 도메인에서는 불가능. 동적 방법이 모든 테스트 케이스를 커버하지는 못해도(따라서 가장 긴 실행 시간을 가지는 케이스를 찾지 못해도) 산출된 WCET가 소프트 실시간 시스템의 요구사항은 충족 시킬 수 있음

Accord/UML로 실시간 임베디드 애플리케이션 모델링

• Accord/UML은 실시간 시스템 모델링에 적합하도록 기존 UML을 개선한 UML 확장판(extensions). CEA의 실시간 임베디드 시스템 연구 그룹인 LIST에 의해 제안됨
• 본 논문은 스케쥴가능성 분석(schedulability analysis)과 성능 분석(performance analysis) 수행에 있어 주요 모델인 Accord/UML의 동작 모델(behavioral model)에 중점을 둠
• Accord/UML은 클래스의 동작 고려사항(behavioral concerns)을 콘트롤 측면(control aspects)과 알고리즘 측면(algorithmic aspects)으로 분리 구현함(아래 그림 참조). 이 방식은 개발되는 애플리케이션의 재사용성과 유지보수성을 향상 시킴
• 콘트롤 측면 모델링은 클래스의 순수 논리적 동작(‘오브젝트 생명 주기’라고도 불림)을 묘사하며, 이는 프로토콜 상태 머신(protocol state machine)이라 불리는 특수한 UML 상태 머신에 의해 모델링 됨
• 알고리즘 측면 기술은 클래스 모델의 오퍼레이션 레벨로 미루어지며, UML 액션 시맨틱 표준에 매핑하는 액션 언어(an action language)를 사용하여 모델링 된다.

[Accord/UML 동작 모델(behavioral model)]

• Accord/UML은 실행가능모델(executable models)을 얻기 위해 두 가지 형식의 액션 언어 표기법(action language notation)을 정의함:
  - i) 모델에서 직접 편집 가능한 텍스트 형식과,
  - ii) UML 모델러에서 그릴 수 있는 UML 액티비티 다이어그램의 그래픽 형식.
  양쪽 뷰가 동등하며 오퍼레이션의 텍스트 정의 형식이 사용이 편한 경우도 있고 또는 그래프 형식이 더 이해가 쉬울 수도 있음
• Accord/UML 액션 언어는 조건 액션(conditional actions), 루프 액션(loop actions), 그룹 액션(group actions), 메시징 액션(messaging actions) 등으로 구성됨. 즉, Accord/UML로 실시간 시스템 모델링을 하는데 있어 필요한 모든 기본 액션(elementary actions)들이 정의됨
• 아래의 조건 액션(conditional actions) 예에서 첫 번째 것은 “if-then-else” 기본 액션이고 두 번째 것은 “switch” 기본 액션이다.
• 이 액션 언어는 특정 프로그래밍 언어에 종속적이지 않은 완전한 실행가능모델을 얻게 해준다(C, C++, Java 같은 실제 프로그래밍 언어 코드는 이 동작 모델로부터 생성됨).

[ACCORD/UML 액션 언어에서 조건 액션(conditional actions)의 예]

아가사 툴 셋(The Agatha toolset)

• 본 논문은 Accord/UML 동작 모델(behavioral models)의 알고리즘 측면 분석에 중점을 두어 애플리케이션 클래스의 각 오퍼레이션의 WCET를 결정하는 정적 방법과 동적 방법을 제안함. 제안된 이 정적 및 동적 WCET 분석 방법은 Agatha라는 툴셋을 활용
• CEA의 LIST 그룹이 개발한 Agatha는 기호 실행(symbolic execution) 기법을 기반으로 한 테스트 도구이며 소프트웨어 구현이 그 명세에 부합하는지 결정하기 위한 테스트 케이스 집합을 생성한다.
• 기호 실행 기법에서는 입력 값으로 실제 값을 주는 대신 기호를 사용하고 프로그램 실행 동안 기호의 상태(status)를 유지. 기호 연산(Symbolic calculus)에서 모든 동작을 컴퓨팅 하는 것과 입력의 모든 가능한 값을 시도하는 것과는 다르므로 이 기법은 입력 범위가 크거나 무한인 변수 도메인을 다룰 수 있게 해 줌
• Agatha 툴셋을 WCET 분석에 적용 시 오퍼레이션의 UML 모델을 Agatha 고유의 입력 형식인 STGA(Symbolic Input Transition Graph with Assignment)로 전환하고, 기호 연산(symbolic calculus)을 통해 모든 가능한 기호 동작(symbolic behavior)을 계산함
• 아래는 Agatha의 입력 언어인 STGA의 예이다(STGA의 자세한 내용이나 UML을 STGA로 전환하는 방법은 본 논문의 범위 밖이므로 설명 생략)

[STGA 전이(transition)의 예]

제안된 정적 WCET 분석 방법

• 정확한 플랫폼 정보와 주어진 실행 플랫폼에서의 액션 언어의 기본 액션들의 WCET를 알고 있다면 WCET를 정적으로 결정하는 것이 가능함
• 특정 실행 플랫폼에서 기본 액션의 WCET 값은 런타임 측정 도구(a runtime measurement tool)나 정적 분석(static analysis) 활용 같은 여러 방법으로 획득 가능함

1) 정적 WCET 분석 프로세스

①     첫 단계는 플랫폼에 독립적인 작업으로 애플리케이션의 알고리즘을 기술한 UML 동작 모델(behavior model)을 기호 실행(symbolic execution)을 통해 정적으로 분석한다.
- 먼저 아래 좌측 그림과 같은 오퍼레이션 모델(Accord/UML 액션 언어의 기본 액션)에 아래 우측 그림처럼 WCET 변수를 첨가한다. 즉, 각 기본 액션에 상응하는 기호 값(symbolic value)을 할당하여 WCET 정보를 기호 표현식(symbolic expressions)으로 나타냄. 예를 들면, 기호 값 AssignAction은 할당 액션(an assignment action)에, AddAction은 덧셈 액션(an addition action)에, TestAction은 결과가 참/거짓인 테스트 액션(a test action)에 할당되고, AsynchronousCallAction은 비동기 호출 액션(an asynchronous call action)을 나타낸다.
- 이렇게 주석이 달린 UML 동작 모델이 Agatha 내부 언어인 STGA로 전환되며, Agatha는 기호 실행(symbolic execution)을 수행한다. 즉, Agatha 툴이 주어진 오퍼레이션의 모든 가능한 기호 실행 경로(all symbolic execution paths)를 계산한다.
- 최종적으로 WCET에 대한 모든 가능한 기호 값들의 집합(a set of all possible symbolic values)을 얻게 됨

②     플랫폼에 종속적인 두 번째 단계는 각 기본 액션의 기호 표현(symbolic expression)을 타겟 플랫폼의 상응하는 수치 값(numerical values)으로 대체함으로써 주어진 플랫폼에서의 WCET를 얻는다.

-->

2) 정적 WCET 분석 예

• 위 좌측 그림의 예(간략한 설명을 위해 오퍼레이션의 일부분만 제시)는 먼저 변수 x의 할당이 있은 후 이 변수의 값을 체크하여 두 개의 다른 경로 중 하나를 선택한다.
• 위 우측 그림처럼 이 오퍼레이션 모델에 0으로 초기화된 WCET 변수가 자동 첨부되며, 기본 액션의 실행에 따라 WCET 변수 값도 증가하게 된다.
• 이 모델은 Agatha 툴의 입력 형식인 STGA로 자동으로 변환되고, x≤10와 x>10 경로에 상응하는 두 개의 실행 경로가 Agatha의 기호 실행 결과로 나오게 된다. 즉, 아래와 같은 두 개의 WCET 표현식을 얻게 되고, 결국 x≤10 경로가 최고실행시간(WCET)이 된다.

 

1. W1 - WCET = 2*WCET_AssignAction + WCET_TestAction + WCET_AddAction (x≤10 경로)

2. W2 - WCET = 2*WCET_AssignAction + WCET_TestAction (x>10 경로)

제안된 WCET 동적 분석 방법

• 플랫폼 아키텍쳐에 대한 정보가 없거나 현대식 아키텍쳐의 복잡한 매카니즘을 고려해야 하는 정적 방법의 어려움을 피하기 위해 동적 WCET 분석 방법이 사용됨
• 동적 분석 방법은 런타임에 동작 모델을 분석한다. 즉, 모델화된 오퍼레이션의 모든 가능한 실행 경로를 테스팅하여 특정 플랫폼 상에서의 각 경로의 실행 시간을 측정하고, 이를 기반으로 주어진 실행 플랫폼에서의 주어진 오퍼레이션의 WCET를 추정한다.

1) 동적 WCET 분석 프로세스

①     첫 단계는 플랫폼에 독립적으로 수행된다. UML 모델이 Agatha의 STGA 형식으로 자동 변환되며, Agatha는 기호 실행을 통해 오퍼레이션의 모든 가능한 실행 경로를 결정하고 각 경로를 커버하는 테스트 케이스를 자동으로 생성한다.
- 이 때 식별된 각 경로는 오퍼레이션 패러미터에 대한 제약 조건 집합(a set of constraints)인 경로 조건(Path Condition: PC)으로 특징지어진다(각 PC는 유사한 테스트 케이스 값들이 속해 있는 동등 클래스에 상응함).
- Agatha의 제약조건해결자(constraint solver)는 PC의 각 변수에 대한 단일 값(a single value)을 계산해 준다. 하지만 산출된 이 단일 값이 가장 긴 실행시간을 가진다고 보장하지는 않음. 즉 해당 PC의 다른 값이 더 긴 실행 시간을 가질 수도 있다.

②     플랫폼에 종속적인 두 번째 단계는 UML 모델로부터 코드를 생성하고, 컴파일하고, 이전 단계에서 생성한 모든 테스트 케이스를 사용하여 타겟 플랫폼에서의 오퍼레이션 실행 시간을 측정하고, WCET를 유추한다.
- 실행 시간에 영향을 주는 플랫폼 요소로 소프트웨어 자원(예, 모델로부터 생성된 프로그래밍 언어, 코드 생성 패턴, 컴파일러와 코드를 컴파일 하는데 선택된 옵션, 운영체제)과 하드웨어 자원(예, 마이크로프로세서, 메모리 configuration)이 있다.
- 여러 다른 테스트 케이스의 실행 시간 측정을 위해 이런 아키텍쳐 정보와 메커니즘을 모두 고려하는 것은 매우 어려우므로 본 논문에서 제안된 방법은 모델로부터 생성된 코드가 타이밍 루틴(실행 중 경과된 시간을 캡쳐하는 기능)을 포함하도록 한다. 즉, 생성되는 프로그래밍 언어, 하단에 놓이는 운영체제, 마이크로프로세서의 타입을 고려하여 자동 코드 생성 중에 타이밍 루틴 코드가 추가된다.
- 오퍼레이션의 실행 시간을 측정하는 이 타이밍 루틴의 코드는 플랫폼마다 다르지만 기본 원칙은 동일하다. 오퍼레이션 호출(operation call)의 전과 후의 시간을 캡쳐하고 이 두 시간의 차이를 실행 시간으로 함

[동적 WCET 분석 프로세스 개요]

2) 동적 WCET 분석 예

• 아래 보여진 간단한 오퍼레이션 myOperation은 두 개의 입력 패러미터(a와 b)를 가진다.
• 이 예제의 실행 플랫폼은 인텔 1.2 GHz 펜티엄 III 모바일이며 256 Mo 메모리에 운영체제는 Linux이다. 생성된 코드는 아무런 최적화 옵션 없이 GCC 3.2 컴파일러로 컴파일 되었다.

[오퍼레이션 모델의 예]

• 동적 WCET 분석의 첫 단계로 오퍼레이션 모델이 Agatha 내부 언어로 변환되었고, 이 모델에 대한 기호 실행(symbolic execution)이 수행되었다. Agatha는 각각의 연관 PC를 가진 4개의 실행 경로를 계산해 냄. 아래 표는 산출된 PC와 해당 PC를 충족시키는 패러미터 a와 b의 테스트 케이스 값(numeric test cases values)의 예이다.

[경로 조건(PC)과 테스트 케이스 수치 값]

• 두 번째 단계로 위의 테스트 케이스로 타겟 플랫폼에서 오퍼레이션을 실행하고 실행 시간을 측정함. 범용 운영체제의 타이밍 루틴은 정밀도가 낮으므로 이 예제는 마이크로프로세서 클락 사이클 내부 카운터(TSC register)를 사용하여 측정하였음.
• 단순 오퍼레이션의 단일 호출에 대한 실행 시간 측정의 정확성이 떨어져서 해당 오퍼레이션을 여러 번 반복 호출하여 실행 시간을 측정함. 이 때 사용된 호출 반복(loops of call)이 캐시의 영향을 받지 않도록 하기 위해 캐시는 비활성화 시킴
• 아래 그림은 예제 애플리케이션의 4개 PC의 실행 시간 측정 결과를 보여준다. 실행 시간이 오퍼레이션 호출의 반복에 따라 정비례로 증가하며, 세 번째 테스트(위 표에서 a=10이고 b=20인 테스트 케이스)가 가장 긴 실행 시간을 보인다. 이 오퍼레이션의 최고실행시간(WCET)은 27μs로 측정되었다.

[Agatha에 의해 식별된 4개 PC의 실행 시간 측정]