\documentclass[11pt,a4paper]{article} %\usepackage{latexsym} \usepackage{url} %\usepackage{times} \usepackage{comment} \pagestyle{plain} \setlength{\textwidth}{16truecm} \setlength{\textheight}{24truecm} \setlength{\oddsidemargin}{-0.3truecm} \setlength{\evensidemargin}{-0.3truecm} \setlength{\topmargin}{0.0truecm} \setlength{\topskip}{0.0truecm} \setlength{\headheight}{0.0truecm} \setlength{\headsep}{0.0truecm} \newcommand{\emn}[1]{{\em #1\/}} \newcommand{\NOTE}[1]{{\medskip\bf #1\medskip}} \title{\bf PP \emph{Compilation Techniques for Robust Embedded Systems}} \author{{\sc Andreas Krall and Jens Knoop}\\ \{andi,knoop\}@complang.tuwien.ac.at } \bibliographystyle{unsrt} \begin{document} \maketitle PP leader: \emph{Jens Knoop and Andreas Krall} Associated researchers: \emph{} \subsubsection*{Motivation:} %\emph{Informal description of the purpose of the PP (3-5 lines)} Every embedded system consists of software which is written in a high level language, compiled to machine language and executed on a processor. For robust embedded systems new verified compilation, simulation and specification methods are necessary to optimize for performance, power, space, concurrency and reliability. \subsubsection*{State of the art and related work:} %\emph{Briefly describe the scientific state of the art (20-30 lines)} %Compilation Techniques for Reliability Because of the exponential increase of the number of transistors and the continuing decrease of the feature sizes of current processors soft errors mainly caused by energetic particles are becoming an important design issue for robust embedded systems. Blome et al.~\cite{Blome+06} observed that a majority of faults that affect the architectural state of a processor come from the register file. Lee and Shrivastava and proposed different solutions to cope with this problem. The first assigns variables depending on their lifetime to either the ECC protected or the unprotected part of a register file to balance energy consumption and reliability \cite{LeeShrivastava09a}. The second spills registers to ECC protected memory if the register contents are not used for a long period \cite{LeeShrivastava09c}. There exist complete software solutions which use different forms of code duplications \cite{Oh+02a,Reis+05}, which do failure virtualization \cite{WapplerMueller08} or which use techniques like control flow checking \cite{Oh+02b}. A complete overview of processor description languages and generation of compilers and simulators from processors specifications gives the book of Mishra and Dutt \cite{MishraDutt08}. A good survey of current instruction set simulators gives our chapter in the Handbook of Signal Processing systems \cite{BrHoKr09}. A famous instruction set simulator with modelling of energy consumtion is Wattch \cite{BrooksTiwariMartonosi00}. Three aspects of program and compiler correctness exist. The verifying compiler proves properties of the translated program and is a grand challenge for computing research \cite{Hoare03}. A certified compiler like Verfix is proven once to do semantically equivalent optimizations and translations \cite{GlesnerGoosZimmeermann04,GoosZimmermann00}. Translation validation proves at every compiler run that the translation is correct and was introduced by Pnueli et al.\ \cite{Pnueli98a,Pnueli98b} and Necula \cite{Necula00}. Until now some optimizations have been verified, recently lazy code motion \cite{TristanLeroy09}, instruction scheduling \cite{TristanLeroy08}, or the whole code generation phase \cite{BlechPoetzsch07}. Another research direction is the construction of general frameworks for validation \cite{ZaksPnueli08} or generalizations like parameterized equivalence checking \cite{Kundu+09}. WCET \cite{} \subsubsection*{Previous achievements:} %\emph{Brief description of your own contributions to the related %scientific state-of-the art (5-10 lines)} Jens Knoop has a long history on work on program analysis with topics like partial redundancy elimination or lazy code motion \cite{knoop:DSP:2008:1575,conf/cc/XueK06,scholz04}. Recently he changed his research focus on worst case execution time analysis \cite{SchrSchoKn09,Prantl:WLPE2008,prantl_et_al:DSP:2008:1661, kirner_et_al:DSP:2008:1657,kirner_et_al:DSP:2007:1197}. He is involved in the organization of many compiler conferences and since 2002 program cochair of the yearly workshop on compiler optimization meets verification. Andreas Krall does research in the area of architecture description languages and the automatic generation of highly optimizing compilers, efficient instruction set simulators and hardware from one single specification of a processor \cite{BrFeKrRi09,BrEbKr07,FaKrHo07, FarKrStBrand06,Krall+04micro}. An important focus is on optimization techniques for embedded processors \cite{EbBrSchKrWiKa08,MeKr07,PrKrHo06,HiKr03} as he lead the Christian Doppler research laboratory {\em compilation techniques for embedded processors} with partners from industry (Infineon, OnDemand Microelectronics). \subsubsection*{Goals (first 4 years):} %\emph{Description of the research %topics to be addressed during the first 4 years. Make sure to explicitly %stress what the significant additions to the scientific knowledge are, %and why they are important. (30-40 lines)} New modeling and representation techniques of non-functional program and system properties on the programming and intermediate language levels Definitions and measures of non-functional program and system properties (performance, time, space/memory, power, concurrency). Modeling and representation of these properties alongside with the programming languages semantics Adapting and enhancing state-of-the-art compilation techniques towards non-functional property and platform awareness New functional and non-functional property and platform-aware compilation techniques Analyses for non-functional program and system properties Functional and non-functional property and platform-aware code generation techniques Enabling validation and verification throughout the compilation process Techniques for reducing or eliminating trusted code, annotation, etc., bases \subsubsection*{Work Plan (first 4 years):} %\emph{Brief description of how %you intend to conduct the actual research during the first 4 years. Be sure %to also describe and (coarsely) quantify the resources (staff, cost of %special equipment) required for this work in a table. (20-30 lines)} Compilation techniques for robust embedded systems comprise different areas. Therefore, the project is divided into three work packages: compilation and simulation techniques for reliabiltiy, verified compilation and worst case execution time analysis. \paragraph*{WP1 - Compilation and Simulation Techniques for Reliability} In previous work we have developed a processor description language with a very concise semantics from where we automatically generate optimized compilers \cite{BrEbKr07} and high efficient instruction set simulators \cite{BrFeKrRi09}. This environment we use as testbed for our compiler optimizations for embedded processors \cite{EbBrSchKrWiKa08,PrKrHo06,MeKr07}. We will extend this environment to do research on compilation and simulation techniques to enhance the reliability of processor/memory systems by mixed hardware/software and pure software techniques. \begin{itemize} \item Specification method to specify an energy consumption model in a processor specification. \item Specification method for redundancy and error correction in the processor specification \item Specification method for fault injection and fault checking in the processor specification \item Generation of optimized instruction set simulators from the extended processor specification \item Generation of optimizing compilers from the extended processor specification \item Research into new compiler optimizations to increase reliability by pure software solutions, mixed hardware/software solutions and balancing performance, code space, reliability and energy consumption \item Research of correctness proofs and validation of the new optimizations \end{itemize} \paragraph*{WP2 - Verified Compilation} Suitable semantics are necessary which support efficient translation validation or support easy verification of a compiler. We will research into different semantics and into mappings between the semantics of our processor description language \cite{BrEbKr07} and a compiler backend semantics, intermediate representation semantics (compatible to LLVM) and source language semantics. The main research will be on verification and translation validation for all kinds of compiler optimizations. \begin{itemize} \item Evaluate different semantics regarding suitability for compiler verification and translation validation, eventually develop new semantics \item Develop a translator for an automatic mapping from our processor description language into verification semantics \item Develop a validation system from the intermediate representation (LLVM) to the processor semantics \item Develop a validation system from the source language (C) to the intermediate representation (LLVM) \item Research into verification and translation validation for different frontend and backend optimizations \end{itemize} \paragraph*{WP3 - Worst Case Ececution Time Analysis} WCET \begin{tabular}{llll} \\ \hline {\bf Pos} & {\bf Type} & {\bf Description} & {\bf Duration} \\ NN1 & PhD & reliable compilation / simulation & 4 years \\ NN2 & PhD & verified compilation & 4 years \\ NN3 & PhD & WCET & 4 years \\ \hline \end{tabular} \subsubsection*{Goals (last 4 years):} %\emph{Brief description of the %eesearch topics to be addressed during the last 4 years. Make sure to %explicitly stress what the significant additions to the scientific %knowledge are, and why they are important. (20-30 lines)} New programming languages and compilers for RESs Non-functional properties and requirements as first-class language and compiler citizens New compilation techniques enabling a uniform and integrated approach for ensuring functional and non-functional program and system requirements Replacing trust by proof Certifying compilation, proof-carrying code, translation validation Verified compilers, verifying compilation for RESs Making legacy applications fit to and available on RESs Techniques for adjusting and decompiling legacy applications \subsubsection*{Collaboration with other PPs:} %\emph{List the PPs you are expecting to collaborate with, and describe briefly %the topic and nature of such a collaboration. (10-20 lines)} \begin{itemize} \item PP Composition of Non-functional Requirements [I.S.T.A./Henzinger]: Links to specification and modeling of timing properties, to execution models, hardware and software models. \item PP Composition and Predictability in RES Architectures [E182/Puschner]: Links to hard- and software models for time predictable systems, verification of timing behaviour. \item PP Formal Verification for Robustness [E184/Veith]: Links to software model checking and testing of code (on source code and intermediate code levels), support for program analysis and transformation. \item PP Modeling \& Analysis of Robust Distributed Systems [E182/Schmid]: Links to functional and non-functional system requirements, distribution, concurrency. \end{itemize} \subsubsection*{External Collaborations:} %\emph{List envisioned international and national collaborations, and %describe briefly the topic and nature of such a collaboration. (5-10 %lines)} Aviral Shrivastava, Arizona State University, Tempe, AZ, USA Wolf Zimmermann, Universit\"at Halle, Halle, Germany \begin{comment} %Bitte hier die Bibtex-Entries einfuellen, z.B., ------------------------------------ @article{Hoare, author = {Tony Hoare}, title = {The verifying compiler: A grand challenge for computing research}, journal = {Journal of the ACM}, volume = {50}, number = {1}, year = {2003}, issn = {0004-5411}, pages = {63--69}, doi = {http://doi.acm.org/10.1145/602382.602403}, publisher = {ACM}, address = {New York, NY, USA}, } @article{1328444, author = {Jean-Baptiste Tristan and Xavier Leroy}, title = {Formal verification of translation validators: a case study on instruction scheduling optimizations}, journal = {SIGPLAN Not.}, volume = {43}, number = {1}, year = {2008}, issn = {0362-1340}, pages = {17--27}, doi = {http://doi.acm.org/10.1145/1328897.1328444}, publisher = {ACM}, address = {New York, NY, USA}, } @article{1314860, author = {Jan Olaf Blech and Arnd Poetzsch-Heffter}, title = {A Certifying Code Generation Phase}, journal = {Electron. Notes Theor. Comput. Sci.}, volume = {190}, number = {4}, year = {2007}, issn = {1571-0661}, pages = {65--82}, doi = {http://dx.doi.org/10.1016/j.entcs.2007.09.008}, publisher = {Elsevier Science Publishers B. V.}, address = {Amsterdam, The Netherlands, The Netherlands}, } @INPROCEEDINGS{LeeShrivastava09, TITLE = {A Compiler Optimization to Reduce Soft Errors in Register Files}, AUTHOR = {Jongeun Lee and Aviral Shrivastava}, BOOKTITLE = {ACM SIGPLAN/SIGBED Conference on Languages, Compilers, and Tools for Embedded Systems}, EDITOR = {Mahmut Kandemir}, PUBLISHER = {ACM}, PAGES = {??--??}, ADDRESS = {Dublin}, MONTH = {June}, YEAR = {2009}, } @BOOK{MishraDutt08, TITLE = {Processor Description Languages}, AUTHOR = {Prabhat Mishra and Nikil Dutt (Editor)}, PUBLISHER = {Morgan Kaufmann}, YEAR = {2008}, } %Eigene Referenzen ab hier. @InProceedings{SchrSchoKn09, TITLE = "Adding Timing-Awareness to {AUTOSAR} Basic-Software - A Component Based Approach", AUTHOR = "Dietmar Schreiner and Markus Schordan and Jens Knoop", BOOKTITLE = "12th IEEE International Symposium on Object/component/service-oriented Real-time distributed Computing (ISORC 2009)", PUBLISHER = "IEEE", ADDRESS = "Tokyo, Japan", YEAR = "2009", MONTH = "March", PAGES = "288--292", } @inproceedings{Prantl:WLPE2008, Address = {Udine, Italy}, Author = {Adrian Prantl and Jens Knoop and Markus Schordan and Markus Triska}, Booktitle = {The 18th Workshop on Logic-based methods in Programming Environments (WLPE 2008)}, Month = {December 12}, Title = {Constraint solving for high-level WCET analysis}, Year = {2008}, URL = {http://costa.tuwien.ac.at/papers/wlpe08.pdf} } @InProceedings{prantl_et_al:DSP:2008:1661, author = "Adrian Prantl and Markus Schordan and Jens Knoop", title = "TuBound - {A} Conceptually New Tool for Worst-Case Execution Time Analysis", booktitle = "8th Intl. Workshop on Worst-Case Execution Time (WCET) Analysis", year = "2008", editor = "Raimund Kirner", publisher = "Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany", address = "Dagstuhl, Germany", URL = "http://drops.dagstuhl.de/opus/volltexte/2008/1661", annote = "Keywords: Worst-case execution time (WCET) analysis, Tool Chain, Flow Constraints, Source-To-Source", ISBN = "978-3-939897-10-1", note = "also published in print by Austrian Computer Society (OCG) under ISBN 978-3-85403-237-3", } @InProceedings{kirner_et_al:DSP:2008:1657, author = "Raimund Kirner and Albrecht Kadlec and Adrian Prantl and Markus Schordan and Jens Knoop", title = "Towards a Common {WCET} Annotation Language: Essential Ingredients", booktitle = "8th Intl. Workshop on Worst-Case Execution Time (WCET) Analysis", year = "2008", editor = "Raimund Kirner", publisher = "Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany", address = "Dagstuhl, Germany", URL = "http://drops.dagstuhl.de/opus/volltexte/2008/1657", annote = "Keywords: Worst-case execution time (WCET) analysis, annotation languages, WCET annotation language challenge", ISBN = "978-3-939897-10-1", note = "also published in print by Austrian Computer Society (OCG) under ISBN 978-3-85403-237-3", } @InProceedings{kirner_et_al:DSP:2007:1197, author = "Raimund Kirner and Jens Knoop and Adrian Prantl and Markus Schordan and Ingomar Wenzel", title = "{WCET} Analysis: The Annotation Language Challenge", booktitle = "7th Intl. Workshop on Worst-Case Execution Time (WCET) Analysis", year = "2007", editor = "Christine Rochange", publisher = "Internationales Begegnungs- und Forschungszentrum f{"u}r Informatik (IBFI), Schloss Dagstuhl, Germany", address = "Dagstuhl, Germany", URL = "http://drops.dagstuhl.de/opus/volltexte/2007/1197", annote = "Keywords: Worst-case execution time analysis, WCET, path description, annotation language challenge, expressiveness, convenience", } @InProceedings{knoop:DSP:2008:1575, author = {Jens Knoop}, title = {Data-Flow Analysis for Multi-Core Computing Systems: A Reminder to Reverse Data-Flow Analysis}, booktitle = {Scalable Program Analysis}, year = {2008}, editor = {Florian Martin and Hanne Riis Nielson and Claudio Riva and Markus Schordan}, number = {08161}, series = {Dagstuhl Seminar Proceedings}, ISSN = {1862-4405}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany}, address = {Dagstuhl, Germany}, URL = {http://drops.dagstuhl.de/opus/volltexte/2008/1575}, annote = {Keywords: Multi-core computing systems, scalable program analysis, reverse data-flow analysis, demand-driven data-flow analysis} } @InProceedings{conf/cc/XueK06, title = "A Fresh Look at {PRE} as a Maximum Flow Problem", author = "Jingling Xue and Jens Knoop", bibdate = "2006-04-05", bibsource = "DBLP, http://dblp.uni-trier.de/db/conf/cc/cc2006.html#XueK06", booktitle = "CC", booktitle = "Compiler Construction, 15th International Conference, {CC} 2006, Held as Part of the Joint European Conferences on Theory and Practice of Software, {ETAPS} 2006, Vienna, Austria, March 30-31, 2006, Proceedings", publisher = "Springer", year = "2006", volume = "3923", editor = "Alan Mycroft and Andreas Zeller", ISBN = "3-540-33050-X", pages = "139--154", series = "Lecture Notes in Computer Science", URL = "http://dx.doi.org/10.1007/11688839_13", } @InProceedings{scholz04, author = "Bernhard Scholz and Nigel Horspool and Jens Knoop", title = "Optimizing for space and time usage with speculative partial redundancy elimination", booktitle = "LCTES '04: Proceedings of the 2004 ACM SIGPLAN/SIGBED conference on Languages, Compilers, and Tools for Embedded Systems", year = "2004", ISBN = "1-58113-806-7", pages = "221--230", location = "Washington, DC, USA", publisher = "ACM Press", } @InProceedings{HiKr03, TITLE = "{VLIW} Operation Refinement for Reducing Energy Consumption", AUTHOR = "Ulrich Hirnschrott and Andreas Krall", BOOKTITLE = "International Symposium on System-on Chip", PUBLISHER = "IEEE", ADDRESS = "Tampere, Finland", YEAR = "2003", PAGES = "131--134", } @Article{Krall+04micro, author = {Andreas Krall and Ulrich Hirnschrott and Christian Panis and Ivan Pryanishnikov}, title = {x{DSP}core: {A} {C}ompiler-{B}ased {C}onfigureable {D}igital {S}ignal {P}rocessor}, journal = {IEEE Micro}, year = {2004}, OPTkey = {}, volume = {24}, number = {4}, pages = {67-78}, month = {July/August}, OPTnote = {}, OPTannote = {}, } @INPROCEEDINGS{FarKrStBrand06, TITLE = {Effective Compiler Generation by Architecture Description}, AUTHOR = {Stefan Farfeleder and Andreas Krall and Edwin Steiner and Florian Brandner}, BOOKTITLE = {ACM SIGPLAN/SIGBED Conference on Languages, Compilers, and Tools for Embedded Systems}, EDITOR = {Koen De Bosschere}, PUBLISHER = {ACM}, PAGES = {145--152}, ADDRESS = {Ottawa}, MONTH = {June}, YEAR = {2006}, URL = {http://doi.acm.org/10.1145/1134650.1134671}, } @ARTICLE{PrKrHo06, AUTHOR = {Ivan Pryanishnikov and Andreas Krall and Nigel Horspool}, TITLE = {Compiler Optimizations for Processors with {SIMD} Instructions}, JOURNAL = {Software---Practice and Experience}, PUBLISHER = {Wiley}, VOLUME = {37}, NUMBER = {1}, PAGES = {93--113}, YEAR = {2007}, URL = {http://www3.interscience.wiley.com/cgi-bin/fulltext/112783581/PDFSTART}, } @ARTICLE{FaKrHo07, AUTHOR = {Stefan Farfeleder and Andreas Krall and Nigel Horspool}, TITLE = {Ultra Fast Cycle-Accurate Compiled Emulation of Inorder Pipelined Architectures}, JOURNAL = {Journal of Systems Architecture}, PUBLISHER = {Elsevier}, VOLUME = {53}, NUMBER = {8}, PAGES = {501--510}, YEAR = {2007}, } @INPROCEEDINGS{MeKr07, TITLE = {Instruction Set Encoding Optimization for Code Size Reduction}, AUTHOR = {Michael Med and Andreas Krall}, BOOKTITLE = {International Conference on Embedded Computer Systems: Architectures, Modeling, and Simulation}, ADDRESS = {Samos, Greece}, PAGES = {9--17}, MONTH = {July}, YEAR = {2007} } @INPROCEEDINGS{BrEbKr07, TITLE = {Compiler Generation from Structural Architecture Descriptions}, AUTHOR = {Florian Brandner and Dietmar Ebner and Andreas Krall}, BOOKTITLE = {International Conference on Compilers, Architecture, and Synthesis for Embedded Systems}, ADDRESS = {Salzburg, Austria}, PAGES = {13--22}, MONTH = {September}, YEAR = {2007} } @INPROCEEDINGS{EbBrSchKrWiKa08, TITLE = {Generalized Instruction Selection using {SSA}-Graphs}, AUTHOR = {Dietmar Ebner and Florian Brandner and Bernhard Scholz and Andreas Krall and Peter Wiedermann and Albrecht Kadlec}, BOOKTITLE = {ACM SIGPLAN/SIGBED Conference on Languages, Compilers, and Tools for Embedded Systems}, EDITOR = {John Regehr}, PUBLISHER = {ACM}, PAGES = {31--40}, ADDRESS = {Tucson}, MONTH = {June}, YEAR = {2008}, } @INPROCEEDINGS{BrFeKrRi09, TITLE = {Fast and Accurate Simulation using the LLVM Compiler Framework}, AUTHOR = {Florian Brandner and Andreas Fellnhofer and Andreas Krall and David Riegler}, BOOKTITLE = {Rapid Simulation and Performance Evaluation: Methods and Tools (RAPIDO'09)}, EDITOR = {Smail Niar, Rainer Leupers, Olivier Temam}, PUBLISHER = {HiPEAC}, PAGES = {1--6}, ADDRESS = {Paphos, Cyprus}, MONTH = {January}, YEAR = {2009}, } \end{comment} \bibliography{res} % Input von res.bib, kommt dann spaeter dazu ... \end{document}