A Numerical Abstract Domain in light of Expression Abstraction Max Operator with Application in Timing Analysis

Slide1 l.jpg
1 / 21
0
0
1308 days ago, 480 views
PowerPoint PPT Presentation
Diagram. Timing Analysis = Compute typical many-sided quality limits of projects as far as inputs (expecting unit cost for statements)Challenges in Timing AnalysisReduce Timing Analysis to Abstract InterpretationExtend direct area with Expression AbstractionExtend straight space with Max Operator.

Presentation Transcript

Slide 1

A Numerical Abstract Domain in light of Expression Abstraction + Max Operator with Application in Timing Analysis Bhargav Gulavani (IIT Bombay, India) Sumit Gulwani (MSR Redmond) TexPoint textual styles utilized as a part of EMF. Perused the TexPoint manual before you erase this container.: An A

Slide 2

Outline Timing Analysis = Compute typical many-sided quality limits of projects as far as sources of info (expecting unit cost for articulations) Challenges in Timing Analysis Reduce Timing Analysis to Abstract Interpretation Extend straight area with Expression Abstraction Extend direct space with Max Operator

Slide 3

Timing Analysis Challenges Bounds for even straightforward projects might be Disjunctive (i.e., they include max administrators) Non-direct (polynomial, logarithmic, exponential) Sometimes notwithstanding demonstrating end is hard. We might want to register exact limits.

Slide 4

Simple Examples may have Disjunctive Bounds. Limits Max (0,n) n + Max(0,m ) Max( n,m ) Simple( int n) x := 0; while (x<n) x++; Simple2( int n,m ) Assume(n>0); x := 0; y := 0 ; while (x<n) if (y<m) y++ else x++; Simple3( int n, int m) Assume ( n,m > 0); x := 0; y := 0; while (x<n || y<m) x++; y++;

Slide 5

Simple Examples may have Non-direct limits. Limits n 2 n(n+1)/2 n 2 ModularMultiply ( int n) for (x:=0; x<n; x++) for (y:=0; y<n; y++); ModularSquare ( int n) for (x:=0; x<n; x++) for(y:=0; y<x; y++); Simple4( int n) x := 0; y := 0; while (x<n) if (y<n) y++; else y := 0; x++;

Slide 6

Even demonstrating end might be non-trifling. while (x<n) { x := x+y ; y := y+1; } Termination confirmation: lexicographic polyranking fns Our device processes bound: sqrt {2n} + max(0,- 2y 0 ) + 1 while (x<y) { if (z>x) x++; else z++; } Termination verification: disjunctively very much established positioning fns. Our apparatus registers bound: Max(0,y-x 0 ) + Max(0,y-z 0 )

Slide 7

We'd additionally get a kick out of the chance to figure exact limits. Accept n,m >0 and introductory estimation of x,y is 0. while (x<n || y<m) { x++; y++; } Bound is max( n,m ) while (x<n && y<m) { if (*) x++; else y++; } Bound is n+m while (x<n) { y++; if (y<m) y=0 else x++; } Bound is n £ m All cases above have same end contention : Between any two progressive (not really successive) emphasess: Either x increments and is limited by n Or y increments and is limited by m This infers a bound of n £ m for each situation conversely, we find exact limits for each of these.

Slide 8

Outline Challenges in Timing Analysis Reduce Timing Analysis to Abstract Interpretation Extend straight area with Expression Abstraction Extend direct space with Max Operator

Slide 9

Reduce Timing Analysis to Abstract Interpretation while c do S ctr := 0; while c do ctr := ctr+1 ; S Claim: Let u be an upper bound on circle counter ctr inside the circle. At that point Max(0,u) indicates an upper bound on the quantity of circle cycles.

Slide 10

Example x := 0; y := n; ctr := 0; while (x < y) ctr := ctr+1; if (*) x := x+2; else y := y-2; Abstract Interpreter delivers the circle invariant: 2* ctr = x + (n-y) Æ x<y Projecting out x and y yields ctr · n/2 . In this manner, Max{ 0, n/2 } is an upper bound on circle cycles.

Slide 11

Design of our Numerical space We have to perform theoretical translation over a numerical area that can reason about non-linearity and also disjunctions. Numerical Domain = Linear Arithmetic Domain, (for example, Polyhedra ) lifted with Expression Abstraction (for non-linearity) and Max Operator (for taking care of disjunctions)

