9846641
VIS: A System for Verification and Synthesis
ion Manual abstraction can be performed by giving a file containing the names of variables to abstract. For each variable appearing in the file, a new primary input node is created to drive all the nodes that were previously driven by the variable. Abstracting a net effectively allows it to take any value in its range, at every clock cycle. Fair CTL model checking and language emptiness check VIS performs fair CTL model checking under Buchi fairness constraints. In addition, VIS can perform language emptiness checking by model checking the formula EG true. The language of a design is given by sequences over the set of reachable states that do not violate the fairness constraint. The language emptiness check can be used to perform language containment by expressing the set of bad behaviors as another component of the system. If model checking or language emptiness fail, VIS reports the failure with a counterexample, (i.e., behavior seen in the system that does not satisfy the property for model checking, or valid behavior seen in the system for language emptiness). This is called the “debug” trace. Debug traces list a set of states that are on a path to a fair cycle and fail the CTL formula. Equivalence checking VIS provides the capability to check the combinational equivalence of two designs. An important usage of combinational equivalence is to provide a sanity check when re-synthesizing portions of a network. VIS also provides the capability to test the sequential equivalence of two designs. Sequential verification is done by building the product finite state machine, and checking whether a state where the values of two corresponding outputs differ, can be reached from the set of initial states of the product machine. If this happens, a debug trace is provided. Both combinational and sequential verification are implemented using BDD-based routines. Simulation VIS also provides traditionaldesign verification in the form of a cycle-based simulator that uses BDD techniques. Since VIS performs both formal verification and simulation using the same data structures, consistency between them is ensured. VIS can generate random input patterns or accept user-specified input patterns. Any subtree of the specified hierarchy may be simulated.
34510774
Sequential circuit design using synthesis and optimization
A description is given of SIS, an interactive tool for synthesis and optimization of sequential circuits. Given a state transition table or a logic-level description of a sequential circuit, SIS produces an optimized net-list in the target technology while preserving the sequential input-output behavior. Many different programs and algorithms have been integrated into SIS, allowing the user to choose among a variety of techniques at each stage of the process. It is built on top of MISII and includes all (combinational) optimization techniques therein as well as many enhancements. SIS serves as both a framework within which various algorithms can be tested and compared and as a tool for automatic synthesis and optimization of sequential circuits.<<ETX>>
17361322
Compatible observability don't cares revisited
CODCs stands for compatible observability don't cares. We first examine the definition of compatibility and when a set of CODCs is compatible. We then discuss Savoj's CODC computation for propagating CODCs from a node's output to its fanins, and show by example, that the results can depend on the current implementation of the node. Then we generalize the computation so that the result is independent of the implementation at the node. The CODCs propagated by this computation are proved to be maximal in some sense. Local don't cares (LDCs) are CODCs of a node, pre-imaged to the primary inputs and then imaged and projected to the local fanins of the node. LDCs combine CODCs with SDCs (satisfiability don't cares), but only the CODC part is propagated to the fanin network. Another form of local don't cares, propagates both the CODC and SDC parts to the fanin network. Both are shown to be compatible in some sense, but conservative. We give a method for updating both kinds of local don't cares incrementally when other nodes in the network are changed.
6086711
On the verification of sequential equivalence
The state-explosion problem limits formal verification on large sequential circuits partly because the sizes of binary decision diagrams (BDDs) sizes heavily depend on the number of variables dealt with. In the worst case, a BDD size grows exponentially with the number of variables. Thus, reducing this number can possibly increase the verification capacity. In particular, this paper shows how sequential equivalence checking can be done in the sum state space. Given two finite state machines M/sub 1/ and M/sub 2/ with numbers of state variables m/sub 1/ and m/sub 2/, respectively, conventional formal methods verify equivalence by traversing the state space of the product machine with m/sub 1/+m/sub 2/ registers. In contrast, this paper introduces a different possibility, based on partitioning the state space defined by a multiplexed machine, which can have merely max{m/sub 1/,m/sub 2/}+1 registers. This substantial reduction in state variables potentially enables the verification of larger instances. Experimental results show the approach can verify benchmarks with up to 312 registers, including all of the control outputs of microprocessor 8085.
1826252
Generalized cofactoring for logic function evaluation
Logic evaluation of a Boolean function or relation is traditionally done by simulating its gate-level implementation, or creating a branching program using its Binary Decision Diagram (BDD) representation, or using a set of look-up tables. We propose a new approach called generalized cofactoring diagrams, which are a generalization of the above methods. Algorithms are given for finding the optimal cofactoring structure for free-ordered BDD's and generalized cube cofactoring under an average path length (APL) cost criterion. Experiments on multi-valued functions show superior results to previously known methods by an average of 30%. The framework has direct applications in logic simulation, software synthesis for embedded control applications, and functional decomposition in logic synthesis.
7226318
River PLAs: a regular circuit structure
A regular circuit structure called a River PLA and its re-configurable version, Glacier PLA, are presented. River PLAs provide greater regularity than circuits implemented with standard-cells. Conventional optimization stages such as technology mapping, placement and routing are eliminated. These two features make the River PLA a highly predictable structure. Glacier PLAs can be an alternative to FPGAs, but with a simpler and more efficient design methodology.
5723912
Fishbone: a block-level placement and routing scheme
A block-level placement and routing scheme called Fishbone is presented. The routing uses a two-layer spine topology. The pin locations are configurable and restricted to certain routing grids in order to ensure full routability and precise predictability. With this scheme, exact net topologies are determined by pin positions only; hence during block placement, net parameters such as wire length (and delay) can be derived directly. The construction of Fishbone nets is much faster than for Steiner trees; this enables the integration of block placement and routing; there is no separate routing stage.
7302649
Functional Dependency for Verification Reduction
The existence of functional dependency among the state variables of a state transition system was identified as a common cause of inefficient BDD representation in formal verification. Eliminating such dependency from the system compacts the state space and may significantly reduce the verification cost. Despite the importance, how to detect functional dependency without or before knowing the reachable state set remains a challenge. This paper tackles this problem by unifying two closely related, but scattered, studies — detecting signal correspondence and exploiting functional dependency. The prior work on either subject turns out to be a special case of our formulation. Unlike previous approaches, we detect dependency directly from transition functions rather than from reached state sets. Thus, reachability analysis is not a necessity for exploiting dependency. In addition, our procedure can be integrated into reachability analysis as an on-the-fly reduction. Preliminary experiments demonstrate promising results of extracting functional dependency without reachability analysis. Dependencies that were underivable before, due to the limitation of reachability analysis on large transition systems, can now be computed efficiently. For the application to verification, reachability analysis is shown to have substantial reduction in both memory and time consumptions.