关键词: 最坏情况执行时间, 冲突检测, 实时软件

Abstract: A new program worst-case execution time estimation method with path conflict detection is proposed.Firstly，the method pre-computes program branch constraints，then converts these branch constraints to semantic conflicts between node-pair of Control Flow Graph（CFG） and saves these semantic conflicts into conflicts array of corresponding program in order to exclude impossible paths when searching path and improve searching path efficiency.The method finally selects path which has the maximum execution time from possible paths collection.Compared with some other former methods，this method can avoid high cost of all path enumeration and improve search efficiency while holding the same estimation precision.The experimental results show that the proposed method can efficiently and quickly give WCET estimation for high semantic dependency real-time programs.

Key words: Worst-Case Execution Time（WCET）, conflict detection, real-time software