Research On Prediction Of Instruction Cache Behavior In Real-time Embedded System

With the expansion of the application field of real-time embedded systems,related research has received further attention.The worst-case execution time of the real-time task is one of the most important indicators to measure the performance of real-time embedded systems.Therefore,it is usually necessary to predict the instruction cache behavior in the system design stage to estimate the upper bound on the execution time of the real-time task accurately.Because the time delay of instruction cache behavior is the important part of the upper bound,the research emphasis for predicting instruction cache behavior is to identify cache hits and misses,and the goal is to estimate the time delay caused by the cache behavior.The instruction cache of modern embedded processors is very complex in terms of type,structure and usage.Real-time embedded systems may adopt different task scheduling modes.These factors will increase the difficulty of predicting the behavior of instruction cache.In view of this,based on dual-core and two-level typical architecture,under the two task scheduling modes that ?the task is fixed and repetitively runs periodically? and ?the task is constantly changing over time and repetitively runs periodically?,the thesis studies effective methods for predicting the instruction cache behavior.The work includes modeling the instruction cache behavior,verifying the correctness of the models,and solving the models,that is,estimating the time delay caused by the cache behavior.(1)The thesis studies the identification and capture of the key information needed for modeling the instruction cache behavior.It redefines the instruction classification method to identify the instruction type more accurately,designs the path pruning rules to reduce the time cost of identifying the instruction type as much as possible,re-analyzes the path pruning rules and designs a new path capture method in order to capture the access that may occur on the level 2 instruction cache.(2)The thesis analyzes the model characteristics of the instruction cache behavior under the mode that ?the task is fixed and repetitively runs periodically?,the deficiency of the correctness verification of the model and the challenge of the optimized solution of the model.Depending on the satisfiability modulo theories,it establishes the SMT model of the cache behavior delay,verifies the correctness of the model,designs the optimization algorithm and proves the optimality of the algorithm in theory.(3)The thesis analyzes the model characteristics of the instruction cache behavior under the mode that ?the task is constantly changing over time and repetitively runs periodically?,and the deficiency of the correctness verification of the model.Combined with the satisfiability modulo theories,it establishes the multi-period behavior delay model,and verifies the correctness of the model and the equivalence of model transformation.Based on evolutionary algorithm,it analyzes the different factors that may affect the optimized results,such as individual selection,mating and mutation,proposes the corresponding countermeasures and solves the model.The experimental results prove the following conclusions.(1)The instruction classification method using path pruning can complete the instruction classification more accurately with the acceptable time cost.(2)The new path capture method can guarantee the accurate prediction of high-level instruction cache access with the time cost that is lower than that of the original path capture method.(3)The satisfiability modulo theories not only enable accurate modeling of instruction cache behavior,but also facilitate automatic verification of the correctness and the equivalence transformation of the cache behavior model.(4)The optimization algorithm of the static multi-objective cache behavior model can obtain the optimized solution within the number of logarithmic iterations proved by theory.(5)The optimization algorithm of the dynamic multi-objective cache behavior model can make most of the selected benchmarks cache behavior results converge to the optimized solutions,and the closeness of the remaining few benchmarks cache behavior results to the optimized solution exceeds 98.5%.The main innovative contributions are as follows:(1)propose a modeling pre-process frame for instruction cache behavior,including a rule-based path sampling method and an accurate 2-level path capture method,which not only improves the accuracy of capturing the key information required for modeling,but also takes into account the time efficiency;(2)propose a method for predicting the instruction cache behavior based on SMT,which is not only easy to carry out automatic verification of model correctness,but also can efficiently compute the optimized solution;(3)propose a method for predicting the behavior of instruction cache based on the dynamic multi-objective modeling method,SMT and the evolutionary solving technology,which not only establishes the multi-period delay model of cache behavior and takes into account the correctness verification of the model,but also can compute the optimized solution.