Write a C program called threadcircuit to run on ocelot which will provide a multithreaded solution to the circuit-satisfiability problem which will compute for what combinations of input values will the circuit output the value 1. This is the sequential solution, which is also attached. You should create 4 threads and divide the 65,536 test cases among them. For example, if p=4, each thread would be responsible for roughly 65,536/4 number of iterations (if it's not divisible, some threads can end up with one more iteration than the others).
#include
#include
/* Return 1 if 'i'th bit of 'n' is 1; 0 otherwise */
#define EXTRACT_BIT(n,i) ((n&(1int check_circuit (int z) {
int v[16]; /* Each element is a bit of z */
int i;
for (i = 0; i
if ((v[0] || v[1]) && (!v[1] || !v[3]) && (v[2] || v[3])
&& (!v[3] || !v[4]) && (v[4] || !v[5])
&& (v[5] || !v[6]) && (v[5] || v[6])
&& (v[6] || !v[15]) && (v[7] || !v[8])
&& (!v[7] || !v[13]) && (v[8] || v[9])
&& (v[8] || !v[9]) && (!v[9] || !v[10])
&& (v[9] || v[11]) && (v[10] || v[11])
&& (v[12] || v[13]) && (v[13] || !v[14])
&& (v[14] || v[15])) {
printf ("%d%d%d%d%d%d%d%d%d%d%d%d%d%d%d%d\n",
v[0],v[1],v[2],v[3],v[4],v[5],v[6],v[7],v[8],v[9],
v[10],v[11],v[12],v[13],v[14],v[15]);
return 1;
} else return 0;
}
int main (int argc, char *argv[])
{
int count, i;
count = 0;
for (i = 0; i
count += check_circuit (i);
printf ("There are %d solutions\n", count);
return 0;
}
If a thread finds a combination that satisfies the circuit, it should print out the combination (like in the given sequential version), along with the thread id (a number between 0 and 3 (p-1)). In the end, the main thread should print out the total number of combinations that satisfy this circuit (like in the given sequential program). Mutex should be used to update the total by each thread. An example output of the program is shown below:
% threadcircuit
0) 0110111110011001
0) 1110111111011001
2) 1010111110011001
1) 1110111110011001
1) 1010111111011001
1) 0110111110111001
0) 1010111110111001
2) 0110111111011001
2) 1110111110111001
There are 9 solutions