// How to compile it: // gcc -o ga_find_wcet ga_find_wcet.c -lm // How to use it: // ./ga_find_wcet myconf ./bubblesort // where // bubblesort is the program for which we want to find the WCET. // myconfig is a textfile with configuration parameters. // Right now, the file myconfig stores the following parameters: // 0 // 262144 // The first parmeter (0) indicates the mode; it indicates that we want to find the WCET for a program using default hyperparameters (population size, multation rate). // The second parmeter (262144) indicates the input size to the program we want to execute. // It assumes that bubblesort reads from stdin. // The first parameter can be a number in {0,1,2,3}. 0 means normal GA. 1 means steepest descent. 2 means meta with GA. 3 means meta with steepest descent. #include #include #include #include #include #include #include #include #include int NUMBER_OF_BURNIN_INDIVIDUALS_DISCARDED = 4; int NUMBER_OF_INDIVIDUALS = 4; // this is the size of the population double MUTATIONRATE = 0.2; // this is the probability that an individual gets a mutation; if so, one bit is flipped int NGENERATIONS = 4; // this is the number of iterations that the population evolves char conffilename[200]; int mode = 0; int inputsizeinnumberofbits; // this must be a multiple of sizeof(int) struct individual { int* inputtoprogram; // this stores an array of bits but it is encoded as an array of int // for example 262144 bits equals 8192 words if one word is 32 bit double measuredexecutiontimeofprogram; // in seconds struct individual* next; }; struct individual* listof_individuals; FILE* mylogfile; int getinputtoprogram_size_in_number_of_bits() { return inputsizeinnumberofbits; } int getinputtoprogram_size_in_number_of_bytes() { return inputsizeinnumberofbits/8; } int getinputtoprogram_size_in_number_of_ints() { return inputsizeinnumberofbits/(sizeof(int)*8); } int obtain_intindex_from_bitindex(int bitindex) { int intindex; intindex = bitindex / ((sizeof(int))*8); return intindex; } int obtain_localbitindex_from_bitindex(int bitindex) { int localbitindex; localbitindex = bitindex % ((sizeof(int))*8); return localbitindex; } void flipbit_bitposition_in_integer(int* p_anint, int localbitindex) { int mask; mask = 1 << localbitindex; (*p_anint) = (*p_anint) ^ mask; } int isbitonein_bitposition_in_integer(int anint, int localbitindex) { int mask; int temp; mask = 1 << localbitindex; temp = anint & mask; if (temp==0) { return 0; } else { return 1; } } void setbitonein_bitposition_in_integer(int* p_anint, int localbitindex) { int mask; int temp; mask = 1 << localbitindex; (*p_anint) = (*p_anint) | mask; } void fill_int_array_with_random_bits(int* inputtoprogram) { int n; int i; int localbitindex; n = getinputtoprogram_size_in_number_of_ints(); for (i=0;inext; free( p->inputtoprogram); free( p); } else { p = listof_individuals; oldp = p; p = p->next; while ((p!=NULL) && (p!=p_anindividual_that_we_want_to_delete)) { oldp = p; p = p->next; } if (p==NULL) { printf("This is an error. We tried to delete an individual that does not exist.\n"); exit(-1); } // now, we know that p==p_anindividual_that_we_want_to_delete oldp->next = p->next; free( p->inputtoprogram); free( p); } } unsigned long long diff_ns_timespec(struct timespec *x, struct timespec *y) { unsigned long long abillion = 1000000000; unsigned long long u; u = x->tv_sec; u = u * abillion; u = u + x->tv_nsec; unsigned long long v; v = y->tv_sec; v = v * abillion; v = v + y->tv_nsec; return u-v; } double diff_s_timespec (struct timespec *x, struct timespec *y) { unsigned long long abillion = 1000000000; unsigned long long t; unsigned long long tsec; unsigned long long tnsec; double t_as_double_secondpart; double t_as_double_usecondpart; double t_as_double; t = diff_ns_timespec( x, y); tsec = t / abillion; tnsec = t % abillion; t_as_double_secondpart = tsec; t_as_double_usecondpart = tnsec; t_as_double_usecondpart = t_as_double_usecondpart / abillion; t_as_double = t_as_double_secondpart + t_as_double_usecondpart; return t_as_double; } double run_program_with_input(int* inputtoprogram, char* commandtorun) { struct timespec mybegin; struct timespec myend; int status_clock_gettime_begin; int status_clock_gettime_end; int fd; int countwritten; double t; fd = open("inputfile.dat", O_RDWR | O_CREAT, S_IRUSR | S_IWUSR ); if (fd==-1) { printf("Error when opening file\n"); exit(-1); } countwritten = write( fd, inputtoprogram, getinputtoprogram_size_in_number_of_bytes() ); if (countwritten==0) { printf("Error when writing to file\n"); exit(-1); } close(fd); status_clock_gettime_begin = clock_gettime(CLOCK_MONOTONIC_RAW, &mybegin); system(commandtorun); status_clock_gettime_end = clock_gettime(CLOCK_MONOTONIC_RAW, &myend); t = diff_s_timespec(&myend, &mybegin); return t; } int create_individual_and_insert_as_head(int* giveninputtoprogram, char* commandtorun) { struct individual* p_anindividual; if (giveninputtoprogram==NULL) { giveninputtoprogram = malloc(getinputtoprogram_size_in_number_of_bytes()); fill_int_array_with_random_bits(giveninputtoprogram); } p_anindividual = malloc(sizeof(struct individual)); p_anindividual->inputtoprogram = giveninputtoprogram; p_anindividual->measuredexecutiontimeofprogram = run_program_with_input(p_anindividual->inputtoprogram,commandtorun); p_anindividual->next = listof_individuals; listof_individuals = p_anindividual; } void fill_listof_individuals(int n, char* commandtorun) { int i; listof_individuals = NULL; for (i=0;imeasuredexecutiontimeofprogram < p->measuredexecutiontimeofprogram) { largestexecindividual = p; } } p = p->next; } if (largestexecindividual==NULL) { printf("There was an error. There is no individual with largest execution time.\n"); } *q = largestexecindividual; } void findindividualwithsmallestmeasuredexecutiontimeofprogram(struct individual** q) { struct individual* p; struct individual* smallestexecindividual; p = listof_individuals; smallestexecindividual = NULL; while (p!=NULL) { if (smallestexecindividual==NULL) { smallestexecindividual = p; } else { if (smallestexecindividual->measuredexecutiontimeofprogram > p->measuredexecutiontimeofprogram) { smallestexecindividual = p; } } p = p->next; } if (smallestexecindividual==NULL) { printf("There was an error. There is no individual with smallest execution time.\n"); } *q = smallestexecindividual; } double getmaximumexecutiontimeofindividuals() { struct individual* p_foundindividual; findindividualwithlargestmeasuredexecutiontimeofprogram(&p_foundindividual); return p_foundindividual->measuredexecutiontimeofprogram; } void do_mutations_on_inputtoprogram(int* inputtoprogram) { int bitindex; int intindex; int localbitindex; bitindex = rand()%inputsizeinnumberofbits; intindex = obtain_intindex_from_bitindex(bitindex); localbitindex = obtain_localbitindex_from_bitindex(bitindex); flipbit_bitposition_in_integer( &(inputtoprogram[intindex]), localbitindex); } void copy_inputtoprogram(int* inputtoprogram_destination, int* inputtoprogram_source) { int i; int n; n = getinputtoprogram_size_in_number_of_ints(); for (i=0;iinputtoprogram); create_individual_and_insert_as_head(giveninputtoprogram, commandtorun); } p = p->next; } } void do_steepest_descent(char* commandtorun) { struct individual* p; int bitindex; int intindex; int localbitindex; double new_measuredexecutiontimeofprogram; p = listof_individuals; while (p!=NULL) { bitindex = rand()%inputsizeinnumberofbits; intindex = obtain_intindex_from_bitindex(bitindex); localbitindex = obtain_localbitindex_from_bitindex(bitindex); flipbit_bitposition_in_integer( &((p->inputtoprogram)[intindex]), localbitindex); new_measuredexecutiontimeofprogram = run_program_with_input(p->inputtoprogram, commandtorun); if ((p->measuredexecutiontimeofprogram)measuredexecutiontimeofprogram) = new_measuredexecutiontimeofprogram; } else { flipbit_bitposition_in_integer( &((p->inputtoprogram)[intindex]), localbitindex); } p = p->next; } } void get_statistics_about_population(int* p_n,double* p_averageexecutiontime, double* p_minexecutiontime, double* p_maxexecutiontime) { struct individual* p; int n; double sum; double minexecutiontime; double maxexecutiontime; if (listof_individuals==NULL) { printf("An error has occured in get_statistics_about_population. There are no elements in list.\n"); exit(-1); } p = listof_individuals; n = 1; sum = p->measuredexecutiontimeofprogram; minexecutiontime = p->measuredexecutiontimeofprogram; maxexecutiontime = p->measuredexecutiontimeofprogram; p = p->next; while (p!=NULL) { n = n + 1; sum = sum + p->measuredexecutiontimeofprogram; if (p->measuredexecutiontimeofprogrammeasuredexecutiontimeofprogram; } if (p->measuredexecutiontimeofprogram>maxexecutiontime) { maxexecutiontime = p->measuredexecutiontimeofprogram; } p = p->next; } *p_n = n; *p_averageexecutiontime = sum/n; *p_minexecutiontime = minexecutiontime; *p_maxexecutiontime = maxexecutiontime; } int get_numberof_individuals_with_executiontime_greaterthan_or_equal_to(double THR) { struct individual* p; int count; p = listof_individuals; count = 0; while (p!=NULL) { if (p->measuredexecutiontimeofprogram>=THR) { count++; } p = p->next; } return count; } struct individual* identify_individual_with_executiontime_greaterthan_or_equal_to(double THR,int orderamongselection) { struct individual* p; int count; p = listof_individuals; count = 0; while (p!=NULL) { if (p->measuredexecutiontimeofprogram>=THR) { if (count==orderamongselection) { return p; } else { count++; } } p = p->next; } printf("An error has occured in identify_individual_with_executiontime_greaterthan_or_equal_to. Count not find element.\n"); exit(-1); } struct individual* get_an_individual_with_executiontime_greaterthan_or_equal_to(double THR) { struct individual* p; int count; int orderamongselection; count = get_numberof_individuals_with_executiontime_greaterthan_or_equal_to(THR); orderamongselection = random()%count; p = identify_individual_with_executiontime_greaterthan_or_equal_to(THR,orderamongselection); return p; } void create_new_stringthroughcrossover(int* giveninputtoprogram_destination,int* inputtoprogram_source1,int* inputtoprogram_source2) { int bitindex; int intindex; int localbitindex; int i; bitindex = rand()%getinputtoprogram_size_in_number_of_bits(); intindex = obtain_intindex_from_bitindex(bitindex); localbitindex = obtain_localbitindex_from_bitindex(bitindex); for (i=0;iinputtoprogram,p2->inputtoprogram); create_individual_and_insert_as_head(giveninputtoprogram, commandtorun); } } void do_crossover(char* commandtorun) { create_new_individuals_by_doing_crossover(NUMBER_OF_INDIVIDUALS,1,1, commandtorun); create_new_individuals_by_doing_crossover(NUMBER_OF_INDIVIDUALS,1,0, commandtorun); create_new_individuals_by_doing_crossover(NUMBER_OF_INDIVIDUALS,0,1, commandtorun); create_new_individuals_by_doing_crossover(NUMBER_OF_INDIVIDUALS,0,0, commandtorun); } void delete_individual_with_lowest_measuredexecutiontimeofprogram() { struct individual* individual_with_smallest_executiontime; findindividualwithsmallestmeasuredexecutiontimeofprogram(&individual_with_smallest_executiontime); delete_individual_and_deallocate_memory(individual_with_smallest_executiontime); } void trim_population(int n_targetpopulationsize) { int n; double averageexecutiontime; double minexecutiontime; double maxexecutiontime; get_statistics_about_population(&n,&averageexecutiontime,&minexecutiontime,&maxexecutiontime); while (n>n_targetpopulationsize) { delete_individual_with_lowest_measuredexecutiontimeofprogram(); n = n - 1; } } void delete_all_individuals() { trim_population(0); listof_individuals = NULL; } void readfromconffilename(char* conffilename) { FILE* f; int temp; f = fopen(conffilename, "r"); fscanf(f,"%d", &mode); fscanf(f,"%d", &inputsizeinnumberofbits); fclose(f); } void print_to_log_generation(int generationindex) { int n; double averageexecutiontime; double minexecutiontime; double maxexecutiontime; get_statistics_about_population(&n,&averageexecutiontime,&minexecutiontime,&maxexecutiontime); fprintf(mylogfile,"Generation %d. n=%d avg=%lf min=%lf max=%lf\n", generationindex, n, averageexecutiontime, minexecutiontime, maxexecutiontime); fflush(mylogfile); } void print_to_log_end(int generationindex) { int n; double averageexecutiontime; double minexecutiontime; double maxexecutiontime; get_statistics_about_population(&n,&averageexecutiontime,&minexecutiontime,&maxexecutiontime); fprintf(mylogfile,"End. n=%d avg=%lf min=%lf max=%lf\n", n, averageexecutiontime, minexecutiontime, maxexecutiontime); fflush(mylogfile); } void get_command_to_run(int argc, char* argv[], char* commandtorun) { sprintf(commandtorun,"%s < %s", argv[2], "inputfile.dat"); } void printallexecutiontimes() { struct individual* p; p = listof_individuals; while (p!=NULL) { printf("executiontime: %lf\n", p->measuredexecutiontimeofprogram ); p = p->next; } } void printworstcase(char* fn_inputfile,char* fn_measuredexecutiontime) { int fd; int countwritten; FILE* f; struct individual* individual_with_largest_executiontime; findindividualwithlargestmeasuredexecutiontimeofprogram(&individual_with_largest_executiontime); fd = open(fn_inputfile, O_RDWR | O_CREAT, S_IRUSR | S_IWUSR ); if (fd==-1) { printf("Error when opening file\n"); exit(-1); } countwritten = write( fd, individual_with_largest_executiontime->inputtoprogram, getinputtoprogram_size_in_number_of_bytes() ); if (countwritten==0) { printf("Error when writing to file\n"); exit(-1); } close(fd); f = fopen(fn_measuredexecutiontime, "w+"); fprintf(f,"%lf", individual_with_largest_executiontime->measuredexecutiontimeofprogram); fclose(f); } void produce_results_GA(char* commandtorun) { char fn_inputfile[200]; char fn_measuredexecutiontime[200]; int generationindex; fill_listof_individuals(NUMBER_OF_INDIVIDUALS, commandtorun); for (generationindex=0;generationindex=4) { printf("You gave too many parameters.\n"); exit(-1); } sscanf(argv[1],"%s",conffilename); readfromconffilename(conffilename); get_command_to_run(argc, argv, commandtorun); srand(137); srand48(137.0); if (mode==0) { produce_results_GA(commandtorun); } else { if (mode==1) { produce_results_steepest_descent(commandtorun); } else { if (mode==2) { produce_results_GA_metamode(commandtorun); } else { if (mode==3) { produce_results_steepest_descent_metamode(commandtorun); } else { printf("Not yet implemented\n"); exit(-1); } } } } closelog(); return 0; } // Below, we present the following: // 1. Source code for bubblesort. We have used it to test our WCET analysis tool // 2. Source code for quicksort. We have used it to test our WCET analysis tool // 3. Source code for generate_ascending_integers.c We have used it to test bubblesort and quicksort // 4. Source code for generate_descending_integers.c We have used it to test bubblesort and quicksort // 5. Experimental results for ascending and descending with bubblesort // 6. Experimental results for ascending and descending with quicksort // 7. Miscellaneous experiments // 8. Experimental results for mode 2 with bubblesort // 9. Experimental results for mode 3 with bubblesort // 10. Experimental results for mode 2 with quicksort // 11. Experimental results for mode 3 with quicksort // // ******************** 1. Source code for bubblesort ******************** // // how to compile it // gcc -o bubblesort bubblesort.c // #include // #include // #include // #include // #include // #include // #include // // #define ARSIZE 8192 // // int ar[ARSIZE]; // // void swap(int* p1, int *p2) { // int temp; // temp = *p1; // *p1 = *p2; // *p2 = temp; // } // // void bubblesort() { // int n; int i; int swapped; // n = ARSIZE; // do { // swapped = 0; // for (i=1;i<=n-1;i++) { // if (ar[i-1] > ar[i]) { // swap( &(ar[i-1]), &(ar[i]) ); // swapped = 1; // } // } // } while (swapped); // } // // int main(int argc, char *argv[]) { // int countread; // if (argc!=1) { printf("Incorrect number of arguments. argc=%d argv[0]=%s argv[1]=%s\n", argc, argv[0], argv[1]); exit(-1); } // countread = read( STDIN_FILENO, ar, ARSIZE*sizeof(int) ); // if (countread==0) { printf("Error when reading file\n"); exit(-1); } // bubblesort(); // return 0; // } // // // ******************** 2. Source code for quicksort ******************** // // how to compile it // gcc -o quicksort quicksort.c // // #include // #include // #include // #include // #include // #include // #include // // #define ARSIZE 8192 // // int ar[ARSIZE]; // // void quicksort(int first, int last) { // int i; int j; int pivot; int temp; // if (firstar[pivot]) { // j--; // } // if(i // #include // #include // #include // #include // #include // #include // // #define ARSIZE 8192 // // int ar[ARSIZE]; // // int main(int argc, char *argv[]) { // int i; int fd; int countwritten; // for (i=0;i // #include // #include // #include // #include // #include // #include // // #define ARSIZE 8192 // // int ar[ARSIZE]; // // int main(int argc, char *argv[]) { // int i; int fd; int countwritten; // for (i=0;i