m (Scipediacontent moved page Draft Content 591675720 to Engblom Jonsson 2007a) |
|||
| Line 3: | Line 3: | ||
When developing real-time systems, the worst-case execution time (WCET) is a commonly used measure for predicting and analyzing program and system timing behavior. Such estimates should preferrably be provided by static WCET analysis tools. Their analysis is made difficult by features of common processors, such as pipelines and caches.This paper examines the properties of single-issue in-order pipelines, based on a mathematical model of temporal constraints. The key problem addressed is to determine the distance (measured in number of subsequent instructions) over which an instruction can affect the timing behavior of other instructions, and when this effect must be considered in static WCET analysis. We characterize classes of pipelines for which static analysis can safely ignore effects longer than some arbitrary threshold. For other classes of pipelines, pipeline effects can propagate across arbitrary numbers of instructions, making it harder to design safe and precise analysis methods.Based on our results, we discuss how to construct safe WCET analysis methods. We also prove when it is correct to use localworst-case approximations to construct an overall WCET estimate. | When developing real-time systems, the worst-case execution time (WCET) is a commonly used measure for predicting and analyzing program and system timing behavior. Such estimates should preferrably be provided by static WCET analysis tools. Their analysis is made difficult by features of common processors, such as pipelines and caches.This paper examines the properties of single-issue in-order pipelines, based on a mathematical model of temporal constraints. The key problem addressed is to determine the distance (measured in number of subsequent instructions) over which an instruction can affect the timing behavior of other instructions, and when this effect must be considered in static WCET analysis. We characterize classes of pipelines for which static analysis can safely ignore effects longer than some arbitrary threshold. For other classes of pipelines, pipeline effects can propagate across arbitrary numbers of instructions, making it harder to design safe and precise analysis methods.Based on our results, we discuss how to construct safe WCET analysis methods. We also prove when it is correct to use localworst-case approximations to construct an overall WCET estimate. | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| Line 16: | Line 11: | ||
* [http://user.it.uu.se/~jakob/publications/engblom-emsoft-2002.pdf http://user.it.uu.se/~jakob/publications/engblom-emsoft-2002.pdf] | * [http://user.it.uu.se/~jakob/publications/engblom-emsoft-2002.pdf http://user.it.uu.se/~jakob/publications/engblom-emsoft-2002.pdf] | ||
| − | * [http://link.springer.com/content/pdf/10.1007/3-540-45828-X_25 http://link.springer.com/content/pdf/10.1007/3-540-45828-X_25],[http://dx.doi.org/10.1007/3-540-45828-x_25 http://dx.doi.org/10.1007/3-540-45828-x_25] under the license http://www.springer.com/tdm | + | * [http://link.springer.com/content/pdf/10.1007/3-540-45828-X_25 http://link.springer.com/content/pdf/10.1007/3-540-45828-X_25], |
| + | : [http://dx.doi.org/10.1007/3-540-45828-x_25 http://dx.doi.org/10.1007/3-540-45828-x_25] under the license http://www.springer.com/tdm | ||
| − | * [https://link.springer.com/chapter/10.1007 | + | * [https://link.springer.com/chapter/10.1007%2F3-540-45828-X_25 https://link.springer.com/chapter/10.1007%2F3-540-45828-X_25], |
| + | : [http://www.diva-portal.org/smash/record.jsf?pid=diva2:71805 http://www.diva-portal.org/smash/record.jsf?pid=diva2:71805], | ||
| + | : [https://dblp.uni-trier.de/db/conf/emsoft/emsoft2002.html#EngblomJ02 https://dblp.uni-trier.de/db/conf/emsoft/emsoft2002.html#EngblomJ02], | ||
| + | : [https://www.scipedia.com/public/Engblom_Jonsson_2007a https://www.scipedia.com/public/Engblom_Jonsson_2007a], | ||
| + | : [https://rd.springer.com/chapter/10.1007/3-540-45828-X_25 https://rd.springer.com/chapter/10.1007/3-540-45828-X_25], | ||
| + | : [https://academic.microsoft.com/#/detail/2122666034 https://academic.microsoft.com/#/detail/2122666034] | ||
Latest revision as of 14:44, 21 January 2021
Abstract
When developing real-time systems, the worst-case execution time (WCET) is a commonly used measure for predicting and analyzing program and system timing behavior. Such estimates should preferrably be provided by static WCET analysis tools. Their analysis is made difficult by features of common processors, such as pipelines and caches.This paper examines the properties of single-issue in-order pipelines, based on a mathematical model of temporal constraints. The key problem addressed is to determine the distance (measured in number of subsequent instructions) over which an instruction can affect the timing behavior of other instructions, and when this effect must be considered in static WCET analysis. We characterize classes of pipelines for which static analysis can safely ignore effects longer than some arbitrary threshold. For other classes of pipelines, pipeline effects can propagate across arbitrary numbers of instructions, making it harder to design safe and precise analysis methods.Based on our results, we discuss how to construct safe WCET analysis methods. We also prove when it is correct to use localworst-case approximations to construct an overall WCET estimate.
Original document
The different versions of the original document can be found in:
- http://dx.doi.org/10.1007/3-540-45828-x_25 under the license http://www.springer.com/tdm
Document information
Published on 01/01/2007
Volume 2007, 2007
DOI: 10.1007/3-540-45828-x_25
Licence: CC BY-NC-SA license
Share this document
Keywords
claim authorship
Are you one of the authors of this document?