Computer science colloquia
| Date/Time: | Thursday, 05 Mar 2009 at 3:40 pm |
|---|---|
| Location: | B29 Atanasoff |
| Cost: | free |
| Phone: | 515-294-7609 |
| Channel: | Groups, governance |
| Categories: | Lectures |
| Actions: | Download iCal/vCal | Email Reminder |
Synchronous block diagrams are a hierarchical signal-flow diagram notation with synchronous semantics. They are the fundamental model behind widespread tools in the embedded software domain, such as SCADE and the discrete-time subset of Simulink. Automatic code generation from such models is key to the success of so-called model-based design, which promises to lift design to high-level models, by proving properties at the high level, and then somehow guaranteeing that these properties are preserved by the implementation.
We study modular code generation from SBDs: modular means that code is generated for a given composite block independently from context (i.e., without knowing in which diagrams this block is to be used). Existing methods fail to address this problem in a satisfactory manner. They generate "monolithic" code, e.g., a single step-function per block. This introduces false dependencies between block inputs and outputs, and compromises reusability, by not allowing the block to be used in some contexts. As a result, state-of-the-art tools either impose restrictions on the diagrams they can handle or resort to flattening.
We propose a framework that fixes this by generating, for a given block, a variable number of interface functions, as many as needed to achieve maximal reusability, but no more. In the worst case, N+1 functions may be needed, where N is the number of outputs of the block. It is crucial to minimize the number of interface functions, for reasons of scalability, but also because of IP concerns. We are thus led to define a quantified notion of modularity, in terms of the size of the interface of a block. The smaller the interface, the more modular the code is. Our framework exposes fundamental trade-offs between reusability, modularity and code size. We show how to explore these trade-offs by choosing appropriate graph clustering algorithms. We present a prototype implementation and experimental results carried on Simulink models. We also describe extensions of our framework to triggered and timed diagrams.
Biography:
Stavros Tripakis obtained a PhD degree in Computer Science at the Verimag Laboratory in Grenoble, France, in December 1998. He worked from 1999 to 2001 as a Post-doctoral Researcher at UC Berkeley, from 2001 to 2006 as a CNRS Research Scientist at Verimag, and from 2006 to 2008 as a Research Scientist at Cadence Research Labs in Berkeley, CA. He is currently a Visiting Associate Research Engineer at UC Berkeley. His work broadly lies in the areas of embedded software, real-time and distributed systems, and computer-aided design and verification.