Instructions
Requirements and Specifications
Source Code
/**
* Your Name
* Your Panther ID
* A multi-threaded program that counts circuit combinations that yields to a value of 1.
* This is an affirmation of originality.
*/
#include
#include
#include
#include
/* Return 1 if 'i'th bit of 'n' is 1; 0 otherwise */
#define EXTRACT_BIT(n, i) ((n&(1<
#define NUM_THREADS 8
#define NUM_TASKS 65536
pthread_mutex_t count_mutex = PTHREAD_MUTEX_INITIALIZER;
int count = 0;
/* We'll use this to assign the job to be worked on by a thread */
typedef struct thread_parameter_s {
int id;
int *values;
int num_values;
} thread_parameter_t;
int check_circuit(int thread_id, 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])) {
printf("%d) %d%d%d%d%d%d%d%d%d%d%d%d%d%d%d%d\n",
thread_id,
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]);
eturn 1;
} else {
return 0;
}
}
/* Entry point of a thread */
void *run_thread(void *args) {
thread_parameter_t *parameter;
int i;
int result;
/* Work on the values given to the thread */
parameter = (thread_parameter_t *) args;
for(i = 0; i < parameter->num_values; i++) {
result = check_circuit(parameter->id, parameter->values[i]);
if(result > 0) {
/* Use mutex to protect shared variables from race condition */
pthread_mutex_lock(&count_mutex);
count++;
pthread_mutex_unlock(&count_mutex);
}
}
return (void *) NULL;
}
/* Entry point of the program */
int main(int argc, char *agv[]) {
thread_parameter_t parameters[NUM_THREADS];
pthread_t threads[NUM_THREADS];
int i, id;
int length_per_thread;
/* Initialize the threads */
length_per_thread = NUM_TASKS / NUM_THREADS;
i = 0;
for(id = 0; id < NUM_THREADS; id++) {
parameters[id].id = id;
parameters[id].values = (int *) malloc(sizeof(int) * length_per_thread);
parameters[id].num_values = 0;
}
/* Distribute the the each number to each thread like a deck of card */
id = 0;
for(i = 0; i < NUM_TASKS; i++) {
parameters[id].values[parameters[id].num_values++] = i;
id = (id + 1) % NUM_THREADS;
}
/* Run the threads */
for(id = 0; id < NUM_THREADS; id++)
pthread_create(&threads[id], NULL, &run_thread, ¶meters[id]);
/* Wait for all threads to finish */
for(id = 0; id < NUM_THREADS; id++)
pthread_join(threads[id], NULL);
printf("There are %d solutions\n", count);
/* Delete allocated memory */
for(id = 0; id < NUM_THREADS; id++)
free(parameters[id].values);
return 0;
}