Changeset 1860


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

...

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

Legend:

Unmodified
Added
Removed
  • Deliverables/D1.2/Presentations/WP4-dominic.tex

    r1859 r1860  
    475475\includegraphics[scale=0.33]{recursive_structure.png}
    476476\end{center}
    477 Static cost = k($l_1$) + \ldots + k($l_4$)
    478 \end{frame}
    479 
    480 \begin{frame}
    481 \frametitle{Recursive structure of `good' execution II}
     477\end{frame}
     478
     479\begin{frame}
     480\frametitle{Static and dynamic costs}
    482481\begin{center}
    483 \includegraphics[scale=0.3]{dynamic_cost.png}
     482\includegraphics[scale=0.33]{recursive_structure.png}
     483\begin{tabular}[b]{ll}
     484    & emit(l1) \\
     485    & MOV r1 0\\
     486    & ADD r1 r2\\
     487    & CALL f \\
     488    & ADD r2 r2\\
     489    & MOV r2 0\\
     490    & RET \\ \\ \\ \\
     491\end{tabular}
    484492\end{center}
    485 Dynamic cost = \texttt{clock}(Final$_1$) - \texttt{clock}(Start$_1$)
    486 \end{frame}
    487 
    488 \begin{frame}
    489 \frametitle{Static and dynamic costs I}
    490 \begin{itemize}
    491 \item
    492 Given a structured trace, we can compute its associated cost
    493 \item
    494 In previous slide, cost of trace is cost assigned to \texttt{label\_1} + \texttt{label\_2} + \texttt{label\_3} (+ \texttt{label\_4})
    495 \item
    496 This is the \emph{static} cost of a program execution
    497 \item
    498 Similarly, given a program counter and a code memory (corresponding to the trace), we can compute a \emph{dynamic cost} of a simple block
    499 \item
    500 Do this by repeatedly fetching, obtaining the next instruction, and a new program counter
    501 \item
    502 This requires some predicates defining what a `good program' and what a `good program counter' are
    503 \item
    504 Want program counters on instruction boundaries
    505 \end{itemize}
     493\makebox[0pt][l]{k($l_1$) = k(MOV) + k (ADD) + \ldots + k(RET)}\\
     494Static-cost(trace) = k($l_1$) + \ldots + k($l_4$)\\
     495Dynamic-cost(trace) = \texttt{clock}(Final$_1$) - \texttt{clock}(Start$_1$)\\
     496\alert{Theorem: Static-cost(trace) = Dynamic-cost(trace)}
    506497\end{frame}
    507498
    508499\begin{frame}
    509500\frametitle{Static and dynamic costs II}
    510 \begin{itemize}
    511 \item
    512 We aim to prove that the dynamic and static cost calculations coincide
    513 \item
    514 This would imply that the static cost computation is correct
    515 \item
    516 This proof is surprisingly tricky to complete (about 3 man months of work so far)
     501This proof is surprisingly tricky to complete ($\approx$ 3 man months)
     502\begin{itemize}
     503\item Issues
     504 \begin{itemize}
     505  \item Finite memory\\
     506   the PC can overflow during fetching and/or execution
     507  \item Variable length instructions\\
     508    not all addresses corresponds to instruction boundaries
     509 \end{itemize}
     510\item
     511Requires predicates defining `good program' and `good program counter'
    517512\item
    518513Is now about 95\% complete
Note: See TracChangeset for help on using the changeset viewer.