mdh.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Identifying irreducible loops in the Instrumentation Point Graph
Mälardalen University, School of Health, Care and Social Welfare.
Rapita Syst Ltd, IT Ctr, York, England.
2011 (English)In: Journal of systems architecture, ISSN 1383-7621, E-ISSN 1873-6165, Vol. 57, no 7, 720-733 p.Article in journal (Refereed) Published
Abstract [en]

The Instrumentation Point Graph (IPG) is a program model whose primary usage is within hybrid measurement-based frameworks that compute Worst-Case Execution Time (WCET) estimates. The IPG represents the transitions between instrumentation points (Ipoints) that are inserted into the program to collect measurements at run time. However, uncontrolled Ipoint placement often causes the resultant IPG to contain unstructured (i.e. irreducible) loops, potentially compromising the safety of WCET estimates unless the hierarchical containment among IPG loops can be correctly identified. The contributions of this paper are fourfold: (1) we show that the IPG is more susceptible to irreducibility even when the program itself is well structured; (2) we demonstrate that state-of-the-art loop detection algorithms, designed specifically to handle irreducible loops, generally fail to construct the correct hierarchical relationship between IPG loops; (3) we present an algorithm that identifies arbitrary irreducible loops in the IPG during its construction from another graph-based model, an extended type of Control Flow Graph (CFG) called the CFG(+); (4) we show how the structural relation between the IPG and the CFG(+) allows loop bounds obtained through static analysis to be transferred onto the IPG. (C) 2011 Elsevier B.V. All rights reserved.

Place, publisher, year, edition, pages
2011. Vol. 57, no 7, 720-733 p.
Keyword [en]
Instrumentation Point Graph, WCET analysis, Reducibility
National Category
Engineering and Technology
Identifiers
URN: urn:nbn:se:mdh:diva-15539DOI: 10.1016/j.sysarc.2011.03.002ISI: 000293939100005Scopus ID: 2-s2.0-79960276527OAI: oai:DiVA.org:mdh-15539DiVA: diva2:562285
Available from: 2012-10-23 Created: 2012-10-10 Last updated: 2013-04-05Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus
By organisation
School of Health, Care and Social Welfare
In the same journal
Journal of systems architecture
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar

Altmetric score

Total: 27 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf