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