최악의 경우 실행 시간

Worst-case execution time

계산 태스크의 Worst-Case Execution Time(WCET; 최악의 경우 실행 시간)은 작업이 특정 하드웨어 플랫폼에서 실행되는 데 걸리는 최대 시간입니다.

용도

최악의 경우 실행 시간은 일반적으로 신뢰할 수 있는 실시간 시스템에서 사용됩니다. 이 시스템에서는 소프트웨어의 최악의 경우 타이밍 동작을 이해하는 것이 신뢰성 또는 올바른 기능 동작에 중요합니다.

예를 들어, 차량에서 엔진의 동작을 제어하는 컴퓨터 시스템은 특정 시간 내에 입력에 응답해야 할 수 있습니다.응답 시간을 구성하는 컴포넌트 중 하나는 소프트웨어 실행에 소요된 시간입니다.따라서 최악의 경우 실행 시간을 결정할 수 있는 경우 시스템 설계자는 이를 스케줄 가능성 분석 등의 다른 기술과 함께 사용하여 시스템이 충분히 빠르게 응답할 수 있도록 할 수 있습니다.

WCET는 많은 실시간 시스템에 잠재적으로 적용 가능하지만, 실제로는 높은 신뢰성 또는 안전성과 관련된 실시간 시스템에 주로 WCET 보증이 사용된다.예를 들어, 항공 소프트웨어에서 DO178C 섹션 6.3.4에 따라 소프트웨어에 대한 어느 정도 주의가 요구된다.자동차 시스템에서 소프트웨어의 사용이 증가함에 따라 소프트웨어의 WCET 분석을 사용해야 하는 필요성이 대두되고 있습니다.

일부 시스템의 설계에서는 WCET가 스케줄러빌리티 분석의 입력으로 사용되는 경우가 많지만, 중요한 시스템에서는 WCET가 훨씬 더 일반적으로 사용되는 것은 파티션 스케줄된 시스템(ARINC 653)에서 사전 할당된 타이밍 버젯을 위반하지 않도록 하는 것입니다.

계산

임베디드 컴퓨팅의 초창기 이후 임베디드 소프트웨어 개발자는 다음 중 하나를 사용해 왔습니다.

  • 코드 엔드 투 엔드 측정(예를 들어 작업 시작 시 디바이스의 I/O 핀을 하이로 설정하고 작업 종료 시 로우로 설정하고 논리 분석기를 사용하여 최장 펄스 폭을 측정하거나 프로세서 클럭 또는 명령 카운트를 사용하여 소프트웨어 내에서 측정하는 등)
  • 각 기능, 루프 등에 대한 조립자 명령을 카운트하고 결합하는 수동 정적 분석 기법.

두 기술 모두 한계가 있습니다.엔드 투 엔드 측정은 가장 긴 경로를 달성하기 위한 소프트웨어 테스트에 큰 부담을 줍니다.계수 지침은 단순한 소프트웨어와 하드웨어에만 적용됩니다.두 경우 모두 테스트되지 않은 코드, 하드웨어 성능 근사치 또는 오류를 설명하기 위해 오류 여유를 사용하는 경우가 많습니다.20%의 마진이 종종 사용되지만, 이 수치에는 역사적 신뢰("지난 번에는 효과가 있었다")를 제외하고는 정당성이 거의 없습니다.

소프트웨어와 하드웨어가 복잡해짐에 따라 도구 지원이 필요하게 되었습니다.정적 분석과 측정 모두에서 복잡성이 점점 더 문제가 되고 있습니다.오차범위가 얼마나 넓어야 하는지, 소프트웨어 시스템이 얼마나 잘 테스트되었는지 판단하기는 어렵습니다.시험 중 달성된 최고점에 기초한 시스템 안전성 주장은 널리 사용되지만 소프트웨어와 하드웨어의 예측성이 떨어짐에 따라 정당화하기가 어려워진다.

향후 안전 중요 시스템에 대한 요건은 정적 [citation needed]및 측정 기반 접근방식을 모두 사용하여 분석해야 할 가능성이 높다.

고려 사항.

분석을 통해 WCET를 찾는 문제는 정지 문제와 같기 때문에 일반적으로 해결할 수 없습니다.다행히 엔지니어가 일반적으로 WCET를 찾고자 하는 종류의 시스템에서는 소프트웨어는 일반적으로 잘 구조화되어 있고 항상 종료되며 분석 가능합니다.

