Changeset 3117

Apr 10, 2013, 6:25:20 PM (4 years ago)


1 edited


  • Deliverables/D6.3/report.tex

    r3116 r3117  
    300301obtained from the execution history by forgetting all the remaining information.
    301302The execution path of the history $\sigma_0 \longrightarrow \sigma_1 \longrightarrow \sigma_2 \ldots$ is $pc_0,pc_1,\ldots$ where each $pc_i$ is the program
    302 counter of $\sigma_i$.
     303counter of $\sigma_i$. We denote the set of finite execution paths with $EP$.
    304305We claim this simple model to be generic enough to cover real world
    370371Among the possible views, the ones that we will easily be able to work
    371 with in the labelling approach are the \emph{execution path dependent views}.
    372 A view $(\mathcal{V},|.|)$ is execution path dependent when there exists
     372with in the labelling approach are the \emph{execution history dependent views}.
     373A view $(\mathcal{V},|.|)$ is execution history dependent when there exists
    373374a transition function $\hookrightarrow : PC \times \mathcal{V} \to \mathcal{V}$
    374375such that for all $(\sigma,\delta)$ and $pc$ such that $pc$ is the program
    376377$(pc,|\delta|) \hookrightarrow |\delta'|$.
     379The reference to execution historys in the names is due to the following
     380fact: every execution history dependent transition function $\hookrightarrow$
     381can be lifted to the type $EP \times \mathcal{V} \to \mathcal{V}$ by folding
     382the 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}$.
     385Moreover, the folding is clearly associative:
     386$(\tau_1 @ \tau_2, v) \hookrightarrow v''$ iff
     387$(\tau_1,v) \hookrightarrow v'$ and $(\tau_2,v') \hookrightarrow v''$.
    378389As a final definition, we say that a cost function $K$ is
    379390\emph{data independent} if it is dependent on a view that is execution path
    380 dependent. In the next paragraph we will show how we can extend the
     391dependent. In two paragraphs we will show how we can extend the
    381392labelling approach to deal with data independent cost models.
     394Before that, we show that the class of data independent cost functions
     395is not too restricted to be interesting. In particular, at least simple
     396pipeline models admit data independent cost functions.
     398\paragraph{A data independent cost function for simple pipelines}
     399We consider here a simple model for a pipeline with $n$ stages without branch
     400prediction and hazards. We also assume that the actual value of the operands
     401of the instruction that is being read have no influence on stalls (i.e. the
     402creation of bubbles) nor on the execution cost. The type of operands, however,
     403can. For example, reading the value 4 from a register may stall a pipeline
     404if the register has not been written yet, while reading 4 from a different
     405register may not stall the pipeline.
     407The internal states $\Delta$ of the pipeline are $n$-tuples of decoded
     408instructions or bubbles:
     409$\Delta = (\mathcal{I} \times \Gamma \cup \mathbbm{1})^n$.
     410This representation is not meant to describe the real data structures used
     411in the pipeline: in the implementation the operands are not present in every
     412stage of the pipeline, but are progressively fetched. A state
     413$(x_1,x_2,\ldots,(I,\gamma))$ represents the state of the pipeline just before
     414the completion of instruction $(I,\gamma)$. The first $n-1$ instructions that
     415follow $I$ may already be stored in the pipeline, unless bubbles have delayed
     416one or more of them.
     418We introduce the following view over internal states:
     419$(\{0,1\}^n,|.|)$ where $\mathbb{N}_n = {0,\ldots,2^n-1}$ and
     420$|(x_1,\ldots,x_n)| = (y_1,\ldots,y_n)$ where $y_i$ is 1 iff $x_i$ is a bubble.
     421Thus the view only remembers which stages of the pipelines are stuck.
     422The view holds enough information to reconstruct the internal state given
     423the current data state: from the data state we can fetch the program counter
     424of the current and the next $n-1$ instructions and, by simulating at most
     425$n$ execution steps and by knowing where the bubbles were, we can fill up
     426the internal state of the pipeline.
     428The assumptions on the lack of influence of operands values on stalls and
     429execution times ensures the existence of the transition function
     430$\hookrightarrow : PC \times \{0,1\}^n \to \{0,1\}^n$ and the data
     431independent cost function $K: PC \times \{0,1\}^n \to \mathbb{N}$.
     433While the model is a bit simplicistic, it can nevertheless be used to describe
     434existing pipelines. It is also simple to be convinced that the same model
     435also captures static branch prediction: speculative execution of conditional
     436jumps is performed by always taking the same branch which does not depend on
     437the execution history. In order to take in account jumpt predictions based on
     438the execution history, we just need to incorporate in the status and the view
     439statistical informations on the last executions of the branch.
     441\paragraph{The labelling appraoch for data independent cost models}
     442We now describe how the labelling approach can be slightly modified to deal
     443with data independent cost models.
Note: See TracChangeset for help on using the changeset viewer.