ࡱ> ibcdefgh@= q9it2 X7=Td8U. x[}lTw|;8LMm=qظih5.v%gG?h QEMdҴ iZQԄCF? *iD̾ٻ}&.΄bVw+>'Kty]a"s WuJ[6koz߯̐w|f!GGGsvQH^ɲx~~gy2jje*{+vk?=H؄$?bW˸ -T1hiRO{o!"mFB`3riK䝶Dv7z7lsxt#V -b,S 9~t3&hfMެɫ4yU7_:2K_x Uį,%Oz|>䚀NwDoҧU'ś=\Z qnuk FpرR]HrHO"D9vdao4OC/DR rYD޹~W/"ݍtF"r0msnC= (CΈ Ӗ;o_:eFRqD-w@7^߫hb´%NK;:'0muWDnAۖ=WQ#AOaig Kb0-]Jۍ (\*sGR2,?;ן=A^D韪o 'ufZ=';/nÖ] $z.hӉ_5FwWqѹr8(j[AXkPo$j J_b:izU5F;vK,3=ڢPՑ<"wB^d@EkZh#=xٵsWZwWtԷ+Oo]6h>5}5cH .d} UaM~XG4yD7kfM^f(UaU,5y\'4M~ATyPA7h&'jHsoEs8v(փɾ!M7JN}\MOo <}ųA_})o@h^ "c)?F:%b镶n']F#Ⱦ/}z0.mwS);þ(%}OI_}KH<]of/Nsk.uC*"%YiAd6mH/ =1#O&f#DR6Q1Z j("0c佐}#y^ o*<}mH|PU̕~ZD v}u6bGFʆ{~T@ō9pK11d9Y}A&xΘSr;$tzY4zN6[FmV)&L/[+p?|YI^6{/j*@3}Z\WzyoñMHja/#?v`c,]dW;a9pƜcA[ϊybDqkړHǑ.k0䇺7Cxt8F6l1_S D2{6Gؙ ŗ-E<!}u|)L1)f_FWp-hM\;O,t^JXWy"17NbǺWl<_S2R۬A?b] rc3%د͑$>Rs6;S\${/O6<" cW I%ɽcEɽ/{sfxoWro{Ocyț7cg:7P12o9JmY>lgJY'qЫ1trFo :D!{TV\1}{=D88Qb_E /!WJM5o2gskuz C댱2Qe: ?Ӂ+xmR>m=m>/xL'J].mަ~qf<,,[>+ӦLK? 7^an}Uu‘D PNG  IHDR7;sRGB pHYsjPLTE׀@.ĂACIDATh۱m03* O@@ iҳ iUr r|-??U Qn6:rQ5|eW (. 8<pTΜ&.4iw.UFL  ώ8@> F(Ahʁd!`w1dqjGKP2@W DbJ@d,>u 5 bd)z_Ġyl_xo >{7KkavYËnIENDB`@=\%Q6bm`ڳ=L>0(;bri7uxZ}lTE}z-ZX<9?J"*5 b4^=,DGDM$ƿ$+&&%?0~=HbF!1jٝ۾{]&owgwfvf;IWd=@"k`].#օhP,DjGBq v$ѲwԮg!ps.498N|9w\W2K8y$;t.RkWAݲBڅ}3堍M'.;dR9tSO^s@٭VVKsx<Hǁ_7]/ x5-19 '7_SiߴBܾwޢQ|]hCfW潖6%<"%D@[(h.odl8ln z >LinҽHaZ|Q?j[YŏWji)kSc%=#&VK'NX/NO Tyyyk:OT鼊6KZs~\ڣo*Q"W^[v^:0nmoخm~rH#G8^b~I=Y_y iVnK 1q;։<,{\SdVv}S:eOփ׻\.[v+ټmاDٶXSX>.m+X ߾,:eOփ/6| ns>:eOփw,zggm#ŘqliD]OփVOط??A_$ò'E{o_tbò'~3sZU#NTgw̾.45[ɫ~P杯' I `z;]9V9ٿmɏ"fr,҅3~z`>U5X^en?t,?C%\xiH;RGGF%aM~?_stdИc/J +ٺd;}dp6o!ޯbH.t̒_2;Y?jG-vY>Y{I%f͕+4@g:/i\ˍʄ;Dgvo"- 껟=.u/o]}MP_'[飯3sk&k{I?Ǵņ?~O4-+cssBBסyrGFI`_0/AGɣK*aԴA;?F>gL3pio< p 6 l)fK'3T< [AMhXߟ ~['ͫ/C?`!Y,kkn ` P'x}QMJPf^LŢ"". Vֽ]P(y! \xw^ Gp~}3|3̄T `ě( bcC{r ?FIcIvuKFG'AwU HjfWPa^+ {pʩC˂7y&u>>G=M%~P}ROWz'2tG;n7ص^'1(UKUr flUp.;y.zt&( p)g־AG}@=1 s[. ,|75=8P' x l|}}}{}b"l nZҸF FRn5i+-~(۫pFR 0c-.dɺdf9]2l3UttnQ^iY^N{Ϲs=ܟ> % ߷f zJX(azӆ€ K: _8xmez`v N/6ҕ\:YR|mlC2$֮v(j {5cA՜9u)vǢ|Q/\]llۋ_مʭ2_4؂s%\h_!Lz!F~zH<80K|2^5757Ӄ_cG*PLѮnN?hlbupbZYLgU>MDozh̵,c~+|?lT?P˹< >AAwU[=%)Ao&A"~7k[d2c|ٿ .5G拡t1q1sq|:A'=#莠; z=%M$u>1 woW aAK3A]w*9h߭Ut:y=+O,[|=S-J.tQw3edyRrJ2ݪߢQ34.]]\ jccQO1|wsi]l{]Kߵ uzuOrq?Ct0sځz{K뾋u?kumuOi^DÒ<*cYn_ <'lFƳHD6 vƸHhQ1 U8Fǔif$@T@kZUa}+Rqq{=d߂"ǀ?#Q J݅ي#qy=ǽg*1A#>ȸƝl؆~6j c m#r96ީ.>%FlƕMjioc8X'8?{N{6 |Oi-V@~;ӦoV-ȟivML; L;>gڃL3δl2~vssBuO{}9o6>m%zo3g>;jm;ƾR 1>5br$^XyWAzt!nTΥ*Y+$/04;\zy4,G\z˰a~ɱe[i$'!|TpWry?˓TKi=yqǒ_Dc;);ϝyݍ%$jhlV0nй߂*T[e}Y& 9/%4lG}lG=wEw]b>םsvL;"{bXب7֡0;i޲ܻ9<=ᫍL3GvSN~ꏹ_ uܯc\W5}n2m|eo*h{QUOKlC'Q-M]'s#PFZuZJwfr:[w[\'di덗4*?,c3(0 #  Z Chart Excel.Chart.80*Microsoft Excel Chart:Equation Equation.30,Microsoft Equation 3.0? Chart Excel.Chart.80*Microsoft Excel Chartz Chart Excel.Chart.80*Microsoft Excel Chart/ 00DTimes New Roman(0(z[ 0 DArialNew Roman(0(z[ 0  DSymbolew Roman(0(z[ 0 0DWingdingsRoman(0(z[ 0  a .  @n?" dd@  @@`` `( + .^j ]MG %1C,,.a8E9;!R/S/2](^9A*gLh/3('&&(w 3_&8F&MWFG<<<=}./-h8QA::;;F:<<<qS "<o"$q9it2  b$}Uu‘D  "$\%Q6bm`ڳ=L> 2$,kkna$"$s[. ,|79 c $0e0e     A@ A5% 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E||s " 0e@        @ABC DEEFGHIJK5%LMNOPQRSTUWYZ[ \]^_ `abN E5%  N E5%  N F   5%    !"?N@ABC DEFFGHIJK5%LMNOPQRSTUWYZ[ \]^_ `ab ff@ ʚ;x(-ʚ;g4KdKd@z[ 0jpp" <4!d!dl 0P-<4ddddl 0P-<4BdBdl 0P-$ 80___PPT10 ``? *O  =o,9Framework for Profile-Analysis Data-Layout Optimizations  :8(( Shai Rubin CData Layout Optimization (What) (QData Layout Optimization (How)(A/Problems with Current Data-Layout Optimization00$Computationally hard to find the optimal layout [Petrank]. Computationally hard to approximate the optimal layout [Petrank]. Implication - heuristics are not robust: will not work for all programs. From our experience with heuristics: Field Reordering [Chilimbi PLDI 99]  no improvement (on perl). Custom Memory Allocator [Seidl ASPLOS 98] degrades performance (on espresso). !%!%t1< 1 Searching For a Data Layout( Z"Is Search Practical? OutlineBackground and Problem Definition Search is a solution, but may not practical Making the search practical Applications SummaryvPxxx"+32Making the Search Practical`%Trace Representation(M&Framework for Data-Layout Optimization'' XAvoid re-compilationProblem: data layout evaluation (edit+compilation+simulation). Solution:  pretend that the program was edited and compiled. ,x Z#DN&Framework for Data-Layout Optimization'' S'Memoization: Efficient Trace Simulation((  ZOutlineBackground and Problem Definition Search is a solution, but maybe not feasible Making the search practical: Trace representation Avoid recompilation Efficient simulation Applications SummaryQxx>xx".>  HFramework Application (1)Application: an implementation of the framework that searches in a sub-space of the layout space. Field Reordering: Objective: reduce number of cache misses. Sub-space: all possible (legal) orders of fields in (heap) objects. Our search strategy: (almost) exhaustive search. .uxxu%#Field Reordering: Exhaustive Search$$$We compared: Best field order found by our iterative search. Field orders produced by existing heuristics: Fields Temporal Affinity [ChilimbiPLDI 99] Fields Access Frequency [TruongPACT 98]. v x_xXxx 1f.U?Custom Memory Allocator (CMA)( @CMA Placement Function (PF)(}0 CMA Results $'Contributions and Future Work(fFormulate data layout optimization as a search process. Build a framework for efficient search process. Improve existing optimizations; enable new optimizations. Framework limitations: Difficult to handle very large traces (>0.5B references). Requires some guidance from the programmer (search strategy). Future work Advanced search strategies that combine several optimizations. Other non-data-layout optimization  prefetching. xzx xqxxxz o/0 )+BU ]$b)9;HILQWY]^ceP  ` ` ̙33` 333MMM` ff3333f` f` f` 3>?" dd@,|?" dd@   " @ ` n?" dd@   @@``PR    @ ` ` p>>K0 $(    6 h8  T Click to edit Master title style! !  0(   RClick to edit Master text styles Second level Third level Fourth level Fifth level!     S  0ė ``  X*  0 `   Z*  0 0P  Z*H  0޽h ? ̙33y___PPT10Y+D=' = @B + Default Design 0 P*(    0 s$   X*   0  0$  Z* d  c $ ?LD    0  K  RClick to edit Master text styles Second level Third level Fourth level Fifth level!     S  6h* s   X*   6H  0  Z* H  0j ? ̙3380___PPT10.q`-f (    0 <  s$    X*   0L   0$   Z*   6  s    X*   6   0   Z* H  0j ? ̙3380___PPT10.q@c^K0 p (  r  S <\o> o r  S ]oF   o   0X^o F   9 Ras Bodik   0Hao F dh  @Trishul Chilimbi  0 ,$@a 0 7B#- 8 TPo?"6@`NNN?N  ,$@c 0 7A#B 8 TD?"0@NNN?N!e ,$@ 0B 8 TD?"0@NNN?Nc ,$@ 06 8 T`o ?"6@`NNN?Nb|,$@ 0 @# 6 8 To ?"6@`NNN?N|a,$@% 0 @# 6 "8 To ?"6@`NNN?Nb,$@, 0 @# 6 #8 To ?"6@`NNN?Na,$@- 0 @# I &8 To?"6@`NNN?Nb| ,$@Z 0 SA.x# 0 '8 To ?"6@ NNN?N & m U,$  0 :time#0 (8 To ?"6@ NNN?N+ r ,$! 0 :time#8 )8 T|o ?"6@ NNN?NT,$ 0 B cache blocks  #6 +8 TXo ?"6@`NNN?N`,$@  0 @# B .8 ND?"0@NNN?N@,$@ 0B /8 ND?"0@NNN?N&A&,$@ 0B 08 ND?"0@NNN?NA,$@ 0B 18 ND?"0@NNN?NG,$@ 0- 28 To ?"6@ NNN?Na,$ 0 71# - 38 Tpo ?"6@ NNN?Nf,$ 0 72# - 48 To ?"6@ NNN?Nb,$ 0 73# - 58 To ?"6@ NNN?Nb,$# 0 74# 9 68 TLo ?"6@ NNN?Ne  % ,$" 0 C Memory Pages #B 78 ND?"0@NNN?N I ,$@( 0B 88 ND?"0@NNN?N H ,$@) 0- 98 T ?"6@ NNN?N &b ,$* 0 71# - :8 T` ?"6@ NNN?N ; ,$+ 0 72# 6 ;8 T  ?"6@`NNN?N`|,$@ 0 @# 6 =8 T ?"6@`NNN?N^,$@ 0 @# 6 ?8 T<  ?"6@`NNN?N|^,$@  0 @# B B8@ TD?"0@NNN?N e,$@; 0B C8 TD?"0@NNN?N  ,$@. 06 D8 T$ ?"6@`NNN?N 7Q ,$@7 0 @# 6 E8 Th ?"6@`NNN?Ns 7Q ,$@8 0 @# 6 F8 TX ?"6@`NNN?N Rl ,$@9 0 @# 6 G8 T ?"6@`NNN?Ns Sm ,$@: 0 @# 6 H8 Th# ?"6@`NNN?N m ,$@< 0 @# 6 I8 T& ?"6@`NNN?Ns n ,$@= 0 @# - L8 T)?"6@`NNN?N T ,$@p 0 7B#- M8 T/?"6@`NNN?N m ,$@r 0 7A#- O8 T0?"6@`NNN?N 5O ,$@g 0 7A#B P8 TD?"0@NNN?Nf ,$@> 0B Q8 TD?"0@NNN?N,$@? 06 R8 T\6 ?"6@`NNN?Nc!A,$@@ 0 @# 6 T8 T4 ?"6@`NNN?NcEe,$@M 0 @# 6 V8 T= ?"6@`NNN?Nci,$@V 0 @# 6 W8 TA ?"6@`NNN?Nib,$@W 0 @# 0 [8 TC ?"6@ NNN?N Bv,$H 0 :time#0 \8 TG ?"6@ NNN?N g ,$I 0 :time#8 ]8 TK ?"6@ NNN?NU_Y,$/ 0 B cache blocks  #6 ^8 TO ?"6@`NNN?N`Ee,$@1 0 @# 6 _8 TS ?"6@`NNN?N`i,$DX 0 @# - `8 TtV?"6@`NNN?N_G,$@q 0 7B# B b8 ND?"0@NNN?N,$@A 0B c8 ND?"0@NNN?N'',$@B 0B d8 ND?"0@NNN?N,$@C 0B e8 ND?"0@NNN?N,$@D 0- f8 T\[ ?"6@ NNN?Nb&,$E 0 71# - g8 T4_ ?"6@ NNN?N&g,$F 0 72# - h8 T c ?"6@ NNN?Nc&,$G 0 73# - i8 THg ?"6@ NNN?N&c,$K 0 74# 9 j8 T4k ?"6@ NNN?Nf 0& ,$J 0 C Memory Pages #B k8 ND?"0@NNN?N  ,$@O 0B l8 ND?"0@NNN?N  ,$@Q 0- m8 Tto ?"6@ NNN?N /c ,$S 0 71# - n8 TLs ?"6@ NNN?N '< ,$U 0 72# 6 o8 Tw ?"6@`NNN?N`!A,$@0 0 @# 6 p8 T{ ?"6@`NNN?NEe_,$@5 0 @# 6 q8 T@ ?"6@`NNN?Ni_,$@6 0 @# 6 s8 T| ?"6@`NNN?N!A_,$@4 0 @# z  z$  v8  u ,$@z 0f w8 6 $  x8 <T z  ?DL Optimizatione y8 T䉜 ?"6@ NNN?N  z,$ 0 oA.x B A.z#$ z ( a   8  (a ,$@  0B z8 TD?"0@NNN?N( ( B {8 TD?"0@NNN?N1 1 B |8 TD?"0@NNN?NA A B }8 TD?"0@NNN?Na a  zz ( a   8 R ,$@  0B 8 ND?"0@NNN?N( ( B 8 ND?"0@NNN?N1 1 B 8 ND?"0@NNN?NA A B 8 ND?"0@NNN?Na a  k 8 T ?"6@ NNN?N ,$ 0 uA.x B A.z #$ 8 N8?"6@`NNN?N  ,$@e 0 A.x B A.z `'#'# #$ i 8 Nԝ?"6@`NNN?N ,$Df 0 yA.x B A.z '$zz ( a   8   ,$@R 0B 8 ND?"0@NNN?N( ( B 8 ND?"0@NNN?N1 1 B 8 ND?"0@NNN?NA A B 8 ND?"0@NNN?Na a  d 8 NH ?"6@`NNN?N ix|,$2 0 tA.x B A.z #$^ 8 N ?"6@`NNN?Nb ,$3 0 nA.x B A.z#$zz ( a   8   ,$@T 0B 8 ND?"0@NNN?N( ( B 8 ND?"0@NNN?N1 1 B 8 ND?"0@NNN?NA A B 8 ND?"0@NNN?Na a  - 8 T ?"6@`NNN?N Qk ,$@v 0 7A#- 8 T천 ?"6@`NNN?N 6 ,$Dw 0 7B#- 8 T ?"6@`NNN?N i ,$@s 0 7B#m 8 BH?"6@`NNN?N : e,$@x 0 A.x B A.z ,'#$ x 8 NȾ?"6@`NNN?Nc ,$Dy 0 A.x B A.z ,'#$y 8 T Ĝ ?"6@ NNN?N^R,${ 0 MDL optimization: increase spatial locality of data to prevent memory faults. NN#B 8 TDɜ ?"6@ NNN?N'*v ,$$ 0 LOriginal data layout#B 8 T͜ ?"6@ NNN?N(,$P 0 LModified data layout#6 <8 TМ ?"6@`NNN?N^,$@  0 @# 6  8 T՜ ?"6@`NNN?Nc,$@& 0 @# 6 *8 Tp؜ ?"6@`NNN?Na,$@ 0 @# 6 !8 Tڜ ?"6@`NNN?Nb,$@' 0 @# I -8 Tޜ?"6@`NNN?NP`,$Dd 0 SA.z# - ,8 T?"6@`NNN?N`.,$@b 0 7B# 6 8 TL ?"6@`NNN?N  ,$@ 0 @# 6 8 T ?"6@`NNN?N  ,$@ 0 @# - 8 T?"6@`NNN?N  ,$@Y 0 7A#6 U8 T?"6@`NNN?NFfb,$@N 0 @# 6 S8 T?"6@`NNN?N!Ab,$@L 0 @# I Z8 T?"6@`NNN?Nb*,$@o 0 SA.x# I a8 T?"6@`NNN?Nb,$@n 0 SA.z# I 8 Th ?"6@`NNN?NbJ,$@t 0 SA.z# I 8 T` ?"6@`NNN?Nb_,$@u 0 SA.x# H 8 0޽h ??`8888888 8 8 ̙33X TIMING<|49.|6.3|17.6|42.9|8.2|43.1|5.___PPT10m.+D' = @B D' = @BA?%,( < +O%,( < +DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*8%(DV' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*8%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*)8%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*;8%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<**8%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*8%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*y8%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*8%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*+8%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*8%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*?8%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*<8%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*=8%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*8%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*8%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*8%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*8%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*8%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*8%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*8%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*8%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*8%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*8%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*.8%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*/8%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*08%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*18%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*28%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*38%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*48%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*'8%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*(8%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*68%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*58%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*8%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*8%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* 8%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*!8%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*78%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*88%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*98%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*:8%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*"8%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*#8%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*C8%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*]8%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*o8%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*^8%(D' =A@BBBB0B%())))?D' =1:Bvisible*o3>+B#style.visibility<*8%(D' =A@BBBB0B%())))?D' =1:Bvisible*o3>+B#style.visibility<*8%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*s8%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*p8%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*q8%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*D8%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*E8%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*F8%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*G8%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*B8%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*H8%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*I8%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*P8%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*Q8%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*R8%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*b8%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*c8%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*d8%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*e8%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*f8%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*g8%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*h8%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*[8%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*\8%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*j8%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*i8%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*S8%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*T8%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*U8%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*k8%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*8%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*l8%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*8%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*m8%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*8%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*n8%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*V8%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*W8%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*_8%(D4' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*8%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*&8%(D!' =4@BBBB%(D' =,54*3>Bfillcolor=@BPB<*8D' =1:B solid*a3>Bfill.type<*8D' =1:B true*]3>Bfill.on<*8D!' =4@BBBB%(D' =,54*3>Bfillcolor=@BPB<*8D' =1:B solid*a3>Bfill.type<*8D' =1:B true*]3>Bfill.on<*8D!' =4@BBBB%(D' =,54*3>Bfillcolor=@BPB<*8D' =1:B solid*a3>Bfill.type<*8D' =1:B true*]3>Bfill.on<*8D!' =4@BBBB%(D' =,54*3>Bfillcolor=@BPB<*#8D' =1:B solid*a3>Bfill.type<*#8D' =1:B true*]3>Bfill.on<*#8D!' =4@BBBB%(D' =,54*3>Bfillcolor=@BPB<**8D' =1:B solid*a3>Bfill.type<**8D' =1:B true*]3>Bfill.on<**8D!' =4@BBBB%(D' =,54*3>Bfillcolor=@BPB<*8D' =1:B solid*a3>Bfill.type<*8D' =1:B true*]3>Bfill.on<*8D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*8%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*,8%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*8%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*-8%(D' =%(D0' =%(Dh' =A@BB BB0B%()))D' =1:Bvisible*o3>+B#style.visibility<*8%(D' =-g6B fade*<3<*8Dh' =A@BB BB0B%()))D' =1:Bvisible*o3>+B#style.visibility<*8%(D' =-g6B fade*<3<*8D%' =%(D$' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*O8%(D!' =4@BBBB%(D' =,54*3>Bfillcolor=@BPB<*D8D' =1:B solid*a3>Bfill.type<*D8D' =1:B true*]3>Bfill.on<*D8D!' =4@BBBB%(D' =,54*3>Bfillcolor=@BPB<*F8D' =1:B solid*a3>Bfill.type<*F8D' =1:B true*]3>Bfill.on<*F8D!' =4@BBBB%(D' =,54*3>Bfillcolor=@BPB<*R8D' =1:B solid*a3>Bfill.type<*R8D' =1:B true*]3>Bfill.on<*R8D!' =4@BBBB%(D' =,54*3>Bfillcolor=@BPB<*H8D' =1:B solid*a3>Bfill.type<*H8D' =1:B true*]3>Bfill.on<*H8D!' =4@BBBB%(D' =,54*3>Bfillcolor=@BPB<*V8D' =1:B solid*a3>Bfill.type<*V8D' =1:B true*]3>Bfill.on<*V8D!' =4@BBBB%(D' =,54*3>Bfillcolor=@BPB<*^8D' =1:B solid*a3>Bfill.type<*^8D' =1:B true*]3>Bfill.on<*^8D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*a8%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*Z8%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*L8%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*`8%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*M8%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*8%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*8%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*8%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*8%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*8%(D' =%(DP' =%(Dx' =A@BB BB0B%())))?D' =1:Bvisible*o3>+B#style.visibility<*8%(D' =-g6B fade*<3<*8Dx' =A@BB BB0B%())))?D' =1:Bvisible*o3>+B#style.visibility<*8%(D' =-g6B fade*<3<*8D' =%(Du' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*v8%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*8%(+(+0+8 ++0+8 ++0+8 ++0+8 ++0+8 ++0+8 ++0+8 ++0+8 ++0+8 ++0+"8 ++0+#8 ++0+&8 ++0+'8 ++0+(8 ++0+)8 ++0++8 ++0+28 ++0+38 ++0+48 ++0+58 ++0+68 ++0+98 ++0+:8 ++0+;8 ++0+=8 ++0+?8 ++0+D8 ++0+E8 ++0+F8 ++0+G8 ++0+H8 ++0+I8 ++0+L8 ++0+M8 ++0+R8 ++0+T8 ++0+V8 ++0+W8 ++0+[8 ++0+\8 ++0+]8 ++0+^8 ++0+_8 ++0+`8 ++0+f8 ++0+g8 ++0+h8 ++0+i8 ++0+j8 ++0+m8 ++0+n8 ++0+o8 ++0+p8 ++0+q8 ++0+s8 ++0+y8 ++0+8 ++0+8 ++0+8 ++0+8 ++0+8 ++0+8 ++0+8 ++0+8 ++0+8 ++0+8 ++0+8 ++0+8 ++0+<8 ++0+ 8 ++0+*8 ++0+!8 ++0+-8 ++0+,8 ++0+8 ++0+8 ++0+8 ++0+U8 ++0+S8 ++0+Z8 ++0+a8 ++0+8 ++0+8 +\ K0   .l* (  l)" ,l N,G0*?"0`NNN?N ,$@  0 ? Data Layout #," )l N G0*?"0`NNN?NY,$@ 0 B Layout Space  #B !l TD?"0@NNN?N ,$@ 0~ l s * h8   8 l HT?"6@`NNN?N& F,$@ 0 NOptimal for simple loops#/ l N?"6@`NNN?N ( ,$@ 0 ? Heuristic  #1" l N<G0*?"0`NNN?NJ,$@ 0 GReference Summary#P" l T?"0`NNN?N,$@ 0 `Array Dep. Analysis (static)(# #I" l Tx?"0`NNN?N,$@ 0 YRef. Trace (dynamic)( # #a  l T$?"6@`NNN?Nm v,$@ 0 kScientific (array based) 6 # ##Y  l TX*?"6@`NNN?No v,$@ 0 cGeneral purpose (pointer based)( ##-  l Hx/?"6@`NNN?Ne & Fn,$D 0 C Compile Time #]  l T$3?"6@`NNN?Ng ( n,$@ 0 g1. Compile Time 2. Runtime# @`'  l H=?"6@`NNN?N m ,$@ 0 =Program#" l  `G*H 4SI?"0@NNN?N ,$@ 0 l H?"6@`NNN?N ,$@  0bz  &l ,$@  0 l N?"6@`NNN?N5 l ZB ?"6@ NNN?N DOptimal Layout#. l HF?"6@`NNN?N Fh ,$@ 0 DEnforce layout#5 l HJ?"6@`NNN?Na F,$@ 0 KData Layout Optimizer#nz Z;. (l j;>,$@  0 l N?"6@`NNN?NpM  l Z|O ?"6@ NNN?NxZ;. P Good Layout#B "l TD?"0@NNN?N  ,$@ 0B #l HI?"6@`NNN?N ch ,$@ 0 XProgram2 , #B $l TD?"0@NNN?N H` ,$D 0B +l TD?"0@NNN?N H ,$@ 0B -l TD?"0@NNN?N* * p ,$@  0B .l TD?"0@NNN?N : : ,$@ 0H l 0޽h ? lll ̙33;0 TIMING|36.4|63.2j;___PPT10J;+0dD7' = @B D6' = @BA?%,( < +O%,( < +D' =%(%(D ' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*l%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*l%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* l%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*!l%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*l%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*)l%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*+l%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*,l%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*-l%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*&l%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*l%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*(l%(D!' =4@BBBB%(D' =,54*3>Bfillcolor=@BPB<*lD' =1:B solid*a3>Bfill.type<*lD' =1:B true*]3>Bfill.on<*lD' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*l%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*.l%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*"l%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*#l%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*$l%(D ' =%(DX ' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* l%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* l%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*l%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*l%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*l%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*l%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* l%(D' =A@BBBB0B%())))?D' =1:Bvisible*o3>+B#style.visibility<* l%(D ' =%(DH ' =%(D6' =A@BB BB0B%(D' =-g6B fade*<3<* lD' =1:Bhidden*o3>+B#style.visibility<* l%(D6' =A@BB BB0B%(D' =-g6B fade*<3<*lD' =1:Bhidden*o3>+B#style.visibility<*l%(D6' =A@BB BB0B%(D' =-g6B fade*<3<*lD' =1:Bhidden*o3>+B#style.visibility<*l%(D6' =A@BB BB0B%(D' =-g6B fade*<3<* lD' =1:Bhidden*o3>+B#style.visibility<* l%(+(+0+,l ++0+)l ++0+l ++0+l ++0+l ++0+l ++0+l ++0+l ++0+l ++0+ l ++0+ l ++0+ l ++0+ l ++0+ l ++0+ l ++0+ l ++0+l ++0+l ++0+#l + K0 }uD`(  ~  s *h8   r B S ^   . 0x 5| <   D 0| L,$ 0 u?Our approach: replace heuristic with feedback-driven search. @@fH  0޽h ? ̙33& TIMING |49.2___PPT10+ΈDO' = @B D ' = @BA?%,( < +O%,( < +DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*D%(+8+0+D + * K0 \0(  8(  0." 0 N,à?"0`NNN?N O8 ,$@ 0 DData Layout Space ~ 0 s *Šh8   z  lS Y0 l S,$D 0 40 Tɠ? "0`NNN?N  ' <  80 Z̠ ? "6@ NNN?N lS MCurrent program data layoutD ;0 TË3? "6@`NNN?N ,t ,$@ 0 N Good LayoutsRz C 0  Z0 ;  ,$@  0T 3t 1 H0#  C % " I0 NPѠ?"6@`NNN?N=  < " J0 N ՠ?"6@`NNN?N t Z  <  " K0 Zנ??"6@`NNN?N3 1 < @ F0 T۠? "6@`NNN?NZ 0  vD Good +  easy to enforce layouts## R0 00 c}v m,$ 0 T a  good layout.B` T0 00 Y `,$  0 Search advantage: Robust, for each program finds a  good layout. *11z = ; 1  [0  ; = 1 ,$@ 0 >0 T@? "0`NNN?N= ; G-  <  ?0 Z ? "6@ NNN?NJ 1  EOptimal data layout U0 0 }v ,$  0 l8an  easy to enforce layout.B V0 0 F^Z,$ 0 i3Problem: Perform a search in the data layout space.4x4 \0 0 8bL,$ 0 ? Look for: x H 0 0޽h ? ̙336 TIMING|9.7|34.2|8.2}___PPT10]+s'D' = @B Dt' = @BA?%,( < +O%,( < +D' =%(%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*V0%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*0%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*Y0%(D' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*\0%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*;0%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*[0%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*R0%(D' =%(Du' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*Z0%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*U0%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*T0%(++0+0 ++0+;0 ++0+R0 ++0+T0 ++0+U0 ++0+V0 ++0+\0 +yC $ K0 Y!Q!'! (  B  TD?"0@NNN?N   ~  s *xh8   "  NG?"0`NNN?NU IPossible layouts c   `GHI?"0@NNN?N44"  ZG *?"0`NNN?N 2   A Data Layout  # "   ZdGV?"0`NNN?N HReference Trace c   H ?"6@`NNN?NK  MOptimizer (Heuristic)c  H %?"6@`NNN?N b  \Enforce layoutc @`  6-"` ,$@ 0 :Editc  62"` 99 ,$D 0 =Compilec  65"` ,$D  0 =Executec  64"` 9`,$D  0 >Evaluate c  N?"0@NNN?N 9 ,$D  0  N?"0@NNN?N 9 ,$D  0  N?"0@NNN?N 9 ,$D  0B  TD?"0@NNN?N. .B  TD?"0@NNN?N    6>"` v,$D 0 ? Continue? c2  6C"`,$@ 0 9Endc  N?"0@NNN?N ` ,$@ 0 @ N?"0@NNN?N,$@ 0B @ TD?"0@NNN?N r ,$D 0   TG ?"6@ NNN?N E Not clear:  c  %  p0e0e    BP CDEF A@  A5% 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E||P P P @s " 0e@        @ABC DEEFGHIJK5%LMNOPQRSTUWYZ[ \]^_ `abN E5%  N E5%  N F   5%    !"?N@ABC DEFFGHIJK5%LMNOPQRSTUWYZ[ \]^_ `abH  ,$D 0 ' N ?"6@`NNN?Nx Z ,$@ 0- & NL?"6@`NNN?N 0 ] ,$D 0 =Enforce#H  0޽h ?o   ̙33!& TIMING |13.1z!___PPT10Z!+Y0D~' = @B D9' = @BA?%,( < +O%,( < +Dp' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =A@BBBB0B%(D' =1:Bhidden*o3>+B#style.visibility<*%(D' =4@BBBB%(D' =1:Bhidden*o3>+B#style.visibility<*%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(Du' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*'%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*&%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =%( D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =%( D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =%(pD' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%%(++0+ ++0+ ++0+ ++0+ ++0+ ++0+ ++0+ ++0+& +  7K0 X6(  X~ X s *qh8   x X c $\r  H X 0޽h ? ̙33y___PPT10Y+D=' = @B + ;SK0 ZY0 IV X(  B F TD?"0@NNN?N||,$@' 0B = TD?"0@NNN?N  ,$@  0~  s *87   "  ZH8jIi?"0@NNN?N q    T܃?"6@`NNN?Nzq GReference Tracec  H?"6@`NNN?N  QData Layout Search Enginec  6"` ~ :Editc  6"` 9  =Compilec   6@"`  =Executec   6"` 9" >Evaluate c   N?"0@NNN?Nz~9z   N?"0@NNN?Nz z   N?"0@NNN?Nz9zB  TD?"0@NNN?NR R  6P"` g   Continue?2  s *䟢"`JnH 3End  N?"0@NNN?Nz"z  N?"0@NNN?N J  TH?"6@`NNN?N&Bk ,$@1 0 Compress(T)CST> cc2   fZG/H{GI&?"0@NNN?N {k ,$@- 0B  TD?"0@NNN?N   H\?"6@`NNN?NV ,$@ 0 HData Object Analysis DOA(CST,LS)NLSL%# c  H?"6@`NNN?N ,$@ 0 FLayout Selector LS(NLS,B,CST,SS)DLL$#c  T?"0`NNN?NJ  ,$@ 0 8Enforce Layout AL(DL,CST)NTNc cc  T?"6@`NNN?NT ,$@! 0 .Evaluate Simulate(NT)BN c cc   N?"0@NNN?Nw y,$@# 0 F   " EG # HĢ?"6@`NNN?N  3 " $ H ?"6@`NNN?N " % N ?"6@`NNN?N -E " & H ?"6@`NNN?N A qn " ' Hpɢ?"0`NNN?N p -  < " ( H$΢?"0`NNN?N # ]  < " ) HTѢ?"0`NNN?N v  < " * TԢ?"0`NNN?N 2   < " + Hآ?"0`NNN?N b  < " , H\ۢ?"0`NNN?N   ;  < <" - Tܢ ?"6@`NNN?N J z .  r@ good  and enforceable layouts!!z   . ,\,$D 0 /" BA   ) 0  fx ?"6@`NNN?N}   MClass Splitting"g # 1  f ?"6@`NNN?N   G Linearizationc + 2  f ?"6@`NNN?N C 3 OField Reordering"g " 3 H?"6@`NNN?Nw~,$@  0 4 N?"0@NNN?Ny 9z,$@ 08 5 T ?"6@ NNN?N k,$ 0 B Layout Space cN 7 T ?"6@ NNN?N ,$  0 XNarrowed Space.cB 8 TD?"0@NNN?Nz z ,$@ 0< 9 T ?"6@ NNN?N` h ,$ 0 FSearch Strategyc3 ; T ?"6@ NNN?N,$ 0 =Tracec8 < T ?"6@ NNN?NQ w ,$ 0 B Data Layout cB >@ TD?"0@NNN?N  ,$D  0B ? TD?"0@NNN?N xxB ,$@ 0H @ TH ?"6@ NNN?NV ,$( 0 R New Trace, cM A TH?"6@`NNN?N h,$D* 0 W Continue(B)   7 B T ?"6@ NNN?N`G,$+ 0 ABenefit1 D T ?"6@ NNN?N,$) 0 ;Benefit G N?"0@NNN?Nv{&,$D. 0 H@  fZGbHiIb?"0@NNN?Nk {y,$@0 0E I T ?"6@ NNN?N W? ,$/ 0 OCompressed Symbolic Tracec1 ! H?"6@`NNN?N$ ,$@ 0 GSearch Strategyc J  h0e0e    BCDE F A@  A5% 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E||@s " 0e@        @ABC DEEFGHIJK5%LMNOPQRSTUWYZ[ \]^_ `abN E5%  N E5%  N F   5%    !"?N@ABC DEFFGHIJK5%LMNOPQRSTUWYZ[ \]^_ `ab   ,$@  05 K H0 ?"6@`NNN?N< ,$@ 0 KT.c5 L H$?"6@`NNN?NE  ,$@ 0 KT.c N@  fZGH$I?"0@NNN?Nvy,$@ 03 O T) ?"6@ NNN?NPE,$ 0 =Tracec R  p0e0e    B C DEF A@  A5% 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E||  @s " 0e@        @ABC DEEFGHIJK5%LMNOPQRSTUWYZ[ \]^_ `abN E5%  N E5%  N F   5%    !"?N@ABC DEFFGHIJK5%LMNOPQRSTUWYZ[ \]^_ `ab   S T 8c?"6@`NNN?N( ,$D: 0 T T 8c?"6@`NNN?N  ,$D9 0 U T 8c?"6@`NNN?N ,$D8 0 V 00/ "`b12,$D7 0 V&Framework for Data Layout Optimization'' 5 M H1?"6@`NNN?N#,$@ 0 KT.cH  0޽h ?          4GHN ̙33=nh TIMINGL|23.5|22.3|20.|19.2|13.1|13.6|21.1|7.1m___PPT10m+-Df' = @B D|f' = @BA?%,( < +O%,( < +D4' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*.%(D' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(DB' =A@BB*BB0B%()?)?)Dy' =.A7 BBBBBSM -0.00209 3.7037E-7 L -0.00209 0.25764 *3>*B ppt_xB ppt_y=@0BBAApBBB><*D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*K%(D' =4@BBBB%())))?D' =1:Bhidden*o3>+B#style.visibility<*%(D ' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*5%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*O%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*J%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*7%(D' =4@BBBB%())))?D' =1:Bvisible*o3>+B#style.visibility<*=%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*>%(D' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*3%(D' =4@BB#BB%()@D)' =+4 8?^CBhiddenBCBvisibleB*o3>+B#style.visibility<*3D ' =%(Dp ' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*!%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*L%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*8%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*9%(D' =A@BBBB0B%(D' =1:Bhidden*o3>+B#style.visibility<*%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*<%(D0' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*4%(D' =4@BBBB%(D' =1:Bhidden*o3>+B#style.visibility<*=%(D' =A@BBBB0B%(D' =1:Bhidden*o3>+B#style.visibility<*%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*N%(D' =4@BBBB%(D' =1:Bhidden*o3>+B#style.visibility<* %(D' =A@BBBB0B%(D' =1:Bhidden*o3>+B#style.visibility<*%(D' =4@BBBB%())))?D' =1:Bvisible*o3>+B#style.visibility<*?%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*M%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*;%(D' =A@BBBB0B%(D' =1:Bhidden*o3>+B#style.visibility<* %(D' =%(DA' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =A@BBBB0B%(D' =1:Bhidden*o3>+B#style.visibility<* %(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =4@BBBB%(D' =1:Bhidden*o3>+B#style.visibility<*4%(D' =4@BBBB%())))?D' =1:Bhidden*o3>+B#style.visibility<*R%(D' =4@BBBB%(D' =1:Bhidden*o3>+B#style.visibility<*%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*F%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*@%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*D%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*A%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*B%(D;' =%(D' =%(D' =4@BBBB%(D' =1:Bhidden*o3>+B#style.visibility<*%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*G%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*I%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*H%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =4@BBBB%(D' =1:Bhidden*o3>+B#style.visibility<*N%(D' =A@BBBB0B%(D' =1:Bhidden*o3>+B#style.visibility<*O%(D6' =A@BB BB0B%(D' =-g6B fade*<3<*MD' =1:Bhidden*o3>+B#style.visibility<*M%(D6' =A@BB BB0B%(D' =-g6B fade*<3<*LD' =1:Bhidden*o3>+B#style.visibility<*L%(D6' =A@BB BB0B%(D' =-g6B fade*<3<*KD' =1:Bhidden*o3>+B#style.visibility<*K%(D' =%(D' =%(D8' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*V%(D' =-g6B fade*<3<*VD' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*U%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*T%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*S%(++0+ ++0+ ++0+ ++0+ ++0+  ++0+  ++0+ ++0+ ++0+ ++0+ ++0+ ++0+5 ++0+7 ++0+9 ++0+; ++0+< ++0+@ ++0+A ++0+B ++0+D ++0+I ++0+! ++0+K ++0+K ++0+L ++0+L ++0+O ++0+O ++0+V ++0+M ++0+M +I )RK0  | pK (  ~  s *h8    > H ?"6@`NNN?N=O  Problem: reference trace cannot be easily manipulated since it is too large (>10GB, >100M references). Solution: compressed trace (using modified SEQUITUR). Example: 0cc} I Z ?"6@ NNN?Ns ,$ 0  Trace: acbcbcbcbdbdbdbde*-ff J H ?"6@`NNN?N ,$ 0 x Representation advantage: Compact; fits into main memory [ChilimbiPLDI 01]. Expose repetitions (we use this later). It produces a symbolic trace (i.e., a terminal is a data object). @-ccR K T ?"6@ NNN?N B ,$ 0 \SEQUITUR Representation SacBBBAAe Bbc ACC CbdVS%f'f9f'f>  H  0޽h ? ̙33U0 TIMING|19.1|34.1___PPT10+lD1' = @B D' = @BA?%,( < +O%,( < +D' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*I%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*K%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*J%(++0+I ++0+J ++0+K +? W 2K0 >>@ ;E1=(  B  TD?"0@NNN?N||~  s *0Ƥ7      TxǤ?"6@`NNN?Nzq GReference Tracec  HH̤?"6@`NNN?N  QData Layout Search Enginec   6 Ф"` O  =Compilec   N?"0@NNN?Nzz  N?"0@NNN?Nz9zB  TD?"0@NNN?NR R  6֤"` g   Continue?2  s *ؤ"`n 3End  N?"0@NNN?Nz"z  N?"0@NNN?N T  Tܤ?"6@`NNN?N&Bk  Compress(T)CST> cc2   fZG/H{GI&?"0@NNN?N {k f  H@?"6@`NNN?NV  HData Object Analysis DOA(CST,LS)NLSL%# cd  H?"6@`NNN?N  FLayout Selector LS(NLS,B,CST,SS)DLL$#cb  TP?"0`NNN?NJ   <Enforce Layout EL(DL,CST)CST Nc cc|  T?"6@`NNN?NT  .Evaluate Simulate(NT)BN c cc   N?"0@NNN?Nw y F    EG  H?"6@`NNN?N  3 "  H ?"6@`NNN?N "   N ?"6@`NNN?N -E " ! H ?"6@`NNN?N A qn " " H?"0`NNN?N p -  < " # H ?"0`NNN?N # ]  < " $ H?"0`NNN?N v  < " % T ?"0`NNN?N 2   < " & Ht?"0`NNN?N b  < " ' HP?"0`NNN?N   ;  < <" ( T ?"6@`NNN?N J z .  r@ good  and enforceable layouts!!oF   ) ,\ *" BA   ) +  f ?"6@`NNN?N}   MClass Splitting"g # ,  f  ?"6@`NNN?N   G Linearizationc + -  f" ?"6@`NNN?N C 3 OField Reordering"g " . H?"6@`NNN?Nw~ 0 T& ?"6@ NNN?N k B Layout Space c 1 T+ ?"6@ NNN?N  XNarrowed Space.cB 2 TD?"0@NNN?Nz z  3 T/ ?"6@ NNN?N `,  FSearch Strategyc 4 T4 ?"6@ NNN?N =Tracec 5 T6 ?"6@ NNN?NA g  B Data Layout cB 6@ TD?"0@NNN?N  B 7 TD?"0@NNN?N xxB  9 T;?"6@`NNN?N h W Continue(B)    : T`@ ?"6@ NNN?N`G ABenefit ; TD ?"6@ NNN?N ABenefit < N?"0@NNN?Nv{& =@  fZGbH\"Ib?"0@NNN?Nk {y > T C ?"6@ NNN?N W/  OCompressed Symbolic Tracec ? HxI?"6@`NNN?N$  GSearch Strategyc @  n0e0e    BCDE F @  5% 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E||@s " 0e@        @ABC DEFGHIJK5%LMNOPQRSTUWYZ[ \]^_ `abN 5%  N 5%  N    5%    !"?N@ABC DEFGHIJK5%LMNOPQRSTUWYZ[ \]^_ `ab    A TP ?"6@ NNN?N2 r  @"6 B T 8c?"6@`NNN?N(  C T 8c?"6@`NNN?N j  D T 8c?"6@`NNN?N  E T8T ?"6@ NNN?NV  R New Trace, cH  0޽h ?    < = ̙33y___PPT10Y+D=' = @B +L c`$K0 o(  ~  s *^h8   x  c $_  "  0_G0*"`z ., ,$D  0 `A.x, B, A.z, Bc f2  N d?"0`NNN?N(ZW  $A.x10 A.z14 B20pccc9"  ZkG$?"0`NNN?NG  ?S ,$@ 0 C 30,20,34,20  c@  Tp ?"6@ NNN?N` 1G ,$ 0 JNew concrete tracecC  Ts ?"6@ NNN?N-,$ 0 MSingle symbolic tracec   T,x?"6@`NNN?Np N  =Compile#   T{?"6@`NNN?Np@  DRun (simulate)#   N?"0@NNN?N@Z)B   N?"0@NNN?ND E   N?"0@NNN?NDN@D  T?"6@`NNN?Nq   C Edit program#:  T?"6@`NNN?N, r ,$@ 0 DEnforce Layout# @ N?"0@NNN?NW , ,$@ 0  N?"0@NNN?Nr z ,$@ 0  N?"0@NNN?N  ,$@  0   `G,HI,?"0@NNN?N ? ,$@  0J  0 &G,$ 0 nSymbolic trace + data layout concrete address trace. ,8x2  N?"0`NNN?N0{` ,$D 0 $A.x30 A.z34 B20pccc9"  ZG$?"0`NNN?NH  >T ,$@ 0 C 30,20,34,20  c\  T ?"6@ NNN?N@M,$ 0 f. Simple, but crucial for an efficient search.//#r  ZtG?"0`NNN?N\ (  XUser (Optimizer),# #  N?"0@NNN?NB E4  T\?"6@`NNN?NqA ,$@ 0 >Simulate  #H  0޽h ?         ̙33q0J TIMING.|22.3|22.2|11.7|6.7|10.0___PPT10/+^۽D-' = @B D,' = @BA?%,( < +O%,( < +DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =%(D}' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =%(D' =%(D6' =A@BB BB0B%(D' =-g6B fade*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D)' =4@BB BB%(D' =-g6B fade*<3<* D' =1:Bhidden*o3>+B#style.visibility<* %(D)' =4@BB BB%(D' =-g6B fade*<3<* D' =1:Bhidden*o3>+B#style.visibility<* %(D6' =A@BB BB0B%(D' =-g6B fade*<3<* D' =1:Bhidden*o3>+B#style.visibility<* %(Df' =A@BB BB0B%()))D' =-g6B fade*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(Dh' =A@BB BB0B%()))D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-g6B fade*<3<*DY' =4@BB BB%()))D' =-g6B fade*<3<*D' =1:Bhidden*o3>+B#style.visibility<*%(D)' =4@BB BB%(D' =-g6B fade*<3<* D' =1:Bhidden*o3>+B#style.visibility<* %(D' =%(D0' =%(Dh' =A@BB BB0B%()))D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-g6B fade*<3<*Dh' =A@BB BB0B%()))D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-g6B fade*<3<*DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(++0+ ++0+ ++0+ ++0+ ++0+  ++0+ ++0+ ++0+ ++0+ ++0+ ++0+ ++0+ ++0+ +F? Y0(K0 U>M> :;<(  B  TD?"0@NNN?N||~  s *hߨ7   "  ZH8jIi?"0@NNN?N q    T|?"6@`NNN?Nzq GReference Tracec  HL?"6@`NNN?N  QData Layout Search Enginec  6$"` 9  =Compilec  N?"0@NNN?Nz~9z   N?"0@NNN?Nz9zB   TD?"0@NNN?NR R   6"` g   Continue?2   s * "`f 3End   N?"0@NNN?Nz"z @ N?"0@NNN?N T  T?"6@`NNN?N&Bk  Compress(T)CST> cc2   fZG/H{GI&?"0@NNN?N {k f  H?"6@`NNN?NV  HData Object Analysis DOA(CST,LS)NLSL%# c  d  H?"6@`NNN?N  FLayout Selector LS(NLS,B,CST,SS)DLL$#c  b  T ?"0`NNN?NJ   <Enforce Layout EL(DL,CST)CST Nc c  c   T?"6@`NNN?NT  4Evaluate Simulate(CST )BN ccc   N?"0@NNN?Nw y F    EG  HH?"6@`NNN?N  3 "  H ?"6@`NNN?N "  N ?"6@`NNN?N -E "  H ?"6@`NNN?N A qn "  H?"0`NNN?N p -  < "  H?"0`NNN?N # ]  < "  H"?"0`NNN?N v  < "  T &?"0`NNN?N 2   < "  H)?"0`NNN?N b  < "   H,?"0`NNN?N   ;  < <" ! T/ ?"6@`NNN?N J z .  r@ good  and enforceable layouts!!oF   " ,\ #" BA   ) $  f4 ?"6@`NNN?N}   MClass Splitting"g # %  f0 ?"6@`NNN?N   G Linearizationc + &  f\< ?"6@`NNN?N C 3 OField Reordering"g " ' H?"6@`NNN?Nw~ ( T? ?"6@ NNN?N s B Layout Space c ) T`C ?"6@ NNN?N  XNarrowed Space.cB * TD?"0@NNN?Nz z  + TH ?"6@ NNN?N h  FSearch Strategyc , T M ?"6@ NNN?N =Tracec - TQ ?"6@ NNN?NY _  B Data Layout cB .@ TD?"0@NNN?N  B / TD?"0@NNN?N xxB  1 TU?"6@`NNN?N h W Continue(B)    2 TdY ?"6@ NNN?N`G ABenefit 3 T] ?"6@ NNN?N ABenefit 4 N?"0@NNN?Nv{& 5@  fZGbH6 Ib?"0@NNN?Nk {y 6 T\ ?"6@ NNN?N o/  OCompressed Symbolic Tracec 7 He?"6@`NNN?N$  GSearch Strategyc 8  n0e0e    BCDE F @  5% 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E||@s " 0e@        @ABC DEFGHIJK5%LMNOPQRSTUWYZ[ \]^_ `abN 5%  N 5%  N    5%    !"?N@ABC DEFGHIJK5%LMNOPQRSTUWYZ[ \]^_ `ab    9 Ti ?"6@ NNN?N2 r  @"6 : Tm ?"6@ NNN?N{ 4  @"6 ; Txl ?"6@ NNN?NV  R New Trace, cH  0޽h ?      4 5 ̙33y___PPT10Y+D=' = @B +! ]4K0 B:@ R(  ~  s *zh8   K  T{ ?"6@ NNN?N| Evaluation using simulation: MissRateT=Simulate(T); Problem: simulation of the whole trace (T) is too expensive. Solution: avoids re-simulation of repeated sub-traces. z#'f/f 'f'fv#,  y @`X  T| ?"6@ NNN?N  ,$ 0 bSEQUITUR Representation SBBBAA Bbc ACC CbdfW###$#,1f  T ?"6@ NNN?NE 7k ,$ 0 pCSC=Simulate2 (C) CSB=Simulate2 (B) CSA = CSCCSC CSS = CSBCSBCSBCSACSAJx#+#+#+#+#+#+#+#+#+,  *s  T ?"6@ NNN?N Q B,$ 0 }T: bcbcbcbdbdbdbd.cc < T̸ ?"6@ NNN?N $ 0bZ___PPT9<4 Memoization: Simulate each  low level rule, compute its memoization value. For cache simulation: memoization value = CacheState [CS]. Recursively compose memoization values for  higher rules.  ?<"< c?c<#< # Z .     @` O Zܽ ?"6@ NNN?N&I,$ 0  MissRateT = V x+  P0 TA :? ?h 9H :$D 0 H  0޽h ? ̙33MB TIMING&|19.3|33.2|6.3|55.4___PPT10+D ' = @B Db ' = @BA?%,( < +O%,( < +D2' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*<%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =%(Du' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*O%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*P%(++0+ ++0+ ++0+ ++0+< ++0+O + eZK0 06(  ~  s *8h8   x  c $  @   H  0޽h ? ̙33y___PPT10Y+D=' = @B + QK0  `6(  `~ ` s *h8   x ` c $  H ` 0޽h ? ̙33y___PPT10Y+D=' = @B +Q  K0 ` X @+ (  ~  s * h8   x  c $ =    )0  60e0eA Z    ? A@  A5% 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E||s " 0e@        @ABC DEEFGHIJK5%LMNOPQRSTUWYZ[ \]^_ `abN E5%  N E5%  N F   5%    !"?N@ABC DEFFGHIJK5%LMNOPQRSTUWYZ[ \]^_ `ab c Z  + T ?"6@ NNN?N_ F  TRuntime improvement: 0%-4.5%. #H  0޽h ? ̙33y___PPT10Y+D=' = @B +8{ H1K0 11` -7!1(  ~  s *h8   B  ND?"0@NNN?ND 0 D ,$@  0B  TD?"0@NNN?N ,$@ 0B  ND?"0@NNN?N: x : ,$@ 0B  ND?"0@NNN?Nx ,$@ 07  Zh?"6@ NNN?N k ,$@ 0 ;Ac7   Z@?"6@ NNN?No D ,$@ 0 ;Bc7   Z#?"6@ NNN?ND k ,$@ 0 ;Ac4   TT' ?"6@ NNN?Nv ,$ 0 >Page 1c4   T@+ ?"6@ NNN?NDv ,$ 0 >Page 2c7   Z.?"6@ NNN?No ,$@ 0 ;Bc7  Z*?"6@ NNN?N @ k ,$@  0 ;AcB  TD?"0@NNN?N a a u ,$@  0B  TD?"0@NNN?N 0 0 u ,$@ 0B  TD?"0@NNN?ND D ,$@  0B  TD?"0@NNN?ND D ,$@  00  T<7 ?"6@ NNN?N3 c  ,$  0 :time#3  T; ?"6@ NNN?N ,$ 0 =address#B  ND?"0@NNN?ND tD ,$@ 0B  TD?"0@NNN?N ,$@ 0B  ND?"0@NNN?N: : ,$@ 0B  ND?"0@NNN?N,$@ 07  Z@?"6@ NNN?N\k ,$@! 0 ;Ac7  ZD?"6@ NNN?N}k ,$@" 0 ;Bc7  ZH?"6@ NNN?N}k ,$@# 0 ;Ac4   TL ?"6@ NNN?N ,$ 0 >Page 1c4 ! TP ?"6@ NNN?N<,$ 0 >Page 2c7 " Z`T?"6@ NNN?N k ,$@$ 0 ;Bc7 # ZlO?"6@ NNN?N,k ,$@% 0 ;AcB $ TD?"0@NNN?N u ,$@ 0B & TD?"0@NNN?N ttu ,$@ 0B ) TD?"0@NNN?ND "OD ,$@ 0B * TD?"0@NNN?ND D ,$@ 00 , T\ ?"6@ NNN?N;  ,$ 0 :time#3 - T` ?"6@ NNN?N,$ 0 =address#" . T d ?"6@ NNN?N@` `* Objective: reduce number of page faults. ++!S / T,i ?"6@ NNN?N? [ j,$ 0 ] Allocator 1  # S 0 Tm ?"6@ NNN?N &h,$ 0 ] Allocator 2  # 9 1 T@q ?"6@ NNN?N6 0 ,$& 0 C Poor locality#9 2 T+B#style.visibility<*/%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*0%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*!%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*$%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*&%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*)%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<**%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*,%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*-%(D' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<* %(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*"%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*#%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*1%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*2%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*4%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*5%(DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*3%(++0+ ++0+  ++0+  ++0+  ++0+  ++0+  ++0+ ++0+ ++0+ ++0+ ++0+ ++0+ ++0+  ++0+! ++0+" ++0+# ++0+, ++0+- ++0+/ ++0+0 ++0+1 ++0+2 ++0+3 +=; I@K0 SK P (  ~  s *ؼh8     HDڼ ?"6@ NNN?N k cmalloc(size s){ }n#     N<߼?"6@`NNN?N XPF: Map objects to heaps PF(heap object)intF-###,   H ?"6@ NNN?Nh ,$ 0 2 How we can find a placement function using our framework? A placement function defines a data layout. Learn by measuring the benefits of its data layout. How: use a learning algorithm. X;xx;!!c#3 0 T?"6@`NNN?N P F ,$@ 0 =Learner# 1 N4?"6@`NNN?N 9! ,$D  0 $PF(Attributes)int8## 2 H?"6@`NNN?N@  ,$@ 0 3 H?"6@`NNN?NI  ,$@  0B 4 N?"6@`NNN?NO) ,$@ 0 RUse Framework to Evaluate PF#l   K ?,$@ 0 2 7 Z?"6@`NNN?N5 50  :Size# 9 <D"`" 71a ; <"`" 92c < N  ?"6@ NNN?N   ?size<24(2#( = N ?"6@ NNN?N   dsize24:(2## >B T?"0@NNN?Nb0 5" ? T?"0@NNN?N50 =" L NZ?"6@`NNN?N e ,$@ 0 M N?"6@`NNN?N  ,$@ 0B N T?"6@`NNN?No  O ,$@  0 LDecision Tree Learner# P N@?"6@`NNN?Nr zH ,$@ 0 Profiling Information Profile(Heap objects) runtime attributesFA### H  0޽h ?/@79>7;? ̙33z": TIMING|28.5|24.8|35.50"___PPT10"+ACD' = @B D' = @BA?%,( < +O%,( < +DA' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D<' =%(D ' =%(D' =A@BBBB0B%())))?D' =1:Bvisible*o3>+B#style.visibility<*4%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*M%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*L%(D' =A@BBBB0B%())))?D' =1:Bvisible*o3>+B#style.visibility<*P%(D' =A@BBBB0B%())))?D' =1:Bvisible*o3>+B#style.visibility<*0%(D' =4@BBBB%())))?D' =1:Bvisible*o3>+B#style.visibility<*2%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*3%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*1%(Da' =%(D ' =%(D6' =A@BB BB0B%(D' =-g6B fade*<3<*0D' =1:Bhidden*o3>+B#style.visibility<*0%(D6' =A@BB BB0B%(D' =-g6B fade*<3<*1D' =1:Bhidden*o3>+B#style.visibility<*1%(D' =A@BBBB0B%())))?D' =1:Bvisible*o3>+B#style.visibility<*N%(D+' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*K%(D'  =-g6B fade*<3<*KD' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*N%(D' =4@BBBB%())))?D' =1:Bvisible*o3>+B#style.visibility<*L%(D' =4@BBBB%())))?D' =1:Bvisible*o3>+B#style.visibility<*M%(++0+ ++0+0 ++0+0 ++0+1 ++0+1 ++0+4 ++0+N ++0+N ++0+P +' 9K0 p(  p~ p s *<h8    8  p #"."8   ep NDF ?"6@ NNN?Nb] [Number of heapsB @` fp N(? ?"6@ NNN?Nb] SProgramB @` gp TX ?"6@ NNN?Nb= 4  N10B @`9 hp Tb ?"6@ NNN?N= b4  o Ghostscript  B  @` ip Tk ?"6@ NNN?Nb]U M2B @` jp Tdm ?"6@ NNN?N]bU REspresso  B @` kp T} ?"6@ NNN?NbUM  M8B @` lp T ?"6@ NNN?NUbM  PBoxsimB @` mp T ?"6@ NNN?NbE =  M5B @` np T ?"6@ NNN?NE b=  NPerlB @` op T ?"6@ NNN?Nb4 8  M6B @` pp Tp ?"6@ NNN?N4 b8  RLp_solve  B @` qp T ?"6@ NNN?NbM E  M5B @` rp Tp ?"6@ NNN?NM bE  OTwolfB @`B sp To ?"0@NNN?NB tp N1 ?"0@NNN?NE E B up To ?"0@NNN?N8 8 B vp To ?"0@NNN?N8 B wp N1 ?"0@NNN?Nbb8 B xp To ?"0@NNN?N8 B yp N1 ?"0@NNN?N= = B zp N1 ?"0@NNN?NM M B {p N1 ?"0@NNN?NUUB |p N1 ?"0@NNN?N4 4 B }p N1 ?"0@NNN?N]] p  `A ?? ?"6@ NNN?NN F 8 ?$ 0 p  `A z? ?"6@ NNN?N P 8 z$ 0c p Tp ?"6@ NNN?N =0,$ 0 m'1Relative to original working set size.*(+ '# H p 0޽h ? ̙33 & TIMING |23.8\ ___PPT10< +DX' = @B D' = @BA?%,( < +O%,( < +DJ' =%(D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*p%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*p%(D' =A@BBBB0B%())))?D' =1:Bvisible*o3>+B#style.visibility<*p%(D' =A@BBBB0B%(D' =1:Bhidden*o3>+B#style.visibility<*p%(++(+p 0+ɾ+(+p 0+ʾ+(+p 0+ʾ+0+p + K0 `6(  ~  s *ثh8   x  c $%  H  0޽h ? ̙33y___PPT10Y+D=' = @B +R  0   4 (  4d 4c $LD    4s * K~  f^___PPT9@8 Here is the DL space (all legal data layout for the program) Here is the current program data layout. Our first interest: layouts that improves the program memory performance. Clearly, the optimal layout is part of the  good sub-space. But, does it enough? Let us look at the properties of the optimal layout. It is optimal only from one aspect  the memory behavior. But DL optimization has other aspects. For example, we need to enforce the layout. The optimal layout may be very hard to enforce. why? since it might assign different field orders to different instances of the same Java class. Even if we can ensure such a case, what would be the overhead to impose it? So, we are interested in layouts that has another property: We want a layout that is  easy to enforce, and I will discuss how to define these later. Transition: OK, we have a search space, but how can we do a search in this space? 7" " " <" [" " R" " 7  < [ T   H 4 0j ? ̙33#  0 P\s(  \^ \ S LD    \ c $  K   iUSo, in the rest of the talk, I will focus on techniques to make the search feasible. H \ 0j ? ̙33 0 tl(  d c $LD   ` s *) Kl  TL___PPT9.& What we can learn from the graph An example that heuristics are not robust (Perl based on pair-wise temporal affinity) Iteration always outperforms heuristics. Transition Now let us look on a little bit more challenging optimization. P!" " M!MLH  0j ? ̙33! 0 q(  d c $LD    s *P K   [GPurpose of this slide What we did Summary of contribution Future work?H  0j ? ̙33 0 G?(  d  c $LD   3  s *  K  zr___PPT9TL ?[The difficulties: The optimal data layout is hard to compute. The optimal data layout is even hard to approximate. The result of the theoretical and the practical difficulties: DL heuristics are not robust: For example. 4. What is the conclusion? Transition: So let us see how we can define the search problem for data layout optimization Z" Z+" ZZZaZZ  +     a  H  0j ? ̙33  0   0pL (  pd p c $LD     p s *  K|  d\___PPT9>6  There are several DL optimizations that were proposed in the past. All optimization use the following process. The optimization has a  layout optimizer that is task is to compute a new data layout for the program data objects. The calculator takes two inputs. The program memory trace, it is needed to expose the locality patterns of the program. A description of possible layouts that the optimization considers. The output of the optimizer is a new data layout. Ideally, we might want to calculate the optimal layout. Well, we learned that this computationally difficult. So, most optimization compromise and calculate only  good layout. A layout that suppose to improve the program performance. But the process does not end here after we found the layout we need to enforce it, this is done by program transformation There are two instances to the process. Scientific programs  static data, simple control flow based on nested loops; hence the memory access pattern is predictable. General purpose programs  dynamic data, complicated control flow, memory access pattern hard to predict. Transition: We are going to focus on general purpose programs, and let us see what are the difficulties in this data layout optimization process. o" " ?" X" (" " " o?X(      H p 0j ? ̙33" 0 (  d  c $LD   z  s *hu K   So, we want to do a search. Usually a search is based on some  exhaustiveness principle. You consider a lot of possibilities selecting the more  promising ones. In order to do so, we need to evaluate a lots of layouts But how do we evaluate a layout? This is a time consuming task: Transition: So maybe we have a solution but it is not feasible. bbH  0j ? ̙33K% 0  (  d  c $LD     s *]  KT  <4___PPT9 ASymbolic trace SEQUITUR I will review how SEQUITUR represent the trace, since later we exploit this representation. 4. Representation advantages. Transition: The main point to remember for now: Traversal of the trace is linear (in the number of references). From this figure we can see how SEQUITUR actually compress the trace. It represent repeated sub-traces (sub-strings) as sub-dags that are traversed several times. And we are going to use this repetitions later.8t" O" " H  0j ? ̙330 0  t4(  td t c $LD    t s *$ K    H t 0j ? ̙332 0 TL@ (  d  c $LD   @  s *  K|  d\___PPT9>6 bb So, how do we make the search feasible. The first step, we define narrow the search space. How we do that? First, please remember that we are interested in  easy to enforce layout. So, we focus only on layouts that we know that they are easy to enforce. We define these layouts as layouts that are the result of existing (or future optimizations) Our second technique to narrow the search space is based on analysis. We analyze the program trace and determine which parts of the layout space should not be explored since there seems to be no potential for these layouts to improve our program performance. We feed this narrowed space into out search engine, and we also provide a search strategy input, so we can perform a directed search further increasing the search efficiency. However, we still remained with the main problem, how to efficiently evaluate a given layout. We simply avoid it. How? As I will shortly describe we combine the new data layout and the current trace to produce a new trace. The trace that would result if we would have applied the transformation to the program. So we have new trace, but it still takes time to evaluate it. what is to evaluate a trace? to simulate it. To shorten the simulation time we have developed efficient evaluation techniques. Since out technique require analysis of the trace and we use the trace to avoid recompilation, we compress it. Summary 1. We narrowed the search space only to those optimization that has a potential to improve performance. 2. We have shorten the search cycle, we avoid recompilation, and we use efficient simulation methods. Transition. In the rest of the talk I m going to talk about the components of the framwork. (C" " ," " " (C,    0  H  0j ? ̙33? 0 tlp (  d  c $LD   `  s *  K    The objective of CMA is to increase page utilization of heap objects, and hence to improve the virtual memory performance. Let us see how the memory allocator can influence the performance of the virtual memory: 1. Here is a program that has a while look that repeatedly update two objects A and B. 2. Let us assume that these objects are heap objects that where allocated by allocator 1 dynamically allocates three objects and then excessively touches two of them. 3. Show the animation. 4. Now let us assume that the objects where allocated by allocator 2 5. show the animation. 6. Compare poor locality to good locality. Punch line: The goal of the optimization is to customize the allocator for the program under consideration. In order to do so, we need a good (great) placement function. Transition: Let us take a closer look on placement functions and how we can find them. P    H  0j ? ̙33r@ 0 2* (  d  c $LD     s * Kl  TL___PPT9.& PPlacement function: part of the allocation routine The domain is the heap objects allocated during runtime. The range are integers  represent heaps. Purpose of this slide What we did Summary of contribution Future work?@" HHIH  0j ? ̙33 C 0 N F <(  <d < c $LD   : < s *̉  K  xp___PPT9RJ HMemory hierarchy Several layers Access to each layer has a different cost For example: 1. a memory access that hits in the cache - cost only one cycles 2. a memory access that misses in the cache but hits in memory  cost hundreds of cycles. 3. Hence, the data organization in memory greatly affect the program performance. Let me illustrate how the data layout affects performance: Assume a program that accesses three data objects, A and B in the following sequence. Let us try to  picture the memory behavior: we will plot the memory addresses versus their time. Let assume that our physical memory contains only two virtual pages, and that our cache contains 4 blocks. Let us see what happen Now let as assume a different memory layout Transition: Now I will discuss the commonly used process to perform DL optimization. FD" \F  D\H < 0j ? ̙33/H 0  d(  dd d c $LD    d s *ԟ  K   iUSo, in the rest of the talk, I will focus on techniques to make the search feasible. H d 0j ? ̙334M 0 P (  d  c $LD     s *  K   n(I have reviewed how we represent the trace by a compressed symbolic trace. This representation is very useful because it enables us to shorten the search cycle, a cycle that includes producing a layout, producing the trace that is the result of this layout, simulating the trace and deciding whether we what to continue. Now let me describe how this representation helps us to shorten the search cycle. First I will show how we can produce a trace that reflect a data layout we want to evaluate. Later I will show how to efficiently evaluate the trace.))H  0j ? ̙33N 0  "(  d  c $LD   ~  s *_  K   So where are we now We have a data layout we want to evaluate. Using the symbolic trace we crated a new concrete trace that represent this layout. No we what to evaluate the performance of the new trace. The best way to do that  by smulation So, I will show now how we exploit the SEQUITURE representation to perform efficient simulationSS aH  0j ? ̙33S 0 P*(  d  c $LD     s *a  K`  H@___PPT9"  Problem read the problem Solution: read the solution Let us look again at the repetitions in SEQUITUR. Shaw what we want to avoid. We will use memoization General approach of memoization. Now I will illustrate what memoization values we need to keep in order to perform cache simulation. ,#" #>   ?H  0j ? ̙33, 0 \T`(  X  C LD   T  S  K    So, Yesterday we heard a talk about the theoretical aspects of data layout optimization. Today I m going to talk about the practical aspects of the optimization and I m going to present  Framework for Profile-Driven Data-Layout Optimizations I m shai rubin and this is a joint work with Ras Bodik and Trishul Chilimbi P"H  0j ? ̙3380___PPT10. p]X 0 f(  d  c $LD     s *x K   P<Purpose of this slide to explain how we avoid re-compilationH  0j ? ̙33/Z 0 @(  d  c $LD     s *(  K   iUSo, in the rest of the talk, I will focus on techniques to make the search feasible. H  0j ? ̙33px] `}^%D1 /GO[jWToT^EZ(Vj=Zݷ޾ٗ|sfvognIy9c$3NfL`l\$pۑdw1?`Q53epmdBG&kH[v[7JXZ̜&SY- =$IԻΤKgǀu>ųs<3?fIOp/3haߋ?ۯpV;9npƱ3jX Xf0e \G\N\!Xp\_\p wbp%J 7pǃ n w"Nbض16 \\ƀ+7J{2N7DpM7ܩং\%N7a26 f;pg; \p UPn"V/x_Ǻg_}oޡ͵PVQp  \3;Rp4|pE~q C=wX}E]ד#UѦhM<&m 5GN`8}PDn\8Ў|]ؾyꁹ` [$&`8?/(3OX?=B{ d@Q(!D\.ʋ<$ƟYIE+)9Rn"^Fhm5) V5kC˻1R Vz%8o. ܷ ME}*pF^V ?&ʣpw:@lBβb6kM<$ =IP ] ab\ C@ )׼g3,S]KB:(IJ.QJXa޴Je𦍀^=C]84B1%g4Bo0#gfOD$: 8U5y_i{IN:B#(};]a+; ]9.O;] {ٳxnVR!4Hcf0>V\n"P"Yx7V )48d}pXcnom:}XތQ,gpD>!qBLv'18&>2]FwW2m2%eCADlzUO? oӐ)亡nUF{wyz- j=[FeS&C:o߄rzN&(辂OK yx-vbkZ5>TmAMdzrǤA晕ˁ2 [(-G|A|cGvKrx,3x]k {,C.Fkx V6JpMVbgɶ{ (1xbzfq+=A̽{rs%(FGAV 5P'v| "}e6KCЅ7,n^Es{FuhwōMaHT=7(Ϗ.ƚ͡Z'C rvMdKб Ej6% T }PtPsz<j1QjjEK/}¯F Tpp$T!J \asnz"SM>gq 0iAaȹf[VVCg WQ^iJ`s0x ԛz5\{A+[K!#3mpC,  o۬|Zgɺ,eZRz]F7f@ $h60t9'BAW~2$zMJӼCH vfB]鯮~6˄CULM\)#?$դ%S+N(0Z y!qS3QUDRmV565!f9?n^Ī`I2Ui(*B.62&[|h~e0SƇc|X Pl) ExQP%V:lbn(]v'-.ȧ]#S68-ff:3J; ;ΆS`G8h4Bp(i {087r .R‘l7z)RSpIX5ٟtpP".3\g;B;۱Q C8Ż8/XML\At|'1!=(Cã=U{| ȴxYȴoNt2dp&^p!~i}@/K&p _s%>uzqzPYURʁ4-F9 m'3$c./d|,qz&Mf j_^QZ^rppL>߬ԆXL)"I "DɈh'C5sZh9Y2&MԖV'dĀ0UtgK8sjdbӰn-q f~0t#f]io `?;rDN_}ɀ{YP0զ{k_/(k݅ +tcȎ4ɦЕ00)goL?u\%z?:_B0*;Df|P1MlLT-RWEGbNHu2 Ӡ~8E_r94Ԏ~LU Ԯ2p3{uPwb]Є¯.5OY~O.fo \MZ hfՀf3 hhem@м4o@ R h4Z-Ài@2e+x96wEc;Ǹ O~ZS'ԓZnU`Ѝ` Z~JXKiRA?;r_U c[F3OR}f֟i,t+gR6nTC;!W sXn5;C{U*=IxHG9[g j> >tH.Nwbu9xta^]Oׅta)"|Y1L,bD-$|hO&d?Or(ΫWAb7we#/ ;P^-} +~sàRAqO}[Y(3ɤ ympfm$-w?|ʶ4WރdXʁ"`OP.6I$frPeag!; a7Z~rSsev Ϗ7[>z vg[f/(U>䆿nǠmE=Tvw#F݄beB 48#;9ȩ(ZE hѣh!<%/usZ1IEEѪhաh%]E+xӧxLs0Qx Gġ!(mݲYn|OTV "{2$(࿆7~ńd-AA+!Ȃs1<;}+{.ץ~v3"VDЪGJqi#CLRnUtAԳ/!( i#~& "8ʲy/DacOnr m>cs^6-\A 66`4zmO_ m$aKWd"hCmzm>_MRnSu AvBp3~nnbNZi'/mڻsF "88Vtk1k S"suS҃ڊ{op@NfϾstA;"h#h'Ijr;!H9(KA(fdTwRJINgs9){AY f3dsn_A2Xsu=੗߸|eP:sw`TlLZjՊ:*$\^w#D\Sp'Iʝjtȸtȸ@Eamo,xbAAdͮ>c 2\V*(vr wy_OPOHfq%EE\^|Q q!2.=2.BFį&)w2l k\׍k~RQG=v&5W- /L%ᥒH%ᥒkg~vIS$,ڛSP$?dMK{#*,=r|A8ޛ俎&(XK)vJ›$>bIx$RId3ֽ+ LRUOEƧCGȤ d| i4 r "sc~=ZO!Sf{I#*mKg ^.<^t 8 *+F*̾YNeCT|OPy'_?vLRS_iaYL‡2o*fϼ /O I#q,XJ7,̳'đ1p $1&}u+8ǀȎe[\ecZRڕC$IM !rz.M 3ok3zEg "rNw{f "RMsQ.AT.>L$E$k+?IADR=")\dàֻu`fvfZ4|ivNWK RfHu2J@~#:nb:B/kg\X0APz iTARXƬcӔTX _/-KaWO{K˔Or$ғD:D/}$ұ$ұ$%N%OWu3CE&CL!% dZ ^e.c!*w'Us4AAd'Rx 2~š "{H! /Vu D&#]mbL8jD}}ʧ/h5lqR{fv&Ln8"{P^(U SV2sc/RUc`.:& wM_iyasCMp/VSA  6y0& fNHI{1z~x􌷖y&`%*` `. ˍ# d?liWEj"W/2pz%_{N'ɑ' :b8켁/׿؝ Nǩ8w'͗vi k%MJN*b'A (=1^pLyjگ SCɖҰGKNtKx5J9aytmEhN8G)ЋGs43IoL4;媧0M4'(eŎ||iCn7 x%kHy)qf0$hOW Xӻn(~qc(8CkO77fv3NM'E<~5>Ε>6=Σ_䋬ak5DIK33,4f@4G/ha3XՇE0q+Т?pЎhf0s) sQ(Dw }$#)T}Vh>ڧsLbԟbK4L*R=h)'Gr˭4J8+Xhy b]e;z岖EN]64v<^3 l488S`bV0ؠs[? \D*k ~;FT>jVʱm`+sr59)#h9PկEv]℠,J2,TLXA}/SnW ⏑2cWy?24{[ ҐRGG0Cz߁8> !2;kPv0&t(:y$Z!+@;nu{@H?ʈScC[W!'1}zt%C8)'Wؕ-Ȋ|.fCSEy Ƨi'ҕ*U?+[[8C.b(/>1p.N!ghoywǀ) Y+w8C.CoCe%.9 p,Fx~!Fx!88X\iNّu1wRN22_t?{e]}MufytJ_4_4P+$Z5 T5S+QX641#%vr|bfE&fIRNƿs2[^wuj:5]tjGNN w:PJt:i&ـf1Y h6݀09 h.;*:"~j[c]ܻj-jG"11a ,4w0?L}Vb&O2Tu1N]L.[ILaq6u3suoRõ?FWZ;kS; 4Q\NS\ܛFѶ Gq.qmw_Z&SEq3|̓ RwA\٠]$u,8akPF""? 3 DRHdhNLj3T4!ISҌsG t;WKYLA.dc+dw)b 'QR$ +zX[J##NnUGi pݠ]2A5Ϯ?~]կ=_{؎G_{h(~Xӯ+=Ul۳nz_ׯC\kݹS&.WN/.W[)۹ut8T}>Mu+NIa4pMhbfT5RT8E3_ƏSI l]wh"e_O;4~}¯?( h1[@2 hfŀf5 hvÀ4 hnǀ5ufbO&*~>vc`+M,+~ƿ4pE3n?Ĩ|=>^dz4dvmTz4~ڿQ NdtT7~QOrW}^0`C&>DqKd՗ )/ |ݎʷ@ Rq'E& =OՓ}ep{o}Bǫ N4"oY}Ytyp^b:ς'LeujN i63SJgk@eJj1m\H!ds5w%&~* '!Y#۾6=^1 l"ɚz8nЗ Ua  rƲQ63f&$Y"dI4t^B՝:#1f8 ,Ye FIs|e?ۚny7@).3,ƲYP6 f!,$E*dG1튻B6+V1ycpY5-ĦVڗ[@Tl^ʶA*34s? ٬ƲYQ6+f%٬$rCSG"fp ܫ pXLgil 1eR˪qxt>6=X.]6zhI;AgmbS٬.Ik G=" "xmŧ,6KDB]`ѝ[bqEE78ns3h[G="hSrm$nn}b(5*nZRU.~;Z͓ G#Z0&E#D+:}vkG="n÷i#DVx{D &%a7d6עw]kl,g7?6R@)"̾l}]$(m n6RzT\ z5NdՈ%\7}mmvHkKcMm$zz o=vi_SoEm.]TuEjǴRE$1ǵP|niLR}$ږSǾ~MM:gj#tPm/#"o~P3H"X)11T)?%{/5UOb\]H(m־""|}~6RbI̷Y+⊹SX?cwl4KXeb aJY:a@lwNQ0ϘEH2Shr:@FK: ;~93׆S"e+CV+ͳa1yHY^tvIHt s%'".ZW!K3v)K#GcIr.rIXVB,^6^4z,m1Y,ADZ*Zڈ)w'xq\!H\mu}އ'wX]wp?v_]q;ZZ_“6N&J|hxk1ƭ_B-աq!>g}huh>.+7܊lAp؄\698= h4q[xzk7 \Š㩠P, 9J5+p8q }2@0ݠw:Ḯc=MH3 F>$͢,4RW.Oe%*#"%đuqpe[Kc'ЊiԃvЎ@LB&hh 05 4N|΁k/Tx9d6H\'{0vD-P gN:R:@.~fԡ)RYbuNt=3;,GW|[@rz͕8׻_J l*uoC-\{rp$\$"?r$oJr|[CӑbtFcVcJǔ4NǬKwh:2J\TLŜbn/bASd]&a]&a]&a]G1 9;6 C99&a|5IOg%Ds(hkMKbꅃ^ v>fڥqӮK;Z&C1nLLk(?>b&Ig(fPltb&Ig(ftb&Ig(ƥb&Ig(fɺY)TƆb+s&ꌩ}=k:6|`z9?'89g?d#1lItڎ_)}SV:[5TEL9m)enFMFTƆb\ջ tTљcc*.[sTn2>lp~G) 'SAxf12M#s3*nR7226{ۮ3oՃwܱ1m&UݐqH;J=ݱUζn>antL[%M{߳{^*__w_VI(@جJ[Y$^m=k*K8mV=EBy}c""\iCH"И)H5JfH5UcHeN? CtcC*vr4&cC)&nglsDјVbHLiM\Jt`,#Dc)N^$L:4wO0ꈩX*{lKp,l;Ե">78p dۏa&z3Lhp|a^Üʾg|'Mzaf{屮Kxa?wv:a|#Q'#zz2\$tH "#F~p'o8 7Cߤ}@zS]ٞ.}E~N><ɇ]f']f'jvnPNf'\mIIIqǡiR7 P G Cp(~.u=8)jL hfŀf5 hvӀ2 h׀3h8zGl+ز|}TKU}J\<Շ#!Շ3*a2ppiL?gCbE4[D ]Ǖ M3&!VZ~mn#@ۦV/qUp~Up>*HwJȫhzLـo(9VG~ށ5YZEԂ9x5W-[ff%UǼ-w"6u?&u"u"2V O*#O9Z)ǧsVĦe&Z J9+tgʦW/U9?6c^J+0eRqkK*ha8]wcJkjuM3eISOUϬ|xg'Zem~v]~]~N]~.MMwu`"cؗ\nͨޢE* N gk~H]$蘲cN/.'."hH6 %vHv}9*N6#RX{e M"Gt¹咉Múɕf}D7XŵWED\sDOm/{ɘ&¤&dUk#Yt/>F"!w:_"D$*ju+Ⱥ ڬ+!F*`nB07"Ȯ&G(yҾq DIт}~4&0+xxw\ǮF"!5MHV]$Dvٹo6MD& B6ƫ!D֣ !d/dU߽Cփ2yT<즦{kAdu.әE(:Jέ ]+D /!{|z.Eɬ͘&Ub&"U~n)hBX^dKhNK4b#M#A2xL+`U }6’Md(*qAE C6}>j핷7.gc0žľfhH]$CAYPP jS :nTpk{L G6~UзA? l6U9Fnd%}>Q6OK6G(<{$OcVlwbp5o}`ߏά?]? %V0O6qꉣ54Bbӣɬή+Yo/k$h[CTC@s)@CMs b\fbJcWL'3x!')a5z#?zKudF; }"MCgj|R}؀dI4?sh/ zN("q{OӞKo4Otipl<'j2'MOe9QDMBAs!c ]fF4spu9] -ks[ zjNg:|2n>8Ԅ͇1ى;S! pNi̎[eZ |TG:8(!XpxXQGʫhg8p@["pL3ǕR;o%Gv zu+Km,I7{A+AkAf氕Qe,jb3 㥰>gzexe,L$e  Q{յZ /~ppL3q?Û?>؜g(v";h/l>AM4\,A+ݡclQ?;M c~\w|dr1iDH1ȒϏԳ(4cVkteoʩ%t3=/޺QR Q;nv 5m<ʸ{cF2Bc_9~6ErDp9qpm\6V%εhpm\Դ0nn5</!'xԎڅ훷W֯b_oDh/qq +MFk͌Ѱ,V_N0BgZ@bT4#u&uaYVւ4f-U!X_ލ+awG\~߿=uaUGc]c"ihH*pF^V ?&ʣp#VHβ7rvi?F!naO|4l9z|5E~Fq4:?D7$Fh7xҹ\}{ҼKl"?[ nU*7tM,dbơy:)9ۤߤKdnpIAC;NcbC pa^RGӥJߎCWvWXɇ7MaQa={sފgN .1 ?"\}>R!-0FXV+.7u(Ez_Y-n Rhp.$tDq)FM7Gin9jT,㡵,TI8!e&߈A{S`bkA.D;A]fMFпtt?H3;<$OB4s~ cnUF{wyz- jtLoUpsŗMt~߾ $8M7Q.}xːL0~F|<5!} zZxMi5B״;]Y kz}xq9ԚM6/lNB+yfr`i2.],Z!J'c9MHK7k,wK1<øˁ7Z~5bnA WM#7| Nl~>eWa/m%f$Qbބ^2db̌ YΘY5A\btad4*I_Hf_Y}>Jsch75s~VYx nZDsÍj`9ub?= GkMT Pv`C\"Kp.)-ʃ%Cr))}kU>_4U5ϧ#d M ᦦ(p[W0 5.is5.UH .hrL Kq 3].R??XCPp]Y+ 0zh ]%L PmXF2cTy͑Ao `gbB on sK@44͡PUcJL^ 5 PUXcLsl{Oň)XܾXqMX7;* Yfp]4r=N |dۻ)\' d6YdjFMf6Ky@M) ժXTQ + !pU~~SBdl,|(ƒ>`ZԇlKNfZʳ-.W F D!(<[xȜK͒\^ sE8TpĒb ' X 7)O'G5(f-!\˽A"'j_,=ЯAypJ@ 'KBj«̥z?GF 2ó6*'4/ʓCKU_ =$T߰36R=K3#B#ŸNx$!I) tI}Hm\UG5s: 0 jFUiPh5k5xjU7!\/V60H k/h%|+2CZho,NP6ͪȭȭ? VZ\-cSo$l5Ŵ9Y5O|uXvAM~&d0O;ܼs:4O W/D!] 陧}Rg.#5qp#;z_K#:#5s%>uz #zx8jg K?r F.')EIJ0^(M4qc(fv.-T#Ȓ1ٔH󁸔6RSb@MjNO4f|eS)V/(cvzʷ1;=u 74ir1M+ƥU~DֵJq-]K/2 =|hS;*{<-C 7C'\~_ʞ;;\.#Gեi{"5O"%9K()#av̱4'q $R h4Z-Ài@ˊ~PpF Ɩ[rpWUfnZp? Ɨ:\:2Kp7ܯ ۣ͌Vp1FI ; 'w7vkw/p{:%c{q|O[)pO{:6|_6p^"86{ܫ^{pn bvчr` m_}n7} nO3 I7Z-7*Z0\?e~D+k_wl/EI}i-qA |3C-#'>3O4q3tJy*ݡҝU9j,ҽ*V~d|Q%}iqAP+\ePKsAmϕ6̮KaȋRrr¼0.̯ RDX+{\e@KY,bD-$|ʺlOk?!)8^W (yPV k6LP@y+PX> J v>nA (ҍw68o Fۃ~̰m8m'ռXs-*p2r˔>ZIjrmſ,:,S`g!&b[Or bw#sLP?.z+oSl{+ӣ#Tv7׏]CWgǭ`7~!$|(c/ko r bDx9 7щD8biIሥt"q<{?~LAA  @RFmmM7jWq =‘˶v^$v+EH !.B\Bgf D\D/ 7&\0#\l}IIH V~9! ")zDRɆAw$)jJd͊|iLY[C|;%N)3E S d:N% kqm1J3., (X =`)}vcֱiJ*, I0޽񂂥e'TIK"J_GWXXH'Iպ"C&d2-O/21AoŪĹ| 2)(mZ@?i!f0s) sQ(Dw }$#)T}Vh>ڧsp$ #΃C&V -l*J[ O(<|53tJw6,e-6-b5+98n:yLwE\NxrKl88S`bV0ؠ+媛u%RY+ yˇ1bƧZYEOhUsRm[iDF_#Haʶm@`VDdQ^ux*x6={|܇^>Aݮ H<|= -lZiH##!sP~E~JA]5(;Ё:B< :y= t$ȟeͩ!CNb-+ˇ^ >=:P!`+dE>m!u/v 9O N+U~>Wp!vq\P_|xc -C.О +CS糜W0q\:ކ}ˊK@zgVn ~P# U}v]L.Sӥ1yAf`qM k!qpϭQNB+Mv׮SӶ Gq.qmw_Z&SEq3|̓ RwAZl.:xR5Ijk#Y F]"[$]2X{W'&uc~A$ߩv Ziƹ#\:+ȥ, q뎱λdbwgyy1vU̓(R)aK=խmmdinC£4inЮhgCtN.מЯ=IklGuu#ѯ=t}>~8g_=VExjǦczuFׯZwhsx|I˕*ec++VvؤB͌m/Smw7340Sk!k>h]t>ݥOw?Uƣ(/OS݊ӯ4~lwX& \q8X$)Um||i8&NLbWԪv[?H/tE  h&ـf1Y h6݀09 h.ۀ1y hY`+37EYC'[ib!^3vS&'0sPdz4ddf?b!~Vb!~6V8Շ'>{U|>4 PQR7YoKߩ [nۂxnsF)Z"ԧɾ28k7 >Z'B]|V?aAv>{7s+fg<,X,Ⱦ,<8hz1gALٓ q&ٲ: g'p4EYfmx@)tN?m[6.wLǻO ?ͬm^elOtsdM=y KE*[_lfc(d3lfͬf$yVx:f!vјl3llMSekmZS$9pɲmM7<y͙{lc,(dl͢f#yv!d\zӘ1b8 ٬ٖ~bSe+~KݭglP*6 e tj?ο9lVc٬(dlV !cor~~)Tg3bۅKb8h,||T34Ә2eՌ8ixL,.tq$_Tf)}lpM|zOA%"!NN`ѭa8ƢYâXU빙{-` YN)lk6KDq7>1{7-~Qp8,7('A4F`L4F4Vtw6$6z~E$m}ݘoFrH$LK*olvAEx=TTٲYiom.R DJ}H)HhQ{mT qzpjpɪK~oHۈ9ڨחݛH. q&ի5I#zߵVIz ?cIc[ŋH]$5]黨R)E q=`i#Hck6ӈH?-}_[=:#1?țt΢/^F "_GJEB1(ߡgRE$-"Sb5b&R~K^gmmkܹ 6i#tP;۬}?EJEB1/.?VmT o"Vsl=q`;,i:L0%ÔtÔ0e\S)}:L3f,PŽ{ÔHP+wA,e2)q.eRV18vR9RE/BbtnI KU}Ȩ/䌝Ô%ɑ$9B$,Hrf l//(Kicdp!?(K.֪6b/I:^~F~`]~kp:p}c:V@Wǭi@܏]GaWNֶ󗠃$S_%Z(wAF̽qDc;ưb iuh\<7OYZs 5 %^lB.fr 4P֭Q~Iq.aTP(K|DMjr8Ȋτi> n]x{_87#$ 6ҔK]\H:>N>竄V؂ZGJcJcJcNcʼn_Õo+.b:@+bSZ3^1 䚌\h ?3@<:ï~j:vRKIx##r6dW@QXcxHt9H#xPSu9S RKUg1v8i`]=oo! 5W\fQ+[C'YLTo peӒp\e<Xxʒ)}o:MGb{r9EJGJȧ3Z)!SB>|8%>.ݡl(qR1s&WbRwihMuuuu?$>Gh$ wdiM&a>9͡L͏7ۻ(sfwلMBvA>8ֶAEcH 6$+|Ǟ"=)5/>R Tq?n=hsܙn6LL;wwPW'~"`*FoRQS.K#QӻRզ(|2ETf!if!iHNTf!if!if!if!q+eJ%if!i%(&TD1+⥕2w~6S\vV*}60;z90|lۛ_TT1QqJU So>F};䤶&7Ѡƽ M?wU]nw+\lC%}o>͇7'QI**h!_-䫾3M"'v>̦qn'O;3MvJ %f +˙TP+yMUB YW! *UB\I$ 4'wԝ$1-]}! %i$xoϿCw׮>Y;Ih}^?Iwީd_HB1*IH7A+qg?qcwhA\_ZW5$*+)I嬤;+eYI3t;+iQ"?$mV>ռ">]wVRUnYI _sG_rg%[G-~̝8ӪRu{LmJc)@f}OB!psEhEUn E Yg:7T)DS%#RPTzQD"g"9Y1 Mqu2srI6`J/D!2\R`8,ų,EqdJ'܌hԐ~"`|m׳Z4d#j`=yM( M(2@4A*N6JNѳ|##$_ H=L7aodF=̉Sh* Ň  '7܊q}$P|L|íH ߸G 7܎yM)@QJkBvCh'B;yov T Nҥ@B9>$ M&KKsyj8T$ }!ֹ{D܄?4iyt=|z")F~ҹ>s9F8h L(9V|˱[,JKʶg0d495뇷.\п5zib*9aϳ%r"Lɘkoעk09?^ؼQBqPzDM[s&s 7>{?Nܰy%k ضIۍ A*dۧO~2㝉ܫ E\ל}zצXxbd?z?~|VUcȞ+Uk>2}Y|ED6#k\ll.FqڜίD6|ʕN{jљW," Bd;+!  캫z~tU+tF_]X Z=7*Ad'2;T!!)"!icdCِl#[/- O!Fvw.DVn_o z'@=ұ\i+<"yKhZ<!]M"y|P'eF }h'% Zn:,3еNt-7:c(4 F<>)4xyat4<৩BL6) G6GQ騎̰t4p 9 >p>壣w<4I"AkBQp4(6]3-惙|l(eߖUTou [< 1GnR'v)|#$`-Oط/"}]u#7L|\yScWNMe騜جE5 W5/iY+TnZL6}%rZa>AZ04[CI0B,4 *pLK'Z!Y\ݮ}[x2Ƌ\{%Kޘg. IF0tdLARb' 7 FT)Q򍢔(ViGBj\N`@/ugLTGC6]O @Ip =Ռa/#V$\ÞaM ]dl;+%2v8Rmأy𰘲yZx2||:Ok {3|S3=O4166vB}Ógj$5|ЁE--nEsXzȨg+N#r<1K05^&^wp m>B@,q{A0lQ7bOcȬ_YeO#ʠ4PTL]Qt` {uֵߵN~%,S,.q+~>ZlbƁ}pk)~_A9#tT(Z g|偀 ,WY gEtՋ B|=FQ^7=xy8wk9&#gx 셴;i{G5@CFM SSn=ek]pbg(/\1F<Z>*KT3GzVӰȦ~Q-*l24z#?Oz(5lzB+k (pJ`HAᩛoܷQJPzVIwk`AkK'F~"ʼ2o[#ȼ2BAD2lj](5Ck;ns* xRߛҷʸo8z6I5} ӧ֐:^ymdB<*chcɮK߇k1-Mo"gqLc\l?i&~+{nc?+/ic5ǾF~k1-Vz>{yPXl?iqV1\l?iqlvk1J{e[鴡TߍD~ M;n ͱ|jKCM#IVBHDȋ_y[eVF歑y dW!*Yn,ܿ3tQtʼT=<yMYQ{)ړcg󩦝7kyk[b. NbsCRs6q{ͱUK[DXNohm-i+[ ewC{~=ӿ߱?rH]t鸋Ǎ<'QѠhԊ̣x7d8>/pύ_m˒8~y(BesԵ4UFawGkXV&d|[kb83Eϰ8>'?-5Fg ؟=~<4GMNcK1j*cO<^dk{8[T?hhkC\>N/fKk9W8,+&FЈ,ohjh[,D:^CD75۪Ӂvi68DW߀n鲺 #& ,k9NE&L;?d4"T}A=ڽtYӓpZV};S=f?z5쉬@ضC)!3+>U(5ߩYdY{(I'l'_Ʋ(dOQ4VB-u[L2K*ò*4L٨ߗ*Lţp ϊDh+ Sl7$IH[EuȼW+jfPsD 5c6ɣ~ &+r1tOi5c6~ ?] 0m?c~ &sk0Jפӆd H'"fb3y2o":d^̫yOL1dnQ?2O?1OL?e_ 䤀< ge/AVsA`?]?#ǒ,AZ~8=?E-1Fk؟=Zed3&~Mf77g_Kk YHW.,7+/OMG;~pۯB6L7zdr#_3&F,^=/ɽ9 MWmsdaI-ZnxWMLSA BHlL$%I11i+j xE'=yԃF&h<p41=իI֙}*@fߙ7m<|p46 ZX6Y.@ i($bSs.WY[c.˦ĪilM^%{tQyI|]H+/Lg[g0ra \d{ܿ!i¦ˏvAkڨj}/=P}NquZCWރj6XrI k<MD>7cc`UN yU)}v!Gk<8wwP\HMt"D(8ɏ'! ϸhtαZ}OdvtiGp{sh-\/8ɗB8IdP $&Hq$8Ro^˭#Џww"Bx8|ZB}1cORL 悪ڛڛY@݊k~$'>1Lmen1K[N2!q~֩\uM[FT̠lGHL?:Ju5M3XeDgl"#=Y+ ic!~B;R2ak-,`0L}BA1Qo$"xs;_siC ÈRV35e$t*x9y*r6K֌E#^J~c|&Cw; ͛~+!p3tCJ t9@2DK{DDJ#-/E[^3[zJvQⱇB>.a0OF.2x=kpu~Z>=,X~//F.1ㇼ6-!$nĦ $42qMa!Mɤ6aheZ'L Plsv+Kdw{}kVv߻7 k F͸  aBmЅ}8=*}Nc!"GHh='kx1Ƚ>xS(MhKʴ tXOqKIt?{Y`/`>\O B/krmᒊC(^cK0NX @c%)@c`*j0^q:Ba,j_ #;i3`br)3Q88ׁlqqpaqFZ\;u)^a\q1ހ0ވ&+1¸HX:1nx3cpm2!luL xlbi97ĆXWu[ ŵa ap~BkiXIO2/¾}5K8ٺn-t=hIv ۑDkeC86ON$gu=ɽiy9YW: ^8Cs#5&) R7> RY Jpy]1-P4ul#mDR+J.䆎=-Ve]={ TYBM~.ޡ?eߜ;87L .߭J]vM{K ؒl:o9֞dճ_<&0`=r4iP_uU^q*p4Yss&xƿ#N u'}Wkca8RUx~}DAQW A'e_=᪓tQYu7yG:Z=}}'݇:wvuޛ#}/%z "l'uC'0l'e۴H)&pnu]z=7Wݪ[ḫV괮OqUHǧ*t։j+\'mU~=b2$/ҋU)roTh*a+/xQwSD tL1f2&0G0}^Mz,1Xs)܁ *ix77bnF}NDgq$*A(=l騤t^ɕpHe*A:*Nу6\ "}a'.濇y8@%zD J1)G:‡vT(׏xO>ߏox@R>pO]m8n2џNXƿvP0G<91N-A׈] iNې~%q1frsR)M~#Up;+/:Q90F[نl|2,!ŔE3/X٣VxQpS%ڿV'A>ZU@>ARMsًd/; {3؟qRSa"he̞KԦDArڭH*S!$A0##7Uv`/m \2HA^mY@|~/mXe1Ԧ_щ\Ni$xT |’fاh6 k AGrl8kڮuv]Tbݏce\߽-Zf|/3$ 4~EJTz] q#fK$tVF2L4X|`atXVw&z).S71LZZPPC|YH8uo3ۑ|6B5s菮VO6q2tص9#iW-0ehUH#UYi$iJF"lf üvw!(;x?K3[kk0[~^6Ld1O% t?@fDNU~B|'+(i?yEa89OK(., )Zqlo&_X?'Ј;myO"m?9q'Nx=y@ֿ5,+Pп a]C.qߓKwoH{ Z2mqV喆`lFJ{٩݃e1onfJVvrm;)wVrsVn?g8קPnݜǃrpp3((>-ׄRngbm?FMGmpU۱y8Vk/3gCj-5Z9lh-g&lBи{$ƹYMM&;qm&g| x [0u[i

