File:  [gforth] / res / PP-compiler.tex
Revision 1.4: download - view: text, annotated - select for diffs
Fri Jun 26 07:34:20 2009 UTC (13 years, 5 months ago) by andi
Branches: MAIN
CVS tags: HEAD
state art reliability finished

\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 Ulrich Schmid}\\
s@ecs.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
techniques 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}.

Compiler Verification \cite{Hoare,1328444,1314860}

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)}



(1) Specification and efficient simulation of reliable processors (partial redundancy,
ECC, lockstep etc) and compiler optimizations to exploit/balance reliabiliy features.
Connection with CESAR NN1

(2) translation verification, specification of semantics of IRs solving
subproblems. NN1 + NN2

(3) WCET NN3


\begin{tabular}{llll}
\hline
{\bf Pos} & {\bf Type} & {\bf Description}    & {\bf Duration} \\
NN1 & PhD & reliable compilation / simulation & 4 years \\
NN2 & PhD & compiler verificationi            & 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}

FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>