Hybrid methodology for the performance analysis of distributed real-time embedded systems

다국어 초록 (Multilingual Abstract)

Since multi-processor systems have benefits of scalability in performance and power, they become prevalent in embedded systems as well as desktop computers. A critical issue of designing a multiprocessor embedded system is to evaluate the expected performance early in the design process before actual implementation. For the application domains that have hard real-time constraints, it is essential to estimate the worst-case performance of the application. In particular we are interested in the worst-case response time (WCRT) of an application once it is triggered. In an automotive system, for example, an application algorithm is triggered by the arrival of a sensor input and the computation result should be delivered to actuators on time. However, it is a very challenging problem to determine a tight upper bound of the worst-case response time in a distributed real-time embedded system when execution time variations of tasks, jitter of input arrivals, scheduling anomaly behavior in a multi-tasking system, and heterogeneity of processing elements, are considered all together.
In the first part of this dissertation, we propose a novel analytical method, called STBA (Scheduling Time Bound Analysis) technique, which has a polynomial time complexity to the number of tasks while producing a much tighter bound than well-known compositional approaches, SymTA/S and MPA. Unlike conventional schedulability analysis approaches that are based on preemptive scheduling policy, the proposed technique supports an arbitrary mixture of preemptive and non-preemptive processing elements. In the STBA technique, by analyzing the graph topology and worst-case scheduling scenarios on the mapped processing element, we measure the schedulable time bound of each task as tightly as possible, which is characterized by two pairs of timing information: (minimum start time, maximum start time) and (minimum finish time and maximum finish time)
In the second part of dissertation, we propose a novel optimal method based on MILP (Mixed Integer Linear Programming) that is a well-known technique for combinatorial optimization problems. We translate the worst case response time problem as an optimization problem to use MILP solver. In the proposed technique, we formulate a set of MILP formula in a compositional way for modeling flexibility, but solve the problem holistically to achieve exact upper bounds. To mitigate the time complexity of the MILP method, we exploit the result from STBA technique to reduce the number of variables and confine the variable ranges.
As another method, we propose a meta-heuristic based method for the performance analysis. Like an optimal method we translate WCRT problem to optimization problem, but use meta-heuristic algorithm to solve the problem. In this method, we cannot achieve exact worst case response time. However, it overcomes the main limitation of optimal method that is exponential time complexity. Furthermore, we can get many near worst case scenarios which are close to exact worst scenario as population converged.
Extensive experiments are performed to confirm that the proposed technique gives reasonable performance for analysis. A real-life example shows promising results that give tight bounds in an affordable solution time.

국문 초록 (Abstract)

