14923930
Cache Performance of SAT Solvers: a Case Study for Efficient Implementation of Algorithms
We experimentally evaluate the cache performance of different SAT solvers as a case study for the efficient implementation of SAT algorithms. We evaluate several different Boolean Constraint Propagation (BCP) mechanisms and show their respective run time and cache performances on selected benchmark instances. From the experiments we conclude that a cache friendly data structure is a key element in the efficient implementation of SAT solvers. We also show empirical cache miss rates of several modern SAT solvers based on the Davis-Logemann-Loveland (DLL) algorithm with learning and non-chronological backtracking. We conclude that the recently developed SAT solvers are much more cache friendly in data structures and algorithm implementations compared with their predecessors.
5444394
A First Look at Peer-to-Peer Worms: Threats and Defenses
Peer-to-peer (P2P) worms exploit common vulnerabilities in member hosts of a P2P network and spread topologically in the P2P network, a potentially more effective strategy than random scanning for locating victims. This paper describes the danger posed by P2P worms and initiates the study of possible mitigation mechanisms. In particular, the paper explores the feasibility of a self-defense infrastructure inside a P2P network, outlines the challenges, evaluates how well this defense mechanism contains P2P worms, and reveals correlations between containment and the overlay topology of a P2P network. Our experiments suggest a number of design directions to improve the resilience of P2P networks to worm attacks.
70202123
The Quest for Efficient Boolean Satisfiability Solvers
The classical NP-complete problem of Boolean Satisfiability (SAT) has seen much interest in not just the theoretical computer science community, but also in areas where practical solutions to this problem enable significant practical applications. Since the first development of the basic search based algorithm proposed by Davis, Putnam, Logemann and Loveland (DPLL) about forty years ago, this area has seen active research effort with many interesting contributions that have culminated in state-of-the-art SAT solvers today being able to handle problem instances with thousands, and in same cases even millions, of variables. In this paper we examine some of the main ideas along this passage that have led to our current capabilities. Given the depth of the literature in this field, it is impossible to do this in any comprehensive way; rather we focus on techniques with consistent demonstrated efficiency in available solvers. For the most part, we focus on techniques within the basic DPLL search framework, but also briefly describe other approaches and look at some possible future research directions.
7358200
The Quest for Efficient Boolean Satisfiability Solvers
The classical NP-complete problem of Boolean Satisfiability (SAT) has seen much interest in not just the theoretical computer science community, but also in areas where practical solutions to this problem enable significant practical applications. Since the first development of the basic search based algorithm proposed by Davis, Putnam, Logemann and Loveland (DPLL) about forty years ago, this area has seen active research effort with many interesting contributions that have culminated in state-of-the-art SAT solvers today being able to handle problem instances with thousands, and in same cases even millions, of variables. In this paper we examine some of the main ideas along this passage that have led to our current capabilities. Given the depth of the literature in this field, it is impossible to do this in any comprehensive way; rather we focus on techniques with consistent demonstrated efficiency in available solvers. For the most part, we focus on techniques within the basic DPLL search framework, but also briefly describe other approaches and look at some possible future research directions.
8920735
Partition-based decision heuristics for image computation using SAT and BDDs
Methods based on Boolean satisfiability (SAT) typically use a conjunctive normal form (CNF) representation of the Boolean formula, and exploit the structure of the given problem through use of various decision heuristics and implication methods. We propose a new decision heuristic based on separator-set induced partitioning of the underlying CNF graph. It targets those variables whose choice generates clause partitions with disjoint variable supports. This can potentially improve performance of SAT applications by decomposing the problem dynamically within the search. In the context of a recently proposed image computation method combining SAT and BDDs, this results in simpler BDD subproblems. We provide algorithms for CNF partitioning - one based on a clause-variable dependency matrix, and another based on standard hypergraph partitioning techniques, and also for the use of partitioning information in decision heuristics for SAT. The effectiveness of the proposed partition-based heuristic is shown with practical results for reachability analysis of benchmark sequential circuits.
10515113
Validating SAT solvers using an independent resolution-based checker: practical implementations and other applications
As the use of SAT solvers as core engines in EDA applications grows, it becomes increasingly important to validate their correctness. In this paper, we describe the implementation of an independent resolution-based checking procedure that can check the validity of unsatisfiable claims produced by the SAT solver zchaff. We examine the practical implementation issues of such a checker and describe two implementations with different pros and cons. Experimental results show low overhead for the checking process. Our checker can work with many other modern SAT solvers with minor modifications, and it can provide information for debugging when checking fails. Finally we describe additional results that can be obtained by the validation process and briefly discuss their applications.
9760560
An edge-guided image interpolation algorithm via directional filtering and data fusion
Preserving edge structures is a challenge to image interpolation algorithms that reconstruct a high-resolution image from a low-resolution counterpart. We propose a new edge-guided nonlinear interpolation technique through directional filtering and data fusion. For a pixel to be interpolated, two observation sets are defined in two orthogonal directions, and each set produces an estimate of the pixel value. These directional estimates, modeled as different noisy measurements of the missing pixel are fused by the linear minimum mean square-error estimation (LMMSE) technique into a more robust estimate, using the statistics of the two observation sets. We also present a simplified version of the LMMSE-based interpolation algorithm to reduce computational cost without sacrificing much the interpolation performance. Experiments show that the new interpolation techniques can preserve edge sharpness and reduce ringing artifacts
52862068
Robust face alignment based on local texture classifiers
We propose a robust face alignment algorithm with a novel discriminative local texture model. Different from the conventional descriptive PCA local texture model in ASM, classifiers using LUT-type Haar-like features are trained from a large data set as local texture model. The strong discriminative power of the classifier greatly improves the accuracy and robustness of local searching on faces with expression variation and ambiguous contours. A Bayesian framework is configured for shape parameter optimization and the algorithm is implemented in a hierarchical structure for efficiency. Extensive experiments are reported to show its accuracy and robustness.
7654369
Extension of a list coloring problem
Abstract For a graph H , f ( H ) is the smallest integer k such that the join of H with an empty graph E k of order k is not | V ( H ) | -choosable. It was conjectured that for a triangle-free graph G , f ( G ) = n 2 μ ( G ) n n − 2 μ ( G ) , where n = | V ( G ) | and μ ( G ) is the cardinality of a maximum matching of graph G [S. Gravier, F. Maffray, B. Mohar, On a list-coloring problem, Discrete Math. 268 (2003) 303–308]. We verify this conjecture in the case of forests, and propose some related problems.
11022941
XML-Based Advanced UDDI Search Mechanism for B2B Integration
Exploring appropriate business applications published as Web Services in UDDI registries is a critical issue. Search for such applications should be effective in terms of time and uniformed in terms of interfaces. In this paper, an XML-based advanced UDDI exploring engine, Business Explorer for Web Services (BE4WS), that provides developers with standard interfaces for efficiently searching business and service information in single or multiple UDDI registries is presented. The engine processes the proposed UDDI Search Markup Language (USML) that specifies a search request comprising multiple queries, UDDI sources, search criteria, and aggregation operator. The core component of BE4WS, Advanced UDDI Search Engine (AUSE), aggregates search results from different UDDI registries based on the USML request and built-in intelligent search facilities with the ability to cross-reference multiple categories. An aggregation example using BE4WS is demonstrated to enable easy B2B integration.
18609835
Extraction and visualization of architectural structure based on cross references among object files
Reverse engineering of legacy systems is a knowledge-intensive process to reconstruct the understanding of a system. A semi-automatic process that can extract architecture level structure from legacy systems is introduced in This work. Exact facts related to cross-references among ELF objects are extracted from files automatically, and then partitioned into hierarchical groups by close cooperation between domain experts and an assistant tool DEREF. By resolving the cross references among these groups, the architectural structure is reconstructed and then visualized using auto-layout techniques. A case study on three embedded operating system demonstrates that this process can be used to obtain a comprehensive understanding about legacy systems even without any a priori knowledge about its design.