Slide 12

Outline Challenges in Timing Analysis Reduce Timing Analysis to Abstract Interpretation Extend straight space with Expression Abstraction Extend direct area with Max Operator

Slide 13

Extend Linear area with Expression Abstraction Choose an arrangement of expressions S over program factors V (shut under sub-expressions) Extended space speaks to limitations over V [ S Define semantics of administrators in S utilizing coordinated derivation rules ( T , L , R ) s.t . L and R are direct disparities over expressions in T. On the off chance that L holds, then R holds (according to the semantics of the administrators utilized as a part of T). {e 1 ,e ,2 e 1 ,2 e 2 } e 1 · e 2 +c ) 2 e 1 · 2 e 2 £ 2 c { e 1 , e 2 , log(e 1 ), log(e 2 )} e 1 · ce 2 Æ 0 · e 1 Æ 0 · e 2 ) log(e 1 ) · log c + log(e 2 ) { e i , ee i } i  i c i e i ¸ c Æ e ¸ 0 )  i c i ee i ¸ ce

Slide 14

Transfer Functions of Extended Domain Transfer Functions for augmented space basically apply comparing exchange work over given straight area in the wake of soaking the sources of info (which includes including new direct connections utilizing modify rules). Saturate(A): do A' := A; for every induction govern (T, L , R ) for each match ¾ : T ! S if A' ) L ¾ , then A' := A' Æ R ¾ while ( : (A ) A') && not drained)

Slide 15

Outline Challenges in Timing Analysis Reduce Timing Analysis to Abstract Interpretation Extend straight space with Expression Abstraction Extend direct area with Max Operator

Slide 16

Extend direct space with Max Operator Choose a subset U of program factors V Typically U is set of sources of info New space speaks to imperatives over V-U, however with wealthier steady terms, developed utilizing (direct blends of) max-direct expressions over U Example: x + 2y · Max( n+m , 2n+3) Max-direct expression over U is of the frame Max(e 1 ,.., e n ), where e i is direct over U

Slide 17

Transfer Functions of Extended Domain Transfer Functions make utilization of Witness Function in view of Farkas lemma. Farkas Lemma Let e, e i be some direct number juggling expressions with no consistent term. On the off chance that { e i · 0 } i ) e · 0, then 9 ¸ i ¸ 0 s.t . e "  i ¸ i e i We allude to ( ¸ i ) as Witness ( { e i · 0} i , e · 0 ). Cases: Witness( y-2x · 0 Æ x · 0 , y · 0 ) = (1,2)

Slide 18

Join Transfer Function Join(A, B ): Let A be { e i · f i } i [ e i : direct over V-U, f i : max-straight over U] Let B be { e i " · f i '} i A s := { e i · 0} i ; B s := { e i " · 0} i ; C s := Join(A s ,B s ); Result := { e · f "" | (e · 0) 2 C s } where f'' is as per the following: ( ¸ i ) := Witness(A s , e · 0); f :=  i ¸ i f i ; ( ¸ i ') := Witness(B s , e · 0); f' :=  i ¸ i " f' i ; f'' := Max( f,f '); Correctness Proof: It can be demonstrated that A ) e · f "" and B ) e · f "" Example : Let V be { y,x,n,m } and U be { n,m } Let A be y · m and B be y–2x · k Æ x · n Then, Join(A,B ) is y · max (m, k+2 n )

Slide 19

Experiments

Slide 20

Related Work Worst Case Execution Time Wilhelm, CAV 2008 (Focus on building points of interest). Our attention is on circle limits Non-direct (polynomial imbalances) invariant era Sankaranarayanan et al, POPL 2004; Muller-Olm , Seidl , POPL 2004; Bagnara et al, SAS 2005 We permit any administrator however over a settled arrangement of expressions Inference run based thinking for choice techniques ( eg , Jhala , McMillan; CAV 2007) We demonstrate to stretch out thoughts to digest translation. Disjunctive Numerical Domains Our calculation finds a particular sort of disjunctive invariants utilizing Farkas lemma.

Slide 21

Conclusion Timing Analysis utilizing a numerical area reached out with Expression Abstraction (to deal with non-linearity) Max Operator (to deal with disjunctions) Part 2 of the discussion @ HAV 2008 Data-structures Bonus: An alternate approach to find non-straight and disjunctive limits utilizing just a direct numerical space, however in a CEGAR setting.

SPONSORS