基于取指执行时序范畴的多核共享Cache干扰分析  

Analysis of Inter-Thread Interference on Shared Cache Multi-Core Architectures Based on Instruction Fetch Timing Frame

作　　者：陈芳园[1] 张冬松[2] 刘聪[1] 王志英[1] 

机构地区：[1]国防科学技术大学计算机学院,长沙410073 [2]国防科学技术大学并行与分布处理国家重点实验室,长沙410073

出　　处：《计算机研究与发展》2013年第1期206-217,共12页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(61272097);高等学校博士学科点专项科研基金项目(20104307110005);国防科学技术大学优秀研究生创新资助项目(B100601);湖南省研究生科研创新资助项目(CX2010B026)

摘　　要：在多核结构中,获得并行应用线程的安全、精确的最坏情况执行时间(worst case execution time,WCET)的最大挑战之一在于共享资源的竞争冲突检测.在共享Cache的多核处理器中,线程在共享Cache中的指令可能被其他并行线程的指令替换,从而导致了线程间在共享Cache上的干扰,因此多核结构下线程WCET需要考虑并行线程间在共享Cache上的干扰.在现有的简单地址映射干扰分析基础上,考虑了指令取指执行时序因素对干扰的影响,提出了非干扰状态的充分不必要条件,根据指令的取指执行时序范畴判断线程在共享Cache上的干扰状态.通过排除非干扰状态,可以进一步精确多核结构中线程的WCET估值.理论分析证明了该方法的有效性.实验结果表明,与当前现有的考虑执行周期和基于逻辑访问先后顺序的方法相比,基于时序方法下的WCET估值分别可以提高12%和7%的精确度.In real-time systems, designers need to obtain a safe and tight worst-case execution time （WCET） of applications. It is very challenging for multi core processors due to the possible inter- thread interference caused by shared resources. For multi-core platforms with shared caches, instructions may be evicted by another co-running thread, which results in inter-thread interference in shared cache. In this case the execution time of applications can not be analyzed independently. The inter-thread interference should be taken into consideration in WCET analysis on multi-core platforms. This paper proposes a sufficient and unnecessary condition of non-interference to analyze the worst-case inter-thread interference by considering the timing frame of instruction fetch. Our approach introduces the consideration of timing frames into the conservative address analysis. Therefore, the worst-case shared cache misses can be reasonably estimated to determine the latency of inter-thread interference in shared cache. Our experiments indicate that the proposed approach improves the tightness of WCET estimation by 12~//00 as compared with the representative related work which proposes an lifetime-based method, and by 7 ~ as compared with another representative related work which is based on the structure order of shared cache accesses.

关 键 词：多核体系结构 共享CACHE 干扰 取指执行时序 最坏情况下执行时间 

分 类 号：TP302[自动化与计算机技术—计算机系统结构]