WCET를 찾는 대부분의 방법은 근사치(일반적으로 불확실성이 있을 때 위쪽으로 반올림)를 포함하므로, 실제로는 정확한 WCET 자체를 얻을 수 없는 것으로 간주된다.대신, WCET를 찾기 위한 다른 기법이 WCET에 [1]대한 추정치를 산출한다.이러한 추정치는 일반적으로 비관적이며, 이는 추정된 WCET가 실제 WCET보다 높은 것으로 알려져 있다는 것을 의미한다.WCET 분석에 대한 많은 작업은 분석의 비관론을 줄이는 것으로, 추정치는 시스템 설계자에게 가치가 있을 만큼 충분히 낮습니다.

WCET 분석은 일반적으로 단일 스레드, 태스크 또는 프로세스의 실행 시간을 나타냅니다.그러나 최신 하드웨어, 특히 멀티코어에서는 캐시, 메모리 라인 및 기타 하드웨어 기능을 공유하는 경우 시스템의 다른 태스크가 특정 태스크의 WCET에 영향을 미칩니다.또한 특정 시스템에서 발생할 수 있는 경우 차단 또는 중단과 같은 작업 스케줄링 이벤트를 WCET 분석에서 고려해야 한다.따라서 WCET 분석이 적용되는 컨텍스트를 고려하는 것이 중요합니다.

자동화된 접근법

WCET를 계산하는 방법에는 위의 수동 기법 외에도 많은 자동화된 방법이 있습니다.여기에는 다음이 포함됩니다.

  • 테스트 사례를 개선하여 엔드 투 엔드 측정의 신뢰도를 높이는 분석 기법
  • 소프트웨어의 정적 분석("소프트웨어를 실행하지 않고 정적")
  • 측정과 구조 분석의 조합으로 종종 "대부분" 분석이라고 불리는 복합 접근법

정적 분석 기법

정적 WCET 툴은 하드웨어 상에서 직접 실행하지 않고 컴퓨터 소프트웨어를 검사함으로써 WCET의 견적을 시도합니다.산업 환경에서 엔드 투 엔드 측정 접근법이 표준 관행이었지만 정적 분석 기법은 1980년대 후반부터 이 지역의 연구를 지배해 왔다.

정적 분석 도구는 소스 코드 조각 또는 분해된 이진 실행 파일에서 작업하는 프로그램의 작업 구조를 결정하기 위해 개략적으로 작동합니다.또한 작업이 실행되는 실제 하드웨어에 대한 타이밍 정보와 모든 특정 기능을 사용하여 낮은 수준에서 작동합니다.이 두 종류의 분석을 조합함으로써 툴은 특정 하드웨어 플랫폼에서 특정 태스크를 실행하는 데 필요한 시간의 상한을 부여하려고 합니다.

저수준에서는 예를 들어 명령/데이터 캐시, 분기 예측 및 명령 파이프라인 등 프로세서의 평균 케이스 성능을 향상시키는 아키텍처 기능이 존재하기 때문에 정적 WCET 분석이 복잡해집니다.분석에 의해 사용되는 타이밍 모델에서 이러한 최신 아키텍처 특성을 고려한다면 엄격한 WCET 경계를 결정하는 것은 가능하지만 점점 더 어려워지고 있습니다.

따라서 유럽항공안전청(European Aviation Safety Agency)과 같은 인증 기관은 모델 검증 [citation needed]스위트에 의존합니다.

정적 분석을 통해 보다 단순한 하드웨어에 좋은 결과를 얻을 수 있었습니다.그러나 정적 분석의 가능한 한계는 하드웨어(특히 CPU)가 모델링하기 매우 어려운 복잡성에 도달했다는 것입니다.특히 모델링 프로세스에서는 칩 설계 오류, 문서 부족, 문서 오류, 모델 생성 오류 등 여러 소스에서 오류가 발생할 수 있습니다. 이 모든 오류는 모델이 실제 하드웨어에서 관찰된 것과 다른 동작을 예측하는 경우로 이어집니다.일반적으로 동작을 정확하게 예측할 수 없는 경우에는 비관적인 결과가 사용되므로 WCET 추정치가 런타임에 달성된 것보다 훨씬 커질 수 있습니다.

멀티코어 프로세서에서는 특히 정적 WCET의 정확한 평가를 얻기 어렵습니다.

