# WCET Analysis Based on Micro-Architecture Modeling for Embedded System Security
## 3 Design
### Prefetching Strategy  
In the previous two subsections, the analyses of the instruction cache and the dynamic branch predictor were performed independently. When analyzing the cache using the CCG, the impact of branch prediction on program execution time was ignored. Similarly, when analyzing the impact of branch prediction using HS, the influence of cache hits or misses due to the branch predictor was not considered. In reality, instruction cache prefetching occurs based on the predicted branch direction, which affects whether instructions hit the cache and, consequently, influences the program's execution time. In this paper, we assume that the processor can only allow one branch instruction to be in the prediction stage at any given time. This ensures that all previous instructions have finished executing before the branch instruction is processed.  
When branch prediction is incorrect, an invalid cache may cause a cache miss, resulting in delays. For this scenario, we introduce virtual nodes for the CCG. If the cache line blocks on the predicted path conflict with the other cache line blocks, virtual node \(B_{i,j}^{x}\) is introduced for cache basic block \(B_{(i,j)}\), to describe the mutual influence between branch prediction and instruction cache. \(x\) denotes the actual execution outcome of the branch instruction. If a cache line basic block along the predicted path does not conflict with other blocks, there is no need to add a virtual node. After adding virtual nodes, the CCG in Figure 4 is modified to the CCG shown in Figure 6. For branch instruction 2, when the actual execution is 0 but the prediction is 1, we do not need to add additional nodes because, in this scenario, instruction prefetching will proceed along the erroneous path and no instructions within basic block \(B_{2}\) conflict with other instructions. Similarly, for branch instruction 3, when the execution is 1 but the prediction is 0, we also do not need to add nodes. \(B_{3.1}^{(2,1)}\) denotes the impact on cache line 3.1 when the actual execution branch instruction 2 is 1, but the prediction is 0. The edge \(B_{1.2}\to B_{3.1}^{(2,1)}\) indicates that, due to the branch instruction 2 is predicted as 0, 3.1 is already in the cache. However, when instruction 1.2 is executed, the cache miss for 1.2 occurs because of 3.1. For edge \(B_{3.1}^{(2,1)}\to B_{3.1}\), when the prediction for branch instruction 2 is 0 but the execution is 1, the incorrect prediction results in instruction 3.1 being cached. This scenario actually improves the cache hit rate.  
After adding virtual nodes, the target equation is modified to Equation (15). \(delay\_b\) represents the total time consumed by the branch prediction. \(delay\_c\) denotes the total time consumed by the cache misses. The Equation illustrates that when a branch prediction error occurs, instruction prefetching will proceed along the erroneous path. Consequently, when the program executes along the correct path, at least one cache miss will occur. Here, \(l\) denotes the number of instructions fetched in a single prefetch operation.  
\[WCET=\sum_{i=1}^{N}[cost_{i}\times cnt_{i}+delay\_b+delay\_c]+\sum_{b\in Branch (P)}[cmp\times l]; \tag{15}\]  
\[delay\_b=bmp\timesbmi; \tag{16}\]  
\[delay\_c=\sum_{j=1}^{n_{i}}(cmp\times cm_{(i,j)}); \tag{17}\]