ABSTRACTS ED&TC 97

Session 1A: System Analysis Techniques and Applications

RATAN: A Tool for Rate Analysis and Rate Constraint Debugging for Embedded Systems [pp 2]

A. Dasdan, A. Mathur, and R.K. Gupta

The increasingly complex design of embedded systems creates the problems of specifying consistent and satisfiable rate constraints on process execution rates, checking them for consistency and satisfiability, computing process execution rates, and debugging rate con- straint violations. The high complexity of these problems requires a complete and automated framework to help the designer in producing correct systems in shorter design time. We present such a framework and its implementation in a tool called Ratan . Experiments on large benchmarks show the suitability of the tool for an interactive debugging environment.

Efficient Utilization of Scratch-Pad Memory in Embedded Processor Applications [pp 7]

P.R. Panda, N.D. Dutt, and A. Nicolau

Efficient utilization of on-chip memory space is extremely important in modern embedded system applications based on microprocessor cores. In additionto a data cache that interfaces with slower off-chip memory, a fast on-chip SRAM, called Scratch-Pad memory, is often used in several applications. We present a technique for efficiently exploiting on-chip Scratch-Pad memory by partitioning the applications scalar and array variables into off-chip DRAM and on-chip Scratch-Pad SRAM, with the goal of minimizing the total execution time of embedded applications. Our experiments on code kernels from typical applications show that our technique results in significant performance improvements.

Interface Timing Verification with Delay Correlation Using Constraint Logic Programming [pp 12]

P. Girodias and E. Cerny

Using constraint logic programming and relational interval arithmetic, as implemented in CLP (BNR) Prolog, we develop a simple yet complete method for interface timing verification. We show how the problems raised by timing verification (consistency, causality and compatibility) can be formulated as constraint satisfaction problems and solved using relational interval arithmetic when the timing constraints are of the linear, earliest or latest type; we examine the effect of correlation between timing delays (within their specified intervals) and show how an interval delay narrowing method can be applied in this context. The original contribution of this paper is to provide a unifying framework for interface timing verification and to present a method that allows delay correlation to be considered.

Session 1B: Sequential ATPG

Sequential Circuit Test Generation Using Dynamic State Traversal [pp 22]

M.S. Hsiao, E.M. Rudnick, and J.H. Patel

A new method for state justification is proposed for sequential circuit test generation. The linear list of states dynamically obtained during the derivation of test vectors is used to guide the search during state justification. State-transfer sequences may already be known that drive the circuit from the current state to the target state. Otherwise, genetic engineering of existing state-transfer sequences is required. In both cases, genetic-algorithm-based techniques are used to generate valid state justification sequences for the circuit in the presence of the target fault. This approach achieves extremely high fault coverages and thus out-performs previous deterministic and simulation-based techniques.

MOSAIC: A Multiple-Strategy Oriented Sequential ATPG for Integrated Circuits [pp 29]

A. Dargelas, C. Gauthron, and Y. Bertrand

The paper proposes a novel approach in an attempt to solve the test problem for sequential circuits. Up until now, most of the classical test pattern techniques use a number of algorithms in several passes to detect faults. Our so –called Multiple Strategy Approach takes into account the existing techniques and algorithms, (improvements are proposed for some of them) and at each step selects the strategy that is best adapted to catch the targeted faults. This work has been done with a focus on designing a real industrial ATPG, able to handle real circuits consisting of several hundreds of thousands of gates.

New Static Compaction Techniques of Test Sequences for Sequential Circuits [pp 37]

F. Corno, P. Prinetto, M. Rebaudengo, and M. Sonza Reorda

This paper describes an algorithm for compacting the Test Sequences generated by an ATPG tool without reducing the number of faults they detect. The algorithm is based on re-ordering the sequences so that some of them can be shortened and some others eliminated. The problem is NP-complete, and we adopt Genetic Algorithms to obtain optimal solutions with acceptable computational requirements. As it requires just one preliminary Fault Simulation experiment, the approach is much more efficient than others proposed before; experimental results gathered with Test Sets generated by different ATPG tools show that the method is able to reduce the size of the Test Set by a factor varying between 50% and 62%.

Session 1C: Design and Design Methodology for Analog Circuits

A Methodology for Designing Continuous-Time Sigma-Delta Modulators [pp 46]

P. Benabes, M. Keramat, and R. Kielbasa

A methodology for analysis and synthesis of lowpass sigma-delta ( SD) converters is presented in this paper. This method permits to synthesize SD modulators employing continuous-time filters from discrete-time topologies. The analysis method is based on the discretization of continuous-time model and using a discrete simulator which is more efficient than an analog simulator. Finally, a realistic design of a second-order SD modulator with a compensation of the non ideal behavior of DAC is given. Moreover, simulation results show a good agreement with the theoretical bases.

A CMOS Low-Voltage, High-Gain Op-Amp [pp 51]

G.N. Lu and G. Sou

A CMOS, self-biasing, single-supply op-amp is presented. It is designed with regulated cascode transistors for gain enhancement and a common-mode feedback technique for bias stabilisation of complementary regulated cascodes. It enables supply voltage lowering to about 2|VT | + 2|Vds ,sat | with the maintain of high-gain operation. At V dd = 1.8 V, the measured dc gain of the op-amp is 115 dB, with a unity-gain frequency of 8.6 MHz for a capacitive load of 20 pF.

High-Level Synthesis of Analog Sensor Interface Front-Ends [pp 56]

S. Donnay, G. Gielen, W. Sansen, W. Kruiskamp, D. Leenaerts, and W. van Bokhoven

In this paper we will compare three different methodologies for analog high-level synthesis. Two optimization-based methods one with simulations in the loop, the other with equations and a library-based approach are discussed and illustrated with experimental results. The comparison is made by means of a real life design example a radiation detector interface ASIC although the methodologies presented in this paper, are generally applicable.

Session 2A: Panel P1 - How to Introduce Advanced Design Technology in Qualified Industrial Design Flows?

Coordinator: I. Bolsens, IMEC, Belgium
Moderator: P. De Wilde, TU Delft/DIMES, The Netherlands

Panel:
P. Reynaert, Mentor Graphics, Belgium
P. Pype, Coware, USA
R. Jain, University of California, Los Angeles, USA
P. Odent, Philips, The Netherlands
P. Paulin, ST, France
K-P. Estola, Nokia Mobile Phones, Finland
H. Cloetens, Philips, The Netherlands

Session 2B: Advances in Built-In Self-Test

Structural BIST Insertion Using Behavioral Test Analysis [pp 64]

M. Nourani and C. Papachristou

The purpose of this work is to develop a test synthesis technique based on BIST methodology which uses the test metrics (i.e. controllability and observability) obtained by test analysis of the behavior to enhance the testability quality (fault coverage) of the corresponding structure and obtain the scheduled test behavior accordingly. The key feature of this work is in using the Structured Data Flow Graph (SDG) which anno- tates the behavioral information (e.g. data dependency) and structural information (e.g. binding, connectivity). To enhance testability of the structure, the SDG will be modified using transformation technique to improve the fault coverage and shorten the test schedule.

On the Generation of Pseudo-Deterministic Two-Patterns Test Sequence with LFSRs [pp 69]

C. Dufaza and Y. Zorian

Many Built-in Self Test pattern generators use Linear Feedback Shift Registers (LFSR) to generate test sequences. In this paper, we address the generation of deterministic pairs of patterns for delay faults testing with LFSRs. A new synthesis procedure for a n-size LFSR is given and guarantees that a deterministic set of n precomputed test pairs is embedded in the maximum length pseudo-random test sequence of the LFSR. Sufficient and necessary conditions for the synthesis of this pseudo-deterministic LFSR are provided and show that at-speed delay faults testing becomes a reality without any additional cost for the LFSR. Moreover, since the theoretical properties of LFSRs are preserved, our method could be benefically used in conjunction with any other technique proposed so far.

Cellular Automata for Generating Deterministic Test Sequences [pp 77]

D. Kagaris and S. Tragoudas

