Worst Case Execution Time Estimation

Worst Case Execution Time Estimation

Speaker Dr. Y.N. Srikant,
Department of Computer Science and Automation
Indian Institute of Science
Bangalore, India
CECS Host Nikil Dutt
Location Donald Bren Hall (DBH) 4011
Date & Time February 10, 2011
Refreshments at 1:30 pm, Lecture begins at 2:00pm
Abstract Estimation of worst case execution time of programs is extremely important in the context of real time systems where the correctness of the system depends not only on the computations performed, but also on the timing of such computations. For task scheduling on such systems, it is necessary to know whether the task can execute to completion within a predetermined time interval. Thus, given a program and a target architecture, the WCET problem is to estimate a bound on the maximum execution time taken by the program for any input data set. 

WCET estimation is usually required to be safe and tight. Static analysis based techniques for WCET estimation use micro-architectural models for the target architecture and abstract interpretation for program analysis. Their results are safe but are not very tight. Measurement based techniques estimate the execution time for basic blocks by actual execution, and then combine the results using integer linear programming. These results are tighter but not safe.

In this talk, an overview of a probabilistic scheme for WCET estimation, which is a hybrid of static and measurement based methods is presented. Preliminary results on a novel measurement based technique using program phases will also be presented.

Biography

Y.N. Srikant received his B.E in Electronics from Bangalore University, and M.E and Ph.D in Computer Science from the Computer Science and Automation department of the Indian Institute of Science. He was the recipient of Young Scientist medal of the Indian National Science Academy in 1988. Srikant is currently a Professor in the Department of Computer Science and Automation at the Indian Institute of Science in Bangalore. He was the chair of the CSA department from 2000-05.

His area of interest is compiler design. He is the editor of a handbook on advanced compiler design published by CRC Press in 2002 and 2008 (2nd ed.). His most recent research includes compiler and runtime optimizations for reducing energy consumption in embedded systems and performance estimation of programs through program analysis.