Improving and Estimating the Precision of Bounds on the Worst-Case Latency of Task Chains.
Saved in:
| Title: | Improving and Estimating the Precision of Bounds on the Worst-Case Latency of Task Chains. |
|---|---|
| Authors: | Girault, Alain, Prevot, Christophe, Quinton, Sophie, Henia, Rafik, Sordon, Nicolas |
| Source: | IEEE Transactions on Computer-Aided Design of Integrated Circuits & Systems. Nov2018, Vol. 37 Issue 11, p2578-2589. 12p. |
| Subjects: | Embedded computer system design & construction, Microprocessor design & construction, Mathematical bounds, Real-time computing, Computer scheduling, Industrial design |
| Abstract: | One major issue that hinders the use of performance analysis in industrial design processes is the pessimism inherent to any analysis technique that applies to realistic system models. Indeed, such analyses may conservatively declare unschedulable systems that will in fact never miss any deadlines. We advocate the need to compute not only tight upper bounds on worst-case behaviors but also tight lower bounds. As a first step, we focus on uniprocessor systems executing a set of sporadic or periodic hard real-time task chains. Each task has its own priority, and the chains are scheduled according to the fixed-priority pre-emptive scheduling policy. Computing the worst-case end-to-end latency (WCEL) of each chain is complex because of the intricate relationship between the task priorities. Compared to the state of the art, our analysis provides upper bounds on the WCEL in the more general case of asynchronous task chains, and also provides lower bounds on the WCEL both for synchronous and asynchronous chains. Our computed lower bounds correspond to actual system executions exhibiting a behavior that is as close to the worst case as possible, while all other approaches rely on simulations. Extensive experiments show the relevance of lower bounds on the worst-case behavior for the industrial design of real-time embedded systems. [ABSTRACT FROM AUTHOR] |
| Copyright of IEEE Transactions on Computer-Aided Design of Integrated Circuits & Systems is the property of IEEE and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
| FullText | Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 132478535 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Improving and Estimating the Precision of Bounds on the Worst-Case Latency of Task Chains. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Girault%2C+Alain%22">Girault, Alain</searchLink><br /><searchLink fieldCode="AR" term="%22Prevot%2C+Christophe%22">Prevot, Christophe</searchLink><br /><searchLink fieldCode="AR" term="%22Quinton%2C+Sophie%22">Quinton, Sophie</searchLink><br /><searchLink fieldCode="AR" term="%22Henia%2C+Rafik%22">Henia, Rafik</searchLink><br /><searchLink fieldCode="AR" term="%22Sordon%2C+Nicolas%22">Sordon, Nicolas</searchLink> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22IEEE+Transactions+on+Computer-Aided+Design+of+Integrated+Circuits+%26+Systems%22">IEEE Transactions on Computer-Aided Design of Integrated Circuits & Systems</searchLink>. Nov2018, Vol. 37 Issue 11, p2578-2589. 12p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Embedded+computer+system+design+%26+construction%22">Embedded computer system design & construction</searchLink><br /><searchLink fieldCode="DE" term="%22Microprocessor+design+%26+construction%22">Microprocessor design & construction</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematical+bounds%22">Mathematical bounds</searchLink><br /><searchLink fieldCode="DE" term="%22Real-time+computing%22">Real-time computing</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+scheduling%22">Computer scheduling</searchLink><br /><searchLink fieldCode="DE" term="%22Industrial+design%22">Industrial design</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: One major issue that hinders the use of performance analysis in industrial design processes is the pessimism inherent to any analysis technique that applies to realistic system models. Indeed, such analyses may conservatively declare unschedulable systems that will in fact never miss any deadlines. We advocate the need to compute not only tight upper bounds on worst-case behaviors but also tight lower bounds. As a first step, we focus on uniprocessor systems executing a set of sporadic or periodic hard real-time task chains. Each task has its own priority, and the chains are scheduled according to the fixed-priority pre-emptive scheduling policy. Computing the worst-case end-to-end latency (WCEL) of each chain is complex because of the intricate relationship between the task priorities. Compared to the state of the art, our analysis provides upper bounds on the WCEL in the more general case of asynchronous task chains, and also provides lower bounds on the WCEL both for synchronous and asynchronous chains. Our computed lower bounds correspond to actual system executions exhibiting a behavior that is as close to the worst case as possible, while all other approaches rely on simulations. Extensive experiments show the relevance of lower bounds on the worst-case behavior for the industrial design of real-time embedded systems. [ABSTRACT FROM AUTHOR] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>Copyright of IEEE Transactions on Computer-Aided Design of Integrated Circuits & Systems is the property of IEEE and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=132478535 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1109/TCAD.2018.2861016 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 12 StartPage: 2578 Subjects: – SubjectFull: Embedded computer system design & construction Type: general – SubjectFull: Microprocessor design & construction Type: general – SubjectFull: Mathematical bounds Type: general – SubjectFull: Real-time computing Type: general – SubjectFull: Computer scheduling Type: general – SubjectFull: Industrial design Type: general Titles: – TitleFull: Improving and Estimating the Precision of Bounds on the Worst-Case Latency of Task Chains. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Girault, Alain – PersonEntity: Name: NameFull: Prevot, Christophe – PersonEntity: Name: NameFull: Quinton, Sophie – PersonEntity: Name: NameFull: Henia, Rafik – PersonEntity: Name: NameFull: Sordon, Nicolas IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 11 Text: Nov2018 Type: published Y: 2018 Identifiers: – Type: issn-print Value: 02780070 Numbering: – Type: volume Value: 37 – Type: issue Value: 11 Titles: – TitleFull: IEEE Transactions on Computer-Aided Design of Integrated Circuits & Systems Type: main |
| ResultId | 1 |