다양한 형태의 정적 분석을 구현하는 많은 상업 및 학술 도구가 있습니다.

측정 및 하이브리드 기술

측정 기반 접근법과 하이브리드 접근법은 보통 실제 하드웨어에서 짧은 코드 세그먼트의 실행 시간을 측정하려고 하며, 그런 다음 더 높은 수준의 분석으로 결합됩니다.툴은 소프트웨어의 구조(루프, 브랜치 등)를 고려하여 대규모 프로그램의 WCET 견적을 작성합니다.그 이유는 복잡한 소프트웨어에서 가장 긴 경로를 테스트하는 것은 어렵지만 많은 작은 컴포넌트에서 가장 긴 경로를 테스트하는 것은 더 쉽기 때문입니다.최악의 경우 효과는 분석에서 다른 최악의 경우 사건과 결합할 수 있도록 테스트 중에 한 번만 확인하면 됩니다.

일반적으로 소프트웨어의 작은 섹션은 계측(소프트웨어에 마커 추가) 등의 기술을 사용하거나 디버거, CPU 하드웨어 트레이스 모듈 등의 하드웨어 지원을 사용하여 자동으로 측정할 수 있습니다.이러한 마커는 프로그램을 통과하는 경로와 다른 포인트가 실행된 시간을 모두 포함하는 실행 트레이스를 생성합니다.다음으로 트레이스를 분석하여 프로그램의 각 부분이 실행에 소요된 최대 시간, 각 루프의 최대 관측된 반복 시간 및 테스트되지 않은 소프트웨어 부분이 있는지 여부를 판단합니다(코드 커버리지).

측정 기반 WCET 분석은 단순 하드웨어와 복잡한 하드웨어 모두에 좋은 결과를 가져왔지만 정적 분석과 마찬가지로 하나의 코어가 다른 코어에 미치는 영향을 정의하기 어려운 멀티 코어 상황에서는 지나친 비관론을 겪을 수 있습니다.측정의 한계는 테스트 중 최악의 경우 영향을 관찰하는 데 의존한다는 것이다(반드시 동시에 관찰할 필요는 없지만).최악의 경우 효과가 반드시 테스트되었는지 확인하는 것은 어려울 수 있습니다.

다양한 형태의 측정 기반 분석을 구현하는 많은 상업 및 학술 도구가 있습니다.

조사.

가장 활발한 연구 그룹은 스웨덴(Mélardalen, Linköping), 독일(Saarbrücken, 도르트문트, Braunschweig), 프랑스(Toulouse, Saclay, Rennes), 오스트리아(Vienna), 영국(University of York and Rapita Systems Ltd), 이탈리아(Span)입니다.최근 코드 레벨 타이밍 분석은 미국(노스캐롤라이나, 플로리다), 캐나다, 호주, 방글라데시(MBI LAB 및 RDS), 사우디아라비아-UQU(HISE LAB) 및 싱가포르의 연구 그룹에 의해 유럽 이외의 지역에서 더 많은 주목을 받고 있다.

WCET 툴의 과제

제1회 WCET Tool Challenge는 2006년 가을에 개최되었습니다.Mélardalen 대학이 주최하고, ARTIST2 Network of Excellence on Embedded Systems Design이 후원했습니다.이 과제의 목적은 최악의 경우 실행 시간을 분석할 때 서로 다른 접근 방식을 검사하고 비교하는 것이었습니다.WCET 작업에 대한 안전한 상한을 결정할 수 있는 모든 도구와 프로토타입이 참여했습니다.최종 결과는[2] 2006년 11월 키프로스 파포스에서 열린 ISoLA 2006 국제 심포지엄에서 발표되었습니다.

두 번째 챌린지는 [3]2008년에 개최되었습니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ 「최악의 실행 시간의 문제 - 방법과 툴의 개요」, Wilhelm, Reinhard 등, ACM Transactions on Embedded Computing Systems(TECS), Vol.7, No.3, 2008.
  2. ^ "Archived copy" (PDF). Archived from the original (PDF) on 2011-10-01. Retrieved 2010-08-15.{{cite web}}: CS1 maint: 제목으로 아카이브된 복사(링크)
  3. ^ "Archived copy". Archived from the original on 2012-02-16. Retrieved 2008-08-16.{{cite web}}: CS1 maint: 제목으로 아카이브된 복사(링크)

기사 및 백서

외부 링크