Electrical & Computer Engineering     |     Carnegie Mellon

Tuesday, January 24, 12:00-1:00 p.m. HH-1112


Twan Basten
Eindhoven University

The Essence of Computation

There is a clear trend in today's electronic systems towards concurrency and dynamism, with multiple applications sharing the underlying compute infrastructure. Networked systems are evolving into ambient systems, and traditional circuits are becoming multiprocessor systems-on-chip. As a consequence, today's design flows do not fit tomorrow's design problems. We are facing many interesting challenges. How can we guarantee predictable system behavior, not only from a functionality point of view, but also from the timing, energy, quality, points of view? And how do we handle all the trade-offs between application quality, the use of processing, communication, and storage resources, energy, security etc.?

These challenges can only be addressed if we develop a solid mathematical basis for our engineering practices. We will only succeed in this, if we manage to capture the essence of computation in our models and theories. To illustrate this, in the first part of this talk, I will present conservative execution-time estimation techniques for multi-media applications running on an on-chip multiprocessor with network-based interconnect. The techniques can cope with concurrency and data-dependent execution times, and the accuracy appears to be promising. In the second part, I will present an algebra of Pareto points, which forms the basis for compositional reasoning about trade-offs.


Twan Basten is an associate professor in the Department of Electrical Engineering at the Eindhoven University of Technology, The Netherlands. He received his M.Sc. and Ph.D. degrees in Computing Science from the Eindhoven University of Technology in 1993 and 1998, respectively. His current research interest is the design of complex, resource-constrained embedded systems, based on a solid mathematical foundation, with a special focus on multiprocessor systems and models of computation. Twan Basten has publications in the areas of system design, models of computation, embedded systems, formal methods, and workflow management. He was the topic chair for ambient intelligence and ubiquitous computing in the program committee of DATE from 2003 till 2005. He can be reached at http://www.es.ele.tue.nl/~tbasten/.