A Worst-Case Execution Time Analysis Approach Based on Independent Paths for ARM Programs  

作　　者：KONG Liangliang JIANG Jianhui 

机构地区：[1]School of Software Engineering,Tongji University,Shanghai 201804,China

出　　处：《Wuhan University Journal of Natural Sciences》2012年第5期391-399,共9页武汉大学学报（自然科学英文版）

基　　金：Supported by the National High Technology Research and Development Program of China(863 Program,2009AA011705);the National Natural Science Foundation of China(60903033)

摘　　要：To overcome disadvantages of traditional worst-case execution time （WCET） analysis approaches, we propose a new WCET analysis approach based on independent paths for ARM programs. Based on the results of program flow analysis, it reduces and partitions the control flow graph of the program and obtains a directed graph. Using linear combinations of independent paths of the directed graph, a set of feasible paths can be generated that gives complete coverage in terms of the program paths considered. Their timing measurements and execution counts of program segments are derived from a limited number of measurements of an instrumented version of the program. After the timing measurement of the feasible paths are linearly expressed by the execution times of program seg-ments, a system of equations is derived as a constraint problem, from which we can obtain the execution times of program segments. By assigning the execution times of program segments to weights of edges in the directed graph, the WCET estimate can be calculated on the basis of graph-theoretical techniques. Comparing our WCET estimate with the WCET measurement obtained by the exhaustive measurement, the maximum error ratio is only 8.259 3 %. It is shown that the proposed approach is an effective way to obtain the safe and tight WCET estimate for ARM programs.To overcome disadvantages of traditional worst-case execution time （WCET） analysis approaches, we propose a new WCET analysis approach based on independent paths for ARM programs. Based on the results of program flow analysis, it reduces and partitions the control flow graph of the program and obtains a directed graph. Using linear combinations of independent paths of the directed graph, a set of feasible paths can be generated that gives complete coverage in terms of the program paths considered. Their timing measurements and execution counts of program segments are derived from a limited number of measurements of an instrumented version of the program. After the timing measurement of the feasible paths are linearly expressed by the execution times of program seg-ments, a system of equations is derived as a constraint problem, from which we can obtain the execution times of program segments. By assigning the execution times of program segments to weights of edges in the directed graph, the WCET estimate can be calculated on the basis of graph-theoretical techniques. Comparing our WCET estimate with the WCET measurement obtained by the exhaustive measurement, the maximum error ratio is only 8.259 3 %. It is shown that the proposed approach is an effective way to obtain the safe and tight WCET estimate for ARM programs.

关 键 词：worst-case execution time independent path realtime system least squares ARM microprocessor 

分 类 号：TP302[自动化与计算机技术—计算机系统结构]