International Business Machines Corporation

Intranational Business Machines Corporation

Eyal Bin

Allon Adir

Avi Ziv

Roy Emek

Vitali Sokhin

Amir Nahir

Odellia Boni

Anatoly Koyfman

Shady Copty

Elena Tsanko

Shimon Landa

Kirill Shoikhet

Yael Ben-Haim

Merav Aharoni

Technical solutions are described for reusing a solution for a test. An example method includes building, by a processor, a solution cache including a tree structure representative of a plurality of solutions, which stores a key configurable immediate value of a previous solution as a node, the previous solution as a leaf node of the tree, and an edge from the node indicative of a value of the key configurable immediate value at the node. The method includes traversing nodes of the tree structure in the solution cache to identify key configurable immediate values of a previous solution identical to configurable immediate values from the test by identifying edges associated values identical to those from the test. In response to reaching a leaf node of the tree structure, using the solution(s) at the leaf node as a solution of the test.

Building and reusing solution cache for constraint satisfaction problems

A method and product for solving a Constraint Satisfaction Problem (CSP) having a constraint associated with a string variable, comprising: defining a string variable using a string domain data structure representing a domain of string values for string variables, the structure represents the domain as a Deterministic Finite Automaton (DFA) with no back loops longer than 1 and edges representing characters; defining a constraint for the CSP, wherein the constraint involves the variable and is to be complied with by a solution to the CSP; invoking a CSP solver using the string variable while complying with the constraint, and to invoke operations performed over the domain, wherein the solver: propagates values into the domain of string values, wherein the value propagation reduces the domain size; or selects values from the domain thus reducing the domain to a singleton domain, whereby value propagation to domains of other variables is invoked by the solver.

String variables reprsentation in solvers

An apparatus and a computer-implemented method performed by a computerized device, comprising: generating a collection of test data for testing one or more domains, wherein the test data is useful for post-silicon verification of hardware devices; selecting a subset of the collection of test data in accordance with a hardware device to be tested and at least one of the domains to be tested with respect to the hardware device; and indexing the subset of the collection of test data to obtain an indexed collection.

Method and apparatus for post-silicon testing

A computer-implemented method, apparatus and product for solving a Constraint Satisfaction Problem (CSP). The computer-implemented method, performed by a computerized device, comprising: obtaining the CSP comprising a set of variables, a set of corresponding domains, and a set of constraints; and solving the CSP by iteratively: limiting the domains to exclude values that cannot satisfy one or more constraints of the set of constraints; heuristically selecting a variable out of the set of variables, wherein said heuristically selecting is based on constraint semantics of a constraint of the set of constraints; and limiting a corresponding domain of the selected variable.

Constraint satisfaction problem solving using constraint semantics

A CSP is modified to include an auxiliary variable. A component of a constraint of the CSP is modified to refer to the auxiliary variable instead of referring to a pair of variables. A domain for the auxiliary variable may be defined based on domains of the pair of variables. A binding constraint is added to the CSP to bind the value of the auxiliary variable with the values of the pair of variables. The modified CSP is solved using a CSP solver.

Constraint satisfaction problem solver

A method for automatically generating test programs includes receiving a description of a system under test, expressed in terms of variables associated with the system and conditional constraints including semantics applied to the variables, and receiving a definition of an event to be tested in the system. The method generates an ECondCSP over the variables responsively to the definition of the event and to the conditional constraints, such that at least some of the semantics of the conditional constraints are preserved in the ECondCSP when one or more of the variables to which the semantics are applied are inactive. The ECondCSP is solved to generate a test case for the system.

Growing community of inventors

Haifa, Israel

Eyal Bin