【作者】 陈芳园；

【导师】 孙成政； 王志英；

【作者基本信息】 国防科学技术大学 ， 计算机科学与技术， 2011， 博士

【摘要】 实时程序最坏情况执行时间（Worst-Case Execuion Time, WCET）分析是指在程序或者程序片段执行之前获得其最坏情况的执行时间估值。事先获知任务的WCET估值是实时系统进行调度及可调度性分析的前提，也是检查实时系统性能是否满足要求的依据。随着VLSI技术的发展，多核处理器已经取代单核处理器成为时代的主流。而实时领域由于应用需求的提高开始对高性能的多核处理器投入越来越多地关注。但是，在多核处理器中，任务在访问硬件共享资源时会产生干扰，一个任务的执行时间可能会受到并行任务的影响。较之于体系结构简单的单核处理器而言，多核处理器在体系结构上对实时系统WCET分析提出了更多的挑战和难题。本文从影响多核处理器可预测性的硬件共享资源入手，深入研究了引起干扰的硬件共享资源对WCET估值的影响：片上共享资源（共享Cache、片上互连）和片外共享资源（片外共享存储），提出了基于多核处理器平台的实时系统WCET分析方法。所取得的研究成果主要包括：1、提出了一种基于多核处理器平台的实时系统WCET静态分析模型。该模型借鉴成熟的单核WCET静态分析流程，在底层微体系结构分析中综合考虑片上共享资源和片外共享资源干扰对实时任务执行时间的影响，以及共享资源干扰之间的相互影响。该模型用于指导后续的多核共享资源干扰分析、WCET计算和基于多核处理器平台的WCET分析工具的设计与实现。2、提出了一种基于指令取指执行时序范畴的共享指令Cache干扰分析方法。该方法考虑线程控制逻辑和执行时序对干扰的影响，基于指令取指执行时序范畴判断并行线程间在共享Cache上的干扰状态。理论分析证明该方法的有效性，实验结果表明，该方法在保守的地址映射分析方法的基础上可以更合理地分析共享Cache干扰，从而获得更精确的WCET估值。3、提出了一种迭代的共享总线干扰分析方法。针对共享Cache和共享总线的多核结构，综合考虑共享总线干扰和共享Cache干扰对线程WCET估值的影响以及二者之间的相互影响，以获得更精确的WCET估值。其核心思想是根据本文提出的基于指令取指执行时序范畴的共享Cache干扰分析方法，考虑共享总线对共享Cache访问时序的影响以及共享Cache干扰状态对共享总线的访问影响，确定合理的共享Cache和共享总线干扰状态，通过收敛的迭代分析方法获得更精确的WCET估值。4、提出了一种基于访问时序范畴的片外共享存储访问干扰分析方法。该方法针对并行线程竞争访问片外共享存储引起的干扰问题，借鉴执行图的思想构建线程存储访问图，在此基础上确定父辈窗口和干扰窗口：通过父辈窗口分析存储访问操作之间的影响以确定合理的线程存储访问延迟，通过干扰窗口分析并行线程间片外共享存储访问干扰，从而获得合理的、更精确的存储访问时间开销。该方法不仅考虑了线程内的存储访问请求之间的影响，而且基于时序范畴更好的分析了并行线程间的存储访问请求干扰。5、设计并实现了基于多核处理器平台的实时系统WCET静态分析工具MCTA。基于前面提出的干扰分析方法，在多核处理器平台的实时系统WCET静态分析模型的指导下，设计并实现了面向多核处理器的WCET静态分析工具MCTA。MCTA在底层微体系结构分析中考虑共享资源干扰对WCET估值的影响以及干扰之间的相互影响，以此获得更精确的WCET估值。WCET分析工具的实现、实验验证和评估结果表明，本文提出的上述技术是有效的，能够很好地应用于多核处理器在实时系统中的设计和实现。更多还原

【Abstract】 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.更多还原