TCAD Newsletter - August 2010 Issue
Placing you one click away from the best new CAD research!


Regular Papers
==============

ANALOG, MIXED-SIGNAL, AND RF CIRCUITS

Bond, B. N.; Mahmood, Z.; Li, Y.; Sredojevic, R.; Megretski, A.; Stojanovi, V.;
Avniel, Y.; Daniel, L., "Compact Modeling of Nonlinear Analog Circuits Using
System Identification via Semidefinite Programming and Incremental Stability
Certification"

URL:
http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=HYPERLINK "http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5512699&isnumber=5512686"&HYPERLINK "http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5512699&isnumber=5512686"arnumber=5512699HYPERLINK "http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5512699&isnumber=5512686"&HYPERLINK "http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5512699&isnumber=5512686"isn...

Abstract: This paper presents a system identification technique for generating
stable compact models of typical analog circuit blocks in radio frequency
systems. The identification procedure is based on minimizing the model error
over a given training data set subject to an incremental stability constraint,
which is formulated as a semidefinite optimization problem. Numerical results
are presented for several analog circuits, including a distributed power
amplifier, as well as a MEM device. It is also shown that our dynamical models
can accurately predict important circuit performance metrics, and may thus, be
useful for design optimization of analog systems.

FPGAs AND RECONFIGURABLE COMPUTING

Smith, A. M.; Constantinides, G. A.; Cheung, P. Y. K., "FPGA Architecture
Optimization Using Geometric Programming"

URL:
http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=HYPERLINK "http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5512702&isnumber=5512686"&HYPERLINK "http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5512702&isnumber=5512686"arnumber=5512702HYPERLINK "http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5512702&isnumber=5512686"&HYPERLINK "http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5512702&isnumber=5512686"isn...

Abstract: This paper is concerned with the application of geometric programming
to the design of homogeneous field programmable gate array (FPGA)
architectures. The paper builds on an increasing body of work concerned with
modeling reconfigurable architectures, and presents a full area and delay model
of an FPGA. We use a geometric programming framework to show how transistor
sizing and high-level architecture parameter selection can now be solved as a
concurrent optimization problem. We validate the model through the use of
simulation program with integrated circuit emphasis (SPICE) models and the
versatile place and route (VPR) FPGA architecture simulation tool. Not only
does the optimization framework allow architectures to be optimized orders of
magnitude faster than previous work, but the combined optimization can lead to
different architectural conclusions compared to conventional methods by
exploring the coupling between the two sets of optimization variables.
Specifically, we show that as delay takes more significance in the objective of
the optimization, there should be more lookup tables in a logic block, whereas
conventional techniques suggest that there should be fewer lookup tables in an
FPGA logic block.

HIGH-LEVEL SYNTHESIS

Pang, Y.; Radecka, K.; Zilic, Z., "Optimization of Imprecise Circuits
Represented by Taylor Series and Real-Valued Polynomials"

URL:
http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=HYPERLINK "http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5512688&isnumber=5512686"&HYPERLINK "http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5512688&isnumber=5512686"arnumber=5512688HYPERLINK "http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5512688&isnumber=5512686"&HYPERLINK "http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5512688&isnumber=5512686"isn...


Abstract: Arithmetic circuits in general do not match specifications exactly,
leading to different implementations within allowed imprecision. We present a
technique to search for the least expensive fixed-point implementations for a
given error bound. The method is practical in real applications and overcomes
traditional precision analysis pessimism, as it allows simultaneous selection
of multiple word lengths and even some function approximation, primarily based
on Taylor series. Starting from real-valued representation, such as Taylor
series, we rely on arithmetic transform to explore maximum imprecision by a
branch-and-bound search algorithm to investigate imprecision. We also adopt a
new tight-bound interval scheme, and derive a precision optimization algorithm
that explores multiple precision parameters to get an implementation with
smallest area cost.


Shen, S.; Qin, Y.; Wang, K.; Xiao, L.; Zhang, J.; Li, S., "Synthesizing
Complementary Circuits Automatically"


URL:
http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=HYPERLINK "http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5512692&isnumber=5512686"&HYPERLINK "http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5512692&isnumber=5512686"arnumber=5512692HYPERLINK "http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5512692&isnumber=5512686"&HYPERLINK "http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5512692&isnumber=5512686"isn...

