Name
Abstract | ||
|---|---|---|
In the past decades, embedded system designers moved from simple, predictable system designs towards complex systems equipped with caches, branch prediction units and speculative execution. This step was necessary in order to fulfill increasing requirements on computational power. Static analysis techniques considering such speculative units had to be developed to allow the estimation of an upper bound of the execution time of a program. This bound is called worst-case execution time (WCET). Its knowledge is crucial to verify whether hard real-time systems satisfy their timing constraints, and the WCET is a key parameter for the design of embedded systems. In this paper, we propose a WCET-driven branch prediction aware optimization which reorders basic blocks of a function in order to reduce the amount of jump instructions and mispredicted branches. We employed a genetic algorithmwhich rearranges basic blocks in order to decrease the WCET of a program. This enables a first estimation of the possible optimization potential at the cost of high optimization runtimes. To avoid time consuming repetitive WCET analyses, we developed a new algorithm employing integer-linear programming (ILP). The ILP models the worst-case execution path (WCEP) of a program and takes branch prediction effects into account. This algorithm enables short optimization runtimes at slightly decreased optimization results. In a case study, the genetic algorithm is able to reduce the benchmarks' WCET by up to 24.7% whereas our ILP-based approach is able to decrease the WCET by up to 20.0%. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1145/2038698.2038724 | CASES |
Keywords | Field | DocType |
wcet-driven branch prediction,execution time,high optimization runtimes,aware optimization,speculative execution,optimization result,basic block,aware code positioning,possible optimization potential,time consuming repetitive wcet,worst-case execution path,short optimization runtimes,branch prediction,upper bound,static analysis,performance,worst case execution time,genetic algorithm,complex system,integer programming,satisfiability,linear programming,software engineering,system design,embedded system,embedded systems,genetic algorithms,genetics | Complex system,Upper and lower bounds,Computer science,Speculative execution,Parallel computing,Static analysis,Real-time computing,Integer programming,Linear programming,Genetic algorithm,Branch predictor | Conference |
Citations | PageRank | References |
3 | 0.40 | 14 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sascha Plazar | 1 | 95 | 4.71 |
| Jan Kleinsorge | 2 | 3 | 0.40 |
| Heiko Falk | 3 | 462 | 31.54 |
| Peter Marwedel | 4 | 1904 | 184.40 |