Changeset 3117
 Timestamp:
 Apr 10, 2013, 6:25:20 PM (6 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

Deliverables/D6.3/report.tex
r3116 r3117 12 12 \usepackage{stmaryrd} 13 13 \usepackage{url} 14 \usepackage{bbm} 14 15 15 16 \title{ … … 300 301 obtained from the execution history by forgetting all the remaining information. 301 302 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 302 counter of $\sigma_i$. 303 counter of $\sigma_i$. We denote the set of finite execution paths with $EP$. 303 304 304 305 We claim this simple model to be generic enough to cover real world … … 369 370 370 371 Among the possible views, the ones that we will easily be able to work 371 with in the labelling approach are the \emph{execution pathdependent views}.372 A view $(\mathcal{V},.)$ is execution pathdependent when there exists372 with in the labelling approach are the \emph{execution history dependent views}. 373 A view $(\mathcal{V},.)$ is execution history dependent when there exists 373 374 a transition function $\hookrightarrow : PC \times \mathcal{V} \to \mathcal{V}$ 374 375 such that for all $(\sigma,\delta)$ and $pc$ such that $pc$ is the program … … 376 377 $(pc,\delta) \hookrightarrow \delta'$. 377 378 379 The reference to execution historys in the names is due to the following 380 fact: every execution history dependent transition function $\hookrightarrow$ 381 can be lifted to the type $EP \times \mathcal{V} \to \mathcal{V}$ by folding 382 the 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}$. 385 Moreover, 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''$. 388 378 389 As a final definition, we say that a cost function $K$ is 379 390 \emph{data independent} if it is dependent on a view that is execution path 380 dependent. In t he next paragraphwe will show how we can extend the391 dependent. In two paragraphs we will show how we can extend the 381 392 labelling approach to deal with data independent cost models. 382 393 394 Before that, we show that the class of data independent cost functions 395 is not too restricted to be interesting. In particular, at least simple 396 pipeline models admit data independent cost functions. 397 398 \paragraph{A data independent cost function for simple pipelines} 399 We consider here a simple model for a pipeline with $n$ stages without branch 400 prediction and hazards. We also assume that the actual value of the operands 401 of the instruction that is being read have no influence on stalls (i.e. the 402 creation of bubbles) nor on the execution cost. The type of operands, however, 403 can. For example, reading the value 4 from a register may stall a pipeline 404 if the register has not been written yet, while reading 4 from a different 405 register may not stall the pipeline. 406 407 The internal states $\Delta$ of the pipeline are $n$tuples of decoded 408 instructions or bubbles: 409 $\Delta = (\mathcal{I} \times \Gamma \cup \mathbbm{1})^n$. 410 This representation is not meant to describe the real data structures used 411 in the pipeline: in the implementation the operands are not present in every 412 stage 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 414 the completion of instruction $(I,\gamma)$. The first $n1$ instructions that 415 follow $I$ may already be stored in the pipeline, unless bubbles have delayed 416 one or more of them. 417 418 We introduce the following view over internal states: 419 $(\{0,1\}^n,.)$ where $\mathbb{N}_n = {0,\ldots,2^n1}$ and 420 $(x_1,\ldots,x_n) = (y_1,\ldots,y_n)$ where $y_i$ is 1 iff $x_i$ is a bubble. 421 Thus the view only remembers which stages of the pipelines are stuck. 422 The view holds enough information to reconstruct the internal state given 423 the current data state: from the data state we can fetch the program counter 424 of the current and the next $n1$ instructions and, by simulating at most 425 $n$ execution steps and by knowing where the bubbles were, we can fill up 426 the internal state of the pipeline. 427 428 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}$. 432 433 While the model is a bit simplicistic, it can nevertheless be used to describe 434 existing pipelines. It is also simple to be convinced that the same model 435 also captures static branch prediction: speculative execution of conditional 436 jumps is performed by always taking the same branch which does not depend on 437 the execution history. In order to take in account jumpt predictions based on 438 the execution history, we just need to incorporate in the status and the view 439 statistical informations on the last executions of the branch. 440 441 \paragraph{The labelling appraoch for data independent cost models} 442 We now describe how the labelling approach can be slightly modified to deal 443 with data independent cost models. 383 444 384 445 \end{document}
Note: See TracChangeset
for help on using the changeset viewer.