Abstract: One of the most difficult jobs in designing communication and
multimedia chips is to design and verify the complex complementary circuit pair
(E, E^{-1}), in which circuit E transforms information into a format suitable
for transmission and storage, and its complementary circuit E^{-1} recovers
this information. In order to facilitate this job, we proposed a novel two-step
approach to synthesize the complementary circuit E^{-1} from E automatically.
First, a SAT solver was used to check whether the input sequence of E can be
uniquely determined by its output sequence. Second, the complementary circuit
E^{-1} was built by characterizing its Boolean function, with an efficient
all-solution SAT solver based on discovering XOR gates and extracting
unsatisfiable cores. To illustrate its usefulness and efficiency, we ran our
algorithm on several complex encoders from industrial projects, including PCIE
and 10 G Ethernet, and successfully built correct complementary circuits for
them.

MODELING AND SIMULATION

Zhang, Z.; Wong, N., "An Efficient Projector-Based Passivity Test for
Descriptor Systems"

URL:
http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=HYPERLINK "http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5512691&isnumber=5512686"&HYPERLINK "http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5512691&isnumber=5512686"arnumber=5512691HYPERLINK "http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5512691&isnumber=5512686"&HYPERLINK "http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5512691&isnumber=5512686"isn...

Abstract: An efficient passivity test based on canonical projector techniques
is proposed for descriptor systems (DSs) widely encountered in circuit and
system modeling. The test features a natural flow that first evaluates the
index of a DS, followed by possible decoupling into its proper and improper
subsystems. Explicit state-space formulations for respective subsystems are
derived to facilitate further processing such as model order reduction and/or
passivity enforcement. Efficient projector construction and a fast generalized
Hamiltonian test for the proper-part passivity are also elaborated. Numerical
examples then confirm the superiority of the proposed method over existing
passivity tests for DSs based on linear matrix inequalities or
skew-Hamiltonian/Hamiltonian matrix pencils.

Suvak, O.; Demir, A., "Quadratic Approximations for the Isochrons of
Oscillators: A General Theory, Advanced Numerical Methods, and Accurate Phase
Computations"

URL:
http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=HYPERLINK "http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5512703&isnumber=5512686"&HYPERLINK "http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5512703&isnumber=5512686"arnumber=5512703HYPERLINK "http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5512703&isnumber=5512686"&HYPERLINK "http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5512703&isnumber=5512686"isn...

Abstract: The notion of isochrons for oscillators, introduced by Winfree and
thereon heavily utilized in mathematical biology, were instrumental in
introducing a notion of generalized phase and form the basis for oscillator
perturbation analyses. Computing isochrons is a hard problem, existing
brute-force methods incurring exponential complexity. In this paper, we present
a precise and carefully developed theory and numerical techniques for computing
local but quadratic approximations for isochrons. Previous work offers the
techniques needed for computing only local linear approximations. Our treatment
is general and applicable to oscillators with large dimension. We present
examples for isochron computations, verify our results against exact
calculations in a simple analytically calculable case, test our methods on
complex oscillators, and show how quadratic approximations of isochrons can be
used in formulating accurate, novel phase computation schemes and finally
allude to second-order accurate compact phase macromodels. Oscillator studies
seem to have progressed independently in electronics and biology. Even though
analyses in electronics did not make use of the notion of isochrons, similar
models and methods, expressed in totally different terminologies, have been
developed in both disciplines. In this paper, we also reveal the connection
between oscillator analysis work in these two seemingly disparate disciplines.

PHYSICAL DESIGN

Gupta, M.; Jeong, K.; Kahng, A. B., "Timing Yield-Aware Color Reassignment and Detailed Placement Perturbation for Bimodal CD Distribution in Double Patterning Lithography"

URL:
http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=HYPERLINK "http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5512693&isnumber=5512686"&HYPERLINK "http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5512693&isnumber=5512686"arnumber=5512693HYPERLINK "http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5512693&isnumber=5512686"&HYPERLINK "http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5512693&isnumber=5512686"isn...