14y_oN14y_81{#< osLc:F^X<:4|f5W5Wfฏv8u3 =qYNmgmG]lA.EJ)Q:*ͼXmVYZVSkޱF~~|FNUSxT%;UNU2v*vk"XHk,{#ז:}đVXuGK.u gk~Hq :J+8˖?DH+4v~z婍8j[RlC;hcG%D9r4]6˟'lȵUbhƢo%$̅M'xV=15 %_65WFU(;#F0s՛-S_ϊd3 :hfGJy NFb{` M,Vh5?id'Xr {޶ƷL}vzAG+smcv0O2=1}/=߯WF;,#p7 zswHӸ_?_PC^+{f*5vj͌6dJ+CaaR~1ײ>}14fUa^ D^ y|~h2|q ל/{# &&ۮ4ٍ^`dGϗaV6t?ZzsHz4. [P Rˣa GÛpxW$JSCX>ߺHy4/ q ehy~Ԃ[4 G[x4W㱟aD4< ɹ-=>J*x64`gËwB:Sw`뜿‹OO:\H8CMxNq 벐pBB‘ C g(G f/B©s뇐pmwBFNgL_ꄐx 48ds>9DWSq'&' '0VssZ9x&} -cnaj98|O$,eC0DxpGh' zp' o(+ a/ XrRd $K 6-"7 a||N6i">]:mB#mw}]>@sܙw;3wֿ{_@\O*y}CdwtڛGb]W{_OOg$ryCk`N7 5Ϟ,D>icpPtBfꍡW% I=Y<í\{Y9o}a,g 9FWPאzym(ǂ6_x\tB ~YwR5E?ܐJyѧ<(+큥*nIG@ca]|菄xw>0=) 6x9ޏ-PIsԗwpw .G9'钥Jh {C. \cЊ膱=9|Xinjʣ$|# U 2u3̜Ym[s58FtP-VEN:RqxƗބ#l#Y%Q DZmކUj.UsVф[9ɶ9ql,,ŝ\Q?r\sb0Xa0Lxa^!^/q&/HL?yA ѵxג/_K ײQ\h"A:)4¼i$م6){ oXwó_}d6q{1:8 (cd_AZ8  4CoJBk+W'h8]l᪝XKo_GO헕=2#=ݝ(֎nV鏴uFVwѵ} .'m> Mvܳ#e5Bo:wAnI,H|f"ϙSʧjX#Zb^)Qׂs |>C0[/s%^k>WuSrHoBλpa59xe``A |9lzezQhB2s`2֙oAfxf·(UݥՇ OUЊO(b\MJJ;ITl6wmx{;ۀX#h8-g?jGd^mjQD NUH=YA~+u3Pep(UR{|7Xj@ż<;$+cAsl*{HrbE``PQj1E C.*W UR%n+hI:ABvfKhKlˇxkޅe s`6,7KHe.jT#IH:ljJM5~DM-U;bK4%'`?YA#HSx=-=o?^v=NO\gm낟0 *ӤuTI׃:X}d S_hNT zъ\֢]KS_ :x55:2ޅW! PO`߉-ohe4 lW͎ h>TVGW+DŽ Vi*l@tžOTIzpMHpVV xڢTɲHyqfHgF!G=ݑ*N*_ՙWMN&̩(2Y8Uʖv^Sқw R8j}GŇp-t*sSp3nנhp1n)?S u{-BxPoaKG%iÙn־/D'JU+ᗳmN׳sꄱ'j0+Wkl{fu]vܺ,xw1rH<%*N38JLl+-/&OWRytsւ3>1K~&PWI5u~nj[Z1Flq\jU}@g [\ʼnCJ>7b?cBϜOA|5HX_I[^Ȁ0!Sp/Oo~?U~KF^)c'Mq:W˶a: ,w<]Km؇|i!)Vy~,ߐ+c%嗆rE[h\|Go0&Ŝb+/XJYF JJVLy@_O/hd8a?la;? (vh-0^!۷G_dMMvKg-75Co/˯_EhhlY-,V#4fA$')WOkO?O"2M\?} 6+"PFK('L⋉ބ22>G/rĐWD?%8 8=\_x /v即ўkW3T>''U(V*ڼϒYuN:+euz.!#io'e*gy-$5WWMɽTZ:j c JuD:" (I#3oޤ}VȾBn&{VQ$ReWL*2!Kҥ3pMFh⨧8{dIj{UK-fCFFGR5BF^oz ,HvgSo QG9m}0D1崑#^cbQ{ ^w'JyAQy8,er(m/.(#-+R3~z{-+vtC`oeR 3 ͸w1q=&nhM\檨9ra &;oΛsf,1y2qL}.2XJW~u>ɲ~^Ġ#4HYnp6:8zy:|iƐOmᶮ:¦/;n X<)?+Ĕ&%6w>q?ïO?3>%] lcZb*LKwb.˿>h0pK,\krџ59XOw1҄b|jhs kΜ߇UQW ΰlOkOoͭ 1Ho ۡͩ9A>9q߂,|wLc)6e 73ulj61EHW ? O4  r0ADY? @pOh+'0\ `h  What this talk is about Shai Gopana shai rubina141Microsoft PowerPointut@K@0\)m]l@3 GL g  *  -- @ !--'@Times New Roman-.  2 1 ."System-@Arial-. '2 ,yFramework for Profilei"/'$ .-@Arial-.  2 ,-.-@Arial-. 2 , Analysis %  .-@Arial-.  2 oData(.-@Arial-.  2 o"-.-@Arial-. %2 o5Layout Optimizations, /  .-@Arial-. 2 V Shai Rubin  .-@Arial-. 2  Ras Bodikn .-@Arial-. 2 Trishul Chilimbi   ! .-@Arial-. "2 WMicrosoft Research    .-@Arial-. *2 W8University of Wisconsin     .-@Arial-. *2 WmUniversity of Wisconsin     .-՜.+,0    +On-screen ShowUWsLA Times New RomanArialSymbol WingdingsDefault DesignMicrosoft Excel ChartMicrosoft Equation 3.0:Framework for Profile-Analysis Data-Layout Optimizations Data Layout Optimization (What)Data Layout Optimization (How)0Problems with Current Data-Layout OptimizationSearching For a Data LayoutIs Search Practical?OutlineMaking the Search PracticalTrace Representation'Framework for Data-Layout OptimizationAvoid re-compilation'Framework for Data-Layout Optimization(Memoization: Efficient Trace SimulationOutlineFramework Application (1)$Field Reordering: Exhaustive SearchCustom Memory Allocator (CMA)CMA Placement Function (PF) CMA ResultsContributions and Future Work  Fonts UsedDesign TemplateEmbedded OLE Servers Slide Titles"_q  shai rubinshai rubin  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIKLMNOPQSTUVWXY[\]^_`ajRoot EntrydO)Pictures/!Current UserZSummaryInformation(JPowerPoint Document(qDocumentSummaryInformation8R