bruteforce_muxxor.c
No OneTemporary
Actions

Size

7 KB

Referenced Files

None

Subscribers

None

bruteforce_muxxor.c
View Options

	#include <stdio.h>
	#include <stdlib.h>
	#include <pthread.h>
	#include <stdint.h>
	#include <string.h>

	// -------------- 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->area<data->best_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; y<current_circuit->gate_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(&current_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<best_area){
	best_area = thread_args[i].best_area;
	memcpy(best_circuit, &thread_args[i].best_circuit, sizeof(Circuit));
	}
	}

	// Output the best circuit
	}

	void fill_target_outputs(int truth_table[], int target_outputs[], int num_inputs) {
	int num_combinations = 1 << num_inputs;
	for (int i = 0; i < num_combinations; i++) {
	int inputs[num_inputs];
	for (int j = 0; j < num_inputs; j++) {
	inputs[j] = (i >> j) & 1; // Extract each bit of i as an input
	truth_table[i*num_inputs+j] = (i >> j) & 1;;
	}
	target_outputs[i] = target_function(inputs);
	}
	}



	int main() {
	// Define target function output
	int target_outputs[1 << NUM_INPUTS]; // 1<<NUM_INPUTS is equivalent to 2^NUM_INPUTS
	int truth_table[(1 << NUM_INPUTS)*NUM_INPUTS]; // create a truth_table the size of target_output with an entry for every input.
	fill_target_outputs(truth_table, target_outputs, NUM_INPUTS);

	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; y<best_circuit.gate_count; y++){
	printf("%d: %s, in1: %d, in2: %d\n",y,best_circuit.gates[y].gate->type,best_circuit.gates[y].in1,best_circuit.gates[y].in2);
	}
	// Print best circuit details
	return 0;
	}

File Metadata

Mime Type: text/x-c
Expires: Fri, Jul 4, 7:29 AM (1 h, 2 m)
Storage Engine: blob
Storage Format: Raw Data
Storage Handle: 157524
Default Alt Text: bruteforce_muxxor.c (7 KB)

bruteforce_muxxor.cNo OneTemporaryActions

bruteforce_muxxor.cView Options

File Metadata

Event Timeline

bruteforce_muxxor.c
No OneTemporary
Actions

bruteforce_muxxor.c
View Options