Abstract: Double patterning lithography (DPL) is in current production for
memory products, and is widely viewed as inevitable for logic products at the
32 nm node. DPL decomposes and prints the shapes of a critical-layer layout in
two exposures. In traditional single-exposure lithography, adjacent identical
layout features will have identical mean critical dimension (CD), and spatially
correlated CD variations. However, with DPL, adjacent features can have
distinct mean CDs, and uncorrelated CD variations. This introduces a new set of
"bimodal" challenges for timing analysis and optimization. We assess the
potential impact of bimodal CD distribution on timing analysis and
guardbanding, and find that the traditional "unimodal" characterization and
analysis framework may not be viable for DPL. We propose new bimodal-aware
timing analysis and optimization methods to improve timing yield of
standard-cell based designs that are manufactured using DPL. Our first
contribution is a DPL-aware approach to timing modeling, based on detailed
analysis of cell layouts. Our second contribution is an integer linear
programming-based maximization of "alternate" mask coloring of instances in
timing-critical paths, to minimize harmful covariance and performance
variation. Third, we propose a dynamic programming-based detailed placement
algorithm that solves mask coloring conflicts and can be used to ensure double
"patterning correctness" after placement or even after detailed routing, while
minimizing the displacement of timing-critical cells with manageable
engineering change order (ECO) impact. With a 45 nm library and open-source
design testcases, our timing-aware recoloring and placement optimization
together achieve up to 271 ps (respectively, 55.75 ns) reduction in worst
(respectively, total) negative slack, and 70% (respectively, 72%) reduction in
worst (respectively, total) negative slack variation, respectively.

TEST

Hsiao, Y.-Y.; Chen, C.-H.; Wu, C.-W., "Built-In Self-Repair Schemes for Flash Memories"

URL:
http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=HYPERLINK "http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5512690&isnumber=5512686"&HYPERLINK "http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5512690&isnumber=5512686"arnumber=5512690HYPERLINK "http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5512690&isnumber=5512686"&HYPERLINK "http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5512690&isnumber=5512686"isn...

Abstract: The advancement of deep submicrometer Integrated circuit
manufacturing technology has pushed the use of embedded memory, and the strong
demand of embedded nonvolatile memory for system-on-chip and system in package
applications has made flash memory increasingly important as well.
Nevertheless, the yield loss of memory products caused by deep submicrometer
defects and manufacturing uncertainties is still a critical issue. In order to
solve the yield issue, built-in self-repair (BISR) has been considered as the
most cost-effective solution. However, implementing BISR on flash memories is
not trivial. In this paper, we propose BISR schemes for nor flash memory and
nand flash memory, respectively. The BISR schemes perform built-in self-test,
built-in redundancy analysis, and on-chip repair. For the BISR scheme of nor
flash memory, a typical redundancy architecture is assumed, based on which we
analyze three existing algorithms and propose a redundancy analysis (RA)
algorithm. On the other hand, for nand flash memory, an RA algorithm based on
an efficient 2-D redundancy architecture is proposed, and considering the
widely used page-mode operation in nand flash memory, a method to discover
currently accessed address is also proposed. A simulation tool is also
developed, supporting nor flash memory and nand flash memory. The simulation
results show that our approach can effectively repair defective memories.


Huang, L.; Xu, Q., "Economic Analysis of Testing Homogeneous Manycore Chips"

URL:
http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=HYPERLINK "http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5512694&isnumber=5512686"&HYPERLINK "http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5512694&isnumber=5512686"arnumber=5512694HYPERLINK "http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5512694&isnumber=5512686"&HYPERLINK "http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5512694&isnumber=5512686"isn...


Abstract: The employment of a large number of structurally identical cores on a
single silicon die is generally regarded as a promising solution for tera-scale
computation, known as manycore chips. To ensure the product quality of such
complex integrated circuits before shipping them to final users, extensive
manufacturing tests are necessary and the associated test cost can account for
a large share of the total production cost. By introducing spare cores on-chip,
the burn-in test time can be shortened and the defect coverage requirements for
core tests can be also relaxed, without sacrificing quality of the shipped
products. If the above test cost reduction exceeds the manufacturing cost of
the extra cores, the total production cost of manycore chips can be reduced. In
this paper, we develop novel analytical models to study the above tradeoff and
we verify the effectiveness of the proposed test economics model for
hypothetical manycore chips with various configurations.

VERIFICATION

Han, H.; Somenzi, F.; Jin, H., "Making Deduction More Effective in SAT Solvers"

