Name
Title | ||
|---|---|---|
An ILP-based Worst-case Performance Analysis Technique for Distributed Real-time Embedded Systems |
Abstract | ||
|---|---|---|
Finding a tight upper bound of the worst-case response time in a distributed real-time embedded system is a very challenging problem since we have to consider execution time variations of tasks, jitter of input arrivals, scheduling anomaly behavior in a multi-tasking system, all together. In this paper, we translate the problem as an optimization problem and propose a novel solution based on ILP (Integer Linear Programming). In the proposed technique, we formulate a set of ILP formulas in a compositional way for modeling flexibility, but solve the problem holistically to achieve tighter upper bounds. To mitigate the time complexity of the ILP method, we perform static analysis based on a scheduling heuristic to reduce the number of variables and confine the variable ranges. Preliminary experiments with the benchmarks used in the related work and a real-life example show promising results that give tight bounds in an affordable solution time. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1109/RTSS.2012.86 | RTSS |
Keywords | Field | DocType |
ilp-based worst-case performance analysis,scheduling anomaly,ilp method,scheduling,time complexity,problem holistically,anomaly behavior scheduling,distributed real-time embedded systems,ilp formula,worst-case response time,distributed real-time embedded system,input arrival jitter,integer programming,ilp-based worst-case performance analysis technique,linear programming,integer linear programming,multi-tasking system,multitasking system,optimization problem,computational complexity,static analysis,challenging problem,affordable solution time,task execution time variations,embedded systems,worst-case performance estimation,scheduling heuristic,execution time variation,distributed processing | Computer science,Real-time computing,Integer programming,Linear programming,Time complexity,Optimization problem,Distributed computing,Mathematical optimization,Fair-share scheduling,Least slack time scheduling,Dynamic priority scheduling,Embedded system,Computational complexity theory | Conference |
ISSN | ISBN | Citations |
1052-8725 | 978-1-4673-3098-5 | 6 |
PageRank | References | Authors |
0.52 | 12 | 6 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jinwoo Kim | 1 | 1918 | 168.52 |
| Hyunok Oh | 2 | 457 | 40.49 |
| Hyojin Ha | 3 | 16 | 1.10 |
| Shin-Haeng Kang | 4 | 93 | 5.16 |
| Junchul Choi | 5 | 49 | 4.34 |
| Soonhoi Ha | 6 | 1684 | 174.65 |