Changeset 3120


Ignore:
Timestamp:
Apr 11, 2013, 2:04:33 PM (4 years ago)
Author:
sacerdot
Message:

...

File:
1 edited

Legend:

Unmodified
Added
Removed
  • Deliverables/D6.3/report.tex

    r3119 r3120  
    371371Among the possible views, the ones that we will easily be able to work
    372372with 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'|$.
     373A view $(\mathcal{V},|.|)$ is execution history dependent with a lookahead
     374of length $n$ when there exists
     375a transition function $\hookrightarrow : PC^n \times \mathcal{V} \to \mathcal{V}$
     376such 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
     380Less formally, a view is
     381dependent on the execution history if the evolution of the views is fully
     382determined by the evolution of the program counters. To better understand
     383the definition, consider the case where the next instruction to be executed
     384is a conditional jump. Without knowing the values of the registers, it is
     385impossible to determine if the true or false branches will be taken. Therefore
     386it is likely to be impossible to determine the value of the view the follows
     387the current one. On the other hand, knowing the program counter that will be
     388reached executing the conditional branch, we also know which
     389branch will be taken and this may be sufficient to compute the new view.
     390Lookaheads longer then 1 will be used in case of pipelines: when executing
     391one instruction in a system with a pipeline of length $n$, the internal state
     392of the pipeline already holds information on the next $n$ instructions to
     393be executed.
    378394
    379395The reference to execution historys in the names is due to the following
     
    381397can be lifted to the type $EP \times \mathcal{V} \to \mathcal{V}$ by folding
    382398the definition over the path trace:
    383 $((pc_0,\ldots,pc_n),v_0) \hookrightarrow v_{n+1}$ iff for all $i \leq n$,
    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}$.
    385401Moreover, the folding is clearly associative:
    386402$(\tau_1 @ \tau_2, v) \hookrightarrow v''$ iff
     
    427443
    428444The 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}$.
     445execution 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
     447pipeline with $n$ stages may require $n$ lookaheads:
     448$\hookrightarrow : PC^n \times \{0,1\}^n \to \{0,1\}^n$.
    432449
    433450While the model is a bit simplicistic, it can nevertheless be used to describe
     
    467484The cost $K(v_0,L)$ associated to the block labelled with
    468485$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
     488lookahead required. When the lookahead requires program counters outside the
     489block under analysis, we are free to use dummy ones because the parts of the
     490view that deal with future behaviour have no impact on the cost of the
     491previous operations by assumption.
     492
     493The static analysis can be performed
    471494in linear time in the size of the program because the cardinality of the sets
    472495of labels (i.e. the number of basic blocks) is bounded by the size of the
     
    487510just gave. The reason is that, if $pc_i$ is a function call executed in
    488511the 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
     512will 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).
     514Indeed $pc_{i+1}$ is the program counter of the instruction that follows
     515the call, whereas the next program counter to be reached is the one of the
     516body 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
     518the call, while we should know the state after the function returns.
     519The latter cannot be
    492520statically predicted. That's why we had to impose labels after calls.
    493521Associativity, on the other hand, trivially holds. Therefore the proof
     
    496524So 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.
    497525The 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
     527associates to each pair of consecutively executed basic blocks and input view
     528the view obtained at the end of the execution of the first block.
     529
     530The 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
     532with $L'$. We assume here that $m$ is always longer or equal to the lookahead
     533required by the transition function $\hookrightarrow$ over execution paths.
     534When this is not the case we could make the new transition function take in
     535input 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.
     537In the rest of the paragraph we assume to have followed the second approach
     538to simplify the presentation.
     539
     540The extended transition function over labels is not present in the basic labelling approach. Actually, the basic labelling
     541approach can be understood as the generalized approach where the view $\mathcal{V} = \mathbbm{1}$.
     542The computation of the extended $\hookrightarrow$ transition function
     543is again linear in the size of the program.
    505544
    506545Both the versions of $K$ and $\hookrightarrow$ defined over labels can be
    507546lifted 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
     547trace: 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
    512550clearly associative.
    513551
     
    526564values of the views during execution:
    527565\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.
    537589\end{itemize}
    538590
     591\paragraph{An example of instrumentation in presence of a pipeline}
     592In Figure~\ref{factprogi} we show how the instrumentationof a program
     593that computes the factorial of 10 would look like in presence of a pipeline.
     594The instrumentation has been manually produced. The \texttt{\_\_next}
     595function says that the body of the internal loop of the \texttt{fact}
     596function can be executed in two different internal states, summarized by the
     597views 2 and 3. The view 2 holds at the beginning of even iterations,
     598while the view 3 holds at the beginning of odd ones. Therefore even and odd
     599iterations are assigned a different cost. Also the code after the loop can
     600be executed in two different states, depending on the oddness of the last
     601loop iteration.
     602
     603\begin{figure}[t]
     604\begin{center}
     605\begin{verbatim}
     606int fact (int n) {
     607  int i, res = 1;
     608  for (i = 1 ; i <= n ; i++) res *= i;
     609  return res;
     610}
     611
     612int 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
     620The definitions of \texttt{\_\_next} and \texttt{\_\_K} are just examples.
     621For instance, it is possible as well that each one of the 10 iterations
     622is executed in a different internal state.
     623
     624\begin{figure}[t]
     625\begin{tiny}
     626\begin{verbatim}
     627int __cost = 8;
     628int __label = 0;
     629int __view;
     630
     631void __cost_incr(int incr) {
     632  __cost = __cost + incr;
     633}
     634
     635int __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
     647int __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
     657int 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
     680int 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
    539701\end{document}
Note: See TracChangeset for help on using the changeset viewer.