diff --git a/bruteforce_approach/bruteforce_multiple_outputs.c b/bruteforce_approach/bruteforce_conventional_gates.c similarity index 99% rename from bruteforce_approach/bruteforce_multiple_outputs.c rename to bruteforce_approach/bruteforce_conventional_gates.c index 9493a99..abd3cc7 100644 --- a/bruteforce_approach/bruteforce_multiple_outputs.c +++ b/bruteforce_approach/bruteforce_conventional_gates.c @@ -1,472 +1,472 @@ #include #include #include #include #include #include #include #include // -------------- config #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 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] ^ 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; 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); 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"); + fprintf(fptr, "digraph Circuit {\n rankdir=LR; // Makes the graph left-to-right\n node [shape=ellipse]; // Default shape for nodes\n ranksep=2; // Increases vertical separation\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; } 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) || //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 - NUM_OUTPUTS);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 = 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; 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 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 #include #include // -------------- config -#define MAX_AREA 15000 //Determine the initial max_area +#define MAX_AREA 10000 //Determine the initial max_area #define NUM_INPUTS 3 //speaks for itself -#define MAX_GATES 10 // determine the max_amount of gates +#define MAX_GATES 6 // 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. +//#define target_truth_table "11101000" //exampe here [Target A][Target B] pasted after another. +//MAJ testing +#define target_truth_table "1110100010010110" +//half adder /* 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; + int8_t in4; } 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} + {"MUX-XOR", 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,"---------- 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'; + int print_in4 = circuit->gates[y].in4 + '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'; } + if((print_in4-2-'0')=0){ + print_in4 = circuit->gates[y].in4-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,"%d: %s, in1: %c, in2: %c, in3: %c, in4: %c\n",y+NUM_INPUTS+2,circuit->gates[y].gate->type,print_in1,print_in2,print_in3,print_in4); } tee(fptr,"Output "); for(int i='x';(i-'x')gate_count-NUM_OUTPUTS+(i-'x')+2);} tee(fptr,"\n"); - 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"); + fprintf(fptr, "digraph Circuit {\n rankdir=LR; // Makes the graph left-to-right\n node [shape=ellipse]; // Default shape for nodes\n ranksep=2; // Increases vertical separation\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'; + int print_in4 = circuit->gates[y].in4 + '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'; } + if((print_in4-2-'0')=0){ + print_in4 = circuit->gates[y].in4-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); + fprintf(fptr," %d [ shape=record, label=\"{{ ==| XOR 0| XOR 1| !=}| MUX-XOR %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 %c:e -> %d:p4;\n",print_in1,unit_number,print_in2,unit_number,print_in3,unit_number,print_in4,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 out4 = intermediate_outputs[circuit->gates[i].in4]; 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; + else if (circuit->gates[i].gate == &all_gates[1]) //MUX-XOR + output = (out4^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. +int detect_tautology(Circuit *current_circuit, int in1, int in2, int in3, int in4, int gate_selected, ThreadArgs *data){ + if ((in1 == in2 && gate_selected != 0) || + //(in1 == in3 || in2 == in3) || + (in3 == in4)){ + //(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; + input_used[in4] = 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++){ + for (int in4 = 0; in4 < depth + data->num_inputs + 2; in4++){ + for (int in3 = 0; in3 < depth + data->num_inputs + 2; in3++){ - //Going for multithread approach - if(in3 != data->worker_id+2 && depth == 0){ - continue; - } + //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; + 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; + // 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->gates[depth].in4 = in4; + 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"); - //} + //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 tautology = detect_tautology(current_circuit,in1,in2,in3,in4,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; + 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; + 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); - } + //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_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); } - 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 #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 MAX_GATES 6 // 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. +#define target_truth_table "11101000" //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"); + fprintf(fptr, "digraph Circuit {\n rankdir=LR; // Makes the graph left-to-right\n node [shape=ellipse]; // Default shape for nodes\n ranksep=2; // Increases vertical separation\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) || + if ((in1 == in2 && gate_selected != 0) || + (in1 == in3 || in2 == in3) || (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< "./temp/${yosys_file}_temp.ys" yosys $additional_yosys_args "./temp/${yosys_file}_temp.ys" } #Switch between 3T and 4T pass through gates switch_liberty() { if [ "$LIBERTY_FILE" == "nem_basic_yosys.lib" ]; then LIBERTY_FILE="nem_basic_yosys_extended.lib" LIBERTY_USED="4T" echo "Now using extended (4T devices) libary" elif [ "$LIBERTY_FILE" == "nem_basic_yosys_extended.lib" ]; then LIBERTY_FILE="nem_basic_yosys.lib" LIBERTY_USED="3T" echo "Now using normal libary" else echo "Unknown LIBERTY_FILE value: $LIBERTY_FILE" fi } compare_area() { # Extract area values from .stat files local area_3T=$(grep "Chip area for module" "./temp/${FILE_BASENAME}_3T.stat" | awk '{print $6}') local area_4T=$(grep "Chip area for module" "./temp/${FILE_BASENAME}_4T.stat" | awk '{print $6}') local area_MUX=$(grep "Chip area for module" "./temp/${FILE_BASENAME}_MUX.stat" | awk '{print $6}') # Calculate ratio as (area_3T / area_4T) * 100 local ratio_4T=$(echo "($area_4T / $area_3T)" | bc -l) local ratio_MUX=$(echo "($area_MUX / $area_3T)" | bc -l) { echo "------------- normal 3T ---------------" cat "./temp/${FILE_BASENAME}_3T.stat" echo "------------- 4T ---------------" cat "./temp/${FILE_BASENAME}_4T.stat" echo "------------- Muxig ---------------" cat "./temp/${FILE_BASENAME}_MUX.stat" echo "------------- Stats ---------------" echo "Area 3T: $area_3T" echo "Area 4T: $area_4T" echo "Ratio 4T->3T: $ratio_4T%" echo "Area MUX: $area_MUX" echo "Ratio MUX->3T: $ratio_MUX%" ec } > "./output/${FILE_BASENAME}.ratio" # Output the areas and the ratio echo "Area 3T: $area_3T, Area 4T: $area_4T, Ratio 4T->3T: $ratio_4T, Area MUX: $area_MUX, Ratio MUX->3T: $ratio_MUX%" } create_report() { # Output CSV file name csv_output="./output/output_report.csv" # Clear the CSV file by redirecting an empty string to it > "$csv_output" # Write the CSV header echo "Module,3T,4T,Ratio" > "$csv_output" # Print the header of the table printf "%-20s %-20s %-20s %-20s %-20s %-20s\n" "Module" "3T" "4T" "Ratio 4T" "MUX" "Ratio MUx" printf "%-20s %-20s %-20s %-20s %-20s %-20s\n" "-------" "------" "------" "-----" "-----" "-----" # Loop through each .ratio file in the directory for file in ./output/*.ratio; do # Check if the file exists if [[ -f "$file" ]]; then # Extract the module name module_name=$(grep -m 1 -oP '(?<==== ).*(?= ===)' "$file") # Extract the module name # Extract areas using grep and sed area1=$(grep "Chip area for module" "$file" | sed -n '1s/.*: //p') # Area 3T area2=$(grep "Chip area for module" "$file" | sed -n '2s/.*: //p') # Area 4T area3=$(grep "Chip area for module" "$file" | sed -n '3s/.*: //p') # Area MUX # Extract the ratio ratio_4T=$(grep -oP '(?<=Ratio 4T->3T: )[\d.]+' "$file") # Extract the ratio ratio_MUX=$(grep -oP '(?<=Ratio MUX->3T: )[\d.]+' "$file") # Extract the ratio # Append the data to the CSV file echo "$module_name,$area1,$area2,$ratio_4T,$area3,$ratio_MUX" >> "$csv_output" # Print the results in the table format printf "%-20s %-20s %-20s %-20s\n" "$module_name" "$area1" "$area2" "$ratio" fi done } #START ACTUAL EXECUTION #Check if in menu mode or in CLI mode if [ -z "$1" ]; then # in menu mode request_data else #in cli mode. Filter through all the parameters while getopts ":d:f:m:v:x:r:" opt; do case $opt in d) # -d option for directory file_directory="$OPTARG" ;; f) # -f option for file FILE="$OPTARG" ;; m) # -m option for module (requires -f to be set) MODULE="$OPTARG" ;; v) # -v visualize before and after synthesis echo "found visualize" visualize=1 ;; x) # -x switch to extended nem liberty file echo "switching to 4T libert file" switch_liberty ;; r) # -r generate report of output echo "generating report" create_report ;; \?) # Invalid option echo "Invalid option: -$OPTARG" >&2 usage ;; :) # Missing argument for an option echo "Option -$OPTARG requires an argument." >&2 usage ;; esac done #running synthesis on al lthe files in the directory if [ -n "$file_directory" ]; then if [ -d "$file_directory" ]; then echo "Directory exists: $file_directory" for file in "$file_directory"/*.v; do # Check if it's a regular file if [ -f "$file" ]; then # Use grep to find the line that starts with 'module' and extract the module name module_name=$(grep -m 1 -oP '^module\s+\K\w+' "$file") # If the module name is found, print the file path and the module name if [ -n "$module_name" ]; then echo "File: $file" echo "Module: $module_name" echo FILE=$file FILE_BASENAME=$(basename "$FILE" | cut -d. -f1) MODULE=$module_name #synthesise the file echo "running sequence of test commands" run_yosys_file "synth_nem" 0 #run_yosys_file "sat_test" 0 switch_liberty run_yosys_file "synth_nem" 0 #run_yosys_file "sat_test" 0 run_yosys_file "bruteforce" 0 compare_area switch_liberty else echo "No module found in file: $file" echo fi fi done #done with synthesis create_report exit 0 else echo "Directory does not exist: $file_directory" exit 1 fi fi #running synthesis on the file requested if [ -n "$FILE" ]; then if [ -n "$MODULE" ]; then if [ -f "$FILE" ]; then echo "File exists: $file" echo "Module: $module" FILE_BASENAME=$(basename "$FILE" | cut -d. -f1) run_yosys_file "synth_nem" 0 if [ "$visualize" -eq 1 ]; then run_yosys_file "visual" 0 run_yosys_file "visual" 1 else echo "no visualize set" fi exit 0 else echo "File does not exist: $file" exit 1 fi else echo "Missing module (-m) for the file (-f)." usage fi fi exit 1 fi # Loop to allow multiple selections while true; do show_menu read -p "Enter your choices (e.g., 1 2 3, or 0 to finish): " -a choices for choice in "${choices[@]}"; do case $choice in 1) echo "performing synthesis" run_yosys_file "synth_nem" 0 ;; 2) echo "Plotting the initial design with $FILE and $MODULE" run_yosys_file "visual" 0 ;; 3) echo "Plotting the NEM design with $FILE and $MODULE" run_yosys_file "visual" 1 ;; 4) echo "Performing SAT test on $FILE and $MODULE" run_yosys_file "sat_test" 0 ;; 5) echo "Exporting FSM overview of the design" make clean #to make sure no previous .kiss2 file remains run_yosys_file "fsm_export" 0 if [ -f "./temp/${FILE_BASENAME}.kiss2" ]; then # If the file exists, run the python script and xdot python3 ./yosys/kiss2dot.py ./temp/${FILE_BASENAME}.kiss2 > ./temp/${FILE_BASENAME}.dot xdot ./temp/${FILE_BASENAME}.dot else # If the file doesn't exist, print a message echo "Could not detect an FSM in ${MODULE}" fi ;; 6) echo "Plotting the initial design with $FILE and $MODULE" make clean #Clean directories run_yosys_file "synth_nem" 0 make all #build plugins ls ./plugins/*.so run_yosys_file "start_shell" 0 "$(for so_file in ./plugins/*.so; do echo -m "$so_file"; done)" #create a list of all plugins to load ;; 7) echo "Switching libary" switch_liberty ;; 8) echo "running sequence of test commands" run_yosys_file "synth_nem" 0 #run_yosys_file "visual" 1 switch_liberty run_yosys_file "synth_nem" 0 #run_yosys_file "visual" 1 run_yosys_file "bruteforce" 0 compare_area ;; 9) - echo "Exporting PLA file for bruteforce" + echo "exporting truth table and running in mockturtle for muxig" run_yosys_file "bruteforce" 0 ;; 10) + echo "exporting truth table and running in mockturtle for MIG" + run_yosys_file "bruteforce" 1 + ;; + 11) echo "requesting new module" request_data ;; 0) echo "exiting" break 2 ;; *) echo "Invalid choice. Please select a number between 1 and 6." ;; esac done echo done diff --git a/sources/test_set/adder1.v b/sources/test_set/adder1.v index b9ecf31..017b922 100644 --- a/sources/test_set/adder1.v +++ b/sources/test_set/adder1.v @@ -1,12 +1,12 @@ module adder1 (A, B, Ci, S, Co); input A; input B; input Ci; output S; output Co; wire[1:0] Sum5; assign Sum5 = A + B + Ci ; -assign S = Sum5[0] ; -assign Co = Sum5[1] ; +assign S = Sum5[0]; +assign Co = Sum5[1]; endmodule diff --git a/sources/test_set/maj.v b/sources/test_set/maj.v new file mode 100644 index 0000000..aa96566 --- /dev/null +++ b/sources/test_set/maj.v @@ -0,0 +1,6 @@ +module maj ( + input A, B, C, + output M +); + assign M = (A & B) | (A & C) | (B & C); +endmodule diff --git a/sources/test_set/multiplier1.v b/sources/test_set/multiplier1.v new file mode 100644 index 0000000..8a06ad5 --- /dev/null +++ b/sources/test_set/multiplier1.v @@ -0,0 +1,11 @@ +module multiplier1 #(parameter BITWIDTH = 1) (A, B, P); + + // Input and Output Declarations + input [BITWIDTH-1:0] A; // A is an input of size BITWIDTH + input [BITWIDTH-1:0] B; // B is an input of size BITWIDTH + output [2*BITWIDTH-1:0] P; // P is an output of size 2*BITWIDTH + + // Multiply A and B + assign P = A * B; // Calculate the product + +endmodule \ No newline at end of file diff --git a/sources/test_set/redundancy_check.v b/sources/test_set/redundancy_check.v new file mode 100644 index 0000000..476a96f --- /dev/null +++ b/sources/test_set/redundancy_check.v @@ -0,0 +1,9 @@ +module redundancy_check ( + input A, B, C, D, + output F +); + wire O, R; + assign O = A | B | C | D; + assign R = (A & B) | (C & D); + assign F = O & R; +endmodule diff --git a/sources/test_set/xor_and.v b/sources/test_set/xor_and.v new file mode 100644 index 0000000..0a09ab0 --- /dev/null +++ b/sources/test_set/xor_and.v @@ -0,0 +1,8 @@ +module xor_and ( + input A, B, C, + output Y +); + wire X; + assign X = (A & ~B) | (~A & B); + assign Y = X & C; +endmodule diff --git a/sources/test_set/xor_test.v b/sources/test_set/xor_test.v index 8aabe35..5d30bfc 100644 --- a/sources/test_set/xor_test.v +++ b/sources/test_set/xor_test.v @@ -1,9 +1,11 @@ -module xor_test (A, B, S); +module xor_test (A, B, C, D, S); input A; input B; +input C; +input D; output S; -assign S = A^B; +assign S = A^B^C^D; endmodule diff --git a/yosys/bruteforce.ys b/yosys/bruteforce.ys index 5231a6c..3b34cd4 100644 --- a/yosys/bruteforce.ys +++ b/yosys/bruteforce.ys @@ -1,38 +1,44 @@ read_verilog {{FILE}} #map to basic cells techmap opt;; write_blif ./temp/{{FILE_BASENAME}}.blif -abc -liberty ./{{LIBERTY_FILE}} -script "+strash; &get -n; collapse; write_eqn ./temp/{{FILE_BASENAME}}.eqn;" + +abc -liberty ./{{LIBERTY_FILE}} -script "+strash; &get -n; collapse; write_eqn ./temp/{{FILE_BASENAME}}.eqn; &write_truths -x ./temp/{{FILE_BASENAME}}.truth" delete -exec -- ./mockturtle/build/experiments/muxig_rewriting ./temp/{{FILE_BASENAME}}.blif +#IF {{DEPTH}}==0 +exec -- ./mockturtle/build/experiments/muxig_rewriting ./temp/{{FILE_BASENAME}}.blif 1 +#ELSE +exec -- ./mockturtle/build/experiments/muxig_rewriting ./temp/{{FILE_BASENAME}}.blif 0 +#END + exec -- python3 ./yosys/map_ports.py ./temp/{{FILE_BASENAME}}.blif ./temp/{{FILE_BASENAME}}_mockturtle.blif read_blif ./temp/mapped_{{FILE_BASENAME}}_mockturtle.blif rename top {{MODULE}}_nem techmap -map ./yosys/mockturtle_map.v techmap opt_expr clean -purge abc -liberty {{LIBERTY_FILE}} -script "+attach" clean -purge write_verilog -selected ./temp/{{FILE_BASENAME}}_nem.v #Output stats tee -o ./temp/{{FILE_BASENAME}}_MUX.stat stat -liberty ./{{LIBERTY_FILE}}