An efficient solver for Cache Miss Equations

AN IZFI~ICXENT SOLVER FOR CACHE MISS EQUATIONS * Nerina Bermudo, Xavier Vera, Antonio GOIIZBIC~, Joscp Llosa Coniputcr Arcliitccture Department Univw'sitat Politbcnica dc Catalunya-Barcelona {nbermudo, xvera, antonio, josepll}@ac.upc.cs ABSTII AC'I' Cachc Miss Eqnntions (CMLI) [21 is n incthoil that accnratcly describes the cache behavior by nicnns ofpnlyhcdra. Gvcii though t.he computation cost ol generating CME is a linear luiicticin nl' the number of references, sdvitig them is a vcry liirie consiiiniiig task utid thus trying to study a whole progr tl m tn ay he in fcasiblo. This paper presents effectivc tcchniqucs that cxpluit somc propcrtics OP Ihe pnrticular polyhedra generated by CME. Such rechniques rcdticc tlic cuinplexity of thc nlgurittiin to solvc CMG, which results in n significent speedup whcn coinpared with traditional methods. In particular, thc prop(iscd approach does not require thc computation of thc vcrticcs ol' each polyhedron, which has an cxponential coi nplcx i ly. I INTRODUCTION Cache Miss Equntiotis 121 arc a very accurate analytical iriorlel of the c;ictic mcmory. They describe the cnche behavior. by rnenns of diophnntine cquntions, which allows 11'; to use mathematic;rl tccbniqucs to compute the locality of cidl incinory rcference. For instnnce, by solving CME onc cr~rld c(impitte the different types of cache misses that each refcrence will causc. Unfortuiiatcly, a dircct solution 01' ilic CMB is compiitationally intractable due to its NI'- hnid iintiiix. CME allow us to study each rcfcrciicc in a particular itel.iitioii point intlepcndcntly of all othcr mcmory rcfcrciiccs. nccicling whether n reference cmises i? miss or il hit for ii giveii itcraticui point is equivalcnt to dcciding whcther it helongs to the pnlyhedra rlefitietf by the CMU. The iwiibci01' cnche inisses can be computed by analyzing either all iteration points 131 or a subset of thein ttirougti the use of statistical tcchniqrics 141. In this pwper, wc pi'cscnt erficieii~ techniques to count ttrc nuriibcr of integer points inside the polyhedra defined "Thk work ]ins IICCU cuppomd Iy tlic ESPRIT projcct MHAOTEU (lit' 24942) mid tliC CICYI' pi-oject 51 1/98, 0-7803-641 8-WOO/$lO.OO @ 2000 IEEE 139 by thc CME. By cxploitiiig soinc intrinsic properties of tlic palticular typcs of pdyhcdra generated by CME, we rcduce the complexity ofthe atgorithm, which results in very high speed-ups. We show that the proposcd tcchnique cnn coinpute the inks ratio of most SPECfpD5 benchmarks just in a Iew seconds on a lypical workstaticm. This opcns the possibility to iticlitde this niialysis i'ramewnrk in production compilers in order to snpport many optimiziitiuns. The rest uf this papa is organized as follows. In section 2, some background on plytiedrn is reviewcd. Section 3 sumrnarizes thc in& featurcs of the (:ME. Section 4 dcscrihcs some crileria €or detecting cinpty CME polyhedra. Section 5 presents R techtiique to compute whether n reference is il miss for a particular iteration point. Section 6 discusses thc computation cost uf the niethocls describcd in the previous sections. IGiiaIly, section 7 dmws the main conclusions of this work. 11 HACKCROUNI) This sectioti revicws tlic tlefiniticin of cotivex polyhedra and n getieral method to compute the nuinbcr of integer points inside of it and a technique to identify whether it is cnipty. A Definitions 1)efiiiition 2.1 Given the points 21, . . . , :I:,& and scalars A,, I , , A,,, we defne a convex co~nbiitatioit of XI,. . . ,xpt as Er-, Xaea whcrc E;:, Xi = 1 and all Xi 2 n. Dctiniticm 2.2 A iwmvofa set I< is any point iti Ir' which cnnnot bc cxpw"i as a coiwcx combination of any other distinct pain& in IC. Definition 2.3 A sct K is (:onvex U evcry convex combination or any two points io Ir' is also n point in K. Definition 2.4 A cowex poljjhedron I' is the intersec[im of R finitc iinity of clr)scrl lincar half-spaces of the fortn {ZIC,?' 2 c} whcrc n is a noli-zero row vector and c is a scalar constant. We only consirlcr bounded convex polyhedra becausc polyhcdra defiierl by Cache Miss Equatiuns are cotivex and always bounded. Sincc the points of ii convex bounrletl polyhedron cm be expressed as a convcx coinhination of its vertices, 21 polyhcttron is fiilly rlcscribcd by its verticcs. 'Thcrcfore, thc plyhctlril can be given either by x system ol'lincar constraints or a set of vertices IS]. Ibfiaitinn 2.5 Wc rlcfitic thc red rliliiiui~i(inregerdnmnm) of a variablc :I: in a polyhedron I' RS the range oT rcal valucs (intcgcr values) it takes inside oPP. 11 Rnipty Pnlyhcdra Srilving ilie CME requires tn compute whether some polylicrlrn arc empty. A polyhedron is considered ernpty when it does not contain any intcgcr point, although it inay crmtain rcal points. Coinitiiig ihe number of intcgcr points in cmpty ~polylicdra often takes as much time as doing it for non einpty polyhcrlra. 'l'hus, a critcuia foiidentifying ernpty polyhcdrii inay be desirable. Fos ;I given polyhetlron, if there cxists a variable that cimnoi. take any integer value, therc will not hc any integer points insidc thc givcn polyherlmn. This gives us it gcncral criterion fol-.rlctccting cinpty po1yhcdr;i , itlthough it does not dctcct all of thcin. For each variable xk, its definition clr)m~iin [(t.~~, hh] in thc polyhcdron is calculatcti. Lct khk and ~rba, bc thc ltrwcr ;ind upper boiinrls of thc corrcspmdent integer domain. Ifdi~ < Ibk then the polyhedron is etnpty. C Coiintiiig Integer Points Thc niethorl lor couiititig pl-cscnterl next is h;iscd oti the lxt tlial [lie vcrliccs oT a polyhcdron arc cxtrcine points. This iniplics that the greatest and smallest values that any voriaI)lc C;III takc insidc a polyhctlron can be found in the verticcs. Thcrcforc, tlic ci)mpntation of the domain of a variatilc can be done using its vertices. I.et I' be ;I polyhedron in W. Wc wke il variabie xi ;riid c:ilcul;itc its intcgeldoinaiti {lbi, ubi]. Then, for every intcpcr value x from rhis doninin. wc consider the (p-I)- rlirnuiixinrrnl 11oIytictlrn that result from giving tlic vnriablc xi the value 2. This IJ~DCCSS is rcpcatcd recursively, until wc liiivc polyhedra delined onIy by onc vsiahle. LcL P,', , I . , .PiT be these polyhcdm. Thc nuinher of integer points insitlc onc of thcin is lib - Ib + 1, where ub and Ib are the iippcr and lowcl houiitls of the corresponding vilrinble. Thc total numher of integer points in the polyhcLImi is obtained by idding thc pilints of P:, . , , , Pif. Itemarks 1. Thc selection of the variable to be fixed is not irrelcvanl. Sincc in gciieral the domain of' a variable in U polyhcdron is a function of the other variables, we take evcry timc the variable that has tho smallest definition domain in order to minimizc thc number of nodes in the recurrence tree. Although wc do spend soinc timc in choositig the vnriablc, this criterion helps 11s to reduce the hc consumed by counting thc numbcr of iiitcgcr points inside thc pnlyl~erlron. 2. Thc domains of the variables arc calculatetl as follows: J.et ZA hc tlic vaIiahle whose domain we want to detcrminc. kt Vp bc thc sct of vertices of r. Then the hounds of thc inlcgcr domain of the variable iu P are: l6k = r min ilk1 whfi r: 1 trmx uh J Unfurtunatcly, computing the vertices of il polyhedron is ii problcm with cxpcincntial complcxi~y. Our approach avoids this cxpcnsivc phase of the coinputation. U:.;(. L ,... ,TI,,)€ I'p v=(v ,,,,. >v,.)Cvp 111 CME Ov~~vraw CME 121 are :in analysis framework lhwt describes the behavior of il cache meinury. The general idciz is to obtain for each mcmory rcfcrcnce ii set of equdities and inequalitics defined over tlic iteration space that represent the cache misses. Thcsc cquations iiiakc use of the reuse vectors l:fi]. I!adi cquattirm' describes the iteration points where thc rcusc is not rcalizcd. This section prcscnts an overview of thc CME. Our study is inainly based on the structure of thc CME polyhedra. Tlicrcforc, ttic interpretation of the diffct-cnt constants that appear in thcir definition is avoided except in some special cases, where tlic incaning of somc of lhcm is useful for the tlcvelopincnt of nur techniqucs. For morc dctails mi Cachc Miss Hquiitions, thc interested rcader is referred to the original publications [2, 31. . . . , gTrr are integer villties. For each induction variable ik (k = 1.) , . , ,m.), uhk and Ibk stand for the upper and lower bounds of Ihis variable in tlic itcration spacc. A Cold Miss Hqoations Thcsc cquations describe the iteration points where a rcusc dma not hold bccause the reference reuses data from an iteration point outside the iteration space, 'L'hcsc pdyhcdra arc defined ovcr the iteration space. This tnentis the We assutne that fi, . . . , ff,,, . - . .. . . 'The term etlitation hm becn used loosely tn rcpimcnl n SCI of siiiiultalicoils cqiialitics or i~icqmlitics. 140 only variables that appear iii their definition (in the lincw inequalities that ciinractcrize the sct), are the inductioin variahlcs. The Cold Miss Equations constraint the possihie viiliics ot'one ofthe variables inside thc iteration space. Thcy hi.we the Following forin: wlicrc if corrcspoitds to the I-th variable of the itcri~ticin space, dl E X. Thc lirst equation represents an additional iwtriclioti 011 oiic of the variables. Nutc that this equatiun CtJLIld i ntnicluce t~ hwer bound of the viuiahlc il;, instead 01' ilI1 Lipper boiiiitl. The othcr 2m constlwints determine the itel.ation spncc. i! Cold Miss Bomids 'I'hcse equations descrihc Ihe iteraticin points where ii spnlial rcusc is not rcalizetl becausc the reference reuscs (lata thal is iiiappcd in a cliffwent cachc line. These polyIiuIra arc tIcfinerI OVCI' Rn.l.I , wticrc rri is the dimensiuii of tlic itcration spic~. A new wrinbie z is ititroducctl for 1inc;irity rcasons [I 1, In fact, here is ii vcrsion oflhe cache inks etlu;\tions Iliiit ignorcs Ihis v;uiahle 131, but we focus UII the iiiorc precise niodel that incluclcs it. The equatiuns IIilvc thc following hni: jlil + f2i2 4. " ' + f,,,.i,, - Lz 2 Ln ],it +fA+'" + f,,i,, -- Lz 5 un lllk 5 ik z: Plhk, (L'fwq k = 1 , . . 711 wlim LJIl, LDa, 1/11 E Z,anrl Lis the cachc linc size. I: Rcplaecinont Eqiiations Givcn n rciclcncc, Replaccmcn1 Equations rcprcsent its interfercnccs with atiy uthcr reference. For each pail ol'refereticcs (RA and nn), Ihc following oxprcssioti gives thc cnnrlition for ii cache set contetition in ;L k-w;iy set associative cache: Ch CllC? "SP t ( fi ,I r3 c n clte-Sc: t ( j) R ~ I E ;r whci-c J represents ttic iteration poiiits lxtwcen ;(the curre.iit onc) and Ihc itelation point hmni which RA rcuscs. 'I'his iclciitily results in 'I'tiis is the type of polylicrlron obtained from thc CME lliat lios lhc most complicated q~ology. A Kcplaccmcnt polylietli.on is containccl in lK2''~r+R. 2~ri of' its variables (i I ~ . . . , i.,,,, jl: . . . , j,,,) refer in soinc way to the iteraticin spx~ and the reinaitiiiig variables (b, 11, and x) artiIicid iintl havc hccn introduced, as in thc ciisc of the Cold where ArJ, AL, DW, UL E %. Solving CMA The points inside cadi CME polyhcdrot] rcprcsent the potential cachc misses (the number ok'points is the numbcr of potential cnchc misses). This leads 11s to consider several ways for computing thetn: Snlver Given R reference It with ni reuse vectors and rik equations for tIic Pa I-CLISC vcctor, ttie pnlyhcdron that contains all thc ilcrnlioii points ttiat rcsirlt in a miss is [Z]: S c t I M i s s i: s = n rT1 U;: I Snlq.iti on. -,5 e t _Equ ut i un j This approach itnplics tu count the numbcr of points inside ttie un?on nf cunvcx polyhcrlra. 0 'lkavcrsing the iteration space Given a referencc, all the iteratirni pciints ciin bc tcstcd intlcpendently 131. 141I this approach, we need io compute whcthor a polyhedron is empty after sulistitutit1g thc iteration point in the equations. In n k-way set associative cwhc, there are k caclic line in every set, so k distinct contentions nre needed hcfore a cache miss occur. 'I'hercforc, the first method cm only be applied to direct-mappcd crichcs whcreas thc second tnethorl works for hoth direct-mappcd and setnssociative organizations. Our proposal builds upon the second nicthorl. 1v RFMUVIN(~: I'MPTY I'Ol.YI-[Er>RA The complcxity of boih methods inentiooetl ahovc is a hinction of tlic nmnbcr ol CML polyhedra. For this rcasm it is interesting to rcducc the number of them. This scction presents somc critcria forderecting empty CMH polylicdra. The gcncral cciferioti that has been presented in scction I3 docs not detect dl empty polyhctlm. 111 cirdcr to increase ttic nuinhcr 01' detected empty polyherln~, spccific criteria for cnch type 01 polyhedron have heen (levclr)pcd. These criteria rcly on thc structure of the equations and thcir interpretation iii tcrnis of tho cache behavior. 141 A Cold Miss Equations Sincc cncli of thcsc polyhedra coiisists of the iteration space and an additionat constraint on one of the variables, it will be empty if the constraint is incompatible with the iteretion space. If' the additionat restriction has the form i, 5 dl and dl < 11~1, there is B contradiction between the two conditions and WG conclude that the polyhedron is einpty. The same happens when the constraint has the form I:, 2 (Jd and di > I&. Hence. the time taken to compute the cmptiiicss is o(I). B Cold Miss Rounds Recall the equations that define the Cold Miss Bounds polyhcdi-a. Sincc thc domains of il, . . . , i, are explicitly given, and lhey arc not constrained by any other equation, the only variable that might have R domain without integer values inside is variable 2: Let us observc the constraints invulving varinble z. f,%13.'..+f,rti,,l-~B< Lz 5 f,il-t..~+fminl-LR Wc haw that where 1 stands for the iteration space. Then, the integer domain ofthe variable 7 in the polyhedron (CMB) is [[zlraanl, L~~41 n E If there me no intcgcr values inside this interval, we can conclude that the (CMl3) polyhedron is empty in O(m). This condition is su'licicnt, but not nccessary. That is, even if the domain of z contains integcr values, the polyhedron [night bc empty. C Rcplnccmcnt Equations Different critcria to detect einpty Replacement polyhedra have been developed. In this case, not only the inforrnntion given hy the equations is considered, but also its intcrpretntion in tertns of'thc cache behavior. In a Rcplacement polyhedron, there is a subset of equations which relates the variables ik ancl jk fork = 1,. . . , ~n. ik-,jl;>pk, ik-jksqk, k=i ,.., m Thcsc equations appear from the division in convex regions of the domain ofthe variables jl, . . . j, [2]. 111 order to detect empty Replacement polyhedra, it is cliccked whyher these constraints are consistent with the fact that i and ;must belong to the iteration space. Thc worst case complexity for calculating it is O(m). 0 Convex Rcgions: Mernn, - MCWLR~ and the vnriable n have different sign: Recall that Replwcernent equations result from the following identity: where RA and RB are the references whose interferences are being studied, C stands for cachE size, where k is the associativity of the cache, n stands for the distance between RA and Xn in cache size units, and b is the difference between the offset of each reference with respect to the beginning of their respective lines. Sincc the placement of the two references RA and Rn in the memory is fixed, their relative position will not change, so that $f:nzn, (9 - Mem.n, (;) has constant sign for all i, j. Besides. this sign must be the same as thc sign of the variable n, as this variable represents thc distance, in terms of cache sizc, between the two references, A Keplaceinent polyhedron is empty if the range nf feasible values of the expression MemRn (3 - Memn, (i), (which depends on the variables il,. . . , 'i, and j1, . . . ,j,,), causcs a contradiction with the conslraint that determines thc sign of the vai.iablen. This can be donc in O(1). 0 Incompatiblc range of Mcrrzn, -PIemlZn with the constraint an thc variable n: Dfipending on the constraint on the variable n, one of the fotluwing expression holds: nl -1: As this restriction gives an uppcr bound of n, that is a lower bound of -R, we considcr the second constraint 411-nY 2 f~ii-~,..t.I,nim+eiji +...+arnj,n-Cp 2 fiii +, . . + Im i, 1oljl t, . . + n,,j,, + C 2 miu (IIil +...+ fmim+~lii+. .+unrjn,> ?E1 ,jEJ -to n>l: Infiis case the considered inequation is the first one. AT. - Dl, 5 5 5 )til .t,, , + fmi~,a +olil i-, . , + gmjn~ - 6th fi'i ,+. . + Inlink + siil -k.. . + Rmjm + C llinx Xr.7w i-c (Jiii .I. .. . t Inlint +. eij1 +. . . +81nirn1 where 1 sfands for the iteration space and d for the domain of (jl, . . . ,j&). In each of these cases, if the constraint does not hold, we conclude the polyhedron is empty in O(m). 0 The variable TI cannot tnkc intcger values: The inequlztions (1) and (1) are used in order to compute the domain of the variable n. If it contains no integer pints, the polyhedron is empty. 142 Hence, the worst case complexity to decidc whether a Re- @cement Equation is empty or not is O(m). V ANALYZING ITRRATION POINTS This section shows some inethods for knowing whether a11 iteration point i; fulfills a CME. This problem is equivalent to finding nut whether the resulting polyhedron after substituting the variables il,. . I ,i,, with the values given by the iteration point is empty. A Cold Miss Equations ied. Thc only inequality it might not verify is Let $ = (iul, i02,. . . , iona), be the iteration point studas the others represents the iteration space. So, ii is apoint from tlic given Cold Miss polyhedron its I-th componcnt verifies inequality (1). B Cold Miss Bounds When an iteration point i; is substituted in the Cold Miw Bouinds Equations, n I-dimensional polyhedron is obtained. Deciding whether i; verifies the equations is equivalent to deciding whether the I-dinaensionalpolyhedron (CMB') LB' 5 -Lz 5 UBI IS cmpty, where LB' = LD - fiiol - - + - jPrmionm and The reel rlornnin of the varinbte 2, [ - "L"' , - "."'I c R, is first computed, and ihen the integer domain of z is obtaincd froin its rcnl domain. By comparing its bounds, it is tletcrinincd whether it is empty. C RepIaccment Equations Afier an iteraation point i; has been substituted in the cquations of n Replacement polyhedron, the problem of deciding whether it is a potential miss depends on the associativity cif tlic yhe. When considering ii k-way set associative cache, io fulfills the equations if the polyhedron . contains a set of inleger points with k different values ofthe iwinble IL (that represent k distinct contentions, k 2 1). We propose II inethod for counting integer points inside Rcplaccnien t polyhedra that works either for direct mapped ciiclies 01' for sct-associativc orgnnizations. C. 1 Counting Intcgcr Points In this scction, a inethud for counting the Replacement polyhedra will be dcscrihed. It is based on the general method prescnted in section C, extended with n new technique to computc thc domains of the variables. WiP = uu - f,io, - . ' ' - frrLiOna. When considering a k-way set associative cache, n polyhedron is not empty when it contains a set of integer points with at least IC different values of the variable n, From the definition of (RCM') we can derive the following conclusion: The domains of the variables j, , I . . ,j,, are explicitly given in the expression CIF the polyhedron, so they do not need to be cahlated. The domain of the variable n can be calculated by means of the two ncxt incquations: 01 11 + '' + amjml - UU' 5 ~n 5 gijl + . , - + gmiln - Dr.' (2) Let us define nmin where J is the domain of j' = (jl,. . . ,,jm). Then, the integer domain of the variable n in the polyhedron (RCM') is [rnminl, 1n7n4 n z We can thus conclude that the domains of all variables are easily computed and the explicit computation of' the vertices is not needed. Since the domains of the variables jl,. . . , j, may change when the variable n is fixed, the order in which the variables will be fixed cannot be determined at the beginning. Thus, the real domain of these variables must be recalcuIated every time. This is done in a similar way to the computation of the domain of n in the initial polyhe dron: for every variable jk, its greatest and lowest valucs given by the two inequations (cq. 2) nre calculated. The actual domain of this variable is the intersection between this interval and the explicit domain giwn by the equations of the polyhedrun. In order to detect empty polyhedra, the search ofempty integer domains must be done for all the variables. Thcoretically, the complexity is #(#iterotion-points), but in practice, it is O(1.5pn) for our benchmarks. VI PERFORMANCE UVALUATrON We have generated the CME for tlic SPECfp95 benchmark suite. For each program, we havc chosen the most time consuming loop nests that in total represent between the 60-70% of' the total cxecution time using the reference input data. A Empty Polyhedra Pirst we evaluate the effectiveness of our proposal for detecting empty polyhedra, assuming a 32K direct mapped cache. Figure 1 coinpares our mcthod with the technique 143 ............................................. ............................... , I' ............................................. ................................. ....... Figure 1. Empty Polyhedra oi'thc Polylib [,SI for dctccting ctnpty polyhedra. Oiily Replaceineii t pnIyIietlra Ii;ivc been considered, as their evaluatiori is thc inust time consortling atnorig dl CME polyhedra The first cidinnn shows the number of Replacement polyhetli,n obtnirietl for c;ch SPEC1'p95 program mnlyzetl. Thc sccuiiti colomn depicts the niunhcr of empty polyhctfra tletcctecl by nur approach, wliereas the third colii inn shows thc iiiirriber of empty I<eplaccmcnt dctccted through thc l'dylib. We can see that cHIr approach dctccts U signilicnntly higher numbcr of cinpty polyticdm. This is due io thc fact that Polylib only detects polytiedra without any Ical point insirlc. Cultmns I and 2 of table 2 show ttic execution time rcquired hy hoth tncihnds to check the emptiness trl all polyhedra. Uuc fo the coniplexity ol' the coinpulation 01' the vertices ol' n polyhedron, our proposal is much Iistcr than Polylib's technique. The cornplexity of the prop~xi nicthritl is O(ITL). On the other hand, Polylib's rnethotl relies on cotnputing the vertices of each polyhedron. The cumplexity of the algorittim that it uses is Cl(#~:nn.stl.ni~s-t~1~-.-2-- -,I). For IZeplacernent Polyhedra, thc nirinber of constraints is 2mn + 3 and the number of varinbles is m + 1, where m is t.he nesting depth of the Iricqincst. Thus, the coinplcxity of Polylih's approach is lln, llllrlC0 1. I,) (*rl i y R Analyzing Itcrilti(>n Poinb In order to evaluiite the techniques proposed lor analyzing itcr;ition points, we implemented a solver of the Cache Miss liquations hascd on trwersitig a subsct of the iteration spacc through sainplitig techniques as described in 141. Next, we evaliialc Ihc el'fectivcncss of thc proposcd technique fnr hoth dircct niappcd and sct-associative caches, and it is comparctl Io an algorithm that counts thc nimhcr of iiitcger points inside the polylicdrn by means of the gencral mclhad loor counting presenlcd in section C. The computation of thc vcrticcs [)E tlic lmlyherlrtl needed for this second rnethotl (Verfire.7) is dnne by incans of' functions from tlic Polylib librmy. Tnble I shows .the tiinc in seconds required to atialyzc the different SPECfp95 [or four dif'fcrcnt orgariimtiriiis of sct-associative caches, for both the proposed method nnd thc Verlices method. The specd-up of 011r appIo;ich is vcry important, due tr) the different complexities of both algorithms. For a direct mapped cache, it is between 7 and 41 8 times faster than the Vclriices method and it is 30 on average. 'Uic spced-up for different set-associative conIigurations is cvcn higher. For instance, the average speed-up foot a 4-way sct-associative cachc Is 42. The differerice between these two algorithms relies on tbc apprrmh tu compiitc fhc doinains of all variables. Thc ploposcd method clocs it with a coinplcxity of O(rnZ). Thc Vertices neth hod is split into two stcps: first the vertices of the polyhedron :Ire computed with a complexity of O(mi yj), as explained in the previous section. Then, by mcans of thc vcrticos, thc dom;iins of the variiiblcs :ire computed with a complexity of 8(mn * #?icptices). Note that most programs can be analyzed by the proposed approach in less than a iiiinutc and thc most expensive one is npplu which takes about I .5 minutes, whereas the approach based on the Vercices method takes several minutes anti in the worst use it trikes innre than one hour. 144 Table 1. Execution time for different cache organizatlons using an Origin2000. Table 2. Execution time (in seconds) using a Sun Ultra Sparc I. VI1 CONCLLJStONS ticins. Technical Report UPC-DAC1999-50, Universiht Palitbcnica de Ctitalunya, November 1999. C:achc Miss Equations prnvidc nn aiialytical atid precise rlescription of thc ciichc inemory behavior. Ilnfortunately teger points insirlc polyhedra is R very tiinc consuming task thal inakes them infcasiblc for inany ~pplicatioiis. In this paper we proposc some techniques lhat exploit sonic intrinsic properries of thc particular polyhedra generntctl by CME. These techniqoes significantly reducc he cnriiplcxity of thc nlgoritlinis and result in spccd-ups of inorc tlim one order of magaitudc fnr the SPECTp95 Imicliinarks. This irnportantspccd-up is due to the fact that he propnsctl appr(i:ich does iiot require the computatinn of thc vcrticcs OF thc nssocinted plyhcdra. Wc have shown that thc prnposccl approach usually takcsjust a Few seconds lo analyze R program 01 thc SPECfpp95. and it never takes iiiorc thw 2 ininiites Ibr the different cnchc configurations that liavc becn aiirdynetl. This cost is sindl enough to allow the technique tn Ix iticluclcd in a production compiler. [s] D, Wjl&. A library for CloiIIg polyhedral operations, sol viiig CMR hy t.raditiona1 methods based on counting int 993. [hl M. E, Wolf and M. S. Lam. A datn locnlity optimizing algririthm. In ACM SIGFI.AN91, pages 3044, 1991, REFERENCES I I I t'. Clatiss. Couiiting solutions to linear atid iionlinear constraints through ehrhart pol ynoin ial s: applications to analyze AI~S transform sciciitific progmms. In ICSY6, ~YI~CS 278-2R5, 1996. 121 S. Ghosh, M. Mnrtotiosi, atid S. Malik. Cacbc miss cquations: an analyticnl represetitation of cache inisscs. In IUS97, pagcs 3 17-324, 1987. [3] S. Ghosh, M. Martotmi, and S. Malik. Prccisc miss niialysis for program trxnsforinatir)ns with caches of ;uhitlary associativity. In ASI'LOS98, 1998. 141 X. Vera, J. Llosa, A. Gonzalez, and C. Ciuranetn. A fast iinpletncntation of cache miss eqiia145