source: Deliverables/D6.2/supplement.tex @ 2013

Last change on this file since 2013 was 2013, checked in by Ian Stark, 9 years ago

Put in HiPEAC 2013

  • Property svn:eol-style set to native
  • Property svn:mime-type set to text/x-latex
File size: 14.2 KB
1% CerCo: Certified Complexity
3% Supplement to Deliverable 6.2
5% Plan for Dissemination and Use
7% At the end of year 1, this deliverable was rejected by the reviewers and
8% they asked for an addendum, which I wrote shortly after the review.  At the
9% end of year 1, that was itself rejected by the reviewers.  They said:
11% "The reviewers request the resubmission of the addenda to deliverables D2.1
12% and D6.2 within one month from the receipt of this report.
14% ...
16% Deliverable D6.2 does not contain a specific and clear dissemination
17% strategy or plan till the end of the project.  The reviewers request the
18% resubmission of D6.2 detailing an event targeting at the promoting the
19% results of the CerCo project.  It should be planned at least as a half-day
20% event solely presenting the CerCo project.  In order to attract an audience
21% from academia as well as from industry the event should try to focus on case
22% studies for the dependent labelling approach in more modern processor
23% architectures, e.g., as applied in the embedded domain."
25% I'm writing this supplement to D6.2 as our response to this.  At the May
26% 2012 meeting in Bologna we discussed:
28%  - Plans for the CerCo workshop at ETAPS 2013 (later HiPEAC 2013 too)
29%  - Subject areas for papers to be written and submitted
31% Strictly, the reviewers request only mentions the event.  However, if we can
32% make a good job of the paper list, then that would be an advance on the
33% addendum as of last year — and resubmitting the addendum is what was
34% requested. 
36% Ian Stark
37% 2012-05-24
48\vspace*{1cm}Project FP7-ICT-2009-C-243881 {\cerco}}
69Supplement to Deliverable 6.2\\[\jot]
70CerCo Workshop and Publication Planning
77Version 1.0
84Main Authors:\\
85I. Stark
91Project Acronym: {\cerco}\\
92Project full title: Certified Complexity\\
93Proposal/Contract no.: FP7-ICT-2009-C-243881 {\cerco}
95\clearpage\pagestyle{myheadings}\markright{{\cerco}, FP7-ICT-2009-C-243881}
99In March~2012 the second-year review panel for the {\cerco} project requested
100details of specific plans to promote the final results of the project.  This
101document is a response to that, with the following two contributions.
103\item Plans for the {\cerco} workshop at the HiPEAC~'13 meeting in Berlin /
104  the ETAPS~2013 conference in Rome (Deliverables 6.4 and~6.5).
105\item A list of proposed publications reporting {\cerco} results.
107This report supplements the \emph{Plan for the Use and Dissemination of
108  Foreground}, Deliverable~6.2, from August 2010 and addendum \emph{Future
109  Dissemination Plans} of April 2011.
111\section{{\cerco} Workshop}
115We shall hold a {\cerco} one-day workshop for academic and industrial
116researchers.  Our preferred destination is \emph{HiPEAC '13}, to be held in
117Berlin at the end of January~2013.  This is an international meeting on
118high-performance and embedded architectures and compilers, organised by the
119European Network of Excellence in the field, and as such provides an ideal
120audience for {\cerco} results.  The conference workshops for 2013 have not yet
121been selected, but we have submitted our {\cerco} proposal for consideration.
122In case this is not successful, we are also holding an offer of a workshop day
123at ETAPS~2013, the European Joint Conferences on Theory and Practice of
124Software.  This too is a forum for a range of academic and industrial
125researchers, but it takes place in March 2013 and so would only fall within
126the {\cerco} calendar if we obtained an extension to the project.
130The organisers of ETAPS~2013 have accepted a {\cerco} workshop proposal.  The
131ETAPS conferences run for a week during March 2013, in Rome, with workshops
132and tutorials in the adjacent weekends.  {\cerco} will have a full one-day
133workshop as part of this programme.
137This {\cerco} workshop has two objectives:
139\item To publicise the results of {\cerco} to members of the relevant
140  industrial and academic research communities.
141\item To stimulate discussion between the industrial and academic participants
142  about future work building on the current state of the art.
144To support these objectives, we propose to send invitations to a dozen
145industrial and academic research groups working in the field.  While the
146workshop will be open to anyone at HiPEAC who wishes to register, we consider
147an invitational workshop to be the most direct way to bring together {\cerco}
148researchers with potential users of the project results.  A list of invitees
149appears below.
151The workshop, with these objectives, is designed to meet the requirements of
152Deliverables 6.4 and~6.5 as set out in the original {\cerco} proposal (Annex~I
153``Description of Work'', Workplan Table 3, Work package~6).  In particular,
154that proposal envisioned overlapping the presentation of {\cerco} results to
155invited industrial and scientific audiences at an event co-located with an
156international conference.
158We plan the following draft structure for the workshop:
160\item Morning: Short talks by {\cerco} partners presenting the project and its
161  results.
162  \begin{itemize}
163  \item Project overview: a trustworthy framework for cost analysis of
164    embedded code.
165  \item Demonstration of Frama-C plugin: high-level static reasoning about
166    global runtime complexity.
167  \item Demonstration of Lustre plugin: automatic analysis of component
168    reaction time.
169  \item The {\cerco} compiler: what makes a certified compiler trustworthy.
170  \item The labelling approach to cost analysis: a modular way to prove
171    correctness.
172  \item Structured traces: tracking high-level structure in low-level
173    execution.
174  \item Dependent labels: managing refined cost information for richer
175    architectures.
176  \item Future directions: the latest very-low-power embedded processors;
177    other runtime costs; further languages.
178  \end{itemize}
179\item Afternoon: Short presentations by some of the invited participants on the
180  state of the art in static analysis of execution costs for embedded systems.
181\item Conclusion: Round-table discussion on potential applications and future
182  challenges.
184This structure addresses both of the listed objectives, with the morning
185dedicated to dissemination of {\cerco} results and the afternoon to promoting
186interaction between academic and industrial researchers working in the field.
188We have identified the following relevant groups to invite to the {\cerco}
191\item[AbsInt]  AbsInt provide tools for validation of safety-critical
192  software, including static analysis for worst-case execution time through
193  abstract interpretation.  They have participated in a previous {\cerco}
194  event, and their insights into the requirements for precise timing analysis
195  are extremely relevant to the domain of {\cerco}.
196\item[Frama-C]  The \emph{Frama-C} platform for static analysis of C source
197  code provides the context for the {\cerco} plugin which demonstrates the use
198  of automated cost annotations on source code.
199\item[Rapita Systems] The \emph{RapiTime} timing analysis tool for real-time
200  embedded systems uses runtime instrumentation of C to identify source-level
201  execution costs and predict worst-cast execution time.
202\item[PASTA]  This research group at the University of Edinburgh are the
203  designers of the \emph{EnCore} family of configurable embedded
204  microprocessors.  Their \emph{ArcSim} tool offers cycle-accurate simulation
205  of these low-energy cores, giving significant insights into the
206  practicalities of precise cost analysis.
207\item[WCET-Aware Compilation]  Dr Heiko Falk at TU Dortmund leads this
208  research project investigating the optimizations and compilation techniques
209  appropriate to the requirements of worst-case rather than average-case
210  timing.
211\item[Hume/EmBounded]  Prof. Kevin Hammond at the University of St Andrews
212  leads a research team working on the quantification and certification of
213  resource use in concurrent real-time embedded software.
214\item[ARM Verification Project]  Gordon, Fox and Myreen at the University of
215  Cambridge have a machine-checked mathematical model of the ARM
216  microprocessor.  With the release of the ARM Cortex-M series of low-power
217  embedded processors, this is a potential application area for {\cerco}
218  technology in the future.
219\item[CompCertTSO]  Sewell's group, also at the University of Cambridge, have
220  a verified C compiler treating concurrency in a relaxed memory model.  Like
221  {\cerco}, they have relevant experience of extending CompCert-based
222  verification to additional code properties.
223\item[Artemis]  The European industry association \emph{Advanced Research \&
224    Technology for Embedded Intelligence and Systems}.  We already have
225  contact with Artemis through the University of Bologna, which is a member of
226  the association.
227\item[IMDEA Software]  Dr Boris K\"opf applies quantitative analysis of code
228  execution time to evaluate potential security weaknesses by side-channel
229  attacks. 
230\item[ADSIG] The \emph{ArtistDesign Special Interest Group on Embedded Systems
231    Design} is a large consortium of experts in embedded systems design,
232  arising from the ARTIST Network of Excellence.
234We propose to invite each of these groups to send participants and, if they
235wish, contribute a short talk on their work to the afternoon session.
238\section{Publication Planning}
240The original Deliverable~6.2 and its addendum, prepared earlier in the
241project, presented a list of conferences and journals suitable for publicising
242{\cerco} results.  Now that the project has progressed, we have reviewed the
243technical activities to date and identified a specific list of topics which we
244propose as suitable for dissemination in individual papers and articles.
247\item[Labelling] As presented in Deliverable~2.1, the use of labelling to
248  build cost annotations and prove their correctness is key to the {\cerco}
249  development.  It allows decoupling the certification of machine code
250  execution properties from the verification of the compilation map between C
251  source and assembler.
252\item[Dependent labelling] The indexing of labels with additional
253  data-dependent information makes is possible to track sources of variation
254  in execution cost: compiler optimizations such as unrolling or loop peeling;
255  or processor features like instruction pipelining and caches.
256\item[The {\cerco} Frama-C plugin] This was demonstrated at the second-year
257  review panel, and a paper would describe its operation and effect.  The
258  plugin annotates C source code with fine-grained cycle costs according to
259  {\cerco} analysis.  This instrumented code is passed to the \emph{Jessie}
260  plugin which can generate the verification conditions necessary to check the
261  cost specifications of complete procedures.  Finally, these conditions can
262  be passed to a range of automatic proof engines.  The overall result is
263  verified declarations of the cycle execution time of identified C functions,
264  in terms of input and other parameters, given in the ACSL specification
265  language.
266\item[Lustre analysis] This was also demonstrated at the review panel.  The
267  {\cerco} tools can perform automated analysis of response time for
268  individual components in the Lustre synchronous control language.  Lustre
269  automatically generates C source code for concurrent components, in a
270  sufficiently standard form to allow precise costing of execution paths.
271\item[Certifying machine code] {\cerco} extends previous work on compilation
272  by also verifying the final step from assembler to binary object code.  In
273  addition, it is essential to prove that cost annotations exactly capture
274  machine execution steps.  These are both substantial proofs with novel
275  features.
276\item[Correctness of branch selection] Many processors provide a range of
277  branch commands at the machine level, typically for different ranges of
278  jump.  Generating efficient and compact assembly code requires appropriate
279  branch selection.  This is non-trivial --- indeed, finding the optimum
280  selection is in some cases NP-hard --- and the complexity of any algorithm
281  here makes it a challenge for proving correctness.  {\cerco} have developed
282  a novel decomposition of branch selection into policy and implementation, to
283  separate concerns and allow for tractable proof.
284\item[Structured traces] {\cerco} reports execution costs at the level of C
285  source, where there is an evident code structure of nested call and return;
286  but these costs arise from unstructured individual steps at the machine
287  level.  We have developed a notion of structure on machine execution traces
288  which captures precisely the information necessary to correctly relay cost
289  information between these levels.  This is essential to the compiler proof,
290  and interesting in itself as a carrier of high-level information in a
291  low-level execution environment.
292\item[The {\cerco} formalisation] The large-scale structure of the {\cerco}
293  formalisation, its components, how they depend upon each other, and what is
294  required of them to complete the correctness proof.  Some parts of these are
295  related to analogous constructions in work such as CompCert; many are novel
296  and arise from our particular attention to verifying non-functional runtime
297  properties of code.
298\item[A survey of {\cerco} results] All the above papers deal with individual
299  parts of the {\cerco} project, or the technical details of its operation.  A
300  final paper should survey the outcome of the project, its achievements and
301  potential future work to build on these.
306%  LocalWords:  Frama AbsInt Rapita RapiTime EnCore ArcSim WCET Heiko HiPEAC
307%  LocalWords:  Falk EmBounded Myreen CompCertTSO ADSIG ArtistDesign ACSL
Note: See TracBrowser for help on using the repository browser.