URL:
http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=HYPERLINK "http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5512695&isnumber=5512686"&HYPERLINK "http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5512695&isnumber=5512686"arnumber=5512695HYPERLINK "http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5512695&isnumber=5512686"&HYPERLINK "http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5512695&isnumber=5512686"isn...

Abstract: Satisfiability (SAT) solvers often benefit from transformations of
the formula to be decided that allow them to do more through deduction and
decrease their reliance on enumeration. For formulae in conjunctive normal
form, subsumed clauses may be removed or partial resolution may be applied. The
objectives of simplifying the formula and speeding up the solver are sometimes
competing. We characterize existing transformations in terms of their impact on
the deductive power of the formula and their effects on the sizes of the
implication graphs. For example, we show that variable elimination works by
improving implication graphs. We also present two new techniques that try to
increase deductive power. The first is a check performed during the computation
of resolvents. The second is a new preprocessing algorithm based on
distillation that combines simplification and increase of deductive power. Most
current SAT solvers apply resolution at various stages to derive new clauses or
simplify existing ones. The former happens during conflict analysis, while the
latter is usually done during preprocessing. We show how subsumption of the
operands by the resolvent can be inexpensively detected during resolution; we
then discuss how this detection is used to improve three stages of the SAT
solver: variable elimination, clause distillation, and conflict analysis. The
"on-the-fly" subsumption check is easily integrated in a SAT solver. In
particular, it is compatible with strong conflict analysis and the generation
of unsatisfiability proofs. Experiments show the effectiveness of the new
techniques.


Short Papers
============

Chiou, D.-S.; Chen, Y.-T.; Juan, D.-C.; Chang, S.-C., "Sleep Transistor Sizing for Leakage Power Minimization Considering Temporal Correlation"

URL:
http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=HYPERLINK "http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5512698&isnumber=5512686"&HYPERLINK "http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5512698&isnumber=5512686"arnumber=5512698HYPERLINK "http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5512698&isnumber=5512686"&HYPERLINK "http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5512698&isnumber=5512686"isn...

Abstract: Power gating is one of the most effective ways to reduce leakage
power. In this paper, we introduce a new relationship among maximum
instantaneous current, IR-drops and sleep transistor networks from a temporal
viewpoint. Based on this relationship, we propose an algorithm to reduce the
total sizes of sleep transistors in distributed sleep transistor network
designs with the consideration of decoupling capacitances is taken. Our method
achieves significantly better results than previous works on sleep transistor
sizes.

Beygi, A.; Dounavis, A., "Sensitivity Analysis of Lossy Multiconductor Transmission Lines Based on the Passive Method of Characteristics Macromodel"

URL:
http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=HYPERLINK "http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5512701&isnumber=5512686"&HYPERLINK "http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5512701&isnumber=5512686"arnumber=5512701HYPERLINK "http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5512701&isnumber=5512686"&HYPERLINK "http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5512701&isnumber=5512686"isn...

Abstract: This paper describes an efficient approach for time domain
sensitivity analysis of lossy high speed interconnects in the presence of
nonlinear terminations. The sensitivity information is derived using the
recently developed passive method of characteristics. An important feature of
the proposed method is that the sensitivities are obtained from the solution of
the original network, leading to significant computational advantages.
Numerical examples are presented to illustrate the validity of the proposed
approach.

Shi, Y.; Togawa, N.; Yanagisawa, M.; Ohtsuki, T., "Improved Launch for Higher TDF Coverage With Fewer Test Patterns"

URL:
http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=HYPERLINK "http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5512687&isnumber=5512686"&HYPERLINK "http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5512687&isnumber=5512686"arnumber=5512687HYPERLINK "http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5512687&isnumber=5512686"&HYPERLINK "http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5512687&isnumber=5512686"isn...

Abstract: Due to the limitations of scan structure, the second vector in
transition delay test is usually applied either by shift operation or by
functional launch, which possibly results in unsatisfying transition delay
fault (TDF) coverage. To overcome such a limitation for higher TDF coverage, a
novel improved launch delay test technique that combines the pros of
launch-on-shift and launch-on-capture tests is introduced in this paper. The
proposed method can achieve near perfect TDF coverage with fewer test patterns
without the need for a global fast scan enable signal. Experimental results on
ISCAS89 and ITC99 benchmark circuits are included to show the effectiveness of
the proposed method.