<![CDATA[
<BODY>
<H3><A HREF="../../../../../main_ss.htm">DAC 97 Home Page</A></BR>
DAC 97 :
[ <A HREF="dactoc.htm">Table of Contents </A> ]
[ <A HREF="dacsess.htm">Session Index</A> ]
[ <A HREF="dacai.htm">Author Index</A> ]</H3>
<HR>
<H2>ABSTRACTS DAC 97</H2>
<B>
Sessions:
[<A HREF="#ceo">Panel</A>]
[<A HREF="#sess1">1</A>]
[<A HREF="#sess2">2</A>]
[<A HREF="#sess3">3</A>]
[<A HREF="#sess4">4</A>]
[<A HREF="#sess5">5</A>]
[<A HREF="#sess6">6</A>]
[<A HREF="#sess7">7</A>]
[<A HREF="#sess8">8</A>]
[<A HREF="#sess9">9</A>]
[<A HREF="#sess10">10</A>]
[<A HREF="#sess11">11</A>]
[<A HREF="#sess12">12</A>]
[<A HREF="#sess13">13</A>]
[<A HREF="#sess14">14</A>]
[<A HREF="#sess15">15</A>]
[<A HREF="#sess16">16</A>]
[<A HREF="#sess17">17</A>]
[<A HREF="#sess18">18</A>]
[<A HREF="#sess19">19</A>]
[<A HREF="#sess20">20</A>]
[<A HREF="#sess21">21</A>]
[<A HREF="#sess22">22</A>]
[<A HREF="#sess23">23</A>]
[<A HREF="#sess24">24</A>]
[<A HREF="#sess25">25</A>]
[<A HREF="#sess26">26</A>]
[<A HREF="#sess27">27</A>]
[<A HREF="#sess28">28</A>]
[<A HREF="#sess29">29</A>]
[<A HREF="#sess30">30</A>]
[<A HREF="#sess31">31</A>]
[<A HREF="#sess32">32</A>]
[<A HREF="#sess33">33</A>]
[<A HREF="#sess34">34</A>]
[<A HREF="#sess35">35</A>]
[<A HREF="#sess36">36</A>]
[<A HREF="#sess37">37</A>]
[<A HREF="#sess38">38</A>]
[<A HREF="#sess39">39</A>]
[<A HREF="#sess40">40</A>]
[<A HREF="#sess41">41</A>]
[<A HREF="#sess42">42</A>]
[<A HREF="#sess43">43</A>]
[<A HREF="#sess44">44</A>]
[<A HREF="#sess45">45</A>]
[<A HREF="#sess46">46</A>]
[<A HREF="#sess47">47</A>]
[<A HREF="#sess48">48</A>]
[<A HREF="#sess49">49</A>]
[<A HREF="#tutorials">Tutorials</A>]<P>
</B>
<HR>
<H2>Panel:
<A HREF="order.htm" NAME="ceo"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="98_0">
AN EXECUTIVE VIEW OF THE EDA INDUSTRY
</A></H2>
Chair: <I>A. Richard Newton</I><BR>
Organizers: <I>Mike Murray</I><BR>
Panelists: <I>Joseph Costello, Aart de Geus, William Herman,
Gerald Hsu, Keith Lobo, Walden Rhines</I><P>
<HR>
<H2>Session 1:<A NAME="sess1">
SEQUENTIAL SYNTHESIS
</A></H2>
Chair: <I>Richard L. Rudell</I><BR>
Organizers: <I>Fabio Somenzi, Sharad Malik</I><P>
<DL>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<a href="http://www.ee.iastate.edu/~sachin/DAC97.html"><img src="../../../../../icons/url.gif"></a>
<A HREF="order.htm" NAME="01_1">
<B>1.1 An Improved Algorithm For Minimum-Area Retiming</B></A><BR>
<DD><I>Naresh Maheshwari, Sachin S. Sapatnekar</I><P>
The concept of improving the timing behavior of a circuit by relocating
flip-flops is called retiming and was first presented by Leiserson and Saxe.
The ASTRA algorithm proposed an alternative view of retiming using the
equivalence between retiming and clock skew optimization. This work defines
the relationship between the Leiserson-Saxe and the ASTRA approaches and
utilizes it to solve the problem of retiming for minimum area. The new
algorithm, Minaret, uses the linear programming formulation of the
Leiserson-Saxe approach. The underlying philosophy of the ASTRA approach is
incorporated to reduce the number of variables and constraints in the linear
program. This reduction in the size of the linear program makes Minaret space
and time efficient, enabling minimum area retiming of circuits with over
56,000 gates in under 15 minutes.<P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="01_2">
<B>1.2 Efficient Latch Optimization Using Exclusive Sets</B></A><BR>
<DD><I>Ellen M. Sentovich, Horia Toma, Gérard Berry</I><P>
Controller circuits synthesized from high-level languages often have many more
latches than the minimum, with a resulting sparse reachable state space that
has a particular structure. We propose an algorithmthat exploits this structure
to remove latches. The reachable state set (RSS) is much easier to compute for
the new, smaller circuit and can be used to efficiently compute the RSS of the
original. Thus we provide a method for obtaining the RSS, and two different
initial implementations from which to begin logic optimization.<P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="01_3">
<B>1.3 Sequence Compaction for Probabilistic Analysis of Finite-State Machines</B></A><BR>
<DD><I>Diana Marculescu, Radu Marculescu, Massoud Pedram</I><P>
The objective of this paper is to provide an effective technique for accurate
modeling of the external input sequences that affect the behavior of Finite
State Machines (FSMs). The proposed approach relies on adaptive modeling of
binary input streams as Markov sources of fixed-order. The input model itself
is derived through a one-pass traversal of the input sequence and can be used
to generate an equivalent sequence, much shorter in length compared to the
original sequence. The compacted sequence can be subsequently used with any
available simulator to derive the steady-state and transition probabilities,
and the total power consumption in the target circuit. As the results
demonstrate, large compaction ratios of orders of magnitude can be obtained
without a significant loss (less than 3% on average) in the accuracy of
estimated values.<P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="01_4">
<B>1.4 Synthesis of Speed-Independent Circuits from STG-unfolding Segment</B></A><BR>
<DD><I>Alexei Semenov, Alexandre Yakovlev, Enric Pastor, Marco A. Pena,
Jordi Cortadella</I><P>
This paper presents a novel technique for synthesis of speed-in-dependent
circuits. It is based on partial order representation of the state graph called
STG-unfolding segment. The new method uses approximation technique to speed up
the synthesis process. The method is illustrated on the basic implementation
architecture. Experimental results demonstrating its efficiency are presented
and discussed.<P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="01_5">
<B>1.5 Telescopic Units: Increasing the Average Throughput of Pipelined Designs by
Adaptive Latency Control</B></A><BR>
<DD><I>Luca Benini, Enrico Macii, Massimo Poncino</I><P>
This paper presents a technique, alternative to performance-driven synthesis,
that allows to drastically increase the average throughput of combinational
logic blocks by transforming fixed-latency units into variable-latency ones
that run with a faster clock cycle. The transformation is fully automatic and
can be used in conjunction with traditional design techniques, such as
pipelining, to improve the overall performance of speed-critical systems.
Results, obtained on a large set of benchmark circuits, are very promising.<P>
</DL>
<HR>
<H2>Session 2:<A NAME="sess2">
INTERCONNECT MODELING
</A></H2>
Chair: <I>Lawrence T. Pileggi</I><BR>
Organizers: <I>Andrew Yang, Jacob White</I><P>
<DL>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="02_1">
<B>2.1 Zeros and Passivity of Arnoldi-Reduced-Order Models for Interconnect Networks</B></A><BR>
<DD><I>Ibrahim M. Elfadel, David D. Ling</I><P>
CAD tools and research in the area of reduced-order modeling of large linear
interconnect networks have evolved from merely finding a Padé
approximation for the given network transfer function to finding an approximate
transfer function that preserves such circuit-theoretic properties of the
network as stability, passivity, and RLC synthesizability. In particular,
preserving passivity guarantees that the reduced-order models will be
well-behaved when embedded back in the circuit where the interconnect network
originated. While stability can be ascertained by studying the poles of the
reduced-order transfer function, passivity depends on both the poles and zeros
of the network driving-point impedance. In this paper, we present a novel
method for studying the zeros of reduced-order transfer functions and show how
it yields conclusions about passivity and synthesizability. Moreover, in order
to obtain a guaranteed-passive reduced-order model for multiport RC networks,
a new algorithm based on the Arnoldi iteration is presented. This algorithm is
as computationallyefficient as the one used to generate guaranteed-stable
reduced-order models [1].<P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="02_2">
<B>2.2 Preservation of Passivity During RLC Network Reduction via Split Congruence
Transformations</B></A><BR>
<DD><I>Kevin J. Kerns, Andrew T. Yang</I><P>
None of the existing network reduction tools preserve passivity for RLC
networks. The loss of passivity can be a serious problem because simulations
of the reduced networks may encounter time step too small errors. This
paper presents a set of transformations called Split Congruence
Transformations (SCTs) which can be used to accurately reduce a RLC
network while preserving passivity.<P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="02_3">
<B>2.3 Lumped Interconnect Models Via Gaussian Quadrature</B></A><BR>
<DD><I>Keith Nabors, Tze-Ting Fang, Hung-Wen Chang, Kenneth S. Kundert, Jacob K. White</I><P>
This paper presents a new Gaussian quadrature method for interconnect modeling
which applies to one-dimensional distributions of circuit element values, the
line structures often used to model interconnect wires. The method takes a line
circuit, which may be an arbitrary combination of lumped and distributed
elements, and produces a small lumped model whose transfer and input
characteristics approximately match those of the original circuit. The same
algorithm may be used to generate lumped models for distributed elements, or
to reduce long chains of lumped elements. The method also applies to
one-dimensional distributions of coupling circuit elements, and, in general,
to any one-dimensional distribution of circuit element quantities. Several
examples demonstrate that the quadrature-based method is capable of
automatically generating compact RC, LC and RLC line models with arbitrary
accuracy.<P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="02_4">
<B>2.4 Calculating Worst-Case Gate Delays Due to Dominant Capacitance Coupling</B></A><BR>
<DD><I>Florentin Dartu, Lawrence T. Pileggi</I><P>
In this paper we develop a gate level model that allows us to determine the
best and worst case delay when there is dominant interconnect coupling.
Assuming that the gate input windows of transition are known, the model can
predict the worst and best case noise, as well as the worst and best case
impact on delay. This is done in terms of a Ceff based gate model under general
RC interconnect loading conditions.<P>
</DL>
<HR>
<H2>Session 3:<A NAME="sess3">
NOVEL TECHNIQUES FOR SOFTWARE SCHEDULING
</A></H2>
Chair: <I>Gaetano Borriello</I><BR>
Organizers: <I>Rajesh K. Gupta, Luciano Lavagno</I><P>
<DL>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="03_1">
<B>3.1 Schedule Validation for Embedded Reactive Real-Time Systems</B></A><BR>
<DD><I>Felice Balarin, Alberto Sangiovanni-Vincentelli</I><P>
Task scheduling for reactive real time systems is a difficult problem due to
tight constraints that the schedule must satisfy. A static priority scheme is
proposed here that can be formally validated. The method is applicable both for
preemptive and non-preemptive schedules and is conservative in the sense that a
valid schedule may be declared invalid, but no invalid schedule may be declared
valid. Experimental results show that the run time of our validation method is
negligible with respect to other steps in system design process, and compares
favorably with other methods of schedule validation.<P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="03_2">
<B>3.2 Incorporating Imprecise Computation into System-Level Design Of
Application-Specific Heterogeneous Multiprocessors</B></A><BR>
<DD><I>Yosef Gavriel Tirat-Gefen, Diogenes C. Silva, Alice C. Parker</I><P>
This paper introduces a basic mixed integer-linear model (MILP) to design
application-specific heterogeneous multiprocessors (ASHM) allowing imprecise
computation of tasks executed in a non-preemptive mode. The proposed model was
used in the development of a genetic algorithm integrated into the tool set
MEGA that uses soft computing techniques for design of optimal/near-optimal
ASHMs subject to constraints on performance, cost and output-data quality.<P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="03_3">
<B>3.3 Data Memory Minimisation for Synchronous Data Flow Graphs Emulated on
DSP-FPGA Targets</B></A><BR>
<DD><I>Marleen Adé, Rudy Lauwereins, J.A. Peperstraete</I><P>
The paper presents an algorithm to determine the close-to-smallest possible
data buffer sizes for arbitrary synchronous data flow (SDF) applications, such
that we can guarantee the existence of a deadlock free schedule. The presented
algorithm fits in the design flow of GRAPE, an environment for the emulation
and implementation of digital signal processing (DSP) systems on arbitrary
target architectures, consisting of programmable DSP processors and FPGAs.
Reducing the size of data buffers is of high importance when the application
will be mapped on Field Programmable Gate Arrays (FPGA), since register
resources are rather scarce.<P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="03_4">
<B>3.4 An Efficient Implementation of Reactivity for Modeling Hardware in the
Scenic Design Environment</B></A><BR>
<DD><I>Stan Liao, Steve Tjiang, Rajesh K. Gupta</I><P>
Reactivity is one of the key features of hardware description languages.
We present an efficient implementation of reactivity in the Scenic framework
that allows the system designer to model hardware blocks. Scenic allows the
designer to use C++ to model mixed hardware/software systems with a C++
compiler and a small library and without the need of a complex event-driven
run-time kernel often found embedded in hardware description languages (HDL)
such as VHDL and Verilog. Moreover, Scenic hardware descriptions can be easily
mapped to HDL and synthesized into hardware implementations using commercially
available tools. In this paper we present Scenics implementation of concurrency
(signals and processes) and reactivity (waiting and watching). When C++ is used
as an HDL, context-switching overhead can become a significant performance
issue during simulation. We introduce the notion of delayed expression objects,
or lambdas, to reduce context-switching. Examples and experimental results are
presented to show the utility and simulation efficiency using the Scenic
framework.<P>
</DL>
<HR>
<H2>Session 4:<BR>
<A HREF="order.htm" NAME="sess4"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="04_0">
PANEL: LOW-POWER DESIGN TOOLS: WHERE IS THE IMPACT?
</A></H2>
Chair: <I>Jan M. Rabaey</I><BR>
Organizer: <I>Nanette Collins</I><BR>
Panelists: <I>Bill Bell, Jerry Frenkil, Vassilios Gerousis,
Massoud Pedram, Deo Singh, Jim Sproch</I><P>
<DL><DD>
Power dissipation is rapidly becoming one of the most significant problems in
IC design, and this in portables as well as ASIC and high-performance
microprocessor platforms. In recent years, we have witnessed the emergence of
a variety of design methods and design automation tools to keep dissipation
within bounds. This might give the impression that power minimization is a
solved issue, both from a design and a design automation perspective.
Unfortunately, the truth is far from that. The next-generation designs are
destined to be even more challenging from a power-dissipation perspective and
novel solutions will be needed to meet the challenges. This in turn will
require innovative EDA tools and methodologies. This panel, composed of
designers, CAD managers and EDA manufacturers, addresses the most compelling
issues in low-power low-energy design automation, including what effectively
works in the real-world and what does not. The discussion also focuses on what
breakthroughs are needed for the next-generation designs.<P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="04_1">
<B>4.1 Embedded Tutorial: Tools and Methodologies for Low Power Design</B></A><BR>
<DD><I>Jerry Frenkil</I><P>
Designing for low power has become increasingly important in a wide variety of
applications, including wireless telephony, mobile computing, high performance
computing, and high speed networking. Despite reductions in power supply
voltages, power consumption continues to rise and demands increased support
from EDA tools and methodologies. Various tools have emerged to address
different levels of the power problem, yet conventional methodologies often
focus on the low leverage aspects. This paper will survey existing commercial
tools used in low power design and present them in the context of an
architecture focused low power design methodology.<P>
</DL>
<HR>
<H2>Session 5:<A NAME="sess5">
SIMULATION TECHNIQUES FOR MICROPROCESSORS
</A></H2>
Chair: <I>Haruyuki Tago</I><BR>
Organizers: <I>Haruyuki Tago, Neil Weste</I><P>
<DL>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="05_1">
<B>5.1 A C-Based RTL Design Verification Methodology for Complex Microprocessor</B></A><BR>
<DD><I>Joon-Seo Yim, Yoon-Ho Hwang, Chang-Jae Park, Hoon Choi, Woo-Seung Yang,
Hun-Seung Oh, In-Cheol Park, Chong-Min Kyung</I><P>
As the complexity of high-performance microprocessor increases, functional
verification becomes more and more difficult and RTL simulation emerges as the
bottleneck of the design cycle. In this paper, we suggest C language-based
design and verification methodology to enhance the simulation speed instead of
the conventional HDL-based methodologies. RTL C model( StreC) describes the
cycle-based behaviors of synchronous circuits and is followed by model refining
and optimization using LifeTime Analyzer( LTA ) and Cleaner . The simulation
speed of cycle-based C model makes it possible to test the RTL design with
the 'real-world' application programs in the order-of-magnitude faster speed
than the commercial event-driven simulators. Using the proposed functional
verification methodology, HK486, an intel 80486-compatible microprocessor
was successfully designed and verified.<P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="05_2">
<B>5.2 Hierarchical Random Simulation Approach for the Verification Of S/390 CMOS
Multiprocessors</B></A><BR>
<DD><I>Jörg Walter, Jens Leenstra, Gerhard Döttling, Bernd Leppla,
Hans-Jürgen Münster, Kevin Kark, Bruce Wile</I><P>
In this paper an approach is presented for the hierarchical verification of the
memory control units, I/O adapters and processor interconnect units as found in
multiprocessor computer systems. It is shown how such units could be verified
better and faster by the introduction of random executable timing diagrams and
associated CAD tool support. Furthermore, it is shown how the timing diagrams
for the unit network verification are easily derived from the timing diagrams
specified for the units. The multiprocessor hardware test showed the
effectiveness of the proposed verification approach.<P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="05_3">
<B>5.3 Efficient Testing of Clock Regenerator Circuits in Scan Designs</B></A><BR>
<DD><I>Rajesh Raina, Robert Bailey, Charles Njinda, Robert Molyneaux, Charlie Beh</I><P>
This paper describes the use of a high-level view (functional view) of a clock
regenerator circuit for generating effective and inexpensive manufacturing
tests. It is shown that the tests gen-erated from the traditional, structural
view add hardware overhead, increase design time and potentially lower
effective yield when compared to the tests generated from the functional view.
A test generation procedure is described and successfully used on a
microprocessor design.<BR>
Index terms : Microprocessor Testing, Test Pattern Generation, Fault
Simulation, Clocks, Clock Regenerators.<P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="05_4">
<B>5.4 A Real-Time RTL Engineering-Change Method Supporting On-Line Debugging for
Logic-Emulation Applications</B></A><BR>
<DD><I>Wen-Jong Fang, Allen C.-H. Wu, Ti-Yen Yen</I><P>
In recent years, logic emulation has been widely used as a key design
verification methodology in many complex CPU, telecom, and multimedia design
projects. When using logic emulation for design verification, designers often
need toperform engineering changes as a result of design debugging of a design
specification modification. One of the essential issues to engineering changes
is the turn-around time. Ideally, after designers modify their designs, they
resume their debugging and verification tasks immediately. However, converting
a design from its Register-Transfer-Level (RTL) description to a target
emulator is a time-consuming procedure which may take hours. Such long
engineering-change turn-around times are unacceptable by the designers. In this
paper, we present a real-time RTL engineering-change method supporting on-line
debugging for logic-emulation applications. We propose a novel design method
which is able to link design data generated at different design stages in a
unified way. Using this method, the users can immediately locate the portion of
the circuit design affected by the design modification from its RTL
specification. This feature provides users with a fast time-to-debug
environment by significantly improving the efficiency of the engineering-change
process. We have developed aprototype system Quick ECO supporting interactive
on-line RTL engineering changes. Experimental results on a number of industrial
designs are reported to demonstrate the effectiveness of the proposed method.<P>
</DL>
<HR>
<H2>Session 6:<A NAME="sess6">
COMBINATIONAL LOGIC SYNTHESIS
</A></H2>
Chair: <I>Hamid Savoj</I><BR>
Organizers: <I>Andreas Kuehlmann, Massoud Pedram</I><P>
<DL>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="06_1">
<B>6.1 A Graph-Based Synthesis Algorithm for AND/XOR Networks</B></A><BR>
<DD><I>Yibin Ye, Kaushik Roy</I><P>
In this paper, we introduce a Shared Multiple Rooted XOR-based Decomposition
Diagram (XORDD) to represent functions with multiple outputs. Based on the
XORDD representation, we develop a synthesis algorithm for general Exclusive
Sum-of-Product forms (ESOP). By iteratively applying transformations and
reductions, we obtain a compact XORDD which gives a minimized ESOP. Our method
can synthesize larger circuits than previously possible. The compact ESOP
representation provides a form that is easier to synthesize for XOR heavy
multi-level circuit, such as arithmetic functions. We have applied our
synthesis techniques to a large set of benchmark circuits in both PLA and
combinational formats. Results of the minimized ESOP forms obtained from our
synthesis algorithm are also compared to the SOP forms generated by ESPRESSO.
Among the 74 circuits we have experimented with, the minimized ESOP's have
fewer product terms than those of SOP's in 39 circuits.<P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="06_2">
<B>6.2 Optimizing Designs Containing Black Boxes</B></A><BR>
<DD><I>Tai-Hung Liu, Khurram Sajid, Adnan Aziz, Vigyan Singhal</I><P>
We define a notion of equivalence for designs containing black boxes i.e.,
components whose functionality is not known; these arise naturally in the
course of hierarchical design. Using this notion, we describe a sound and
complete methodology for optimizing such designs.<P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="06_3">
<B>6.3 Solving Covering Problems Using LPR-Based Lower Bounds</B></A><BR>
<DD><I>Stan Liao, Srinivas Devadas</I><P>
Unate and binate covering problems are a special class of general integer
linear programming problems with which several problems in logic synthesis,
such as two-level logic minimization and technology mapping, are formulated.
Previous branch-and-bound methods for exactly solving these problems use
lower-bounding techniques based on finding maximal independent sets. In this
paper we examine lower-bounding techniques based on linear programming
relaxation (LPR) for the binate covering problem. We show that a combination of
traditional reductions (essentiality and dominance) and incremental computation
of LPR-based lower bounds can exactly solve difficult covering problems orders
of magnitude faster than traditional methods.<BR>
Keywords- overing problems, integer linear programming.<P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="06_4">
<B>6.4 Exact Coloring of Real-Life Graphs is Easy</B></A><BR>
<DD><I>Olivier Coudert</I><P>
Graph coloring has several important applications in VLSI CAD. Since graph
coloring is NP-complete, heuristics are used to approximate the optimum
solution. But heuristic solutions are typically 10% off, and as much as 100%
off, the minimum coloring. This paper shows that since real-life graphs appear
to be 1-perfect, one can indeed solve them exactly for a small overhead.<P>
</DL>
<HR>
<H2>Session 7:<A NAME="sess7">
INTERCONNECT PARASITIC EXTRACTION
</A></H2>
Chair: <I>Andrew T. Yang</I><BR>
Organizers: <I>Jacob White, Jason Cong</I><P>
<DL>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="07_1">
<B>7.1 Hierarchical 2-D Field Solution for Capacitance Extraction for VLSI
Interconnect Modeling</B></A><BR>
<DD><I>E. Aykut Dengi, Ronald A. Rohrer</I><P>
A hierarchical two-dimensional field solution technique is introduced for
capacitance extraction for VLSI interconnect modeling. As a basis for
compromise between the efficiency of Boolean rules-based extraction and the
accuracy of flat field solution, this hierarchical approach can handle
realistic conductor cross-sections and multiple conformal and/or planarized
dielectrics.<P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="07_2">
<B>7.2 Bounds for BEM Capacitance Extraction</B></A><BR>
<DD><I>Michael W. Beattie, Lawrence T. Pileggi</I><P>
In this paper we prove that simply discarding conductors beyond a certain
spacing during BEM capacitance extraction will result in a lower bound on the
self-capacitance calculations and an upper bound on the mutual capacitance
calculations that lie within that spacing. We prove that a potential-shift and
truncate scheme can yield bounds opposite to those for the truncate only case;
namely, an upper bound on the self capacitance and a lower bound on the mutual
capacitance that lies within the chosen spacing. The ease with which the upper
and lower bounds are calculated is shown, and their utility for selection of an
optimal window size is described. A metal shell is also presented here that
results in bounds similar to those of shift-truncate. We further propose a
new potential-shift function that yields increased approximation accuracy
compared to shift-truncate in many cases.<P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="07_3">
<B>7.3 SPIE: Sparse Partial Inductance Extraction</B></A><BR>
<DD><I>Zhijiang He, Mustafa Celik, Lawrence Pileggi</I><P>
Extracting the inductance of complex interconnect topologies is a formidable
task, and simulating the resulting dense partial inductance matrix is even more
difficult. Furthermore, it is well known that simply discarding smallest terms
to sparsify the inductance matrix can render the partial inductance matrix
indefinite and result in an unstable circuit model. In this paper, we describe
a methodology for incrementally generating a sparse partial inductance matrix
based on using moments about s=0 to determine when a sufficient number of
mutual inductances have been captured. The minimally required mutual
inductances are extracted for a provably stable model.<P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="07_4">
<B>7.4 A Fast Method of Moments Solver For Efficient Parameter Extraction Of MCMs</B></A><BR>
<DD><I>Sharad Kapur, Jinsong Zhao</I><P>
The Method of Moments (MoM) is often effectively used in the extraction of
passive components in modeling integrated circuits and MCM packaging. MoM
extraction, however, involves solving a dense system of linear equations, and
using direct factorization methods can be prohibitive for large problems. In
this paper, we present a Fast Method of Moments Solver (FMMS) for the rapid
solution of such linear systems. Our algorithm exploits the fact that the
integral equation kernels are locally 'smooth' and can be dramatically
compressed via the singular value decomposition (SVD). This greatly speeds up
the matrix-vector products in a Krylov-subspace iterative algorithm (e.g.,
GMRES). We demonstrate the efficiency and exibility of our scheme for the
modeling of embedded inductors in MCM-D. Results are presented to show that
the method isaccurate and can be two orders of magnitude faster than Gaussian
elimination and one order of magnitude faster than standard iterative schemes.<P>
</DL>
<HR>
<H2>Session 8:<A NAME="sess8">
ADVANCES IN TIMING ANALYSIS FOR EMBEDDED SOFTWARE
</A></H2>
Chair: <I>Wendell Baker, Hiroto Yasuura</I><BR>
Organizers: <I>Rajesh K. Gupta, Luciano Lavagno</I><P>
<DL>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="08_1">
<B>8.1 Embedded Tutorial: Static Timing Analysis of Embedded Software</B></A><BR>
<DD><I>Sharad Malik, Margaret Martonosi, Yau-Tsun Steven Li</I><P>
This paper examines the problem of statically analyzing the performance of
embedded software. This problem is motivated by the increasing growth of
embedded systems and a lack of appropriate analysis tools. We study different
performance metrics that need to be considered in this context and examine a
range of techniques that have been proposed for analysis. Very broadly these
can be classified into path analysis and system utilization analysis techniques.
It is observed that these are interdependent, and thus need to be considered
together in any analysis framework.<P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<a href="http://www.ee.princeton.edu/~wolf/codesign/"><img src="../../../../../icons/url.gif"></a>
<A HREF="order.htm" NAME="08_2">
<B>8.2 A Task-Level Hierarchical Memory Model for System Synthesis of
Multiprocessors</B></A><BR>
<DD><I>Yanbing Li, Wayne Wolf</I><P>
This paper introduces the first high-level (task-level) model of hierarchical
memories and describes a scheduling and allocation algorithm for system-level
synthesis of heterogeneous multiprocessors. Caches are essential for modern
RISC embedded cores to obtain sustained high performance. However, caches have
received limited use in priority-driven preemptive real-time systems due to the
unpredictability of caches average-case improvements are of no use in systems
with hard deadlines. Program-level cache models do not take into account
preemptions between multiple tasks running at multiple rates on embedded cores.
Our task-level model of performance in the presence of memory hierarchies
provides an efficient means to bound the guaranteed memory performance of tasks
running in a multi-rate, multi-tasking environment. Our system synthesis
algorithm uses software-based cache partitioning and reservation techniques to
guarantee cache hits for some tasks and therefore improve task schedulability.
Experimental results show that our model significantly improves schedulability
of real-time tasks and can be evaluated efficiently during system-level
synthesis.<P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="08_3">
<B>8.3 Predicting Timing Behavior In Architectural Design Exploration of Real-Time
Embedded Systems</B></A><BR>
<DD><I>Rajeshkumar Sambandam, Xiaobo Hu</I><P>
The degree of flexibility of a real-time system architecture indicates the
capability of the system to tolerate perturbations in timing related
specifications. Flexibility is also an important factor in the trade-off
studies between cost and performance. In this paper, we identify the need for
a flexibility metric and show that the existing real-time analysis results
cannot be directly used as such a metric. We formulate new metrics and
illustrate their effectiveness in comparing the flexibility of different system
architectures.<P>
</DL>
<HR>
<H2>Session 9:<A NAME="sess9">
APPLICATIONS OF FORMAL VERIFICATION
</A></H2>
Chair: <I>Andreas Kuehlmann</I><BR>
Organizers: <I>Haruyuki Tago, Neil Weste</I><P>
<DL>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="09_1">
<B>9.1 Formal Verification of a Superscalar Execution Unit</B></A><BR>
<DD><I>Kyle L. Nelson, Alok Jain, Randal E. Bryant</I><P>
Many modern systems are designed as a set of interconnected reactive
subsystems. The subsystem verification task is to verify an implementation of
the subsystem against the simple deterministic high-level specification of the
entire system. Our verification methodology, based on Symbolic Trajectory
Evaluation, is able to bridge the wide gap between the abstract specification
and the implementation specific details of the subsystem. This paper presents
a detailed description of an industrial application of this methodology to the
fixed point execution unit of the PowerPC processor. We were able to verify a
representative instruction under all possible stall, bypass, pipeline
conditions and under all possible timings for interface to other functional
units in the processor.<P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<a href="http://www.cs.cmu.edu/~pandey/dac97.html"><img src="../../../../../icons/url.gif"></a>
<A HREF="order.htm" NAME="09_2">
<B>9.2 Formal Verification of Content Addressable Memories using Symbolic
Trajectory Evaluation</B></A><BR>
<DD><I>Manish Pandey, Richard Raimi, Randal E. Bryant, Magdy S. Abadir</I><P>
In this paper we report on new techniques for verifying content addressable
memories (CAMs), and demonstrate that these techniques work well for large
industrial designs. It was shown in [6], that the formal verification technique
of symbolic trajectory evaluation (STE) could be used successfully on memory
arrays. We have extended that work to verify what are perhaps the most
combinatorially difficult class of memory arrays, CAMs. We use new Boolean
encodings to verify CAMs, and show that these techniques scale well, in that
space requirements increase linearly, or sublinearly, with the various CAM
size parameters. In this paper, we describe the verification of two CAMs
from a recent PowerPC TM microprocessor design, a Block Address Translation
unit (BAT), and a Branch Target Address Cache unit (BTAC). The BAT is a complex
CAM, with variable length bit masks. The BTAC is a 64entry, 64bits per entry,
fully associative CAM and is part of the speculative instruction fetch
mechanism of the microprocessor. We believe that ours is the first work on
formally verifying CAMs, and we believe our techniques make it feasible to
efficiently verify the variety of CAMs found on modern processors.<P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="09_3">
<B>9.3 Formal Verification of FIRE: A Case Study</B></A><BR>
<DD><I>Jae-Young Jang, Shaz Qadeer, Matt Kaufmann, Carl Pixley</I><P>
We present our experiences with the formal verification of an automotive chip
used to control the safety features in a car. We used a BDD based model checker
in our work. We describe our verification methodology for verifying a very
complicated property on a relatively large design. We also describe the bugs
that were found and present our views on how to make model checking an
effective integrated part of the design flow for complex hardware systems.<P>
</DL>
<HR>
<H2>Session 10:<A NAME="sess10">
SYSTEM-LEVEL EXPLORATION AND REFINEMENT
</A></H2>
Chair: <I>Ivo Bolsens</I><BR>
Organizers: <I>Ivo Bolsens, Anders Forsen</I><P>
<DL>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="10_1">
<B>10.1 Interface-Based Design</B></A><BR>
<DD><I>James A. Rowson, Alberto Sangiovanni-Vincentelli</I><P>
A new system design methodology is proposed that separates com-munication from
behavior. To demonstrate the methodology we applied it to a simple ATM design.
Since verification is clearly a major stumbling block for large system design,
we focussed on the verification aspects of our methodology. In particular, a
simulator was developed that is based on the communication paradigm typical of
our methodology. The simulator gives substantial performance improvements
without sacrificing user access to detail. Finally, the potential for this
methodology to improve verification, modeling and synthesis is explored.<P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<a href="http://csis.ee.virginia.edu/~rassp"><img src="../../../../../icons/url.gif"></a>
<A HREF="order.htm" NAME="10_2">
<B>10.2 An Integrated Design Environment for Performance and Dependability
Analysis</B></A><BR>
<DD><I>Robert H. Klenke, Moshe Meyassed, James H. Aylor, Barry W. Johnson, Ramesh Rao,
Anup Ghosh</I><P>
This paper presents an integrated design environment that supports the design
and analysis of digital systems from initial concept to the final
implementation. The environment supports both system level performance and
dependability analysis from a common modeling representation. A tool called
ADEPT (Advanced Design Environment Prototype Tool) has been developed to
implement the environment. ADEPT is based on IEEE 1076 VHDL and uses commercial
schematic capture systems as a front end via an EDIF interface. Several
examples are presented which demonstrate various aspects of the environment.<P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="10_3">
<B>10.3 A Dynamic Design Estimation and Exploration Environment</B></A><BR>
<DD><I>Ole Bentz, Jan M. Rabaey, David B. Lidsky</I><P>
The rapid increase in the complexity of systems demands new approaches to
design exploration and trade-off analysis. This paper presents an exploration
environment that provides a uniform way to perform exploration at the
conceptual (pre-specification) stages of design. The environment encapsulates
knowledge about how to perform estimations in different application domains,
and separates a designer from the mechanics of the estimation process.<P>
</DL>
<HR>
<H2>Session 11:<A NAME="sess11">
BINARY DECISION DIAGRAMS
</A></H2>
Chair: <I>Andreas Kuehlmann</I><BR>
Organizers: <I>Massoud Pedram, Andreas Kuehlmann</I><P>
<DL>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="11_1">
<B>11.1 Remembrance of Things Past: Locality and Memory in BDDs</B></A><BR>
<DD><I>Srilatha Manne, Dirk Grunwald, Fabio Somenzi</I><P>
Binary Decision Diagrams (BDDs) are efficient at manipulating large sets in a
compact manner. BDDs, however, are inefficient at utilizing the memory
hierarchy of the computer. Recent work addresses this problem by manipulating
the BDDs in breath-first manner (BFS). BFS processing is quite successful at
reducing the number of page faults when the BDDs do not fit in the available
physical memory. When paging does not take place, it is much less clear which
paradigm leads to the better performance. In this paper, we perform a detailed
analysis of BFS and DFS packages using simulation and direct performance
monitoring of the memory hierarchy. We show that there is very little difference
in TLB and cache miss rates for DFS and BFS paradigms. We also show that
differences in execution time between carefully tuned BFS and DFS
implementations are primarily a function of the lossless computed table used
in BFS implementations, and not a function of memory locality. Furthermore, we
present implementation changes to the the Cudd package that can improve
execution times by asmuch as 26% when the problem fits in main memory, and a
factor of six when paging is involved.<P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="11_2">
<B>11.2 Linear Sifting of Decision Diagrams</B></A><BR>
<DD><I>Christoph Meinel, Fabio Somenzi, Thorsten Theobald</I><P>
We propose a new algorithm, called linear sifting, for the optimization of
decision diagrams that combines the efficiency of sifting and the power of
linear transformations. We show that the new algorithm is applicable to large
examples, and that inmany cases it leads to substantially more compact diagrams
when compared to simple variable reordering. We show inwhat sense linear
transformations complement variable reordering, and we discuss applications of
the new technique to synthesis and verification.<P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="11_3">
<B>11.3 Safe BDD Minimization Using Don't Cares</B></A><BR>
<DD><I>Youpyo Hong, Peter A. Beerel, Jerry R. Burch, Kenneth L. McMillan</I><P>
In many computer-aided design tools, binary decision diagrams (BDDs) are used
to represent Boolean functions. To increase the efficiency and capability of
these tools, many algorithms have been developed to reduce the size of BDDs.
This paper presents heuristic algorithms that minimize the size of BDDs
representing incompletely specified functions by intelligently assigning don'tt
cares to binary values. The traditional algorithm, restrict [8], is often
effective in BDD minimization, but can increase the BDD size. We propose new
algorithms based on restrict which are guaranteed never to increase the size
of the BDD, thereby significantly reducing peak memory requirements.
Experimental results show that our techniques typically yield significantly
smaller BDDs than restrict.<P>
</DL>
<HR>
<H2>Session 12:<A NAME="sess12">
TIMING ANALYSIS
</A></H2>
Chair: <I>Karem A. Sakallah</I><BR>
Organizers: <I>Karem Sakallah, Sharad Malik</I><P>
<DL>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="12_1">
<B>12.1 Timing Optimization for Multi-Source Nets: Characterization and
Optimal Repeater Insertion</B></A><BR>
<DD><I>John Lillis, Chung-Kuan Cheng</I><P>
This paper presents new results in the area of timing optimization for
multi-source nets. The Augmented RC-Diameter (ARD) is proposed as a natural
and practical performance metric and a linear time algorithm for computing the
ARD of a multi-source net is presented. Building on the ARD, an algorithm for
optimal repeater insertion is presented: for a given multi-source topology the
algorithm efficiently identifies an optimal assignment of repeaters to
prescribed insertion points under the 'min cost timing feasible' problem
formulation. The algorithm has been implemented and preliminary experimental
results are promising.<P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="12_2">
<B>12.2 Exact Required Time Analysis via False Path Detection</B></A><BR>
<DD><I>Yuji Kukimoto, Robert K. Brayton</I><P>
This paper addresses how to compute required times at intermediate nodes in a
combinational network given required times at primary outputs. The simplest
approach is to compute them based on topological delay analysis without any
consideration of false paths. In this paper, however, we take into account
false paths between the intermediate nodes and the primary outputs explicitly
to characterize the timing constraints at the nodes more accurately. We show
that this approach leads to a technique for computing a more refined and
relaxed timing constraint than that obtained by topological analysis. We
generalize the notion of required times from a single constant to a relation
where a signal is required at different times depending on the values of the
other signals.<P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<a href="http://www.cs.swt.edu/papers/dac97/"><img src="../../../../../icons/url.gif"></a>
<A HREF="order.htm" NAME="12_3">
<B>12.3 Symbolic Timing Verification of Timing Diagrams using Presburger Formulas</B></A><BR>
<DD><I>Tod Amon, Gaetano Borriello, Taokuan Hu, Jiwen Liu</I><P>
We present a novel set of tools for performing symbolic timing verification of
timing diagrams. The tools are multi-purpose with uses in verification,
derivation of synthesis constraints, and design evaluation. Our methodology is
based on using techniques for manipulating Presburger formulas. We demonstrate
using several interesting examples that the method is efficient in practice and
should be considered for inclusion in commercial tools.<P>
</DL>
<HR>
<H2>Session 13:<BR>
<A HREF="order.htm" NAME="sess13"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="13_1">
EMBEDDED TUTORIAL: CODE GENERATION FOR CORE PROCESSORS
</A></H2>
Chair: <I>Peter Marwedel</I><BR>
Organizers: <I>Giovanni DeMicheli</I><BR>
Organizers: <I>Peter Marwedel</I><P>
<DL><DD>
This tutorial responds to the rapidly increasing use of cores in general and
of processor cores in particular for implementing systems-on-a-chip. In the
first part of this text, we will provide a brief introduction to various cores.
Applications can be found in most segments of the embedded systems market.
These applications demand for extreme efficiency, and in particular for
efficient processor architectures and for efficient embedded software.
In the second part of this text, we will show that current compilers do not
provide the required efficiency and we will give an overview over new compiler
optimization techniques, which aim at making assembly language programming for
embedded software obsolete. These new techniques take advantage of the special
characteristics of embedded software and embeddedarchitectures. Due to
efficiency considerations, processor architectures optimized for application
domains or even for particular applications are of interest. This results in a
large number of architectures and instruction sets, leading to the requirement
for retargeting compilers to those numerous architectures. In the final section
of the tutorial, we will present techniques for retargeting compilers to new
architectures easily. We will show, how compilers can be generated from
descriptions of processors. One of the approaches closes the gap which so far
existed between electronic CAD and compiler generation.<P>
</DL>
<HR>
<H2>Session 14:<BR>
<A HREF="order.htm" NAME="sess14"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="14_1">
PANEL: PHYSICAL DESIGN AND SYNTHESIS: MERGE OR DIE !
</A></H2>
Chair: <I>Massoud Pedram</I><BR>
Organizer: <I>Massoud Pedram</I><BR>
Panelists: <I>Richard G. Bushroe, Raul Camposano, Giovanni
De Micheli, Antun Domic, Chi-Ping Hsu, Michael Jackson</I><P>
<DL><DD>
As IC fabrication capabilities extend down to sub-half-micron, the significance
of interconnect delay and power dissipation can no longer be ignored. Existing
enhancements to synthesis and physical design tools (such as non-linear delay
modeling, custom wire load models, back annotation of calculated delays, early
floorplanning, post-layout re-mapping and resizing) have not been able to solve
the problem. It thus remains that tradeoffs in logical and physical domains
must be addressed in an integrated fashion. Huge business opportunities will
be lost unless more revolutionary changes to design flow are made.<BR>
This panel of experts will address the current split between logic synthesis
and physical design and its effect on the design flow. It will then discuss
possibilities for merging the two, or at least bringing them closer together.
In particular, issues such as consistent wire load and timing models and
algorithms which must be employed across the design flow, EDA standards and
common databases to support the integration of layout and synthesis tools,
evolving structured design-driven logic synthesis, and timing-driven physical
design will be discussed. Finally, the panel will seek to highlight challenges
and potential pitfalls that lie ahead. <P>
</DL>
<HR>
<H2>Session 15:<A NAME="sess15">
SYSTEM-LEVEL OPTIMIZATION AND VERIFICATION
</A></H2>
Chair: <I>Phil Duncan</I><BR>
Organizers: <I>Ivo Bolsens, Jim Rowsen</I><P>
<DL>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="15_1">
<B>15.1 Interface Timing Verification Drives System Design</B></A><BR>
<DD><I>Ajay J. Daga, Peter R. Suaris</I><P>
System design, i.e. the design of board-level circuits and systems-on-a-chip,
focuses on the integration of off-the-shelf and application-specific VLSI
components. A key aspect of system design is to ensure the satisfaction of
component interface timing requirements. This is necessary for the correct
exchange of information among components on a system. We present a methodology
for the interface timing verification and subsequent timing-driven
floorplanning of systems. We present results on the application of this
methodology to real-world circuits.<P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="15_2">
<B>15.2 Memory-CPU Size Optimization for Embedded System Designs</B></A><BR>
<DD><I>Barry Shackleford, Mitsuhiro Yasuda, Etsuko Okushi, Hisao Koizumi,
Hiroyuki Tomiyama, Hiroto Yasuura</I><P>
Entire systems embedded in a chip and consisting of a processor, memory, and
system-specific peripheral hardware are now commonly contained in commodity
electronic devices. Cost minimization of these systems is of paramount
economic importance to manufactures of these devices. By employing a variable
configuration processor in conjunction with a multi-precision compiler generator
there are situations in which considerable system cost reduction can be obtained
by synthesizing a CPU that is narrower than the largest variable in the
application program.<P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="15_3">
<B>15.3 Methodology for Behavioral Synthesis-based Algorithm-Level Design Space
Exploration: DCT Case Study</B></A><BR>
<DD><I>Miodrag Potkonjak, Kyosun Kim, Ramesh Karri</I><P>
Numerous fast algorithms for the Discrete Cosine Transform (DCT) have been
proposed. Until recently, it has been difficult to compare different DCT
algorithms and select one which is best suited for implementation under a given
set of design goals. We propose an approach for design space exploration at
the algorithm and behavioral levels using behavioral synthesis tools and
demonstrate its effectiveness for designing DCT ASIC. In particular, we study
and compare the following nine DCT algorithms: Lee's, Wang's, DIT, DFT, Arai's,
DIF, Vetterli's, planar rotation, and direct algorithm. The main conclusions of
this study are (i) the best choice among fast DCT algorithms depends on a
particular set of design goals and constraints and (ii) almost always more than
an order of magnitude improvement can be achieved using algorithm and
behavioral design space exploration.<P>
</DL>
<HR>
<H2>Session 16:<A NAME="sess16">
FORMAL VERIFICATION
</A></H2>
Chair: <I>Fabio Somenzi</I><BR>
Organizers: <I>Fabio Somenzi, Andreas Kuehlmann</I><P>
<DL>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="16_1">
<B>16.1 Embedded Tutorial: Formal Verification in a Commercial Setting</B></A><BR>
<DD><I>R.P. Kurshan</I><P>
This tutorial addresses the following questions:
<UL>
<LI>Why do formal verification?
<LI>Who is doing it today?
<LI>What are they doing?
<LI>How are they doing it?
<LI>What about the future?
</UL>
<P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="16_2">
<B>16.2 Equivalence Checking Using Cuts and Heaps</B></A><BR>
<DD><I>Andreas Kuehlmann, Florian Krohm</I><P>
This paper presents a verification technique which is specifically targeted to
formally comparing large combinational circuits with some structural
similarities. The approach combines the application of BDDs with circuit graph
hashing, automatic insertion of multiple cut frontiers, and a controlled
elimination of false negative verification results caused by the cuts. Two
ideas fundamentally distinguish the presented technique from previous approaches
. First, originating from the cut frontiers, multiple BDDs are computed for the
internal nets of the circuit, and second, the BDD propagation is prioritized by
size and discontinued once a given limit is exceeded.<P>
</DL>
<HR>
<H2>Session 17:<A NAME="sess17">
ANALOG SIMULATION
</A></H2>
Chair: <I>Giorgio Casinovi</I><BR>
Organizers: <I>Jacob White, Hidetoshi Onodera</I><P>
<DL>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="17_1">
<B>17.1 Efficient Methods for Simulating Highly Nonlinear Multi-Rate Circuits</B></A><BR>
<DD><I>Jaijeet Roychowdhury</I><P>
Widely-separated time scales appear in many electronic circuits, making
traditional analysis difficult or impossible if the circuits are highly
nonlinear. In this paper, an analytical formulation and numerical methods
are presented for treating strongly nonlinear multi-rate circuits effectively.
Multivariate functions in the time domain are used to capture widely separated
rates efficiently, and a special partial differential equation (the MPDE) is
known to relate the multicariate forms of a circuit signals. Time-domain and
mixed frequency-time simulation algorithms are presented for solving the
MPDE. The new methods can analyze circuits that are both large and strongly
nonlinear. Compared to traditional techniques, speedups of more than two
orders of magnitude, as well as improved accuracy, are obtained. <P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="17_2">
<B>17.2 Rapid Frequency-Domain Analog Fault Simulation Under Parameter Tolerances</B></A><BR>
<DD><I>Michael W. Tian, C.-J. Richard Shi</I><P>
Fault-driven analog and mixed-signal testing calls for rapid fault simulation
techniques. A problem that has not been addressed effectively by existing
research is that circuit parameters have tolerance ranges. In this paper, we
propose representing parameters under variations as intervals, and present an
efficient algorithm based on interval analysis and Householder's formula to
compute the worst-case response bounds of good and faulty linear(ized) circuits
under parameter variations. Our approach takes CPU time comparable to one
nominal circuit simulation, and always produces correct and conservative
results. The algorithm has been implemented into SPICE3F5. Experimental results
show an acceptable accuracy.<P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="17_3">
<B>17.3 SWITTEST: Automatic Switch-Level Fault Simulation and Test Evaluation
of Switched-Capacitor Systems</B></A><BR>
<DD><I>S. Mir, A. Rueda, T. Olbrich, E. Peralías, J.L. Huertas</I><P>
A tool for the switch-level fault simulation and test evaluation of
switched-capacitor systems is presented. Time or frequency-domain fault
simulations with SWITCAP and time-domain fault simulations with HSPICE can be
performed. Adequate fault models are presented for both simulators. The tool
has proven to be very useful in the early evaluation of test strategies,
providing similar results to those obtained at the transistor-level.<P>
</DL>
<HR>
<H2>Session 18:<A NAME="sess18">
SOFTWARE SYNTHESIS FOR EMBEDDED SYSTEMS
</A></H2>
Chair: <I>Sharad Malik</I><BR>
Organizers: <I>Sharad Malik, Luciano Lavagno</I><P>
<DL>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="18_1">
<B>18.1 Analysis and Evaluation of Address Arithmetic Capabilities in Custom
DSP Architectures</B></A><BR>
<DD><I>Ashok Sudarsanam, Stan Liao, Srinivas Devadas</I><P>
Many application-specific architectures provide indirect addressing modes with
auto-increment/decrement arithmetic. Since these architectures generally
do not feature an indexed addressing mode, stack-allocated variables must
be accessed by allocating address registers and performing address arithmetic.
Subsuming address arithmetic into auto-increment/decrement arithmetic
improves both the performance and size of the generated code.
Our objective in this paper is to provide a method for comprehensively
analyzing the performance benefits and hardware cost due to an auto-increment/
decrement feature that varies from <I>-l</I> to <I>+l</I>, and allowing
access to <I>k</I> address registers in an address generator. We provide this
method via a parameterized optimization algorithm that operates on a
procedure-wise basis. Hence, the
optimization techniques in a compiler can be used not only to generate
efficient or compact code, but also to help the designer of a custom DSP
architecture make decisions on address arithmetic features.
We present two sets of experimental results based on selected benchmark
programs: (1) the values of <I>l</I> and <I>k</I> beyond which there is little
or no improvement in performance, and (2) the values of <I>l</I> and <I>k</I>
which result in minimum code area. <P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<a href="http://www.ert.rwth-aachen.de/Personen/willems.html"><img src="../../../../../icons/url.gif"></a>
<A HREF="order.htm" NAME="18_2">
<B>18.2 System Level Fixed-Point Design Based on an Interpolative Approach</B></A><BR>
<DD><I>Markus Willems, Volker Bürsgens, Holger Keding, Thorsten Grötker, Heinrich Meyr</I><P>
The design process for fixed-point implementations either in software or in
hardware requires a bit-true specification of the algorithm in order to analyze
quantization effects on an algorithmical level, abstracting from
implementational details. On the other hand, system design starts from a
floating-point description, so that a transformation of a floating-point
description into a fixed-point description becomes necessary. Within this
paper we present a tool that allows an automated, interactive transformation
from floating-point ANSI-C into a bit-true specification based on a new data
type fixed that is introduced as an extension to ANSI-C. The concept is rooted
in a sophisticated data dependency analysis that allows to handle control
structures as well as pointers. It is part of the fixed-point design
environment FRIDGE 1 which includes an advanced simulator that covers the
extended ANSI-C syntax as well as target specific compilers which allow to
generate efficient fixed-point implementations either for HW or for SW,
starting from the bit-true algorithm specification.<P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<a href="http://rle-vlsi.mit.edu/spam"><img src="../../../../../icons/url.gif"></a>
<A HREF="order.htm" NAME="18_3">
<B>18.3 ISDL: An Instruction Set Description Language for Retargetability</B></A><BR>
<DD><I>George Hadjiyiannis, Silvina Hanono, Srinivas Devadas</I><P>
We present the Instruction Set Description Language, ISDL, a machine description
language used to describe target architectures to a retargetable compiler.
The features and flexibility of ISDL enable the description of vastly different
architectures, in particular VLIW architectures. ISDL explicity supports
constraints that define valid operation groupings within an instruction,
increasing the range of specifiable architectures. We have written a tool
that, given an ISDL description of a processor, automatically generates an
assembler for it. Ongoing work includes the development of an automatic
code-generator generator.<P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="18_4">
<B>18.4 Generation of Software Tools from Processor Descriptions for
Hardware/Software Codesign</B></A><BR>
<DD><I>Mark R. Hartoog, James A. Rowson, Prakash D. Reddy, Soumya Desai,
Douglas D. Dunlop, Edwin A. Harcourt, Neeti Khullar</I><P>
An experimental set of tools that generate instruction set simulators,
assemblers, and disassemblers from a single description was developed to test
if retargetable development tools would work for commercial DSP processors and
microprocessors. The processor instruction set was described using a language
called nML. The TMS320C50 DSP processor and the ARM7 microprocessor were
modeled in nML. The resulting instruction set models execute about 25,000
instructions per second, and compiled instruction set simulation models execute
about 150,000 instructions per second. The viability of this approach and the
deficiencies of nML are discussed.<P>
</DL>
<HR>
<H2>Session 19:<A NAME="sess19">
EXPERIENCES IN SYSTEM DESIGN AND EDUCATION AT UNIVERSITIES
</A></H2>
Chair: <I>Jan M. Rabaey, Anantha Chandrakasan</I><BR>
Organizers: <I>Jan M. Rabaey</I><P>
<DL>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="19_1">
<B>19.1 Education for the Deep-Submicron Age: Business As Usual ?</B></A><BR>
<DD><I>Hugo De Man</I><P>
Exploitation of deep-submicron technology will depend critically on the
availability of global system engineers able to bridge the gap between
software-centric system thinking and hardware-software implementation of it in
novel silicon architectures. This requires a rethinking of present engineering
schools which are not well equipped to tackle global system engineering aspects.
The concept of design institute is introduced where , based on visionary system
design demonstrators, new methodologies, tools, libraries and courses are
created and distributed over the global network. Design institutes provide a
learning school for new design paradigms and form the ideal environment for the
education of global system designers.<P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="19_2">
<B>19.2 InfoPad: An Experiment in System Level Design and Integration</B></A><BR>
<DD><I>Robert W. Brodersen</I><P>
The InfoPad project was started at UC Berkeley in 1992 to investigate the
issues involved in providing multimedia information access using a portable,
wireless terminal. It quickly became clear that a key design constraint
was the energy consumption, which could best be addressed through an
integrated system approach. The project was therefore organized to address
all design levels, including the applications and user interface, backbone
network protocols, software for distributed network support, the wireless
link, and the pad itself which used a number of low voltage ASIC designs
and a processor running embedded code. Tools were developed when not
available (particularly in support of low energy design), as well as an
interface to mechanical designers who created a custom injection molded
case. The wide scope of the project presented a number of unique challenges
for a research environment and the lessons learn will be presented. <P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="19_3">
<B>19.3 Very Rapid Prototyping of Wearable Computers: A Case Study of Custom
versus Off-the-Shelf Design Methodologies</B></A><BR>
<DD><I>Asim Smailagic, Daniel P. Siewiorek, Richard Martin, John Stivoric</I><P>
The Wearable Computer Project is a testbed integrating research on rapid design
and prototyping. Based on representative examples from six generations of
wearable computers, the paper focuses on the differences in rapid prototyping
using custom design versus off-the-shelf components. The attributes
characterizing these two design styles are defined and illustrated by
experimental measurements. The off-the-shelf approach required ten times the
overhead, 30% more cost, fifty times the storage resources, 20% more effort,
five times more power, but 30% less effort to port software than the embedded
approach.<P>
</DL>
<HR>
<H2>Session 20:<A NAME="sess20">
STANDARD CELL AND PHYSICAL DESIGN METHODS
</A></H2>
Chair: <I>Neil Weste</I><BR>
Organizers: <I>Neil Weste, Randolph Harr</I><P>
<DL>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="20_1">
<B>20.1 CAD at the Design-Manufacturing Interface</B></A><BR>
<DD><I>H.T. Heineken, J. Khare, W. Maly, P.K. Nag, C. Ouyang, W.A. Pleskacz</I><P>
Owing to rapid changes of IC technologies, traditional design rule checking is
becoming inadequate to assure satisfactory levels of IC manufacturability. This
paper describes a new computer supported design analysis environment that
improves the efficiency of manufacturability assessment of new products. This
environment, called MAPEX 2, is described in the paper along with some of its
key procedures and algorithms. Illustrations of MAPEX 2 applications and
performance figures are provided as well.<P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="20_2">
<B>20.2 CELLERITY - A Fully Automatic Layout Synthesis System for Standard Cell
Libraries</B></A><BR>
<DD><I>Mohan Guruswamy, Robert L. Maziasz, Daniel Dulitz, Srilata Raman,
Venkat Chiluvuri, Andrea Fernandez, Larry G. Jones</I><P>
This paper describes a fully automatic standard-cell layout synthesis system,
CELLERITY. The system is flexible in supporting a wide variety of process
technologies and a range of library template styles. The tool is fully
automatic and provides several options to the user to customize the layout
template. The tool considers performance and yield and generates dense,
design-rule correct layouts. Experimental results indicate that the area
of CELLERITY-generated standard cells is competitive with manually designed
cells in a majority of circuits. In block-level tests of industrial circuits,
standard-cell blocks generated using CELLERITY cells are about equal to the
block area produced by using a manually-designed library. Recently, an
embedded microcontroller in a state-of-the-art sub-micron process technology
was fabricated using CELLERITY-generated standard cells.<P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="20_3">
<B>20.3 Developing a Concurrent Methodology For Standard-Cell Library Generation</B></A><BR>
<DD><I>Donald G. Baltus, Thomas Varga, Robert Armstrong, John Duh, T.G. Matheson</I><P>
This paper describes the development of a concurrent methodology for standard
cell library generation. Use of a novel physical design automation method
enables a high degree of concurrency among process, circuit, and layout
development. In addition to reducing overall time-to-market, the new method
allows optimization to occur simultaneously across the circuit, layout, and
process design spaces. The result is libraries with improved density, circuit
performance, and process yield.<P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="20_4">
<B>20.4 A Fast And Accurate Technique to Optimize Characterization Tables for
High-Level Synthesis</B></A><BR>
<DD><I>John F. Croix, Martin D.F Wong</I><P>
Cell characterization data is used by synthesis and timing verification tools
to compile and validate a cell netlist which meets timing constraints imposed
by the designer. Characterization tables contain data for multiple, simple
equations representing a cells behavior and are an alternative to the single,
monolithic characteristic equation. Data in the table is fit to a function
whose form is fixed by the application, and the cells response is
interpolated from the function. Tables can potentially increase accuracy, but
large tables can cause a program to use dramatically more memory and run much
slower. The optimization of characterization tables, in which accuracy is
maintained but table size is significantly reduced, is important if large
programs, such as synthesis, are to complete accurately and in a reasonable
runtime. In this paper we address some of the issues involved in characterizing
cells and optimizing characterization tables quickly and accurately.
Experimental results from the use of these techniques within AMD for a
Synopsys cell library is also presented.<P>
</DL>
<HR>
<H2>Session 21:<A NAME="sess21">
MODELING AND TRANSFORMATIONS IN SYNTHESIS
</A></H2>
Chair: <I>David Ku</I><BR>
Organizers: <I>Kazutoshi Wakabayashi, Raul Camposano</I><P>
<DL>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<a href="http://www.ics.uci.edu/~jian/papers/DAC97-21-1.html"><img src="../../../../../icons/url.gif"></a>
<A HREF="order.htm" NAME="21_1">
<B>21.1 Limited Exception Modeling and its Use in Presynthesis Optimizations</B></A><BR>
<DD><I>Jian Li, Rajesh K. Gupta</I><P>
In behavioral descriptions, statements that allow limited control jumps, such
as Verilog disable statements on named blocks, are often used for describing
system behavior in presence of exceptions. In this paper, we extend Timed
Decision Tables (TDT), a tabular behavior model, to represent more general
control structures including exceptions. We introduce the notion of action
sharing that allows us to reduce resource requirements using existing
high-level synthesis tools on descriptions with control exceptions. We present
presynthesis algorithms that work on the extended TDT model and an algorithm
that performs action sharing in TDT models. Our experiments on well-known
HardwareC benchmarks show size reduction resulting from sharing actions in the
input behavioral descriptions.<P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="21_2">
<B>21.2 Potential-Driven Statistical Ordering Of Transformations</B></A><BR>
<DD><I>Inki Hong, Darko Kirovski, and Miodrag Potkonjak</I><P>
Successive, well organized application of transformations has been widely
recognized as an exceptionally effective, but complex and difficult CAD task.
We introduce a new potential-driven statistical approach for ordering
transformations. Two new synthesis ideas are the backbone of the approach. The
first idea is to quantify the characteristics of all transformations and the
relationship between them based on their potential to reorganize a computation
such that the complexity of the corresponding implementation is reduced. The
second one is based on the observation that transformations may disable each
other not only because they prevent the application of the other transformation,
but also because both transformations target the same potential of the
computation. These two observations drastically reduce the search space to find
efficient and effective scripts for ordering transformations. A key algorithmic
novelty is that both conceptual and optimization insights as well as all
optimization algorithms are automatically derived by organized experimentation
and statistical methods. On a large set of diverse real-life examples
improvements in throughput, area, and power by large factors have been obtained.
Both qualitative and quantitative statistical analysis indicate effectiveness,
high robustness, and con-sistency of the new approach for ordering
transformations.<P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="21_3">
<B>21.3 Synthesis of Application Specific Programmable Processors</B></A><BR>
<DD><I>Kyosun Kim, Ramesh Karri, Miodrag Potkonjak</I><P>
Synthesis of Application Specific Programmable Processors poses numerous new
tasks on behavioral synthesis tools. We address some of them including
application bundling. Application Bundling is a synthesis task where n
control-data flow graphs are bundled into at most m groups, so that each
application belongs to at least one group and through-put constraints for all
applications are satisfied. We have shown how avariety of application specific
constraints such as manufacturing cost reduction and production risk reduction
can be targeted during the synthesis process. The effectiveness of our approach
is demonstrated on a number of real examples.<P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="21_4">
<B>21.4 Symbolic Evaluation of Performance Models for Tradeoff Visualization</B></A><BR>
<DD><I>Jeffrey Walrath, Ranga Vemuri</I><P>
Often during the design process, it is necessary to analyze the effects of
tradeoff among various performance attributes of the design. Visual
representations in the form of plots, graphs, and tables are typically used.
These visualizations can be generated using different applications such as
MatLab R , Mathematica R , Excel R , and so forth. In order to use these tools,
performance equations for the design must be rendered in an equational form
with only a few variables, usually 2-3. However, performance models usually
consist of a large number of attributes and evaluation procedures, typically
written using the full power of a programming or hardware description language.
We introduce a symbolic evaluation procedure to simplify performance models.
Given partial data, such evaluation yields a residual performance model which
is simpler than the original model. Symbolic evaluation can be effectively used
to obtain residual performance equations in terms of the variables whose
tradeoff visualization is of interest to the user.<P>
</DL>
<HR>
<H2>Session 22:<A NAME="sess22">
STATISTICAL POWER ESTIMATION TECHNIQUES
</A></H2>
Chair: <I>Luca Benini</I><BR>
Organizers: <I>Massoud Pedram, Andrew Yang</I><P>
<DL>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="22_1">
<B>22.1 Power Macromodeling for High Level Power Estimation</B></A><BR>
<DD><I>Subodh Gupta, Farid N. Najm</I><P>
A modeling approach is presented that captures the dependence of the power
dissipation of a combinational logic circuit on its input/output signal
switching activity. The resulting power macromodel, consisting of a single
three dimensional table, can be used to estimate the power consumed in the
circuit for any given input/output signal statistics. Given a low-level
(typically gate-level) description of the circuit, we describe a
characterization process by which such a table model can be automatically built.
In contrast to other proposed techniques, this can be done for any given logic
circuit without any user intervention, and applies to all possible input/output
signal statistics; it does not require one to construct specialized analytical
equations for the power dissipation. The three dimensions of our table-based
model are the average input signal probability, average input transition
density, and average output zero-delay transition density. This approach has
been implemented and models have been built for many benchmark circuits. Over
a wide range of input signal statistics, we show that this model gives very
good accuracy, with an RMS error of under about 6%.<P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="22_2">
<B>22.2 Statistical Estimation of the Cumulative Distribution Function for Power
Dissipation in VLSI Circuits</B></A><BR>
<DD><I>Chih-Shun Ding, Qing Wu, Cheng-Ta Hsieh, Massoud Pedram</I><P>
This paper proposes to use quantile points of the cumulative distri-bution
function for power consumption to provide detailed information about the power
distribution in a circuit. The paper also presents two techniques based on
population pruning and stratification to improve the efficiency of estimation.
Both population pruning and stratification are based on a lowcost predictor,
such as zero-delay power estimate. Experimental results show the effectiveness
of the proposed techniques in providing detailed power distribution
information.<P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="22_3">
<B>22.3 Statistical Estimation of Average Power Dissipation in Sequential Circuits</B></A><BR>
<DD><I>Li-Pen Yuan, Chin-Chi Teng, Sung-Mo Kang</I><P>
In this paper, we present a new statistical technique for estimating average
power dissipation in sequential circuits. Due to the feedback mechanism, in
sequential circuits power dissipation in consecutive clock cycles are
temporally correlated, which violates the basic requirement of statistical
mean inference procedures. We overcome this problem by using a randomness test
and a sequential procedure to select a proper independence interval, which in
turn is used to generate random power samples. A distribution-independent
stopping criterion is applied to analyze the sample data and terminate the
simulation upon achievement of the accuracy specification. The technique is
successfully applied to a set of benchmark circuits.<P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="22_4">
<B>22.4 Vector Generation for Maximum Instantaneous Current Through Supply
Lines for CMOS Circuits</B></A><BR>
<DD><I>Angela Krstic, Kwang-Ting Cheng</I><P>
We present two new algorithms for generating a small set of patterns for
estimating the maximum instantaneous current through the power supply lines for
CMOS circuits. The first algorithm is based on timed ATPG, while the second is
a probability-based approach. Both algorithms can handle circuits with
arbitrary but known delays and they produce a set of 2-vector tests.
Experimental results demonstrating that the outcome of applying our algorithms
is a small set of patterns producing a current that is a tight lower bound on
the maximum instantaneous current are included.<P>
</DL>
<HR>
<H2>Session 23:<A NAME="sess23">
CO-SIMULATION
</A></H2>
Chair: <I>Kunle Olukotun</I><BR>
Organizers: <I>Rajesh Gupta, Kunle Olukton</I><P>
<DL>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="23_1">
<B>23.1 Fast Hardware/Software Co-Simulation for Virtual Prototyping and Trade-
Off Analysis</B></A><BR>
<DD><I>Claudio Passerone, Luciano Lavagno, Massimiliano Chiodo, Alberto
Sangiovanni-Vincentelli</I><P>
Hardware/software co-simulation is generally performed with separate simulation
models. This makes trade-off evaluation difficult, because the models must be
re-compiled whenever some architectural choice is changed. We propose a
technique to simulate hardware and software that is almost cycle-accurate, and
uses the same model for both types of components. Only the timing information
used for synchronization needs to be changed tomodify the processor choice, the
implementation choice, or the scheduling policy. We show how this technique
can be used todecide the implementation of a real-life example, a car dashboard
controller.<P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="23_2">
<B>23.2 Dynamic Communication Models in Embedded System Co-Simulation</B></A><BR>
<DD><I>Ken Hines, Gaetano Borriello</I><P>
Many co-simulation techniques either suffer from poor performance when
simulating communications intensive systems, or they represent communications
with a uniformly low level of detail. This paper presents a technique which
allows communication to be represented at multiple levels of detail and which
gives a designer the ability to dynamically choose the appropriate level for
different parts of the system. This paper also presents a tool which uses this
technique and experiments which show relative simulation speedups.<P>
</DL>
<HR>
<H2>Session 24:<BR>
<A HREF="order.htm" NAME="sess24"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm">
PANEL: CHALLENGES IN WORLDWIDE IP REUSE
</A></H2>
Chair: <I>Rita Glover</I><BR>
Organizers: <I>Takahide Inoue, Rita Glover, John Teets</I><BR>
Panelists: <I>Doug Fairbairn, Larry Cooke, Steve Schulz, Takahide Inoue, Raj Raghavan,
Jean-Louis Bories, Wally Rhines</I><P>
<DL><DD>
Advances in IC process technology have enabled the design of complex systems
on a single chip. System-on-chip developers need to be able to mix and match
pre-designed, best-in-class functional blocks from many providers if they are
to meet design deadlines with limited design engineering resources.
Consequently, there is a rising interest in the creation, distribution, and
design application of reusable, interoperable blocks of intellectual property,
referred to as "IP" or "virtual components.". This panel will explore the
opportunities and challenges for design innovation offered by a worldwide,
open reuse mechanism for virtual components.<BR>
This session will begin with an embedded tutorial case study on the VSIA (
Virtual Socket Interface Alliance) approach to design reuse. Then IP
providers and users will discuss the technical and business challenges in
establishing a mechanism for reuse of virtual components. The panelists
will also discuss the issues in integrating virtual components from multiple
providers into system-on-chip designs.<P>
<DT>
<B>24.1 Embedded Tutorial: Applying VSIA Standards to System on Chip Design</B><BR>
</DL>
<HR>
<H2>Session 25:<A NAME="sess25">
EMERGING TECHNOLOGIES AND ARCHITECTURES FOR LOW POWER
</A></H2>
Chair: <I>Vivek Tiwari</I><BR>
Organizers: <I>Anatha Chandrakasan, Robert C. Frye</I><P>
<DL>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="25_1">
<B>25.1 Device-Circuit Optimization for Minimal Energy and Power Consumption in
CMOS Random Logic Networks</B></A><BR>
<DD><I>Pankaj Pant, Vivek De, Abhijit Chatterjee</I><P>
We demonstrate a new approach for minimizing the total of the static and the
dynamic power dissipation components in a CMOS logic network required to
operate at a specified clock frequency using joint optimization of both device
and circuit designs for a specific logic schematic and activity profile. We
present a new approach to designing ultra low-power CMOS logic circuits by
joint optimization of supply voltage, threshold voltage and device widths for
a specified speed constraint. The static (leakage) and dynamic (switching)
energy components are considered and an efficient heuristic is developed that
delivers over an order of magnitude savings in power over conventional
optimization methods.<P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="25_2">
<B>25.2 Transisitor Sizing Issues and Tool For Multi-Threshold CMOS Technology</B></A><BR>
<DD><I>James Kao, Anantha Chandrakasan, Dimitri Antoniadis</I><P>
Multi-threshold CMOS is an increasingly popular circuit approach that enables
high performance and low power operation. However, no methodologies have been
developed to size the high Vt sleep transistor in an intelligent manner that
trades off area and performance. In fact, many attempts at sizing the sleep
transistor without close consideration of input vector patterns or internal
structures can lead to large overestimates or large underestimates in sleep
transistor sizing. This paper describes some of the issues involved in sizing
transistors for MTCMOS and also introduces a variable breakpoint switch level
simulator that can rapidly calculate delay in MTCMOS circuits as functions of
design variables such as Vdd , Vt , and sleep transistor sizing.<P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="25_3">
<B>25.3 Architectural Exploration Using Verilog-Based Power Estimation: A Case
Study Of The IDCT</B></A><BR>
<DD><I>Thucydides Xanthopoulos, Yoshifumi Yaoi, Anantha Chandrakasan</I><P>
We describe an architectural design space exploration methodology that
minimizes the energy dissipation of digital circuits. The centerpiece of our
methodology is a Verilog-based power estimation tool, Pythia, that blends the
accuracy of low-level circuit simulators such as powermill with the speed of
high level power estimators geared to design exploration. Pythia takes into
account voltage-dependent capacitive nonlinearities and supports runtime
adaptation of supply voltage. It employs a hybrid modeling aproach in which
low-level simulation of logic gates and flip-flops can be combined with high
level macromodels for memory structures where the energy per access is not as
sensitive to input data statistics. The speed and accuracy of Pythia has
enabled a detailed case study of two different approaches for the computation
of the Inverse Discrete Cosine Transform, an integral component of the MPEG
video coding algorithm. One approach uses conventional methods and the other
exploits signal statistics to dynamically minimize the average number of
operations required and the operating supply voltage.<P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="25_4">
<B>25.4 A Power Estimation Framework for Designing Low Power Portable Video
Applications</B></A><BR>
<DD><I>Chi-Ying Tsui, Kai-Keung Chan, Qing Wu, Chih-Shun Ding, Massoud Pedram</I><P>
This paper presents a power evaluation framework designed for estimating power
consumption of a new video telephone compression standard, ITU-H.263, at the
system level. A hierarchical, mixed-level simulation environment is built and
cycle-accurate power macro-modeling is used for the architectural power
evaluation. Experimental results show the effectiveness of the proposed
framework and models.<P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="25_5">
<B>25.5 An Investigation of Power Delay Trade-offs On PowerPC Circuits</B></A><BR>
<DD><I>Qi Wang, Sarma B.K. Vrudhula, Shantanu Ganguly</I><P>
Logic and structural transformations to reduce power have been considered by a
number of authors. [2, 3, 4, 5]. However, all the results presented so far have
been based on models of power and estimation methods that may not be a accurate
reflection of `real world' constraints. The performance requirements of
industrial designs often significantly restrict the applicability of the power
reducing transformations. In this paper we present the results of
investigations on the efficacy of a recently reported logic level power
optimizing algorithm [5] on some commercial circuits, using customer supplied
input waveforms. Based onaaccurate delay model, the power consumption of the
circuits is estimated using the commercial package called `PowerMill'. The
experimental results show that a maximum 21% average power and 27.7% peak power
power reduction can be obtained with only 3% delay increase. Based on the
experiments, we propose a general methodology for the practical application of
the transformations for power optimization of CMOS logic circuits. Finally, a
comparison between the experiments using random input waveforms and customer
provided input waveforms is presented.<P>
</DL>
<HR>
<H2>Session 26:<A NAME="sess26">
HIGH LEVEL SYNTHESIS FOR LOW POWER
</A></H2>
Chair: <I>Kazutoshi Wakabayashi</I><BR>
Organizers: <I>Raul Camposano, Kazutoshi Wakabayashi</I><P>
<DL>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<a href="http://www.ee.princeton.edu/~anand"><img src="../../../../../icons/url.gif"></a>
<A HREF="order.htm" NAME="26_1">
<B>26.1 Power Management Techniques for Control-Flow Intensive Designs</B></A><BR>
<DD><I>Anand Raghunathan, Sujit Dey, Niraj K. Jha, Kazutoshi Wakabayashi</I><P>
This paper presents a low-overhead controller-based power management technique
that re-specifies control signals to reconfigure existing multiplexer networks
and functional units to minimize unnecessary activity. We demonstrate that
conventional power management techniques may often not be suited to
control-flow intensive designs, and provide a comprehensive analysis of the
potential negative effects of power management on circuit delay, glitching
activity at control and data path signals, and formation of false combinational
cycles. We present techniques to perform power management through controller
re-specification while avoiding the above negative effects, and demonstrate
the efficiency of the techniques through experiments.<P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="26_2">
<B>26.2 Low Energy Memory and Register Allocation Using Network Flow</B></A><BR>
<DD><I>Catherine H. Gebotys</I><P>
This paper presents for the first time low energy simultaneous memory and
register allocation. A minimum cost network flow approach is used to
efficiently solve for minimum energy dissipation solutions in polynomial time.
Results show that estimated energy improvements of 1.4 to 2.5 times over
previous research are obtained. This research is important for industry since
energy dissipation is minimized without requiring an increase in cost.<P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="26_3">
<B>26.3 Power-Conscious High Level Synthesis Using Loop Folding</B></A><BR>
<DD><I>Daehong Kim, Kiyoung Choi</I><P>
In this paper, a transformation technique, called power-conscious loop folding
is proposed for high level synthesis of a low power system. Our work is focused
on reducing the power consumed by functional units through the decrease of
switching activity in a data path dominated circuit containing loops. The
transformation algorithm has been implemented and integrated into a high level
synthesis system for experiments. In our experiments, we could achieve power
reduction of up to 50% for circuits dominated by functional units.<P>
</DL>
<HR>
<H2>Session 27:<A NAME="sess27">
MODULE GENERATION
</A></H2>
Chair: <I>Dwight D. Hill</I><BR>
Organizers: <I>Antun Domic, Patrick Groeneveld</I><P>
<DL>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="27_1">
<a href="http://www.cadabratech.com/dac97/"><img src="../../../../../icons/url.gif"></a>
<B>27.1 Embedded Tutorial: The Future of Custom Cell Generation in Physical
Synthesis</B></A><BR>
<DD><I>Martin Lefebvre, David Marple, Carl Sechen</I><P>
We present a subjective review of custom cell generation methods in the context
of future advances in state-of-the-art digital circuit synthesis. In particular,
we describe three opportunities for coupling circuit optimization operations
with the library development process. These operations include electrical
optimization, technology mapping, and cell level place and route.<P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<a href="http://www.eecs.umich.edu/~avigupta/phd.html"><img src="../../../../../icons/url.gif"></a>
<A HREF="order.htm" NAME="27_2">
<B>27.2 CLIP: An Optimizing Layout Generator for Two-Dimensional CMOS Cells</B></A><BR>
<DD><I>Avaneendra Gupta, John P. Hayes</I><P>
We present a novel technique CLIP for optimizing both the height and width of
CMOS cell layouts in the two-dimensional (2-D) style. CLIP is based on
integer-linear programming (ILP) and proceeds in two stages: First, an ILP
model is used to determine a 2-D layout of minimum width W cell . Then, another
model generates a 2-D layout that has width W cell and requires a minimum number
of routing tracks. Run times are in seconds for circuits with up to 16
transistors. For larger circuits, we extend CLIP to a hierarchical method HCLIP
that places series-connected transis-tors contiguously. This reduces run times
by up to three orders of magnitude, and still yields optimal results in over
80% of cases.<P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="27_3">
<B>27.3 An Efficient Transistor Folding Algorithm for Row-Based CMOS Layout Design</B></A><BR>
<DD><I>Jaewon Kim, Sung-Mo Kang</I><P>
In timing-driven layout synthesis, transistor sizes tend to be significantly
different from each other and thus the use of conventional layout approaches
can cause inefficient area utilization. We propose an efficient algorithm to
find the optimal transistor folding sizes in row-based designs. Our algorithm
finds optimal folding sizes given a CMOS circuit with m pairs of pMOS and nMOS
transistors in O(m^2 log m) time complexity with the effective reduction of the
solution space. MCNC benchmark circuits are used to demonstrate the
area-efficiency of the physical layouts with optimal folding sizes.<P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="27_4">
<B>27.4 Technology Retargeting For IC Layout</B></A><BR>
<DD><I>John Lakos</I><P>
The ability to recognize polygon-based layout as a collection of objects
representing circuit elements connected by path-based wires, enables existing
designs implemented using an older fabrication process to be reimplanted
quickly in a new process. The approach taken here, based on layout generator
technology, is to create a collection of parameterized circuit objects that,
with appropriate arguments, are able to represent the devices (e.g.,
transistors, contacts) implicitly described in the flattened design. The
recognition engine is fully programmable, is independent of any particular
technology or device set, and is not restricted to manhattan or even octilinear
geometries. In this paper, we describe a novel three-phase approach to object
recognition: device recognition, exact wire recognition, and wire synthesis.
We believe exact wire recognition to be entirely new and cover it in detail.
Experimental results demonstrate the effectiveness of the algorithms on actual
layout.<P>
</DL>
<HR>
<H2>Session 28:<A NAME="sess28">
BIST AND DFT
</A></H2>
Chair: <I>Yervant Zorian</I><BR>
Organizers: <I>Janusz Rajski, Yervant Zorian</I><P>
<DL>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="28_1">
<B>28.1 A Test Synthesis Approach to Reducing BALLAST DFT Overhead</B></A><BR>
<DD><I>Douglas Chang, Mike Tien-Chien Lee, Malgorzata Marek-Sadowska,
Takashi Aikyo, Kwang-Ting Cheng</I><P>
In this paper, we present a test synthesis approach which integrates BALLAST
(BALAnced structure Scan Test) with an enhanced test point insertion (TPI)
algorithm to functionally scan the flip-flops chosen by BALLAST. BALLAST is an
attractive partial scan technique in that it offers combinational ATPG
efficiency while promising to reduce full scan overhead. However, the practical
problem with BALLAST is it typically requires more scan flip-flops than other
partial scan techniques. The TPI enhancements enable TPI to aim at the
reduction of BALLAST overhead. The enhancements include a more exible test
point insertion heuristic, a modified gain function which enables TPI to target
a selected set of flip-flops, and a more efficient procedure to remove
redundant test points. The experimental results on nine benchmark circuits
show the proposed test synthesis approach can achieve on average 38% area
saving compared to full scan, while BALLAST alone achieves 17%.<P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="28_2">
<B>28.2 STARBIST: Scan Autocorrelated Random Pattern Generation</B></A><BR>
<DD><I>K.H. Tsai, Sybille Hellebrand, Janusz Rajski, Malgorzata Marek-Sadowska</I><P>
This paper presents a new scan-based BIST scheme which achieves very high fault
coverage without the deficiencies of previously proposed schemes. This approach
utilizes scan order and polarity in scan synthesis, effectively converting the
scan chain into a ROM capable of storing some center patterns from which
the other vectors are derived by randomly complementing some of their
coordinates. Experimental results demonstrate that a very high fault coverage
can be obtained without any modification of the mission logic, no test data to
store and very simple BIST hardware which does not depend on the size of the
circuit.<P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="28_3">
<B>28.3 A Hybrid Algorithm for Test Point Selection for Scan-Based BIST</B></A><BR>
<DD><I>Huan-Chih Tsai, Kwang-Ting Cheng, Chih-Jen Lin, Sudipta Bhawmik</I><P>
We propose a new algorithm for test point selection for scan-based BIST. The
new algorithm combines the advantages of both explicit-testability-calculation
and gradient techniques. The test point selection is guided by a cost function
which is partially based on explicit testability recalculation and partially
on gradients. With an event-driven mechanism, it can quickly identify a set of
nodes whose testability need to be recalculated due to a test point, and then
use gradients to estimate the impact of the rest of the circuit. In addition,
by incorporating timing information into the cost function, timing penalty
caused by test points can be easily avoided. We present the results to
illustrate that high fault coverages for both area-and timing-driven test point
insertions can be obtained with a small number of test points. The results also
indicate a significant reduction of computational complexity while the
qualities are similar to the explicitly-testability-calculation method.<P>
</DL>
<HR>
<H2>Session 29:<BR>
<A HREF="order.htm" NAME="sess29"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="29_1">
PANEL: HARDWARE/SOFTWARE CO-VERIFICATION
</A></H2>
Chair: <I>Gary Smith</I><BR>
Organizers: <I>Michel Courtoy, Marion Kenefick</I><BR>
Panelists: <I>Brian Bailey, Kurt Keutzer, Amr Mohsen, Richard Moseley,
Jim Rowson, Geoff Bunza, Willis Hendley</I><P>
<DL><DD>
Over the recent past, the focus of EDA tools has been on tackling the chip
issues. Today, system design issues are emerging as the top concerns of
design teams. The issues include the inability to simulate at the system
level, incomplete and inaccurate spaces, and immature hardware/software
co-design.
Co-design is an essential element of new design methodologies for system
development:
<UL>
<LI>ratios of seven software engineers per hardware engineer are now common
in the development of complex embedded systems;
<LI> errors cost 10 times more to correct at the integration stage than during
design;
<LI> system specifications change impacting both hardware and software development;
<LI> interfaces between hardware and software are non-trivial for system design.
</UL>
A comprehensive hardware/software co-design methodology needs to deliver a
unified implementation environment addressing the issues outlined above. What
kind of tools can meet this challenge ? Are EDA vendors close to providing the
tools that the designers need ? <P>
</DL>
<HR>
<H2>Session 30:<A NAME="sess30">
DSP & TELECOMMUNICATION SYSTEM DESIGN
</A></H2>
Chair: <I>Rajeev Jain</I><BR>
Organizers: <I>Phil Duncan, Teresa Meng</I><P>
<DL>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="30_1">
<B>30.1 Design and Synthesis of Array Structured Telecommunication Processing
Applications</B></A><BR>
<DD><I>Wolfgang Meyer, Andrew Seawright, Fumiya Tada</I><P>
This paper describes an automated design and synthesis methodology for
telecommunications ASICs. Array frames, an array structured visualization
of the processing problem, are used in the specification and debugging of the
design. This allows design much closer to the specification level. The array
frame concept is integrated into the Dali structured control logic design
environment. An SDH (Synchronous Digital Hierarchy) style example demonstrates
the use of array frames. The array frame approach was successfully applied in
industrial applications.<P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="30_2">
<B>30.2 RASSP Virtual Prototyping of DSP Systems</B></A><BR>
<DD><I>Carl Hein, Junius Pridgen, Bill Kline</I><P>
This paper describes a top-down hierarchical simulation process that
dramatically accelerates the design-evolution of DSP systems when compared
with traditional physical prototyping methods. A summary of the model
abstraction hierarchy and purposes for the various types of models provides
critical guidance in selecting appropriate abstractions to achieve accurate
yet efficient simulations. The simulations enable rapid exploration of many
more alternative software and hardware solutions than would be practical using
conventional gate-level simulation technologies. The result is improved design
adaptations and quality.<P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="30_3">
<B>30.3 A Parallel/Serial Trade-Off Methodology for Look-Up Table Based Decoders</B></A><BR>
<DD><I>Claus Schneider</I><P>
A methodology for architecture exploration of look-up table based decoders is
presented. For the degree of parallel processing a trade-off can be made by
exploring system level and register transfer level models. Executable
specifications (pure functional software models, VHDL behavior models) are
used to analyze the performance of different architectures. Hardware cost
(area) and feasibility (timing) are determined by synthesis of RTL models.
These models are generated directly out of the specification to avoid errors
due to manual transformations and to reduce overall design time.
Generator-based reuse modeling and hardware cost estimation is demonstrated
using a decoder for MPEG variable length codes (VLC).<P>
</DL>
<HR>
<H2>Session 31:<BR>
<A HREF="order.htm" NAME="sess31"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="3_1">
EMBEDDED TUTORIAL: HIGH LEVEL POWER MODELING, ESTIMATION AND OPTIMIZATION
</A></H2>
Chair: <I>Massoud Pedram</I><BR>
Organizers: <I>Giovanni De Micheli, Massoud Pedram</I><BR>
Presenters: <I>Enrico Macii, Massoud Pedram, Fabio Somenzi</I><P>
<DL><DD>
In the past, the major concerns of the VLSI designers were area, performance,
cost, and reliability. In recent years, however, this has changed and,
increasingly, power is being given comparable weight to area and speed.
This is mainly due to the remarkable success of personal computing devices
and wireless communication systems, which demand high-speed computation and
complex functionality with low power consumption. In addition, there exists
a strong pressure for manufacturers of high-end products to keep power
under control. The main driving factors for lower power
dissipation in these products are the costs associated with packaging and
cooling, and circuit reliability. Tools for the automatic design of low-power
VLSI systems have thus become mandatory. More specifically, following a
natural trend, interests of researchers have lately shifted to the
investigation of high-level power modeling, estimation, synthesis, and
optimization techniques that account for power dissipation as the primary
cost factor. This paper provides a non-exhaustive survey of the most
successful and innovative ideas in this area that have appeared in the
literature in the last few years.<P>
</DL>
<HR>
<H2>Session 32:<A NAME="sess32">
ADVANCES IN PARTITIONING
</A></H2>
Chair: <I>Martin D.F Wong</I><BR>
Organizers: <I>Antun Domic, Patrick Groeneveld</I><P>
<DL>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="32_1">
<B>32.1 A Network Flow Approach for Hierarchical Tree Partitioning</B></A><BR>
<DD><I>Ming-Ter Kuo, Chung-Kuan Cheng</I><P>
Network flow approaches have been used for partitioning with success in the
past. However, most of them can not deal with size constraints directly in
partitioning. Instead, they incorporate the size constraints implicitly in the
objective function. This paper presents a new network flow approach for
partitioning circuits into tree hierarchies. We formulate a linear program for
the hierarchical tree partitioning problem by spreading metrics proposed in
[3][4]. The size constraints in partitioning can be formulated directly as
linear constraints. Motivated by the duality between the linear programs for
partitioning and network flow problems, we devise a heuristic algorithm based
on network flow and spreading metric computations. Experimental results
demonstrate that the new algorithm can generate better solutions for MCNC
benchmarks.<P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="32_2">
<B>32.2 Multi-Way FPGA Partitioning by Fully Exploiting Design Hierarchy</B></A><BR>
<DD><I>Wen-Jong Fang, Allen C.-H. Wu</I><P>
In this paper, we present a new integrated synthesis and partitioning method
for multiple-FPGA applications. This method first synthesizes a design
specification in a fine-grained way so that functional clusters can be
preserved based on the structural nature of the design specification. Then, it
applies a hierarchical set-covering partitioning method to form the final FPGA
partitions. Our approach bridges the gap between HDL synthesis and physical
partitioning by fully exploiting the design hierarchy. Experimental results on
a number of bench-marks and industrial designs demonstrate that I/O limits are
the bottleneck for CLB utilization when applying a traditional multiple-FPGA
synthesis method on attened netlists. In contrast, by fully exploiting the
design structural hierarchy during the multiple-FPGA partitioning, our proposed
method produces fewer FPGA partitions with higher CLB and lower I/O-pin
utilizations.<P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="32_3">
<B>32.3 A Hierarchy-Driven FPGA Partitioning Method</B></A><BR>
<DD><I>Helena Krupnova, Ali Abbara, Gabrièle Saucier</I><P>
This paper addresses an automatic partitioning method of a design into several
FPGAs. Although the circuit partitioning methods have recently been
significantly advanced, partitioning is commonly performed at the gate netlist
level. To cope with large designs and explore the solution space efficiently,
clustering of the logic is mandatory. In this paper, the hierarchy of the
design, naturally introduced by the designer, guides the partitioning. The
basic concepts are introduced in terms of "envelope" delimiting hierarchy
blocks. These concepts lead to an "envelope"-based clustering and to the
proposed final hierarchy-driven partitioning. Results are given on industrial
examples on XILINX 4000 technology.<P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="32_4">
<B>32.4 Multilevel Hypergraph Partitioning: Application in VLSI Domain</B></A><BR>
<DD><I>George Karypis, Rajat Aggarwal, Vipin Kumar, Shashi Shekhar</I><P>
In this paper, we present a new hypergraph partitioning algorithm that is based
on the multilevel paradigm. In the multilevel paradigm, a sequence of
successively coarser hypergraphs is constructed. A bisection of the smallest
hypergraph is computed and it is used to obtain a bisection of the original
hypergraph by successively projecting and refining the bisection to the next
level finer hypergraph. We evaluate the performance both in terms of the size
of the hyper-edge cut on the bisection as well as run time on a number of VLSI
circuits. Our experiments show that our multilevel hypergraph partitioning
algorithm produces high quality partitioning in relatively small amount of time.
The quality of the partitionings produced by our scheme are on the average
4% to 23% better than those produced by other state-of-the-art schemes.
Furthermore, our partitioning algorithm is significantly faster, often
requiring 4 to 15 times less time than that required by the other schemes. Our
multilevel hypergraph partitioning algorithm scales very well for large
hypergraphs. Hypergraphs with over 100,000 vertices can be bisected in a few
minutes on todays workstations. Also, on the large hypergraphs, our scheme
outperforms other schemes (in hyperedge cut) quite consistently with larger
margins (9% to 30%).<P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="32_5">
<B>32.5 Multilevel Circuit Partitioning</B></A><BR>
<DD><I>Charles J. Alpert, Jen-Hsin Huang, Andrew B. Kahng</I><P>
Recent work [2] [5] [11] [12] [14] has illustrated the promise of multilevel
approaches for partitioning large circuits. Multilevel par-titioning
recursively clusters the instance until its size is smaller than a given
threshold, then unclusters the instance while applying a partitioning
refinement algorithm. Our multilevel partitioner uses a new technique to
control the number of levels in the matching-based clustering phase and also
exploits recent innovations in clas-sic iterative partitioning [7] [10]. Our
heuristic outperforms numerous existing bipartitioning heuristics, with
improvements ranging from 6.9 to 27.9% for 100 runs and 3.0 to 20.6% for just
10 runs (while also using less CPU time).<P>
</DL>
<HR>
<H2>Session 33:<A NAME="sess33">
PROCESSOR TEST TECHNIQUES
</A></H2>
Chair: <I>Janusz Rajski</I><BR>
Organizers: <I>Yervant Zorian, Janusz Rajski</I><P>
<DL>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="33_1">
<B>33.1 Hierarchical Test Generation and Design for Testability of ASPPs and ASIPs</B></A><BR>
<DD><I>Indradeep Ghosh, Anand Raghunathan, Niraj K. Jha</I><P>
In this paper, we present design for testability (DFT) and hierarchical test
generation techniques for facilitating the testing of application-specific
programmable processors (ASPPs) and application-specific instruction processors
(ASIPs). The method utilizes the register transfer level (RTL) circuit
description of an ASPP or ASIP and tries to generate a set of test microcode
patterns which can be written into the instruction read-only memory (ROM) of
the processor. These lines of microcode dictate a new control/data flow in the
circuit and can be used to test modules which are not easily testable. The new
control/data flow is used to justify precomputed test sets of a module from the
system primary inputs to the module inputs and propagate output responses from
the module output to the system primary outputs. If the derived test microcode
cannot test all untested modules in the circuit, then test multiplexers are
added to the data path to test these modules and thus testability of all modules
is guaranteed. This scheme has the advantages of low area and delay overheads
(average of 3.1% and 0.4% respectively), high fault coverage (>99.6% for all
cases) and at-speed testing. Test generation times are about three orders of
magnitude smaller than an efficient gate-level sequential test generator. Only
one external test pin is required for the DFT method. <P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="33_2">
<B>33.2 Frequency-Domain Compatibility in Digital Filter BIST</B></A><BR>
<DD><I>Laurence Goodby, Alex Orailoglu</I><P>
We examine frequency-domain issues in the design and selection of on-chip test
generators for built-in self-test (BIST) of high-performance digital filters.
Test-generator/circuit compatibility is identified as a significant factor in
testing large filters. A fault-injection experiment is used to show that when
an incompatible test generator is used, high fault coverage (over 99%) does not
guarantee that all serious faults will be detected. The frequency-domain
characteristics of some basic test generation schemes are examined, and
guidelines for test generator selection are proposed. Analytical techniques
for identifying frequency-related testability problems are discussed, and
several test generation schemes are evaluated by fault simulating them against
lowpass, bandpass, and highpass fil-ters. A mixed test generation scheme is
shown to reduce the number of untested faults by a factor of two to three over
a standard linear-feedback shift-register (LFSR) based test scheme, at little
added cost.<P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="33_3">
<B>33.3 A Scheme for Integrated Controller-Datapath Fault Testing</B></A><BR>
<DD><I>M. Nourani, J. Carletta, C. Papachristou</I><P>
In systems consisting of interacting datapaths and controllers and utilizing
built-in self test (BIST), the datapaths and controllers are traditionally
tested separately by isolating each component from the environment of the
system during test. This work facilitates the testing of datapath-controller
pairs in an integrated fashion. The key to the approach is the addition of
logic to the system that interacts with the existing controller to push the
effects of controller faults into the data ow, so that they can be observed at
the datapath registers rather than directly at the controller outputs. The
result is to reduce the BIST overhead over what is needed if the datapath and
controller are tested independently, and to allow a more complete test of the
interface between datapath and controller. Fault coverage and overhead results
are given for four example circuits.<P>
</DL>
<HR>
<H2>Session 34:<BR>
<A HREF="order.htm" NAME="sess34"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="34_0">
PANEL: THE NEXT GENERATION HDL
</A></H2>
Chair: <I>Steve E. Schulz</I><BR>
Organizers: <I>Richard Goering, Nanette Collins</I><BR>
Panelists: <I>Kurt Keutzer, James A. Rowson, Larry Saunders,
Alberto Sangiovanni-Vincentelli, Maq Mannan, Gerard Berry</I><P>
<DL><DD>
The recent market battle between VHDL and Verilog HDL has obscured the larger
issue of whether either of these languages is adequate for next-generation
design. can they be extended, or do we need an entirely new language that's
constructed to handle system-level design descriptions, behavioral and logic
synthesis, simulation, and formal verification ? If so, how should that language
be created ?<P>
</DL>
<HR>
<H2>Session 35:<A NAME="sess35">
DESIGN PROCESSES AND FRAMEWORKS
</A></H2>
Chair: <I>Teresa Meng</I><BR>
Organizers: <I>Teresa Meng, Jan M. Rabaey</I><P>
<DL>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<a href="http://www.cbl.ncsu.edu/publications/1997-DAC-Lavana"><img src="../../../../../icons/url.gif"></a>
<A HREF="order.htm" NAME="35_1">
<B>35.1 Executable Workflows: A Paradigm for Collaborative Design on the Internet</B></A><BR>
<DD><I>Hemang Lavana, Amit Khetawat, Franc Brglez, Krzysztof Kozminski</I><P>
This paper introduces a directed hypergraph model that supports (1) work flow
composition and reconfiguration while accessing and executing programs, data,
and computing resources across the Internet, (2) synchronous and asynchronous
peer-to-peer interaction between members of any team during work flow
composition and execution, (3) synchronous and asynchronous peer-to-work flow
interaction between any team member and any object in the work flow. Given a
library of program and data nodes, editing the work flow and its execution is
as intuitive as the hierarchical schematic design capture and simulation.
Examples of multi-site multi-user applications demonstrate that the proposed
work flow implementation provides a user-friendly paradigm for distributed
and collaborative team design.<P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="35_2">
<B>35.2 Electronic Component Information Exchange (ECIX)</B></A><BR>
<DD><I>Donald Cottrell</I><P>
A number of industry trends are shaping the requirements for IC and electronic
equipment design. The density and complexity of circuit technologies have
increased to a point where design cannot be performed without EDA tools. The
availability of completely designed and verified reusable design components has
become a major impediment to meeting required design productivity goals. Design
reuse is moving down the package hierarchy to include chip design in addition
to PCA design. At the same time, the widespread use of Internet and Worldwide
Web technologies offer component suppliers global access to customers, and
component users access to suppliers, worldwide. To realize the full potential
of modern technology, it is necessary that a level of consistency be defined
and used to represent component information. Standard formats for datasheets
and standard terminology within datasheets aids customers in their analysis and
value-comparison of components from multiple suppliers. Additionally, standards
are required to facilitate software tools than can help automate current manual
processes to populate customers Component Information System (CIS) databases
and generate CAD libraries from this component information. Electronic
Component Information Exchange (ECIX) is a multi-company project that is
focused on the development of standards and architecture that supports the
flow of component information from suppliers to all potential customers in a
manner that improves productivity for:<BR>
<UL>
<LI>Component suppliers
<LI>Information suppliers
<LI>Component engineering
<LI>CAD library development
<LI>Product designers
</UL>
By working collaboratively, these companies are able to tackle a problem that
is too large for any individual company, yet minimizes development cost. Even
though they are all business competitors, they are committed to cooperation
for the development of ECIX as its success will provide industry-wide benefits
to all.<P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="35_3">
<B>35.3 Modeling Design Tasks and Tools - The Link between Product and Flow Model</B></A><BR>
<DD><I>Bernd Schürmann, Joachim Altmeyer</I><P>
The important step towards a comprehensive CAD framework is the development of
a suitable, complete design model on which the design system's components are
based. To date, we generally find 'island' solutions for different aspects
as data and process management, but in future, we need more and more integrated
solutions. Only the integration gives us the traceability we need for design
planning, to generate parts of the design tool's code automatically, etc.
This paper describes how a suitable Design Task Model can be used to link
the Product and Flow Models which are currently separated in most frameworks.
Using the PLAYOUT Design Model as an example, we show how the Product, the
Task, and the Flow Models may fit together, the development of consistent,
integrated models.<P>
</DL>
<HR>
<H2>Session 36:<A NAME="sess36">
PROBABILISTIC MODELS OF INPUT DATA FOR EFFICIENT POWER ESTIMATION
</A></H2>
Chair: <I>Farid N. Najm</I><BR>
Organizers: <I>Fabio Somenzi, Andrew Yang</I><P>
<DL>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="36_1">
<B>36.1 Hierarchical Sequence Compaction for Power Estimation</B></A><BR>
<DD><I>Radu Marculescu, Diana Marculescu, Massoud Pedram</I><P>
This paper presents an effective technique for compacting a large sequence of
input vectors into a much smaller one such that when the two sequences are
applied to any circuit, the resulting power dissipations are nearly the same.
Specifically, this paper introduces the hierarchical modeling of Markov chains
as a flexible framework for capturing not only complex spatiotemporal
correlations, but also dynamic changes in the characteristics of the input
sequence. The new framework has a high degree of adaptability, i.e. the
hierarchical model is dynamically grown according to the sequence behavior.
Experimental results demonstrate that large compaction ratios can be obtained
without a significant loss in accuracy (less than 5% on average) of power
estimates.<P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="36_2">
<B>36.2 Profile-Driven Program Synthesis for Evaluation of System Power
Dissipation</B></A><BR>
<DD><I>Cheng-Ta Hsieh, Massoud Pedram, Gaurav Mehta, Fred Rastgar</I><P>
This paper presents a new approach for estimating power dissipation in a
high performance microprocessor chip. First, characteristic profile (including
parameters such as the cache miss rate, branch prediction miss rate, pipeline
stalls, instruction mix, memory references, etc.) is extracted from application
programs. Then, mixed integer linear programming and heuristic rules are used
to gradually transform a generic program template to into a fully functional
program. The synthesized program exhibits the same performance and power
dissipation behavior (as characterized by the extracted profile), yet it has an
instruction trace orders of magnitude smaller than the initial trace. The
synthesized program is subsequently simulated on a register-transfer level
description of the target microprocessor to provide the power dissipation value
. Results obtained for the Intel's Pentium processor executing standard
benchmark programs show a simulation time reduction by 3-5 orders of magnitude.<P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="36_3">
<B>36.3 Analytical Estimation Of Transition Activity From Word-Level Signal
Statistics</B></A><BR>
<DD><I>Sumant Ramprasad, Naresh R. Shanbhag, Ibrahim N. Hajj</I><P>
Presented here is an analytical methodology to determine the average signal
activity, T , from the high- level signal statistics, a statistical signal
generation model, and the signal encoding. Simulation results for 16 bit
signals generated via AR (1) and MA (1) models indicate an estimation error in
T of less than 2%. The application of the proposed method to the estimation of
T in DSP hardware is also explained.<P>
</DL>
<HR>
<H2>Session 37:<A NAME="sess37">
HOT TOPICS IN ROUTING
</A></H2>
Chair: <I>Carl Sechen</I><BR>
Organizers: <I>Patrick Groeneveld, Antun Domic</I><P>
<DL>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="37_1">
<B>37.1 Wire Segmenting for Improved Buffer Insertion</B></A><BR>
<DD><I>Charles J. Alpert, Anirudh Devgan</I><P>
Buffer insertion seeks to place buffers on the wires of a signal net to
minimize delay. Van Ginneken [14] proposed an optimal dynamic programming
solution (with extensions proposed by [7] [8] [9] [12]) such that at most one
buffer can be placed on a single wire. This constraint can hurt solution
quality, but it may be circumvented by dividing each wire into multiple smaller
segments. This work studies the problem of finding the correct number of
segments for each wire in the routing tree. Too few segments yields sub-par
solutions, but too many segments can lead to excessive run times and memory
loads. We derive new theoretical results for computing the appropriate number
of buffers (and hence wire segments) which motivate our new wire segmenting
algorithm. We show that using wire segmenting as a precursor to buffer
insertion produces solutions within a few percent of optimal, while using only
seconds of CPU time.<P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="37_2">
<B>37.2 More Practical Bounded-Skew Clock Routing</B></A><BR>
<DD><I>Andrew B. Kahng, C.-W. Albert Tsao</I><P>
Academic clock routing research results has often had limited impact on industry
practice, since such practical considerations as hierarchical buffering,
rise-time and overshoot constraints, obstacle- and legal location-checking,
varying layer parasitics and congestion, and even the underlying design flow
are often ignored. This paper explores directions in which traditional
formulations can be extended so that the resulting algorithms are more useful
in production design environments. Specifically, the following issues are
addressed: (i) clock routing for varying layer parasitics with nonzero via
parasitics; (ii) obstacle-avoidance clock routing; (iii) a new topology design
rule for prescribed-delay clock rout-ing; and (iv) predictive modeling of the
clock routing itself. We develop new theoretical analyses and heuristics, and
present experimental results that validate our new approaches.<P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<a href="http://ballade.cs.ucla.edu/~cchang/cad/publications/DAC97-37.3.html"><img src="../../../../../icons/url.gif"></a>
<A HREF="order.htm" NAME="37_3">
<B>37.3 An Efficient Approach to Multi-layer Layer Assignment with Application to
Via Minimization</B></A><BR>
<DD><I>Chin-Chih Chang, Jason Cong</I><P>
In this paper, we present an efficient heuristic algorithm for the layer
assignment and via minimization problem for multi-layer gridless IC, PCB, and
MCM layout. We introduce the notion of the extended conflict-continuation (ECC)
graph to represent the multi-layer layer assignment problem. Our algorithm is
based on a linear time optimal algorithm that solves a special case of the
layer assignment problem when the ECC graph is a tree. For the general layer
assignment problem where the ECC graph is not a tree, our algorithm constructs
a sequence of induced subtrees in the ECC graph and applies our linear time
optimal algorithm to each of the induced subtrees. We have applied this
algorithm to the via minimization problem and get very encouraging results. We
have achieved 13%-16% via reduction on the routing layout generated by V4R
router[13], which is a router known to have low usage of vias. We successfully
applied our algorithm to routing examples of over 30,000 wire segments and over
40,000 vias.<P>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="37_4">
<B>37.4 Optimal Wire-Sizing Function with Fringing Capacitance Consideration</B></A><BR>
<DD><I>Chung-Ping Chen, D.F. Wong</I><P>
In this paper, we consider non-uniform wire-sizing under the Elmore delay
model. Given a wire segment of length C, let f(x) be the width of the wire
at position x, 0 < x <= L. It was shown in [2, 5] that the
optimal wire-sizing function which minimizes delay is an exponential tapering
function f(x) = ae^(-bx), where a > 0 and b > 0 are constants.
Unfortunately, [2,5] did not consider fringing capacitance in deep submicron
designs. As a result, exponential tapering is no longer the optimal strategy.
In this paper, we show that the optimal wire-sizing function, taking fringing
capacitance into consideration, is f(x) = -cf/2c0 ( 1/(w(-cf/(ae^(-bx))))+1)
where W(x) = Σ (n=1 to infinity) ((-n)^(n-1))/n! x(n) is the Lambert's
W function, cf and co are the respective fringing capacitance and area
capacitance of wire per unit square, a > 0 and b > 0 are constants.
he optimal wire-sizing function degenerates into an exponential tapering
function as cf = 0, and degenerates into a square-root tapering function
(f(x) = sqrt(b-ax), where a > 0 and b > 0) as cf -> infinity.
Our experimental results show that the optimal wire-sizing function can
significantly reduce the interconnection delay of exponentially tapered
wires. In the case where lower and upper bounds on the wire widths are
given, the optimal wire-sizing function is a truncated version of the
above function. Finally, our optimal wire-sizing function can be iteratively
applied to optimal size all the wire segments in a routing tree for objectives
such as minimizing weighted sink delay, minimizing maximum sink delay, or
minimizing area subject to delay bounds at the sinks.<P>
</DL>
<HR>
<H2>Session 38:<A NAME="sess38">
TEST GENERATION AND FAULT SIMULATION
</A></H2>
Chair: <I>Vishwani Agrawal</I><BR>
Organizers: <I>Yervant Zorian, Janusz Rajski</I><P>
<DL>
<DT>
<A HREF="order.htm"><IMG SRC="../../../../../icons/pdficon.gif"></A>
<A HREF="order.htm" NAME="38_1">
<B>38.1 Fault Simulation under the Multiple Observation Time Approach using
Backward Implications</B></A><BR>
<DD><I>Irith Pomeranz, Sudhakar M. Reddy</I><P>
We present an improved procedure for fault simulation under the multiple
observation time approach based on state expansi]]>