Introduction To Cache Analysis For Real-Time Systems - Texas A&M University
CPSC-663: Real-Time SystemsDeterministic Cache AnalysisIntroduction to Cache Analysisfor Real-Time Systems[C. Ferdinand and R. Wilhelm, “Efficient and Precise Cache Behavior Prediction forReal-Time Systems”, Real-Time Systems, 17, 131-181, MPe.g.no caches(memory performance) Ignoring cache leads to significant resource under-utilization. Q: How to appropriately account for cache? R. BettatiWorst-Case Execution Time (WCET) WCET analysis must be safe WCET analysis must be tight WCET depends on:– execution path (in program)– cache behavior (depends on execution history)– pipelining (depends on very recent execution history)1
CPSC-663: Real-Time SystemsDeterministic Cache AnalysisProblems with Cache MemoriesTwo fundamental problems with cache analysis:1.Large differences in cache behavior (and execution time!) resultfrom minor changes in program code in input data2. Inter-task cache interferenceWCET analysis for single tasks remains prerequisite for multi-taskanalysis!Cache MemoriesMajor parameters of caches:1. Capacity: how many bytes in the cache?2. Line size (block size): number of contiguous bytes thatare transferred from memory on cache miss.Cache contains n capacity / line size blocks3. Associativity: In how many cache locations can aparticular block reside?A 1 “direct mapped”A n “fully associative”2
CPSC-663: Real-Time SystemsDeterministic Cache AnalysisCache Semantics A-way associative cache can be considered as asequence of n/A fully associative setsF f1, , fn/A Each set fi is a sequence of linesL l1, , lA The store is a set of memory blocksM {m1, ., ms} The function adr : M - integers gives address of eachblock. The function set : M - F denotes where block getsstored:set(m) fi, where i adr(m) % (n/A) 1 No memory in a set line:M’ M u {I}Cache Semantics (II)Cache semantics separates two aspects:1. Set, where memory block is stored. Can be statically determined,as it depends only on address of the memory block. Dynamicallocation of memory blocks to sets is modeled by the cachestates.2. Replacement strategy within one set of the cache: History ofmemory references if relevant here. Modeled by set states. Def: set state is a function s: L - M’, “what memory block in ingiven line?”– Note: In fully associative cache a memory block occurs onlyonce. Def: Set S of all set states. Def: cache state is a function c: F - S, “what ‘lines’ does setcontain?”3
CPSC-663: Real-Time SystemsDeterministic Cache AnalysisLRU Replacement Policy The side effects of referencing memory on the set/cache isrepresented by an update function. We note that– behavior of sets is independent of each other– order of blocks within a set indicates relative age of block. We number cache lines according to relative age of their memoryblock: s(lx) m, m ! I describes the relative age of block mEFFICIENTCACHEpositionBEHAVIOR PREDICTION141according to LRU,not ANDits PRECISEphysicalin the set. Def: set update function US: S x M - S describes new set statefor given set state and referenced memory block. Def: cache update function Ux PRECISEM AND- C describesnew cacheEFFICIENTPRECISECACHE BEHAVIOR PREDICTIONC: C ANDEFFICIENTCACHE BEHAVIOR PREDICTIONstate for a given cache state and a referenced memory block.141141Figure 3. Update of a concrete fully associative set.The most recently referenced memory block is put in the first position l1 of the set. Ifthe referenced memory block m is in the set already, then all memory blocks in the setFigure3. Updateassociativethat have been moreFigurerecentlyusedthanof amconcreteare fullyshiftedbyset.one position to the next set3. Update of a concrete fully associative set.line, i.e., they increase their relative age by one. If the memory block m is not yet inThemostrecentlyreferencedmemoryblocksetis putin the thefirst positionl1 of the set. Ifthe set, then all memoryin thereferencedset are memoryshiftedblockand,isifputtheis positionfull,‘oldest’,Theblocksmost recentlyfirstofthe set.If in the setthe referencedmemory blockm is in theinsetthealready,then alll1memoryblocksi.e., least recently oryblockm isinfromthe setalready,memoryblocksin the tosetthe next setthathave isbeenmorerecentlyusedthanareallshiftedby onepositionLRU Replacement Policy (II)that have beenrecentlyusedtheirthan relativem are shiftedoneIf positionto theblocknextmsetis not yet inline,morei.e., theyincreaseage by byone.the memoryline, i.e., they increase their relative age by one. If the memory block m is not yet inthe set, then all memory blocks in the set are shifted and, if the set is full, the ‘oldest’,: Sset areblockMshifted S describesthenew setDefinition 5 (set update). theAset,setthenupdatefunctionUinStheall leastmemoryblocksand,if theset theis full,i.e.,recentlyusedmemoryis removedfromset. the ‘oldest’,state for a given set state andreferencedmemoryblock.i.e.,aleastrecently usedmemory blockis removed from the set.Definition 5 (set update). A set update function U S : S M S describes the new setDefinition 5 (set update). A set update function U : S M S describes the new setstate for a given set state and a referencedS memory block.M C describes the newDefinition 6 (cache update).cacheC: C state forAa givensetupdatestate andfunctiona referencedUmemoryblock.cache state for a given cache stateand a 6referencedmemoryblock.function UC : C M C describes the newDefinition(cache update).A cache updateEFFICIENT AND PRECISE CACHE BEHAVIOR PREDICTIONM C block.describes the newDefinition 6cache(cacheupdate).A cacheupdateUC : C memorystatefor a givencachestate functionand a referenced141for a given cache state and a referenced memory block.cache stateUpdates of fully associative setswith LRU replacement strategy are modeled in theUpdates of fully associative sets with LRU replacement strategy are modeled in thefollowing way (see FigureUpdates3): offully associativesets withfollowingway (see Figure3): LRU replacement strategy are modeled in thefollowing way (see Figure 3): [l1 # m , [l #m,1 [l1 # m , l # s(l ) i li # s(li 1 ) i 2 . . . h, l2i # . . s(l. h,i s(l2i .) . . ih, h 1 . . . A]; if lh : s(lh ) mi 1 i 1l)i # U iS (s, m ) #s(l i h if1 . l. . hA];lii.) A];h : s(l #s(l) i h 1.: s(lhif) l mh ) mlU S i(s, m ) i U S (s, m ) [l # m , 1 [l1 # m , li # s(li 1 ) for i 2 . . . A];otherwise [l1 # m ,otherwiseli # s(li 1 ) for i 2 . . . A]; [y # z] denotes a function that maps y to z. f [y # z] denotes a function that)Notation:fory toi 2.A];otherwiseli # s(li 1mapsz and all x ̸ y to f (x).Notation: [y # z] denotes a function that maps y to z. f [y # z] denotes a function thatUpdatesof yA-wayset associative caches are modeled in the following way:maps y to z andall x ̸ to f (x).Notation: [y # z] denotesa functionthatmaps ycachesto z.aref modeled[y # z]denotesa functionthatUpdatesof A-way setassociativein thefollowingway:maps y to z and all x ̸ y to f (x). UC (c, m ) c[set(m ) # US (c(set(m )), m )]UC (c, m ) c[set(m ) # U S (c(set(m )), m )]Updates of A-way set associative caches are modeled in the following way:Figure 3. Update of a concrete fully associative set.UC (c, m ) c[set(m ) # U S (c(set(m )), m )]The most recently referenced memory block is put in the first position l1 of the set. Ifthe referenced memory block m is in the set already, then all memory blocks in the setthat have been more recently used than m are shifted by one position to the next setline, i.e., they increase their relative age by one. If the memory block m is not yet inthe set, then all memory blocks in the set are shifted and, if the set is full, the ‘oldest’,i.e., least recently used memory block is removed from the set.Definition 5 (set update). A set update function U S : S M S describes the new setstate for a given set state and a referenced memory block.Definition 6 (cache update). A cache update function UC : C M C describes the newcache state for a given cache state and a referenced memory block.Updates of fully associative sets with LRU replacement strategy are modeled in thefollowing way (see Figure 3): [l1 # m , li # s(li 1 ) i 2 . . . h,li # s(li ) i h 1 . . . A]; if lh : s(lh ) mU S (s, m ) [l # m , 1otherwiseli # s(li 1 ) for i 2 . . . A];Notation: [y # z] denotes a function that maps y to z. f [y # z] denotes a function thatmaps y to z and all x ̸ y to f (x).Updates of A-way set associative caches are modeled in the following way:U (c, m ) c[set(m ) # U (c(set(m )), m )]4
CPSC-663: Real-Time SystemsDeterministic Cache AnalysisControl Flow Representation Program represented as Control Flow Graph (CFG):– Nodes are Basic Blocks.– Basic block is “a sequence of instructions in which control flowenters at the beginning and leaves at the end without halt orpossibility of branching except at the end.”– For each basic block the sequence of memory references isknown. We can map control flow nodes to sequences of memory blocks (atleast for instruction caches) and represent this as functionL: V - M* We can extend UC to sequences of memory references:UC(c, m1, , my ) UC(. UC(c,m1) ., my) Extend UC to path k1, ., kp in control flow graph:UC(c, k1, , kp ) UC(c, L(k1), , L(kp))Must Analysis vs. May Analysis Must Analysis determines set of memory blocksdefinitely in the cache whenever control reaches agiven program point. May Analysis determines all memory blocks that maybe in the cache at a given program point. May analysis is used to guarantee absence of a memoryblock in the cache. Analysis for basic blocks and paths of basic blocks issimple. What about when paths merge?!5
CPSC-663: Real-Time SystemsDeterministic Cache AnalysisAbstract Cache StatesDef: abstract set state is a function s : L - 2M, maps set lines to setsof memory blocks.Def: Set S of all abstract set states.“An abstract set state sˆ describes a set of concrete set states s.”Def: abstract cache state is a function c : F - S , maps sets toabstract set states.Def: Set C of all abstract cache states.“An abstract cache state cˆ describes a set of concrete cache states c.”MUST Analysis ma sˆ(lx) for some x means that the memory block ma is in thecache. Observation 1: The position (relative age) of a memory block ma ina set can only be changed by memory references that go into thesame set.– i.e. by references to memory blocks mb with set(ma) set(mb). Observation 2: The position is not changed by references tomemory blocks mb sˆ(ly) where y x, i.e., memory blocks thatare already in the cache and are “younger” or the same age asma. Observation 3: ma will stay in the cache at least for the next A x references that go to the same set and are not yet in the cacheor are older than ma.6
CPSC-663: Real-Time SystemsDeterministic Cache AnalysisFigure 4. Update of an abstract fully associative set for the Must analysis.145EFFICIENT AND PRECISE CACHE BEHAVIOR PREDICTIONThe meaning of an abstract cache state is given by a concretization function concĈ : Ĉ 2C , or, worded otherwise, concĈ (ĉ) describes the set of concrete cache states that arerepresented by ĉ. The concretizationfunction for the must analysis concĈ is given by:FERDINAND AND WILHELMMUST Analysis: Update Function144concĈ (ĉ) {c 1 i n/A: c( f i ) conc Ŝ (ĉ( f i ))}conc Ŝ (ŝ) {s 1 a A: m ŝ(la ): b: s(lb ) m and b a}A concrete cache state c is in concĈ (ĉ), if all its concrete set states are described accordingly by the abstract set states of ĉ. A concrete set state s is in conc Ŝ (ŝ), if all memoryblocks that are in ŝ are also in s and the position (relative age) is less or equal than in theabstract set.WesetusethefollowingFigure 4. Update of an abstract fully associativefor theMustanalysis. abstract set update function (see Figure 4 for an example): [l1 ' {m }, The meaning of an abstract cache state is given by a concretizationconcĈ :. .Ĉ. h 1, li ' ŝ(lfunctioni 1 ) i 2 of concrete cache states that are2C , or, worded otherwise, concĈ (ĉ) describes the set lh ' ŝ(lh 1 ) (ŝ(lh ) {m }),Figure5.JoinfortheMustanalysis.represented by ĉ. The concretization functionformthemust analysis concĈ is given by:) Û (ŝ,li ' ŝ(li ) i h 1 . . . A]; 1 i n/A: c( f i ) [l ' {m },the oldest age, if it hasdifferentages(see Figure5).ŝ(lbi 1li m' and 1 two a A: m ŝ(l )a} i 2 . . . A];a ): b: s(lb ) ŜconcĈ (ĉ) {cconc Ŝ (ŝ) {sif lh : m ŝ(lh )conc Ŝ (ĉ( f i ))}1otherwise (ĉ), if allconcretestatesare describedAJˆconcreteis in concĈ Note:(ŝ1 , ŝcacheŝ, cwhere:2 ) stateTheitsproofof setlocalconsistencyof accordÛ Ŝ and U S can be found in Ferdinand (1997).Ŝingly by the abstract set states of ĉ. A concrete set state s is in conc Ŝ (ŝ), if all memoryÛ Ŝ preserves condition (4) on abstract set states.blocks that are in ŝ are also in s and the position (relative age) is less or equal than in theThe address of a memory block determines the set in which it is stored. The abstractabstract set.thesame structure following{m laabstract, lb withm updateŝfunctionmŝ2has(lb4)exactlyandan xexample): max(a,b)} as concrete cache update function:ŝ(luseWesetcacheupdate(see Figureforx ) the1 (la ),function [l ' {m }, ÛĈ (ĉ, m ) ĉ[set(m ) ' Û Ŝ (ĉ(set(m )), m )]1 The join function forabstract ŝ(li 1 ) icache 2 . . .statesh 1, applies the join function for abstract set statesli ' states:to all its abstract setlh ' ŝ(lh 1 ) (ŝ(lh ) {m }), Û Ŝ (ŝ, m ) cache states.Û preserves conditionif lh : m(5) onŝ(lhabstract) li ' ŝ(li ) i Ĉh 1 . . . A]; The join function for abstract set states has similarities to set intersection. A memory [[l f ' {mJ(ĉ1 ( fonlyforabstractall 1 n/A]JˆĈ (ĉ1 , ĉ2 ) },ˆ blocki ), ĉstays2 ( f i )) in theseti state,if it is in both operand abstract set states. It gets 1iŜli ' ŝ(li 1 ) i 2 . . . A];otherwiseIn order to use Theorem 1 to solve the must analysis for a program the abstract valuesNote: The proof of local consistency of Û Ŝ and U S can be found in Ferdinand (1997).have to form a complete join semi lattice.The order is imposed by the set inclusion order ofÛ Ŝ preserves condition (4) on abstract set states.the underlyingconcrete(sets oftheconcretecacheAdditionally,a (artificial)The address ofa memorydomainblock determinesset in whichit is states).stored. Theabstractleastcacheelementis used.(In practicethe elementusedfor function:initialization purposes forupdate functionhas exactlythe same structureas concreteiscacheupdatethe fixpointiteration, see below.)Û (ĉ, m ) ĉ[set(m ) ' Û (ĉ(set(m )), m )]For the Ĉdomain of the must Ŝanalysis we define the following orders:MUST Analysis and Control Flow Recall: control flow node k issues sequence of memory blockscondition (5) on abstract cache states.ÛĈ preserves Ŝ functionŝ2 forconc(ŝ ) conc similarities(ŝ2 ) mŝ1 join, ,my A memoryTheabstractto 1setintersection.Ŝ 1set states hasŜL(k)block onlystays in the abstractset state, if it isin both operand abstract set states. It gets ĉ1 Ĉ ĉ2 concĈ (ĉ1 ) concĈ (ĉ2 ) Simple case: node k has only one direct predecessor, say k’.We extend Ŝ by a least element Ŝ , where: Then there is an equation : , m , , m ) U (. U (c ,m ) ., m ) ŜU , ŝ)C (c JˆŜk’(ŝ, 1Ŝ ) ŝ y ŝ Ŝ: c JˆŜ k( C C k’ 1y ŝSolveequationbyfixpointiteration. Ŝ: Ŝ ŝŜ m M ′ : Û Ŝ ( Ŝ , m ) Ŝ Abstract cache state c k describes all possible cache states whencontrol reaches node k. Let s c k(set(m)) for some memory block m. If m sˆ(ly) for some set line ly, then m is definitely in the cacheevery time control reaches k. Therefore, reference to m is classified as ALWAYS HIT.7
CPSC-663:by its address.We will present two analyses. The must analysis determines a set of memory blocksthat are definitely in the cache whenever control reaches a given program point. The mayanalysis determines all memory blocks that may be in the cache at a given program point.Real-TimeSystemsDeterministicThe latteranalysis is used to guarantee the absence of a memory block in the cache.The analyses are used to compute a categorization for each memory reference that describes its cache behavior. The categories are described in Table 1.The abstract semantic functions describe the effect of a memory reference on an elementof the abstract domain. The abstract set (cache) update function Û for abstract set (cache)states is an extension of the set (cache) update function U to abstract set (cache) states.These functions will be defined in the following subsections.EFFICIENTANDPRECISE CACHEBEHAVIOROn control flow nodes withat least twopredecessors,join-functionsarePREDICTIONused to combinethe abstract cache states. Our join functions are associative. On nodes with more than twopredecessors, the join function is used iteratively.Multiple Predecessors: Join FunctionCache Analysis145Definition 9 (join function). A join function Jˆ : Ĉ Ĉ " Ĉ combines two abstract cache145states.EFFICIENT AND PRECISE CACHE BEHAVIOR PREDICTION4.3. Must AnalysisAn abstract cache state ĉ describes a set of concrete cache states c, and an abstract set stateOn control flow nodes with atŝ describes a set of concrete set states s.To determine if a memory block is definitely in the cache weleastuse abstractstates wheretwo setpredecessors,the position (the relative age) of a memory block in the abstract set state ŝ is an upper boundjoin functions are used toof the positions (the relative ages) of the memory block in the concrete set states that ŝcombine the abstract cacherepresents.memoryblockm aMustis inanalysis.the cache.states.The position (relative age) ofm a ŝ(l x ) means that theFigure5. Joinfor thea memory block m a in a set can only be changed by references to memory blocks m b withset(m a ) set(m b ), i.e., by memory references that go into the same set. Other memoryoldestofage,it hastwo differentages(see Figure5). Thepositionis also notchangedby referencesreferences do not change thethepositionm aifto memory blocks m b ŝ(l y ) where y x, i.e., memory blocks that are already in theFigure5. andJoin arefor theMust analysis.cache“younger”or the sameage a .ŝ, where:JˆŜ (ŝ1 , ŝas2 )mm a will stay in the cache at least for the next A x references that go to the same set andare not yet in the cache or are older than m a .the oldest age, if it has two different ages (see Figure 5).ŝ(l x ) {m la , lb with m ŝ1 (la ), m ŝ2 (lb ) and x max(a, b)}JˆŜ (ŝ1 , ŝ2 ) ŝ, where:The join function for abstract cache states applies the join function for abstract set statesto all its abstract set states: ˆ ŝ1((l [ŝ2f i(l b)}ŝ(l x ) {m la , lb with m Jb ) andĉ1a,),ĉ2m) JˆŜ (xĉ1 ( fmax(a,i ), ĉ2 ( f i )) for all 1 i n/A]ĈThe join function for eorder statesto useappliesTheoremto solvethe formustanalysisa program the abstract valuesto all its abstract set states: have to form a complete join semi lattice. The order is imposed by the set inclusion order ofthe underlying concrete domain (sets of concrete cache states). Additionally, a (artificial)ˆ (ĉ1element( f i ), ĉ2 ( f i )) for all i n/A]JˆĈ (ĉ1 , ĉ2 ) [ f i Jleastis used.(In1practicethe element is used for initialization purposes forŜthe fixpoint iteration, see below.)In order to use Theorem 1 tothe musta programthe abstractvaluesorders:Forsolvethe domainof analysisthe mustforanalysiswe definethe followinghaveform a completesemiklattice.The orderis imposedby the set inclusionorder to Simplecase: joinnodehas morethanone predecessor,sayk1 ofto kx. the underlying concrete domain (setscacheAdditionally,a (artificial)ŝconcrete conc(ŝ states).) conc(ŝ )ŝ1 ofŜ 2 :Ŝ 1Ŝ 2 Thenthereisanequationleast element is used. (In practice the element isused for initializationpurposes for ĉ2 conc(ĉ1 ) concĈ (ĉ(c 1 ,Ĉ ,2)c k U (c k’, ĉ mmy ) ĈU the fixpoint iteration,seeC below.)1C (. U C k’,m1) ., my)For the domainof the must analysis we define the following orders:whereWe extend Ŝ by a least element Ŝ , where: J ŜC (ŝ(c ) concŝ1 Ŝ ŝ2 conc Ŝ (ŝc 1 k’2 ) k1, . J C (c x-1,c x) .) ŝ Ŝ:Jˆ ( , ŝ) JˆŜ (ŝ, Ŝ ) ŝĉ1 Ĉ ĉ2 concĈ (ĉ1 ) concĈ (ĉ2 )Ŝ Ŝ ŝ Ŝ: Ŝ Ŝ ŝMUST Analysis with multiple PredecessorsM ′ : Û Ŝ ( Ŝ , m ) ŜWe extend Ŝ by a least element m Ŝ , where: Rest of classification of memory reference stays the same. ŝ Ŝ: JˆŜ ( Ŝ , ŝ) JˆŜ (ŝ, Ŝ ) ŝ ŝ Ŝ: Ŝ Ŝ ŝ m M ′ : Û Ŝ ( Ŝ , m ) Ŝ8
CPSC-663: Real-Time SystemsDeterministic Cache AnalysisMAY AnalysisQ: How do we know if a memory reference is an ALWAYSMISS?A: We determine the set of memory blocks that MAY bein the cache.MAY Analysis ma sˆ(lx) for some x means that the memory block ma may bein the cache. Observation 1: The position (relative age) of a memory block ma ina set can only be changed by memory references that go into thesame set.– i.e. by references to memory blocks mb with set(ma) set(mb). Observation 2: The position is not changed by references tomemory blocks mb sˆ(ly) where y x, i.e., memory blocks thatare already in the cache and are “younger” or the same age asma. Observation 3: ma will stay in the cache at least for the next A x 1 references that go to the same set and are not yet in thecache or are older than or have the same age as ma.9
CPSC-663: Real-Time SystemsDeterministic Cache AnalysisFigure 6. Update of an abstract fully associative set for the May analysis.MAY Analysis: Update FunctionEFFICIENT AND PRECISE CACHE BEHAVIOR PREDICTIONThe concretization function for the may analysisconcĈ 147is given by:concĈ (ĉ) {c 1 i n/A: c( f i ) conc Ŝ (ĉ( f i ))}conc Ŝ (ŝ) {s 1 a A, s(la ) ̸ I : b: s(la ) ŝ(lb ) and b a}A concrete cache state c is in concĈ (ĉ), if all its concrete set states are described accordingly by the abstract set states of ĉ. A concrete set state s is in conc Ŝ (ŝ), if all memoryblocks that are in s are also in ŝ and the position (relative age) is greater or equal than inthe fullyabstractset. set for the May analysis.Figure 6. Update of an abstractassociativeWe use the following abstract set update function (see Figure 6 for an example): [l1 ' {m}, is given by:The concretization function for the mayconc analysisĈ l 'ŝ(li 1 ) i 2 . . . h, i lh 1 ' ŝ(l h 1 ) (ŝ(l h ) {m }), mn/A: conc(ĉ( f ))}concĈ (ĉ) {c 1 ) c( f ili) ' Û Ŝ i (ŝ,Ŝ i i h 2 . . . A];ŝ(l)if lh : m ŝ(lh )i conc Ŝ (ŝ) {s 1 a A, s(l a ) ̸ I : b: s(la ) ŝ(lb ) and b a} [l ' {m }, 1otherwiseli ' ŝ(li 1 ) i 2 . . . A];A concrete cache state c is in concĈ (ĉ), if all its concrete set states are described accordingly by the abstract set states of ĉ. A concrete set state s is in conc Ŝ (ŝ), if all memoryNote: The proof of local consistency of Û Ŝ and U S can be found in Ferdinand (1997).blocks that are in s are alsoin ŝ and the position (relative age) is greater or equal than inÛ Ŝ preserves condition (4) on abstract set states.the abstract set.The abstract cache update function for the may analysis has the same structure as the oneWe use the following abstract set update function (see Figure 6 for an example):for the must analysis:148FERDINAND AND WILHELM [l '{m},1 Û (ĉ, m ) ĉ[set(m ) ' Û Ŝ (ĉ(set(m )), m )] li ' ŝ(lĈi 1 ) i 2 . . . h, lh 1 ' ŝ(lh 1 ) (ŝ(lh ) {m }),148 Û (ŝ, m ) ŝ(li ) i h 2 . . . A];ifFERDINAND lh :setm states. ANDŝ(lh )WILHELMli Û' preserves condition (4) on abstractŜ Ĉ The join function has similarities to set union. A memory block is in the abstract set state, [l ' {m }, if1 it is in at least one operand abstract set states. If a memory block s has two different agesotherwiseli ' ŝ(li 1 ) i 2 . . . A];Join Function for MAY AnalysisNote: The proof of local consistency of Û Ŝ and U S can be found in Ferdinand (1997).Û Ŝ preserves condition (4) on abstract set states.The abstract cache update function for the may analysis has the same structure as the onefor the must analysis:Figure 7. Join for the May analysis.ÛĈ (ĉ, m ) ĉ[set(m ) ' Û Ŝ (ĉ(set(m )), m )]in two abstract cache states then the join function takes the youngest age (see Figure 7).Figure 7. Join for the May analysis.ÛĈ preserves condition (4)ˆ (ŝ1 , ŝ2 ) ŝ, where:on Jabstractset states.ŜThe join function has similarities to set union. A memory block is in the abstract set state,in two abstract cache states then thefunctiontakesyoungest(see Figure7). {m l, lab thewithm blockŝ1 (lageŝtwoand x min(a,ŝ(ljoinx ) setaIfa ),smhas2 (lb )differentif it is in at least one operand abstractstates.memoryages b)}JˆŜ (ŝ1 , ŝ2 ) ŝ, where: {m m ŝ1 (l x ) and ̸ la with m ŝ2 (la )}̸ la with m ŝ1 (la )}(l x )xandm mŝ2 (l b )ŝ2and min(a,b)}ŝ(l x ) {m la , lb with m ŝ1 (l a ),{mjoinforŝ abstractcache states for the may analysis has the same structure as̸ lafunction) andwith m (l)} {m m ŝ1 (l xThe2 afor the must analysis: {m m ŝ2 (l x ) and ̸ la with m ŝ1 (la )}JˆĈ (ĉ1 , ĉ2 ) [ f i % JˆŜ (ĉ1 ( f i ), ĉ2 ( f i )) for all 1 i n/A]The join function for abstract cachestates for the may analysis has the same structure asAs for the must analysis, we define the following orders for the domain of the mayfor the must analysis:analysis:JˆĈ (ĉ1 , ĉ2 ) [ f i % JˆŜ (ĉ1 ( f i ), ĉ2 ( f i )) for all 1 i n/A]ŝ1 ŝ2 conc (ŝ1 ) conc Ŝ (ŝ2 )As for the must analysis, we defineŜ the followingŜ orders for thedomain of the mayanalysis:ĉ1 Ĉ ĉ2 concĈ (ĉ1 ) concĈ (ĉ2 )ŝ1 Ŝ ŝ2 conc Ŝ (ŝ1 ) conc Ŝ (ŝ2 )We extend Ŝ by a least element Ŝ , where:ĉ1 Ĉ ĉ2 concĈ (ĉ1 ) concĈ (ĉ2 ) ˆ ŝ Ŝ: J Ŝ ( Ŝ , ŝ) JˆŜ (ŝ, Ŝ ) ŝwhere:We extend Ŝ by a least element ŝŜ , Ŝ: ŝŜŜ10
CPSC-663: Real-Time SystemsDeterministic Cache AnalysisMAY Analysis and Control Flow Let s c k(set(m)) for some memory block m. If m is not in sˆ(ly) for at least one line ly, then m is definitelyNOT in the cache whenever control reaches k. Therefore, reference to m is classified as ALWAYS MISS.11
CPSC-663: Real-Time Systems Deterministic Cache Analysis 1 Introduction to Cache Analysis for Real-Time Systems [C. Ferdinand and R. Wilhelm, "Efficient and Precise Cache Behavior Prediction for Real-Time Systems", Real-Time Systems, 17, 131-181, (1999)] (memory performance) Ignoring cache leads to significant resource under-utilization.
Bruksanvisning för bilstereo . Bruksanvisning for bilstereo . Instrukcja obsługi samochodowego odtwarzacza stereo . Operating Instructions for Car Stereo . 610-104 . SV . Bruksanvisning i original
component of DIP predicts that the cache blocks that already reside in the cache will be re-referenced sooner than the missing cache block. As a result, when the working set is larger than the available cache, LIP preserves part of the wo rking set in the cache by replacing the most recently filled cache block instead of using LRU replacement.
This new Tag-Less Cache (TLC) reduces the dynamic en-ergy for a 32kB, 8-way cache by 78% compared to a VIPT cache without a ecting performance. Categories and Subject Descriptors B.3.2 [MEMORY STRUCTURES]: Cache Memories 1. INTRODUCTION Modern processors optimize L1 caches by trading energy for performance. As a result, a signi cant part of the .
called a cache between the main memory and the processor. The idea of cache memories is similar to virtual memory in that some active portion of a low-speed memory is stored in duplicate in a higher-speed cache memory. When a memory request is generated, the request is first presented to the cache memory, and if the cache cannot respond, the
the effective capacity of the cache, and hence, increases cache misses. We need to compare the effect from the in-crease of local hits against that from the increase of cache misses. Suppose we take a snapshot of the L2 cache and find a total of R replicas. As a result, only S-R cache blocks are distinct, effectively reducing the capacity of .
Memory System Performance h cache hit rate: the percentage of cache hits t cache cache access time, t main main memory access time. Average memory access time: t av ht cache (1-h)t main Example: t cache 10ns, t main 100n
SPARC @ Oracle 16 x 2nd Gen cores 6MB L2 Cache 1.7 GHz 8 x 3 rd Gen Cores 4MB L3 Cache 3.0 GHz 16 x 3rd Gen Cores 8MB L3 Cache 3.6 GHz 12 x 3rd Gen 48MB L3 Cache 3.6 GHz 6 x 3 Gen Cores 48MB L3 Cache 3.6 GHz T3 T4 T5 M5 M6 S7 32 x 4th Gen Cores 64MB L3 Cache 4.1 GHz DAX1 M7 8 x 4th Gen Co
EDUQAS A LEVEL - COMPONENT 1 BUSINESS OPPORTUNITIES AND FUNCTIONS SUMMER 2018 MARK SCHEME SECTION A Q. Total 1 Give one example of a business using batch production and describe two benefits of this method of production. Award 1 mark for an appropriate example. AO1: 1 mark Indicative content: A baker making loaves of bread; a clothing manufacturer making batches of a particular garment; a .
