A Declarative Compositional Timing Analysis for Multicores Using the Latency-Rate Abstraction
Ref: CISTER-TR-130108 Publication Date: 21 to 22, Jan, 2013
A Declarative Compositional Timing Analysis for Multicores Using the Latency-Rate Abstraction
Ref: CISTER-TR-130108 Publication Date: 21 to 22, Jan, 2013Abstract:
This paper presents a functional model for timing analysis by abstract interpretation, used for estimation of worst-case execution times (WCET) in multicore architectures using a denotational semantics. The objective aims at surpassing the intrinsic computational complexity of timing analysis of multiple processing units sharing common resources. For this purpose, we propose a novel application of latency-rate (LR) servers, phrased in terms of abstract interpretation, to achieve timing compositionality on requests to shared resources. The soundness of the approach is proven with respect to a calculational fi xpoint semantics for multicores that is able to express all possible ways in which a shared resource can be accessed. Experimental results show that the loss in precision introduced by the LR server model is about 10% on average and is fairly compensated by the gain in analysis time, which is above 99%. The system is implemented in Haskell, taking advantages of the declarative features of the language for a simpler and more robust specifi cation of the underlying concepts.
Vitor Rodrigues
Benny ÅkessonDocument:
View
Download15th International Symposium on Practical Aspects of Declarative Languages (PADL '13), Springer Berlin Heidelberg, Edited: Kostis Sagonas, 7752, pp 43-59.
Rome, Italy.
DOI:10.1007/978-3-642-45284-0_4.
Record Date: 15, Jan, 2013