근래의 임베디드 시스템 환경은 성능과 전력의 한계점 때문에 점차 멀티 프로세서 시스템을 사용하는 추세이다. 멀티 프로세서 시스템을 설계하는데 있어서 중요한 문제들이 몇 가지가 있는데, 그 중에서 설계 초기 단계에서 최종 구현을 하기 전에 성능을 예측하는 문제는 아주 중요하다. 특히 하드 실시간 시스템의 경우 정확한 성능 예측을 하는 것이 중요하다. 성능 예측 문제에서 본 논문에서는 특히 최악 반응 시간(Worst Case Response Time)을 예측하는 것을 주 목적으로 한다. 차량 시스템에서, 센서의 입력으로부터 ECU 에서 동작하는 알고리즘을 통과하여 엑츄에이터까지 도달하는데 걸리는 최악의 시간을 예로 들 수 있다. 하지만 이러한 WCRT를 정확하게 예측하는 것은 매우 어려운 문제이다. 왜냐 하면, 태스크들의 다양한 수행시간, 릴리즈 지터, 멀티 프로세서 시스템으로 인한 어노말리 현상등이 존재 하기 때문에, 이 모든 것을 고려하면 문제의 복잡도가 크게 기하급수적으로 증가하기 때문이다.
이러한 문제를 두고, 본 논문에서는 세가지 방안을 제안한다. 첫째로 분석적 방법이다. STBA 분석이라고 이름 지은 방법은 닿아 시간의 복잡도를 가지고 태스크들의 안전한 최악 시간 바운드를 예측 한다. 스케줄링 기반 접근 방법으로 인해 이점을 지니기 때문에, SymTA/S 나 MPA와 같은 구성적 접근 방법에 비해 더욱 타이트한 최악 시간 바운드를 계산 할 수 있다. 또한 고정 우선순위 선점 비선점 스케줄링을 지원 함으로 인해 폭넓은 모델링 환경을 제공하여, ECU와 CAN으로 이루어진 차량 시스템들을 분석하는데 용이하다. STBA 분석방법은 그래프 토폴로지와 스케줄링 시나리오를 기반으로 하여 각 태스크의 스케줄 시간 바운드 값인 (minimum start time, maximum start time) and (minimum finish time and maximum finish time) 값을 결과로 출력한다.
두 번째 방법은 최적의 WCRT 값을 찾는 방법이다. MILP 를 이용하여 접근하였다. MILP는 최적화 문제의 최적해를 찾는 잘 알려진 방법이다. 우리는 WCRT 문제를 최적화 문제로 치환하여 MILP 기술을 적용하였다. 태스크 스케줄링을 MILP의 리니어 수식으로 표현하는 것이 핵심적인 기술이라고 할 수 있다. MILP 는 기본적으로 기하급수적인 시간 복잡도를 가지기 때문에, 문제의 복잡도가 조금 증가 할수록, 즉 태스크 그래프가 복잡할수록, 최적화에 소모되는 시간이 많이 증가한다. 따라서 우리는 STBA 분석 결과로부터 MILP 시간을 단축시키기 위해 변수들의 범위를 제한하였다.
세번째 방법은 메타 휴리스틱 알고리즘을 이용하는 방법이다. 두번째 방법에서 MILP 대신 메타 휴리스틱 알고리즘, 즉 예를 들면 유전 알고리즘을 이용하여 최적화 문제를 푸는 방법이다. 메타 휴리스틱은 항상 최적해를 구할 수 있다는 보장이 없지만, MILP 에 비해 구하고자 하는 최적해의 수준을 조절 할 수 있다는 장점이 있다. 그러므로 완전히 정확한 WCRT 값을 구할 필요가 없다면 메타 휴리스틱 방법을 이용하여 WCRT 값을 적절한 시간 안에 분석 할 수 있다. 집단 기반 메타 휴리스틱 알고리즘을 이용하기 때문에, 집단이 최적해에 근접하였을 때, 집단을 구성하는 모든 개체들이 최악의 시나리오에 근접하는 테스트 시나리오라고 생각 할 수 있다. 따라서 메타 휴리스틱 방법을 이용하면, 여러가지 최악 시나리오를 얻을 수 있다.
많은 실험들을 통해서 우리가 제안하는 방법의 타당성을 검증하였고, 실제 자동차 응용에 적용해 봄으로써 우리가 제안하는 알고리즘의 실제로 적용 가능한 수준임을 보였다.

목차 (Table of Contents)

• Chapter 1 Introduction 1
• 1.1 Motivation 1
• 1.2 Contribution 3
• 1.3 Architectural Scope of this Research 5
• 1.4 Thesis Organization 6
• Chapter 2 Related Work 7
• 2.1 Introduction 7
• 2.2 Background 10
• 2.2.1 Base schedulability analysis of single processor 10
• 2.2.2 Response time analysis of single processor 11
• 2.3 Holistic approach 12
• 2.3.1 Response time analysis based approach 12
• 2.3.2 Model-checking based approach 15
• 2.4 Compositional approach 22
• 2.4.1 SymTA/S approach 23
• 2.4.2 MPA approach 25
• 2.5 Summary 31
• Chapter 3 A Hybrid Methodology of Performance Analysis 33
• 3.1 Overall structure of analysis framework 33
• 3.2 Problem definition 35
• 3.2.1 Task and architecture model 35
• 3.2.2 Summary of Input and Objective 38
• 3.2.3 Notation Summary 38
• 3.3 Proposed analytical method: STBA algorithm 40
• 3.3.1 Basic algorithm of STBA 40
• 3.3.2 Timing bound computation 45
• 3.3.3 Making the time bounds tighter 53
• 3.4 Proposed optimal method: MILP based analysis 59
• 3.4.1 MILP formulation 59
• 3.5 Hybridization of analytical and optimal methods 72
• 3.6 Extension to multiple task graph 73
• 3.6.1 Considering jitter 75
• 3.7 Experiments 75
• 3.7.1 Simple examples 76
• 3.7.2 Random examples 80
• 3.7.3 Case Studies 86
• 3.8 Summary 89
• Chapter 4 A Meta-Heuristic based Performance Analysis 91
• 4.1 Introduction 91
• 4.2 Proposed solution for performance analysis 92
• 4.3 Experiments 94
• Chapter 5 Conclusion and Future Work 97
• Bibliography 99
• Appendix 106