Reconstructing critical paths from execution traces
conference paper
We consider the problem of constructing critical paths from incomplete information. In general, a directed acyclic graph of tasks with their execution times (i.e., a task graph) is necessary to extract critical paths. We assume, however, that only the set of tasks, and their start and end times are known, e.g., an execution trace in the form of a Gantt chart. This information can be extracted from real machines or from the output of analysis tools, whereas extraction of the exact task graph often is problematic due to imperative modeling formalisms and complicated platform semantics (resource allocation, varying execution
speeds). We show that, based on start and end times only, an overapproximation of the critical paths of an unknown task graph can be extracted nevertheless. Furthermore, this approach is generalized to deal with “noisy” execution traces of real machines in which control overhead is present. Finally, we discuss various methods to deal with false positives, and apply our approach to a complex industrial case study.
speeds). We show that, based on start and end times only, an overapproximation of the critical paths of an unknown task graph can be extracted nevertheless. Furthermore, this approach is generalized to deal with “noisy” execution traces of real machines in which control overhead is present. Finally, we discuss various methods to deal with false positives, and apply our approach to a complex industrial case study.
TNO Identifier
954308
ISBN
9780769549149
Publisher
IEEE
Article nr.
6417337
Source title
Proceedings - 15th IEEE International Conference on Computational Science and Engineering, CSE 2012 and 10th IEEE/IFIP International Conference on Embedded and Ubiquitous Computing, EUC 2012, 15th IEEE International Conference on Computational Science and Engineering, CSE 2012 and 10th IEEE/IFIP International Conference on Embedded and Ubiquitous Computing, EUC 2012, 5 December 2012 through 7 December 2012
Pages
524-531
Files
To receive the publication files, please send an e-mail request to TNO Repository.