基于WCET的多核共享资源冲突分析与约束研究

doi:10.11896/j.issn.1002-137X.2014.08.004

摘要/Abstract

摘要： 随着片上多核处理器在嵌入式实时系统中的应用,片上共享资源给任务的WCET分析带来诸多挑战,使得对多核共享资源冲突问题的研究变得非常重要。依据研究的目标,可以把目前已有的研究分为面向共享资源冲突分析和面向共享资源冲突约束两大类。对于面向共享资源冲突分析问题,探讨了不同共享资源冲突产生的原因,概括和比较了典型的冲突分析方法的优势和局限性；对于面向共享资源冲突约束问题,给出了其主要的研究内容,并评述和分析了几种主流的冲突约束方法。最后针对目前的研究状况指出了一些研究方向。

关键词: 片上多核处理器,最坏执行时间,冲突分析,冲突约束

Abstract: Chip multi-processor(CMP)is well suited to fulfill the increasing performance requirement of real-time embedded systems.However,the use of CMP introduces new challenges to WCET analysis due to conflicts of shared resources．In this paper,the newest research achievements about conflicts of shared resources were introduced and divided into two main categories,i.e.,conflict analysis and constraint conflict,based on their research objective．For the conflict analysis of shared resources,we discussed the different causes of shared resources conflict, compared and surveyed the limitation and superiority of different types of conflict analysis approaches．For constraint conflict, the major research directions were presented,meanwhile, several mainstream method of constraint conflicts were investigated and compared respectively．At last,several major issues and research direction of conflict of shared resources for further exploration were pointed out.

Key words: Chip multi-processor(CMP),Worst case execution time (WCET), Conflict analysis,Constraint conflict

甘志华,古志民,安立奎,赵鑫. 基于WCET的多核共享资源冲突分析与约束研究[J]. 计算机科学, 2014, 41(8): 19-24. https://doi.org/10.11896/j.issn.1002-137X.2014.08.004

GAN Zhi-hua,GU Zhi-min,AN Li-kui and ZHAO Xin. Research on Constraint Conflicts and Analysis of Shared Resources in CMP Based on WCET[J]. Computer Science, 2014, 41(8): 19-24. https://doi.org/10.11896/j.issn.1002-137X.2014.08.004

参考文献

