diff --git a/bruteforce_approach/bruteforce.c b/bruteforce_approach/bruteforce.c index 33290f9..db3a865 100644 --- a/bruteforce_approach/bruteforce.c +++ b/bruteforce_approach/bruteforce.c @@ -1,374 +1,373 @@ #include #include #include #include #include #include // -------------- config #define MAX_AREA 10000 #define NUM_THREADS 3 //Needs to be <= 9 or 18 or 27 for efficient splitting the work load -#define NUM_INPUTS 3 +#define NUM_INPUTS 4 #define MAX_GATES 5 -//0: +#define use_truth_table 1 +#define target_truth_table "0110100110010110" -int target_function(int inputs[]) { - int ys__n0 = inputs[0]; - int ys__n1 = inputs[1]; - int ys__n5 = inputs[2]; - - return (ys__n0 && ((!ys__n1 && !ys__n5) || (ys__n1 && ys__n5))) || (!ys__n0 && ((!ys__n1 && ys__n5) || (ys__n1 && !ys__n5))); // ys__n7 -} - -/* +//AND = &&, OR = ||, XOR = ^, NOT = ! int target_function(int inputs[]) { return inputs[0] ^ inputs[1]; -}*/ +} // -------------- structs typedef struct { char* type; int area; } GateType; typedef struct { GateType* gate; - int in1; - int in2; + int8_t in1; + int8_t in2; } Gate; typedef struct { Gate gates[MAX_GATES]; - int gate_count; + int8_t gate_count; int area; } Circuit; typedef struct { Circuit volatile best_circuit; GateType *gate_types; int num_inputs; int num_gates; int volatile best_area; - int *truth_table; - int *target_outputs; + int8_t *truth_table; + int8_t *target_outputs; int worker_id; int num_circuit[2]; //first is the amount in million and the second is the increment counter. pthread_mutex_t mutex; } ThreadArgs; // -------------- define used gates /* GateType gate_types[] = { {"INV", 1160}, {"AND", 3472}, {"NAND", 2832}, {"OR", 3472}, {"NOR", 2832}, {"XOR", 4632}, {"XNOR", 4632}, {"ANDNOT", 3472}, {"ORNOT", 3472} };*/ GateType gate_types[] = { {"INV", 1160}, {"AND", 1288}, {"NAND", 2448}, {"OR", 1288}, {"NOR", 2448}, {"XOR", 2448}, {"XNOR", 2448}, {"ANDNOT", 1288}, {"ORNOT", 1288} }; // -------------- start functions -int evaluate_circuit(GateType* all_gates, Circuit* circuit, int* inputs) { - int intermediate_outputs[NUM_INPUTS + MAX_GATES]; - memcpy(intermediate_outputs, inputs, NUM_INPUTS * sizeof(int)); +int evaluate_circuit(GateType* all_gates, Circuit* circuit, int8_t* inputs) { + int8_t intermediate_outputs[NUM_INPUTS + MAX_GATES]; + memcpy(intermediate_outputs, inputs, NUM_INPUTS * sizeof(int8_t)); for (int i = 0; i < circuit->gate_count; i++) { int out1 = intermediate_outputs[circuit->gates[i].in1]; int out2 = intermediate_outputs[circuit->gates[i].in2]; int output = 0; if (circuit->gates[i].gate == &all_gates[0]) //INV output = ~out1 & 1; else if (circuit->gates[i].gate == &all_gates[1]) //AND output = out1 & out2; else if (circuit->gates[i].gate == &all_gates[2]) //NAND output = ~(out1 & out2) & 1; else if (circuit->gates[i].gate == &all_gates[3]) //OR output = out1 | out2; else if (circuit->gates[i].gate == &all_gates[4]) //NOR output = ~(out1 | out2) & 1; else if (circuit->gates[i].gate == &all_gates[5]) //XOR output = out1 ^ out2; else if (circuit->gates[i].gate == &all_gates[6]) //XNOR output = ~(out1 ^ out2) & 1; else if (circuit->gates[i].gate == &all_gates[7]) //ANDNOT output = out1 & (~out2 & 1); else if (circuit->gates[i].gate == &all_gates[8]) //ORNOT output = out1 | (~out2 & 1); intermediate_outputs[NUM_INPUTS + i] = output; } return intermediate_outputs[NUM_INPUTS + circuit->gate_count - 1]; } int detect_tautology(Circuit *current_circuit, int in1, int in2, int gate_selected, ThreadArgs *data){ if ((in1 == in2 && gate_selected != 0) || //NOTE THAT IF i == 0 THEN WE SELECT INV (in1 != in2 && gate_selected == 0) || (in1 > in2 && gate_selected != 7 && gate_selected != 8)) { //NOTE THAT i == 7 IS ANDNOT and i ==8 is ORNOT return 1; } for(int i=0; i<(current_circuit->gate_count-1);i++){ if(current_circuit->gates[i].gate == &data->gate_types[gate_selected]){ if(current_circuit->gates[i].in1 == in1 && current_circuit->gates[i].in2 == in2){ return 1; //DETECTED A COMPLETE equivalent circuit } } } int input_used[current_circuit->gate_count + data->num_inputs]; memset(input_used, 0, sizeof(input_used)); for(int i=0; igate_count; i++){ input_used[current_circuit->gates[i].in1] = 1; input_used[current_circuit->gates[i].in2] = 1; } input_used[in1] = 1; input_used[in2] = 1; for(int i=0; i<(current_circuit->gate_count + data->num_inputs -1);i++){ if(input_used[i]==0 && current_circuit->gate_count!=0){ return 2; } } return 0; } void generate_circuits_recursive(Circuit *current_circuit, int depth, ThreadArgs *data) { if (depth == data->num_gates){ // Reached end of amount of gates. return; } GateType* gate_types = data->gate_types; // Loop through gate types and inputs to build possible circuits int num_gate_types = 9; int division = (num_gate_types + NUM_THREADS-1)/NUM_THREADS; int multi_core_division=NUM_THREADS/num_gate_types; //0 - 2, 3 - 5, 6 - 8 for (int i = 0; i < num_gate_types; i++) { // ----------------- Going for multi processor approach if(depth == 0){//at first level has to seperate into threads if(NUM_THREADS<=9){ if((i<(data->worker_id*division)) | (i>=((data->worker_id+1)*division))){ //printf("Thread %d, skipping %s\n",data->worker_id,data->gate_types[i].type); continue; } } else { if( i != (data->worker_id/multi_core_division)){ //printf("Thread %d, skipping %s\n",data->worker_id,data->gate_types[i].type); continue; } } } else if (depth == 1 && NUM_THREADS>9) { if((i<(data->worker_id%multi_core_division)*(9/multi_core_division)) | (i>=((data->worker_id+1)%multi_core_division)*(9/multi_core_division))){ //printf("at depth 1 Thread %d, skipping %s\n",data->worker_id,data->gate_types[i].type); continue; } } if((current_circuit->area+data->gate_types[i].area)>data->best_area){ //printf("worker %d: area %d on gate type %d and depth %d larger then best area %d continueing\n",data->worker_id,current_circuit->area,i,depth,data->best_area); continue; } for (int in1 = 0; in1 < depth + data->num_inputs; in1++) { for (int in2 = 0; in2 < depth + data->num_inputs; in2++) { data->num_circuit[0] += 1; // Add the new gate to the circuit current_circuit->gates[depth].gate = &gate_types[i]; //set pointer to the type of gate current_circuit->gates[depth].in1 = in1; current_circuit->gates[depth].in2 = in2; current_circuit->gate_count = depth + 1; //if(current_circuit->gates[0].gate==&data->gate_types[5]){ // && current_circuit->gates[1].gate==&data->gate_types[5] && current_circuit->gates[2].gate==&data->gate_types[6]){ // printf("test\n"); //} int tautology = detect_tautology(current_circuit,in1,in2,i,data); //0: nothing found, 1: direct tautology, 2:unconnected device may still be connected. if(tautology==1){ continue; //Found already unnecessary combo and should skip it } int valid = 0; if(tautology!=2){ //There is an unconnected gate if this holds true valid = 1; for (int y=0; y < (1 << data->num_inputs); y++){ //CHECK IF IT IS VALID if(evaluate_circuit(data->gate_types, current_circuit, &data->truth_table[y*data->num_inputs])!=data->target_outputs[y]){ //Check if it satisfies the equation valid = 0; } } } //valid circuit add area current_circuit->area += gate_types[i].area; // Example area increment (modify as needed) if(data->num_circuit[0]%10000000 == 0){ data->num_circuit[1] += 1; data->num_circuit[0] = 0; printf("At circuit number %d M in worker %d current best_area %d and tested area %d\n",data->num_circuit[1],data->worker_id,data->best_area,current_circuit->area); } pthread_mutex_lock(&data->mutex); //get mutex if(valid == 1 && current_circuit->areabest_area){ //Found a valid solution! memcpy((void *)&data->best_circuit, current_circuit, sizeof(Circuit)); //write to best circuit printf("Found proper solution with size %d\n",current_circuit->area); for(int y=0; ygate_count; y++){ printf("%d: %s, in1: %d, in2: %d\n",y,current_circuit->gates[y].gate->type,current_circuit->gates[y].in1,current_circuit->gates[y].in2); } data->best_area = current_circuit->area; } pthread_mutex_unlock(&data->mutex); // Recurse to add more gates generate_circuits_recursive(current_circuit, depth + 1, data); current_circuit->area -= gate_types[i].area; // Example area increment (modify as needed) //printf("worker %d: returning with depth %d and area %d\n",data->worker_id,depth,current_circuit->area); } } } } void* search_space_worker(void* args) { // Define and initialize worker-specific parameters and loop through circuits // You will need to pass parameters in `args` and cast them in this function ThreadArgs *data; data = (ThreadArgs *) args; Circuit current_circuit; current_circuit.area = 0; current_circuit.gate_count = 0; printf("In thread %d with best Area %d\nGoing in recusive loop to check all circuits\n",data->worker_id, data->best_area); generate_circuits_recursive(¤t_circuit, 0, data); //finished set worker_id to 1000 to indicate to the management thread that we finished pthread_mutex_lock(&data->mutex); data->worker_id = 1000; pthread_mutex_unlock(&data->mutex); return NULL; // Return the best found circuit and area as needed } -void brute_force_boolean(Circuit* best_circuit, int truth_table[], int target_outputs[], int num_inputs, int max_gates, int max_area) { +void brute_force_boolean(Circuit* best_circuit, int8_t truth_table[], int8_t target_outputs[], int num_inputs, int max_gates, int max_area) { pthread_t threads[NUM_THREADS]; ThreadArgs thread_args[NUM_THREADS]; // Define `ThreadArgs` to pass data to threads int best_area = max_area; int total_circuits = 0; for (int i = 0; i < NUM_THREADS; i++) { thread_args[i].gate_types = gate_types; thread_args[i].num_inputs = num_inputs; thread_args[i].num_gates = max_gates; thread_args[i].best_area = best_area; thread_args[i].truth_table = truth_table; thread_args[i].target_outputs = target_outputs; thread_args[i].worker_id = i; thread_args[i].num_circuit[0] = 0; thread_args[i].num_circuit[1] = 0; pthread_mutex_init(&thread_args[i].mutex, NULL); pthread_create(&threads[i], NULL, search_space_worker, (void *)&thread_args[i]); } int number_of_running_threads = NUM_THREADS; while(number_of_running_threads>0){ number_of_running_threads = NUM_THREADS; for (int i = 0; i < NUM_THREADS; i++) { pthread_mutex_lock(&thread_args[i].mutex); //get lock on the data //Check if it found a better circuit then known before. if(thread_args[i].best_areabest_area){ printf("setting the best_area size %d, on worker: %d\n",best_area,i); thread_args[i].best_area = best_area; } //lastly check if the thread_closed if(thread_args[i].worker_id==1000){ number_of_running_threads -= 1; } pthread_mutex_unlock(&thread_args[i].mutex); // Collect best circuits and area from each thread } printf("running number of threads: %d\n",number_of_running_threads); sleep(1); } printf("no threads running anymore\n"); // Output the best circuit //count total amount of circuits for(int i=0;i> j) & 1; // Extract each bit of i as an input truth_table[i*num_inputs+j] = (i >> j) & 1;; } target_outputs[i] = target_function(inputs); } } int main() { // Define target function output - int target_outputs[1 << NUM_INPUTS]; // 1<(1 << NUM_INPUTS); i++){ + target_outputs[i] = target_truth_table[i]-'0'; + } + } + Circuit best_circuit; brute_force_boolean(&best_circuit, truth_table, target_outputs, NUM_INPUTS, MAX_GATES, MAX_AREA); printf("Found best solution with area: %d\n",best_circuit.area); for(int y=0; ytype,best_circuit.gates[y].in1,best_circuit.gates[y].in2); } // Print best circuit details return 0; }