Changeset 3117

Ignore:
Timestamp:
Apr 10, 2013, 6:25:20 PM (5 years ago)
Message:

...

File:
1 edited

Legend:

Unmodified
 r3116 \usepackage{stmaryrd} \usepackage{url} \usepackage{bbm} \title{ 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 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 $(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}