We propose an on-chip test pattern generator that uses an one{dimensional cellular automaton (CA) to generate either a precomputed sequence of test patterns or pairs of test patterns for path delay faults. To our knowledge, this is the first approach that guarantees successful on-chip generation of a given test pattern sequence (or a given test set for path delay faults) using a finite number of CA cells. Given a pair of columns (Cu, Cv) of the test matrix, the proposed method uses alternative 'linking procedures' Pj that compute the number of extra CA cells to enable the generation of (Cu, Cv) by the CA. A systematic approach uses the linking procedures to minimize the total number of needed CA cells. Experimental results show that the hardware overhead is often reasonable. The performance of the scheme depends on an appropriate choice of linking procedures Pj.
Keywords: Built-In Self-Test, Deterministic Test Pattern Generation.

Session 2C: Synthesis of Controllers

Fast Controllers for Data Dominated Applications [pp 84]

A. Hertwig and H-J. Wunderlich

A target structure for implementing fast edge-triggered control units is presented. In many cases, the proposed con-troller is faster than a one-hot encoded structure as its correct timing does not require master-slave flip-flops even in the presence of unpredictable clocking skews. A synthesis procedure is proposed which leads to a per-formance improvement of 40% on average for the standard benchmark set whereas the additional area is less than 25% compared with conventional finite state machine (FSM) synthesis. The proposed approach is compatible with the state-of-the-art methods for FSM decomposition, state encoding and logic synthesis.
Keywords: FSM synthesis, performance driven synthesis, synthesis of testable controllers

Random Benchmark Circuits with Controlled Attributes [pp 90]

K. Iwama, K. Hino, H. Kurokawa, and S. Sawada

Two major improvements, controlled fan-in and automated initial-circuit production, were made over the random generator of benchmark circuits presented at DAC'94. This is an important progress towards our goal of random benchmarking : more general and secure testing, increasing the naturality of random circuits by controlling their attributes, and obtaining test results by which the difference of performances under evaluation can be made clear.

Technology Mapping of Speed-Independent Circuits Based on Combinational Decomposition and Resynthesis [pp 98]

J. Cortadella, M. Kishinevsky, A. Kondratyev, L. Lavagno, and A. Yakovlev

This paper presents a solution to the problem of sequential multi-level logic synthesis of asynchronous speed-independent circuits. The starting point is a technology-independent speed-independent circuit obtained using, e.g., the monotonous cover conditions. We describe an algorithm for the factorization of this circuit aimed at implementing it in a given standard cell library, while preserving speed-independence. The algorithm exploits known efficient factorization techniques from combinational multi-level logic synthesis, but achieves also boolean simplification. Experimental results show a significant improvement in terms of number and complexity of solvable circuits with respect to existing methods.

Session 2D: Microsystems Design I

Generation of the HDL-A-Model of a Micromembrane from Its Finite- Element-Description [pp 108]

K. Hofmann, M. Glesner, N. Sebe, A. Manolescu, S. Marco, J. Samitier, J-M. Karam, and B. Coutois

A CAD-tool for the automated generation of behavioral models in HDL-A is presented. This CAD-tool has been implemented in the frame of a project for automatical modeling of microsystem components for the co-simulation with VHDL- or Spice-Models. Starting from the Finite-Element-description of a microcomponent a nonlinear behavioral HDL-A-model is generated by successively adding or deleting effects to the HDL-A-model according to the observed differences between the two models. Using the example of a micromembrane the practicability of this approach will be demonstrated. This CAD-tool provides a method for decoupling the generation of behavioral models from the Finite-Element-simulation process.

Microsystem Design Using Simulator Coupling [pp 113]

W. Wünsche, C. Clauß, P. Schwarz, and F. Winkler

The microsystem design process is characterized by inter-disciplinary approaches and close interactions between different domains. A methodology for simulating the performance of complex microsystems using simulator coupling is presented. The technique is based on the coupling of the FEM program ANSYS with the circuit and system simulator SABER. In difference to other known simulator couplings a time step algorithm is employed. Its methodology is reported and the implementation into simulation tools is explained. The system simulations of an acceleration sensor system as well as the simulation of thermal interactions in integrated circuits prove the suitability of the coupling. Finally, simulation results are discussed and advantages of the implemented coupling are concluded.

Modeling and Simulation of Electromechanical Transducers in Microsystems Using an Analogue Hardware Description Language [pp 119]

B. Romanowicz, M. Laudon, P. Lerch, P. Renaud, H.P. Amann, A. Boegli, V. Moser, and F. Pellandini

The analytical modeling and simulation of conservative electrostatic, electromagnetic and electrodynamic transducers found in microsystems using a non-linear lumped-parameter approach is presented in this paper. A comparison is made between this approach and the linearized equivalent circuit method. All models of transducers are written in HDL-A TM , a proprietary analogue hardware description language (HDL). System-level simulation is performed in the SPICE simulator using behavioral models of the transducers. Finally, a parameter extraction and HDL model generation tool for devices is presented.

Session 3A: Software Generation for Embedded Processors

Delay Management for Programmable Video Signal Processors [pp 126]

M.L.G. Smeets, E.H.L. Aarts, G. Essink, and E.A. de Kock

We consider the problem of memory allocation for intermediate data in the mapping of video algorithms onto programmable video signal processors. The corresponding delay management problem is proved to be NP-hard. We present a solution strategy that decomposes the delay management problem into a delay minimization problem followed by a delay assignment problem. The delay minimization problem is solved with network flow techniques. The delay assignment problem is handled by a constructive approach. The performance of the combined approach is analyzed by means of a benchmark set of industrially relevant video algorithms.
Key words. Real-time video signal processing; combinatorial optimization; retiming; life-time analysis of variables; network flow; stream processing.

Hierarchical Scheduling and Allocation of Multirate Systems on Heterogeneous Multiprocessors [pp 134]

Y. Li and W. Wolf

This paper describes new algorithms for system-level software synthesis, namely the scheduling and allocation of a set of complex tasks running at multiple rates on a heterogeneous multiprocessor. The tasks may have precedence constraints within them. The multiprocessor may be composed of both programmable and fixed-function processing elements and may have arbitrary interconnect topology. Our hierarchical algorithm takes advantage of the hierarchical structure of the system's task graph to hierarchically allocate and schedule processes on the multiprocessor to meet the hard real-time constraints on the tasks. Multimedia is an important application of our algorithm.

Retargetable Generation of Code Selectors from HDL Processor Models [pp 140]

R. Leupers and P. Marwedel

Besides high code quality, a primary issue in embedded code generation is retargetability of code generators. This paper presents techniques for automatic generation of code selectors from externally specified processor models. In contrast to previous work, our retargetable compiler Record does not require tool-specific modelling formalisms, but starts from general HDL processor models. From an HDL model, all processor aspects needed for code generation are automatically derived. As demonstrated by experimental results, short turnaround times for retargeting are achieved, which permits to study the HW/SW trade-off between processor architectures and program execution speed.

Session 3B: Register Transfer Level Test Synthesis

An RTL Methodology to Enable Low Overhead Combinational Testing [pp 146]

S. Bhattacharya, S. Dey, and B. Sengupta

Combinational test pattern generation remains a popular testing methodology because of its ability to generate test patterns for large industrial circuits with high test efficiency. Full-scan [1] is the conventional methodology which enables the testing of sequential circuits using test patterns generated by combinational ATPG. However, application of combinational testing to sequential circuits using full-scan methodology may be prohibitively expensive, due to the high area overhead and test application time associated with full-scan. Several gate level techniques like partial scan have been proposed to reduce the area overhead of full scan implementations. However, to avoid requiring substantially less scan FFs than full-scan, partial scan requires an efficient sequential ATPG tool. Recently, a gate-level technique has been proposed to reduce the area overhead of scan design by establishing paths in the scan chain using existing logic [2] instead of using scan FFs. The technique requires setting the primary inputs to establish the free scan paths, thus limiting its applicability. Reduction of test application time has been addressed in several ways, like arranging scan flip-flops in parallel scan chains [3, 4], and reconfiguring scan chains [5]. In the parallel scan chain approach, the number of parallel scan chains, and hence the number of vectors that can be shifted in parallel, is limited by the minimum of the number of primary inputs and primary outputs of the circuit. The reconfigurable scan chain approach [5] is limited by the ability of the circuit to be decomposed into a set of kernels, which are disjoint portions of logic that can be tested independently.

A Controller Testability Analysis and Enhancement Technique [pp 153]

X. Gu, E. Larsson, K. Kuchinski, and Z. Peng

This paper presents a testability analysis and improvement technique for the controller of an RT level design. It detects hard-to-reach states by analyzing both the data path and the controller of a design. The controller is modified using register initialization, branch control, and loop termination methods to enhance its state reachability. This technique complements the data path scan method and can be used to avoid scanning registers involved in the critical paths. Experimental results show the improvement of fault coverage with a very low area overhead.

Analyzing Testability from Behavioral to RT Level [pp 158]

M.L. Flottes, R. Pires, and B. Rouzeyre

In this paper, we present a method for analyzing the testability of a circuit during high level synthesis. The testability analysis returns values that represent the relative difficulty for computing test data, whatever the level of description of a circuit is from the behavioral level initial specification down to the Register Transfer Level high level synthesis output. Experiments show the good correlation of the so obtained testability measures with gatelevel testability measures (e.g. Scoap). The proposed measures are used to guide high level synthesis towards the generation of easily SATPG testable datapaths.

Session 3C: BDDs and Formal Verification

Fast and Efficient Construction of BDDs by Reordering Based Synthesis [pp 168]

A. Hett, R. Drechsler, and B. Becker

We present a new approach to symbolic simulation with BDDs. Our method uses Reordering Based Synthesis (RBS) which allows the integration of dynamic variable ordering (even) within a single synthesis operation (e.g. an AND-operation). Thus, huge peak sizes during the construction can often be avoided, and we obtain a method that, with no penalty in runtime, is more memory efficient than traditional ITE operator based symbolic simulation. The results are confirmed by experiments on a large set of benchmarks: We give a comparison to previously published approaches and also consider some industrial benchmarks which are known to be hard to handle.

Verification and Synthesis of Counters Based on Symbolic Techniques [pp 176]

G. Cabodi, P. Camurati, L. Lavagno, and S. Quer

Symbolic Techniques have undergone major improvements but extending their applicability to new fields is still a key issue. A great limitation on standard Symbolic Traversals is represented by Finite State Machines with a very high sequential depth. A typical example of this behaviour are counters. On the other hand systems containing counters, e.g. embedded systems, are of great practical importance in several fields. Iterative squaring can produce solutions with a logarithmic execution time with respect to the sequential depth but a few drawbacks usually limit its application. We successfully tailored iterative squaring to allow its application for symbolic verification and synthesis of circuits containing counters. Experiments on large and complex home-made and industrials circuits containing counters show the feasibility of the approach.

Using MTBDDs for Discrete Timed Symbolic Model Checking [pp 182]

T. Kropf and J. Ruf

The verification of timing properties is an important task in the validation process of embedded and real time systems. Temporal logic model checking is one of the most successful techniques as it allows the complete automation of the verification. In this paper, we present a new approach to symbolic QCTL (Quantitative CTL) model checking. In contrast to previous approaches we use an intuitive QCTL semantics, provide an efficient model representation and the new algorithms require less iteration steps compared to translating the QCTL problem into CTL and using standard CTL model checking techniques. The new model checking algorithm is based on a MTBDD representation. Some experimental results show the efficiency of the new approach.

Session 3D: Microsystems Design II

Analysis of 3D Conjugate Heat Transfers in Electronics [pp 190]

J.P. Fradin, L. Molla, and B. Desaunettes

An efficient method for the analysis of real 3D conjugate heat transfer for electronic devices is presented. This methodology is based on the coupling of two software : a conductive software based on the Boundary Element Method (REBECA-3D) and a convective software based on the Volume Finite Method (FLUENT). The methodology is tested on a Multi Chip Module (CPGA224) for which experiments have been performed by the CNRS (French National Center for Scientific Research).

Smart Sensor System Application: An Integrated Compass [pp 195]

R.J.W.T. Tangelder, G. Diemel, and H.G. Kerkhoff

A fully integrable electronic compass has been designed based on the pulse position method, using micro-machined fluxgate magnetic sensors. The compass has been designed to have an accuracy of one degree. The analogue and digital circuitry in the system fit on a single Sea-of-Gates array of 200k transistors. Together with the sensors it will be combined on a single MCM.
Keywords: mixed-signal design, micro systems, fluxgate sensors

Automatic Transfer of Parametric FEM Models into CAD-Layout Formats for Top-Down Design of Microsystems [pp 200]

M. Lang, D. David, and M. Glesner

A tool for the transfer of solid models used for FEM simulations into different layout formats used by CAD environments is presented. All necessary layers for the fabrication of microcomponents and -systems in a given extended commercial CMOS process are generated automatically by this tool. Starting with an acceleration sensor the use of this translator for an application in the top-down design of microsystems with parametric components is described.

Session 4A: Panel P3 - What Will Be the Right Test Methodology for the Year 2005?

Coordinator: I. Bolsens, IMEC, Belgium
Moderator: K. Baker, Philips, The Netherlands

Panel:
B. Schneider, Microlex, Denmark
P. De Pauw, Alcatel-Mietec, Belgium
T. Williams, IBM, Boulder, USA
B. Grubel, Texas Instruments, USA
S. Athan, Univ. Florida, USA

Session 4B: High Performance Architectures for Multimedia and Communication ASICs

Highly Scalable Parallel Parametrizable Architecture of the Motion Estimator [pp 208]

R. Cmar and S. Vernalde

In this paper a parametrizable architecture of a motion estimator (ME) is presented. The ME is designed as a generic full pixel calculation module which can be adopted for different video standards. The parameters by which the ME is described allow for a variety of architecture implementations. The parameters specify the level of parallelism reflected by multiple allocation of computational resources, and the use of configurable cache memories. The obtained VHDL description of the ME module is well suited for VLSI implementaion.

Design and Implementation of a Coprocessor for Cryptography Applications [pp 213]

A. Royo, J. Morán, and J.C. López

In this paper, an ASIC suitable for cryptography applications based on modular arithmetic techniques, is presented. These applications, such as for example digital signature (DSA) and public key encryption and decryption (RSA), use, as basic operation, the modular exponentiation. This ASIC works as a coprocessor with a special set of instructions specialized on dealing with high accuracy integers, as well as on the rapid evaluation of modular multiplications and exponentiations. The algorithm, the hardware architecture, the design methodology and the results are described in detail.

On the Way to the 2.5 Gbits/s ATM Network ATM Multiplexer Demultiplexer ASIC [pp 218]

J. Riesco, J.C. Díaz, L.A. Merayo, J.L. Conesa, C. Santos, and E. Juárez

The present paper describes the AMDA integrated circuit (ATM Multiplexer/Demultiplexor ASIC). The circuit has two operation modes: in multiplexer mode an ATM low speed flow (up to 622 Mbits/s) is inserted in the empty slots of a high speed ATM flow (2.5 Gbits/s); in demultiplexer mode, the cells belonging to the low speed channels are extracted from the high speed ATM flow. An specific algorithm of distributed control has been developed, simulated and implemented, in order to guarantee an even bandwidth distribution independently of the network node position. The circuit is able to handle 8K connections, with four different qualities of service; it manages a local queue of up to 16K ATM cells using an external high speed SSRAM. The maximum clock frequency of the circuit is 155,52 MHz and it has been processed with the LSI-LOGICs LCB500K technology (0,5 mm CMOS). It contains 34800 equivalent gates, 48 Kbit of single port memory and 8,5 Kbit dual port memory, using an area of 6,7 x 6,7 mm and it is packaged in a 208 pins QFP.

Session 4C: Decision Diagrams and Diagnosis

Solving Graph Optimization Problems with ZBDDs [pp 224]

O. Coudert

This paper presents a ZBDD (Zero-Suppressed Binary Decision Diagram) based framework that solves a collection of graph optimization problems. We show how these problems reduce to three primitive problems, and how the later can be solved exactly using ZBDDs. The application of this framework is illustrated on multi-layer planar routing, where it can solve real-life instances that cannot be handled otherwise.

Minimizing ROBDD Sizes of Incompletely Specified Boolean Functions by Exploiting Strong Symmetries [pp 229]

C. Scholl, S. Melchior, G. Hotz, and P. Molitor

We present a method computing a minimum sized partition of the variables of an incompletely specified Boolean function into symmetric groups. The method can be used during minimization of robdd s of incompletely specified Boolean functions. We apply it as a preprocessing step of symmetric sifting presented by Panda [24] and Möller [20] and of techniques for robdd minimization of incompletely specified Boolean functions presented by Chang [6] and Shiple [28]. The technique is shown to be very effective: it improves robdd sizes of symmetric sifting by a factor of 51% and by a factor of 70% in combination with a slightly modified version of the technique of Chang and Shiple.

Connection Error Location and Correction in Combinational Circuits [pp 235]

A.M. Wahba and D. Borrione

We present new diagnostic algorithms for localizing connection errors in combinational circuits. Three types of errors are considered: extra, missing, and bad connection errors. Special test patterns are generated to rapidly locate the error. The algorithms are integrated within the Prevail TM system. Results on bench-marks show that the error is always located, within a time proportional to the product of the circuit size, and the number of used patterns.

Session 4D: Performance Modeling

Shaping a VLSI Wire to Minimize Elmore Delay [pp 244]

J.P. Fishburn

Application of the herarchical Schur algorithm to the boundary element method for 3D capacitance extraction shifts the speed bottleneck from inversion of the influence matrix to its calculation. We show how the numerical integration required for the latter can be accelerated by an oder of magnitude with the aid of a multipole expansion in Cartesian formulation. The scheme differs essentially from that of the FASTCAP extractor.

Inductance Analysis of On-Chip Interconnects [pp 252]

S. Kundu and U. Ghoshal

It is generally believed that inductance analysis of on-chip interconnect becomes important when the clock frequency of circuits rise above GHz level. In this paper we show that this perception is not true. It becomes necessary to consider the inductive effects in all circuits implemented in deep submicron CMOS technologies. For 0.25 mm (lithography) technologies, where the supply voltage is expected to be in the range of 1.2-1.8 V, inductive effects are an important consideration regardless of system frequency. Furthermore, contrary to the popular belief, we show that inductive effects are important even for highly resistive lines.

Cartesian Multipole Based Numerical Integration for 3D Capacitance Extraction [pp 256]

U. Geigenmüller and N.P. van der Meijs

Euler's differential equation of the calculus of variations is used to determine the shape of a VLSI wire that minimizes Elmore delay. The solution is given as a power series whose coefficients are formulas involving the load-end wire width, the load capacitance, the capacitance per unit area, and the capacitance per unit perimeter. In contrast to an optimal-width rectangular wire, the RC Elmore delay of the optimally tapered wire goes to zero as the driver resistance goes to zero. The optimal taper is immune, to first order, to process variations affecting wire width.

Session 5A: Hot Topic HT1 - Networked CAD Systems

Session 5B: Progress in IDDQ Test Technology

CCII+ Current Conveyor Based BIC Monitor for IDDQ Testing of Complex CMOS Circuits [pp 266]

V. Stopjaková and H. Manhaeve

In this paper, a quiescent built-in current (BIC) monitor based on a second generation current conveyor CCII+ is presented. The monitor circuit minimises the power supply voltage degradation and provides a sensitive detection of defects that cause an elevated value of the IDDQ current. The proposed monitor offers an accurate current measurement and has a wide operation range. The CCII+ based current monitor is able to handle huge digital ASICs. Significant results summarising possibilities and limitations of the circuit are discussed as well. The design was implemented through Alcatel-Mietec 0.7mm CMOS technology and an evaluation of the prototype chips has been carried out. An experimental application of the proposed monitor in new analogue self-test structure was considered.

Deep Sub-Micron IDDQ Testing: Issues and Solutions [pp 271]

M. Sachdev

The effectiveness of IDDQ testing in deep sub-micron is threatened by the increased transistor sub-threshold leakage current. In this article, we survey possible solutions and propose a deep sub-micron IDDQ test mode. The methodology provides means for unambiguous measurements of IDDQ components and defect diagnosis. The effectiveness of the test mode is demonstrated with a real life example.

A Production-Oriented Measurement Method for Fast and Exhaustive Iddq Tests [pp 279]

B. Laquai, H. Richter, and H. Werkmann

The paper describes a measurement method to perform an iddq test on each vector of a test pattern. The measurement is performed using the functional test mode of a digital tester. Vector rates between 100KHz and 10MHz yield a current resolution of 10uA to 100uA.The great advantage of the method is that the measurements are performed by using only the testers pin electronic and the existing control software. No additional equipment is neccessary and the setup of the loadboard is made without any additional components except a buffering capacitance for the device, if needed. The application of the method to the iddq test of an 8 bit microcontroller is described.

Session 5C: Architecture Exploration

Library Mapping for Memories [pp 288]

P.K. Jha and N.D. Dutt

We present a library mapping technique that synthesizes a source memory module from a library of target memory modules. We define the library mapping problem for memories, identify and solve the three subproblems of port, bit-width and size (word) mapping associated with this task and finally combine these solutions into an efficient memory mapping algorithm. Experimental results on a number of memory-intensive designs demonstrate that our memory mapping approach generates a wide variety of cost-effective designs, often counter-intuitive ones, based on a user- given cost function and the target library.

Architectural Exploration and Optimization for Counter Based Hardware Address Generation [pp 293]

M. Miranda, M. Kaspar, F. Catthoor, and H. De Man

A set of automated system level techniques is presented for architectural exploration and optimization of counter based address generation units in real time signal processign systems. The goal is to explore different architectural alternatives available when mapping array references in order to select the most promising ones in area cost. The techniques are demonstrated on realistic test-vehicles, showing that architectural decision at early stages of the design process, can have a very large impact on the resulting area figure.

RTL Synthesis with Physical and Controller Information [pp 299]

M. Xu and F.J. Kurdahi

The current technology advances towards deep submicron have made it indispensable to consider layout and controller effects during all phases of chip synthesis. This paper proposes a paradigm for incorporating such information when synthesizing anRTL design from a scheduled behavioral specification. Experimental results corroborate the fact that layout and controller effects on chip area and performance are significant and can not be ignored.

Session 5D: Layout Design

Two-Way Partitioning Based on Direction Vector [pp 306]

K.S. Seong and C.M. Kyung

In spectral method, the vertices in a graph can be mapped into the vectors in d-dimensional space, thus the vectors are partitioned instead of vertices to obtain graph partitioning. In this paper, we show a method to obtain optimal two-way vector partitioning based on optimal direction vector. As the problem to find the optimal direction vector is NP-problem, we propose an efficient heuristic to obtain high quality direction vector. As we approximate a given netlist into the graph and only use ten eigenvectors in practice, there is a chance to improve the solution quality by local optimization. Fiduccia-Mattheyses algorithm is employed as a post processing. Compared with FM and MELO, the proposed algorithm PDV reduces cutsize on the average 40% and 20.5%, respectively.

Multi-Layer Chip-Level Global Routing Using an Efficient Graph-Based Steiner Tree Heuristic [pp 311]

L-C.E. Liu and C. Sechen

We present a chip-level global router based on a new, more accurate global routing model for the multi-layer macro-cell technology. The routing model uses a 3-dimensional mixed directed/undirected routing graph, which accurately models the multi-layer routing problem. However, the complexity of the routing graph challenges previous route-generating algorithms. Generating the routes is to search for the Steiner minimum trees for the nets, which is an NP-hard problem. We developed an improved Steiner tree heuristic algorithm suitable for large routing graphs and able to generate high quality Steiner tree routing. Tested on industrial circuits, our algorithm yields comparable results while having dramatically lower time and space complexities than the leading heuristics[2][14]. While minimizing the wire length, our global router can also minimize the number of vias or solve the routing resource congestion problems.

A Gridless Multi-Layer Router for Standard Cell Circuits Using CTM Cells [pp 319]

H-P. Tseng and C. Sechen

We present a gridless multi-layer router suitable for standard cell circuits using central terminal model (CTM) cells. A CTM cell has pins in the middle which split the over-the-cell routing region into top and bottom parts. Our router routes nets in both the channel (if needed) and over-the-cell. The router uses a combined constraint graph and tile expansion algorithm. It achieves channelless solutions for the Primary1 circuit by routing over the cell in three layers. For classical channel routing examples, it achieves solutions at density for Deutschs difficult example in two, three, four and five metal layers. It also generates equal or better results compared to the best of the previous channel routers for all the examples we have tried.

Session 6A: Hot Topic HT2 - Deep Submicron CAD

Session 6B: Testability Solutions for Regular Structures

A Programmable Boundary Scan Technique for Board-Level, Parallel Functional Duplex March Testing of Word-Oriented Multiport Static RAMs [pp 330]

K. Chakraborty and P. Mazumder

A framework for integrating boundary scan (IEEE 1149.1) with board-level self-testing of word-oriented, mul-tiport static RAM chips is proposed. Innovative parallel versions of functional duplex march tests (FDMs) for detecting complex couplings are developed. This approach produces significantly smaller cycle-time penalty during normal operation than built-in self-testing (BIST). It pro-duces two orders of magnitude test acceleration as com-pared to pure boundary scan testing without BIST (i.e., by using EXTEST and SAMPLE/PRELOAD instructions only). Key words and phrases: Boundary scan, bus interface unit, march tests, functional duplex march algorithms (FDM)

Fault-Secure Shifter Design: Results and Implementations [pp 335]

R.O. Duarte, M. Nicolaidis, H. Bederr, and Y. Zorian

Self-checking design [2] is an on-line testability technique, that implements functional blocks delivering outputs belonging on an error detecting code. A checker monitoring this code performs error detection concurrent error detecting ability self-checking (S-C) circuits is of high interest for applications requiring high levels of reliability. S-C circuits will gain increasing industrial interest if they can be implemented with reduced hardware cost and design effort and they can offer high fault coverage. This work concerns the design of low cost, high fault coverage self-checking shifters. In order to achieve the reduced design effort the proposed solutions are implemented into a S-C shifters macro-block generator. This work is part of a broader effort concerning the development of low cost, high fault coverage solutions for S-C data paths, and the implementation of these solutions into a CAD tool. [3], [5], [6]

High-Speed C-Testable Systolic Array Design for Galois-Field Inversion [pp 342]

C-T. Huang and C-W. Wu

Systolic architectures for inversion in Galois eld (GF(2 m )) are presented. The proposed inversion algorithm is a counter-free extended Euclidean algorithm,which results in simple circuit implementation for GF inversion. Additionally, the bit-parallel implementation proposed is shown to be C-testable. Testability and modularity make it suited to VLSI implementation.

Session 6C: Data Converter Test Issues

Efficient and Accurate Testing of Analog-to-Digital Converters Using Oscillation-Test Method [pp 348]

K. Arabi and B. Kaminska

This paper describes a practical test approach for analog-to-digital converters (ADCs) based on the oscillation-test strategy. The oscillation-test is applied to convert the ADC under test to an oscillator. The oscillation frequencies are able to monitor the ADC conversion rate, differential nonlinearity (DNL) and integral nonlinearity (INL) at each quantization band edge (QBE). Using this method, no analog stimulus should be supplied and therefore the need for a costly precision signal generator is eliminated. Besides, as the oscillation frequency is evaluated using pure digital circuitry, test accuracy is increased. This test approach is not limited to a special kind of ADC. Simulations and practical implementation prove the efficiency of the proposed test approach for ADCs.

Built-In Self-Test Methodology for A/D Converters [pp 353]

R. de Vries, T. Zwemstra, E.M.J.G. Bruls, and P.P.L. Regtien

A (partial) Built-In Self-Test (BIST) methodology is proposed for analog to digital (A/D) converters. In this methodology the number of bits of the A/D converter that needs to be monitored externally in a test is reduced. This reduction depends, among other things, on the frequency of the applied test signal. At low test signal frequencies only the least significant bit (LSB) needs to be monitored and a 'full' BIST becomes feasible. An analysis is made of the trade-off between the size of the on-chip test circuitry and the accuracy of this BIST technique.
Keywords: A/D Converter, Mixed-Signal Test, BIST, Statistical Fault Analysis

Reconfigurable Data Converter as a Building Block for Mixed-Signal Test [pp 359]

E.K.F. Lee

A reconfigurable data converter (RDC) that can be configured to a number of ADCs and DACs having different speeds and resolutions for testing mixed-signal systems is proposed. It can be used as a building block in mixed-signal boundary scan or built-in self test (BIST) techniques. The RDC can also be configured as random noise generators and used as test stimuli in BIST. Since the required area of the proposed RDC is only slightly larger than that of a conventional pipelined ADC, it can be used in many mixed-signal systems.

Session 7A: Hot Topic HT3 - Multichip Packages for Consumer Applications

Session 7B: Extensions and Acceleration of Discrete Event Simulation

VHDL Extensions for Complex Transmission Line Simulation [pp 368]

P. Walker and S. Ghosh

This paper proposes extensions to the VHDL grammar and defines new semantics in the language to model the timing behavior of high frequency buses and clock lines with multiple, distinct taps in a VHDL description. The proposed language constructs utilize transmission line analysis to model the timing behavior but avoids the continuous time simulation by using line-events.

Acceleration of Behavioral Simulation on Simulation Specific Machines [pp 373]

M. Shoji, F. Hirose, S. Shimogori, S. Kowatari, and H. Nagai

Behavioral simulation is faster than gate-level logic simulation, however, the simulation speed is too slow for large systems. Simulation specific machines accelerated simulation by parallel processing. We developed the method to extract parallelism from behavioral descriptions for fast simulation utilizing these machines. We evaluated our methods utilizing CAD accelerator TP5000. By the extraction of the parallelism the simulation speed is accelerated about 7 times.

Exploiting Temporal Independence in Distributed Preemptive Circuit Simulation [pp 378]

P. Walker and S. Ghosh

In digital circuit simulation hidden opportunities for concurrent execution of models often exist, arising from the propagation delay associated with the generation of output events by the circuit models. An event prediction algorithm is developed to identify such parallelism thereby, increasing the simulation execution rate. The algorithm uses an event prediction network and simulates circuits asynchronously and deadlock free, while honoring the preemptive semantics associated with digital circuit simulation.

Session 7C: Analog Design and Layout Tools

Analogue Layout Generation by World Wide Web Server-Based Agents [pp 384]

L.T. Walczowski, D. Nalbantis, W.A.J. Waller, and K. Shi

A World Wide Web (WWW) based client/server system has been developed which allows server-side process independent layout generators to generate the design rule correct geometry of analogue components such as resistors, capacitors and transistors for a design system running on a local workstation. The complete system is based on the bidirectional interface between a WWW browser and a VLSI design system, with layout generators running remotely on a WWW server.

A Performance-Driven Placement Algorithm with Simultaneous Placeamp;& Route Optimization for Analog IC’s [pp 389]

J.A. Prieto, A. Rueda, J.M. Quintana, and J.L. Huertas

This paper presents a performance-driven placement algorithm for automatic layout generation of analog ICs. The main innovations of our approach are essentially: (i) an integrated Place&Route optimization algorithm which is able to provide a realistic measurement of the interconnect parasitics, that is a key issue in performance-driven approaches; and (ii) the simultaneous consideration in the cost function of two levels of symmetries: global symmetry with respect to virtual axes and local symmetry affecting groups of cells. The flexibility and efficiency of the algorithm is mainly due to the use of the same slicing-tree representation for placement and global routing, and to the heuristic algorithm we propose for the global routing estimate. The feasibility of the proposed approach has been demonstrated with several practical examples.

An Algorithm for Numerical Reference Generation in Symbolic Analysis of Large Analog Circuits [pp 395]

I. García-Vargas, M. Galán, F.V. Fernández, and A. Rodríguez-Vázquez

This paper addresses the problems arising in the calculation of numerical references (network function coefficients), essential for an appropriate error control in simplification before and during generation algorithms for symbolic analysis of large analog circuits. The conventional polynomial interpolation method reveals to be unable to handle the large circuit sizes needed, mainly due to the dramatic effect of round-off errors. This paper introduces a new algorithm able to accurately calculate the network function coefficients of large analog circuits in an efficient way.

Session 8A: Embedded Tutorial: Hardware and Software Co-Design in Europe and the USA —- A Collaborative Initiative

Session 8B: Power Modeling and Estimation

Adaptive Least Mean Square Behavioral Power Modeling [pp 404]

A. Bogliolo, L. Benini, and G. De Micheli

In this work we propose an effective solution to the main challenges of behavioral power modeling: the generation of models for the power dissipation of technology-independent soft macros and the strong dependence of power from input pattern statistics. Our methodology is based on a fast characterization performed by simulating the gate-level implementation of instances of soft macros within the behavioral description of the complete design. Once characterization has been completed, the backannotated behavioral model replaces the gate-level representation, thus allowing fast but accurate power estimates in a fully behavioral context. Our power characterization procedure is a very efficient process that can be easily embedded in synthesis-based design ows. No additional effort is required from the designer, since power characterization merges seamlessly with a natural top-down design methodology with iterative improvement. After characterization, the behavioral power simulation produces accurate average and instantaneous power estimates (with errors around 7% and 25%, respectively, from accurate gate-level power simulation).

Fast Power Loss Calculation for Digital Static CMOS Circuits [pp 411]

S. Gavrilov, A. Glebov, S. Rusakov, D. Blaauw, L. Jones, and G. Vijayan

In this paper, we present a new dynamic power estimation method that produces accurate power measures at considerably faster run times. The approach uses an enhanced switch-level simulation algorithm that takes into account both short-circuit power and charge-sharing power effects. In benchmarks against a popular commercial power simulation tool, our approach yields power measurements on average within 3% of the commercial solution, while taking between 15 to 20 times less CPU time.

Monte-Carlo Approach for Power Estimation in Sequential Circuits [pp 416]

V. Saxena, F.N. Najm, and I.N. Hajj

In this paper we present a Monte-Carlo based statistical techniques for estimating power in sequential circuits. Mutually independent samples of power are generated by simulating multiple copies of the circuit. Since the approach is simulation-based, spatiotemporal correlations are automatically accounted for. The algorithm iterates until the user-specified accuracy is achieved. Experimental results on ISCAS89 circuits show that reliable results can be obtained inconsiderably less time than that required by exhaustive simulation.

Session 8C: Formal Methods in Synthesis and Verification

Hybrid Symbolic-Explicit Techniques for the Graph Coloring Problem [pp 422]

S. Chiusano, F. Corno, P. Prinetto, and M. Sonza Reorda

This paper presents an algorithmic technique based on hybridizing Symbolic Manipulation Techniques based on BDDs with more traditional Explicit solving algorithms. To validate the approach, the graph coloring problem has been selected as a hard-to-solve prob-lem, and an optimized solution based on hybrid techniques has been implemented. Experimental results on a set of benchmarks derived from the CAD for VLSI area show the applicability of the approach to graphs with millions of vertices in a limited CPU time.

A Constructive Approach Towards Correctness of Synthesis - —Application within Retiming [pp 427]

D. Eisenbiegler, R. Kumar, and C. Blumenröhr

This paper is dedicated to correct synthesis. By correct synthesis we mean, that there is a mathematical proof telling us, that the output circuit description fulfills the input circuit description. There are several ways to achieve correct synthesis. In this paper, we present anovel approach which integrates conventional synthesis algorithms thus guaranteeing the same quality of designs. Our approach is fully automatic, although it is based on rule applications within a theorem prover. We compare our results in the area of retiming to other approaches.

A Symbolic Core Approach to the Formal Verification of Integrated Mixed-Mode Applications [pp 432]

S. Hendricx and L. Claesen

In the past, formal verification - the promising alternative to simulation-based verification has primarily been applied to digital system designs. Despite the ever-growing importance of integrated mixed analog/digital systems, hardly any formal approaches have been introduced to verify such designs. In this paper, a preliminary study of a symbolic modelling technique is presented, which allows us to formally verify the functional correctness of integrated mixed-mode systems. The usefulness of the approach has been demonstrated by verifying the SmartPen (TM), a practical integrated mixed-mode application.

Session 9A: Panel P2 - Are There Conflicts of Interest in Intellectual Property Based Business?

Coordinator: I. Bolsens, IMEC, Belgium
Moderator: M. Cecchini, OMI, CEC

Panel:
J. Goria, Italtel, Italy
M. Muller, ARM, UK
R. Lannoo, Alcatel-Mietec, Belgium
A. Wild, Motorola, USA
O. Levia, Cadence, USA
B. Barrera, Mentor Graphics, USA

Session 9B: Concurrent Checking

A Novel Methodology for Designing TSC Networks Based on Parity Bit Code [pp 440]

C. Bolchini, F. Salice, and D. Sciuto

Combinational circuits encoded with the parity bit code can be defined TSC if and only if the number of the observed out-puts modified by any admissible fault (fault observability) is odd. The methodology presented in this paper allows the use of the parity bit code by synthesizing an encoded network and then modifying the observability of each fault by introducing an auxiliary output, if necessary. In particular, the function implementing the auxiliary output allows an odd observability every time the observability of an internal node in the initial realization is even.

Testing Scheme for IC’s Clocks [pp 445]

M. Favalli and C. Metra

This paper proposes a testing scheme to detect abnormal skews between clock signals inside digital synchronous ICs. The scheme is based on a new CMOS sensing circuit whose compactness and testability with respect to a large set of failures make it suitable for both off-line and on-line testing.

A Totally Self-Checking 1-out-of-3 Code Error Indicator [pp 450]

A. Paschalis, N. Gaitanis, D. Gizopoulos, and P. Kostarakis

In this paper, an asynchronous TSC 1-out-of-3 (1/3) code error indicator is introduced that memorises erroneous 1/3 code inputs {001, 011, 101, 110, 111} with time duraction greater than a discrimination time T. Such an error indicator is used to discriminate transient erroneous 1/3 code inputs from real ones as well as to detect not only faults that cause logical errors but also delay faults (short or long) that alter the circuit delay outside its specified limits (upper or lower bounds) without causing logical errors. To our knowledge, our error indicator is the first TSC 1/3 code error indicator proposed in the open literature.

Session 9C: New Ideas in Scheduling

Cone-Based Clustering Heuristic for List-Scheduling Algorithms [pp 456]

S. Govindarajan and R. Vemuri

List scheduling algorithms attempt to minimize latency under resource constraints using a priority list. We propose a new heuristic that can be used in conjunction with any priority function. At each time-step, the proposed clustering heuristic tries to find a best match between ready operations and the resource set. The heuristic arbitrates among equal priority operations based on operation-clusters formed from the dependency graph. Based on this heuristic we have presented a new Cone-Based List Scheduling ( CBLS ) algorithm. Results presented in this paper compare CBLS with the well-known Force Directed List Scheduling ( FDLS ) algorithm, for several synthesis bench-marks. In cases where FDLS produces sub-optimal schedules, CBLS produces better schedules and in other cases CBLS performs as good as FDLS . Moreover, in conjunction with a simple priority function (namely the self-force ofanoperator), CBLS results in considerable improvement in latency when compared to FDLS that has the same priority function. Finally, we show that CBLS with the simple priority function performs better in execution time as well as latency when compared to the original FDLS that has a relatively complex priority function.

Register Synthesis for Speculative Computation [pp 463]

D. Herrmann and R. Ernst

Speculative computation and branch prediction have been used in high-performance processor design for many years. Recently, it has also been applied to high-level synthesis where a priori knowledge of possible control paths provides an even higher performance potential. One problem of speculative techniques is the circuit overhead necessary for correctness preservation. While in processors, overhead is high due to the required generality, high-level synthesis can, again, employ a priori knowledge. The paper presents a register synthesis and allocation technique for speculative computation with branch prediction which is based on life time trees. It creates shift register structures with little register and control overhead.

Multidimensional Periodic Scheduling: A Solution Approach [pp 468]

W.F.J. Verhaegh, P.E.R. Lippens, E.H.L. Aarts and J.L. van Meerbergen

We present a solution approach to the multidimensional periodic scheduling problem. We introduce the concept of multidimensional periodic operations in order to cope with problems originating from loop hierarchies and explicit timing requirements. We present an iterative algorithm for the scheduling problem, based on an ILP approach for checking the constraints, and we show some experimental results. Finally, we extend the solution approach to handle parametric descriptions.

Session 10A: System Level Design Representation and Transformation

Multi-Thread Graph: A System Model for Real-Time Embedded Software Synthesis [pp 476]

F. Thoen, J. Van Der Steen, G. de Jong, G. Goossens, and H. De Man

Software synthesis is a new approach which focuses on the support of real-time embedded multi-tasking software without the use of operating systems. A software synthesis system starts from a concurrent process system specification and maps this description automatically onto one or more processors. In this paper, the internal system-level model which captures the embedded software and which is the backbone of our software synthesis methodology, is presented. The model captures the fine-grain behaviour of a system, and supports multiple threads of control (concurrency), synchronisation, data communication, hierarchy and timing constraints.
Keywords - real-time embedded software, multi-tasking, software modelling, software synthesis.

PCC: A Modeling Technique for Mixed Control/Data Flow Systems [pp 482]

T. Grötker, R. Schoenen, and H. Meyr

Many signal processing systems make use of event driven mechanisms - typically based on finite state machines (FSMs) - to control the operation of the computationally intensive (data flow) parts. The state machines in turn are often fueled by external inputs as well as by feedback from the signal processing portions of the system. Packet-based transmission systems are a good example for such a close interaction between data and control flow. For a smooth design flow with a maximum degree of modularity it is of crucial importance tobe able to model the complete functionality of the system, containing both control and data flow, within one single design environment. While the degree of abstraction should be sufficiently high to model and simulate efficiently, the link to implementation has to be fully supported. For these reasons we developed acomputational model that integrates the specification of control and data flow. It combines the notion of multirate dynamic data flow graphs with event driven process activation. Thus, it maintains the exibility and expressive power of data flow representations while enabling designers to efficiently control these operations by incorporating control automata that may have been designed using protocol compilers or state machine tools [1].

Procedure Cloning: A Transformation for Improved System-Level Functional Partitioning [pp 487]

F. Vahid

Functional partitioning assigns the functions of a system's program-like specification among system components, such as standard-software and custom-hardware processors. We introduce a new transformation, called procedure cloning, that significantly improves functional partitioning results. The transformation creates a clone of a procedure for sole use by a particular procedure caller, so the clone can be assigned to the caller's processor, which in turn improves performance through reduced communication. We define several cloning heuristics that seek to clone the minimum number of procedures, a goal necessary to obtain the best improvements. We highlight experiments comparing our cloning heuristics and showing partition improvements with cloning.

Session 10B: Diagnosis and Test Generation

A Fault Diagnosis Methodology for the UltraSPARCTM-I Microprocessor [pp 494]

S. Narayanan, R. Srinivasan, R.P. Kunda, M.E. Levitt, and S. Bozorgui-Nesbat

In this paper we study the use of precomputed fault dictionaries to diagnose stuck-at and bridging defects in the UltraSPARC TM -I processor. In constructing the dictionary we analyze the effect of the dictionary format on parameters such as memory size, computational effort, and diagnostic resolution. The dictionary is built based onmodeled stuck-at faults. However to effectively diagnose both stuck-at and bridging faults, we employ a novel procedure that combines dictionary information with potential bridge defects extracted from layout. Experiments with failing devices show excellent correlation of predicted errors with actual defects.

Improved Diagnosis of Realistic Interconnect Shorts [pp 501]

J.T. de Sousa and P.Y.K. Cheung

Original diagnostic schemes for wire interconnect shorts are proposed. The idea is to use layout extracted realistic shorts and a broader range of short behaviour assumptions to derive the schemes. Results on real examples clearly show the superiority of the new schemes, both in terms of test size and diagnostic resolution.

On Improving Genetic Optimization Based Test Generation [pp 506]

I. Pomeranz and S.M. Reddy

Test generation procedures based on genetic optimization were shown to be effective in achieving high fault coverage for bench-mark circuits. In a genetic optimization procedure, the crossover operator accepts two test patterns t1 and t2 , and randomly copies parts of t1 and parts of t2 into one or more new test patterns. Such a procedure does not take advantage of circuit properties that may aid in generating more effective test patterns. In this work, we propose a representation of test patterns where subsets of inputs are considered as indivisible entities. Using this representation, crossover copies all the values of each subset either from t1 or from t2 . By keeping input subsets undivided, activation and propagation capabilities of t1 and t2 are captured and carried over to the new test patterns. The effectiveness of this scheme is demonstrated by experimental results.

Session 10C: Logic Synthesis for Low Power

Symbolic Synthesis of Clock-Gating Logic for Power Optimization of Control-Oriented Synchronous Networks [pp 514]

L. Benini, G. De Micheli, E. Macii, M. Poncino, and R. Scarsi

Recent results have shown that clock-gating techniques are effective in reducing the total power consumption of sequential circuits. Unfortunately, such techniques assume the availability of the state transition graph of the target system, and rely on explicit algorithms whose complexity is polynomial in the number of states, that is, exponential in the number of state variables. This assumption poses serious limitations on the size of the circuits for which automatic gated-clock generation is feasible. In this paper we propose fully symbolic algorithms for the automatic extraction and synthesis of the clock-gating circuitry for large control-oriented sequential designs. Our techniques leverage the compact BDD-based representation of Boolean and pseudo-Boolean functions to extend the applicability of gated- clock architectures to designs implemented by synchronous networks. As a result, we can deal with circuits for which the explicit state transition graph is too large to be generated and/or manipulated. Moreover, symbolic manipulation techniques allow accurate probabilistic computations; in particular, they enable the use of non-equiprobable primary input distributions, a key step in the construction of models that match the behavior of real hardware devices with a high degree of fidelity. The results are encouraging, since power savings of up to 36% have been obtained oncontrollers containing up to 21 registers.

Low Power FSM Design Using Huffman-Style Encoding [pp 521]

P. Surti, L.F. Cho, and A. Tyagi

This paper presents a novel approach to synthesize low power FSMs using non-uniform code length. Switching activity is reduced by decreasing the expected number of state bits switched less than [log|S|]. The state set S of the FSM is decomposed into two sets based on the limit state probabilities. The state set with very high probability is encoded with less than [log|S|] bits. The other state set, being less probable, is encoded using more than [log|S|] bits. To the best of our knowledge, this is the first time two code lengths are used for one state machine. This encoding is realized by using ip-ops with gated clock. The logic generating the enable signal of the clock uses only a single minterm. The state sets can be encoded using any uniform-length encoding algorithm with objectives of low power and low area. The experiments show an average of 13% and 18% reduction in power for two encoding algorithms respectively.

Improving the Accuracy of Support-Set Finding Method for Power Estimation of Combinational Circuits [pp 526]

H. Choi and S.H. Hwang

We address a way to improve the accuracy of support-set finding method for a probability-based power estimation of combinational circuits. Support-set finding methods to build local BDDs have been proposed to handle large circuits. However, because they consider only the shal-low reconvergence, they are not accurate enough to be used in the power optimization. To solve this problem, we propose a new algorithm, Feather algorithm, which can efficiently detect minimal support-set with 100% recon-vergent node detection rate. The experimental results show that the average error of our proposed method is 0.1% for the total power and 1.6% for the node-specific power.

Session 11A: System Design Methodologies

Practical Concurrent ASIC and System Design and Verification [pp 532]

I. Gibson and C. Amies

This paper describes the evolution of a design and verification methodology successfully used to develop advanced ASICs as components of multiple new commercial products. The ASICs are typically large, high speed, algorithmically complex and implement novel functionality. The ASIC development process is driven by the commercial pressures of low cost and short schedules of multiple projects. It is carried out using a team of designers of varying experience including new staff. The dual emphasis of our methodology is maintaining fine control over the design and verification process, together with full independent cross verification as an integral part of the entire ASIC and system development process.

A Methodology for Hardware Architecture Trade-Off at Different Levels of Abstraction [pp 537]

C. Schneider

In this paper a method of architecture exploration and selection is presented. Compared with other approaches, no special tools or modeling languages are needed-instead the models and tools of the ASIC design flow are used. The architecture trade-off process is performed iteratively, and considers information from different levels of abstraction in parallel. At system level, software and behavioral models, which are part of executable specifications are examined to get the necessary top-down information (performance). Bottom-up information (hardware costs) for irregular hardware structures is obtained by generating, analyzing and synthesizing VHDL code at RT-Level. For regular structures, formulas or tables can be used to estimate area and timing. The proposed approach was successfully performed for parts of a multimedia design, where an executable specification (in 'C') was available together with the standard.

Synthesis of Multi-Rate and Variable Rate Circuits for High Speed Telecommunications Applications [pp 542]

P. Schaumont, S. Vernalde, L. Rijnders, M. Engels, and I. Bolsens

A design methodology for the synthesis of digital circuits used in high throughput digital modems is presented. The methodology spans digital modem design from the link level to the gate level. The methodology uses a C++-based untimed data ow system description, which is gradually refined to an optimized, bit-true and clock cycle true C++-description. Through this refinement, a bridge from link level design semantics to architectural VHDL semantics is made within one and the same environment.

Session 11B: Testability at Different Abstraction Levels

Testability of 2-Level AND/EXOR Circuits [pp 548]

R. Drechsler, H. Hengster, H. Schäfer, J. Hartmann, and B. Becker

It is often stated that AND/EXOR circuits are much easier testable than AND/OR circuits. This statement only holds for restricted classes of AND/EXOR expressions, like positive polarity Reed-Muller expressions and fixed polarity Reed-Muller expressions. For these two classes of circuits good deterministic testability properties are known. In this paper we show that for these circuits also good random pattern testability can be proven. An input probability distribution is given which yields a short expected test length for biased random patterns. This is the first time that theoretical results on random pattern testability are presented for 2-level AND/EXOR circuit realizations of arbitrary Boolean functions. For more general classes of 2-level AND/EXOR circuits analogous results are not proven. We present experimental results that show that in general minimized 2-level AND/OR circuits are as well (or badly) testable as minimized 2-level AND/EXOR circuits.

On the Use of Reset to Increase the Testability of Interconnected Finite- State Machines [pp 554]

I. Pomeranz and S.M. Reddy

We propose a DFT solution for synchronous sequential circuits described as interconnections of finite-state machines, that takes into account specific requirements for justification of test sequences and propagation of fault effects occurring during test generation. We present this solution in the context of the output sequence justification problem. The proposed DFT solution is based on the use of reset. Three types of reset mechanisms are considered, having increasing overhead and increasing flexibility. The third type allows every output sequence over the output alphabet of a machine to be justified.

A New Approach to Build a Low-Level Malicious Fault List Starting from High-Level Description and Alternative Graphs [pp 560]

A. Benso, P. Prinetto, M. Rebaudengo, M. Sonza Reorda, and R. Ubar

In this paper a new approach is presented to build a list of faults to be used by the fault injection environment; the list is built starting from a high-level description of the system. The approach especially aims at identifying malicious faults i.e., faults having a critical impact on the system reliability. To overcome the complexity problem inherent in low-level descriptions, high-level ones are exploited, and alternative graphs are applied to carry out the cause-effect analysis, to build up a fault tree and to carry out fault collapsing. The reduced high-level malicious fault list is converted so that it can be used together with the low level description for the final fault injection.

Session 11C: Hardware and Software Tools for Analog and Mixed-Signal Test

On-Chip Analog Output Response Compaction [pp 568]

M. Renovell, F. Azaïs, and Y. Bertrand

In this paper, we propose a technique for on-chip analog output response compaction in order to implement self-test capabilities in analog and mixed-signal integrated circuits. The integration function is identified as a powerful analog compression scheme and an analog signature analyzer is proposed. The opamp-based implementation allows to define single and multiple-input versions. The multiple-input analyzer permits the monitoring of some extra internal nodes in addition to the classical output nodes, or the concurrent control of both voltage and current levels. This ability leads to an improvement of the circuit testability and consequently, the on-chip response evaluation gives a higher fault coverage than the off-chip one.

A New Quality Estimation Methodology for Mixed-Signal and Analogue ICs [pp 573]

T. Olbrich, I.A. Grout, Y. Eben Aimine, A.M. Richardson, and J. Contensou

IC product quality is commonly described as the faulty device level at shipment and is becoming an increasingly important metric in the Microelectronics Industry. This paper presents and demonstrates a quality estimation approach based on Inductive Fault Analysis for mixed-signal and analogue ICs, that quantitatively models the quality related parameters prior to production. It is shown how the approach can be used to optimise the manufacturing test program.

Compact Structural Test Generation for Analog Macros [pp 581]

V. Kaal and H. Kerkhoff

A structural, fault-model based methodology for the generation of compact high-quality test sets for analog macros is presented. Results are shown for an IV-converter macro design. Parameters of so-called test configurations are optimized for detection of faults in a fault-list and an optimal selection algorithm results in determining the best test set. The distribution of the results along the parameter-axes of the test configurations is investigated to identify a collapsed high-quality test set.

Session 11D: Power Estimation and Modeling

Accurate High Level Datapath Power Estimation [pp 590]

J.E. Crenshaw and M. Sarrafzadeh

The cubic switching table, is a new data structure for estimating datapath switching at a high level. It is constructed during behavioral simulation, and is used to estimate the switching for any particular datapath schedule and binding. Time to extract the estimate from the table is independent of the original simulation size. For n operations in the RTL description, it takes O ( n 3 ) time to perform the extraction. We show that an exact switching table would require exponential size, but experimental results show that the cubic table is accurate, with typical error under 5%.

Maximizing the Weighted Switching Activity in Combinational CMOS Circuits Under the Variable Delay Model [pp 597]

S. Manich and J. Figueras

A methodology to find the couple of vectors maximizing the weighted switching activity in combinational CMOS circuits under variable delay model is presented. The weighted switching activity maximization problem is shown to be equivalent to a fault testing problem on a transformed circuit. A maximum weighted switching activity is achieved by test vectors covering a selected set of faults of the transformed circuit. Automatic Test and Pattern Generation tools are used to find the maximizing pair of vectors. The validity of the proposed is demonstrated on the ISCAS-85 benchmark circuits and the results show that the simulation time is reduced by an order of magnitude and the estimation of the maximum weighted switching activity is improved in comparison with pseudo-random sample simulation.

Internal Power Modelling and Minimization in CMOS Inverters [pp 603]

S. Turgis, J.M. Daga, J.M. Portal, and D. Auvergne

We present in this paper an alternative for the internal (short-circuit and overshoot) power dissipation estimation of CMOS structures. Using a first order macro-modelling, we consider submicronic additional effects such as: input slew dependency of short-circuit currents and input-to-output coupling. Considering an equivalent capacitance concept we directly compare the different power components. Validations are presented by comparing simulated values (HSPICE level 6, foundry model 0.7 um) to calculated ones. Application to buffer design enlightens the importance of the internal power component and clearly shows that common sizing alternatives for power and delay minimization can be considered.

Poster Session :

A New Field Programmable System-on-a-Chip for Mixed-Signal Integration [pp 610]

J. Faura, C. Horton, B. Krah, J. Cabestany, M.A. Aguirre, and J.M. Insenser

A new RAM-based, mixed-signal, multicontext dynamically reconfigurable Field Programmable Device with on-chip microprocessor is described. A completely integrated mixed-signal CAD and microprocessor programming environment is used to design and simulate electronic systems composed by microprocessor code and digital and analog hardware. The very flexible communication between the microprocessor, the configurable digital cells and the programmable analog blocks makes possible powerful integration, real-time emulation (internal signals and configuration are available to the microprocessor) and advanced run-time reconfiguration.

PROPHID: A Data-Driven Multi-Processor Architecture for High-Performance DSP [pp 611]

J.A.J. Leijten, J.L. van Meerbergen, A.H. Timmer, and J.A.G. Jess

PROPHID is a design method for high-performance systems with a focus on high-throughput signal processing applications. It makes use of a novel stream-based multi-processor architecture, consisting of data-driven autonomous processors interconnected by a programmable connection network. The key element is the communication arbiter, which controls the flow of data between processors. Variable rates and data-dependent processing times are handled efficiently by performing scheduling at run-time. We give an overview of the characteristics and advantages of the architecture as well as some implementation results.

ReCode: The Design and Re-Design of the Instruction Codes for Embedded Instruction-Set Processors [pp 612]

C. Liem, P. Paulin, and A. Jerraya

A Real-Time Smart Sensor System for Visual Motion Estimation [pp 613]

T. Röwekamp and L. Peters

We present a new smart sensor architecture for visual motion - optical flow - estimation. As the system operates in real-time it is very well suited for collision avoidance on autonomous mobile platforms. The core of the system is an ASIC in standard digital CMOS technology, which forms a pipeline with feedback path for on-line image processing. The presented implementation was tested on image frames of 128 x 128 pixel size.

Full Custom Chip Set for High Speed Serial Communications up to 2.48Gbit/s [pp 614]

J. González-Torres, P.A. Mateos, and J.M. Hernández

An Asynchronous Architecture for Digital Signal Processors [pp 615]

M.R. Karthikeyan and S.K. Nandy

We propose an asynchronous[1] architecture for digital signal processors. This is based on a modification of the counter ow pipeline[2]. In addition to registers, we apply the counter ow technique to memory operands as well. This results in an asynchronous architecture with good performance potential for DSP. We describe the architecture below.

Test Synthesis for DC Test of Switched-Capacitors Circuits [pp 616]

H. Ihs and C. Dufaza

SISSSI—A Tool for Dynamic Electro-Thermal Simulation of Analog VLSI Cells [pp 617]

V. Székely, A. Páhi, A. Poppe, M. Rencz, and A. Csendes

Design of Oscillation-Based Test Structures for Active RC Filters [pp 618]

M. Santo Zarnik, F. Novak, and S. Macek

We apply the oscillation-based test strategy [1] to test active RC filters. We develop general guidelines for the design of the oscillation-based test structures and describe in more details the resonator active filter (biquad filter) configuration. It can be shown that some of the derived structures are achieved by simple circuit modification while for the more general case additional feedback loop network is required.

Using Constraint Logic Programming in Memory Synthesis for General Purpose Computers [pp 619]

R. Beckmann and J. Herrmann

In modern computer systems the performance is dominated by the memory performance. Currently, there is neither a systematic design methodology nor a tool for the design of memory systems for general purpose computers.We present a first approach to CAD support for this crucial subtask of system level design. Dependencies between influencing factors and design decisions are explicitly represented by constraints, and constraint logic programming is used to make the design decisions. The memory design is optimized with respect to several objectives by iterating the (re)design cycle. Event driven simulation is used for evaluation of the intermediate results. The system is organized as an interactive design assistant.

Optimal Scheduling for Fast Systolic Array Implementations [pp 620]

I. Ozimek, R. Verlic, and J. Tasic

Certain real-time applications (e.g. signal filtering and processing in a digital communication system) require the use of a special massively parallel computing structure, called the systolic array structure, to achieve acceptable performance. To implement an algorithm this way, we need a mapping procedure to map a set of equations, which describe the algorithm, to the systolic array. This mapping consists of scheduling (i.e. time mapping, mapping of each DG node to a particular time instant) and space mapping (mapping of each DG node to a systolic array cell). In the paper we propose a new approach to scheduling of complicated algorithms (that are described by a set of equations, fulfilling the requirement of regularity, i.e. constant dependence vectors). It takes into account the exact computational requirements of the basic arithmetic operations used, and yields near optimal scheduling from the viewpoint of execution speed of the resulting implementation.

Scheduling Using Mixed Arithmetic: An ILP Formulation [pp 621]

A. Mignotte and O. Peyran

We present a way to automatically select, within an architectural synthesis tool, the best operand and operator number systems, in order to find the best speed/area tradeoff. This implies the use of different number systems (redundant and non-redundant) for the same design: this is what we call mixed arithmetics. We present an ILP formulation to solve a scheduling problem.

Performance Verification Using Partial Evaluation and Interval Analysis [pp 622]

J. Walrath, R. Vemuri, and W. Bradley

Design and Verification of the Sequential Systems Automata Using Temporal Logic Specifications [pp 623]

A. Ursu, G. Gruita, and S. Zaporojan

A design and verification method of sequential systems automata using temporal logic specifications is proposed. The method is based on well-known Z.Manna and P.Wolper temporal logic satisfiability analysis procedure. A new satisfiability analysis algorithm for temporal logic specifications which includes past time as well as future time temporal logic operators is proposed. A case study is carried out which deals with two design examples.

Application Independent Module Generation in Analog Layouts [pp 624]

M. Wolf and U. Kleine

This paper presents a new feature for a module generator environment that performs application independent module description in analog layouts. With the help of a special capacitance sensitivity matrix one module description can be used for different applications.

A Scheme for Multiple On-Chip Signature Checking for Embedded SRAMs [pp 625]

M.F. Abdulla, C.P. Ravikumar, and A. Kumar

Pseudorandom self testing of embedded memories is commonly used because of its simplicity [1]. A novel scheme pseudorandom testing with multiple-on-chip signature checking (MOSC) has been proposed in [2]. Although this scheme results in significant reductions in aliasing probability at no significant increase in area in most cases, the test area and time overhead may be excessive if the circuit contains multiple embedded RAMs of various sizes. Example of such circuits are the ASICs for the telecommunications. In this paper, we propose a Static-RAM BIST scheme, based on the MOSC scheme, which is applicable for testing chips that have multiple embedded RAMs of various sizes.

Design of Partially Parallel Scan Chain [pp 626]

Y. Higami and K. Kinoshita

This paper presents a design-for-testability technique, called partially parallel scan chain ( PPSC ), which aims at reduction of test length for sequential circuits. Since the partially parallel scan chain allows to control and observe subset of flip-flops (FFs) concurrently during scan shift operations, the number of scan shift clocks is reduced.

March LA: A Test for Linked Memory Faults [pp 627]

A.J. van de Goor, G.N. Gaydadjiev, V.N. Yarmolik, and V.G. Mikitjuk

The Input Pattern Fault Model and Its Application [pp 628]

R.D. Blanton and J.P. Hayes

A Monolithic Off-Chip IDDQ Monitor [pp 629]

M. Svajda, B. Straka, and H. Manhaeve

An integrated off-chip IDDQ measuring unit (IOCIMU) is described in this paper. The semi-digital current monitor is designed for the use with standard automatic test equipment (ATE). Simulations of the monolithic monitor implemented in a 2- mm BiCMOS technology show an accuracy better than 1% for currents in the range from 0 to 1mA and a test rate up to 10kHz.

Extension of the Boundary-Scan Architecture and New Idea of BIST for More Effective Testing and Self-Testing of Interconnections [pp 630]

A. Kristof

The approach presented in this paper enables more effective testing of on-board and board-to-board interconnections and significantly simplifies the interconnection self-testing. Some extensions must be added to the Boundary Scan Architecture which however do not violate the JTAG/IEEE1149.1 standard requirements. Benefits are the reduced complexity and cost of an on-board testing unit as well as better test performance.