waashk/dblp huggingface dataset:
synthesis of hazard-free multi-level logic under multiple-input changes from binary decision diagrams. we describe a new method for directly synthesizing a hazard-free multilevel logic implementation from a given logic specification. the method is based on free/ordered binary decision diagrams (bdd's), and is naturally applicable to multiple-output logic functions. given an incompletely-specified (multiple-output) boolean function, the method produces a multilevel logic network that is hazard-free for a specified set of multiple-input changes. we assume an arbitrary (unbounded) gate and wire delay model under a pure delay (pd) assumption, we permit multiple-input changes, and we consider both static and dynamic hazards. this problem is generally regarded as a difficult problem and it has important applications in the field of asynchronous design. the method has been automated and applied to a number of examples. the results we have obtained are very promising.
dynamical identification of critical paths for iterative gate sizing. since only sensitizable paths contribute to the delay of a circuit, false paths must be excluded in optimizing the delay of the circuit. just identifying false paths in the first place is not sufficient since during iterative optimization process, false paths may become sensitizable, and sensitizable paths false. in this paper, we examine cases for false path becoming sensitizable and sensitizable becoming false. based on these conditions, we adopt a so-called loose sensitization criterion which is used to develop an algorithm for dynamically identification of sensitizable paths. by combining gate sizing and dynamically identification of sensitizable paths, an efficient performance optimization tool is developed. results on a set of circuits from iscas benchmark set demonstrate that our tool is indeed very effective in reducing circuit delay with less number of gate sized as compared with other methods.
cost-free scan: a low-overhead scan path design methodology. conventional scan design imposes considerable area and delay overhead by using larger scan flip-flops and additional scan wires without utilizing the functionality of the combinational logic. we propose a novel low-overhead scan design methodology, called cost-free scan, which exploits the controllability of primary inputs to establish scan paths through the combinational logic. the methodology aims at reducing scan overhead by (1) analyzing the circuit to determine all the cost-free scan flip-flops, and (2) selecting the best primary input vector to establish the maximum number of cost-free scan flip-flops on the scan chain. significant reduction in the scan overhead is achieved on iscas89 benchmarks, where in full scan environment, as many as 89% of the total flip-flops are found cost-free scannable, while in partial scan environment, reduction can be as high as 97% in scan flip-flops needed to break sequential loops.
silent: serialized low energy transmission coding for on-chip interconnection networks. on-chip source-synchronous serial communication has many advantages over multi-bit parallel communication in the aspects of skew, crosstalk area cost, wiring difficulty, and clock synchronization. however, the serial wire tends to dissipate more energy than parallel bus due to the bit multiplexing. we propose a coding method to reduce the transmission energy of the serial communication by minimizing the number of transitions on the serial wire. we demonstrate the significant energy saving in a multimedia application, 3d graphics. we also apply the coding technique to a cmos soc implementation which integrates various processing units with packet switched on-chip networks.
a cell-based power estimation in cmos combinational circuits. in this paper we present a power dissipation model considering the charging/discharging of capacitance at the gate output node as well as internal nodes, and capacitance feedthrough effect. based on the model, a cell-based power estimation (cbpe) method is developed to estimate the power dissipation in cmos combinational circuits. in our technique, we first construct a modified state transition graph called stgpe to model the power consumption behavior of a logic gate. then, according to the input signal probabilities and transition densities of the logic gate, we perform an efficient method to estimate the expected activity number of each edge in the stgpe. finally, the energy consumption of a logic gate is calculated by summing the energy consumptions of each edge in stgpe. for a set of benchmark circuits, experimental results show that the power dissipation estimated by cbpe is on average within 10-percent errors as compared to the exact spice simulation while the cpu time is more than two order-of-magnitudes faster.
aesthetic routing for transistor schematics. a heuristic routing approach for generating transistor schematic diagrams is presented. the method consists of two steps: global routing and channel routing. the global routing step partitions and routes the interconnections, into three levels of abstraction with domain knowledge. it forms desirable intra-block routing styles and local connection patterns, and achieves a reduction of net bends and lengths. channel routing minimizes net crossovers by applying decycling and ordering techniques achieving nonoverlapping routing with a small number of net crossovers
universal logic gate for fpga design. in this paper the problem of selecting an appropriate programmable cell structure for fpga architecture design is addressed. the cells studied here can be configured to the desired functionality by applying input permutation, negation, bridging or constant assignment, or output negation. a general methodology to determine logic description of such cells, which are capable of being configured to a given set of functions is described.experimental results suggest that the new cell behaves as well as the actel 2 cell in terms of logic power but requires substantially less area and wiring overhead.
on the signal bounding problem in timing analysis. in this paper, we study the propagation of slew dependent bounding signals and the corresponding slew problem in static timing analysis. the selection of slew from the latest arriving signal, a commonly used strategy, may violate the rule of monotonic delay. several methods for generating bounding signals to overcome this difficulty are described. the accuracy and monotonicity of each method is analyzed. these methods can be easily implemented in a static timer to improve the accuracy.
throughput-driven ic communication fabric synthesis. as the scale of system integration continues to grow, the on-chip communication becomes the ultimate bottleneck of system performance and the primary determinant of system architecture. in this paper we propose a throughput-driven synthesis methodology for on-chip communication fabrics based on optimized bus models. compared with traditional delay-driven, wire-by-wire planning methods, the throughput-driven methodology provides a feasible and accurate system-level solution to address delay and congestion problems simultaneously during earlyphase design planning. unlike the conventional methods which are based on rather inaccurate rc models and simplistic delay metrics, in our methodology the communication fabrics are characterized in terms of realistic partial element equivalent circuits (peec) extracted from the multi-layer interconnects and transistor level transient analysis via spice-like tools. the characterized models facilitate a flexible interconnect fabric optimization engine that can be embedded into a system planner for throughput-driven synthesis. furthermore, engineering trade-offs considering repeater area and interconnect power consumption are further considered as part of this methodology.
techniques for improving the efficiency of sequential circuit test generation. new techniques are presented in this paper to improve the efficiency of a test generation procedure for synchronous sequential circuits. these techniques aid the test generation procedure by reducing the search space, carrying out non-chronological backtracking, and reusing the test generation effort. they have been integrated into an existing sequential test generation system mix to constitute a new system, named mix-plus. the experimental results for the iscas-89 and addendum-93 benchmark circuits demonstrate the effectiveness of these techniques in improving the fault coverage and test generation efficiency.
tearing based automatic abstraction for ctl model checking. in this paper we present the tearing paradigm as a way to automatically abstract behavior to obtain upper and lower bound approximations of a reactive system. we present algorithms that exploit the bounds to perform conservative ectl and actl model checking. we also give an algorithm for false negative (or false positive) resolution for verification based on a theory of a lattice of approximations. we show that there exists a bipartition of the lattice set based on positive versus negative verification results. our resolution methods are based on determining a pseudo-optimal shortest path from a given, possibly coarse but tractable approximation, to a nearest point on the contour separating one set of the bipartition from the other.
a power modeling and characterization method for the cmos standard cell library. in this paper, we propose power consumption models for complex gates and transmission gates, which are extended from the model of basic gates proposed in [1]. we also describe an accurate power characterization method for cmos standard cell libraries which accounts for the effects of input slew rate, output loading, and logic state dependencies. the characterization methodology separates the power consumption of a cell into three components, e.g., capacitive feedthrough power, short-circuit power, and dynamic power. for each component, power equation is derived from spice simulation results where the netlist is extracted from cell's layout. experimental results on a set of iscas'85 benchmark circuits show that the power estimation based on our power modeling and characterization provides within 7% error of spice simulation on average while the cpu time consumed is more than two orders of magnitude less.
a power modeling and characterization method for macrocells using structure information. to characterize a macrocell, a general method is to store the power consumption of all possible transition events at primary inputs in the lookup tables. though this approach is very accurate, the lookup tables could be huge for the macrocells with many inputs. in this paper, we present a new power modeling method which takes advantage of the structure information of macrocells and selects minimum number of primary inputs or internal nodes in a macrocell as state variables to build a state transition graph (stg). those state variables can completely model the transitions of all internal nodes and the primary outputs. by carefully deleting some state variables, we further introduce an incomplete power modeling technique which can simplify the stg without losing much accuracy. in addition, we exploit the property of the compatible patterns of a macrocell to further reduce the number of edges in the corresponding stg. experimental results show that our modeling techniques can provide spice-like accuracy and can reduce the size of the lookup table significantly comparing to the general approach.
the reproducing placement problem with applications. we study a new placement problem: the reproducing placement problem (rpp). in each phase a module (or gate) is decomposed into two (or more) simpler modules. the goal is to find a &ldquo;good&rdquo; placement in each phase. the problem, being iterative in nature, requires an iterative algorithm. the problem finds applications in several gate-level placement problems, e.g., in layout-driven logic synthesis.we introduce the notion of minimum floating steiner trees (mfst). we employ an mfst algorithm as a central step in solving the rpp. a hanan-like theorem is established for the mfst problem and two approximation algorithms are proposed. experiments on commonly employed benchmarks verify the effectiveness of the proposed technique.
an algorithm to reduce test application time in full scan designs. an algorithm for generating a test with fewer test clocks for full scan designs by using combinational and sequential test generation algorithms adaptively is presented. heuristics combining tests measures and scan strategies are introduced. the algorithm, `test application time reduction for full scan designs' (tarf), is implemented and tested on a set of iscas sequential benchmark circuits. the results show that tarf achieves the same test coverage as combinational test generators but with fewer test clocks
comparing models of computation. we give a denotational framework (a meta model) within which certain properties of models of computation can be understood and compared. it describes concurrent processes as sets of possible behaviors. compositions of processes are given as intersections of their behaviors. the interaction between processes is through signals, which are collections of events. each event is a value-tag pair, where the tags can come from a partially ordered or totally ordered set. timed models are where the set of tags is totally ordered. synchronous events share the same tag, and synchronous signals contain events with the same set of tags. synchronous systems contain synchronous signals. strict causality (in timed systems) and continuity (in untimed systems) ensure determinacy under certain technical conditions. the framework is used to compare certain essential features of various models of computation, including kahn process networks, dataflow, sequential processes, concurrent sequential processes with rendezvous, petri nets, and discrete-event systems.
synthesis of concurrent system interface modules with automatic protocol conversion generation. we describe a new high-level compiler called integral for designing system interface modules. the input is a high-level concurrent algorithmic specification that can model complex concurrent control flow, logical and arithmetic computations, abstract communication, and low-level behavior. for abstract communication between two communicating modules that obey different i/o protocols, the necessary protocol conversion behaviors are automatically synthesized using a petri net theoretic approach. we present a synthesis trajectory that can synthesize the necessary hardware resources, control circuitry, and protocol conversion behaviors for implementing system interface modules.
process-variation-tolerant clock skew minimization. in this paper, we propose a novel hierarchical multiple-merge zero skew clock routing algorithm. the routing results produced by our approach will have zero skew in the nominal case and minimal skew increase in the presence of worst process variations. in order to construct such a clock routing, we formulate the linear placement with maximum spread problem and provide an o(nmin{n,p}lognlogp) algorithm for optimally solving this problem, where n is the number of cells to be placed and p is the maximum spread. experimental results show that our algorithm can indeed reduce the skew in various manufacturing variations effectively.
clustering for processing rate optimization. clustering (or partitioning) is a crucial step between logic synthesis and physical design in the layout of a large scale design. a design verified at the logic synthesis level may have timing closure problems at post-layout stages due to the emergence of multiple-clock-period interconnects. consequently, a trade-off between clock frequency and throughput may be needed to meet the design requirements. in this paper, we find that the processing rate, defined as the product of frequency and throughput, of a sequential system is upper bounded by the reciprocal of its maximum cycle ratio, which is only dependent on the clustering. we formulate the problem of processing rate optimization as seeking an optimal clustering with the minimal maximum-cycle-ratio in a general graph, and present an iterative algorithm to solve it. since our algorithm avoids binary search and is essentially incremental, it has the potential of being combined with other optimization techniques. experimental results validate the efficiency of our algorithm.
a timing analysis algorithm for circuits with level-sensitive latches. for a logic design with level-sensitive latches, we need to validate timing signal paths which may flush through several latches. we developed efficient algorithms based on the modified shortest and longest path method. the computational complexity of our algorithm is generally better than that of known algorithms in the literature. the implementation (cyclopss) has been applied to an industrial chip to verify the clock schedules.
retiming for wire pipelining in system-on-chip. at the integration scale of system-on-chips (socs), the conflicts between communication and computation will become prominent even on a chip. a big fraction of system time willshift from computation to communication. in synchronoussystems, a large amount of communication time is spent onmultiple-clock period wires. in this paper, we explore retimingto pipeline long interconnect wires in soc designs. behaviorally,it means that both computation and communicationare rescheduled for parallelism. the retiming is applied to anetlist of macro-blocks, where the internal structures may notbe changed and ip- ops may not be able to be inserted onsome wire segments. this problem is different from that on agate level netlist and is formulated as a wire retiming problem.theoretical treatment and a polynomial time algorithmare presented in the paper. experimental results showed thebenefits and effectiveness of our approach.
an effective methodology for functional pipelining. the problem of scheduling a loop in a pipelined fashion such that the iteration time (turnaround time) is minimized, given a loop behavior, a target initiation interval, and resource constraints, is considered. the iteration time is an important quality measure of a data path design because of its direct correlation with both the storage and the control costs. the scheduler starts with performing as-soon-as-possible-pipelined (asapp) scheduling without regard to the resource constraint. it then resolves the resource constraint violations, if there are any, by repeatedly rescheduling some operations
optimal wire retiming without binary search. the problem of retiming over a netlist of macro-blocks to achieve the minimal clock period, where the block internal structures may not be changed and flip-flops may not be inserted on some wire segments, is called the optimal wire retiming problem. to the best of our knowledge, there is no polynomial-time approach to solve it and the existence of such an approach is still an open question. we present a brand new algorithm that solves the optimal wire retiming problem with polynomial-time worst case complexity. since the new algorithm avoids binary search and is essentially incremental, it has the potential of being combined with other optimization techniques. experimental results show that the new algorithm is very efficient in practice.
behavioral synthesis for easy testability in data path scheduling. a data path scheduling algorithm to improve testability without assuming any particular test strategy is presented. a scheduling heuristic for easy testability, based on previous work on data path allocation for testability, is introduced. a mobility path scheduling algorithm to implement this heuristic while also minimizing area is developed. experimental results on benchmark and example circuits show high fault coverage, short test generation time, and little or no area overhead
trade-off between latch and flop for min-period sequential circuit designs with crosstalk. latches are extensively used in high-performance sequential circuit designs to achieve high frequencies because of their good performance and time borrowing feature. however, the amount of timing uncertainty due to crosstalk accumulated through latches could be larger than the benefit gained by time borrowing. in this paper, we show that the trade-off between a latch and a flop can be leveraged in a sequential circuit design with crosstalk, so that the clock period is minimized by selecting a configuration of mixed latches and flops. a circular time representation is proposed to make coupling detection easier and more efficient. experiments on our heuristic algorithm for finding an optimal configuration of mixed latches and flops showed promising results.
a path-based methodology for post-silicon timing validation. this work presents a novel path-based methodology for post-silicon timing validation. in timing validation, the objective is to decide if the timing behavior observed from the silicon is consistent with that predicted by the timing model. at the core of our path-based methodology, we propose a framework to obtain the post-silicon path ranking from observing silicon timing behavior. then, the consistency is determined by comparing the post-silicon path ranking and the pre-silicon path ranking calculated based on the timing model. our post-silicon ranking methodology consists of two approaches: ranking optimization and path filtering. we discuss the applications of both approaches and their impacts on the path ranking results. for experiments, we utilize a statistical timing simulator that was developed in the past to derive chip samples and we demonstrate the feasibility of our methodology using benchmark circuits.
simulation of digital circuits in the presence of uncertainty. current extended value set dynamic timing analyzers are not sophisticated enough to detect the subtle timing relationships upon which timing-critical systems depend, and exhaustive simulation achieves very accurate results but at tremendous computational cost. mtv is a simulator that strikes a balance between accuracy and efficiency.mtv is more accurate than other extended value set simulators because it respects the ordering of events. it is more efficient than exhaustive simulators because it efficiently simulates overlapping events and requires only a single waveform to represent a signal. features of mtv include: elimination of common ambiguity, symbolic delays, correlated delays, and sophisticated algorithms to detect ordered events. this paper concludes with simulation results from the iscas85 benchmark suite.
design of robust test criteria in analog testing. test design of analog circuits based on statistical methods for decision making is a topic of growing interest. the major problem of such statistical approaches with respect to industrial applicability concerns the confidence with which the determined test criteria can be applied in production testing. this mainly refers to the consideration of measurement noise, to the selected measurements, as well as to the required training and validation samples. these crucial topics are addressed in this paper. on exploiting experience from the statistical design of analog circuits and from pattern recognition methods, efficient solutions to these problems are provided. a very robust test design is achieved by systematically considering measurement noise, by selecting most significant measurements, and by using most meaningful samples. moreover, parametric as well as catastrophic faults are covered on application of digital testing methods.