Dpll-based sat solver using with application-aware branching

a sat solver and application-aware branching technology, applied in the field of model checking, can solve problems such as inefficiency of techniques, increase of formula size, and search space, and achieve the effect of improving the performance of sat solver

Active Publication Date: 2011-07-28
NEC CORP
View PDF15 Cites 15 Cited by
  • Summary
  • Abstract
  • Description
  • Claims
  • Application Information

AI Technical Summary

Benefits of technology

This patent describes a way to improve the efficiency of a computer program called STAMP (Simultaneous Localization And Mapping). It suggests limiting certain variables in the algorithm's equation to sequences with lower priorities than other parts of it. These orders can be fixed or adjusted depending upon how far the control paths have been taken away from their targets. By doing this, the program becomes more efficient at identifying possible faulty sections of the problem.

Problems solved by technology

In this patent, there is a technical problem with analyzing software or hardware models by searching for ways they can go beyond their reachable properties. Current methods involve finding all possible paths quickly but only considering certain aspects like frequency of occurrence. There is currently no method that considers application-specific information to improve efficiency.

Method used

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
View more

Image

Smart Image Click on the blue labels to locate them in the text.
Viewing Examples
Smart Image
  • Dpll-based sat solver using with application-aware branching
  • Dpll-based sat solver using with application-aware branching
  • Dpll-based sat solver using with application-aware branching

Examples

Experimental program
Comparison scheme
Effect test

Embodiment Construction

[0018]In accordance with the present principles, systems and methods integrate application level information directly into a solver to improve overall performance of the solver. The present embodiments build an application-aware branching technique on top of a Davis Putnam Longman Loveland (DPLL) based satisfiability (SAT) solver. From each bounded model checking problem, control flow information is obtained for a corresponding unrolling control flow graph (CFG). Control state reachability (CSR) information is computed from the unrolled CFG. For the given target control state (reachability goal), a sequence of control states is obtained in an increasing order of its control path distance to reach the target control state. The solver is provided with such a branching sequence corresponding to the derived control state order.

[0019]During a decision phase, the SAT solver picks the first free variable from the sequence provided, and assigns a Boolean value TRUE. If all the variables in the

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to view more

PUM

No PUM Login to view more

Abstract

A system and method for determining satisfiability of a bounded model checking instance by restricting the decision variable ordering of the SAT solver to a sequence wherein a set of control state variables is given higher priority over the rest variables appearing in the formula. The order for control state variables is chosen based on an increasing order of the control path distance of corresponding control states from the target control state. The order of the control variables is fixed, while that of the rest is determined by the SAT search. Such a decision variable ordering strategy leads to improved performance of SAT solver by early detection and pruning of the infeasible path segments that are closer to target control state.

Description

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to view more

Claims

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to view more

Application Information

Patent Timeline
no application Login to view more
Owner NEC CORP
Who we serve
  • R&D Engineer
  • R&D Manager
  • IP Professional
Why Eureka
  • Industry Leading Data Capabilities
  • Powerful AI technology
  • Patent DNA Extraction
Social media
Try Eureka
PatSnap group products

Browse by: Latest US Patents, China's latest patents, Technical Efficacy Thesaurus, Application Domain, Technology Topic.

© 2024 PatSnap. All rights reserved.Legal|Privacy policy|Modern Slavery Act Transparency Statement|Sitemap