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