1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
|
#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include <pthread.h>
/* Return 1 if 'i'th bit of 'n' is 1; 0 otherwise */
#define EXTRACT_BIT(n,i) ((n&(1<<i))?1:0)
int count = 0; // counting solutions
int output_thread = 0; //thread for printing
pthread_mutex_t mutex;
int check_circuit (int z) {
int v[16]; /* Each element is a bit of z */
int i;
for (i = 0; i < 16; i++) v[i] = EXTRACT_BIT(z,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]) && (v[1] == 1)) {
printf ("%d)%d%d%d%d%d%d%d%d%d%d%d%d%d%d%d%d\n",
output_thread, 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;
}
struct circuitStruct{
pthread_t id;
int thread_num; // index of thread
int total_threads; //total number of threads
int work_amount;
int start_pos;
};
void * multiCircuit ( void * tid)
{
struct circuitStruct *arg_struct = (struct circuitStruct *) tid;
int i = arg_struct->start_pos;
int j = arg_struct->work_amount;
printf("\n%d, %d,num:%d\n", i, j,arg_struct->thread_num);
while(i != j){
pthread_mutex_lock(&mutex);
output_thread = arg_struct->thread_num;
count+=check_circuit(i);
pthread_mutex_unlock(&mutex);
i++;
}
return 0;
}
int main (int argc, char *argv[])
{
struct circuitStruct *t;
if(argc != 2) { printf("Please enter a number of threads and ONLY a number between 1 - 128\n"); return -1;}
if(atoi(argv[1]) > 128 || atoi(argv[1]) < 1) {printf("Please enter a number of threads and ONLY a number between 1 - 128\n"); return -1;}
int threads = atoi(argv[1]); // threads in use
pthread_mutex_init(&mutex, NULL); // lock initialized
struct timeval t1, t2; //time setup
gettimeofday(&t1, 0); //time initialized
t = (struct circuitStruct*)malloc(threads*sizeof(struct circuitStruct)); // mem allocation for structure
for(int i = 0; i < threads; i++)
{
if(i == threads -1 && (65536 %threads != 0))
{
t[i].work_amount += 65536%threads;
}
t[i].thread_num = i;
t[i].total_threads = threads;
t[i].work_amount += 65536/threads + t[i-1].work_amount;
t[i].start_pos = t[i-1].work_amount;
pthread_create(&t[i].id, 0, multiCircuit, &t[i]);
gettimeofday(&t2, 0);
}
for(int i = 0; i < threads; i++)
{
pthread_join(t[i].id, 0);
}
printf ("Execution time %fs\n", (t2.tv_sec-t1.tv_sec)+(t2.tv_usec-t1.tv_usec)*1e-6);
printf ("There are %d solutions\n", count);
pthread_mutex_destroy(&mutex);
free(t);
return 0;
}
|
