By Abhik Roychoudhury and Tulika Mitra on Sat April 2, 2005 (whole day)
Goals of the tutorial:
The tutorial aims to emphasize that the issues in embedded software design can be somewhat different from conventional software. The participants will appreciate (through a concrete setting) that designing reliable embedded software involves issues beyond functionality validation. The tutorial will also emphasize that the embedded software designer cannot be totally oblivious to the underlying hardware platform. We do not require background in hardware/architecture from the participants; that is, the material on micro-architectural issues will be presented from first principles.
Summary of Technical Material:
Timing Analysis of
software to estimate an upper bound on the execution time is an important
problem for real-time embedded system design. This problem is known as the
worst-case
execution time (WCET) analysis.
The WCET estimate of a program is useful for schedulability analysis, i.e.
for finding out whether all timing constraints of a real-time embedded system
can be met.
Technically, WCET analysis/optimization cuts
across several layers of a computer system: programming languages, compiler as
well as architecture. This makes the problem challenging and also more
interesting.
In this tutorial, we will introduce the problem of WCET analysis/optimizations,
give an overview of the state-of-the art techniques, as well as touch upon its
applications. We will start with timing analysis of a single sequential program.
The two main components of this analysis are path analysis (for detecting
infeasible paths) and modeling the timing effects of micro-architectural
features (cache, pipeline, branch prediction). Pragmatic issues such as
scalability and performance of WCET analysis techniques will be discussed. This
will be followed by novel optimization techniques aimed to reduce a program's
WCET. In particular, we will study code and data layout optimizations.
We will also discuss WCET analysis of more than one tasks/programs that share some common resources (e.g., buffers, bus or micro-architectural resources like caches). We will look at three concrete problem settings in this regard. The first one is timing analysis of the interaction among threads in a traditional real-time multi-tasking application due to shared micro-architectural resources such as caches. Secondly , we will look at extending these techniques to estimate timing bounds in system-level design of streaming applications. Finally, we will elaborate on the issues in estimating communication times and integrating it with computation time analysis for multi-processor platforms. We will conclude with a discussion on open issues and research directions in timing analysis.
Biographies of the Presenters:
Abhik received his Ph.D. in Computer Science in December 2000 from the State University of New York at Stony Brook. Since then, he has been an Assistant Professor at School of Computing, National University of Singapore. He is interested in models/methods for reasoning about programs and reliable software development with specific focus on embedded and real-time systems. He holds a patent, has published widely and is currently involved in several funded research projects in these areas.
Tulika is currently an Assistant Professor at School of Computing, National University of Singapore. She received her Ph.D. from the State University of New York at Stony Brook in 2000. Her research interest is in the area of computer architecture with specific focus on parallel computing systems and embedded systems. Her research on these issues has been published widely in refereed journals and peer-reviewed conferences. She is currently PI of a research project on timing analysis, details of which can be found here.
URL: http://www.comp.nus.edu.sg/~abhik/WCET_papers.html