Abstract Interpretation with Applications to Timing Validation.ppt
《Abstract Interpretation with Applications to Timing Validation.ppt》由会员分享,可在线阅读,更多相关《Abstract Interpretation with Applications to Timing Validation.ppt(118页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、Timing Analysis-timing guarantees for hard real-time systems-Reinhard WilhelmSaarland UniversitySaarbrckenTexPoint fonts used in EMF.Read the TexPoint manual before you delete this box.:AAAAAStructure of the Lecture1.Introduction2.Static timing analysis1.the problem2.our approach3.the success4.tool
2、architecture3.Cache analysis4.Pipeline analysis5.Value analysis6.Worst-case path determination7.Timing Predictabilitycachesnon-cache-like devicesfuture architectures8.ConclusionIndustrial NeedsHard real-time systems,often in safety-critical applications aboundAeronautics,automotive,train industries,
3、manufacturing control Wing vibration of airplane,sensing every 5 mSecSideairbag in car,Reaction in 10 mSeccrankshaft-synchronous taskshave very tight deadlines,45uSTiming Analysis Embedded controllers are expected to finish their tasks reliably within time bounds.The problem:Given1.a software to pro
4、duce some reaction,2.a hardware platform,on which to execute the software,3.required reaction time.Derive:a guarantee for timeliness.Timing Analysisprovides parameters for schedulability analysis:Execution time,Ci,of tasks,and if that is impossible,upper bounds and maybe also lower bounds on executi
5、on times of tasks,often called Worst-Case Execution Times(WCET)and Best-Case Execution Times(BCET).Architecture(constant executiontimes)Timing Analysis the Search Spaceall control-flow paths(through the binary executable)depending on the possible inputs.Feasible as search for a longest path if itera
6、tion and recursion are bounded,execution time of instructions are(positive)constants.Elegant method:Timing Schemata(Shaw 89)inductive calculation of upper bounds.SoftwareInputub(if if b thenthen S1 elseelse S2):=ub(b)+max(ub(S1),ub(S2)High-Performance Microprosessorsincrease(average-case)performance
7、 by using:Caches,Pipelines,Branch Prediction,SpeculationThese features make timing analysis difficult:Execution times of instructions vary widelyBest case-everything goes smoothly:no cache miss,operands ready,resources free,branch correctly predictedWorst case-everything goes wrong:all loads miss th
8、e cache,resources are occupied,operands not readySpan may be several hundred cyclesVariability of Execution TimesLOAD r2,_aLOAD r1,_bADD r3,r2,r1PPC 755x=a+b;In most cases,executionwill be fast.So,assuming the worst caseis safe,but very pessimistic!AbsInts WCET Analyzer aiT IST Project DAEDALUS fina
9、l review report:The AbsInt tool is probably thebest of its kind in the world and it is justified to consider this result as a breakthrough.”Several time-critical subsystems of the Airbus A380 have been certified using aiT;aiT is the only validated tool for these applications.Tremendous Progressdurin
10、g the 10 years from 1998 to 2008199520022005over-estimation20-30%15%30-50%42560200cache-miss penaltyLim et al.Thesing et al.Souyris et al.The explosion of penalties has been compensated by the improvement of the analyses!10%25%State-dependent Execution TimesExecution time depend on the execution sta
11、te.Execution state results from the execution history.semantics state:values of variablesexecution state:occupancy of resourcesstateArchitectureTiming Analysis the Search Spacewith State-dependent Execution Timesall control-flow paths depending on the possible inputsall paths through the architectur
12、e for potential initial statesSoftwareInputinitialstatemul rD,rA,rB execution states for paths reaching this program pointinstructionin I-cacheinstructionnot in I-cache1bus occupiedbus not occupiedsmall operandslarge operands14 40ArchitectureTiming Analysis the Search Spacewith out-of-order executio
13、nall control-flow paths depending on the possible inputsall paths through the architecture for potential initial statesincluding different schedules for instruction sequencesSoftwareInputinitialstateArchitectureTiming Analysis the Search Spacewith multi-threadingall control-flow paths depending on t
14、he possible inputsall paths through the architecture for potential initial statesincluding different schedules for instruction sequencesincluding different interleavings of accesses to shared resourcesSoftwareInputinitialstateWhy Exhaustive Exploration?Naive attempt:follow local worst-case transitio
15、ns onlyUnsound in the presence of Timing Anomalies:A path starting with a local worst case may have a lower overall execution time,Ex.:a cache miss preventing a branch mis-predictionCaused by the interference between processor components:Ex.:cache hit/miss influences branch prediction;branch predict
16、ion causes prefetching;prefetching pollutes the I-cache.State Space Explosion in Timing Analysisconstantexecutiontimesstate-dependentexecution timesout-of-orderexecutionpreemptiveschedulingconcurrency+shared resourcesyears+methods199520002010Timing schemata Static analysis?Caches,pipelines,speculati
17、on:combined cache andpipeline analysisSuperscalar processors:interleavingsof all schedulesMulti-core withshared resources:interleavingsof several threadsNotions in Timing AnalysisHard or impossible to determineDetermine upper bounds instead High-Level Requirements for Timing AnalysisUpper bounds mus
18、t be safe,i.e.not underestimatedUpper bounds should be tight,i.e.not far away from real execution timesAnalogous for lower boundsAnalysis effort must be tolerableNote:all analyzed programs are terminating,loop bounds need to be known no decidability problem,but a complexity problem!Timing Accidents
19、and PenaltiesTiming Accident cause for an increase of the execution time of an instructionTiming Penalty the associated increaseTypes of timing accidentsCache missesPipeline stallsBranch mispredictionsBus collisionsMemory refresh of DRAMTLB missExecution Time is History-SensitiveContribution of the
20、execution of an instruction to a programs execution time depends on the execution state,e.g.the time for a memory access depends on the cache statethe execution state depends on the execution historyneeded:an invariant about the set of execution states produced by all executions reaching a program p
21、oint.We use abstract interpretation to compute these invariants.Deriving Run-Time GuaranteesOur method and tool,aiT,derives Safety Properties from these invariants:Certain timing accidents will never happen.Example:At program point p,instruction fetch will never cause a cache miss.The more accidents
22、 excluded,the lower the upper bound.MurphysinvariantFastestVariance of execution timesSlowestAbstract Interpretation in Timing AnalysisAbstract interpretation statically analyzes a program for a given property without executing it.Derived properties therefore hold for all executions.It is based on t
23、he semantics of the analyzed language.A semantics of a programming language that talks about time needs to incorporate the execution platform!Static timing analysis is thus based on such a semantics.The Architectural Abstraction inside the Timing AnalyzerTiming analyzerArchitectural abstractionsCach
24、eAbstractionPipeline AbstractionValue Analysis,Control-FlowAnalysis,Loop-BoundAnalysisabstractions ofthe processorsarithmeticAbstract Interpretation in Timing AnalysisDeterminesinvariants about the values of variables(in registers,on the stack)to compute loop boundsto eliminate infeasible pathsto de
25、termine effective memory addressesinvariants on architectural execution stateCache contents predict hits&missesPipeline states predict or exclude pipeline stallsTool ArchitectureAbstract InterpretationsAbstract InterpretationInteger LinearProgrammingValue Analysis Determines enclosingintervals for t
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- Abstract Interpretation with Applications to Timing Validation
链接地址:https://www.taowenge.com/p-85460292.html
限制150内