Stochastic local search accelerator based on cams for solving constraint satisfaction problems

A computer-implemented method of solving a K-Satisfiability (K-SAT) problem using a content addressable memory (CAM) comprising:

• programming, by a processor, one or more clauses of a Boolean expression for a K-SAT problem written in negated disjunctive normal form (DNF) to a ternary-CAM (TCAM) array comprising columns and rows of TCAM cells, wherein each clause of the Boolean expression is programmed to a respective row of the TCAM array, and wherein each occurring variable of each clause is mapped to a respective TCAM cell of the row, and wherein each non-occurring variable is programmed as a don't care value;
• applying, by the processor, an interpretation comprising one or more binary variables expected to solve the Boolean expression as an input along the columns to the TCAM array;
• returning, by the processor, a binary value for each violated clause;
• applying, by the processor, a matrix multi-vector multiplication to one or more values stored in a dot product engine (DPE) to determine which variable contributes most to each violated clause;
• and
• altering, by the processor, one or more literals within the interpretation based on which variable contributes most to each violated clause.

A circuit for solving a K-Satisfiability (K-SAT) problem comprising:

• a ternary content addressable memory (TCAM) configured to determine whether an interpretation comprising one or more clauses of a Boolean expression, written in negated disjunctive normal form (DNF), is satisfied;
• a stochastic multiple match resolver (SMMR) communicatively coupled to the TCAM, wherein the SMMR is configured to randomly select one high value match line from one or more high value match lines communicatively coupled to each row of the TCAM;
• and
• a static random access memory (SRAM), communicatively coupled to the SMMR, wherein the SRAM is configured to return a violated clause to a choice block.

A non-transitory computer readable storage medium storing instructions that, when executed by a processor, cause the processor to:

• program one or more clauses of a Boolean expression for a K-Satisfiability (K-SAT) problem written in negated disjunctive normal form (DNF) to a ternary content addressable memory (TCAM) array comprising columns and rows of TCAM cells, wherein each clause of the Boolean expression is programmed to a respective row of the TCAM array, and wherein each occurring variable of each clause is mapped to a respective TCAM cell of the row, and wherein each non-occurring variable is programmed as a don't care value;
• apply a first interpretation, comprising one or more binary variables expected to solve the Boolean expression, as an input along the columns to the TCAM array;
• return a binary value for each clause;
• randomly select one or more violated clause index;
• determine a break count for each variable of one violated clause;
• and
• alter one or more variables within the first interpretation if at least one clause of the Boolean expression is not satisfied.