Accelerating worst case execution time analysis of timed automata models with cyclic behaviour. (November 2015)

• Record Type: Journal Article
• Authors: Al-Bataineh, Omar; Reynolds, Mark; French, Tim
• Is Part Of: Formal aspects of computing. Volume 27:Number 5(2015)
• Page Start: 917
• Page End: 949
• Publication Date: 2015-11
• Subjects: Worst-case execution time (WCET) -- Timed automata -- Model checking -- Zone abstraction; Computer science -- Periodicals; 004.05
• DOI: 10.1007/s00165-015-0340-4
• Languages: English
• ISSNs: 0934-5043

Abstract

Abstract The paper presents a new efficient algorithm for computing worst case execution time (WCET) of systems modelled as timed automata (TA). The algorithm uses a set of abstraction techniques that improve significantly the efficiency of WCET analysis of TA models with cyclic behaviour. We show that the proposed abstractions are exact with respect to the WCET problem in the sense that the WCET computed in the abstract model is equal to the one computed in the concrete model. We also compare our algorithm with the one implemented in the model checker UPPAAL which shows that when infinite cycles exist (i.e. cycles that can be run infinitely often), UPPAAL's algorithm may not terminate, and when largely repetitive finite cycles exist (i.e. cycles that can be run a large number of times but finite), UPPAAL's algorithm suffers from the state space explosion, thus leading to a low efficiency or resource exhaustion.