Abstracts for Alberto L. Sangiovanni-Vincentelli

The EECS Research Summary for 2003


Interface Synthesis and Verification

Roberto Passerone, Jerry Burch1, and Luca de Alfaro2
(Professors Alberto L. Sangiovanni-Vincentelli and Thomas A. Henzinger)

Composing intellectual property blocks is an essential element of a design methodology based on re-use. The composition of these blocks when the IPs have been developed by different groups inside the same company, or by different companies, is notoriously difficult. Design rules in the form of interface specifications have been proposed which try to alleviate the problem by forcing the designers to be precise about the behavior of the individual components, and to verify this behavior under a number of assumptions about the environment in which they have to operate. In this work we study the problem of the specification, synthesis, and verification of interfaces for different models of computation and across models of computation. This work supports the Metropolis Meta-Model in the construction of a system integration platform that can integrate heterogeneous models.

Roughly speaking, two agents are compatible if they fit together as they are. In this work we formalize this notion by introducing, for each model of computation, a set of agents that “behave well,” and by deriving a refinement ordering that represents substitutability, called the conformance ordering. We show that under certain assumptions we can represent the set of compatible agents by a single maximal environment, called a mirror. Two agents are compatible if one conforms to the maximal environment of the other.

When components are taken from legacy systems or from third-party vendors, it is likely that their interface communication protocols are not compatible. In this case, an additional adapter can sometimes be introduced to convert from one agent to the other so that their composition is compatible. The notion of a maximal environment allows us to formulate a synthesis algorithm for an adapter that conforms to the specification of a desired communication.

We formulate the problem in particular for synchronous and asynchronous systems. We use an automata-based and a game-theoretic based approach to solving the adaptation problem and to synthesize a converter between two specified protocols.

[1]
R. Passerone, J. A. Rowson, and A. L. Sangiovanni-Vincentelli, "Automatic Synthesis of Interfaces between Incompatible Protocols," Proc. Design Automation Conf., San Francisco, CA, June 1998.
[2]
R. Passerone, L. de Alfaro, T. A. Henzinger, and A. L. Sangiovanni-Vincentelli, "Convertibility Verification and Converter Synthesis: Two Faces of the Same Coin," Proc. Int. Conf. Computer Aided Design, San Jose, CA, November 2002.
1Outside Adviser (non-EECS), Cadence Berkeley Laboratories
2Professor, UC Santa Cruz

Send mail to the author : (roby@eecs.berkeley.edu)

Path Categorization Criteria for Static Timing Analysis

Alessandra Nardi1 and Luca Carloni
(Professors Alberto L. Sangiovanni-Vincentelli and Kurt Keutzer)

Static timing analysis is the most used approach to critical path detection in combinational circuits. Since traditional criteria used in standard static timing analysis depend on circuit delay assignment, the analysis has to be repeated after each timing optimization step. A new approach to static timing analysis has been recently proposed in [1]. The cornerstone of the method consists of grouping paths into three categories: strongly perceptible, imperceptible, and weakly perceptible. This categorization allows definite distinction between paths that impact the circuit delay, and therefore need to be sped up, and those that do not, thus reducing the timing optimization effort. Furthermore, this new approach has the advantage of being independent on the circuit delay assignment and, therefore, static timing analysis need not be applied over and over after each timing optimization step. The main drawback of the method is that the criteria to check which category a path belongs to, which has been provided by the author, are partially ambiguous and not easy to compute. We identified new criteria for this path categorization based on the flattening of a circuit into an equivalent normal form (ENF). Our criteria, while being straightforward to check, clear any previous ambiguity, thus allowing the capture of the power of this new path categorization.

[1]
A. Saldanha, "Functional Timing Optimization," Proc. ICCAD, San Jose, CA, November 1999.
1Postdoctoral Researcher

