Changeset 3120
- Timestamp:
- Apr 11, 2013, 2:04:33 PM (8 years ago)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
Deliverables/D6.3/report.tex
r3119 r3120 371 371 Among the possible views, the ones that we will easily be able to work 372 372 with in the labelling approach are the \emph{execution history dependent views}. 373 A view $(\mathcal{V},|.|)$ is execution history dependent when there exists 374 a transition function $\hookrightarrow : PC \times \mathcal{V} \to \mathcal{V}$ 375 such that for all $(\sigma,\delta)$ and $pc$ such that $pc$ is the program 376 counter of $\sigma$, $(\sigma,\delta) \Longrightarrow \delta'$ iff 377 $(pc,|\delta|) \hookrightarrow |\delta'|$. 373 A view $(\mathcal{V},|.|)$ is execution history dependent with a lookahead 374 of length $n$ when there exists 375 a transition function $\hookrightarrow : PC^n \times \mathcal{V} \to \mathcal{V}$ 376 such that for all $(\sigma,\delta)$ and $pc_1,\ldots,pc_n$ such that every 377 $pc_i$ is the program counter of $\sigma_i$ defined by $\sigma \longrightarrow^i \sigma_i$, we have $(\sigma,\delta) \Longrightarrow \delta'$ iff 378 $((pc_1,\ldots,pc_n),|\delta|) \hookrightarrow |\delta'|$. 379 380 Less formally, a view is 381 dependent on the execution history if the evolution of the views is fully 382 determined by the evolution of the program counters. To better understand 383 the definition, consider the case where the next instruction to be executed 384 is a conditional jump. Without knowing the values of the registers, it is 385 impossible to determine if the true or false branches will be taken. Therefore 386 it is likely to be impossible to determine the value of the view the follows 387 the current one. On the other hand, knowing the program counter that will be 388 reached executing the conditional branch, we also know which 389 branch will be taken and this may be sufficient to compute the new view. 390 Lookaheads longer then 1 will be used in case of pipelines: when executing 391 one instruction in a system with a pipeline of length $n$, the internal state 392 of the pipeline already holds information on the next $n$ instructions to 393 be executed. 378 394 379 395 The reference to execution historys in the names is due to the following … … 381 397 can be lifted to the type $EP \times \mathcal{V} \to \mathcal{V}$ by folding 382 398 the definition over the path trace: 383 $((pc_0,\ldots,pc_ n),v_0) \hookrightarrow v_{n+1}$ iff for all $i \leqn$,384 $( pc_i,v_i) \hookrightarrow v_{i+1}$.399 $((pc_0,\ldots,pc_m),v_0) \hookrightarrow v_n$ iff for all $i \leq m - n$, 400 $((pc_i,\ldots,pc_{i+n}),v_i) \hookrightarrow v_{i+1}$. 385 401 Moreover, the folding is clearly associative: 386 402 $(\tau_1 @ \tau_2, v) \hookrightarrow v''$ iff … … 427 443 428 444 The assumptions on the lack of influence of operands values on stalls and 429 execution times ensures the existence of the transition function 430 $\hookrightarrow : PC \times \{0,1\}^n \to \{0,1\}^n$ and the data 431 independent cost function $K: PC \times \{0,1\}^n \to \mathbb{N}$. 445 execution times ensures the existence of the data independent cost function 446 $K: PC \times \{0,1\}^n \to \mathbb{N}$. The transition function for a 447 pipeline with $n$ stages may require $n$ lookaheads: 448 $\hookrightarrow : PC^n \times \{0,1\}^n \to \{0,1\}^n$. 432 449 433 450 While the model is a bit simplicistic, it can nevertheless be used to describe … … 467 484 The cost $K(v_0,L)$ associated to the block labelled with 468 485 $L$ and the initial view $v_0$ is 469 $K(pc_0,v_0) + K(pc_1,v_1) + \ldots + K(pc_n,v_n)$ where for every $i$, 470 $(pc_i,v_i) \hookrightarrow v_{k+1}$. The static analysis can be performed 486 $K(pc_0,v_0) + K(pc_1,v_1) + \ldots + K(pc_n,v_n)$ where for every $i < n$, 487 $((pc_i,\ldots,pc_{i+l}),v_i) \hookrightarrow v_{k+1}$ where $l$ is the 488 lookahead required. When the lookahead requires program counters outside the 489 block under analysis, we are free to use dummy ones because the parts of the 490 view that deal with future behaviour have no impact on the cost of the 491 previous operations by assumption. 492 493 The static analysis can be performed 471 494 in linear time in the size of the program because the cardinality of the sets 472 495 of labels (i.e. the number of basic blocks) is bounded by the size of the … … 487 510 just gave. The reason is that, if $pc_i$ is a function call executed in 488 511 the view (state) $v_i$, it is not true that, after return, the state 489 will be $v_i+1$ defined by $(pc_i,v_i) \hookrightarrow v_{i+1}$. Indeed 490 $v_{i+1}$ will be the state at the execution of the body of the call, while 491 we should know the state after the function returns. The latter cannot be 512 will be $v_i+1$ defined by $(pc_i,pc_{i+1},v_i) \hookrightarrow v_{i+1}$ 513 (assuming a lookahead of 1, which is already problematic). 514 Indeed $pc_{i+1}$ is the program counter of the instruction that follows 515 the call, whereas the next program counter to be reached is the one of the 516 body of the call. Moreover, even if the computation would make sense, 517 $v_{i+1}$ would be the state at the beginning of the execution of the body of 518 the call, while we should know the state after the function returns. 519 The latter cannot be 492 520 statically predicted. That's why we had to impose labels after calls. 493 521 Associativity, on the other hand, trivially holds. Therefore the proof … … 496 524 So far, we have computed the dependent cost $K: \mathcal{V} \times \mathcal{L} \to \mathbb{N}$ that associates a cost to basic blocks and views. 497 525 The second step consists in statically computing the transition function 498 $\hookrightarrow : \mathcal{L} \times \mathcal{V} \to \mathcal{V}$ that 499 associates to each basic block and input view the view obtained at the end 500 of the execution of the block. The definition is straightforward: 501 $(L,v) \hookrightarrow v'$ iff $((pc_0,\ldots,pc_n),v) \hookrightarrow v'$ 502 where $(pc_0,\ldots,pc_n)$ are the program counters of the block labelled by 503 $L$. This transition function is not necessary in the basic labelling approach. 504 Its computation is again linear in the size of the program. 526 $\hookrightarrow : \mathcal{L} \times \mathcal{L} \times \mathcal{V} \to \mathcal{V}$ that 527 associates to each pair of consecutively executed basic blocks and input view 528 the view obtained at the end of the execution of the first block. 529 530 The definition is the following: 531 $(L,L',v) \hookrightarrow v'$ iff $((pc_0,\ldots,pc_n,pc'_0,\ldots,pc'_m),v) \hookrightarrow v'$ where $(pc_0,\ldots,pc_n)$ are the program counters of the block labelled by $L$ and $(pc'_0,\ldots,pc'_m)$ are those of the block labelled 532 with $L'$. We assume here that $m$ is always longer or equal to the lookahead 533 required by the transition function $\hookrightarrow$ over execution paths. 534 When this is not the case we could make the new transition function take in 535 input a longer lookahead of labels. Or we may assume to introduce enough 536 \texttt{NOP}s at the beginning of the block $L'$ to enforce the property. 537 In the rest of the paragraph we assume to have followed the second approach 538 to simplify the presentation. 539 540 The extended transition function over labels is not present in the basic labelling approach. Actually, the basic labelling 541 approach can be understood as the generalized approach where the view $\mathcal{V} = \mathbbm{1}$. 542 The computation of the extended $\hookrightarrow$ transition function 543 is again linear in the size of the program. 505 544 506 545 Both the versions of $K$ and $\hookrightarrow$ defined over labels can be 507 546 lifted to work over traces by folding them over the list of labels in the 508 trace: $K((L_1,\ldots,L_n),v) = K(L_1,v) + K((L_2,\ldots,L_n),v')$ where 509 $(L_1,v) \hookrightarrow v'$ and 510 $((L_1,\ldots,L_n),v) \hookrightarrow v''$ iff $(L_1,v) \hookrightarrow v'$ and 511 $((L_2,\ldots,L_n),v') \hookrightarrow v''$. The two definitions are also 547 trace: for $K$ we have $K((L_1,\ldots,L_n),v) = K(L_1,v) + K((L_2,\ldots,L_n),v')$ where 548 $(L_1,L_2,v) \hookrightarrow v'$; for $\hookrightarrow$ we have 549 $((L_1,\ldots,L_n),v) \hookrightarrow v''$ iff $(L_1,L_2,v) \hookrightarrow v'$ and $((L_2,\ldots,L_n),v') \hookrightarrow v''$. The two definitions are also 512 550 clearly associative. 513 551 … … 526 564 values of the views during execution: 527 565 \begin{itemize} 528 \item We define two global variables \texttt{\_\_cost}, initialized at 0, 529 and \texttt{\_\_view}, initialized with $|\delta_0|$ where $\delta_0$ is 530 the initial value of the internal state at the beginning of program 531 execution. 532 \item At the beginning of every basic block labelled by $L$ we add 533 \texttt{\_\_cost += }$K(\mbox{\texttt{\_\_view}},L)$\texttt{;} which pre-pays the cost for the 534 execution of the block in the current view (state) \texttt{\_\_view}. 535 \item At every exit point from the basic block we add 536 \texttt{\_\_view = }$v$ where 566 \item We define three global variables \texttt{\_\_cost}, initialized at 0, 567 \texttt{\_\_label}, initialized with \texttt{NULL}, and 568 \texttt{\_\_view}, uninitialized. 569 \item At the beginning of every basic block labelled by $L$ we add the 570 following code fragment: 571 572 \begin{tabular}{l} 573 \texttt{\_\_view = \_\_next(\_\_label,}$L$\texttt{,\_\_view);}\\ 574 \texttt{\_\_cost += }$K(\mbox{\texttt{\_\_view}},L)$\texttt{;}\\ 575 \texttt{\_\_label = }$L$\texttt{;} 576 \end{tabular} 577 578 where \texttt{\_\_next(}$L_1,L_2,v$\texttt{)} = $v'$ iff 579 $(L_1,L_2,v) \hookrightarrow v'$ unless $L_1$ is \texttt{NULL}. 580 In that case \texttt{(\_\_next(NULL,}$L$\texttt{)} = $v_0$ where 581 $v_0 = |\delta_0|$ and $\delta_0$ is the initial value of the internal stat 582 at the beginning of program execution. 583 584 The first line of the code fragment computes the view at the beginning of 585 the execution of the block from the view at the end of the previous block. 586 Then we update the cost function with the cost of the block. Finally we 587 remember the current block to use it for the computation of the next view 588 at the beginning of the next block. 537 589 \end{itemize} 538 590 591 \paragraph{An example of instrumentation in presence of a pipeline} 592 In Figure~\ref{factprogi} we show how the instrumentationof a program 593 that computes the factorial of 10 would look like in presence of a pipeline. 594 The instrumentation has been manually produced. The \texttt{\_\_next} 595 function says that the body of the internal loop of the \texttt{fact} 596 function can be executed in two different internal states, summarized by the 597 views 2 and 3. The view 2 holds at the beginning of even iterations, 598 while the view 3 holds at the beginning of odd ones. Therefore even and odd 599 iterations are assigned a different cost. Also the code after the loop can 600 be executed in two different states, depending on the oddness of the last 601 loop iteration. 602 603 \begin{figure}[t] 604 \begin{center} 605 \begin{verbatim} 606 int fact (int n) { 607 int i, res = 1; 608 for (i = 1 ; i <= n ; i++) res *= i; 609 return res; 610 } 611 612 int main () { 613 return (fact(10)); 614 } 615 \end{verbatim} 616 \end{center} 617 \caption{A simple program that computes the factorial of 10.\label{factprog}} 618 \end{figure} 619 620 The definitions of \texttt{\_\_next} and \texttt{\_\_K} are just examples. 621 For instance, it is possible as well that each one of the 10 iterations 622 is executed in a different internal state. 623 624 \begin{figure}[t] 625 \begin{tiny} 626 \begin{verbatim} 627 int __cost = 8; 628 int __label = 0; 629 int __view; 630 631 void __cost_incr(int incr) { 632 __cost = __cost + incr; 633 } 634 635 int __next(int label1, int label2, int view) { 636 if (label1 == 0) return 0; 637 else if (label1 == 0 && label2 == 1) return 1; 638 else if (label1 == 1 && label2 == 2) return 2; 639 else if (label1 == 2 && label2 == 2 && view == 2) return 3; 640 else if (label1 == 2 && label2 == 2 && view == 3) return 2; 641 else if (label1 == 2 && label2 == 3 && view == 2) return 1; 642 else if (label1 == 2 && label2 == 3 && view == 3) return 0; 643 else if (label1 == 3 && label2 == 4 && view == 0) return 0; 644 else if (label1 == 3 && label2 == 4 && view == 1) return 0; 645 } 646 647 int __K(int view, int label) { 648 if (view == 0 && label == 0) return 3; 649 else if (view == 1 && label == 1) return 14; 650 else if (view == 2 && label == 2) return 35; 651 else if (view == 3 && label == 2) return 26; 652 else if (view == 0 && label == 3) return 6; 653 else if (view == 1 && label == 3) return 8; 654 else if (view == 0 && label == 4) return 6; 655 } 656 657 int fact(int n) 658 { 659 int i; 660 int res; 661 int k; 662 __view = __next(__label,1,__view); 663 k = __K(__view,1); 664 __cost_incr(k); 665 __label = 1; 666 res = 1; 667 for (i = 1; i <= n; i = i + 1) { 668 __view = __next(__label,2,__view); 669 __cost_incr(__K(__view,2)); 670 __label = 2; 671 res = res * i; 672 } 673 __view = __next(__label,3,__view); 674 k = __K(__view,3); 675 __cost_incr(k); 676 __label = 3; 677 return res; 678 } 679 680 int main(void) 681 { 682 int t; 683 int k; 684 __view = __next(__label,0,__view); 685 k = __K(__view,0); 686 __cost_incr(k); 687 __label = 0; 688 t = fact(10); 689 __view = __next(__label,4,__view); 690 k = __K(__view,4); 691 __cost_incr(k); 692 __label = 4; 693 return t; 694 } 695 \end{verbatim} 696 \end{tiny} 697 \caption{The instrumented version of the program in Figure~\ref{factprog}.\label{factprogi}} 698 \end{figure} 699 700 539 701 \end{document}
Note: See TracChangeset
for help on using the changeset viewer.