In this assignment, a code to calculate satisfiability in a circuit will be transformed to work with OpenMP.
What is satisfiability? The full name is Boolean Satisfiability Problem (SAT). Given a equation or formula that has boolean inputs (TRUE or FALSE), is there some combination of the inputs where the equation evaluates to TRUE. SAT is one of the first problems that was proven to be NP-complete
A C code, sats.c, checks all 2^16 combinations of inputs to a circuit to find the few
where the circuit has an output of TRUE.
> ./a.out 39413) 1010111110011001 39414) 0110111110011001 39415) 1110111110011001 39925) 1010111111011001 39926) 0110111111011001 39927) 1110111111011001 40437) 1010111110111001 40438) 0110111110111001 40439) 1110111110111001 Done
As is, the code evaluates all the combinations very fast. You should rewrite it to have a more complex circuit with maybe 2^24 inputs (any power greater than 16 is acceptable) to determine whether a speedup occurs with using OpenMP. To increase the size of the circuit, the number of elements in the array has to increased as well as add more combinations of the elements.