Matteo Corti — ETH

Software Design & Development

• Homepage at work

Teaching

• Fall semester 2007: Compiler Design 2 (homepage)
• Summer semester 2007: Computer Systems Lab (homepage)
• Teaching from 1998 to 2005

Research

From December 1998 to March 2005 I was employed at the department of computer science of the Swiss Federal Institute of Technology as a teaching and research assistant while working on my PhD at the Laboratory for Software Technology.

• More on WCET research
• My old homepage at the Computer Systems Institute

Research

Worst-Case Execution Time Analysis

My research focused on a set of static compile-time analyses to estimate the worst-case execution time of Java processes focusing on the approximation of the WCET of fairly large soft-real-time applications on modern hardware systems.

In a first phase the program is analyzed to extract semantic information and to determine the maximal (and minimal) number of iterations for each basic block, by possibly bounding every cyclic structure in the program. As a first step, the semantic analyzer, embedded in an ahead-of-time bytecode-to-native Java compiler, performs an abstract interpretation pass of linear code segments reducing the set of possible values of local variables at a given program point and discovering a subset of the program's infeasible paths. This step is followed by a loop-bounding algorithm based on local induction variable analysis that, combined with structural analysis, is able to deliver fine-grained per-block bounds on the minimum and maximum number of iterations. To resolve the target of method calls the compiler performs a variable type based analysis reducing the call-graph size.

In a second phase the duration of the different program's instructions or basic blocks is computed with respect to the used hardware platform and the computational context where the instructions are executed. Modern systems with preemption and modern architectures with non-constant instruction duration (due to pipelining, branch prediction and different level of caches) hinder a fast and precise computation of a program's WCET. Instead of simulating the CPU behavior on all the possible paths we apply the principle of locality, limiting the effects of a given instruction to a restricted period in time and allowing us to analyze large applications in asymptotically linear time.

We describe the effectiveness in approximating the worst-case execution time for a number of programs from small kernels and soft-real-time applications.

See my list of publications for more information

Compiler construction

The WCET analyzer is implemented as a module of ERCO: A research Java bytecode-to-native compiler. The compiler, which is based on an intermediate representation in SSA form, is completely written in Java and produces native code for the Intel x86 platform on Linux. We rely on GCJ for the memory management and garbage collection routines and on classpath as implementation of the base libraries.

For more information please refer to the compiler homepage.

Teaching

During my stay I taught the recitation classes of

• System Software (WS 2003/2004, WS 2003/2005)
• Compiler Construction I (SS 2000, SS 1999)
• Compiler Construction II (WS 2000/2001, WS 1999/2000)
• Informatik IV (SS 2002, SS 2001)
• Informatik I (WS 2001/2002)
• Programmieren und Problemlösen (SS 2003)

During the winter semester 2004/2005 I taught, toghether with Patrik Reali, the System Software core lecture.

List of supervised master theses and term projects:

• Felix Pfrunder (2004/2005): Instruction Duration Estimation on Modern Processors
• Robert Simons (2003): Worst-Case Memory Usage Estimation
• Damon Fenacci (2001/2002): Pointer Analysis For Object-Oriented Programming Language
• Daniel Augsburger (2001/2002): Instruction-level Timing Analysis for Modern Processors
• Fabiano Ghisla (2001): False Path Analysis for Object-Oriented Language
• Marco Terzer (1999/2000): Java Static Compiler Back End
• Katrin Bretscher (2004), Peer Review System
• Micahel Szediwy (2003/2004), Multi-Interval Loop Analysis
• Nathalie Kellenberger (2003/2004), WCET Estimation of Sample Fx Programs
• Andrea Rezzonico (2003), Control Flow Graph Representation Using Structural Analysis
• Stefan Heimann (2003), Test, Evaluirung und Verbesserung eines Systems zur Automatischen Abschätzung der Worst-Case Execution Time von Java Programmen
• Mathias Althaus (2002/2003): Peer Review System - Analysis and Design.
• Stephen Jones (2001): Efficient Class-Initialization in a Way-Ahead of Time Java Compiler
• Damon Fenacci (2001): Java ahead of time compiler for the XO/2 Hard-Real Time OS.
• Bernhard Egger (2001): Java ahead of time compiler for the XO/2 Hard-Real Time OS.
• Stephen Jones (2001): Java ahead of time compiler for the XO/2 Hard-Real Time OS.
• Daniel Augsburger (2000): Java Runtime Environment on Intel x86