src/sn-evolution.c

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