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