[1] Quirk,William J.Verfication and Validation of Real-Time Soft-ware [M].New York:Springer-Verlag,1985
[2] Candra D,Guo Fei,Kim S,et al．Predicting inter-Thread Cache Contention on a Chip Multi-Processor Architecture [C]∥Proceeding of the 11th International Symposium on High-Perfor-mance Computer Architecture.2005:340-351
[3] Subramanian R,Smaragdakis Y,Loh G H,Adaptive caches:Effective shaping of cache behavior to workload[C]∥Proc of the 39th Annual IEEE/ACM into Symposium on Microarchitecture.2006:118-131
[4] Sha L,Abdelzaher T,arzen K-E,et al.Real-Time SchedulingTheory:A Historical Perspective [J]．Real-Time Systems,2004,28(2/3):101-155
[5] Cousot P,Cousot R．Interpretation:a Unified Lattice Model for Static Analysis of Programs by Construction or Approximation of Fix points [C]∥the Proceedings of ACM Symposium on Principles of Programming Language.1997:1-25
[6] Baier C,Katoen J-P．Principles of Model Checking [M].Cambridge,Massaehusetts:The MIT Press,2007
[7] Park C,Shaw A C．Experiment switches a Program Timing Tool Based on Source-Level Timing Schema [J]．IEEE Transactions on Computers,1991,4(5):48-57
[8] Tsun Y,Li S,Malik S．Performance Analysis of Embedded Software Using Implicit Path Enumeration [C]∥Workshop on Languages Compilers and Tools for Real-Time Systems.1995:456-461
[9] Stappert F,Ermedahl A,Engblom J.Efficient Longest Executable Path Search for Programs with Complex Flows and Pipeline Effects[R]．UPPsalaUniversity,2001
[10] Chattopadhyay S,Roychoudhury A,et al.Modeling Shared Cache and Bus in Multi-cores for Timing Analysis[C]∥13th International Workshop on Software and Compilers for Embedded Systems.Association for Computing Machinery,2010:1042-1053
[11] Kelter T,Falk H,Marwede P.Bus-Aware Multi-core WCET Analysis through TDMA Offset Bounds[C]∥23rd Euromicro Conference on Real-Time Systems.2011:3-12
[12] 陈芳园,张冬松,王志英．多核实时线程间干扰分析及WCET估值[J]．电子学报,2012(7):1372-1378
[13] Xie Yue-jian,Loh H．Dynamic classification of program memory behavior in CMPS[C]∥Proc of CMP-MSI:2^nd Workshop on Chip Multiprocessor Memory Systems and Interconnects in Conjunction with 35^th Symposium on Computer Architecture．2008:112-120
[14] Jia Xiao-min,Lu Ping-jing,Sun Cai-xia,et al.Dynamic Program Behavior Identification for High Performance CMPS with Private LLCS [J]．Transactions on Information and Systems,2010,3:3211-3218
[15] Yoon M-K,Kim J-E,Lui Sha.Optimizing Tunable WCET with Shared Resource Allocation and Arbitration in Hard Real-Time Multicore Systems[C]∥the 32nd IEEE Real-Time System Sym-posium(RTSS).2011:227-238
[16] Bourgade R,Rochange C,De Michie M,et al．MBBA:A Multi-Bandwidth Bus Arbiter for hard real-time[C]∥The 5th Confe-rence on Embedded and Multimedia Computing (EMC-10).2011:1101-1109
[17] Rosen J,Andrei A,Eles P,et al.Bus Access Optimization forPredictable Implementation of Real-Time Application on Multiprocessor Systems-on-Chip[C]∥28th IEEE International Real-Time Systems Symposium(RTSS).2007:49-60
[18] Rosen J,Neikter C-F,Eles P,et al.Bus Access Design for Combined Worst and Average Case Execution Time Optimization of Predictable Real-Time Application on Multiprocessor System-on-chip[C]∥17th IEEE Real-Time and Embedded Technology and Applications Symposium.2011:291-301
[19] MERASA(EU-FP7 Project)．www.merasa.org.2007
[20] Paolieri M,Quinones E,Francisco J,et al.Hardware Support for WCET analysis of hard Real-Time Multi-core Systems[C]∥Proceedings of International Symposium on Computer Architecture(ISCA2009).2009:56-68
[21] 贾小敏,张民选,齐树波,等.片上多核Cache资源管理机制研究[J].计算机科学,2011,38(1):295-301
[22] 王磊,刘道福,陈云雯,等.片上多核处理器共享资源分配与调度策略研究综述[J].计算机研究与发展,2013,50(10):21-32
[23] Suhendra V,Mitra T.Exploring Locking&Partitioning for predictable Shared Caches on Multi-Core[C]∥Proceedings of the 45^th annual Design Automation Conference.2008:300-303[23]Berna B,Puaut I.PDPA:Period Driven Task and Cache Partitioning Algorithm for Multi-Core Systems[C]∥20th International Conference on Real-Time and Network Systems.2012:237-246
[24] Bui B D,Caccamo M,Lui Sha.Impact of Cache Partitioning on Multi-Tasking Real-Time Embedded Systems[C]∥Proceeding of 14th International Conference on Embedded and Real-Time Computing Systems and Application.2008:101-110
[25] Liu Tian-tian,Zhao Ying-chao,Li Min-ming,et al.Joint TaskAssignment and Cache Partitioning with Cache Locking for WCET minimization on MPSoC [J].Journal of Parallel and Distributed Computing,2011,7(2):1473-1483
[26] Paolieri M,Quinones E,Cazorla F J,et al.IA³:An interference-aware allocation algorithm for Multi-core hard real-time systems[C]∥17^th IEEE Real-time and Embedded Technology and Applications Symposium.2011:280-290
[27] Anderson J,Calandrio J,Devi U.Real-time scheduling on multi-core platforms[C]∥2006 Proc of RTAS.2006:179-190
[28] Anderson J,Calandrino J.Parallel Real-time task scheduling on multi-core platforms[C]∥the 27st IEEE Real-Time Systems Symposium(RTSS)．2006:89-100
[29] Wang Ying-xin,Cui Yan,Tao Pin,et al.Reducing Shared Cache Contention by Scheduling Order Adjustment on Commodity Multi-Cores[C]∥2011 IEEE International Parallel & Distributed Processing Symposium.2011:984-992
[30] Yan J,Zhang W.WCET analysis for multi-core processors with shared L2 instruction caches[C]∥Proc of the 14^th IEEE Real-Time and Embedded Technology and Application Symposium.2008:1179-1186
[31] Zhang W,Yan J．Accurately estimating worst-case executiontime for multi-core processors with shared direct-mapped instruction caches[C]∥Proc of the 15^th IEEE Embedded and Real-time Computing Systems and Application.2009:455-463
[32] Lv Ming-song ,Wang Yi,Nan Guan,et al．Combining Interpretation with Model Checking for Timing Analysis of Multi-core Real-Time Software[C]∥the 31st IEEE Real-Time Systems Symposium (RTSS).2010:1176-1183
[33] Chen Fang-yuan,Zhang Dong-song,Wang Zhi-ying．Static analysis of run-time Inter-thread interference in shared Cache multi-core architecture based on instruction fetching timing[C]∥2011 Proceedings of IEEE International Conference on Computer Scienceand Automation Engineering.2011:208-212
[34] 陈芳园,张东松,林聪,等.基于取指执行时序范畴的多核共享Cache干扰分析[J].计算机研究与发展,2013,0(1):206-217
[35] Liang Y,Suhendra V．Timing analysis of concurrent programs running on shared cache multi-cores[C]∥Proc of the 30^th IEEE Real-Time System Symposium.2012:57-67

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed