# Changeset 1860 for Deliverables/D1.2

Ignore:
Timestamp:
Mar 15, 2012, 4:47:54 PM (9 years ago)
Message:

...

Location:
Deliverables/D1.2/Presentations
Files:
2 edited

### Legend:

Unmodified
 r1859 \includegraphics[scale=0.33]{recursive_structure.png} \end{center} Static cost = k($l_1$) + \ldots + k($l_4$) \end{frame} \begin{frame} \frametitle{Recursive structure of good' execution II} \end{frame} \begin{frame} \frametitle{Static and dynamic costs} \begin{center} \includegraphics[scale=0.3]{dynamic_cost.png} \includegraphics[scale=0.33]{recursive_structure.png} \begin{tabular}[b]{ll} & emit(l1) \\ & MOV r1 0\\ & ADD r1 r2\\ & CALL f \\ & ADD r2 r2\\ & MOV r2 0\\ & RET \\ \\ \\ \\ \end{tabular} \end{center} Dynamic cost = \texttt{clock}(Final$_1$) - \texttt{clock}(Start$_1$) \end{frame} \begin{frame} \frametitle{Static and dynamic costs I} \begin{itemize} \item Given a structured trace, we can compute its associated cost \item In previous slide, cost of trace is cost assigned to \texttt{label\_1} + \texttt{label\_2} + \texttt{label\_3} (+ \texttt{label\_4}) \item This is the \emph{static} cost of a program execution \item Similarly, given a program counter and a code memory (corresponding to the trace), we can compute a \emph{dynamic cost} of a simple block \item Do this by repeatedly fetching, obtaining the next instruction, and a new program counter \item This requires some predicates defining what a good program' and what a good program counter' are \item Want program counters on instruction boundaries \end{itemize} \makebox[0pt][l]{k($l_1$) = k(MOV) + k (ADD) + \ldots + k(RET)}\\ Static-cost(trace) = k($l_1$) + \ldots + k($l_4$)\\ Dynamic-cost(trace) = \texttt{clock}(Final$_1$) - \texttt{clock}(Start$_1$)\\ \alert{Theorem: Static-cost(trace) = Dynamic-cost(trace)} \end{frame} \begin{frame} \frametitle{Static and dynamic costs II} \begin{itemize} \item We aim to prove that the dynamic and static cost calculations coincide \item This would imply that the static cost computation is correct \item This proof is surprisingly tricky to complete (about 3 man months of work so far) This proof is surprisingly tricky to complete ($\approx$ 3 man months) \begin{itemize} \item Issues \begin{itemize} \item Finite memory\\ the PC can overflow during fetching and/or execution \item Variable length instructions\\ not all addresses corresponds to instruction boundaries \end{itemize} \item Requires predicates defining good program' and `good program counter' \item Is now about 95\% complete