X-Git-Url: https://git.octo.it/?p=sort-networks.git;a=blobdiff_plain;f=src%2Fsn-evolution.c;h=9f63506a6992dc94fad4a9225c47baed4716fb2a;hp=9cf56f5c0fe2234a8521d716d9d5256790f2da68;hb=7113bfbc96eb65431bad9d9985ba04a18f4912cb;hpb=4776e53d773b8b4290f8a55726a4aa2e08e270d2 diff --git a/src/sn-evolution.c b/src/sn-evolution.c index 9cf56f5..9f63506 100644 --- a/src/sn-evolution.c +++ b/src/sn-evolution.c @@ -1,10 +1,39 @@ -#define _ISOC99_SOURCE -#define _POSIX_C_SOURCE 200112L +/** + * libsortnetwork - src/sn-evolution.c + * Copyright (C) 2008-2010 Florian octo Forster + * + * This program is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License as published by the + * Free Software Foundation; only version 2 of the License is applicable. + * + * This program is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; if not, write to the Free Software Foundation, Inc., + * 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + * + * Authors: + * Florian octo Forster + **/ + +#ifndef _ISOC99_SOURCE +# define _ISOC99_SOURCE +#endif +#ifndef _POSIX_C_SOURCE +# define _POSIX_C_SOURCE 200809L +#endif +#ifndef _XOPEN_SOURCE +# define _XOPEN_SOURCE 700 +#endif #include #include #include #include +#include #include #include @@ -14,15 +43,20 @@ #include #include +#include + +#include + #include "sn_network.h" -#include "sn_population.h" +#include "sn_random.h" -/* Yes, this is ugly, but the GNU libc doesn't export it with the above flags. - * */ -char *strdup (const char *s); +#if !defined(__GNUC__) || !__GNUC__ +# define __attribute__(x) /**/ +#endif static uint64_t iteration_counter = 0; static int inputs_num = 16; +static int inputs_num_is_power_of_two = 1; static char *initial_input_file = NULL; static char *best_output_file = NULL; @@ -30,40 +64,23 @@ static char *best_output_file = NULL; static int stats_interval = 0; static int max_population_size = 128; -static sn_population_t *population; - -static int do_loop = 0; +static population_t *population; -static void sigint_handler (int signal) +static enum { - do_loop++; -} /* void sigint_handler */ - -static int init_random (void) -{ - int fd; - unsigned int r; - - fd = open ("/dev/random", O_RDONLY); - if (fd < 0) - { - perror ("open"); - return (-1); - } - - read (fd, (void *) &r, sizeof (r)); - close (fd); + MERGER_ODDEVEN, + MERGER_BITONIC, + MERGER_RANDOM +} selected_merger = MERGER_ODDEVEN; - srand (r); +static int evolution_threads_num = 4; - return (0); -} /* int init_random */ +static int do_loop = 0; -static int bounded_random (int upper_bound) +static void sigint_handler (int signal __attribute__((unused))) { - double r = ((double) rand ()) / ((double) RAND_MAX); - return ((int) (r * upper_bound)); -} + do_loop++; +} /* void sigint_handler */ static void exit_usage (const char *name) { @@ -73,6 +90,10 @@ static void exit_usage (const char *name) " -i Initial input file (REQUIRED)\n" " -o Write the current best solution to \n" " -p Size of the population (default: 128)\n" + " -P Send individuals to (may be repeated)\n" + " -t Number of threads (default: 4)\n" + " -m Specify the merging network to use.\n" + " Available: \"oddeven\", \"bitonic\", \"random\"\n" "\n", name); exit (1); @@ -82,7 +103,7 @@ int read_options (int argc, char **argv) { int option; - while ((option = getopt (argc, argv, "i:o:p:P:s:h")) != -1) + while ((option = getopt (argc, argv, "i:o:p:P:s:t:m:h")) != -1) { switch (option) { @@ -106,7 +127,23 @@ int read_options (int argc, char **argv) { int tmp = atoi (optarg); if (tmp > 0) + { max_population_size = tmp; + population_set_size (population, (size_t) max_population_size); + } + break; + } + + case 'P': + { + int status; + + status = population_add_peer (population, optarg, /* port = */ NULL); + if (status != 0) + { + fprintf (stderr, "population_add_peer failed with status %i.\n", + status); + } break; } @@ -118,6 +155,27 @@ int read_options (int argc, char **argv) break; } + case 't': + { + int tmp = atoi (optarg); + if (tmp >= 1) + evolution_threads_num = tmp; + break; + } + + case 'm': + { + if (strcasecmp ("oddeven", optarg) == 0) + selected_merger = MERGER_ODDEVEN; + else if (strcasecmp ("bitonic", optarg) == 0) + selected_merger = MERGER_BITONIC; + else if (strcasecmp ("random", optarg) == 0) + selected_merger = MERGER_RANDOM; + else + fprintf (stderr, "Not a valid merging strategy: \"%s\"\n", optarg); + break; + } + case 'h': default: exit_usage (argv[0]); @@ -127,7 +185,6 @@ int read_options (int argc, char **argv) return (0); } /* int read_options */ -#if 0 static int rate_network (const sn_network_t *n) { int rate; @@ -142,93 +199,45 @@ static int rate_network (const sn_network_t *n) return (rate); } /* int rate_network */ -#endif #if 0 -static int population_print_stats (int iterations) +static int mutate_network (sn_network_t *n) { - int best = -1; - int total = 0; - int i; - - for (i = 0; i < population_size; i++) + sn_network_t *n_copy; + int stage_index; + sn_stage_t *s; + int comparator_index; + int status; + + n_copy = sn_network_clone (n); + if (n_copy == NULL) { - if ((best == -1) || (best > population[i].rating)) - best = population[i].rating; - total += population[i].rating; + fprintf (stderr, "mutate_network: sn_network_clone failed.\n"); + return (-1); } - printf ("Iterations: %6i; Best: %i; Average: %.2f;\n", - iterations, best, ((double) total) / ((double) population_size)); - - return (0); -} /* int population_print_stats */ -#endif - -#if 0 -static int insert_into_population (sn_network_t *n) -{ - int rating; - int worst_rating; - int worst_index; - int best_rating; - int nmemb; - int i; - - rating = rate_network (n); + stage_index = sn_bounded_random (0, SN_NETWORK_STAGE_NUM (n_copy) - 1); + s = SN_NETWORK_STAGE_GET (n_copy, stage_index); - if (population_size < max_population_size) - { - population[population_size].network = n; - population[population_size].rating = rating; - population_size++; - return (0); - } + comparator_index = sn_bounded_random (0, SN_STAGE_COMP_NUM (s) - 1); + sn_stage_comparator_remove (s, comparator_index); - worst_rating = -1; - worst_index = -1; - best_rating = -1; - for (i = 0; i < olymp_size; i++) - { - if (population[i].rating > worst_rating) - { - worst_rating = population[i].rating; - worst_index = i; - } - if ((population[i].rating < best_rating) - || (best_rating == -1)) - best_rating = population[i].rating; - } - - if (rating < best_rating) - { - if (best_output_file != NULL) - { - printf ("Writing network with rating %i to %s\n", - rating, best_output_file); - sn_network_write_file (n, best_output_file); - } - else - { - printf ("New best solution has rating %i\n", - rating); - } - } + status = sn_network_brute_force_check (n_copy); + + sn_network_destroy (n_copy); - nmemb = max_population_size - (worst_index + 1); - - sn_network_destroy (population[worst_index].network); - population[worst_index].network = NULL; - - memmove (population + worst_index, - population + (worst_index + 1), - nmemb * sizeof (population_entry_t)); + if (status < 0) + return (-1); + else if (status > 0) /* Mutated network does not sort anymore. */ + return (1); - population[max_population_size - 1].network = n; - population[max_population_size - 1].rating = rating; + /* We saved one comparator \o/ Let's do the same change on the original + * network. */ + s = SN_NETWORK_STAGE_GET (n, stage_index); + sn_stage_comparator_remove (s, comparator_index); return (0); -} /* int insert_into_population */ +} /* int mutate_network */ #endif static int create_offspring (void) @@ -237,14 +246,19 @@ static int create_offspring (void) sn_network_t *p1; sn_network_t *n; - p0 = sn_population_pop (population); - p1 = sn_population_pop (population); + p0 = population_get_random (population); + p1 = population_get_random (population); assert (p0 != NULL); assert (p1 != NULL); /* combine the two parents */ - n = sn_network_combine (p0, p1); + if ((selected_merger == MERGER_ODDEVEN) + || ((selected_merger == MERGER_RANDOM) + && (sn_bounded_random (0, 1) == 0))) + n = sn_network_combine_odd_even_merge (p0, p1); + else + n = sn_network_combine_bitonic_merge (p0, p1); sn_network_destroy (p0); sn_network_destroy (p1); @@ -255,8 +269,8 @@ static int create_offspring (void) int pos; enum sn_network_cut_dir_e dir; - pos = bounded_random (SN_NETWORK_INPUT_NUM (n)); - dir = (bounded_random (2) == 0) ? DIR_MIN : DIR_MAX; + pos = sn_bounded_random (0, SN_NETWORK_INPUT_NUM (n) - 1); + dir = (sn_bounded_random (0, 1) == 0) ? DIR_MIN : DIR_MAX; assert ((pos >= 0) && (pos < SN_NETWORK_INPUT_NUM (n))); @@ -268,56 +282,132 @@ static int create_offspring (void) assert (SN_NETWORK_INPUT_NUM (n) == inputs_num); - sn_population_push (population, n); +#if 0 + if ((SN_NETWORK_INPUT_NUM (n) <= 16) && (sn_bounded_random (0, 100) <= 1)) + mutate_network (n); +#endif + + population_insert (population, n); sn_network_destroy (n); return (0); } /* int create_offspring */ -static int start_evolution (void) +static void *evolution_thread (void *arg __attribute__((unused))) { - uint64_t i; - while (do_loop == 0) { create_offspring (); - + /* XXX: Not synchronized! */ iteration_counter++; - i = iteration_counter; + } -#if 0 - if ((stats_interval > 0) && ((i % stats_interval) == 0)) - population_print_stats (i); -#endif + return ((void *) 0); +} /* int start_evolution */ + +static int evolution_start (int threads_num) +{ + pthread_t threads[threads_num]; /* C99 ftw! */ + int i; + + for (i = 0; i < threads_num; i++) + { + int status; + + status = pthread_create (&threads[i], /* attr = */ NULL, + evolution_thread, /* arg = */ NULL); + if (status != 0) + { + fprintf (stderr, "evolution_start: pthread_create[%i] failed " + "with status %i.\n", + i, status); + threads[i] = 0; + } + } + + while (do_loop == 0) + { + int status; + + status = sleep (1); + if (status == 0) + { + sn_network_t *n; + int stages_num; + int comparators_num; + int rating; + int iter; + + iter = iteration_counter; + + n = population_get_fittest (population); + + rating = rate_network (n); + + stages_num = SN_NETWORK_STAGE_NUM (n); + comparators_num = 0; + for (i = 0; i < stages_num; i++) + { + sn_stage_t *s; + + s = SN_NETWORK_STAGE_GET (n, i); + comparators_num += SN_STAGE_COMP_NUM (s); + } + + sn_network_destroy (n); + + printf ("Best after approximately %i iterations: " + "%i comparators in %i stages. Rating: %i.\n", + iter, comparators_num, stages_num, rating); + } + } + + for (i = 0; i < threads_num; i++) + { + if (threads[i] == 0) + continue; + pthread_join (threads[i], /* value_ptr = */ NULL); } return (0); -} /* int start_evolution */ +} /* int evolution_start */ int main (int argc, char **argv) { struct sigaction sigint_action; + struct sigaction sigterm_action; + + population = population_create ((pi_rate_f) rate_network, + (pi_copy_f) sn_network_clone, + (pi_free_f) sn_network_destroy); + if (population == NULL) + { + fprintf (stderr, "population_create failed.\n"); + return (1); + } + + population_set_serialization (population, + (pi_serialize_f) sn_network_serialize, + (pi_unserialize_f) sn_network_unserialize); read_options (argc, argv); if (initial_input_file == NULL) exit_usage (argv[0]); - init_random (); - memset (&sigint_action, '\0', sizeof (sigint_action)); sigint_action.sa_handler = sigint_handler; sigaction (SIGINT, &sigint_action, NULL); - population = sn_population_create (max_population_size); - if (population == NULL) - { - fprintf (stderr, "sn_population_create failed.\n"); - return (1); - } + memset (&sigterm_action, '\0', sizeof (sigterm_action)); + sigterm_action.sa_handler = sigint_handler; + sigaction (SIGTERM, &sigterm_action, NULL); + + population_start_listen_thread (population, NULL, NULL); { sn_network_t *n; + int tmp; n = sn_network_read_file (initial_input_file); if (n == NULL) @@ -328,7 +418,24 @@ int main (int argc, char **argv) inputs_num = SN_NETWORK_INPUT_NUM(n); - sn_population_push (population, n); + /* Determine if `inputs_num' is a power of two. If so, more merge + * algorithms can be used. */ + tmp = inputs_num; + inputs_num_is_power_of_two = 1; + while (tmp > 0) + { + if ((tmp % 2) != 0) + { + if (tmp == 1) + inputs_num_is_power_of_two = 1; + else + inputs_num_is_power_of_two = 0; + break; + } + tmp = tmp >> 1; + } + + population_insert (population, n); sn_network_destroy (n); } @@ -339,23 +446,25 @@ int main (int argc, char **argv) "=======================\n", initial_input_file, inputs_num, max_population_size); - start_evolution (); + evolution_start (evolution_threads_num); - printf ("Exiting after %llu iterations.\n", iteration_counter); + printf ("Exiting after %llu iterations.\n", + (unsigned long long) iteration_counter); - if (best_output_file == NULL) { sn_network_t *n; - n = sn_population_best (population); + n = population_get_fittest (population); if (n != NULL) { + if (best_output_file != NULL) + sn_network_write_file (n, best_output_file); sn_network_show (n); sn_network_destroy (n); } } - sn_population_destroy (population); + population_destroy (population); return (0); } /* int main */