src/sn-evolution.c

   1 /**
   2  * collectd - src/sn-evolution.c
   3  * Copyright (C) 2008-2010  Florian octo Forster
   4  *
   5  * This program is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License as published by the
   7  * Free Software Foundation; only version 2 of the License is applicable.
   8  *
   9  * This program is distributed in the hope that it will be useful, but
  10  * WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License along
  15  * with this program; if not, write to the Free Software Foundation, Inc.,
  16  * 51 Franklin St, Fifth Floor, Boston, MA  02110-1301 USA
  17  *
  18  * Authors:
  19  *   Florian octo Forster <ff at octo.it>
  20  **/
  21
  22 #ifndef _ISOC99_SOURCE
  23 # define _ISOC99_SOURCE
  24 #endif
  25 #ifndef _POSIX_C_SOURCE
  26 # define _POSIX_C_SOURCE 200112L
  27 #endif
  28
  29 #include <stdlib.h>
  30 #include <stdio.h>
  31 #include <stdint.h>
  32 #include <string.h>
  33
  34 #include <sys/types.h>
  35 #include <sys/stat.h>
  36 #include <fcntl.h>
  37 #include <unistd.h>
  38 #include <signal.h>
  39 #include <assert.h>
  40 #include <limits.h>
  41
  42 #include <pthread.h>
  43
  44 #include <population.h>
  45
  46 #include "sn_network.h"
  47 #include "sn_random.h"
  48
  49 /* Yes, this is ugly, but the GNU libc doesn't export it with the above flags.
  50  * */
  51 char *strdup (const char *s);
  52
  53 static uint64_t iteration_counter = 0;
  54 static int inputs_num = 16;
  55 static int inputs_num_is_power_of_two = 1;
  56
  57 static char *initial_input_file = NULL;
  58 static char *best_output_file = NULL;
  59
  60 static int stats_interval = 0;
  61
  62 static int max_population_size = 128;
  63 static population_t *population;
  64
  65 static int evolution_threads_num = 4;
  66
  67 static int do_loop = 0;
  68
  69 static void sigint_handler (int signal)
  70 {
  71   do_loop++;
  72 } /* void sigint_handler */
  73
  74 static void exit_usage (const char *name)
  75 {
  76   printf ("Usage: %s [options]\n"
  77       "\n"
  78       "Valid options are:\n"
  79       "  -i <file>     Initial input file (REQUIRED)\n"
  80       "  -o <file>     Write the current best solution to <file>\n"
  81       "  -p <num>      Size of the population (default: 128)\n"
  82       "  -P <peer>     Send individuals to <peer> (may be repeated)\n"
  83       "  -t <num>      Number of threads (default: 4)\n"
  84       "\n",
  85       name);
  86   exit (1);
  87 } /* void exit_usage */
  88
  89 int read_options (int argc, char **argv)
  90 {
  91   int option;
  92
  93   while ((option = getopt (argc, argv, "i:o:p:P:s:t:h")) != -1)
  94   {
  95     switch (option)
  96     {
  97       case 'i':
  98       {
  99         if (initial_input_file != NULL)
 100           free (initial_input_file);
 101         initial_input_file = strdup (optarg);
 102         break;
 103       }
 104
 105       case 'o':
 106       {
 107         if (best_output_file != NULL)
 108           free (best_output_file);
 109         best_output_file = strdup (optarg);
 110         break;
 111       }
 112
 113       case 'p':
 114       {
 115         int tmp = atoi (optarg);
 116         if (tmp > 0)
 117         {
 118           max_population_size = tmp;
 119           population_set_size (population, (size_t) max_population_size);
 120         }
 121         break;
 122       }
 123
 124       case 'P':
 125       {
 126         int status;
 127
 128         status = population_add_peer (population, optarg, /* port = */ NULL);
 129         if (status != 0)
 130         {
 131           fprintf (stderr, "population_add_peer failed with status %i.\n",
 132               status);
 133         }
 134         break;
 135       }
 136
 137       case 's':
 138       {
 139         int tmp = atoi (optarg);
 140         if (tmp > 0)
 141           stats_interval = tmp;
 142         break;
 143       }
 144
 145       case 't':
 146       {
 147         int tmp = atoi (optarg);
 148         if (tmp >= 1)
 149           evolution_threads_num = tmp;
 150         break;
 151       }
 152
 153       case 'h':
 154       default:
 155         exit_usage (argv[0]);
 156     }
 157   }
 158
 159   return (0);
 160 } /* int read_options */
 161
 162 static int rate_network (const sn_network_t *n)
 163 {
 164   int rate;
 165   int i;
 166
 167   rate = SN_NETWORK_STAGE_NUM (n) * SN_NETWORK_INPUT_NUM (n);
 168   for (i = 0; i < SN_NETWORK_STAGE_NUM (n); i++)
 169   {
 170     sn_stage_t *s = SN_NETWORK_STAGE_GET (n, i);
 171     rate += SN_STAGE_COMP_NUM (s);
 172   }
 173
 174   return (rate);
 175 } /* int rate_network */
 176
 177 static int mutate_network (sn_network_t *n)
 178 {
 179   sn_network_t *n_copy;
 180   int stage_index;
 181   sn_stage_t *s;
 182   int comparator_index;
 183   int status;
 184
 185   n_copy = sn_network_clone (n);
 186   if (n_copy == NULL)
 187   {
 188     fprintf (stderr, "mutate_network: sn_network_clone failed.\n");
 189     return (-1);
 190   }
 191
 192   stage_index = sn_bounded_random (0, SN_NETWORK_STAGE_NUM (n_copy) - 1);
 193   s = SN_NETWORK_STAGE_GET (n_copy, stage_index);
 194
 195   comparator_index = sn_bounded_random (0, SN_STAGE_COMP_NUM (s) - 1);
 196   sn_stage_comparator_remove (s, comparator_index);
 197
 198   status = sn_network_brute_force_check (n_copy);
 199
 200   sn_network_destroy (n_copy);
 201
 202   if (status < 0)
 203     return (-1);
 204   else if (status > 0) /* Mutated network does not sort anymore. */
 205     return (1);
 206
 207   /* We saved one comparator \o/ Let's do the same change on the original
 208    * network. */
 209   s = SN_NETWORK_STAGE_GET (n, stage_index);
 210   sn_stage_comparator_remove (s, comparator_index);
 211
 212   return (0);
 213 } /* int mutate_network */
 214
 215 static int create_offspring (void)
 216 {
 217   sn_network_t *p0;
 218   sn_network_t *p1;
 219   sn_network_t *n;
 220
 221   p0 = population_get_random (population);
 222   p1 = population_get_random (population);
 223
 224   assert (p0 != NULL);
 225   assert (p1 != NULL);
 226
 227   /* combine the two parents */
 228   n = sn_network_combine (p0, p1, inputs_num_is_power_of_two);
 229
 230   sn_network_destroy (p0);
 231   sn_network_destroy (p1);
 232
 233   /* randomly chose an input and do a min- or max-cut. */
 234   while (SN_NETWORK_INPUT_NUM (n) > inputs_num)
 235   {
 236     int pos;
 237     enum sn_network_cut_dir_e dir;
 238
 239     pos = sn_bounded_random (0, SN_NETWORK_INPUT_NUM (n) - 1);
 240     dir = (sn_bounded_random (0, 1) == 0) ? DIR_MIN : DIR_MAX;
 241
 242     assert ((pos >= 0) && (pos < SN_NETWORK_INPUT_NUM (n)));
 243
 244     sn_network_cut_at (n, pos, dir);
 245   }
 246
 247   /* compress the network to get a compact representation */
 248   sn_network_compress (n);
 249
 250   assert (SN_NETWORK_INPUT_NUM (n) == inputs_num);
 251
 252   if ((SN_NETWORK_INPUT_NUM (n) <= 16) && (sn_bounded_random (0, 100) <= 1))
 253     mutate_network (n);
 254
 255   population_insert (population, n);
 256
 257   sn_network_destroy (n);
 258
 259   return (0);
 260 } /* int create_offspring */
 261
 262 static void *evolution_thread (void *arg)
 263 {
 264   while (do_loop == 0)
 265   {
 266     create_offspring ();
 267     /* XXX: Not synchronized! */
 268     iteration_counter++;
 269   }
 270
 271   return ((void *) 0);
 272 } /* int start_evolution */
 273
 274 static int evolution_start (int threads_num)
 275 {
 276   pthread_t threads[threads_num]; /* C99 ftw! */
 277   int i;
 278
 279   for (i = 0; i < threads_num; i++)
 280   {
 281     int status;
 282
 283     status = pthread_create (&threads[i], /* attr = */ NULL,
 284         evolution_thread, /* arg = */ NULL);
 285     if (status != 0)
 286     {
 287       fprintf (stderr, "evolution_start: pthread_create[%i] failed "
 288           "with status %i.\n",
 289           i, status);
 290       threads[i] = 0;
 291     }
 292   }
 293
 294   while (do_loop == 0)
 295   {
 296     int status;
 297
 298     status = sleep (1);
 299     if (status == 0)
 300     {
 301       sn_network_t *n;
 302       int stages_num;
 303       int comparators_num;
 304       int rating;
 305       int iter;
 306
 307       iter = iteration_counter;
 308
 309       n = population_get_fittest (population);
 310
 311       rating = rate_network (n);
 312
 313       stages_num = SN_NETWORK_STAGE_NUM (n);
 314       comparators_num = 0;
 315       for (i = 0; i < stages_num; i++)
 316       {
 317         sn_stage_t *s;
 318
 319         s = SN_NETWORK_STAGE_GET (n, i);
 320         comparators_num += SN_STAGE_COMP_NUM (s);
 321       }
 322
 323       sn_network_destroy (n);
 324
 325       printf ("Best after approximately %i iterations: "
 326           "%i comparators in %i stages. Rating: %i.\n",
 327           iter, comparators_num, stages_num, rating);
 328     }
 329   }
 330
 331   for (i = 0; i < threads_num; i++)
 332   {
 333     if (threads[i] == 0)
 334       continue;
 335     pthread_join (threads[i], /* value_ptr = */ NULL);
 336   }
 337
 338   return (0);
 339 } /* int evolution_start */
 340
 341 int main (int argc, char **argv)
 342 {
 343   struct sigaction sigint_action;
 344   struct sigaction sigterm_action;
 345
 346   population = population_create ((pi_rate_f) rate_network,
 347       (pi_copy_f) sn_network_clone,
 348       (pi_free_f) sn_network_destroy);
 349   if (population == NULL)
 350   {
 351     fprintf (stderr, "population_create failed.\n");
 352     return (1);
 353   }
 354
 355   population_set_serialization (population,
 356       (pi_serialize_f) sn_network_serialize,
 357       (pi_unserialize_f) sn_network_unserialize);
 358
 359   read_options (argc, argv);
 360   if (initial_input_file == NULL)
 361     exit_usage (argv[0]);
 362
 363   memset (&sigint_action, '\0', sizeof (sigint_action));
 364   sigint_action.sa_handler = sigint_handler;
 365   sigaction (SIGINT, &sigint_action, NULL);
 366
 367   memset (&sigterm_action, '\0', sizeof (sigterm_action));
 368   sigterm_action.sa_handler = sigint_handler;
 369   sigaction (SIGTERM, &sigterm_action, NULL);
 370
 371   population_start_listen_thread (population, NULL, NULL);
 372
 373   {
 374     sn_network_t *n;
 375     int tmp;
 376
 377     n = sn_network_read_file (initial_input_file);
 378     if (n == NULL)
 379     {
 380       printf ("n == NULL\n");
 381       return (1);
 382     }
 383
 384     inputs_num = SN_NETWORK_INPUT_NUM(n);
 385
 386     /* Determine if `inputs_num' is a power of two. If so, more merge
 387      * algorithms can be used. */
 388     tmp = inputs_num;
 389     inputs_num_is_power_of_two = 1;
 390     while (tmp > 0)
 391     {
 392       if ((tmp % 2) != 0)
 393       {
 394         if (tmp == 1)
 395           inputs_num_is_power_of_two = 1;
 396         else
 397           inputs_num_is_power_of_two = 0;
 398         break;
 399       }
 400       tmp = tmp >> 1;
 401     }
 402
 403     population_insert (population, n);
 404     sn_network_destroy (n);
 405   }
 406
 407   printf ("Current configuration:\n"
 408       "  Initial network:  %s\n"
 409       "  Number of inputs: %3i\n"
 410       "  Population size:  %3i\n"
 411       "=======================\n",
 412       initial_input_file, inputs_num, max_population_size);
 413
 414   evolution_start (evolution_threads_num);
 415
 416   printf ("Exiting after %llu iterations.\n",
 417       (unsigned long long) iteration_counter);
 418
 419   {
 420     sn_network_t *n;
 421
 422     n = population_get_fittest (population);
 423     if (n != NULL)
 424     {
 425       if (best_output_file != NULL)
 426         sn_network_write_file (n, best_output_file);
 427       sn_network_show (n);
 428       sn_network_destroy (n);
 429     }
 430   }
 431
 432   population_destroy (population);
 433
 434   return (0);
 435 } /* int main */
 436
 437 /* vim: set shiftwidth=2 softtabstop=2 : */