Research On The WCET Analysis Of Real-time Systems In Multi-core Platform

Analysis of Worst-Case Execution Time (WCET) for real-time applications aimsto obtain the worst-case execution time estimation before execution. For real-timesystems, especially hard real-time systems, WCET of real-time applications providesthe basis for scheduablity analysis and performance checking. With the rapiddevelopment of VLSI technology and the great increase of requirements, the multi-coreprocessors have become the processor mainstream and attract more and more attentionof real-time systems. However, multi-core processors increase the complexity of WCETanalysis due to the possible runtime inter-thread interferences in shared resources,especially shared hardware resources, such as shared cache or bus.To track this challenge, this thesis studies the real-time WCET analysis onmulti-core platforms. We start from the underlying shared hardware resources andanalyze their impact on WCET estimations. We have finally developed WCET analysismethods of real-time systems in multi-core platforms. The primary innovative works inthis thesis are listed as follows.1. We propose a model of static WCET analysis for real-time systems in multi-coreplatforms. Based on the mature WCET analysis flows for mono-core platforms, wepropose the WCET method by introducing the interference analysis of shared resources,on-chip (including shared cache and shared bus) and off-chip (including shared mainmemory) shared hardware resources. According to the analysis steps of static WCETmethods, the shared haredware resources are analyzed in microarchitecture analyis step.Then the impact of interference caused by shared hardware is taken into considerationon WCET estimations, which provides safe and tight WCET estimations. The proposedmodel can be used to guide the multi-core WCET analysis as well as the design andimplementation of WCET analysis tools.2. We develop a novel approach of shared cache interference. The traditionalmethod performs address analysis and assumes interference among instructions whichmapped into same cache line. The method is too conservative to provide tight WCETestimations. To track this problem, we consider the impact of instruction fetching timingon interference. The interference in shared cache is determined based on instructionfetching frames. Then the shared cache statuses are computed according to theinterference. Our approach can reasonably estimate the worst-case shared L2instructioncache misses by analyzing the timing relation to determine the latency of interferenceson shared cache. Theoretical analysis proves the validity of the approach. Experimentsresults indicate that the proposed approach improves the tightness of WCET estimation.3. We put forward an iterative approach for WCET estimations which considersthe circular dependency between shared bus and the runtime inter-thread interference in shared cache. The core idea is to consider the impact of shared bus on shared cacheaccess timings, which in turn affects the shared bus accesses. Therefore a reasonableinterference state can be obtained and the tightness of WCET estimations is improved.4. We put forward an interference analysis method based on access timing framesof off-chip shared memory. To track the problem of interference caused by off-chipmemroy, we introduce the exectuion graph to construct a memroy access graph. Thenwe compute the parent window and interference window to determine memory accesslatency. The parent window is used to analyze the impact among memory accesses,resulting resonable memory access latency. The inteference window is used to analyzethe interference among memory accesses from co-running threads, resulting resonableinterference latency. According to memroy access latency and interference latency, weobtain tight memory access overhead. Finally, tight WCET estimations can becomputed.5. We design and implement a WCET static analysis tool for multi-core processors.With the guidance of the proposed WCET analysis model, the methods proposed inChapters four, five and six are introduced to perform interference analysis in multi-coreprocessors. Then a WCET static analysis tool, named MCTA, is implemented. In orderto obtian tight WCET estimations, MCTA analyzes the impact of shared resourceinterference on WCET estimations as well as the mutual influence among themselves.The implementation of the WCET analysis tool and the experiment results show that theproposed techniques are effective. Meanwhile they can be applied to the design andimplementation of real-time systems in multi-core processors.