Parametric timing estimation with Newton-Gregory formulae

This paper presents a novel method for parametric worst‐case execution time (WCET) estimation of loops. The method determines a parametric bound on the iteration space size of loops with both affine and non‐affine loop bounds in an efficient manner using a formulation based on Newton–Gregory interpo...

Full description

Saved in:
Bibliographic Details
Published in:Concurrency and computation 2006-09, Vol.18 (11), p.1435-1463
Main Authors: van Engelen, Robert A., Gallivan, Kyle A., Walsh, Burt
Format: Article
Language:English
Subjects:
code analysis
interpolation
parametric estimation
WCET
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper presents a novel method for parametric worst‐case execution time (WCET) estimation of loops. The method determines a parametric bound on the iteration space size of loops with both affine and non‐affine loop bounds in an efficient manner using a formulation based on Newton–Gregory interpolating polynomials. Parametric WCET formulae are used to support dynamic scheduling decisions at runtime, where the WCET of a scheduled task might not be known statically. To determine worst‐case execution time estimates of scientific and multimedia codes, which spent most of the execution time on executing loop iterations, efficient and accurate symbolic loop WCET estimation methods must be capable of analyzing loops with symbolic bounds, non‐rectangular loops, zero‐trip loops, loops with multiple critical paths, and loops with non‐unit strides. Copyright © 2006 John Wiley & Sons, Ltd.
ISSN:1532-0626
1532-0634
DOI:10.1002/cpe.1015