Annotation of res/PP-compiler.tex, revision 1.2
1.1 andi 1: \documentclass[11pt,a4paper]{article}
2: %\usepackage{latexsym}
3: \usepackage{url}
4: %\usepackage{times}
5: \usepackage{comment}
6:
7: \pagestyle{plain}
8: \setlength{\textwidth}{16truecm}
9: \setlength{\textheight}{24truecm}
10: \setlength{\oddsidemargin}{-0.3truecm}
11: \setlength{\evensidemargin}{-0.3truecm}
12: \setlength{\topmargin}{0.0truecm}
13: \setlength{\topskip}{0.0truecm}
14: \setlength{\headheight}{0.0truecm}
15: \setlength{\headsep}{0.0truecm}
16:
17: \newcommand{\emn}[1]{{\em #1\/}}
18: \newcommand{\NOTE}[1]{{\medskip\bf #1\medskip}}
19:
20: \title{\bf PP \emph{Compilation Techniques for Robust Embedded Systems}}
21:
22: \author{{\sc Ulrich Schmid}\\
23: s@ecs.tuwien.ac.at
24: }
25:
26: \bibliographystyle{unsrt}
27:
28: \begin{document}
29: \maketitle
30:
1.2 ! andi 31: PP leader: \emph{Jens Knoop and Andreas Krall}
1.1 andi 32:
1.2 ! andi 33: Associated researchers: \emph{}
1.1 andi 34:
35:
36:
37: \subsubsection*{Motivation:}
38: %\emph{Informal description of the purpose of the PP (3-5 lines)}
39: Every embedded system consists of software which is written in a high
40: level language, compiled to machine language and executed on a
41: processor. For robust embedded systems new verified compilation
42: techniques are necessary to optimize for performance, power, space,
43: concurrency and reliability.
44:
45: \subsubsection*{State of the art and related work:}
46: %\emph{Briefly describe the scientific state of the art (20-30 lines)}
47:
1.2 ! andi 48: %Compilation Techniques for Reliability
! 49:
! 50: Because of the exponential increase of the number of transistors and
! 51: the continuing decrease of the feature sizes of current processors
! 52: soft errors mainly caused by energetic particles are becoming an
! 53: important design issue for robust embedded systems. Blome et
! 54: al.~\cite{Blome+06} observed that a majority of faults that affect the
! 55: architectural state of a processor come from the register file. Lee
! 56: and Shrivastava and proposed different solutions to cope with this
! 57: problem. The first assigns variables depending on their lifetime to
! 58: either the ECC protected or the unprotected part of a register file to
! 59: balance energy consumption and reliability \cite{LeeShrivastava09a}.
! 60: The second spills registers to ECC protected memory if the register
! 61: contents are not used for a long period \cite{LeeShrivastava09c}.
1.1 andi 62:
1.2 ! andi 63: %ADL and Instruction Set Simulators \cite{MishraDutt08}
1.1 andi 64:
1.2 ! andi 65: Compiler Verification \cite{Hoare,1328444,1314860}
1.1 andi 66:
67: WCET \cite{}
68:
69: \subsubsection*{Previous achievements:}
70: %\emph{Brief description of your own contributions to the related
71: %scientific state-of-the art (5-10 lines)}
72: Jens Knoop has a long history on work on program analysis with topics
73: like partial redundancy elimination or lazy code motion
74: \cite{knoop:DSP:2008:1575,conf/cc/XueK06,scholz04}. Recently he
75: changed his research focus on worst case execution time analysis
76: \cite{SchrSchoKn09,Prantl:WLPE2008,prantl_et_al:DSP:2008:1661,
77: kirner_et_al:DSP:2008:1657,kirner_et_al:DSP:2007:1197}. He is involved
78: in the organization of many compiler conferences and since 2002 program
79: cochair of the yearly workshop on compiler optimization meets verification.
80:
81: Andreas Krall does research in the area of architecture description
82: languages and the automatic generation of highly optimizing compilers,
83: efficient instruction set simulators and hardware from one single
84: specification of a processor \cite{BrFeKrRi09,BrEbKr07,FaKrHo07,
85: FarKrStBrand06,Krall+04micro}. An important focus is on optimization
86: techniques for embedded processors
87: \cite{EbBrSchKrWiKa08,MeKr07,PrKrHo06,HiKr03} as he lead the Christian
88: Doppler research laboratory {\em compilation techniques for embedded
89: processors} with partners from industry (Infineon, OnDemand
90: Microelectronics).
91:
92:
93: \subsubsection*{Goals (first 4 years):}
94: %\emph{Description of the research
95: %topics to be addressed during the first 4 years. Make sure to explicitly
96: %stress what the significant additions to the scientific knowledge are,
97: %and why they are important. (30-40 lines)}
98:
99: New modeling and representation techniques of non-functional program and system properties on the programming and intermediate language levels
100: Definitions and measures of non-functional program and system properties (performance, time, space/memory, power, concurrency).
101: Modeling and representation of these properties alongside with the programming languages semantics
102: Adapting and enhancing state-of-the-art compilation techniques towards non-functional property and platform awareness
103: New functional and non-functional property and platform-aware compilation techniques
104: Analyses for non-functional program and system properties
105: Functional and non-functional property and platform-aware code generation techniques
106: Enabling validation and verification throughout the compilation process
107: Techniques for reducing or eliminating trusted code, annotation, etc., bases
108:
109:
110: \subsubsection*{Work Plan (first 4 years):}
111: %\emph{Brief description of how
112: %you intend to conduct the actual research during the first 4 years. Be sure
113: %to also describe and (coarsely) quantify the resources (staff, cost of
114: %special equipment) required for this work in a table. (20-30 lines)}
115:
116:
117:
1.2 ! andi 118: (1) Specification and efficient simulation of reliable processors (partial redundancy,
1.1 andi 119: ECC, lockstep etc) and compiler optimizations to exploit/balance reliabiliy features.
1.2 ! andi 120: Connection with CESAR NN1
1.1 andi 121:
1.2 ! andi 122: (2) translation verification, specification of semantics of IRs solving
1.1 andi 123: subproblems. NN1 + NN2
124:
1.2 ! andi 125: (3) WCET NN3
! 126:
1.1 andi 127:
128: \begin{tabular}{llll}
129: \hline
1.2 ! andi 130: {\bf Pos} & {\bf Type} & {\bf Description} & {\bf Duration} \\
! 131: NN1 & PhD & reliable compilation / simulation & 4 years \\
! 132: NN2 & PhD & compiler verificationi & 4 years \\
! 133: NN3 & PhD & WCET & 4 years \\
1.1 andi 134: \hline
135: \end{tabular}
136:
137:
138: \subsubsection*{Goals (last 4 years):}
139: %\emph{Brief description of the
140: %eesearch topics to be addressed during the last 4 years. Make sure to
141: %explicitly stress what the significant additions to the scientific
142: %knowledge are, and why they are important. (20-30 lines)}
143:
144: New programming languages and compilers for RESs
145: Non-functional properties and requirements as first-class language and compiler citizens
146: New compilation techniques enabling a uniform and integrated approach
147: for ensuring functional and non-functional program and system requirements
148: Replacing trust by proof
149: Certifying compilation, proof-carrying code, translation validation
150: Verified compilers, verifying compilation for RESs
151: Making legacy applications fit to and available on RESs
152: Techniques for adjusting and decompiling legacy applications
153:
154: \subsubsection*{Collaboration with other PPs:}
155: %\emph{List the PPs you are expecting to collaborate with, and describe briefly
156: %the topic and nature of such a collaboration. (10-20 lines)}
157:
158: \begin{itemize}
159: \item PP Composition of Non-functional Requirements [I.S.T.A./Henzinger]:
160: Links to specification and modeling of timing properties, to execution
161: models, hardware and software models.
162: \item PP Composition and Predictability in RES Architectures
163: [E182/Puschner]: Links to hard- and software models for time
164: predictable systems, verification of timing behaviour.
165: \item PP Formal Verification for Robustness [E184/Veith]: Links to software
166: model checking and testing of code (on source code and intermediate
167: code levels), support for program analysis and transformation.
168: \item PP Modeling \& Analysis of Robust Distributed Systems [E182/Schmid]:
169: Links to functional and non-functional system requirements,
170: distribution, concurrency.
171: \end{itemize}
172:
173: \subsubsection*{External Collaborations:}
174: %\emph{List envisioned international and national collaborations, and
175: %describe briefly the topic and nature of such a collaboration. (5-10
176: %lines)}
177:
1.2 ! andi 178: Aviral Shrivastava, Arizona State University, Tempe, AZ, USA
! 179:
! 180: Wolf Zimmermann, Universit\"at Halle, Halle, Germany
1.1 andi 181:
182: \begin{comment}
183: %Bitte hier die Bibtex-Entries einfuellen, z.B.,
184:
185:
186: ------------------------------------
187:
188: @article{Hoare,
189: author = {Tony Hoare},
190: title = {The verifying compiler: A grand challenge for computing research},
191: journal = {Journal of the ACM},
192: volume = {50},
193: number = {1},
194: year = {2003},
195: issn = {0004-5411},
196: pages = {63--69},
197: doi = {http://doi.acm.org/10.1145/602382.602403},
198: publisher = {ACM},
199: address = {New York, NY, USA},
200: }
201:
202: @article{1328444,
203: author = {Jean-Baptiste Tristan and Xavier Leroy},
204: title = {Formal verification of translation validators: a case study on instruction scheduling optimizations},
205: journal = {SIGPLAN Not.},
206: volume = {43},
207: number = {1},
208: year = {2008},
209: issn = {0362-1340},
210: pages = {17--27},
211: doi = {http://doi.acm.org/10.1145/1328897.1328444},
212: publisher = {ACM},
213: address = {New York, NY, USA},
214: }
215:
216: @article{1314860,
217: author = {Jan Olaf Blech and Arnd Poetzsch-Heffter},
218: title = {A Certifying Code Generation Phase},
219: journal = {Electron. Notes Theor. Comput. Sci.},
220: volume = {190},
221: number = {4},
222: year = {2007},
223: issn = {1571-0661},
224: pages = {65--82},
225: doi = {http://dx.doi.org/10.1016/j.entcs.2007.09.008},
226: publisher = {Elsevier Science Publishers B. V.},
227: address = {Amsterdam, The Netherlands, The Netherlands},
228: }
229:
230: @INPROCEEDINGS{LeeShrivastava09,
231: TITLE = {A Compiler Optimization to Reduce Soft Errors in Register Files},
232: AUTHOR = {Jongeun Lee and Aviral Shrivastava},
233: BOOKTITLE = {ACM SIGPLAN/SIGBED Conference on Languages, Compilers, and Tools for Embedded Systems},
234: EDITOR = {Mahmut Kandemir},
235: PUBLISHER = {ACM},
236: PAGES = {??--??},
237: ADDRESS = {Dublin},
238: MONTH = {June},
239: YEAR = {2009},
240: }
241:
242: @BOOK{MishraDutt08,
243: TITLE = {Processor Description Languages},
244: AUTHOR = {Prabhat Mishra and Nikil Dutt (Editor)},
245: PUBLISHER = {Morgan Kaufmann},
246: YEAR = {2008},
247: }
248:
249:
250:
251: %Eigene Referenzen ab hier.
252:
253: @InProceedings{SchrSchoKn09,
254: TITLE = "Adding Timing-Awareness to {AUTOSAR} Basic-Software - A Component Based Approach",
255: AUTHOR = "Dietmar Schreiner and Markus Schordan and Jens Knoop",
256: BOOKTITLE = "12th IEEE International Symposium on Object/component/service-oriented
257: Real-time distributed Computing (ISORC 2009)",
258: PUBLISHER = "IEEE",
259: ADDRESS = "Tokyo, Japan",
260: YEAR = "2009",
261: MONTH = "March",
262: PAGES = "288--292",
263: }
264:
265: @inproceedings{Prantl:WLPE2008,
266: Address = {Udine, Italy},
267: Author = {Adrian Prantl and Jens Knoop and Markus Schordan and Markus Triska},
268: Booktitle = {The 18th Workshop on Logic-based methods in Programming Environments (WLPE 2008)},
269: Month = {December 12},
270: Title = {Constraint solving for high-level WCET analysis},
271: Year = {2008},
272: URL = {http://costa.tuwien.ac.at/papers/wlpe08.pdf}
273: }
274:
275: @InProceedings{prantl_et_al:DSP:2008:1661,
276: author = "Adrian Prantl and Markus Schordan and Jens Knoop",
277: title = "TuBound - {A} Conceptually New Tool for Worst-Case
278: Execution Time Analysis",
279: booktitle = "8th Intl. Workshop on Worst-Case Execution Time (WCET)
280: Analysis",
281: year = "2008",
282: editor = "Raimund Kirner",
283: publisher = "Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik,
284: Germany",
285: address = "Dagstuhl, Germany",
286: URL = "http://drops.dagstuhl.de/opus/volltexte/2008/1661",
287: annote = "Keywords: Worst-case execution time (WCET) analysis,
288: Tool Chain, Flow Constraints, Source-To-Source",
289: ISBN = "978-3-939897-10-1",
290: note = "also published in print by Austrian Computer Society
291: (OCG) under ISBN 978-3-85403-237-3",
292: }
293:
294: @InProceedings{kirner_et_al:DSP:2008:1657,
295: author = "Raimund Kirner and Albrecht Kadlec and Adrian Prantl
296: and Markus Schordan and Jens Knoop",
297: title = "Towards a Common {WCET} Annotation Language: Essential
298: Ingredients",
299: booktitle = "8th Intl. Workshop on Worst-Case Execution Time (WCET)
300: Analysis",
301: year = "2008",
302: editor = "Raimund Kirner",
303: publisher = "Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik,
304: Germany",
305: address = "Dagstuhl, Germany",
306: URL = "http://drops.dagstuhl.de/opus/volltexte/2008/1657",
307: annote = "Keywords: Worst-case execution time (WCET) analysis,
308: annotation languages, WCET annotation language
309: challenge",
310: ISBN = "978-3-939897-10-1",
311: note = "also published in print by Austrian Computer Society
312: (OCG) under ISBN 978-3-85403-237-3",
313: }
314:
315: @InProceedings{kirner_et_al:DSP:2007:1197,
316: author = "Raimund Kirner and Jens Knoop and Adrian Prantl and
317: Markus Schordan and Ingomar Wenzel",
318: title = "{WCET} Analysis: The Annotation Language Challenge",
319: booktitle = "7th Intl. Workshop on Worst-Case Execution Time (WCET)
320: Analysis",
321: year = "2007",
322: editor = "Christine Rochange",
323: publisher = "Internationales Begegnungs- und Forschungszentrum
324: f{"u}r Informatik (IBFI), Schloss Dagstuhl, Germany",
325: address = "Dagstuhl, Germany",
326: URL = "http://drops.dagstuhl.de/opus/volltexte/2007/1197",
327: annote = "Keywords: Worst-case execution time analysis, WCET,
328: path description, annotation language challenge,
329: expressiveness, convenience",
330: }
331:
332:
333: @InProceedings{knoop:DSP:2008:1575,
334: author = {Jens Knoop},
335: title = {Data-Flow Analysis for Multi-Core Computing Systems: A Reminder to Reverse Data-Flow Analysis},
336: booktitle = {Scalable Program Analysis},
337: year = {2008},
338: editor = {Florian Martin and Hanne Riis Nielson and Claudio Riva and Markus Schordan},
339: number = {08161},
340: series = {Dagstuhl Seminar Proceedings},
341: ISSN = {1862-4405},
342: publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany},
343: address = {Dagstuhl, Germany},
344: URL = {http://drops.dagstuhl.de/opus/volltexte/2008/1575},
345: annote = {Keywords: Multi-core computing systems, scalable program analysis, reverse data-flow analysis, demand-driven data-flow analysis}
346: }
347:
348: @InProceedings{conf/cc/XueK06,
349: title = "A Fresh Look at {PRE} as a Maximum Flow Problem",
350: author = "Jingling Xue and Jens Knoop",
351: bibdate = "2006-04-05",
352: bibsource = "DBLP,
353: http://dblp.uni-trier.de/db/conf/cc/cc2006.html#XueK06",
354: booktitle = "CC",
355: booktitle = "Compiler Construction, 15th International Conference,
356: {CC} 2006, Held as Part of the Joint European
357: Conferences on Theory and Practice of Software, {ETAPS}
358: 2006, Vienna, Austria, March 30-31, 2006, Proceedings",
359: publisher = "Springer",
360: year = "2006",
361: volume = "3923",
362: editor = "Alan Mycroft and Andreas Zeller",
363: ISBN = "3-540-33050-X",
364: pages = "139--154",
365: series = "Lecture Notes in Computer Science",
366: URL = "http://dx.doi.org/10.1007/11688839_13",
367: }
368:
369: @InProceedings{scholz04,
370: author = "Bernhard Scholz and Nigel Horspool and Jens Knoop",
371: title = "Optimizing for space and time usage with speculative
372: partial redundancy elimination",
373: booktitle = "LCTES '04: Proceedings of the 2004 ACM SIGPLAN/SIGBED
374: conference on Languages, Compilers, and Tools for Embedded Systems",
375: year = "2004",
376: ISBN = "1-58113-806-7",
377: pages = "221--230",
378: location = "Washington, DC, USA",
379: publisher = "ACM Press",
380: }
381:
382: @InProceedings{HiKr03,
383: TITLE = "{VLIW} Operation Refinement for Reducing Energy Consumption",
384: AUTHOR = "Ulrich Hirnschrott and Andreas Krall",
385: BOOKTITLE = "International Symposium on System-on Chip",
386: PUBLISHER = "IEEE",
387: ADDRESS = "Tampere, Finland",
388: YEAR = "2003",
389: PAGES = "131--134",
390: }
391:
392: @Article{Krall+04micro,
393: author = {Andreas Krall and Ulrich Hirnschrott and Christian Panis and Ivan Pryanishnikov},
394: title = {x{DSP}core: {A} {C}ompiler-{B}ased {C}onfigureable {D}igital {S}ignal {P}rocessor},
395: journal = {IEEE Micro},
396: year = {2004},
397: OPTkey = {},
398: volume = {24},
399: number = {4},
400: pages = {67-78},
401: month = {July/August},
402: OPTnote = {},
403: OPTannote = {},
404: }
405:
406: @INPROCEEDINGS{FarKrStBrand06,
407: TITLE = {Effective Compiler Generation by Architecture Description},
408: AUTHOR = {Stefan Farfeleder and Andreas Krall and Edwin Steiner and Florian Brandner},
409: BOOKTITLE = {ACM SIGPLAN/SIGBED Conference on Languages, Compilers, and Tools for Embedded Systems},
410: EDITOR = {Koen De Bosschere},
411: PUBLISHER = {ACM},
412: PAGES = {145--152},
413: ADDRESS = {Ottawa},
414: MONTH = {June},
415: YEAR = {2006},
416: URL = {http://doi.acm.org/10.1145/1134650.1134671},
417: }
418:
419: @ARTICLE{PrKrHo06,
420: AUTHOR = {Ivan Pryanishnikov and Andreas Krall and Nigel Horspool},
421: TITLE = {Compiler Optimizations for Processors with {SIMD} Instructions},
422: JOURNAL = {Software---Practice and Experience},
423: PUBLISHER = {Wiley},
424: VOLUME = {37},
425: NUMBER = {1},
426: PAGES = {93--113},
427: YEAR = {2007},
428: URL = {http://www3.interscience.wiley.com/cgi-bin/fulltext/112783581/PDFSTART},
429: }
430:
431: @ARTICLE{FaKrHo07,
432: AUTHOR = {Stefan Farfeleder and Andreas Krall and Nigel Horspool},
433: TITLE = {Ultra Fast Cycle-Accurate Compiled Emulation of Inorder Pipelined Architectures},
434: JOURNAL = {Journal of Systems Architecture},
435: PUBLISHER = {Elsevier},
436: VOLUME = {53},
437: NUMBER = {8},
438: PAGES = {501--510},
439: YEAR = {2007},
440: }
441:
442: @INPROCEEDINGS{MeKr07,
443: TITLE = {Instruction Set Encoding Optimization for Code Size Reduction},
444: AUTHOR = {Michael Med and Andreas Krall},
445: BOOKTITLE = {International Conference on Embedded Computer Systems: Architectures, Modeling, and Simulation},
446: ADDRESS = {Samos, Greece},
447: PAGES = {9--17},
448: MONTH = {July},
449: YEAR = {2007}
450: }
451:
452: @INPROCEEDINGS{BrEbKr07,
453: TITLE = {Compiler Generation from Structural Architecture Descriptions},
454: AUTHOR = {Florian Brandner and Dietmar Ebner and Andreas Krall},
455: BOOKTITLE = {International Conference on Compilers, Architecture, and Synthesis for Embedded Systems},
456: ADDRESS = {Salzburg, Austria},
457: PAGES = {13--22},
458: MONTH = {September},
459: YEAR = {2007}
460: }
461:
462: @INPROCEEDINGS{EbBrSchKrWiKa08,
463: TITLE = {Generalized Instruction Selection using {SSA}-Graphs},
464: AUTHOR = {Dietmar Ebner and Florian Brandner and Bernhard Scholz and Andreas Krall and Peter Wiedermann and Albrecht Kadlec},
465: BOOKTITLE = {ACM SIGPLAN/SIGBED Conference on Languages, Compilers, and Tools for Embedded Systems},
466: EDITOR = {John Regehr},
467: PUBLISHER = {ACM},
468: PAGES = {31--40},
469: ADDRESS = {Tucson},
470: MONTH = {June},
471: YEAR = {2008},
472: }
473:
474: @INPROCEEDINGS{BrFeKrRi09,
475: TITLE = {Fast and Accurate Simulation using the LLVM Compiler Framework},
476: AUTHOR = {Florian Brandner and Andreas Fellnhofer and Andreas Krall and David Riegler},
477: BOOKTITLE = {Rapid Simulation and Performance Evaluation: Methods and Tools (RAPIDO'09)},
478: EDITOR = {Smail Niar, Rainer Leupers, Olivier Temam},
479: PUBLISHER = {HiPEAC},
480: PAGES = {1--6},
481: ADDRESS = {Paphos, Cyprus},
482: MONTH = {January},
483: YEAR = {2009},
484: }
485: \end{comment}
486:
487: \bibliography{res} % Input von res.bib, kommt dann spaeter dazu ...
488:
489: \end{document}
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>