Changeset 3114
 Timestamp:
 Apr 10, 2013, 9:48:31 AM (9 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

Deliverables/D6.3/report.tex
r3113 r3114 200 200 comparisons on the kind of code used by industry in production systems. 201 201 The first middle term improvement of CerCo would then consist in this kind 202 of analysis, to support or disprove our expectations. In the case where our 202 of analysis, to support or disprove our expectations. It seems that the 203 newborn TACLe Cost Action (Timing Analysis on Code Level) would be the 204 best framework to achieve this improvement. 205 In the case where our 203 206 technique remains promising, the next long term improvement would consist in 204 207 integrating in the FramaC plugin adhoc analysis and combinations of analysis … … 206 209 techniques. 207 210 208 \subsection{Static analysis of basic blocks} 211 \subsection{Static analysis of costs of basic blocks} 212 At the beginning of the project we have deliberately decided to focus our 213 attention on the control flow preservation, the cost model propagation and 214 the exploitation of the cost model induced on the high level code. For this 215 reason we have devoted almost no attention to the static analysis of basic 216 blocks. This was achieved by picking a very simple hardware architecture 217 (the 8051 microprocessor family) whose cost model is fully predictable and 218 compositional: the cost of every instruction  except those that deal with 219 I/O  is constant, i.e. it does not depend on the machine status. 220 We do not regret this choice because, with the limited amount of man power 221 available in the project, it would have been difficult to also consider this 222 aspect. However, without showing if the approach can scale to most complex 223 architectures, our methodology remains of limited interest for the industry. 224 Therefore, the next important middle term improvement will be the extension 225 of our methodology to cover pipelines and simple caches. We will now present our 226 ideas on how we intend to address the problem. The obvious long term 227 improvement would be to take in consideration multicores system and complex 228 memory architectures like the ones currently in use in networks on chips. 229 The problem of execution time analysis for these systems is currently 230 considered extremely hard or even unfeasible and at the moments it seems 231 unlikely that our methodology could contribute to the solution of the problem. 232 233 \subsubsection{Static analysis of costs of basic blocks revisited} 234 We will now describe what currently seems to be the most interesting technique 235 for the static analysis of the cost of basic blocks in presence of complex 236 hardware architectures that do not have non compositional cost models. 237 238 We start presenting an idealized model of the execution of a generic 239 microprocessor (with caches) that has all interrupts disabled and no I/O 240 instructions. 241 242 Let $\sigma,\sigma_1,\ldots$ range over $\Sigma$, the set of the fragments of 243 the microprocessor states that hold the program counter, the program status word and 244 all the data manipulated by the object code program, i.e. registers and 245 memory cells. We call these fragments the \emph{data states}. 246 247 Let $\delta,\delta_1,\ldots$ range over $\Delta$, the set of the 248 fragments of the microprocessor state that holds the internal state of the 249 microprocessor (e.g. the content of the pipeline and caches, the status of 250 the branch prediction unit, etc.). 251 The internal state of the microprocessor influences the execution cost of the 252 next instruction, but it has no effect on the functional behaviour of the 253 processor. The whole state of the processor is represented by a pair 254 $(\sigma,\delta)$. 255 256 Let $I,I_1,\ldots$ range over $\mathcal{I}$, the 257 the set of instructions of the processor and let 258 $\gamma,\gamma_1,\ldots$ range over $\Gamma$, the set of operands 259 of instructions after the fetching and decoding passes. 260 Thus a pair $(I,\gamma)$ represents a decoded instruction and already contains 261 the data required for execution. Execution needs to access the data state only 262 to write the result. 263 264 Let $fetch: \Sigma \to \mathcal{I} \times \Gamma$ be the function that 265 performs the fetching and execution phases, returning the decoded instruction 266 ready for execution. This is not meant to be the real fetchdecode function, 267 that exploits the internal state too to speed up execution (e.g. by retrieving 268 the instruction arguments from caches) and that, in case of pipelines, works 269 in several stages. However, such a function exists and 270 it is observationally equivalent to the real fetchdecode. 271 272 We capture the semantics of the microprocessor with the following set of 273 functions: 274 \begin{itemize} 275 \item The functional transition function $\longleftarrow : \Sigma \to \Sigma$ 276 over data states. This is the only part of the semantics that is relevant 277 to functional analysis. 278 \item The internal state transition function 279 $\Longleftarrow : \Sigma \times \Delta \to \Delta$ that updates the internal 280 state. 281 \item The cost function $K: \mathcal{I} \times \Delta \to \mathbb{N}$ that 282 assigns a cost to transitions. Since decoded instructions hold the data 283 they act on, the cost of an instruction may depend both on the data being 284 manipulated and on the internal state. 285 \end{itemize} 286 287 Given a processor state $(\sigma,\delta)$, the processor evoltes in the 288 new state $(\sigma',\delta')$ in $n$ cost units if 289 $\sigma \longleftarrow \sigma'$ and $(\sigma,\delta) \Longleftarrow \sigma'$ 290 and $fetch(\sigma) = (I,\gamma)$ and $K(I,\gamma,\delta) = n$. 291 292 We claim this simple model to be generic enough to cover real world 293 architectures. 294 295 209 296 210 297 \end{document}
Note: See TracChangeset
for help on using the changeset viewer.