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


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

Combining Data Reuse With Data-Level Parallelization for FPGA-Targeted Hardware Compilation: A Geometric Programming Framework
Liu, Q.; Constantinides, G. A.; Masselos, K.; Cheung, P. Y. K.
http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4785342&isnumber=4785326

A geometric programming optimization framework is proposed in this paper to
automate exploration of the design space consisting of data reuse decisions and
loop-level parallelization within a single step, in the context of
FPGA-targeted hardware compilation.


Application-Driven Voltage-Island Partitioning for Low-Power System-on-Chip Design
Sengupta, D.; Saleh, R. A.
http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4785333&isnumber=4785326

In this paper, a new application-driven approach to voltage partitioning and
island creation with the objective of reducing overall SoC power, area and
floorplanner runtime is proposed. Given an application power state machine
(PSM), the suitable range of supply voltages for each core is identified. Then,
the discrete voltage assignment table using a heuristic technique is generated.
Next, the large number of available choices from the voltage assignment table
is reduced to a useful set. Compared to previously reported techniques, a 9.4%
reduction in power and 8.7% reduction in area are achieved, with an average
runtime improvement of 2.4X.

Semicustom Design of Zigzag Power-Gated Circuits in Standard Cell Elements
Shin, Y.; Paik, S.; Kim, H.-O.
http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4785344&isnumber=4785326
Zigzag power gating (ZPG) can overcome the long wake-up delay of standard power
gating, but its requirement for both nMOS and pMOS current switches, in a
zigzag pattern, requires complicated power networks, limiting application to
custom designs. This paper presents a design framework for cell-based
semicustom design of ZPG circuits, using a new power network architecture that
allows the unmodified conventional logic cells to be combined with custom ZPG
circuitry. The sleep vector selection problem, which targets to minimize both
the transition energy and the total wirelength of a design, is solved by
employing multi-objective genetic-based algorithm.


Detailed-Routing Algorithms for Dense Pin Clusters in Integrated Circuits
Ozdal, M. M.
http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4785339&isnumber=4785326

Due to the high complexity of detailed routing algorithms, it is important to
start the routing process with clean solutions, rather than starting with
suboptimal routes and trying to fix them in an iterative process. This paper
proposes escape routing algorithms that can optimize routing of a set of nets
around terminal clusters. For this, a polynomial-time optimal algorithm for
uniform track structures and a  Lagrangian-relaxation based algorithm for
arbitrary track structures are proposed. The experimental results demonstrate
that these algorithms improve the overall routability significantly by reducing
the number of nets that require rip-up and reroute.


Fast and Accurate Statistical Criticality Computation Under Process Variations
Mogal, H. D.; Qian, H.; Sapatnekar, S. S.; Bazargan, K.
http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4785334&isnumber=4785326

This paper presents a new technique to compute the statistical criticality
information in a digital circuit under process variations.  Errors in
criticality using Clark's statistical maximum formulation are investigated and
dealt with using a new clustering based pruning algorithm which greatly reduces
the size of circuit-level cutsets, improving both accuracy and runtime over the
current state of the art.  The clustering algorithm gives about a 250X speedup
compared to a pairwise pruning strategy with similar accuracy in results.
Coupled with a localized sampling technique, errors are reduced to around 5% of
Monte Carlo simulations with large speedups in runtime.


A Methodology for Constraint-Driven Synthesis of On-Chip Communications
Pinto, A.; Carloni, L. P.; Sangiovanni-Vincentelli, A. L.
http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4785399&isnumber=4785326

This paper presents a methodology and an optimization framework for the
synthesis of on-chip communication through the assembly of components such as
interfaces, routers, buses and links, from a target library. Models for
functionality, cost, and performance of each element are captured in the
library together with their composition rules. The authors develop a
mathematical framework to model communication at different levels of
abstraction from the point-to-point input specification to the library elements
and the final implementation. 


Reducing the Abstraction and Optimality Gaps in the Allocation and Scheduling for Variable Voltage/Frequency MPSoC Platforms
Ruggiero, M.; Bertozzi, D.; Benini, L.; Milano, M.; Andrei, A.
http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4785400&isnumber=4785326

This paper proposes a novel approach to solve the allocation and scheduling
problem for variable voltage/frequency MPSoCs, which minimizes overall system
energy dissipation. Optimality of derived system configurations is guaranteed
while the computation efficiency of the optimizer allows to solve problem
instances that were traditionally considered beyond reach for exact solvers
(optimality gap). Furthermore, this paper illustrates the development- and
run-time software infrastructures that assist the user in developing
applications and implementing optimizer solutions. The proposed approach
guarantees a high level of power, performance and constraint satisfaction
predictability as from validation on the target platform, thus bridging the
abstraction gap.


Reliability Analysis of Logic Circuits
Choudhury, M. R.; Mohanram, K.
http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4785338&isnumber=4785326

Reliability of logic circuits is emerging as an important concern in scaled
electronic technologies. Reliability analysis of logic circuits is
computationally complex because of the exponential number of inputs,
combinations, and correlations in gate failures. This paper presents three
accurate and scalable algorithms for reliability analysis of logic circuits.
Simulation results for several benchmark circuits demonstrate the accuracy,
performance, and potential applications of the proposed algorithms.


Diagnosis of Multiple-Voltage Design With Bridge Defect
Khursheed, S.; Al-Hashimi, B. M.; Reddy, S. M.; Harrod, P.
http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4785343&isnumber=4785326

