Changeset 3117

Timestamp:

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

Author:

sacerdot

Message:

...

File:

• Deliverables/D6.3/report.tex (modified) (4 diffs)

Deliverables/D6.3/report.tex

@@ -12 +12 @@
 \usepackage{stmaryrd}
 \usepackage{url}
+\usepackage{bbm}
 
 \title{
@@ -300 +301 @@
 obtained from the execution history by forgetting all the remaining information.
 The 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
-counter of $\sigma_i$.
+counter of $\sigma_i$. We denote the set of finite execution paths with $EP$.
 
 We claim this simple model to be generic enough to cover real world
@@ -369 +370 @@
 
 Among the possible views, the ones that we will easily be able to work
-with in the labelling approach are the \emph{execution path dependent views}.
-A view $(\mathcal{V},|.|)$ is execution path dependent when there exists
+with in the labelling approach are the \emph{execution history dependent views}.
+A view $(\mathcal{V},|.|)$ is execution history dependent when there exists
 a transition function $\hookrightarrow : PC \times \mathcal{V} \to \mathcal{V}$
 such that for all $(\sigma,\delta)$ and $pc$ such that $pc$ is the program
@@ -376 +377 @@
 $(pc,|\delta|) \hookrightarrow |\delta'|$.
 
+The reference to execution historys in the names is due to the following
+fact: every execution history dependent transition function $\hookrightarrow$
+can be lifted to the type $EP \times \mathcal{V} \to \mathcal{V}$ by folding
+the definition over the path trace:
+$((pc_0,\ldots,pc_n),v_0) \hookrightarrow v_{n+1}$ iff for all $i \leq n$,
+$(pc_i,v_i) \hookrightarrow v_{i+1}$.
+Moreover, the folding is clearly associative:
+$(\tau_1 @ \tau_2, v) \hookrightarrow v''$ iff
+$(\tau_1,v) \hookrightarrow v'$ and $(\tau_2,v') \hookrightarrow v''$.
+
 As a final definition, we say that a cost function $K$ is
 \emph{data independent} if it is dependent on a view that is execution path
-dependent. In the next paragraph we will show how we can extend the
+dependent. In two paragraphs we will show how we can extend the
 labelling approach to deal with data independent cost models.
 
+Before that, we show that the class of data independent cost functions
+is not too restricted to be interesting. In particular, at least simple
+pipeline models admit data independent cost functions.
+
+\paragraph{A data independent cost function for simple pipelines}
+We consider here a simple model for a pipeline with $n$ stages without branch
+prediction and hazards. We also assume that the actual value of the operands
+of the instruction that is being read have no influence on stalls (i.e. the
+creation of bubbles) nor on the execution cost. The type of operands, however,
+can. For example, reading the value 4 from a register may stall a pipeline
+if the register has not been written yet, while reading 4 from a different
+register may not stall the pipeline.
+
+The internal states $\Delta$ of the pipeline are $n$-tuples of decoded
+instructions or bubbles:
+$\Delta = (\mathcal{I} \times \Gamma \cup \mathbbm{1})^n$.
+This representation is not meant to describe the real data structures used
+in the pipeline: in the implementation the operands are not present in every
+stage of the pipeline, but are progressively fetched. A state
+$(x_1,x_2,\ldots,(I,\gamma))$ represents the state of the pipeline just before
+the completion of instruction $(I,\gamma)$. The first $n-1$ instructions that
+follow $I$ may already be stored in the pipeline, unless bubbles have delayed
+one or more of them.
+
+We introduce the following view over internal states:
+$(\{0,1\}^n,|.|)$ where $\mathbb{N}_n = {0,\ldots,2^n-1}$ and
+$|(x_1,\ldots,x_n)| = (y_1,\ldots,y_n)$ where $y_i$ is 1 iff $x_i$ is a bubble.
+Thus the view only remembers which stages of the pipelines are stuck.
+The view holds enough information to reconstruct the internal state given
+the current data state: from the data state we can fetch the program counter
+of the current and the next $n-1$ instructions and, by simulating at most
+$n$ execution steps and by knowing where the bubbles were, we can fill up
+the internal state of the pipeline.
+
+The assumptions on the lack of influence of operands values on stalls and
+execution times ensures the existence of the transition function
+$\hookrightarrow : PC \times \{0,1\}^n \to \{0,1\}^n$ and the data
+independent cost function $K: PC \times \{0,1\}^n \to \mathbb{N}$.
+
+While the model is a bit simplicistic, it can nevertheless be used to describe
+existing pipelines. It is also simple to be convinced that the same model
+also captures static branch prediction: speculative execution of conditional
+jumps is performed by always taking the same branch which does not depend on
+the execution history. In order to take in account jumpt predictions based on
+the execution history, we just need to incorporate in the status and the view
+statistical informations on the last executions of the branch.
+
+\paragraph{The labelling appraoch for data independent cost models}
+We now describe how the labelling approach can be slightly modified to deal
+with data independent cost models. 
 
 \end{document}