More information (http://www-cad.eecs.berkeley.edu/~nardi) or

Send mail to the author : (nardi@eecs.berkeley.edu)

Low Power Network Discovery Methods for Sensor Networks

Abhijit Davare, David Nguyen, and Farinaz Koushanfar
(Professor Alberto L. Sangiovanni-Vincentelli)

Sensor networks present many opportunities for changing the way computers interact with the environment. Sensor network devices present major challenges because they must be functional under strict power requirements. Since wireless communication is the largest source of power consumption, we explore efficient algorithms for information gathering that try to minimize the amount of communication while still gathering the requisite amount of data.

Our research focuses on an efficient traversal method to gather information from the network. We assume that nodes have a fixed communication radius. Our model also assumes that every node has complete information about each of its neighbors. In addition, a node can go into sleep mode, and it will not take part in communication while in this state. Given the above constraints, we are attempting to design heuristic methods that will gather information from all nodes while actually visiting a minimal number of nodes.

Our approach involves a graph theoretical formulation coupled with geographic knowledge about the network. In this approach, each node is represented as a vertex and a communication path is represented as an edge. We are investigating the significance of network perimeter nodes, articulation points, and sub-areas as components of this heuristic approach.


Send mail to the author : (davare@eecs.berkeley.edu)

Upper Bound Estimation for the Noise Current Spectrum of Digital Circuit Blocks

Alessandra Nardi1 and Luca Daniel
(Professor Alberto L. Sangiovanni-Vincentelli)
Semiconductor Research Corporation

The complexity of the systems-on-a-chip design requires an aggressive re-use of intellectual property (IP) circuit blocks. However, IP blocks can be safely re-used only if they do not affect other sensitive components. The switching activity of CMOS digital circuit blocks typically produces high frequency current noise both into the Gnd/Vdd system, and into the substrate of integrated circuits. Such currents can potentially affect circuit reliability and performance of other sensitive components. For instance the Gnd/Vdd currents may produce electromigration, IR voltage drops, voltage oscillations due to resonances, and, possibly, electromagnetic interference. The substrate currents may couple noise to sensitive analog circuitry through body effect or direct capacitive coupling. An analysis of current injection due to switching activity is needed to properly account for all such effects during the design phase. Different effects require different types of current injection models. For instance, power consumption analysis requires time-domain average current estimation over several clock periods. IR drop, electromigration, and timing performance analysis require a time-domain noise current upper-bound with respect to all possible combinations of the inputs. Signal integrity, Gnd/Vdd grid resonances, electromagnetic interference, and substrate coupling on mixed-signal ICs, on the other hand, require an upper-bound on the spectrum of the current injected into the Gnd/Vdd system or into the substrate, respectively. Methodologies developed so far do not address this latter kind of analysis. Therefore, for these problems we are developing a methodology for estimating an upper bound over all possible input combinations for the spectrum of the noise current injected by the switching activity of digital blocks. The methodology identifies an upper bound for the spectrum of a circuit noise current by combining the noise current injected by each gate and accounting for the circuit logic functionality.

[1]
A. Nardi, L. Daniel, and A. Sangiovanni-Vincentelli, A Methodology for the Computation of an Upper Bound on Noise Current Spectrum of CMOS Switching Activity, UC Berkeley Electronics Research Laboratory, Memorandum No. UCB/ERL M02/20, June 2002.
1Postdoctoral Researcher

More information (http://www-cad.eecs.berkeley.edu/~nardi) or

Send mail to the author : (nardi@eecs.berkeley.edu)

Ulysses: Protocol Synthesis from Scenario-based Specifications

Alvise Bonivento and Marco Sgroi
(Professor Alberto L. Sangiovanni-Vincentelli)
GSRC

The design of protocols, i.e., the set of rules that define how the communication among two or more components of a distributed system takes place, requires the use of formal techniques and tools to obtain a correct and efficient implementation. Ulysses is a new approach for protocol synthesis from scenario-based specifications. It allows the designer to specify sequences of interactions called scenarios using message sequence nets (MSNs), a model that includes message sequence charts and explicitly shows the relations of ordering concurrency or conflict among multiple MSCs. It uses Petri Nets (PNs) as an underlying model to formally define the semantics of MSNs and to specify the internal protocol behavior. A covering procedure that uses common case patterns and derives a PN model consistent with the original MSN is defined. Independently-specified scenarios are then composed to derive a minimum cost implementation.


Send mail to the author : (sgroi@eecs.berkeley.edu)

DRAFTS: Distributed Real-Time Applications Fault Tolerant Scheduling

Claudio Pinello
(Professor Alberto L. Sangiovanni-Vincentelli)
Gigascale Silicon Research Center

Some applications are so critical that they need to be resilient to faults in the computing architecture. Typically this is achieved by redundantly scheduling the application on the architecture. Starting from a network of process, some or all of the processes and the data they exchange are replicated. Additional processes may be needed for voting on the results of different replicas of a same process to establish a common result: the consensus problem [1]. We must then devise an assignment and schedule of the augmented network onto the distributed architecture.

It seems profitable to relieve the designer from the burden of devising a fault-tolerant distributed schedule, and opt for an approach based on synthesis.

In order to use resources efficiently, we want to allow the flexible use of passive replicas (replicas of a process that run only when the main replica undergoes a fault). Preliminary results have shown the usefulness of this technique in achieving higher schedulability by "reclaiming" resources from non-running replicas [2]. A further venue of improvement may arise in the context of gracefully degrading applications, where replicas are not an exact copy of the original process. Rather, there may be simpler versions with reduced functionality and/or accuracy and likely less resource requirements [3]. This exposes an opportunity to achieve higher schedulability by requiring strong fault resilience only of the light-weight versions.

Moreover, we want to allow general architectures, removing the strict boundaries of the modules and busses found in the TTA. This also enables more general fault models for the communication subsystem. The resulting architecture is a full-fledged distributed multiprocessor system, where each node can be used per se and not as a mere duplicate of another one. All the parallelism in the hardware can then be exploited to speed up the execution of parallel processes of the application [4,5] without affecting the degree of fault tolerance. We note that most of the results cited above have been derived under very restrictive assumption on the fault model. We believe some of their founding principles can be rephrased in a more general framework. The expected outcome of this research is a systematization of a set of design techniques that could allow for an easy exploration of design alternatives arising from different fault models.

[1]
M. Barborak, M. Malek, and A. Dahbura, "The Consensus Problem in Fault-Tolerant Computing," ACM Computing Surveys, Vol. 25, No. 2, 1993.
[2]
K. Ahn, J. Kim, and S. Hong, "Fault-Tolerant Real-Time Scheduling Using Passive Replicas," Proc. Pacific Rim Int. Symp. Fault-Tolerant Systems, Taipei, Taiwan, December 1997.
[3]
M. Caccamo, G. Buttazzo, and L. Sha, "Capacity Sharing for Overrun Control," Proc. IEEE Real-Time Systems Symp., Orlando, FL, November 2000.
[4]
C. Dima, A. Girault, C. Lavarenne, and Y. Sorel, "Off-line Real-Time Fault-Tolerant Scheduling," Proc. Euromicro Workshop on Parallel and Distributed Processing, Mantova, Italy, February 2001.
[5]
J. Aguilar and M. Hernandez, "Fault Tolerance Protocols for Parallel Programs Based on Tasks Replication," Proc. MASCOTS, San Francisco, CA, August-September 2000.

More information (http://www-cad.eecs.berkeley.edu/~pinello/distributedsystems) or

Send mail to the author : (pinello@eecs.berkeley.edu)

The Fault Tolerant Data Flow platform in Metropolis

Claudio Pinello and Yosinori Watanabe1
(Professor Alberto L. Sangiovanni-Vincentelli)

A new platform library in Metropolis allows the use of the fault tolerant data flow (FTDF) model of computation. FTDF is amenable to specifying periodic feedback control applications. It is structured in such a way that it is possible to analyze it formally and to use automatic and semi-automatic synthesis techniques for obtaining an efficient fault-tolerant implementation of the application under design. The use of the platform is illustrated by a simple controller example: an inverted pendulum stabilizer.

Redundancy can be easily introduced using the Metropolis refinement mechanism. Finally it is possible to simulate and to inject faults in the design. Some of the properties of FTDF include self-synchronization and automatic degradation in case of faults.

1Outside Adviser (non-EECS), Cadence Berkeley Labs

More information (http://www.gigascale.org/metropolis/) or

Send mail to the author : (pinello@eecs.berkeley.edu)

CAMA: A Multi-Valued Satisfiability Solver

Cong Liu, Andreas Kuehlmann1, and Matthew W. Moskewicz
(Professor Alberto L. Sangiovanni-Vincentelli)
GSRC

Boolean satisfiabilty (SAT) has many applications in the area of electronic design automation. In this project, a genuine multi-valued (MV) SAT solver, CAMA, is developed. Unlike encoding approaches, it directly deals with MV variables. We extended the major speed-up techniques used in state-of-the-art binary SAT solvers, such as two literal watch-based Boolean constraint propagation (BCP), conflict-based learning with identifying unique interception point (UIP), non-chronological back-tracking, and so on. An efficient conflict analysis algorithm-based MV SAT is developed. It makes the learned clauses as compact as possible, which has a dramatic impact on the overall performance. Finally, the performance of CAMA is compared to that of Chaff [1], one of the best binary SAT solvers known so far, using a one hot encoding scheme. Our experimental results show that for hard MV SAT problems, CAMA outperforms Chaff. And our analysis also reveals some fundamental reasons why a MV SAT solver has inherent advantages over a binary SAT solver.

[1]
M. Moskewicz, C. Madigan, Y. Zhao, L. Zhang, and S. Malik, "Chaff: Engineering an Efficient SAT Solver," Proc. Design Automation Conf., Las Vegas, NV, June 2001.
1Adjunct Professor

More information (http://www-cad.eecs.berkeley.edu/~congliu/) or

Send mail to the author : (congliu@eecs.berkeley.edu)

Active Watermarking of Data and Information in Wireless Ad Hoc Sensor Networks

Farinaz Koushanfar and Miodrag Potkonjak1
(Professor Alberto L. Sangiovanni-Vincentelli)

Sensor networks (SNs) have emerged as the bridge between the Internet and the physical world, as the driver of the next potential economic revolution, and as the imminent largest producer of data and information. Therefore, development of intellectual property protection (IPP) for SNs are of prime importance.

We propose the first IPP approach for data and information generated in sensor networks. Contrary to the current state-of-the-art of image and audio watermarking, we embed signatures before and/or during the process of data acquisition and processing. The key idea is to impose additional conditions that correspond to the cryptographically encoded author/owner's signature during the data acquisition or processing in such a way that the quality of recording or processing is not impacted, or is only minimally impacted.

The technique is generic in that it is applicable to a number of tasks in SNs, including sensor design, deployment, and data fusion. It enables real-time watermark checking and can be used in conjunction with a variety of watermarking protocols. It can also be applied to any collected multimodal data or data generated for simulation purposes. Finally, the technique is adaptive, optimization-intensive, and resilient against attack. Through simulation and prototyping we demonstrate the effectiveness of active watermarking on three important sensor network tasks: location discovery, navigation, and light characterization.

1Outside Adviser (non-EECS), UCLA

Send mail to the author : (farinaz@eecs.berkeley.edu)

Efficient Localized Network Discovery for Wireless Ad Hoc Sensor Networks

Farinaz Koushanfar and Miodrag Potkonjak1
(Professor Alberto L. Sangiovanni-Vincentelli)

Network discovery is a fundamental task in wireless ad hoc (sensor) networks. The goal is to identify a part of the network with a particular user-specified set of graph theoretic and/or geometric properties. Representative examples of network discovery tasks include finding the shortest path between two points, a path or spanning tree through a specified subset of points, or all nodes in a given area, and areas that are not covered (holes and obstacles). We are developing efficient localized algorithms for all of these problems using the same basic systematic approach. The key new insight and building block is at each step of the process the goal is to visit nodes that provide new knowledge about the network structure, but also are likely to have neighbors that will facilitate the network discovery process. The likelihood is measured using a variety of weighted Monte Carlo integral calculations for evaluation of newly discovered areas. Although the algorithms are localized, they are able to efficiently build or estimate global objective functions.

The algorithms are flexible in the sense that they can be easily adapted to a variety of network, communication, and cost models. The effectiveness of the approach and algorithms is demonstrated on benchmarks using statistical scaling algorithms that quantify the tradeoff between the quality of the solution and the energy cost of the algorithm.

1Outside Adviser (non-EECS), UCLA

Send mail to the author : (farinaz@eecs.berkeley.edu)

Statistical Scaling Analysis of Localized Algorithms in Wireless Ad Hoc Sensor Networks

Farinaz Koushanfar and Miodrag Potkonjak1
(Professor Alberto L. Sangiovanni-Vincentelli)

Scaling can be defined as the quantitative characterization of properties, events, and mechanisms as the instance of the object under consideration increases its size. In many fields, from physics and computational biology to multiprocessor systems and the Internet, scaling is widely studied. Often, the key prerequisite for the application of an architecture, piece of system software, or an algorithm, is how it scales. Until now, scaling has not been systematically studied in the context of wireless ad hoc sensor networks.

From the design point of view, the key novelty is that our goal is not just to analyze how already existing algorithms and mechanisms scale, but also to develop insights and techniques for the development of scalable algorithms. From a methodological point of view, the main novelty is the use of statistical techniques for analysis of scaling, including non-parametric modeling and validation, sampling, correlation, and perturbation. Special emphasis is placed on localized algorithms. We introduce several generic techniques for the development of localized algorithms and study how they scale.

1Outside Adviser (non-EECS), UCLA

Send mail to the author : (farinaz@eecs.berkeley.edu)

Analog Platforms for Analog System-level Design

Fernando De Bernardinis
(Professor Alberto L. Sangiovanni-Vincentelli)
GSRC

System-level analog design is a process largely dominated by heuristics. Given a set of specifications/requirements that describe the system to be realized, the selection of an optimal implementation architecture comes mainly out of experience. Usually, what is achieved is just a feasible point at the system level, while optimality is sought locally at the circuit level. The reason for this is the difficulty in the analog world of knowing if something is realizable without actually attempting to design the circuit. The number of effects to consider and their complex interrelations make this problem approachable only through the experience coming from past designs. One of the main problems is that optimization at the system level is really hard because of the difficulties in abstracting single block behaviors at the system level and in estimating their performances (and feasibility) without further knowledge of the implementation architecture and topology.

The basic idea of the proposed methodology is to extend the concept of platforms developed in the digital world to analog contexts. With an analog platform (AP) [1] we indicate an architectural resource to map analog functionalities during early system level exploration phases and constrain exploration to the feasible space of the considered implementation (or set of implementations). Therefore, an AP consists of a set of behavioral models and of matching performance models. Behavioral models are abstracted parameterized models of the analog functionality which introduce at the functional level a number of non-idealities attributable to the implementation and not intrinsic in the functionality, such as distortion, bandwidth limitations, noise, etc.

We propose applying the AP paradigm to design cases from the BWRC and extending the methodology to capture more accurate design constraints. The activity should start by encapsulating the block architectures required for the candidate transceiver with the AP abstraction. For each block, a set of behavioral models has to be defined and implemented in some executable form, e.g., AMS languages or Simulink/Matlab. Then, a characterization policy and a sampling strategy have to be set up to generate performance models. Particular attention has to be focused on the interfaces of single blocks so that loading effects are properly considered and modeled. For example, the input stage of the mixer has to be considered when extracting the performance figures for the driving LNA, otherwise the loading effect present in the real implementation would not be estimated. For each block, different architectures should be modeled and merged in the platform stack. This allows having a level of abstraction in the platform stack where, for example, two or more LNA topologies are represented by the same functional model and by the union of the respective performance models. When operating at this level, a platform instance selection intrinsically performs architecture selection choosing a performance set achieved by architecture a rather than architecture b or c. At the system level, system optimization will be carried out using a non-linear optimization technique based on behavioral simulations. Possible candidates are simulated annealing and genetic algorithms, which are expected to perform well given the limited number of optimization parameters available at the system level. The challenging design of the reconfigurable radio-mobile terminal should emphasize the strengths and/or weaknesses of APs in evaluating tradeoffs over a wide range of opportunities.

[1]
L. Carloni, F. De Bernardinis, A. Sangiovanni-Vincentelli, and M. Sgroi, “The Art and Science of Integrated Systems Design,” European Solid-State Circuits Conf., Florence, Italy, September 2002.

More information (http://www.eecs.berkeley.edu/~fdb) or

Send mail to the author : (fdb@eecs.berkeley.edu)

Metropolis SystemC-based Simulator

Guang Yang, Daniele Gasperini1, Douglas Densmore, John Moondanos2, and Yosinori Watanabe3
(Professor Alberto L. Sangiovanni-Vincentelli)
GSRC

Metropolis is a design environment for heterogeneous embedded systems. It is more general than other design environments in the sense that it neither biases any application domain, nor favors any particular kind of model of computation. It defines a language called Metropolis MetaModel (MMM), which is one layer above other models of computation. Therefore, it is possible to model any model of computation with MMM. In fact, in Metropolis, MMM is taken as the design input and internal representation.

Starting from the MMM design input, validating the design is the first and most important step. For this purpose, the SystemC-based simulator is widely used in Metropolis. Currently, the SystemC-based simulator can generate simulation traces out of all possibilities resulting from the non-deterministic nature of MMM. The SystemC-based simulator is still under active development. The next step is having the ability to evaluate the performance and check the properties of a design. These require the handling of function-architecture mapping, quantity resolution, and constraints checking. The first two are coming from the concept of platform-based design, where function and architecture are completely separated. By doing a simulation of the mapping between them, it is possible to evaluate the cost of implementing one function by one particular architecture. Other than simulation, it is also sometimes desirable to check properties of a design formally. MMM provides such mechanisms and it would be nice if such mechanisms could be incorporated into the SystemC-based simulator.

1Visiting Scholar, Italy
2Visiting Industrial Fellow, Intel
3Outside Adviser (non-EECS), Cadence Berkeley Lab

Send mail to the author : (guyang@eecs.berkeley.edu)

Constraint-driven Synthesis of System-on-a-Chip Communication Architectures

Luca Carloni and Alessandro Pinto
(Professor Alberto L. Sangiovanni-Vincentelli)
Semiconductor Research Corporation

The design of the communication architecture is an essential step in the realization of a system-on-a-chip (SOC). The semiconductor industry is experiencing a paradigm shift from "computation-bound design" to "communication-bound design." The number of transistors that can be reached in a clock cycle, and not those that can be integrated on a chip, will drive the design process. In the context of a communication-based design methodology for SOC, we are developing the idea of constraint-driven communication synthesis. As logic synthesis was the key to the success of ASIC design in the VLSI era, we predict that the automatic synthesis of the on-chip communication architecture will be the key to the success of SOC design in the gigascale integration era. The goal of this research is to start with a system-level view of the SOC communication problem and automatically synthesize the best communication architecture among the SOC modules while considering both high level issues, such as communication topologies, protocol interfacing, resource sharing, as well as low level ones, such as metal layer allocation, wire buffering, and wire pipelining.

The first step in constraint-driven communication synthesis is the specification of the key communication parameters that govern the interactions among the SOC modules as a set of constraints for the synthesis problem. Then, the synthesis process proceeds in two stages. First, the optimal high-level architecture structure is derived while considering the different communication topologies, the possibility of mixing and matching them, the role of resource sharing (e.g., time multiplexing), the choice of the various communication protocols, and the needs of interfacing incompatible protocols. Notice that since the notion of optimality may vary from one design to another, depending on the designers' priorities (area, power, performance, complexity), the cost figure of a communication topology must be a configurable parameter. Once the best communication architecture is established, the focus shifts to finding the best low-level implementation based on the features that are available with the given technology process. In other words, this step corresponds to designing the global interconnect among the SOC modules and includes exploring the characteristics of the various metal layers, the insertion of buffers (stateless repeaters) on long wires, and the pipelining of (even) longer wires by means of latches (stateful repeaters).

The present research project relies on several results from our previous work. In particular, we have recently presented a generic theoretical framework to support constrained-driven communication synthesis as well as its application to the case of bus-based communication topologies [1]. Also, we plan to incorporate key results from our research on latency-insensitive design [2,3] and interface-based design [4].

[1]
A. Pinto, L. P. Carloni, and A. L. Sangiovanni-Vincentelli, "Constraint-driven Communication Synthesis," Proc. Design Automation Conf., Montreal, Canada, September-October 2002.
[2]
L. P. Carloni, K. L. McMillan, and A. L. Sangiovanni-Vincentelli, "Theory of Latency-Insensitive Design," IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, Vol. 20, No. 9, September 2001.
[3]
L. P. Carloni, K. L. McMillan, A. Saldanha, and A. L. Sangiovanni-Vincentelli, "A Methodology for Correct-by-Construction Latency-Insensitive Design," ed. A. Kuehlmann et al., The Best of ICCAD: 20 Years of Excellence in Computer-Aided Design, Kluwer Academic Publishers, 2003.
[4]
R. Passerone, J. A. Rowson, and A. L. Sangiovanni-Vincentelli, "Automatic Synthesis of Interfaces between Incompatible Protocols," Proc. Design Automation Conf., San Francisco, CA, June 1998.

More information (http://www-cad.eecs.berkeley.edu/~lcarloni) or

Send mail to the author : (lcarloni@eecs.berkeley.edu)

Coping with Latency in System-on-a-Chip Design

Luca Carloni
(Professor Alberto L. Sangiovanni-Vincentelli)
Semiconductor Research Corporation

As commercial demand for system-on-a-chip (SOC)-based products grows, the effective reuse of existing intellectual property design modules (also known as IP cores) is essential to meet the challenges posed by deep-submicron (DSM) technologies and to complete a reliable design within time-to-market constraints. An IP core must be both flexible, to collaborate with other modules within different environments, and independent from the particular details of one-among-many possible implementations. The prerequisite for easy trade, reuse, and assembly of IP cores is the ability to assemble predesigned components with little or no effort. The consequent challenge is addressing the communication and synchronization issues that naturally arise while assembling predesigned components. We believe that the semiconductor industry will experience a paradigm shift from computation- to communication-bound design: The number of transistors that a signal can reach in a clock cycle--not the number that designers can integrate on a chip--will drive the design process. The strategic importance of developing a communication-based design methodology naturally follows.

An essential element of communication-based design is the encapsulation of predesigned functional modules within automatically generated interface structures. Such a strategy ensures a correct-by-construction composition of the system. Latency-insensitive design [1] and the recycling paradigm [2] are a step in this direction. High-end microprocessor designers have traditionally anticipated the challenges that ASIC designers are going to face in working with the next process generation. Latency is increasingly affecting the design of state-of-the-art microprocessors (latency, for example, drove the design of so-called drive stages in the new hyperpipelined Netburst microarchitecture of Intel's Pentium 4) and will become a shaping force for SOC architectures [3]. On the one hand, the increasing impact of latency variations will drive architectures toward modular designs with an explicit global latency mechanism. In the case of multiprocessor architectures, latency variation will lead the designers to expose computation/communication tradeoffs to the software compilers. At the same time, the focus on latency will open the way to new synthesis tools that can automatically generate the hardware interfaces responsible for implementing the appropriate synchronization and communication strategies, such as channel multiplexing, data coherency, and so on. All these considerations lead us to propose a design methodology that guarantees the robustness of the system's functionality and performance with respect to arbitrary latency variations [4].

[1]
L. P. Carloni, K. L. McMillan, and A. L. Sangiovanni-Vincentelli, "Theory of Latency-Insensitive Design," IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, Vol. 20, No. 9, September 2001.
[2]
L. P. Carloni and A. L. Sangiovanni-Vincentelli, "Performance Analysis and Optimization of Latency Insensitive Systems," Proc. Design Automation Conf., Los Angeles, CA, June 2000.
[3]
L. P. Carloni and A. L. Sangiovanni-Vincentelli, "Coping with Latency in SOC Design," IEEE Micro, special issue on systems on chip, Vol. 22, No. 5, September-October 2002.
[4]
L. P. Carloni, K. L. McMillan, A. Saldanha, and A. L. Sangiovanni-Vincentelli, "A Methodology for Correct-by-Construction Latency-Insensitive Design," ed. A. Kuehlmann et al., The Best of ICCAD--20 Years of Excellence in Computer-Aided Design, Kluwer Academic Publishers, 2003.

More information (http://www-cad.eecs.berkeley.edu/~lcarloni) or

Send mail to the author : (lcarloni@eecs.berkeley.edu)

The Theory of Latency Insensitive Design

Luca Carloni and Kenneth L. McMillan1
(Professor Alberto L. Sangiovanni-Vincentelli)
Semiconductor Research Corporation

The theory of latency insensitive design is the foundation of a new correct-by-construction methodology to design complex systems by assembling intellectual property components [1]. Latency insensitive designs are synchronous distributed systems and are realized by composing functional modules that exchange data on communication channels according to an appropriate protocol [2]. The protocol works on the assumption that the modules are stallable, a weak condition to ask them to obey. The goal of the protocol is to guarantee that latency insensitive designs composed of functionally correct modules behave correctly independent of the channel latencies. This allows us to increase the robustness of a design implementation, because any delay variations of a channel can be "recovered" by changing the channel latency while the overall system functionality remains unaffected. As a consequence, an important application of the proposed theory is represented by the latency insensitive methodology to design large digital integrated circuits by using deep sub-micron technologies [3].

[1]
L. P. Carloni, K. L. McMillan, and A. L. Sangiovanni-Vincentelli, "Theory of Latency-Insensitive Design," IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, Vol. 20, No. 9, September 2001.
[2]
L. P. Carloni, K. L. McMillan, and A. L. Sangiovanni-Vincentelli, "Latency Insensitive Protocols," Proc. Int. Conf. Computer-Aided Verification, Trento, Italy, July 1999.
[3]
L. P. Carloni, K. L. McMillan, A. Saldanha, and A. L. Sangiovanni-Vincentelli, "A Methodology for Correct-by-Construction Latency-Insensitive Design," Proc. ICCAD, San Jose, CA, November 1999.
1Cadence Berkeley Laboratories

More information (http://www-cad.eecs.berkeley.edu/~lcarloni/) or

Send mail to the author : (lcarloni@eecs.berkeley.edu)

Simulation Techniques for Electromagnetic Interference (EMI) and Signal Integrity (SI) in High-Speed Electronic Circuits

Luca Daniel and Jacob White1
(Professor Alberto L. Sangiovanni-Vincentelli)
Semiconductor Research Corporation and MARCO Interconnect Focus Center

Electromagnetic interference (EMI) is becoming an exceptionally crucial issue in the design of modern electronic systems. Frequencies are continuously increasing, while integration trends are squeezing entire systems into extraordinarily high circuit densities. In the conventional design methodology, electromagnetic compatibility (EMC) issues are addressed only after a prototype is built. At that stage, the traditional EMC remedies are confined to adding extra components, metal shields, metal plans, or even redesigning the entire system, with a potentially significant impact both on the cost and on the time-to-market of the products. It is our firm opinion that EMC must instead be addressed as early as possible during the design phase, and not after. EMI simulation could shorten the design time, allowing the analysis of circuits before manufacturing.

Large and expensive electronic equipment can effectively employ standard EMC solutions. But smaller, high-volume, low-priced electronic devices, automotive electronics, and most of the embedded systems cannot afford those costly solutions. Such devices are the most susceptible to EMI problems and the most sensitive to post-prototype EMC added costs. Unfortunately, they are also the most difficult to simulate with respect to EMI problems since they require "full-board" capabilities, and no tool is available to date for such task.

Full-board EMI simulation capability would therefore be instrumental in promptly verifying EMC compliance during the very first stages of the design of high-speed PCBs and IC-packages. For this application, we are investigating the use of integral equation methods:

  1. Our research focuses on minimizing the number of unknowns needed to model each conductor in the system. We have found two alternative set of basis functions [1-3], requiring 16 to 20 times fewer unknowns than the classical thin filaments discretization, for the same final accuracy. In our method, we use as basis functions some of the physically admissible solutions of the diffusion equation for the current density in the interior of the conductors.
  2. We are currently implementing our method based on our new basis functions. We solve the resulting linear system using the very efficient Krylov subspace iterative methods. The complexity of the algorithm is dominated by an O(N2) matrix-vector product operation. We propose to further reduce the computational complexity of the iterative method. Fast algorithms exist for such products with complexity O(Nlog(N)). Such algorithms have been already successfully implemented in tools for the static capacitance extraction problem (FASTCAP) and for the magneto-quasi-static problem (FASTHENRY). We plan to modify and extend one such algorithm, Precorrected-FFT, to our full-wave EMI analysis problem.
Desirable results from an EMI analysis range from the characterization of the spectrum emissions observed on a measurement sphere at 10 meters, to the generation of a model of the interconnect structures for instance to be later used within a non-linear time domain simulator.

To address efficiently the first specification, we propose to use an adjoint method to calculate a set of transfer functions from the thousands of circuit inputs (e.g., the pins of the ICs) to the tens of observation points on the measurement sphere.

To address the second specification, we are working on the generation of "dynamical linear systems" that mimic the same behavior of the original interconnect structure, but have a state vector orders of magnitude smaller. In some recent papers of ours, we show how to generate guaranteed passive reduced order models from originally passive structures including dielectrics [4], and for distributed systems with frequency dependent matrices [5] (as generated for instance when accounting for substrate effects or for fullwave effects). Finally we are developping techniques for "parameterized" model order reduction techniques [6] for enabling optimization of interconnect structures.

[1]
L. Daniel, A. Sangiovanni-Vincentelli, and J. White, "Interconnect Electromagnetic Modeling Using Conduction Modes as Global Basis Functions," IEEE Topical Meeting on Electrical Performance of Electronic Packages, Scottsdale, AZ, October 2000.
[2]
L. Daniel, J. White, and A. Sangiovanni-Vincentelli, "Conduction Modes Basis Functions for Efficient Electromagnetic Analysis of On-Chip and Off-Chip Interconnect," Proc. Design Automation Conf., Las Vegas, NV, June 2001.
[3]
L. Daniel, A. Sangiovanni-Vincentelli, and J. White, "Proximity Templates for Modeling of Skin and Proximity Effects on Packages and High Frequency Interconnect," ," ICCAD, San Jose, CA, November 2002.
[4]
L. Daniel, A. Sangiovanni-Vincentelli, and J. White, "Techniques for Including Dielectrics when Extracting Passive Low-Order Models of High Speed Interconnect," ICCAD, San Jose, CA, November 2001.
[5]
L. Daniel, J. Phillips, "Guaranteed Passive Model Order Reduction for Strictly Passive and Causal Distributed Systems," Proc. Design Automation Conf., New Orleans, June 2002.
[6]
L. Daniel, C. Ong, S. Low, K. Lee, J. White, "Geometrically Parameterized Interconnect Performance Models for Interconnect Synthesis," International Symposium on Physical Design, San Diego, CA, May 2002.
1Professor, Massachusetts Institute of Technology

More information (http://www.eecs.berkeley.edu/~dluca) or

Send mail to the author : (dluca@eecs.berkeley.edu)

Synthesis of Robust Control Systems with Computation Constraints

Luigi Palopoli1, Claudio Pinello, and Antonio Bicchi2
(Professor Alberto L. Sangiovanni-Vincentelli)
GSRC

We address the problem of synthesizing real-time embedded controllers, taking into account constraints deriving from the implementation platform. Specifically, we address the problem of controlling a set of independent systems by using a shared single CPU processor board. Assuming a time-triggered model of computation for control processes and a real-time preemptive scheduling policy, the problem of optimizing robustness of the controlled systems is formulated. Decision variables of the optimization problem are the processes' activation periods and the feedback gains. The analytical formulation of the problem enables an efficient numerical solution based on a branch and bound scheme. The resulting design is directly implementable without performance degradations that may otherwise arise due to scheduling and execution delays.

1Postdoctoral Researcher, ReTiS Lab-Scuola Superiore S. Anna, Italy
2Professor, Università di Pisa, Italy

Send mail to the author : (pinello@eecs.berkeley.edu)

Interaction Between Heterogeneous Models: A Formal Approach

Roberto Passerone and Alessandro Pinto
(Professor Alberto L. Sangiovanni-Vincentelli)
GSRC

Embedded systems often exhibit behaviors that are best described using different formalisms and models of computation. While each model offers specialized and efficient techniques to solve particular problems in their domain of application, the interaction across models is made more difficult by their differences. As a result, this interaction is not yet well understood and is often not formally defined. In this project we seek to determine a consistent way to define interactions across different models.

We regard a system as the composition of computational domains. Each computational domain is an island in which the semantics of the coordination and communication among agents is defined, and differs from the semantics of other domains. This definition is generic and covers many possible applications: from communication between models of computation as mathematical domains, to co-simulation of applications described in different programming languages.

We use the framework of trace algebra to describe the semantic domain of each computational domain. We then investigate ways to compose domains in order to obtain additional hybrid domains that exhibit properties from their components. Constructions of this kind include products of algebras and their disjoint sums. We then study the composition of heterogenous agents (agents drawn from different computational domains) in the context of a hybrid domain, and define identity elements with respect to the operation of composition. The objective of this research is to derive correct conversion mechansisms, or communicators, from the identities in the hybrid domain.

[1]
J. Burch, R. Passerone, and A. Sangiovanni-Vincentelli, "Overcoming Heterophobia: Modeling Concurrency in Heterogeneous Systems," Proc. Application of Concurrency to System Design, Newcastle, UK, June 2001.

Send mail to the author : (apinto@eecs.berkeley.edu)

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.

[1]
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.
[2]
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.
[3]
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 : (roby@eecs.berkeley.edu)

Communication-driven Hardware Synthesis: A New Processor Design Methodology

Trevor Meyerowitz
(Professor Alberto L. Sangiovanni-Vincentelli)
SRC (Intel)

Processor design today is very much an art form. The architect comes up with a design to support an instruction set, creates a high level simulator, and then passes it on to the design team to implement. This process makes it hard for the architect to explore the design space, and requires the design team to rewrite much of the architect’s model. In this research we present a communication-aware methodology for turning a description of an instruction set architecture (ISA) into a potentially complicated microarchitectural implementation. The three major goals of this work are: reusability, correct by construction designs, and the automatic generation of control and binding logic.

Previous work has produced simple in-order pipelines along with their associated control logic. Through the methodology, we aim to achieve more complicated features such as out-of order execution, speculation, and caching. Instead of aiming for automatic synthesis, we break the process into a series of steps, allowing the design decisions to be considered one at a time, and be viewed separately from the functionality of the system. Each step transforms from the previous step through refinement, mapping, or relaxation


More information (http://www-cad.eecs.berkeley.edu/~tcm) or

Send mail to the author : (tcm@eecs.berkeley.edu)

Communication-based Analog Design

Yanmei Li and Fernando De Bernardinis
(Professor Alberto L. Sangiovanni-Vincentelli)
GSRC

To enable design reusability and system integration, we apply the communication based design (CBD) methodology to analog design, i.e., CBD-A. In CBD, formal specifications are used and communication adapters are introduced to deal with the mismatch between communicating blocks without modifying the incompatible blocks. Such adapters enable the interaction between the incompatible blocks. In CBD-A, similar adapters are inserted between analog blocks. To provide suitable adapters, a formal description of the analog interface is required, such as DC level, dynamic range, driving/loading capabilities, biasing requirements, and so on. On the other hand, since the analog block acting as an adapter introduces some non-ideal effects which will cause degradation on the signal (e.g., SNR degradation), we need to know the specifications of the adaptation block in terms of inserted noise, distortion, CMRR, etc.

Currently, we are exploring CBD-A based on an available hardware platform, field programmable analog array (FPAA). Its unique feature is to implement analog functions in reconfigurable architecture. So, it gives us the analog equivalent of FPGA. The FPAA is based on CMOS-based fully differential switched-capacitor technology with an analog switch fabric.

To implement analog interface adapters with FPAA, some dedicated simulation strategies based on FPAA behavioral models are developed to ensure fast and accurate estimations of the non-ideal effects introduced by specific FPAA configurations. Another part of this research is to formalize the analog interface specification from the electrical point of view and also formalize the signal degradation. We plan to develop a synthesis mechanism to map analog system descriptions and interface specifications onto an FPAA platform.


Send mail to the author : (yanmei@eecs.berkeley.edu)