diff --git a/bruteforce_approach/bruteforce.c b/bruteforce_approach/bruteforce_multiple_outputs.c similarity index 63% rename from bruteforce_approach/bruteforce.c rename to bruteforce_approach/bruteforce_multiple_outputs.c index db3a865..9493a99 100644 --- a/bruteforce_approach/bruteforce.c +++ b/bruteforce_approach/bruteforce_multiple_outputs.c @@ -1,373 +1,472 @@ +#include #include #include #include #include #include +#include #include // -------------- config -#define MAX_AREA 10000 +#define MAX_AREA 10000 //Determine the initial max_area +#define NUM_INPUTS 3 //speaks for itself +#define MAX_GATES 5 // determine the max_amount of gates #define NUM_THREADS 3 //Needs to be <= 9 or 18 or 27 for efficient splitting the work load -#define NUM_INPUTS 4 -#define MAX_GATES 5 -#define use_truth_table 1 -#define target_truth_table "0110100110010110" +#define use_truth_table 1 //If 1 use the truth table below. If multiple outputs then paste the truth table after another from the [file].truth +#define target_truth_table "10010110" //exampe here [Target A][Target B] pasted after another. +/* +The truth table matching this is that of a increase in value of the input variables +Let's say 3 input variables + +A, B, Cin, | S Cout +0, 0, 0, | 0 0 +0, 0, 1, | 1 0 +0, 1, 0, | 1 0 +0, 1, 1, | 0 1 +1, 0, 0, | 1 0 +1, 0, 1, | 0 1 +1, 1, 0, | 0 1 +1, 1, 1, | 1 1 + +S = 10010110 +Cout = 11101000 +target_truth_table = "S Cin" = "1110100010010110" +also means that output B +*/ //AND = &&, OR = ||, XOR = ^, NOT = ! int target_function(int inputs[]) { - return inputs[0] ^ inputs[1]; + return inputs[0] ^ inputs[1] ^ inputs[2] ^ inputs [3]; } +// -------------- Auto-define + +#define NUM_COMBINATION (1 << NUM_INPUTS) +#define NUM_OUTPUTS (sizeof(target_truth_table)-1)/NUM_COMBINATION + // -------------- structs typedef struct { char* type; int area; } GateType; typedef struct { GateType* gate; int8_t in1; int8_t in2; } Gate; typedef struct { Gate gates[MAX_GATES]; 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; 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 +void tee(FILE *f, char const *fmt, ...) { + va_list ap; + va_start(ap, fmt); + vprintf(fmt, ap); + va_end(ap); + va_start(ap, fmt); + vfprintf(f, fmt, ap); + va_end(ap); +} + +void print_circuit(Circuit * circuit){ + FILE *fptr; + + fptr = fopen("../output/output_bruteforce.txt", "a"); + + for(int y=0; ygate_count; y++){ + printf("%d: %s, in1: %d, in2: %d\n",y,circuit->gates[y].gate->type,circuit->gates[y].in1,circuit->gates[y].in2); + } + + tee(fptr,"------- Circuit area: %d -------\n",circuit->area); + tee(fptr,"Input "); + for(int i='a';(i-'a')gate_count; y++){ + int print_in1 = circuit->gates[y].in1 + '0'; + int print_in2 = circuit->gates[y].in2 + '0'; + if((print_in1-'0')gates[y].in1 + 'a'; + } + if((print_in2-'0')gates[y].in2 + 'a'; + } + + tee(fptr,"%d: %s, in1: %c, in2: %c\n",y+NUM_INPUTS,circuit->gates[y].gate->type,print_in1,print_in2); + } + + tee(fptr,"Output "); + for(int i='x';(i-'x')gate_count-NUM_OUTPUTS+(i-'x'));} + tee(fptr,"\n"); + tee(fptr,"----------------------------------\n"); + fclose(fptr); +} + +void write_circuit_to_file(Circuit * circuit, int area, int worker_number, int file_number){ + FILE *fptr; + + char file_name[100]; + sprintf(file_name, "../output/output_%d_%d_%d_bruteforce.dot", area, worker_number, file_number); -int evaluate_circuit(GateType* all_gates, Circuit* circuit, int8_t* inputs) { + fptr = fopen(file_name, "w"); + + //for(int y=0; ygate_count; y++){ + // printf("%d: %s, in1: %d, in2: %d, in3: %d\n",y,circuit->gates[y].gate->type,circuit->gates[y].in1,circuit->gates[y].in2,circuit->gates[y].in3); + //} + fprintf(fptr, "digraph Circuit {\n rankdir=LR; // Makes the graph left-to-right\n node [shape=ellipse]; // Default shape for nodes\n"); + + + for(int i='a';(i-'a')gate_count; y++){ + int print_in1 = circuit->gates[y].in1 + '0'; + int print_in2 = circuit->gates[y].in2 + '0'; + if((print_in1-'0')gates[y].in1 + 'a'; + } + if((print_in2-'0')gates[y].in2 + 'a'; + } + + int unit_number = y+NUM_INPUTS; + fprintf(fptr," %d [ shape=record, label=\"{{ in 0| in 1}| %s %d |{ Y}}\", color=\"darkred\", fontcolor=\"darkred\" ];\n",unit_number,circuit->gates[y].gate->type,unit_number); + fprintf(fptr," %c:e -> %d:p1;\n %c:e -> %d:p2;\n",print_in1,unit_number,print_in2,unit_number); + } + + for(int i='x';(i-'x') %c;\n",NUM_INPUTS+circuit->gate_count-NUM_OUTPUTS+(i-'x'),i);} + + + fprintf(fptr,"}\n"); + fclose(fptr); +} + +void evaluate_circuit(GateType* all_gates, Circuit* circuit, int8_t* inputs, int8_t* outputs) { 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]; + + for(int z=0; zgate_count-NUM_OUTPUTS+z]; + } } 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 + if ((in1 == in2 && gate_selected != 0) || //Skip gate if it has the same input both ports NOTE THAT IF i == 0 THEN WE SELECT INV. + (in1 != in2 && gate_selected == 0) || //Skip if inverter has different in2. + (in1 > in2 && gate_selected != 7 && gate_selected != 8)) { //skip if with symmetry connected 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++){ + for(int i=0; i<(current_circuit->gate_count + data->num_inputs - NUM_OUTPUTS);i++){ if(input_used[i]==0 && current_circuit->gate_count!=0){ - return 2; + return 2; //missing an used output } } 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 } + //if(current_circuit->gates[0].gate==&data->gate_types[1] && current_circuit->gates[1].gate==&data->gate_types[0] && current_circuit->gate_count==2 && tautology==0){// && current_circuit->gates[2].gate==&data->gate_types[6]){ + // printf("test\n"); + //} int valid = 0; if(tautology!=2){ //There is an unconnected gate if this holds true valid = 1; + int8_t output[NUM_OUTPUTS]; 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; + evaluate_circuit(data->gate_types, current_circuit, &data->truth_table[y*data->num_inputs], output); + for(int z=0; ztarget_outputs[y+NUM_COMBINATION*z]){ + 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){ + if(data->num_circuit[0]%1000000000 == 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); + printf("%d:At circuit number %d M current best_area %d and tested area %d\n",data->worker_id,data->num_circuit[1],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); - } + printf("%d: Found proper solution\n",data->worker_id); + print_circuit(current_circuit); + write_circuit_to_file(current_circuit,current_circuit->area,data->worker_id,data->num_circuit[0]*100 + data->num_circuit[1]); 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); + printf("%d: best Area %d, Going 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, 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]); } + clock_t begin = clock(); 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); + + clock_t toc = clock(); + printf("%f: running number of threads: %d\n",(double)(toc - begin) / (CLOCKS_PER_SEC*number_of_running_threads),number_of_running_threads); + sleep(5); } 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 - int8_t target_outputs[1 << NUM_INPUTS]; // 1<(1 << NUM_INPUTS); i++){ - target_outputs[i] = target_truth_table[i]-'0'; + for(int i=0; i<(NUM_COMBINATION*NUM_OUTPUTS); i++){ + target_outputs[i] = target_truth_table[(NUM_COMBINATION*NUM_OUTPUTS-1)-i]-'0'; //load in the truth table but then flipped } } 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); - } + printf("Found best solution\n"); + print_circuit(&best_circuit); + write_circuit_to_file(&best_circuit,best_circuit.area,0,0); // Print best circuit details return 0; } diff --git a/bruteforce_approach/bruteforce_muxig.c b/bruteforce_approach/bruteforce_muxig.c new file mode 100644 index 0000000..df70d86 --- /dev/null +++ b/bruteforce_approach/bruteforce_muxig.c @@ -0,0 +1,463 @@ +#include +#include +#include +#include +#include +#include +#include + +// -------------- config + +#define MAX_AREA 15000 //Determine the initial max_area +#define NUM_INPUTS 3 //speaks for itself +#define MAX_GATES 10 // determine the max_amount of gates +#define NUM_THREADS 3 //Needs to be <= 9 or 18 or 27 for efficient splitting the work load + +#define use_truth_table 1 //If 1 use the truth table below. If multiple outputs then paste the truth table after another from the [file].truth +#define target_truth_table "10010110" //exampe here [Target A][Target B] pasted after another. + +/* +The truth table matching this is that of a increase in value of the input variables +Let's say 3 input variables + +I3 I2 I1 | O2 O1 +A, B, Cin, | S Cout +0, 0, 0, | 0 0 +0, 0, 1, | 1 0 +0, 1, 0, | 1 0 +0, 1, 1, | 0 1 +1, 0, 0, | 1 0 +1, 0, 1, | 0 1 +1, 1, 0, | 0 1 +1, 1, 1, | 1 1 + +S = 10010110 +Cout = 11101000 +MUX = 11001010 +target_truth_table = "S Cin" = "1110100010010110" +also means that output B +*/ +//AND = &&, OR = ||, XOR = ^, NOT = ! +int target_function(int inputs[]) { + return inputs[0] ^ inputs[1]; +} + +// -------------- Auto-define + +#define NUM_COMBINATION (1 << NUM_INPUTS) +#define NUM_OUTPUTS (sizeof(target_truth_table)-1)/NUM_COMBINATION + +// -------------- structs + +typedef struct { + char* type; + int area; +} GateType; + +typedef struct { + GateType* gate; + int8_t in1; + int8_t in2; + int8_t in3; +} Gate; + +typedef struct { + Gate gates[MAX_GATES]; + 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; + 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}, + {"MUX", 1288} +}; + +// -------------- start functions +void tee(FILE *f, char const *fmt, ...) { + va_list ap; + va_start(ap, fmt); + vprintf(fmt, ap); + va_end(ap); + va_start(ap, fmt); + vfprintf(f, fmt, ap); + va_end(ap); +} + +void print_circuit(Circuit * circuit){ + FILE *fptr; + + fptr = fopen("../output/output_bruteforce.txt", "a"); + + //for(int y=0; ygate_count; y++){ + // printf("%d: %s, in1: %d, in2: %d, in3: %d\n",y,circuit->gates[y].gate->type,circuit->gates[y].in1,circuit->gates[y].in2,circuit->gates[y].in3); + //} + + tee(fptr,"------- Circuit area: %d -------\n",circuit->area); + tee(fptr,"Input "); + for(int i='a';(i-'a')gate_count; y++){ + int print_in1 = circuit->gates[y].in1 + '0'; + int print_in2 = circuit->gates[y].in2 + '0'; + int print_in3 = circuit->gates[y].in3 + '0'; + if((print_in1-2-'0')=0){ + print_in1 = circuit->gates[y].in1-2 + 'a'; + } + if((print_in2-2-'0')=0){ + print_in2 = circuit->gates[y].in2-2 + 'a'; + } + if((print_in3-2-'0')=0){ + print_in3 = circuit->gates[y].in3-2 + 'a'; + } + + tee(fptr,"%d: %s, in1: %c, in2: %c, in3: %c\n",y+NUM_INPUTS+2,circuit->gates[y].gate->type,print_in1,print_in2,print_in3); + } + + tee(fptr,"Output "); + for(int i='x';(i-'x')gate_count-NUM_OUTPUTS+(i-'x')+2);} + tee(fptr,"\n"); + tee(fptr,"----------------------------------\n"); + fclose(fptr); +} + +void write_circuit_to_file(Circuit * circuit, int area, int worker_number, int file_number){ + FILE *fptr; + + char file_name[100]; + sprintf(file_name, "../output/output_%d_%d_%d_bruteforce.dot", area, worker_number, file_number); + + fptr = fopen(file_name, "w"); + + //for(int y=0; ygate_count; y++){ + // printf("%d: %s, in1: %d, in2: %d, in3: %d\n",y,circuit->gates[y].gate->type,circuit->gates[y].in1,circuit->gates[y].in2,circuit->gates[y].in3); + //} + fprintf(fptr, "digraph Circuit {\n rankdir=LR; // Makes the graph left-to-right\n node [shape=ellipse]; // Default shape for nodes\n"); + + + for(int i='a';(i-'a')gate_count; y++){ + int print_in1 = circuit->gates[y].in1 + '0'; + int print_in2 = circuit->gates[y].in2 + '0'; + int print_in3 = circuit->gates[y].in3 + '0'; + if((print_in1-2-'0')=0){ + print_in1 = circuit->gates[y].in1-2 + 'a'; + } + if((print_in2-2-'0')=0){ + print_in2 = circuit->gates[y].in2-2 + 'a'; + } + if((print_in3-2-'0')=0){ + print_in3 = circuit->gates[y].in3-2 + 'a'; + } + int unit_number = y+NUM_INPUTS+2; + fprintf(fptr," %d [ shape=record, label=\"{{ in 0| in 1| S}| MUX %d |{ Y}}\", color=\"darkred\", fontcolor=\"darkred\" ];\n",unit_number,unit_number); + fprintf(fptr," %c:e -> %d:p1;\n %c:e -> %d:p2;\n %c:e -> %d:p3;\n",print_in1,unit_number,print_in2,unit_number,print_in3,unit_number); + } + + for(int i='x';(i-'x') %c;\n",NUM_INPUTS+circuit->gate_count-NUM_OUTPUTS+(i-'x')+2,i);} + + + fprintf(fptr,"}\n"); + fclose(fptr); +} + +void evaluate_circuit(GateType* all_gates, Circuit* circuit, int8_t* inputs, int8_t* outputs) { + int8_t intermediate_outputs[NUM_INPUTS + MAX_GATES+2]; + intermediate_outputs[0] = 0; //Make sure that intermediate_outputs[0] = 0 and [1] = 1 for constant signal attachments + intermediate_outputs[1] = 1; + memcpy(&intermediate_outputs[2], inputs, NUM_INPUTS * sizeof(int8_t)); //copy boolean value over this + + 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 out3 = intermediate_outputs[circuit->gates[i].in3]; + int output = 0; + + if (circuit->gates[i].gate == &all_gates[0]) //INV + output = ~out1 & 1; + else if (circuit->gates[i].gate == &all_gates[1]) //MUX + output = out3 ? out2 : out1; + + intermediate_outputs[NUM_INPUTS + i + 2] = output; + } + + for(int z=0; zgate_count-NUM_OUTPUTS+z]; + } +} + +int detect_tautology(Circuit *current_circuit, int in1, int in2, int in3, int gate_selected, ThreadArgs *data){ + if ((in1 == in2 && gate_selected != 0) || + (in1 == 0 && in2 == 1 && gate_selected != 0) ){ //|| //Skip gate if it has the same input both ports NOTE THAT IF i == 0 THEN WE SELECT INV. + 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 && current_circuit->gates[i].in3 == in3){ + return 1; //DETECTED A COMPLETE equivalent circuit + } + } + } + + int input_used[current_circuit->gate_count + data->num_inputs+2]; + memset(input_used, 0, sizeof(input_used)); + + input_used[0] = 1; //make sure that the constant don't trigger a faulty tautology result. + input_used[1] = 1; + + 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[current_circuit->gates[i].in3] = 1; + } + + input_used[in1] = 1; + input_used[in2] = 1; + input_used[in3] = 1; + + for(int i=0; i < (current_circuit->gate_count + data->num_inputs - NUM_OUTPUTS+2); i++){ + if(input_used[i]==0 && current_circuit->gate_count!=0){ + return 2; //missing an used output + } + } + + 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 = 1; + //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++) { + int i = 1; //Only select the multiplexer + + 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); + return; + } + + for (int in3 = 2; in3 < depth + data->num_inputs + 2; in3++){ + + //Going for multithread approach + if(in3 != data->worker_id+2 && depth == 0){ + continue; + } + + for (int in2 = 0; in2 < depth + data->num_inputs + 2; in2++) { + for (int in1 = 0; in1 < depth + data->num_inputs + 2; in1++){ + 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->gates[depth].in3 = in3; + current_circuit->gate_count = depth + 1; + + //if(current_circuit->gates[0].in1 == 0 && current_circuit->gates[0].in2 == 1 && current_circuit->gates[0].in3 == 3 && current_circuit->gates[1].in1 == 2 && current_circuit->gates[1].in2 == 3 && current_circuit->gates[1].in3 == 4 && current_circuit->gates[2].in1 == 4 && current_circuit->gates[2].in2 == 5 && current_circuit->gates[2].in3 == 6){// && current_circuit->gates[2].gate==&data->gate_types[6]){ + //if(current_circuit->gates[0].in1 == 2 && current_circuit->gates[0].in2 == 3 && current_circuit->gates[0].in3 == 4){ + // printf("test\n"); + //} + + int tautology = detect_tautology(current_circuit,in1,in2,in3,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; + int8_t output[NUM_OUTPUTS]; + for (int y=0; y < (1 << data->num_inputs); y++){ //CHECK IF IT IS VALID + evaluate_circuit(data->gate_types, current_circuit, &data->truth_table[y*data->num_inputs], output); + for(int z=0; ztarget_outputs[y+NUM_COMBINATION*z]){ + valid = 0; + } + } + } + } + //valid circuit add area + current_circuit->area += gate_types[i].area; // Example area increment (modify as needed) + + if(data->num_circuit[0]%1000000000 == 0){ + data->num_circuit[1] += 1; + data->num_circuit[0] = 0; + printf("%d:At circuit number %d M current best_area %d and tested area %d\n",data->worker_id,data->num_circuit[1],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("%d: Found proper solution\n",data->worker_id); + print_circuit(current_circuit); + write_circuit_to_file(current_circuit,current_circuit->area,data->worker_id,data->num_circuit[0]*100 + data->num_circuit[1]); + 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("%d: best Area %d, Going 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, 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]); + } + + clock_t begin = clock(); + 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 + } + + clock_t toc = clock(); + printf("%f: running number of threads: %d\n",(double)(toc - begin) / (CLOCKS_PER_SEC*number_of_running_threads),number_of_running_threads); + sleep(5); + } + 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 + int8_t target_outputs[NUM_COMBINATION*NUM_OUTPUTS]; // 1< -#include -#include -#include -#include - -// -------------- config - -#define MAX_AREA 100000000 -#define NUM_THREADS 1 //Needs to be <= 9 or 18 or 27 for efficient splitting the work load -#define NUM_INPUTS 2 -#define MAX_GATES 5 - - -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; - int S1; - int S2; -} Gate; - -typedef struct { - Gate gates[MAX_GATES]; - int gate_count; - int area; -} Circuit; - -typedef struct { - Circuit best_circuit; - GateType *gate_types; - int num_inputs; - int num_gates; - int best_area; - int *truth_table; - int *target_outputs; - int worker_id; -} ThreadArgs; - -// -------------- define used gates - -GateType gate_types[] = { - {"MUXXOR", 4632}, -}; - -// -------------- start functions - -int evaluate_circuit(GateType* all_gates, Circuit* circuit, int* inputs) { - int intermediate_outputs[2 + NUM_INPUTS + MAX_GATES]; - memcpy(intermediate_outputs, inputs, NUM_INPUTS * sizeof(int)); - - 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 S1 = intermediate_outputs[circuit->gates[i].S1]; - int S2 = intermediate_outputs[circuit->gates[i].S2];; - int output = 0; - - if(out1 == out2){ - output = S1; - } else { - output = S2; - } - - intermediate_outputs[2 + NUM_INPUTS + i] = output; - } - return intermediate_outputs[2 + NUM_INPUTS + circuit->gate_count - 1]; -} - -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 - //0 - 2, 3 - 5, 6 - 8 - // ----------------- Going for multi processor approach - - for (int in1 = 0; in1 < 2 + depth + data->num_inputs; in1++) { - for (int in2 = in1; in2 < 2 + depth + data->num_inputs; in2++) { - for (int S1 = 0; S1 < 2 + depth + data->num_inputs; S1++){ - for(int S2 = 0; S2 < 2 + depth data->num_inputs; S2++){ - if(S1==S2) - continue; - - current_circuit->gates[depth].gate = &gate_types[0]; //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; - } - } - // Add the new gate to the circuit - - - 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(valid == 1 && current_circuit->areabest_area){ - //Found a valid solution! - memcpy(&data->best_circuit, current_circuit, sizeof(Circuit)); //write to best circuit - printf("Found proper solution\n"); - 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; - } - // 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) - } - } - } -} - -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; - int best_area = data->best_area; - - 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); - 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) { - pthread_t threads[NUM_THREADS]; - ThreadArgs thread_args[NUM_THREADS]; // Define `ThreadArgs` to pass data to threads - int best_area = max_area; - - - - 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; - pthread_create(&threads[i], NULL, search_space_worker, (void *)&thread_args[i]); - } - - for (int i = 0; i < NUM_THREADS; i++) { - pthread_join(threads[i], NULL); - // Collect best circuits and area from each thread - } - - for (int i = 0; i< NUM_THREADS; i++) { - if(thread_args[i].best_area> 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<type,best_circuit.gates[y].in1,best_circuit.gates[y].in2); - } - // Print best circuit details - return 0; -} -