Determination of Worst-Case Data Using an Adaptive Surrogate Model for Real-Time System

The estimation of worst-case execution time (WCET) is a critical activity in the analysis of real-time systems. Evolutionary algorithms are frequently employed for the determination of worst-case data, used in the estimation of WCET. However, in order to employ an evolutionary algorithm, several executions of the application program are required, either on the target hardware or using its simulator. Multiple executions of the application program consume a huge amount of time. In order to reduce the huge execution time, this paper proposes the use of an adaptive surrogate model. The initial training of surrogate model is performed with a cycle-accurate simulator. The initially trained model is then used to assist the evolutionary algorithm by predicting the execution time of an application program. However, contrary to the direct training approach, the surrogate model in this paper is updated (adapted) during the evolution process. The adaptive training of a surrogate model increases its prediction accuracy and reduces the overall time. The validity of proposed methodology is illustrated with multiple sorting algorithms, extensively used in real-time systems.