Reducing WCET Overestimations by Correcting Errors in Loop Bound Constraints
In order to reduce overestimations of worst-case execution time (WCET), in this article, we firstly report a kind of specific WCET overestimation caused by non-orthogonal nested loops. Then, we propose a novel correction approach which has three basic steps. The first step is to locate the worst-cas...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2017-12-01
|
| Series: | Energies |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1996-1073/10/12/2113 |
| _version_ | 1811187879892746240 |
|---|---|
| author | Fanqi Meng Xiaohong Su |
| author_facet | Fanqi Meng Xiaohong Su |
| author_sort | Fanqi Meng |
| collection | DOAJ |
| description | In order to reduce overestimations of worst-case execution time (WCET), in this article, we firstly report a kind of specific WCET overestimation caused by non-orthogonal nested loops. Then, we propose a novel correction approach which has three basic steps. The first step is to locate the worst-case execution path (WCEP) in the control flow graph and then map it onto source code. The second step is to identify non-orthogonal nested loops from the WCEP by means of an abstract syntax tree. The last step is to recursively calculate the WCET errors caused by the loose loop bound constraints, and then subtract the total errors from the overestimations. The novelty lies in the fact that the WCET correction is only conducted on the non-branching part of WCEP, thus avoiding potential safety risks caused by possible WCEP switches. Experimental results show that our approach reduces the specific WCET overestimation by an average of more than 82%, and 100% of corrected WCET is no less than the actual WCET. Thus, our approach is not only effective but also safe. It will help developers to design energy-efficient and safe real-time systems. |
| first_indexed | 2024-04-11T14:11:06Z |
| format | Article |
| id | doaj.art-3dafb00f9e4a46d09c61a89f500f31c8 |
| institution | Directory Open Access Journal |
| issn | 1996-1073 |
| language | English |
| last_indexed | 2024-04-11T14:11:06Z |
| publishDate | 2017-12-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Energies |
| spelling | doaj.art-3dafb00f9e4a46d09c61a89f500f31c82022-12-22T04:19:42ZengMDPI AGEnergies1996-10732017-12-011012211310.3390/en10122113en10122113Reducing WCET Overestimations by Correcting Errors in Loop Bound ConstraintsFanqi Meng0Xiaohong Su1School of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001, ChinaSchool of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001, ChinaIn order to reduce overestimations of worst-case execution time (WCET), in this article, we firstly report a kind of specific WCET overestimation caused by non-orthogonal nested loops. Then, we propose a novel correction approach which has three basic steps. The first step is to locate the worst-case execution path (WCEP) in the control flow graph and then map it onto source code. The second step is to identify non-orthogonal nested loops from the WCEP by means of an abstract syntax tree. The last step is to recursively calculate the WCET errors caused by the loose loop bound constraints, and then subtract the total errors from the overestimations. The novelty lies in the fact that the WCET correction is only conducted on the non-branching part of WCEP, thus avoiding potential safety risks caused by possible WCEP switches. Experimental results show that our approach reduces the specific WCET overestimation by an average of more than 82%, and 100% of corrected WCET is no less than the actual WCET. Thus, our approach is not only effective but also safe. It will help developers to design energy-efficient and safe real-time systems.https://www.mdpi.com/1996-1073/10/12/2113real-time systemsoftware safetyWCET analysisworst-case execution pathloop bound |
| spellingShingle | Fanqi Meng Xiaohong Su Reducing WCET Overestimations by Correcting Errors in Loop Bound Constraints Energies real-time system software safety WCET analysis worst-case execution path loop bound |
| title | Reducing WCET Overestimations by Correcting Errors in Loop Bound Constraints |
| title_full | Reducing WCET Overestimations by Correcting Errors in Loop Bound Constraints |
| title_fullStr | Reducing WCET Overestimations by Correcting Errors in Loop Bound Constraints |
| title_full_unstemmed | Reducing WCET Overestimations by Correcting Errors in Loop Bound Constraints |
| title_short | Reducing WCET Overestimations by Correcting Errors in Loop Bound Constraints |
| title_sort | reducing wcet overestimations by correcting errors in loop bound constraints |
| topic | real-time system software safety WCET analysis worst-case execution path loop bound |
| url | https://www.mdpi.com/1996-1073/10/12/2113 |
| work_keys_str_mv | AT fanqimeng reducingwcetoverestimationsbycorrectingerrorsinloopboundconstraints AT xiaohongsu reducingwcetoverestimationsbycorrectingerrorsinloopboundconstraints |