基于多核处理器平台的实时系统WCET分析研究
|
摘要
实时程序最坏情况执行时间（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分析工具的实现、实验验证和评估结果表明，本文提出的上述技术是有效的，能够很好地应用于多核处理器在实时系统中的设计和实现。
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.
本文从影响多核处理器可预测性的硬件共享资源入手，深入研究了引起干扰的硬件共享资源对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分析工具的实现、实验验证和评估结果表明，本文提出的上述技术是有效的，能够很好地应用于多核处理器在实时系统中的设计和实现。
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.
引文
[1] Nvidia Coporation. Fermi Compute Architecture White Paper [J].2009.
[2] ITRS. International Technology Roadmap for Semiconductors,2008update[R].Tech Report. ITRS2009[EB/OL]. http://public.itrs.net.
[3] ITRS. International Technology Roadmap for Semiconductors,2005edition [R].ITRS, April2005[EB/OL]. http://public.itrs.net.
[4] Burger D, Goodman J R. Billion-Transistor Architectures：There and Back Again[J]. IEEE Computer,2004,37(3):22-28.
[5] Karthikeyan Sankaralingam, Ramadass Nagarajan, et al. Exploiting ILP, TLP,and DLP with the Polymorphous TRIPS architecture [C]∥In Proceedings of the30th Annual International Symposium on Computer Architecture,2003.
[6] M. B. Taylor, Walter Lee, et al. Evaluation of the Raw Microprocessor: AnExposed-Wire-Delay Architecture for ILP and Streams [C]∥In Proceedings ofthe31th Annual International Symposium on Computer Architecture,2004.
[7] D. Pham et. al. The Design and Implementation of a First-Generation CELLProcessor [C]∥International Solid-State Circuits Conference Technical Digest,Feb.2005.
[8] Cameron McNairy, Rohit Bhatia. Montecito: A Dual-Core, Dual-Thread ItaniumProcessor[J]. IEEE Micro, vol.25, no.2, pp.10-20, Mar/Apr,2005.
[9] Asanovic, Krste and etc. The Landscape of Parallel Computing Research: AView from Berkeley[R]. UCB/EECS-2006-183,2006.
[10] Lance Hammond et al. The Stanford Hydra CMP[J]. IEEE Micro, v.20n.2,pp.71-84, March2000.
[11] Jane W.S. Liu. Real-Time Systems [M]. Prentice. Hall,2000.
[12] Robert I. Davis and Alan Burns. A Survey of Hard Real-Time SchedulingAlgorithms and Schedulability Analysis Techniques for Multiprocessor Systems[R]. University of York, Department of Computer Science Technical Report,YCS-2009-443, November2009.
[13] K. Hirata and J. Goodacre. Arm mpcore; the streamlined and scalable arm11processor core [C]∥Design Automation Conference,2007. ASP-DAC’07. Asiaand South Pacific, pages747~748, Jan.2007.
[14] Pham, D.C., et al. Overview of the Architecture, Circuit Design, and PhysicalImplementation of a First-generation cell processor [J]. IEEE Journal ofSolid-State Circuits.2006.41(l):179-196.
[15] P. Puschner and A. Burns. A Review of Worst-Case Execution-Time Analysis [J].Real-Time Systems,2/3:115-127,2000.
[16] Alan C. Shaw. Reasoning about time in highe level language software [J]. IEEETransactions on Software Engineering, July1989,15(7):875-889.
[17] Johann Blieberger. Data-flow framework for worst-case execution time analysis[J]. Real-Time Systems,2002,22:183-227.
[18] N. Holsti, T. Langbacka, and S. Saarinen. Worst-Case Execution-Time Analysisfor Digital Signal Processors [C]//In: Proc. Of the EUSIPCO2000Conference,September2000.
[19] Sung-Soo Lim, Young H.Bae, and et al．An Accurate Worst Case TimingAnalysis for RISC processors [J]. IEEE Transactions on Software Engineering,1995,2l(7):593-604.
[20] Jakob Engblom and Andreas Ermedahl. Pipeline timing analysis using atrace-driven simulator [C]//In Proc．6th International Conference on Real-TimeComputing Systems and Applications, Hong Kong, Dec.1999.
[21] C. A. Healy, D. B. Whalley, and M. G. Harmon．Integrating the Timing Analysisof Pipelining and Instruction Caching [C]//In: Proc. of the Sixteenth IEEEReal-Time Systems Symposium, December1995.288-297.
[22] F．Mueller and D．B．Whalley．Efficient On-the-fly Analysis of ProgramBehavior and Static Cache Simulation [C]//In: Static Analysis Symposium,B．LeCharlier, editor, volume864of lecture Notes in Computer Science,Springer, Sep1994,101-115.
[23] Robert D．Arnold,Frank Mueller,David Whalley,and Marion Harmon．BoundingWorst-Case Instruction Cache Performance [C]//In: Proc.15th Real-TimeSystems Symposium (RTSS), Brooloine, Massachusetts, Dec.1994.172-181.
[24] Frank Mueller．Generalizing Timing Predictions to Set-Associative Caches[C]//In: Workshop Oil Real-Time Systems．Jun．1997:64-71.
[25] Randall T．White and et al．Timing analysis for data Caches and set-associativeCaches [C]//In: Proc. Real-Time Technology and Applications Symposium,Jun.1997.192-202.
[26] Randall T. White, Frank Mueller,Christopher A. Healy, and Marion G．Harmo.Timing Analysis for Data Caches and Wrap Around Fill Caches[J]. Real-TimeSystems,November1999:209-233．
[27] Martin alt,Christi Ferdinand,Florian Martin,and Reinhurd wilhelm． Cachebehavior prediction by abstract interpretation [C]//In: Static AnalysisSymposium(sAs), LNCS l145, Springer,1996:52-66.
[28] Antoine Colin and Isabelle Puant. Worst case execution time analysis foraprocessor with branch prediction [J]. Real-Time Systems, May2000,18(2):249-274.
[29] Tulika Mitra and Abhik Roychoudhnry．A framework to model branch predictionfor wcet analysis [R]. TechnicalReport-01, National University ofSingapore(NUS), Nov.2001.
[30] Xianfeng Li,Tulika Mitra,Abhik Roychoudhury．Accurate Timing Analysis byModeling Caches Speculation and their Infraction [C]//In:40th ACM IEEEDesign Automation Conference(DAC),June2003.
[31] J. Schneider and C. Ferdinand．Pipeline behavior prediction for superscalarprocessors by abstract interpretation [C]//In:Workshop onLanguages,Compilers,and Tools for Embedded Systems (LCTES),1999:35-44.
[32] Thomas Lundqvist and Per Stenstrm. Timing Anomalies in dynamicallyscheduled microprocessors [C]//In: Proc.20th IEEE Real-Time SystemsSymposium(RTSS), December1999:12-21.
[33] Patrick Cmwley,Jean-Loup Baer. Worst-Case Execution Time Estimation forHardware Assisted Mulfithreaded Processors [C]//In:2nd Workshop OilNetwork processors, January2003.
[34] Lurs Wehmeyer, Peter Marwedel. Influence of On chip Scratchpad Memories onWCET prediction [C]//In: Proc. ofthe4th International Workshop on Worst-CaseExecution Tune (WCET)Analysis. Catania,Sicily,Italy,June2004．
[35] I. Puaut and C. Pais. Scratchpad memories vs locked Caches in hard real-timesystems: a qualitative and quantitative comparison[R]. Technical report, IRISA,Paris, France,2006.
[36] F. Mueller. Static Cache simulation and its applications[D]. PhD thesis, FloridaState University,1994.
[37] F. Mueller. Timing analysis for instruction Caches[J]. Real-Time Systems,2000,18(2-3):217-247.
[38] C. Ferdinand. Cache Behavior Prediction for Real-Time Systems[D]. PhD thesis,Saarland University,1997.
[39] C. Ferdinand, R. Heckmann, M. Langenbach, F. Martin, M. Schmidt, H. Theiling,S. Thesing, and R. Wilhelm. Reliable and precise WCET determination forreal-life processor [C]//In EMSOFT’01: Proceedings of the First InternationalWorkshop on Embedded Software, volume2211of Lecture Notes in ComputerScience, pages469–485, Tahoe City, CA, USA, Oct.2001.
[40] H. Theiling, C. Ferdinand, and R. Wilhelm. Fast and precise WCET predictionby separated Cache and path analyses[J]. Real Time Systems,18(2-3):157–179,2000.
[41] R. Heckmann, M. Langenbach, S. Thesing, and R. Wilhelm. The influence ofprocessor architecture on the design and the results of WCET tools[C]//Proceedings of the IEEE, vol.9,2003.
[42] Patterson JRC．Accurate static branch prediction by value range propagation[C]//In: Proc. of the ACM SIGPLAN’95Conf．On Programming LanguageDesign and Implementation. La Jolla: ACM Press.1995:67-78.
[43] S．Thesing．Safe and Precise WCET Determination by Abstract Interpretation ofPipeline Models[D]. PhD thesis. Germany:Samrland University,2004.
[44] J. Yan and W. Zhang. WCET Analysis for Multi-Core Processors with Shared L2Instruction Caches [C]//In the14th IEEE Real-Time and Embedded Technologyand Applications Symposium,2008.
[45] W. Zhang and J. Yan. Accurately Estimating Worst-Case Execution Time forMulti-core Processors with Shared Direct-Mapped Instruction Caches [C]//InRTCSA,2009:455-463.
[46] Y. Li, V. Suhendra, Y. Liang, T. Mitra, and A. Roychoudhury. Timing Analysisof Concurrent Programs Running on Shared Cache Multi-Cores [C]//in the30thIEEE Real-Time Systems Symposium, pages57-67,2009.
[47] D. Hardy, T. Piquet, and I. Puaut. Using Bypass to Tighten WCET Estimates forMulti-Core Processors with Shared Instruction Caches [C]//In the30th IEEEReal-Time Systems Symposium, pages68-77,2009.
[48] N. Guan, M. Stigge, W. Yi, and G. Yu. Cache-aware scheduling and analysis formulticores [C]//In the7th ACM international conference on Embedded software,2009.
[49] V. Suhendra and T. Mitra. Exploring locking&partitioning for predictableshared Caches on multi-cores [C]//In the45th annual Design AutomationConference,2008.
[50] A. Andrei, P. Eles, Z. Peng, and J. RosenRosen. Predictable Implementation ofReal-Time Applications on Multiprocessor Systems-on-Chip [C]//In the21stInternational Conference on VLSI Design,2008.
[51] J. Rosen, A. Andrei, P. Eles, and Z. Peng. Bus Access Optimization forPredictable Implementation of Real-Time Applications on MultiprocessorSystems-on-Chip [C]//In the28th IEEE International Real-Time SystemsSymposium,2007.
[52] J. Stachulat, S. Schliecker, M. Ivers, and R. Ernst. Analysis of Memory Latenciesin Multi-Processor Systems [C]//In5th Intl. Workshop on WCET Analysis,2007.
[53] B. Andersson, A. Easwaran, and J. Lee. Finding an upper bound on the increasein execution time due to contention on the memory bus in COTS-based multicoresystems[J]. SIGBED Rev.,7(1):1–4,2010.
[54] B. Akesson, K. Goossens, and M. Ringhofer. Predator: A predictable SDRAMmemory controller [C]//in CODES ISSS, New York, NY, USA,2007.
[55] R. Pellizzoni and M. Caccamo. Impact of Peripheral-Processor Interference onWCET Analysis of Real-Time Embedded Systems[J]. IEEE Trans. Comput.,2010.
[56] R. Bourgade, C. Ballabriga, H. Cass, C. Rochange, and P. Sainrat. Accurateanalysis of memory latencies for WCET estimation [C]//16th InternationalConference on Real-Time and Network Systems,2008.
[57] C. Liu, A. Sivasubramaniam and M. T. Kandemir. Organizing the last line ofdefense before hitting the memory wall for CMP [C]//In Proc. of HPCA,2004.
[58] J. Chang and G. Sohi. Cooperative caching for chip multiprocessors [C]//In Proc.of the33rd Annual International Symposium on Computer Architecture,2006.
[59] Chen Shimin. Gibbons Phillip B, Kozuch Michael. Scheduling threads forconstructive cache sharing on CMPs [C]//In Proc. of the19th Annual ACMSymp. on Parallel Algorithms and Architectures. New York:ACM.2007:105-115.
[60] M. Paolieri et al. Hardware support for WCET analysis of hard real-timemulticore systems [C]//In ISCA,2009.
[61] E. Kligerman, A.Stoyenko. Real-Time Euclid: A language for reliable real-timesystems[J]. IEEE Transactions On Software Engineering.1986,SE-12(9):941-949.
[62] P. Puschner, C. Koza. Calculating the maximum execution time of real-timeprogram[J]. Real-time systems.1989, l(2):159-176.
[63] A Mok, P. Amerasinghe, K.Tantisirivat. Evaluating tight execution time boundsof programs by annotations [C]//In: proc.6th IEEE workshop on real-timeoperating system and software. Pittsburg,PA USA,1989:74-80.
[64] C. Liu and J. Layland. Scheduling Algorithms for Multipmgraming in a hardreal-time Environment [J]. Journal ofACM,1973,20(1):46-61.
[65] Bernat, G.: Specification and Analysis of Weakly-Hard Real-Time Systems[D].PhD thesis, Departament de Ci`encies Matem`atiques i Inform`atica, Universitatde les Illes Balears (January1998).
[66] Bernat, G., Newby, M., Burns, A.: Probabilistic timing analysis: an approachusing copulas[J]. Journal of Embedded Computing,2005,1(2):179-194.
[67]岳峰.实时软件最坏情况执行时间估计研究[D].大连:大连理工大学,2006:2-21.
[68] Alexandervon Billow, JargonStohr. Towards an Efficient Use of Caches in Stateof the Art Processors for Real-Time Systems [C]//16th Euromicro Conference onReal-Time Systems,5-8, June30July2,2004.
[69] W. Zhao, D. Whalley, C. Healy, E MueRcr. WCET Code Positioning [C]//In:Proc. of the IEEE Real-Tune Systems Symposium, December2004.81-91.
[70] W. Zhao, W. Kreahling, David WhaUey, Christopher Healy, Frank Mueller.Improving WCET by Optimizing Worst-Case Paths [C]//In: IEEE Real-Time andEmbedded Technology and Applications Symposium(RTAS2005), SanFrancisco, California, March2005.
[71] S. Lee, J. Lee, C. Y. Par and S. L. Mill. A Flexible Tradeoff between Code Sizeand WCET Using a Dual Instruction Set Processor [C]//In: Proc. of the8thInternational Workshop on Software and Compilers for EmbeddedSystems(LNCS), Netherlands. September2004:244-258.
[72] Ji Meng-Luo, Wang Xin,and Qi Zhi Chang. Trace Acquirement from Real-TimeSystems Based on WCET Analysis [C]//Proceedings ofICESS2005,LNCS3820,Xi’an,China, December2005.160-171.
[73] L. Baresi and M.Young. Test Oracles. Technical Report,CIS-n1-02, Dept. ofComputer and Information Science[R]. Univ. of Oregon, Aug.2001.
[74] Jakob Engblom, Andreas Ermedahl, Mikael Sjodin, Jan Gustavssony HansHansson. Towards Industry Strength Worst-Case Execution Time Analysis[R].Department of Computer System, Uppsala University, Sweden, Technical ReportDocs109, April,1999.
[75] A.Ermedahl, J.Gustafsson, B. Lisper. Experiences from Industrial WCETanalysis [C]//In:5nd International Workshop on Worst-Case Execution Timeanalysis, Palma de Mallorca, Spain, July6,2005.
[76] J.Souyris, E.le Pavec, G. Himbert, V.Jegu, G.Borios and R.Heckmann.Computing the WCET of an Avionics Program by Abstract Interpretation [C]//In:5nd international workshop on worst-case execution time analysis, Palma deMallorca, Spain, July6,2005.
[77]姬孟洛.实时系统最差情况执行时间分析的研究[D].长沙:国防科学技术大学,2006:1-16.
[78] Deverge, J.F., Puaut, I.: Safe Measurement-Based WCET Estimation [C]//In:Proceedings of the5th International Workshop on Worst Case Execution TimeAnalysis, Palma de Mallorca, Spain, July2005:13-16.
[79] Wegener,J.,and Grochtmann,M. Verifying Timing Constraints of Real-TimeSystems by Means of Evolutionary Testing[J]. Real-TimeSystems,1998,15(2):275-298.
[80] N. Tracey, J. Clark,K. Mander. The Way Forward for Unifying Dynamic TestCase Generation: The Optimization-Based Approach [C]//In: Proc. InternationalWorkshop on Dependable Computing and Its Applications, Johannesburg, SouthAfrica, January1998,12-14.
[81] Stefaa M. Petters．How Much Worst Case is Needed in WCET Estimation?[C]//In:2ed International Workshop on Worst-Case Execution Time Analysis.Technical University of Vienna, Austria, June182002.
[82] Wilhelm, R.2005. Determining Bounds on Execution Times[J]. In Handbook onEmbedded Systems, R. Zurawski, Ed. CRC Press,14-1,14-23.
[83] Raimund Kirner, Peter Puschner. Classification of WCET Analysis Techniques[C]//Proceedings of the Eighth IEEE International Symposium onObject-Oriented Real-Time Distributed Computing (ISORC’05).
[84]姬孟洛,李军,王馨等.一种基于抽象解释的WCET自动分析工具[J].计算机工程.2006,32(14):54-56.
[85] Y. S. Li, S. Malik, A．Wolfe. Efficient Microarchitecture Modeling and PathAnalysis for Real-Time Software [C]//Proceedings of the16th IEEE Real-TimeSystems Symposium, Pisa, Italy,1995:298-307.
[86] T． Lundqvist,P． Stenstrom． Integrating Path and Timing Analysis UsingInstruction-Level Simulation Techniques [C]//In Proceedings of ACM SIGPLANworkshop on Languages, Compilers,and Tools for Embedded Systems, NewYork, USA,1998:1-15.
[87] G. Ottosson, M. Sjodin. Worst Case Execution Time Analysis for ModernHardware Architectrues [C]//ACM SIGPLAN workshop OnLanguage,Compilar,and Tools for Real-Time Systems, New York,USA1997:47-55.
[88] A. Ermedahl, J. Oottsson.Deriving Annotations for Tight Calculation ofExecution Time [C]//Proceedings of European Conference on ParallelProcessing,Lyon,France,1997:1298-1307.
[89] Betts, A., Bernat, G.: Tree-Based WCET Analysis on Instrumentation PointGraphs [C]//In:9th IEEE International Symposium on Object andcomponent-oriented Real-time distributed Computing (ISORC2006), KolonHotel, Gyeongju, Korea (April2006).
[90] Healy, C.A., Arnold, R.D., Mueller, F., Harmon, M.G., Walley, D.B.: BoundingPipeline and Instruction Cache Performance[J]. IEEE Transactions on Computers48(1),53-70(1999).
[91] Stappert, F., Altenbernd, P.: Complete Worst-Case Execution Time Analysis ofStraight-Line Hard Real-Time Programs[J]. Journal of Systems Architecture46(4),339-355(2000).
[92] Steven Li, Y.T., Malik, S.: Performance Analysis of Embedded Software UsingImplicit Path Enumeration [C]//In: LCTES1995: Proceedings of the ACMSIGPLAN1995workshop on Languages, Compilers,&tools for real-timesystems, pp.88–98. ACM Press, New York,1995:456-461.
[93] Puschner, P., Schedl, A.V.: Computing Maximum Task Execution Times-Agraph Based Approach[J]. Real-Time Systems13(1),1997:67-91.
[94] A. Colin and I. Puaut. A Modular and Retargetable Framework for Tree-BasedWCET Analysis [C]//In Proc.13th Euromicro Conference on Real-Time Systems,pages37–44, Delft,Netherland, June2001.
[95] Stefan M．Petters and Georg Farber．Making Worst-Case Execution TimeAnalysis for Hard Real-Time Tasks on State of the Art Processors Feasible[C]//In:Proe.6th International Conference on Real-Time Compming Systems andApplications,Hongkong, ROC: IEEE Computer Society Press,December1999.
[96] Raimund KilTler, Peter Puschner,Ingomar Wenzel. Measurement-BasedWorst-Case Execution Time Analysis using Automatic Test-Data Generation[C]//In: Proc. ofthe4th International Workshop of Worst-Case ExecutionTtme(WCET)Analysis,Catania,Sicily,Italy,June2004.
[97] N．Williams．WCET Measurement Using Modified Path Testing [C]//In：5MInternational Workshop on Worst-Case Execution Time Analysis, Palma deMallorea, Spain, July,2005.
[98] A．Betts,G Bemat．Issues Using the Nexus Interface for Measurement-BasedWCET Analysis [C]//In: International Workshop On Worst-Case Execution TimeAnalysis. Palma de Mallorca, Spain,July,2005
[99] Ingomar Wenzel, Raimuod Kirner, Bernhard Rieder, Peter Puschner.Measurement Based Worst-Case Execution Time Analysis [C]//In：Proc.3rdIEEE Workshop on Future Embedded and Ubiquitious Systems, Seattle,WA,May2005,7-10.
[100] S. Cho and L. Jin. Managing Distributed, Shared L2Caches through OS-LevelPage Allocation [C]//In Proceedings of MICRO-39, December2006.
[101] B. K. Bershad, B. J. Chen, D. Lee, and T. H. Romer. Avoiding Conflict MissesDynamically in Large Direct Mapped Caches [C]//In ASPLOS,1994.
[102] Bjerregaard T, Mahadevan S. A Survey of Research and Practices of Network-on-chip [J]. ACM Computing Surveys,2006,38(1):1~51.
[103] Dally W, Towles B. Route Packets, Not Wires: On-Chip InterconnectionNetworks [C]//Proceedings of the38th Design Automation Conference (DAC),New York: ACM Press,2001:684~689.
[104] Nollet V, Marescaux T. Operating-system Controlled Network on Chip [C]//Pro-ceedings of41st Design Automation Conference, New York: ACM Press,2004:256-259.
[105] Atienza D, Angiolini F. Network-on-Chip Design and Synthesis Outlook [J],Integration,2008,41(3):340~359.
[106] X. Li, Y. Liang, T. Mitra and A. Roychoudhury. Chronos: a Timing Analyzer forEmbedded Software[EB/OL]. http://www.comp.nus.edu.sg/rpembed/chronos,October2007.
[107] RapiTime. WCET2005. Worst Case Execution Time (WCET) ProjectHomepage[EB/OL]. www.mrtc.mdh.se/index.phtml?choice=projects&id=0017.
[108] SWEET.[EB/OL]. www.rapitasystems.com.
[109] Y-T. S. Li, S. Malik, and A. Wolfe. Performance Estimation of EmbeddedSoftware with Instruction Cache Modeling[J]. ACM Transactions on DesignAutomation of Electronic Systems,4(3),1999.
[110] J. Poovey. Characterization of the EEMBC Benchmark Suite[EB/OL]. NorthCarolina State University,2007.
[111] Homepage of SNU Real-Time Benchmark Suite[EB/OL].http://archi.snu.ac.kr/realtime/benchmark/, Oct2007.
[112] Price, C. MIPS IV Instruction Set, revision3.1[EB/OL].1995.
[113] CPLEX. The ILOG CPLEX Optimizer v7.5.2002. Commercialsoftware[EB/OL]. http://www.ilog.com.
[114] J. Calandrino, J. Anderson, and D. Baumberger. A Hybrid Real-Time SchedulingApproach for Large-Scale Multi-Core Platforms [C]//In Proc. of the19thEuromicro Conference on Real-Time Systems, July2007.
[115] A. Fedorova, M. Seltzer, C. Small, and D. Nussbaum. Throughput-OrientedScheduling on Chip Multithreading Systems[R]. Technical Report, HarvardUniversity,2005.
[116] J. Anderson, J. Calandrino, and U. Devi. Real-Time Scheduling on MulticorePlatforms [C]//RTAS,2006.
[117] J. Anderson and J. Calandrino. Parallel Real-Time Task Scheduling on MulticorePlatforms [C]//RTSS,2006.
[118] Li Xianfeng, Microarchitecture Modeling for Timing Analysis of EmbeddedSoftware[D]. Dissertation for the Degree of Doctor of Philosophy in Computerscience, National University of Singapore,2005.
[119] X. Li, A. Roychoudhury, T. Mitra, Modeling Out-Of-Order Processors forWCET Analysis[J]. Journal of Real-Time Systems34(3).
[120] Cieslewiez J,Ross K A．Adaptive Aggregation on Chip Multiprocessors [C]//InProc. of the33th International Conf. on Very Large Databases．New York：ACM,2007：339-350.
[121] S. Williams, A. Waterman, and D. Patterson, Roofline: An Insightful VisualPerformance Model for Multicore Architectures[J]. Communications of the ACM,vol.52, no.4,2009.
[122] S. Chattopadhyay, A. Roychoudhury, and T. Mitra. Modeling shared cache andbus in multi-cores for timing analysis [C]//In SCOPES2010.
[123] Langenbach, M., Thesing, S., and Heckmann, R. Pipeline Modeling for TimingAnalysis [C]//In Static Analysis Symposium (SAS),2002.
[124] Burger, J. R. Goodman, and A. K gi. Memory Bandwidth Limitations of FutureMicroprocessors. in ISCA, Philadelphia, Pennsylvania, United States,1996.
[125] JEDEC Solid State Technology Association. DDR2SDRAM Specication,JESD79-2C edition[EB/OL]. May2006.
[126] K. Goossens et al. Interconnect and Memory Organization in SOCs for AdvancedSet-Top Boxes and TV. Evolution, Analysis, and Trends. InInterconnect-Centric Design for Advanced SoC and NoC[M]. Kluwer,2004.
[127] B. Jacob, S. W. Ng, and D. T.Wang, Memory Systems: Cache, DRAM, Disk.[M].New York: Kaufmann,2008.
[128] Marco Paolieri et al. An Analyzable Memory Controller for Hard Real-TimeCMPs[J]. Embedded Systems Letters,2009,1(4):86-90.
[129] John Hennessy and David Patterson. Computer Architecture: A QuantitativeApproach[M]. Morgan Kaufmann,2003.
[130] P. Atanassov and P. Puschner. Impact of DRAM Refresh on the Execution Timeof Real-Time Tasks [C]//in Proc. IWARCC,2001:29–34.
[131]陈国兵.嵌入式异构多核体系的片上通信[D].硕士论文.杭州：浙江大学.2007.
[132]蒋志迪.可编程媒体处理系统芯片（SoC）结构设计研究[D].博士论文.杭州：浙江大学.2005.
[133] A. El-Haj-Mahmoud, A. S. AL-Zawawi, A. Anantaraman, and E. Rotenberg.Virtual multiprocessor: an analyzable, high-performance architecture forreal-time computing. In CASES, San Francisco, CA, USA,2005.
[134] R. Pellizzoni and M. Caccamo. Toward the predictable integration of real-timeCOTS based systems. In RTSS, Tucson, Arizona, USA,2007.
[135] Mingsong Lv, Nan Guan, Yi Zhang, Qingxu Deng, Ge Yu, Jianming Zhang,“ASurvey of WCET Analysis of Real-Time Operating Systems”, in Proc. of the6thIEEE International Conference on Embedded Software and Systems (ICESS2009).
[136] Mingsong Lv, Wang Yi, NanGuan, Ge Yu."Combining Abstract Interpretationwith Model Checking for Timing Analysis of Multicore Real-Time Software", inthe31st IEEE Real-Time Systems Symposium (RTSS), San Diego, CA, US,2010.
[137] Mingsong Lv, Nan Guan, Qingxu Deng, Ge Yu, Wang Yi."Static Worst-CaseExecution Time Analysis of the uC/OS-II Real-Time Kernel", in Frontiers ofComputer Science in China, Number3, September,2010.
[138] aiT.[EB/OL]. http://www.absint.com/.
[139] Bound-T.[EB/OL]. http://www.bound-t.com/.
[140] R. Wilhelm, J. Engblom, et al. The worst-case executiontime problem—overviewof methods and survey of tools. Trans. on Embedded Computing Sys.,7(3):1–53,2008.
[141] ARM. AMBA Specification (Rev2.0).1999.
[142] IBM. The CoreConnect Bus Architecture White Paper[EB/OL].http://www-306.ibm.com/chips/techlib/techlib.nsf/techdocs/852569B20050FF77852569910050C0FB.
[143] Silicore. The wishbone Bus Architecture White Paper[EB/OL].www.opencores.org/wishbone/.
[144] P．Puschner．Worst-case execution time analysis at low cost. Control EngineeringPractice．1998，6(1)：129-13．
[145] Raimund Kirner and Peter Puschner,“Transformation of Path Information forWCET Analysis during Compilation”．In Proc．13th Euromicro InternationalConference on Real-Time Systems，pages29-36，Jun．2001.
[2] ITRS. International Technology Roadmap for Semiconductors,2008update[R].Tech Report. ITRS2009[EB/OL]. http://public.itrs.net.
[3] ITRS. International Technology Roadmap for Semiconductors,2005edition [R].ITRS, April2005[EB/OL]. http://public.itrs.net.
[4] Burger D, Goodman J R. Billion-Transistor Architectures：There and Back Again[J]. IEEE Computer,2004,37(3):22-28.
[5] Karthikeyan Sankaralingam, Ramadass Nagarajan, et al. Exploiting ILP, TLP,and DLP with the Polymorphous TRIPS architecture [C]∥In Proceedings of the30th Annual International Symposium on Computer Architecture,2003.
[6] M. B. Taylor, Walter Lee, et al. Evaluation of the Raw Microprocessor: AnExposed-Wire-Delay Architecture for ILP and Streams [C]∥In Proceedings ofthe31th Annual International Symposium on Computer Architecture,2004.
[7] D. Pham et. al. The Design and Implementation of a First-Generation CELLProcessor [C]∥International Solid-State Circuits Conference Technical Digest,Feb.2005.
[8] Cameron McNairy, Rohit Bhatia. Montecito: A Dual-Core, Dual-Thread ItaniumProcessor[J]. IEEE Micro, vol.25, no.2, pp.10-20, Mar/Apr,2005.
[9] Asanovic, Krste and etc. The Landscape of Parallel Computing Research: AView from Berkeley[R]. UCB/EECS-2006-183,2006.
[10] Lance Hammond et al. The Stanford Hydra CMP[J]. IEEE Micro, v.20n.2,pp.71-84, March2000.
[11] Jane W.S. Liu. Real-Time Systems [M]. Prentice. Hall,2000.
[12] Robert I. Davis and Alan Burns. A Survey of Hard Real-Time SchedulingAlgorithms and Schedulability Analysis Techniques for Multiprocessor Systems[R]. University of York, Department of Computer Science Technical Report,YCS-2009-443, November2009.
[13] K. Hirata and J. Goodacre. Arm mpcore; the streamlined and scalable arm11processor core [C]∥Design Automation Conference,2007. ASP-DAC’07. Asiaand South Pacific, pages747~748, Jan.2007.
[14] Pham, D.C., et al. Overview of the Architecture, Circuit Design, and PhysicalImplementation of a First-generation cell processor [J]. IEEE Journal ofSolid-State Circuits.2006.41(l):179-196.
[15] P. Puschner and A. Burns. A Review of Worst-Case Execution-Time Analysis [J].Real-Time Systems,2/3:115-127,2000.
[16] Alan C. Shaw. Reasoning about time in highe level language software [J]. IEEETransactions on Software Engineering, July1989,15(7):875-889.
[17] Johann Blieberger. Data-flow framework for worst-case execution time analysis[J]. Real-Time Systems,2002,22:183-227.
[18] N. Holsti, T. Langbacka, and S. Saarinen. Worst-Case Execution-Time Analysisfor Digital Signal Processors [C]//In: Proc. Of the EUSIPCO2000Conference,September2000.
[19] Sung-Soo Lim, Young H.Bae, and et al．An Accurate Worst Case TimingAnalysis for RISC processors [J]. IEEE Transactions on Software Engineering,1995,2l(7):593-604.
[20] Jakob Engblom and Andreas Ermedahl. Pipeline timing analysis using atrace-driven simulator [C]//In Proc．6th International Conference on Real-TimeComputing Systems and Applications, Hong Kong, Dec.1999.
[21] C. A. Healy, D. B. Whalley, and M. G. Harmon．Integrating the Timing Analysisof Pipelining and Instruction Caching [C]//In: Proc. of the Sixteenth IEEEReal-Time Systems Symposium, December1995.288-297.
[22] F．Mueller and D．B．Whalley．Efficient On-the-fly Analysis of ProgramBehavior and Static Cache Simulation [C]//In: Static Analysis Symposium,B．LeCharlier, editor, volume864of lecture Notes in Computer Science,Springer, Sep1994,101-115.
[23] Robert D．Arnold,Frank Mueller,David Whalley,and Marion Harmon．BoundingWorst-Case Instruction Cache Performance [C]//In: Proc.15th Real-TimeSystems Symposium (RTSS), Brooloine, Massachusetts, Dec.1994.172-181.
[24] Frank Mueller．Generalizing Timing Predictions to Set-Associative Caches[C]//In: Workshop Oil Real-Time Systems．Jun．1997:64-71.
[25] Randall T．White and et al．Timing analysis for data Caches and set-associativeCaches [C]//In: Proc. Real-Time Technology and Applications Symposium,Jun.1997.192-202.
[26] Randall T. White, Frank Mueller,Christopher A. Healy, and Marion G．Harmo.Timing Analysis for Data Caches and Wrap Around Fill Caches[J]. Real-TimeSystems,November1999:209-233．
[27] Martin alt,Christi Ferdinand,Florian Martin,and Reinhurd wilhelm． Cachebehavior prediction by abstract interpretation [C]//In: Static AnalysisSymposium(sAs), LNCS l145, Springer,1996:52-66.
[28] Antoine Colin and Isabelle Puant. Worst case execution time analysis foraprocessor with branch prediction [J]. Real-Time Systems, May2000,18(2):249-274.
[29] Tulika Mitra and Abhik Roychoudhnry．A framework to model branch predictionfor wcet analysis [R]. TechnicalReport-01, National University ofSingapore(NUS), Nov.2001.
[30] Xianfeng Li,Tulika Mitra,Abhik Roychoudhury．Accurate Timing Analysis byModeling Caches Speculation and their Infraction [C]//In:40th ACM IEEEDesign Automation Conference(DAC),June2003.
[31] J. Schneider and C. Ferdinand．Pipeline behavior prediction for superscalarprocessors by abstract interpretation [C]//In:Workshop onLanguages,Compilers,and Tools for Embedded Systems (LCTES),1999:35-44.
[32] Thomas Lundqvist and Per Stenstrm. Timing Anomalies in dynamicallyscheduled microprocessors [C]//In: Proc.20th IEEE Real-Time SystemsSymposium(RTSS), December1999:12-21.
[33] Patrick Cmwley,Jean-Loup Baer. Worst-Case Execution Time Estimation forHardware Assisted Mulfithreaded Processors [C]//In:2nd Workshop OilNetwork processors, January2003.
[34] Lurs Wehmeyer, Peter Marwedel. Influence of On chip Scratchpad Memories onWCET prediction [C]//In: Proc. ofthe4th International Workshop on Worst-CaseExecution Tune (WCET)Analysis. Catania,Sicily,Italy,June2004．
[35] I. Puaut and C. Pais. Scratchpad memories vs locked Caches in hard real-timesystems: a qualitative and quantitative comparison[R]. Technical report, IRISA,Paris, France,2006.
[36] F. Mueller. Static Cache simulation and its applications[D]. PhD thesis, FloridaState University,1994.
[37] F. Mueller. Timing analysis for instruction Caches[J]. Real-Time Systems,2000,18(2-3):217-247.
[38] C. Ferdinand. Cache Behavior Prediction for Real-Time Systems[D]. PhD thesis,Saarland University,1997.
[39] C. Ferdinand, R. Heckmann, M. Langenbach, F. Martin, M. Schmidt, H. Theiling,S. Thesing, and R. Wilhelm. Reliable and precise WCET determination forreal-life processor [C]//In EMSOFT’01: Proceedings of the First InternationalWorkshop on Embedded Software, volume2211of Lecture Notes in ComputerScience, pages469–485, Tahoe City, CA, USA, Oct.2001.
[40] H. Theiling, C. Ferdinand, and R. Wilhelm. Fast and precise WCET predictionby separated Cache and path analyses[J]. Real Time Systems,18(2-3):157–179,2000.
[41] R. Heckmann, M. Langenbach, S. Thesing, and R. Wilhelm. The influence ofprocessor architecture on the design and the results of WCET tools[C]//Proceedings of the IEEE, vol.9,2003.
[42] Patterson JRC．Accurate static branch prediction by value range propagation[C]//In: Proc. of the ACM SIGPLAN’95Conf．On Programming LanguageDesign and Implementation. La Jolla: ACM Press.1995:67-78.
[43] S．Thesing．Safe and Precise WCET Determination by Abstract Interpretation ofPipeline Models[D]. PhD thesis. Germany:Samrland University,2004.
[44] J. Yan and W. Zhang. WCET Analysis for Multi-Core Processors with Shared L2Instruction Caches [C]//In the14th IEEE Real-Time and Embedded Technologyand Applications Symposium,2008.
[45] W. Zhang and J. Yan. Accurately Estimating Worst-Case Execution Time forMulti-core Processors with Shared Direct-Mapped Instruction Caches [C]//InRTCSA,2009:455-463.
[46] Y. Li, V. Suhendra, Y. Liang, T. Mitra, and A. Roychoudhury. Timing Analysisof Concurrent Programs Running on Shared Cache Multi-Cores [C]//in the30thIEEE Real-Time Systems Symposium, pages57-67,2009.
[47] D. Hardy, T. Piquet, and I. Puaut. Using Bypass to Tighten WCET Estimates forMulti-Core Processors with Shared Instruction Caches [C]//In the30th IEEEReal-Time Systems Symposium, pages68-77,2009.
[48] N. Guan, M. Stigge, W. Yi, and G. Yu. Cache-aware scheduling and analysis formulticores [C]//In the7th ACM international conference on Embedded software,2009.
[49] V. Suhendra and T. Mitra. Exploring locking&partitioning for predictableshared Caches on multi-cores [C]//In the45th annual Design AutomationConference,2008.
[50] A. Andrei, P. Eles, Z. Peng, and J. RosenRosen. Predictable Implementation ofReal-Time Applications on Multiprocessor Systems-on-Chip [C]//In the21stInternational Conference on VLSI Design,2008.
[51] J. Rosen, A. Andrei, P. Eles, and Z. Peng. Bus Access Optimization forPredictable Implementation of Real-Time Applications on MultiprocessorSystems-on-Chip [C]//In the28th IEEE International Real-Time SystemsSymposium,2007.
[52] J. Stachulat, S. Schliecker, M. Ivers, and R. Ernst. Analysis of Memory Latenciesin Multi-Processor Systems [C]//In5th Intl. Workshop on WCET Analysis,2007.
[53] B. Andersson, A. Easwaran, and J. Lee. Finding an upper bound on the increasein execution time due to contention on the memory bus in COTS-based multicoresystems[J]. SIGBED Rev.,7(1):1–4,2010.
[54] B. Akesson, K. Goossens, and M. Ringhofer. Predator: A predictable SDRAMmemory controller [C]//in CODES ISSS, New York, NY, USA,2007.
[55] R. Pellizzoni and M. Caccamo. Impact of Peripheral-Processor Interference onWCET Analysis of Real-Time Embedded Systems[J]. IEEE Trans. Comput.,2010.
[56] R. Bourgade, C. Ballabriga, H. Cass, C. Rochange, and P. Sainrat. Accurateanalysis of memory latencies for WCET estimation [C]//16th InternationalConference on Real-Time and Network Systems,2008.
[57] C. Liu, A. Sivasubramaniam and M. T. Kandemir. Organizing the last line ofdefense before hitting the memory wall for CMP [C]//In Proc. of HPCA,2004.
[58] J. Chang and G. Sohi. Cooperative caching for chip multiprocessors [C]//In Proc.of the33rd Annual International Symposium on Computer Architecture,2006.
[59] Chen Shimin. Gibbons Phillip B, Kozuch Michael. Scheduling threads forconstructive cache sharing on CMPs [C]//In Proc. of the19th Annual ACMSymp. on Parallel Algorithms and Architectures. New York:ACM.2007:105-115.
[60] M. Paolieri et al. Hardware support for WCET analysis of hard real-timemulticore systems [C]//In ISCA,2009.
[61] E. Kligerman, A.Stoyenko. Real-Time Euclid: A language for reliable real-timesystems[J]. IEEE Transactions On Software Engineering.1986,SE-12(9):941-949.
[62] P. Puschner, C. Koza. Calculating the maximum execution time of real-timeprogram[J]. Real-time systems.1989, l(2):159-176.
[63] A Mok, P. Amerasinghe, K.Tantisirivat. Evaluating tight execution time boundsof programs by annotations [C]//In: proc.6th IEEE workshop on real-timeoperating system and software. Pittsburg,PA USA,1989:74-80.
[64] C. Liu and J. Layland. Scheduling Algorithms for Multipmgraming in a hardreal-time Environment [J]. Journal ofACM,1973,20(1):46-61.
[65] Bernat, G.: Specification and Analysis of Weakly-Hard Real-Time Systems[D].PhD thesis, Departament de Ci`encies Matem`atiques i Inform`atica, Universitatde les Illes Balears (January1998).
[66] Bernat, G., Newby, M., Burns, A.: Probabilistic timing analysis: an approachusing copulas[J]. Journal of Embedded Computing,2005,1(2):179-194.
[67]岳峰.实时软件最坏情况执行时间估计研究[D].大连:大连理工大学,2006:2-21.
[68] Alexandervon Billow, JargonStohr. Towards an Efficient Use of Caches in Stateof the Art Processors for Real-Time Systems [C]//16th Euromicro Conference onReal-Time Systems,5-8, June30July2,2004.
[69] W. Zhao, D. Whalley, C. Healy, E MueRcr. WCET Code Positioning [C]//In:Proc. of the IEEE Real-Tune Systems Symposium, December2004.81-91.
[70] W. Zhao, W. Kreahling, David WhaUey, Christopher Healy, Frank Mueller.Improving WCET by Optimizing Worst-Case Paths [C]//In: IEEE Real-Time andEmbedded Technology and Applications Symposium(RTAS2005), SanFrancisco, California, March2005.
[71] S. Lee, J. Lee, C. Y. Par and S. L. Mill. A Flexible Tradeoff between Code Sizeand WCET Using a Dual Instruction Set Processor [C]//In: Proc. of the8thInternational Workshop on Software and Compilers for EmbeddedSystems(LNCS), Netherlands. September2004:244-258.
[72] Ji Meng-Luo, Wang Xin,and Qi Zhi Chang. Trace Acquirement from Real-TimeSystems Based on WCET Analysis [C]//Proceedings ofICESS2005,LNCS3820,Xi’an,China, December2005.160-171.
[73] L. Baresi and M.Young. Test Oracles. Technical Report,CIS-n1-02, Dept. ofComputer and Information Science[R]. Univ. of Oregon, Aug.2001.
[74] Jakob Engblom, Andreas Ermedahl, Mikael Sjodin, Jan Gustavssony HansHansson. Towards Industry Strength Worst-Case Execution Time Analysis[R].Department of Computer System, Uppsala University, Sweden, Technical ReportDocs109, April,1999.
[75] A.Ermedahl, J.Gustafsson, B. Lisper. Experiences from Industrial WCETanalysis [C]//In:5nd International Workshop on Worst-Case Execution Timeanalysis, Palma de Mallorca, Spain, July6,2005.
[76] J.Souyris, E.le Pavec, G. Himbert, V.Jegu, G.Borios and R.Heckmann.Computing the WCET of an Avionics Program by Abstract Interpretation [C]//In:5nd international workshop on worst-case execution time analysis, Palma deMallorca, Spain, July6,2005.
[77]姬孟洛.实时系统最差情况执行时间分析的研究[D].长沙:国防科学技术大学,2006:1-16.
[78] Deverge, J.F., Puaut, I.: Safe Measurement-Based WCET Estimation [C]//In:Proceedings of the5th International Workshop on Worst Case Execution TimeAnalysis, Palma de Mallorca, Spain, July2005:13-16.
[79] Wegener,J.,and Grochtmann,M. Verifying Timing Constraints of Real-TimeSystems by Means of Evolutionary Testing[J]. Real-TimeSystems,1998,15(2):275-298.
[80] N. Tracey, J. Clark,K. Mander. The Way Forward for Unifying Dynamic TestCase Generation: The Optimization-Based Approach [C]//In: Proc. InternationalWorkshop on Dependable Computing and Its Applications, Johannesburg, SouthAfrica, January1998,12-14.
[81] Stefaa M. Petters．How Much Worst Case is Needed in WCET Estimation?[C]//In:2ed International Workshop on Worst-Case Execution Time Analysis.Technical University of Vienna, Austria, June182002.
[82] Wilhelm, R.2005. Determining Bounds on Execution Times[J]. In Handbook onEmbedded Systems, R. Zurawski, Ed. CRC Press,14-1,14-23.
[83] Raimund Kirner, Peter Puschner. Classification of WCET Analysis Techniques[C]//Proceedings of the Eighth IEEE International Symposium onObject-Oriented Real-Time Distributed Computing (ISORC’05).
[84]姬孟洛,李军,王馨等.一种基于抽象解释的WCET自动分析工具[J].计算机工程.2006,32(14):54-56.
[85] Y. S. Li, S. Malik, A．Wolfe. Efficient Microarchitecture Modeling and PathAnalysis for Real-Time Software [C]//Proceedings of the16th IEEE Real-TimeSystems Symposium, Pisa, Italy,1995:298-307.
[86] T． Lundqvist,P． Stenstrom． Integrating Path and Timing Analysis UsingInstruction-Level Simulation Techniques [C]//In Proceedings of ACM SIGPLANworkshop on Languages, Compilers,and Tools for Embedded Systems, NewYork, USA,1998:1-15.
[87] G. Ottosson, M. Sjodin. Worst Case Execution Time Analysis for ModernHardware Architectrues [C]//ACM SIGPLAN workshop OnLanguage,Compilar,and Tools for Real-Time Systems, New York,USA1997:47-55.
[88] A. Ermedahl, J. Oottsson.Deriving Annotations for Tight Calculation ofExecution Time [C]//Proceedings of European Conference on ParallelProcessing,Lyon,France,1997:1298-1307.
[89] Betts, A., Bernat, G.: Tree-Based WCET Analysis on Instrumentation PointGraphs [C]//In:9th IEEE International Symposium on Object andcomponent-oriented Real-time distributed Computing (ISORC2006), KolonHotel, Gyeongju, Korea (April2006).
[90] Healy, C.A., Arnold, R.D., Mueller, F., Harmon, M.G., Walley, D.B.: BoundingPipeline and Instruction Cache Performance[J]. IEEE Transactions on Computers48(1),53-70(1999).
[91] Stappert, F., Altenbernd, P.: Complete Worst-Case Execution Time Analysis ofStraight-Line Hard Real-Time Programs[J]. Journal of Systems Architecture46(4),339-355(2000).
[92] Steven Li, Y.T., Malik, S.: Performance Analysis of Embedded Software UsingImplicit Path Enumeration [C]//In: LCTES1995: Proceedings of the ACMSIGPLAN1995workshop on Languages, Compilers,&tools for real-timesystems, pp.88–98. ACM Press, New York,1995:456-461.
[93] Puschner, P., Schedl, A.V.: Computing Maximum Task Execution Times-Agraph Based Approach[J]. Real-Time Systems13(1),1997:67-91.
[94] A. Colin and I. Puaut. A Modular and Retargetable Framework for Tree-BasedWCET Analysis [C]//In Proc.13th Euromicro Conference on Real-Time Systems,pages37–44, Delft,Netherland, June2001.
[95] Stefan M．Petters and Georg Farber．Making Worst-Case Execution TimeAnalysis for Hard Real-Time Tasks on State of the Art Processors Feasible[C]//In:Proe.6th International Conference on Real-Time Compming Systems andApplications,Hongkong, ROC: IEEE Computer Society Press,December1999.
[96] Raimund KilTler, Peter Puschner,Ingomar Wenzel. Measurement-BasedWorst-Case Execution Time Analysis using Automatic Test-Data Generation[C]//In: Proc. ofthe4th International Workshop of Worst-Case ExecutionTtme(WCET)Analysis,Catania,Sicily,Italy,June2004.
[97] N．Williams．WCET Measurement Using Modified Path Testing [C]//In：5MInternational Workshop on Worst-Case Execution Time Analysis, Palma deMallorea, Spain, July,2005.
[98] A．Betts,G Bemat．Issues Using the Nexus Interface for Measurement-BasedWCET Analysis [C]//In: International Workshop On Worst-Case Execution TimeAnalysis. Palma de Mallorca, Spain,July,2005
[99] Ingomar Wenzel, Raimuod Kirner, Bernhard Rieder, Peter Puschner.Measurement Based Worst-Case Execution Time Analysis [C]//In：Proc.3rdIEEE Workshop on Future Embedded and Ubiquitious Systems, Seattle,WA,May2005,7-10.
[100] S. Cho and L. Jin. Managing Distributed, Shared L2Caches through OS-LevelPage Allocation [C]//In Proceedings of MICRO-39, December2006.
[101] B. K. Bershad, B. J. Chen, D. Lee, and T. H. Romer. Avoiding Conflict MissesDynamically in Large Direct Mapped Caches [C]//In ASPLOS,1994.
[102] Bjerregaard T, Mahadevan S. A Survey of Research and Practices of Network-on-chip [J]. ACM Computing Surveys,2006,38(1):1~51.
[103] Dally W, Towles B. Route Packets, Not Wires: On-Chip InterconnectionNetworks [C]//Proceedings of the38th Design Automation Conference (DAC),New York: ACM Press,2001:684~689.
[104] Nollet V, Marescaux T. Operating-system Controlled Network on Chip [C]//Pro-ceedings of41st Design Automation Conference, New York: ACM Press,2004:256-259.
[105] Atienza D, Angiolini F. Network-on-Chip Design and Synthesis Outlook [J],Integration,2008,41(3):340~359.
[106] X. Li, Y. Liang, T. Mitra and A. Roychoudhury. Chronos: a Timing Analyzer forEmbedded Software[EB/OL]. http://www.comp.nus.edu.sg/rpembed/chronos,October2007.
[107] RapiTime. WCET2005. Worst Case Execution Time (WCET) ProjectHomepage[EB/OL]. www.mrtc.mdh.se/index.phtml?choice=projects&id=0017.
[108] SWEET.[EB/OL]. www.rapitasystems.com.
[109] Y-T. S. Li, S. Malik, and A. Wolfe. Performance Estimation of EmbeddedSoftware with Instruction Cache Modeling[J]. ACM Transactions on DesignAutomation of Electronic Systems,4(3),1999.
[110] J. Poovey. Characterization of the EEMBC Benchmark Suite[EB/OL]. NorthCarolina State University,2007.
[111] Homepage of SNU Real-Time Benchmark Suite[EB/OL].http://archi.snu.ac.kr/realtime/benchmark/, Oct2007.
[112] Price, C. MIPS IV Instruction Set, revision3.1[EB/OL].1995.
[113] CPLEX. The ILOG CPLEX Optimizer v7.5.2002. Commercialsoftware[EB/OL]. http://www.ilog.com.
[114] J. Calandrino, J. Anderson, and D. Baumberger. A Hybrid Real-Time SchedulingApproach for Large-Scale Multi-Core Platforms [C]//In Proc. of the19thEuromicro Conference on Real-Time Systems, July2007.
[115] A. Fedorova, M. Seltzer, C. Small, and D. Nussbaum. Throughput-OrientedScheduling on Chip Multithreading Systems[R]. Technical Report, HarvardUniversity,2005.
[116] J. Anderson, J. Calandrino, and U. Devi. Real-Time Scheduling on MulticorePlatforms [C]//RTAS,2006.
[117] J. Anderson and J. Calandrino. Parallel Real-Time Task Scheduling on MulticorePlatforms [C]//RTSS,2006.
[118] Li Xianfeng, Microarchitecture Modeling for Timing Analysis of EmbeddedSoftware[D]. Dissertation for the Degree of Doctor of Philosophy in Computerscience, National University of Singapore,2005.
[119] X. Li, A. Roychoudhury, T. Mitra, Modeling Out-Of-Order Processors forWCET Analysis[J]. Journal of Real-Time Systems34(3).
[120] Cieslewiez J,Ross K A．Adaptive Aggregation on Chip Multiprocessors [C]//InProc. of the33th International Conf. on Very Large Databases．New York：ACM,2007：339-350.
[121] S. Williams, A. Waterman, and D. Patterson, Roofline: An Insightful VisualPerformance Model for Multicore Architectures[J]. Communications of the ACM,vol.52, no.4,2009.
[122] S. Chattopadhyay, A. Roychoudhury, and T. Mitra. Modeling shared cache andbus in multi-cores for timing analysis [C]//In SCOPES2010.
[123] Langenbach, M., Thesing, S., and Heckmann, R. Pipeline Modeling for TimingAnalysis [C]//In Static Analysis Symposium (SAS),2002.
[124] Burger, J. R. Goodman, and A. K gi. Memory Bandwidth Limitations of FutureMicroprocessors. in ISCA, Philadelphia, Pennsylvania, United States,1996.
[125] JEDEC Solid State Technology Association. DDR2SDRAM Specication,JESD79-2C edition[EB/OL]. May2006.
[126] K. Goossens et al. Interconnect and Memory Organization in SOCs for AdvancedSet-Top Boxes and TV. Evolution, Analysis, and Trends. InInterconnect-Centric Design for Advanced SoC and NoC[M]. Kluwer,2004.
[127] B. Jacob, S. W. Ng, and D. T.Wang, Memory Systems: Cache, DRAM, Disk.[M].New York: Kaufmann,2008.
[128] Marco Paolieri et al. An Analyzable Memory Controller for Hard Real-TimeCMPs[J]. Embedded Systems Letters,2009,1(4):86-90.
[129] John Hennessy and David Patterson. Computer Architecture: A QuantitativeApproach[M]. Morgan Kaufmann,2003.
[130] P. Atanassov and P. Puschner. Impact of DRAM Refresh on the Execution Timeof Real-Time Tasks [C]//in Proc. IWARCC,2001:29–34.
[131]陈国兵.嵌入式异构多核体系的片上通信[D].硕士论文.杭州：浙江大学.2007.
[132]蒋志迪.可编程媒体处理系统芯片（SoC）结构设计研究[D].博士论文.杭州：浙江大学.2005.
[133] A. El-Haj-Mahmoud, A. S. AL-Zawawi, A. Anantaraman, and E. Rotenberg.Virtual multiprocessor: an analyzable, high-performance architecture forreal-time computing. In CASES, San Francisco, CA, USA,2005.
[134] R. Pellizzoni and M. Caccamo. Toward the predictable integration of real-timeCOTS based systems. In RTSS, Tucson, Arizona, USA,2007.
[135] Mingsong Lv, Nan Guan, Yi Zhang, Qingxu Deng, Ge Yu, Jianming Zhang,“ASurvey of WCET Analysis of Real-Time Operating Systems”, in Proc. of the6thIEEE International Conference on Embedded Software and Systems (ICESS2009).
[136] Mingsong Lv, Wang Yi, NanGuan, Ge Yu."Combining Abstract Interpretationwith Model Checking for Timing Analysis of Multicore Real-Time Software", inthe31st IEEE Real-Time Systems Symposium (RTSS), San Diego, CA, US,2010.
[137] Mingsong Lv, Nan Guan, Qingxu Deng, Ge Yu, Wang Yi."Static Worst-CaseExecution Time Analysis of the uC/OS-II Real-Time Kernel", in Frontiers ofComputer Science in China, Number3, September,2010.
[138] aiT.[EB/OL]. http://www.absint.com/.
[139] Bound-T.[EB/OL]. http://www.bound-t.com/.
[140] R. Wilhelm, J. Engblom, et al. The worst-case executiontime problem—overviewof methods and survey of tools. Trans. on Embedded Computing Sys.,7(3):1–53,2008.
[141] ARM. AMBA Specification (Rev2.0).1999.
[142] IBM. The CoreConnect Bus Architecture White Paper[EB/OL].http://www-306.ibm.com/chips/techlib/techlib.nsf/techdocs/852569B20050FF77852569910050C0FB.
[143] Silicore. The wishbone Bus Architecture White Paper[EB/OL].www.opencores.org/wishbone/.
[144] P．Puschner．Worst-case execution time analysis at low cost. Control EngineeringPractice．1998，6(1)：129-13．
[145] Raimund Kirner and Peter Puschner,“Transformation of Path Information forWCET Analysis during Compilation”．In Proc．13th Euromicro InternationalConference on Real-Time Systems，pages29-36，Jun．2001.