Multiple-voltage is an effective dynamic power reduction design technique,
commonly used in low power ICs. To the best of our knowledge there is no
reported work for diagnosing multiple-voltage enabled ICs and the aim of this
paper is to propose a cost-effective method for diagnosing bridge defects in
such ICs. Using synthesized ISCAS benchmarks, with realistic extracted bridges
and a parametric fault model, the paper investigates the impact of varying
supply voltage on the accuracy of diagnosis and demonstrates how the additional
voltage settings can be leveraged to improve the diagnosis resolution through a
novel multi-voltage diagnosis algorithm.


Efficient Boolean Characteristic Function for Timed Automatic Test Pattern Generation
Kuo, Y.-M.; Chang, Y.-L.; Chang, S.-C.
http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4785346&isnumber=4785326

Timing analysis is critical for many circuit optimizations. Accurate timing
analysis can be achieved by finding input vectors that simultaneously satisfy
both functional and temporal requirements. The problem of finding such input
vectors can be modeled as a Boolean equation called the Timed Characteristic
Function (TCF). Despite the usefulness of the TCF, traditional TCF construction
and solving is slow for large circuits. This paper presents a more efficient
way to use the TCF. On average, our method achieves much faster results than
the most recent other work.


Double-Single Stuck-at Faults: A Delay Fault Model for Synchronous Sequential Circuits
Pomeranz, I.; Reddy, S. M.
http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4785337&isnumber=4785326

We describe a new transition fault model for synchronous sequential circuits.
Similar to previous models, it addresses the fact that delayed signal
transitions may span multiple clock cycles. The model requires the activation
of single stuck-at faults with opposite stuck-at values on the same line at
consecutive time units. In addition, it requires the detection of both faults
at the same or later time units. The model can be used together with other
models to increase the confidence that delay defects will be detected. It also
helps detect other types of faults that require two-pattern tests.


Automated Interface Refinement for Compositional Verification
Yao, H.; Zheng, H.
http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4785335&isnumber=4785326

Compositional verification is essential for verifying large systems. However,
approximate environments are needed when verifying the constituent modules in a
system. Effective compositional verification requires finding a simple but
accurate over-approximate environment for each module. Otherwise, many spurious
verification failures may be produced. This paper presents an automated method
to refine the state space of each module within an over-approximate
environment. This method is sound and has less restrictions on system
partitioning. It is also coupled with several state space reduction techniques
for better results. Experiments of this method on several large asynchronous
designs show promising results.


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

Compiler-in-the-Loop Design Space Exploration Framework for Energy Reduction in Horizontally Partitioned Cache Architectures
Shrivastava, A.; Issenin, I.; Dutt, N.; Park, S.; Paek, Y.
http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4785345&isnumber=4785326

Horizontally partitioned data caches (HPCs) are a power-efficient architectural
feature in which the processor maintains two or more data caches at the same
level of hierarchy. Most previous research has focused on exploiting HPCs to
improve performance. However with energy consumption becoming the first class
design constraint, there is an increasing need for compilation techniques aimed
at energy reduction itself. This article proposes and explores several
low-complexity algorithms aimed at reducing the energy consumption. Also
Compiler-in-the-Loop Design Space Exploration methodologies are presented to
carefully choose the HPC parameters that result in minimum energy consumption
for the application.


HLS-pg: High-Level Synthesis of Power-Gated Circuits
Choi, E.; Shin, C.; Shin, Y.
http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4785348&isnumber=4785326

A problem inherent in power-gated circuits is the overhead of state-retention
storage required to preserve the circuit state in standby mode. HLS-pg is a new
design framework that takes power-gating into account, from scheduling,
allocation, and controller synthesis to the final circuit layout. Its main
feature is a new scheduler that minimizes the number of retention registers
required at the power-gating control step. In experiments on benchmark designs
implemented in 0.9 V, 65-nm technology,HLS-pg reduced leakage current by 20.7%
on average,with 5.0% less area and 4.1% less wirelength, compared to the
power-gated circuits produced by conventional high-level synthesis.


Determination of Floquet Exponents for Small-Signal Analysis of Nonlinear Periodic Circuits
Brambilla, A.; Gruosso, G.; Gajani, G. S.
http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4785327&isnumber=4785326

This paper describes an approach to determine the Floquet exponents and the
related eigenfunctions of linear time-varying circuits, that represent a
vehicle to implement the variational model of periodic nonlinear circuits. The
Floquet exponents and eigenfunctions allow to exploit the structure of the
analytical solution of the linear time-varying circuit and as shown yield an
efficient solution.The proposed approach allows the calculation of the Floquet
exponents directly and is developed from the Harmonic Balance formulation
adopted to find the steady state solution of the nonlinear periodic circuit.


Spare Cells With Constant Insertion for Engineering Change
Kuo, Y.-M.; Chang, Y.-T.; Chang, S.-C.; Marek-Sadowska, M.
http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4785347&isnumber=4785326

Engineering change (EC) is the process of modifying a design implementation to
eliminate design errors, to add new specifications, or to correct constraint
violations. This paper describes an iterative method to determine feasible
mapping solutions for an EC problem using spare cells with constant insertion
setting some cell's inputs to fixed values. Our experimental results suggest
constant insertion reduces the area required to find a feasible mapping
solution to 80% of that with no constant insertion for the selected EC
equations.