waashk/dblp huggingface dataset:
symbolic algebra and timing driven data-flow synthesis. the growing market of multi-media applications has required the development of complex asics with significant data-path portions. unfortunately, most high-level synthesis tools and methods cannot automatically synthesize data paths such that complex arithmetic library blocks are intelligently used. symbolic computer algebra has been previously used to automate mapping data flow into a minimal set of complex arithmetic components. in this paper, we present extensions to the previous methods in order to find the minimal critical path delay (cpd) mapping. a new algorithm is proposed that incorporates symbolic manipulations such as tree-height-reduction, factorization, expansion, and horner transformation. such manipulations are used as guidelines in initial library element selection. furthermore, we demonstrate how substitution can be used for multi-expression component sharing and critical path delay optimization.
simultaneous design and placement of multiplexed chemical processing systems on microchips. microchip structures represent an attractive platform for microscale chemical processing of fluidic systems. however, standardized design methods for these devices have not yet been developed. here we describe our work toward adapting traditional soc circuit design techniques for the synthesis of fully customized and multiplexed lab-on-a-chip (loc) devices. we discuss our formulation of the multiplex layout problem and present an approach for the design of microchip based electrophoretic separation systems. this work is extendable to systems incorporating mixing and reaction.
variational interconnect analysis via pmtbr. we demonstrate an algorithm for interconnect modeling in the presence of process variation based on extension of the truncated balanced realization model reduction algorithm to multi-dimensional, parameter varying systems. our scheme, based on a set of estimators of the variational tbr projection spaces, is simple to implement, contains embedded error estimators, and leads to nearly optimally sized models.
analog macromodeling using kernel methods. in this paper we explore the potential of using a general class offunctional representation techniques, kernel-based regression, inthe nonlinear model reduction problem. the kernel-based view-pointprovides a convenient computational framework for regression,unifying and extending the previously proposed polynomialand piecewise-linear reduction methods. furthermore, as many familiarmethods for linear system manipulation can be leveraged ina nonlinear context, kernels provide insight into how new, morepowerful, nonlinear modeling strategies can be constructed. wepresent an svd-like technique for automatic compression of non-linearmodels that allows systematic identification of model redundanciesand rigorous control of approximation error.
simulation approaches for strongly coupled interconnect systems. shrinking feature sizes and increasing speeds of operation make interconnect-related effects very relevant for current circuit verification methodologies. reliable and accurate system verification requires the full analysis of circuits together with the environment that surrounds them, including the common substrate, the packaging structures, and perhaps even board information. in this paper we discuss circuit-level simulation algorithms that enable the analysis of the impact of strongly coupled interconnect structures on nonlinear circuit operation, so as to allow reliable and accurate system verification.
a precorrected-fft method for capacitance extraction of complicated 3-d structures. in this paper we present a new approach to three-dimensional capacitance extraction based on a precorrected fft scheme. the approach is compared to the now commonly used multipole-accelerated algorithms for a variety of structures, and the new method is shown to have substantial performance and memory advantages.
coping with rc(l) interconnect design headaches. physical interconnect effects have a dominant impact on today's deep submicron ic designs. in this tutorial paper we will describe the technology trends which have brought about this interconnect dominance, then consider some of the modeling and analysis approximations available for both pre- and post-layout interconnect design. this coverage will not be an exhaustive summary, but one that is primarily focused on moment-based analysis techniques, from the elmore delay, to the more recent advances in moment-matching approximations, and the corresponding nonlinear driver/load interfaces. future modeling, analysis, and design challenges will be considered throughout this paper.
multi-level synthesis for safe replaceability. we describe the condition that a sequential digital design is a safe replacement for an existing design without making any assumptions about a known initial state of the design or about its environment. we formulate a safe replacement condition which guarantees that if an original design is replaced by a new design, the interacting environment cannot detect the change by observing the input-output behavior of the new design; conversely, if a replacement design does not satisfy our condition an environment can potentially detect the replacement (in this sense the replacement is potentially unsafe). our condition allows simplification of the state transition diagram of an original design. we use the safe replacement condition to derive a sequential resynthesis method for area reduction of gate-level designs. we have implemented our resynthesis algorithm and we report experimental results.
simulation based test generation for scan designs. we describe a simulation-based test generation procedure for scan designs. a test sequence generated by this procedure consists of a sequence of one or more primary input vectors embedded between a scan-in operation and a scan-out operation. we consider the set of faults that can be detected by test sequences of this form, compared to the case where scan is applied with every test vector. the proposed procedure constructs test sequences that traverse as many pairs of fault-free/faulty states as possible, and thus avoids the use of branch-and-bound test generation techniques. additional techniques are incorporated into this basic procedure to enhance its effectiveness.
on undetectable faults in partial scan circuits. we provide a definition of undetectable faults in partial scan circuits under a test application scheme where a test consists of primary input vectors applied at-speed between scan operations. we also provide sufficient conditions for a fault to be undetectable under this test application scheme. we present experimental results on finite-state machine benchmarks to demonstrate the effectiveness of these conditions in identifying undetectable faults.
on application of output masking to undetectable faults in synchronous sequential circuits with design-for-testability logic. design-for-testability (dft ) for synchronous sequentialcircuits causes redundant faults in the original circuit to bedetectable in the circuit with dft logic. it has beenargued that such faults should not be detected in order toavoid reducing the yield unnecessarily. one way to dealwith such faults is to mask (or ignore) their fault effectswhen they appear on the circuit outputs, without maskingthe detection of faults that need to be detected. to investigatethe extent to which this can be accomplished, wedescribe a procedure for masking the effects of redundantfaults of the original circuit under a given test set generatedfor the circuit with dft logic. the procedureattempts to maximize the number of redundant faults thatare masked while minimizing (or holding to zero) thenumber of other masked faults.
on the generation of small dictionaries for fault location. fault location based on a fault dictionary is considered. to justify the use of a precomputed dictionary in terms of computation time, the computational effort invested in computing a dictionary is first analyzed. the number of circuit diagnoses that need to be performed dynamically, without the use of precomputed knowledge, before the overall effort exceeds the effort of computing a dictionary, is studied. experimental results on iscas-85 circuits show that for relatively small numbers of diagnoses, a precomputed dictionary is more efficient. a method to derive small dictionaries without losing resolution of modeled faults is then proposed. methods to compact the resulting dictionary further, using compaction techniques generally applied to fault detection, are then described. experimental results to demonstrate the effectiveness of the methods are presented. internal observation points to increase the resolution of the test set are also considered
an efficient non-enumerative method to estimate path delay fault coverage. a method for estimating the coverage of path delay faults of a given test set, without enumerating paths, is proposed. the method is polynomial in the number of lines in the circuit, and thus allows circuits with large numbers of paths to be considered under the path delay fault model. several levels of approximation, with increasing accuracy and increasing polynomial complexity, are proposed. experimental results to show the effectiveness and accuracy of the estimate in evaluating the path delay fault coverage are presented. combining this nonenumerative estimation method with a test generation method for path delay faults would yield a cost effective method to consider path delay faults in large circuits, which are beyond the capabilities of existing test generation and fault simulation procedures that are based on enumeration of paths
on testing delay faults in macro-based combinational circuits. we consider the problem of testing for delay faults in macro-based circuits. macro-based circuits are obtained as a result of technology mapping. gate-level fault models cannot be used for such circuits, since the implementation of a macro may not have an accurate gate-level counterpart, or the macro implementation may not be known. two delay fault models are proposed for macro-based circuits. the first model is analogous to the gate-level gross delay fault model. the second model is analogous to the gate-level path delay fault model. we provide fault simulation procedures, and present experimental results.
on error correction in macro-based circuits. we consider the problem of correcting errors in a macro-based circuit. our formulation of the problem allows the correction of errors that arise both in the context of design error correction, before the circuit is realized, and in the context where a physical circuit needs to be corrected. two error classes are defined, namely, component errors and line errors. both single and multiple errors are considered. accurate correction procedures are given for single errors. heuristics are given for correcting multiple errors. experimental results are given to demonstrate the correction procedures presented.
functional test generation for delay faults in combinational circuits. we propose a functional fault model for delay faults in combinational circuits and describe a functional test generation procedure based on this model. the proposed method is most suitable when a gate-level description of the circuit-under-test, necessary for employing existing gate-level delay fault test generators, is not available or does not accurately describe the circuit. it is also suitable for generating tests in early design stages of a circuit, before a gate-level implementation is selected. in addition, it can potentially be employed to supplement conventional test generators for gate-level circuits to reduce the cost of handling large numbers of paths. a parameter called &dgr; is used to control the number of funtional faults targeted and thus the number of tests generated. if &dgr; is unlimited, the functional test set detects every robustly testable path delay fault in any gate-level implementation of the given ciruit. an appropriate subset of tests can be selected once the implentation is known. the test sets generated for various values of &dgr; are fault simulated on gate-level realizations to demonstrate their effectiveness. the experiments indicate that functional test sets may be able to identify functions whose realizations have low path delay fault coverage.
built-in test generation for synchronous sequential circuits. we consider the problem of built-in test generation for synchronous sequential circuits. the proposed scheme leaves the circuit flip-flops unmodified, and thus allows at-speed test application. we introduce a uniform, parametrized structure for test pattern generation. by matching the parameters of the test pattern generator to the circuit-under-test, high fault coverage is achieved. in many cases, the fault coverage is equal to the fault coverage that can be achieved by deterministic test sequences. we also investigate a method to minimize the size of the test pattern generator, and study its effectiveness alone and in conjunction with the insertion of test-points.
an approach for improving the levels of compaction achieved by vector omission. we describe a method referred to as sequence counting to improve on the levels of compaction achievable by vector omission based static compaction procedures. such procedures are used to reduce the lengths of test sequences for synchronous sequential circuits without reducing the fault coverage. the unique feature of the proposed approach is that test vectors omitted from the test sequence can be reintroduced at a later time. reintroducing of vectors helps reduce the compacted test sequence length beyond the length that can be achieved if vectors are omitted permanently. experimental results are presented to demonstrate the levels of compaction achieved by the sequence counting approach.
design-for-debugging of application specific designs. abstract: we address the problem of considering debugging requirements during high level synthesis by providing low-cost hardware support and scheduling and assignment methods for ensuring controllability and observability of the user specified variables. two key conceptually new design ideas that enable efficient debugging are developed: pipelining of debugging variables for improving their scheduling and assignment freedom and use of i/o buffers for improving resource utilization of i/o pins. the provably optimal bounds for the maximum cardinality of the set of controllable and observable variables for a given design specification are derived. a polynomial time complexity synthesis algorithm for achieving the bounds is developed. the minimization of hardware overhead gives rise to a combinatorial optimization problem which is solved using a non-greedy heuristic algorithm. the effectiveness of the proposed design-for-debugging approach is demonstrated on several examples.
algorithm selection: a quantitative computation-intensive optimization approach. given a set of specifications for a targeted application, algorithm selection refers to choosing the most suitable algorithm for a given goal, among several functionally equivalent algorithms. we demonstrate an extraordinary potential of algorithm selection for achieving high throughput, low cost, and low power implementations.we introduce an efficient technique for low-bound evaluation of the throughput and cost during algorithm selection and propose a relaxation-based heuristic for throughput optimization. we also present an algorithm for cost optimization using algorithm selection. the effectiveness of methodology and algorithms is illustrated using examples.
cost optimization in asic implementation of periodic hard-real time systems using behavioral synthesis techniques. abstract: modern applications are often defined as sets of several computational tasks. this paper presents a synthesis algorithm for asic implementations which realize multiple computational tasks under hard real-time deadlines. the algorithm analyzes constraints imposed by task sharing as well as the traditional datapath synthesis criteria. in particular we demonstrated an efficient technique to combine rate-monotonic scheduling, a widely used hard real-time systems scheduling discipline, with estimations and scheduling and allocation algorithms. matching the number of bits in tasks assigned to the same processor was the most important factor in obtaining good designs. we have demonstrated the effectiveness of our algorithms on several multiple-task examples.
verilat: verification using logic augmentation and transformations. this paper presents a new framework for formal logic verification. what is depicted here is fundamentally different from previous approaches. in earlier approaches, the circuit is either not changed during the verification process, as in obdd or implication-based methods, or the circuit is progressively reduced during verification. whereas in our approach, we actually enlarge the circuits by adding gates during the verification process. specifically introduced here is a new technique that transforms the reference circuit as well as the circuit to be verified, so that the similarity between the two is progressively enhanced. this requires addition of gates to the reference circuit and/or the circuit to be verified. in the process, we reduce the dissimilarity between the two circuits, which makes it easier to verify the circuits.
a parametric test method for analog components in integrated mixed-signal circuits. in this paper, we present a novel approach to use test stimuli generated by digital components of a mixed-signal circuit for testing its analog components. a wavelet transform is applied to the response signal of the device under test (dut). we will show, that in comparison to fourier transform or no transform at all, particular properties of this transformation are advantageous for mixed-signal test and especially built-in self test.we introduce a new method for test measurement selection based on a non-deterministic parametric fault model for analog circuits. this approach allows for noise and measurement error in testing. we show, how test quality can be optimized in the presented fault model. our test methodology is demonstrated on an analog cmos bandpass filter.
logic optimization by output phase assignment in dynamic logic synthesis. domino logic is one of the most popular dynamic circuit configurations for implementing high-performance logic designs. since domino logic is inherently noninverting, it presents a fundamental constraint of implementing logic functions without any intermediate inversions. removal of intermediate inverters requires logic duplication for generating both the negative and positive signal phases, which results in significant area overhead. this area overhead can be substantially reduced by selecting an optimal output phase assignment, which results in a minimum logic duplication penalty for obtaining inverter-free logic. in this paper, we present this previously unaddressed problem of output phase assignment for minimum area duplication in dynamic logic synthesis. we give both optimal and heuristic algorithms for minimizing logic duplication.
custom-optimized multiplierless implementations of dsp algorithms. linear dsp kernels such as transforms and filters are comprised exclusively of additions and multiplications by constants. these multiplications may be realized as networks of additions and wired shifts in hardware. the cost of such a "multiplierless" implementation is determined by the number of additions, which in turn depends on the value and precision of these constants. for a given transform or filter, the set of constants and their required precision is affected by algorithmic and implementation choices and hence provides a degree of freedom for optimization. in this work we present an automated method to generate, for a given linear transform, a minimum addition multiplierless implementation that satisfies a given quality constraint. the method combines automatic algorithm selection to improve numerical robustness and automatic search methods to minimize constant precisions in a chosen algorithm. we present experiments that show the trade-offs between cost and quality, including custom optimizations of the transforms used in jpeg image and mp3 audio decoders.
a chip-level electrostatic discharge simulation strategy. this work presents a chip-level charged device model (cdm) electrostatic discharge (esd) simulation method. the chip-level simulation is formulated as a dc analysis problem. a network reduction algorithm based on random walks is proposed for rapid analysis, and to support incremental design. a benchmark with a 2.3m-node v/sub dd/ net and 1000 i/o pads is checked in 13 minutes, and 10 re-simulations for incremental changes take a total of 9 minutes.
a hybrid linear equation solver and its application in quadratic placement. this paper presents a new hybrid linear equation solver for quadratic placement. the new solver is a combination of stochastic solver and iterative solver: it is proven in this paper that an approximate ldl factorization can be obtained from random walks, and used as a preconditioner for conjugate gradient solver. testing on real-life placement benchmarks shows a speedup of up to 7.1 times over traditional incomplete cholesky preconditioned conjugate gradient (iccg).
challenges and opportunities in broadband and wireless communication designs. communication designs form the fastest growing segment of the semiconductor market. both network processors and wireless chipsets have been attracting a great deal of research attention, financial resources and design efforts. however, further progress is limited by lack of adequate system methodologies and tools. our goal in this tutorial is to provide impetus for development of communication design techniques and tools.the first part addresses network processors (np) that we study from three viewpoints: application, architecture, and system software and compilation tools. in addition to summary of main issues and representative case studies, we identify main system design issues. the second part of the tutorial focuses on wireless design. the main emphasis is on platform-based design methodology that leverages on functional profiling, architecture exploration, and orthogonalization of concerns to facilitate low-power wireless communication systems. the highlight of the paper, an in-depth study of the state-of-the-art wireless design, picoradio, is used as explanatory design example.
specifying and verifying imprecise sequential datapaths by arithmetic transforms. we address verification of imprecise datapath circuits with sequential elements. using arithmetic transform (at) and its extensions, we verify the sequential datapath circuits with finite precision. an efficient formulation of the precision verification is presented as a polynomial maximization search over boolean inputs. using a branch-and-bound search for the precision error and the block-level composition of ats, we verify the approximated, rounded and truncated pipelined datapaths.