Performance comparison of techniques on static path analysis of WCET

Mingsong Lv; Zonghua Gu; Nan Guan; Qingxu Deng; Ge Yu

doi:10.1109/EUC.2008.178

Performance comparison of techniques on static path analysis of WCET

Mingsong Lv, Zonghua Gu, Nan Guan, Qingxu Deng, Ge Yu

Research output: Chapter in book / Conference proceeding › Conference article published in proceeding or book › Academic research › peer-review

15 Citations (Scopus)

Abstract

Static path analysis is a key process of Worst Case Execution Time (WCET) estimation, the objective of which is to find the execution path that has the largest execution time. Currently, there is an argument in the research community whether model checking is another good solution for WCET analysis, besides ILP. To our knowledge, no paper so far has addressed this argument with real performance data. In this paper, we implement both ILP and model checking for static path analysis of WCET, and the experiment results show that ILP yields very good performance, while model checking only works well for simple programs, and it is inclined to scalability problems when dealing with programs that have complex structures and large loop counts.

Original language	English
Title of host publication	Proceedings of The 5th International Conference on Embedded and Ubiquitous Computing, EUC 2008
Pages	104-111
Number of pages	8
Volume	1
DOIs	https://doi.org/10.1109/EUC.2008.178
Publication status	Published - 1 Dec 2008
Externally published	Yes
Event	5th International Conference on Embedded and Ubiquitous Computing, EUC 2008 - Shanghai, China Duration: 17 Dec 2008 → 20 Dec 2008

Conference

Conference	5th International Conference on Embedded and Ubiquitous Computing, EUC 2008
Country/Territory	China
City	Shanghai
Period	17/12/08 → 20/12/08

Keywords

ILP
Model checking
Real-time
Static path analysis
WCET

ASJC Scopus subject areas

Computer Networks and Communications
Software
Communication

More information

10.1109/EUC.2008.178

Cite this

@inproceedings{7eeee0c2de6c4851a402d3c786878ccd,

title = "Performance comparison of techniques on static path analysis of WCET",

abstract = "Static path analysis is a key process of Worst Case Execution Time (WCET) estimation, the objective of which is to find the execution path that has the largest execution time. Currently, there is an argument in the research community whether model checking is another good solution for WCET analysis, besides ILP. To our knowledge, no paper so far has addressed this argument with real performance data. In this paper, we implement both ILP and model checking for static path analysis of WCET, and the experiment results show that ILP yields very good performance, while model checking only works well for simple programs, and it is inclined to scalability problems when dealing with programs that have complex structures and large loop counts.",

keywords = "ILP, Model checking, Real-time, Static path analysis, WCET",

author = "Mingsong Lv and Zonghua Gu and Nan Guan and Qingxu Deng and Ge Yu",

year = "2008",

month = dec,

day = "1",

doi = "10.1109/EUC.2008.178",

language = "English",

isbn = "9780769534923",

volume = "1",

pages = "104--111",

booktitle = "Proceedings of The 5th International Conference on Embedded and Ubiquitous Computing, EUC 2008",

note = "5th International Conference on Embedded and Ubiquitous Computing, EUC 2008 ; Conference date: 17-12-2008 Through 20-12-2008",

}

Lv, M, Gu, Z, Guan, N, Deng, Q & Yu, G 2008, Performance comparison of techniques on static path analysis of WCET. in Proceedings of The 5th International Conference on Embedded and Ubiquitous Computing, EUC 2008. vol. 1, 4756327, pp. 104-111, 5th International Conference on Embedded and Ubiquitous Computing, EUC 2008, Shanghai, China, 17/12/08. https://doi.org/10.1109/EUC.2008.178

Performance comparison of techniques on static path analysis of WCET. / Lv, Mingsong; Gu, Zonghua; Guan, Nan et al.
Proceedings of The 5th International Conference on Embedded and Ubiquitous Computing, EUC 2008. Vol. 1 2008. p. 104-111 4756327.

Research output: Chapter in book / Conference proceeding › Conference article published in proceeding or book › Academic research › peer-review

TY - GEN

T1 - Performance comparison of techniques on static path analysis of WCET

AU - Lv, Mingsong

AU - Gu, Zonghua

AU - Guan, Nan

AU - Deng, Qingxu

AU - Yu, Ge

PY - 2008/12/1

Y1 - 2008/12/1

N2 - Static path analysis is a key process of Worst Case Execution Time (WCET) estimation, the objective of which is to find the execution path that has the largest execution time. Currently, there is an argument in the research community whether model checking is another good solution for WCET analysis, besides ILP. To our knowledge, no paper so far has addressed this argument with real performance data. In this paper, we implement both ILP and model checking for static path analysis of WCET, and the experiment results show that ILP yields very good performance, while model checking only works well for simple programs, and it is inclined to scalability problems when dealing with programs that have complex structures and large loop counts.

AB - Static path analysis is a key process of Worst Case Execution Time (WCET) estimation, the objective of which is to find the execution path that has the largest execution time. Currently, there is an argument in the research community whether model checking is another good solution for WCET analysis, besides ILP. To our knowledge, no paper so far has addressed this argument with real performance data. In this paper, we implement both ILP and model checking for static path analysis of WCET, and the experiment results show that ILP yields very good performance, while model checking only works well for simple programs, and it is inclined to scalability problems when dealing with programs that have complex structures and large loop counts.

KW - ILP

KW - Model checking

KW - Real-time

KW - Static path analysis

KW - WCET

UR - http://www.scopus.com/inward/record.url?scp=63449125676&partnerID=8YFLogxK

U2 - 10.1109/EUC.2008.178

DO - 10.1109/EUC.2008.178

M3 - Conference article published in proceeding or book

SN - 9780769534923

VL - 1

SP - 104

EP - 111

BT - Proceedings of The 5th International Conference on Embedded and Ubiquitous Computing, EUC 2008

T2 - 5th International Conference on Embedded and Ubiquitous Computing, EUC 2008

Y2 - 17 December 2008 through 20 December 2008

ER -

Performance comparison of techniques on static path analysis of WCET

Abstract

Conference

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this