root/Deliverables/addenda/letter.tex @ 803

% CerCo: Certified Complexity
%
% Addendum to Deliverable 6.2
%
% Plan for Dissemination and Use
% Addendum requested by project reviewers at end of year 1.
%
% Ian Stark
% 2011-05

\documentclass[11pt,a4paper]{article}
\usepackage{../style/cerco}

\hypersetup{bookmarksopenlevel=2}

\title{
INFORMATION AND COMMUNICATION TECHNOLOGIES\\
(ICT)\\
PROGRAMME\\
\vspace*{1cm}Project FP7-ICT-2009-C-243881 {\cerco}}

\date{ }
\author{}

\begin{document}
\thispagestyle{empty}

\vspace*{-1cm}
\begin{center}
\includegraphics[width=0.6\textwidth]{../style/cerco_logo.png}
\end{center}

\begin{minipage}{\textwidth}
\maketitle
\end{minipage}


\vspace*{0.5cm}
\begin{center}
\begin{LARGE}
\bf
Commitment to the Consideration of Reviewer's Reccomendations
\end{LARGE} 
\end{center}

\vspace*{2cm}
\begin{center}
\begin{large}
%Version 1.0
\end{large}
\end{center}

\vspace*{0.5cm}
\begin{center}
\begin{large}
%Main Authors:\\
%I. Stark
\end{large}
\end{center}

\vspace*{\fill}
\noindent
Project Acronym: {\cerco}\\
Project full title: Certified Complexity\\
Proposal/Contract no.: FP7-ICT-2009-C-243881 {\cerco}\\

\clearpage \pagestyle{myheadings} \markright{{\cerco}, FP7-ICT-2009-C-243881}

\tableofcontents

%\section{Premise}
The first Scientific Review Report contains several valuable comments and
recommendations by the scientific reviewers. We discuss here the three
main recommendations, committing ourselves to taking them in account during the
next project period.

\begin{enumerate}
\item The reviewers are worried by the possible limitations that derive from
 the choice of a very old architecture layout. They recommend we adopt a
 modified form of labelling such that basic complexity annotations can be
 obtained from program pieces of larger granularity.

 We will investigate this issue. In particular, the integration of some WCET
 techniques seem feasible. For instance, let us consider the use of
 a simple abstract interpretation technique to improve the accuracy of WCET in
 the presence of caches. The analysis performed on loops, associates to each memory
 access an abstract value in a three valued domain, consisting of cache-hits,
 cache misses and unknown cache behaviour. With this valuable information, we
 can assign a different cost to each single instruction: while the analysis
 is done on a large chunk of code, the cost is finally associated with single
 instructions, as in our approach. Since our approach is totally parametric
 in the function that assigns costs to target instructions, nothing needs
 to be changed in this simple case.

 Realistic tools, however, also use a bound
 on the number of loop iterations to augment precision of the analysis.
 Moreover, they assign different costs to the first iteration of a loop and to
 successive ones. In these cases, the problem posed with our approach consists
 of formally verifying that bounds specified by the user (or automatically
 inferred by some invariant generator) on the source code are preserved in the
 target code. We believe that the labelling technique we have adopted should
 allow us to also accomodate these invariants. In the following project
 period we will perform a theoretical investigation of this issue and we will
 evaluate the feasibility of the implementation of a prototype.

\item The reviewers suggest to quickly outline pencil-and-paper correctness
 proofs for each of the seven stages of the compiler in order to establish an
 estimation for the complexity of completing the formalisation, and time required
 to do so.

 We plan to depart from CompCert when carrying out our proof since we want to
 experiment different proof strategies where possible. In particular, we will
 try to exploit dependent types in our formalisation, as dependent types were
 avoided as a design principle in CompCert. For this reason, we have already
 started to formalise in Matita the intermediate languages of our compiler,
 recording invariants in the types themselves and rearranging some code.
 This should be completed at month 18. At this point we will be able to
 correctly state the intermediate proof statements and to estimate the
 complexity and effort needed for the formalisation.

\item The reviewers suggest we use this estimation to compare two possible
 scenarios: a) proceed as planned, porting all CompCert proofs to Matita or
 b) port D3.1 and D4.1 to Coq and re-use the CompCert proofs.



\end{enumerate}

\end{document}

% LocalWords:  Sacerdoti Coen microcontroller FMCAD VSTTE TPHOLs LPAR Artefacts