Semantic Foundations for Heterogeneous Systems

Roberto Passerone and Jerry Burch1
(Professor Alberto L. Sangiovanni-Vincentelli)

System level designs often include a wide range of hardware and software components (e.g., control logic, data paths, sensors, actuators, drivers, and data-flow engines). Such different components can be most naturally formalized using different models of computation (MoCs). Heterogeneous systems are those systems that are best described with two or more different MoCs. Typically, a formal methodology is only applicable to a particular MoC. The objective of this research is to develop semantic foundations that can be applied to heterogeneous systems involving an unlimited number of MoCs. This is crucial for the development of a system integration platform, like the Metropolis Meta-Model, that acts as the central repository of heterogeneous information (similar to the Genesis database for layout information). In particular, the ability to formally reason about the interaction of different MoCs is fundamental for system level design and for platforms to establish a solid foundation for analysis, including formal verification, synthesis, and simulation.

Informally, the semantics of a model of computation are given by a function that maps the model to a set of agents, called the semantic domain. In this work we develop a framework in which we can express semantic domains in a form that is close to their natural formulation (i.e., the form that is most convenient for a given model of computation), and yet structured enough to give us results that apply regardless of the particular domain in question. For each domain, we define functions that formalize concepts such as parallel and sequential composition of agents, scoping, and instantiation that are naturally expressed in the model of computation. Each semantic domain is also equipped with an order on the agents that represents a refinement relation. The structure composed of the set of agents and the functions and relations over the set of agents is called an agent algebra.

An important factor in the design of heterogeneous systems is the ability to flexibly use different levels of abstraction. In our work we emphasize the relationships that can be constructed between different semantic domains at different levels of abstraction, and how they are related to the functions and the refinement relation defined on the domain. The concept of a conservative approximation is introduced as a class of functions that preserve the notion of refinement across different semantic domains. These functions are powerful tools that we can use to study the problem of the integration of heterogeneous domains. In particular, two heterogeneous models can be composed and studied in the context of a third semantic domain that is detailed enough to refine both. Abstraction can be used again to convert the results in the respective domains.

J. R. Burch, R. Passerone, and A. L. Sangiovanni-Vincentelli, "Using Multiple Levels of Abstraction in Embedded Software Design," Proc. Int. Workshop on Embedded Software, Tahoe City, CA, October 2001.
J. R. Burch, R. Passerone, and A. L. Sangiovanni-Vincentelli, "Overcoming Heterophobia: Modeling Concurrency in Heterogeneous Systems," Proc. Int. Conf. Application of Concurrency to System Design, Newcastle upon Tyne, UK, June 2001.
J. R. Burch, R. Passerone, and A. L. Sangiovanni-Vincentelli, "Modeling Techniques in Design-by-Refinement Methodologies," Proc. World Conf. Integrated Design and Process Technology, Pasadena, CA, June 2002.
1Outside Adviser (non-EECS), Cadence Berkeley Laboratories

Send mail to the author : (

Edit this abstract