25366029
Formal hardware verification methods: A survey
Growing advances in VLSI technology have led to an increased level of complexity in current hardware systems. Late detection of design errors typically results in higher costs due to the associated time delay as well as loss of production. Thus it is important that hardware designs be free of errors. Formal verification has become an increasingly important technique towards establishing the correctness of hardware designs. In this article we survey the research that has been done in this area, with an emphasis on more recent trends. We present a classification framework for the various methods, based on the forms of the specification, the implementation, and the proff method. This framework enables us to better highlight the relationships and interactions between seemingly different approaches.
685138
Tradeoffs in canonical sequential function representations
State space exploration is of prime importance in the study of finite state sequential systems, with several efforts aimed at compact representation of the state space in order to tackle the state explosion problem. In the work presented on formal verification of inductively-defined hardware, we have identified a useful class of Boolean functions called linearly inductive functions (LIFs). We explore the relationship between our LIF representation and the classic DFA (deterministic finite state automaton) representation of a sequential function, and examine the associated tradeoffs. We show that our LIF representation corresponds to a minimal reverse DFA, i.e. a minimal DFA which accepts the language consisting of the reverse input strings, where our implicit method for obtaining an LIF representation does not require explicit construction of a forward DFA. Its practical usefulness arises from our demonstration that reverse DFAs for several datapath circuits are exponentially more compact than the classic forward DFAs. Furthermore, in comparison to the traditional representation of DFAs as state transition diagrams, our LIF representations allow for state-sharing while maintaining decomposition, resulting in memory savings in practice.<<ETX>>
6311626
Combining strengths of circuit-based and CNF-based algorithms for a high-performance SAT solver
We propose Satisfiability Checking (SAT) techniques that lead to a consistent performance improvement of up to 3x over state-of-the-art SAT solvers like Chaff on important problem domains in VLSI CAD. We observe that in circuit oriented applications like ATPG and verification, different software engineering techniques are required for the portions of the formula corresponding to learnt clauses compared to the original formula. We demonstrate that by employing the same innovations as in advanced CNF-based SAT solvers, but in a hybrid approach where these two portions of the formula are represented differently and processed separately, it is possible to obtain the consistently highest performing SAT solver for circuit oriented problem domains. We also present controlled experiments to highlight where these gains come from. Once it is established that the hybrid approach is faster, it becomes possible to apply low overhead circuit-based heuristics that would be unavailable in the CNF domain for greater speedup.
17323833
Verification of scheduling in the presence of loops using uninterpreted symbolic simulation
We propose a novel procedure based on uninterpreted symbolic simulation for checking the scheduling step in high-level synthesis. The primary task in scheduling is the assignment of time steps or, equivalently, states to operations. Various transformations like operation reordering and loop unrolling may be performed in the process to meet the optimization criteria. The contribution of our proposal lied in its ability to efficiently handle loops and a wide range of loop transformations performed during scheduling. Our algorithm is based on loop invariant extraction using a combination of uninterpreted symbolic simulation and induction techniques. In spite of its wide scope, our procedure is relatively complete and practical. This work is a part of our effort to provide a suite of techniques for verifying the various steps involved in the high-level synthesis process. It is being implemented in an in-house verification system for checking equivalence of designs generated from high-level specifications through successive refinements. We present case studies to demonstrate the applicability of our approach. These case studies consist of examples where equivalence cannot be established using conventional FSM-based methods. By providing a viable automated equivalence checking technique for such examples, we improve on the state of the art.
34084077
A Spot Pricing Framework For Pricing Intra-Domain Assured Bandwidth Services
The Internet today offers primarily a best-effort service. Research and technology development efforts are currently underway to allow the provisioning of better than best-effort quality of service assurances. In this article, we develop a spot pricing framework for expected bandwidth guaranteed Internet service contracts on a single domain. A nonlinear pricing model that maximizes the total surplus with cost constraints forms the basis for the framework. The spot price process is obtained for different demand profiles of the customer-base and demand arrival characteristics. Simulation modeling and analysis is employed to implement the pricing framework and analyze the price process under different market conditions and changes due to network failures. The framework when implemented at access or exchange points of different service provider domains will provide assured bandwidth for inter-domain traffic.
2840997
A survey of recent advances in SAT-based formal verification
Dramatic improvements in SAT solver technology over the last decade and the growing need for more efficient and scalable verification solutions have fueled research in verification methods based on SAT solvers. This paper presents a survey of the latest developments in SAT-based formal verification, including incomplete methods such as bounded model checking and complete methods for model checking. We focus on how the surveyed techniques formulate the verification problem as a SAT problem and how they exploit crucial aspects of a SAT solver, such as application-specific heuristics and conflict-driven learning. Finally, we summarize the noteworthy achievements in this area so far and note the major challenges in making this technology more pervasive in industrial design verification flows.
9743987
Complex Visual Activity Recognition Using a Temporally Ordered Database
We propose using a temporally ordered database for complex visual activity recognition. We use a temporal precedence relation together with the assumption of fixed bounded temporal uncertainty of occurrence time of an atomic activity and comparatively large temporal extent of the complex activity. Under these conditions we identify the temporal structure of complex activities as a semiorder and design a database that has semiorder as its data model. A query algebra is then defined for this data model.