17093290
An efficient algorithm for finding the k longest testable paths through each gate in a combinational circuit
Testing the K longest paths through each gate (KLPG) in a circuit detects the smallest local delay faults under process variation. In this work a novel automatic test pattern generation (ATPG) methodology to find the K longest testable paths through each gate in a combinational circuit is presented. Many techniques are used to significantly reduce the search space. The results on the ISCAS benchmark circuits show that this methodology is very efficient and able to handle circuits with an exponential number of paths, such as c6288.
326056
A circuit level fault model for resistive bridges
Delay faults are an increasingly important test challenge. Modeling bridge faults as delay faults helps delay tests to detect more bridge faults. Traditional bridge fault models are incomplete because these models only model the logic faults or these models are not efficient to use in delay tests for large circuits. In this article, we propose a physically realistic yet economical resistive bridge fault model to model delay faults as well as logic faults. An accurate yet simple delay calculation method is proposed. We also enumerate all possible fault behaviors and present the relationship between input patterns and output behaviors, which is useful in ATPG. Our fault simulation results show the benefit of at-speed tests.
283023
Typed memory management in a calculus of capabilities
An increasing number of systems rely on programming language technology to ensure safety and security of low-level code. Unfortunately, these systems typically rely on a complex, trusted garbage collector. Region-based type systems provide an alternative to garbage collection by making memory management explicit but verifiably safe. However, it has not been clear how to use regions in low-level, type-safe code.We present a compiler intermediate language, called the Capability Calculus, that supports region-based memory management, enjoys a provably safe type system, and is straightforward to compile to a typed assembly language. Source languages may be compiled to our language using known region inference algorithms. Furthermore, region lifetimes need not be lexically scoped in our language, yet the language may be checked for safety without complex analyses. Finally, our soundness proof is relatively simple, employing only standard techniques.The central novelty is the use of static capabilities to specify the permissibility of various operations, such as memory access and deallocation. In order to ensure capabilities are relinquished properly, the type system tracks aliasing information using a form of bounded quantification.
37536130
On Encoding p-pi in m-pi
This paper is about the encoding of pπ, the polyadic π-calculus, in mπ, the monadic π-calculus. A type system for mπ processes is introduced which captures the interaction regime underlying the encoding of pπ processes respecting a sorting. A full-abstraction result is shown: two pπ processes are typed barbed congruent iff their mπ encodings are monadic-typed barbed congruent.
1745513
Test generation for global delay faults
This paper describes test generation for delay faults caused by global process disturbances. The correlations between path delays is used to reduce the number of paths that must be tested. We build macro models of path delays as a function of process parameters to reduce test generation time. The test generation problem is formulated as a nonlinear optimization using a set of candidate paths supplied by a path generator. Results are given for the ISCAS85 benchmarks.
980425
Stack-Based Typed Assembly Language
In previous work, we presented a Typed Assembly Language (TAL). TAL is sufficiently expressive to serve as a target language for compilers of high-level languages such as ML. This work assumed such a compiler would perform a continuation-passing style transform and eliminate the control stack by heap-allocating activation records. However, most compilers are based on stack allocation. This paper presents STAL, an extension of TAL with stack constructs and stack types to support the stack allocation style. We show that STAL is sufficiently expressive to support languages such as Java, Pascal, and ML; constructs such as exceptions and displays; and optimizations such as tail call elimination and callee-saves registers. This paper also formalizes the typing connection between CPS-based compilation and stack-based compilation and illustrates how STAL can formally model calling conventions by specifying them as formal translations of source function types to STAL types.
45540078
Timing analysis of combinational circuits including capacitive coupling and statistical process variation
Capacitive coupling between interconnects can lead to pattern-dependent delay variation. Statistical process fluctuations result in variation in gate and interconnect delays, and interconnect coupling. These effects become increasingly important in deep submicron circuits. In this work we describe a statistical timing analyzer for combinational circuits that takes these effects into account. The tool searches for input vectors that sensitize the longest path and maximizes the delay on these paths due to capacitive coupling. The best and worst-case timing on the paths is then computed using random gate delay variation and spatially-correlated interconnect parasitic variation. We demonstrate timing analysis results on a subset of the ISCAS85 circuits.