mpi.cpp

Go to the documentation of this file.

/* -*- coding: latin-1 -*- */
/** \file mpi/mpi/mpi.cpp (January 17, 2018)
 *
 * GPLv3 --- Copyright (C) 2017, 2018 Olivier Pirson
 * http://www.opimedia.be/
 */

// \cond
#include <cassert>

#include <algorithm>
#include <set>
#include <vector>
// \endcond

#include "../../sequential/sequential/sequential.hpp"

#include "mpi.hpp"


namespace mpi {

  /* ***********
   * Functions *
   *************/

  std::set<nat_type>
  mpi_check_gentle_varsigma_odd__dynamic(nat_type first_n, nat_type last_n,
                                         const std::set<nat_type> &previous_bad_table,
                                         bool print_bad,
                                         unsigned int range_size,
                                         unsigned int master_range_size) {
    assert(sigmaodd::is_odd(first_n));
    assert(3 <= first_n);
    assert(first_n <= last_n);
    assert(last_n <= sigmaodd::MAX_POSSIBLE_N);
    assert(sigmaodd::is_even(range_size));
    assert(sigmaodd::is_even(master_range_size));
#ifdef PRIME16
    assert(n < 65536);
#endif

    const unsigned int nb_process = mpi_nb_process();

    const nat_type bad_first_n = (previous_bad_table.empty()
                                  ? first_n
                                  : 0);

    std::set<nat_type> bad_table(previous_bad_table);

    std::set<nat_type>* bad_tables = new std::set<nat_type>[nb_process]();
    nat_type* first_ns = new nat_type[nb_process];

    // Starts empty slave process to simplify following code (all slave process are used)
    for (unsigned int i = 1; i < nb_process; ++i) {
      send_first_last_bad_bad_to(1, 0, 0, 0, i);  // active the slave
      first_ns[i] = first_n;
    }

    for (nat_type n = first_n; n <= last_n; ) {
      // Start each slave process on a range
      first_ns[0] = n;

      // Update the last known possible bad number
      nat_type bad_last_n = sequential::sequential_min_array(first_ns, nb_process) - 1;

      n += master_range_size;  // reserve range for master process

      for (unsigned int i = 1; (i < nb_process) && (n <= last_n); ++i) {
        if (is_finished_from(i)) {  // if slave process i is free
          wait_finished_from(i);

          const std::set<nat_type> new_bad_table = wait_bad_table_from(i);

          first_ns[i] = n;

          // Update the last known possible bad number
          bad_last_n = sequential::sequential_min_array(first_ns, nb_process) - 1;

          // Update bad_table
          bad_table.insert(new_bad_table.cbegin(), new_bad_table.cend());
          if (print_bad) {
            sequential::sequential_print_in_order(new_bad_table);
          }

          // Start this slave process on its range
          send_first_last_bad_bad_to(first_ns[i], std::min(n + range_size - 1, last_n),
                                     bad_first_n, bad_last_n,
                                     i);

          // Send new bad numbers
          std::set<nat_type> diff;

          std::set_difference(bad_table.cbegin(), bad_table.cend(),
                              bad_tables[i].cbegin(),
                              bad_tables[i].cend(),
                              std::inserter(diff, diff.begin()));
          bad_tables[i].insert(diff.cbegin(), diff.cend());
          send_bad_table_to(diff, i);

          // Next range
          n += range_size;
        }
      }

      // Run on master process
      {
        const std::set<nat_type> new_bad_table
          = sequential::sequential_check_gentle_varsigma_odd
            (first_ns[0],
             std::min(first_ns[0] + master_range_size - 1, last_n),
             bad_table,
             bad_first_n, bad_last_n,
             false);

        // Update bad_table
        bad_table.insert(new_bad_table.cbegin(), new_bad_table.cend());
        if (print_bad) {
          sequential::sequential_print_in_order(new_bad_table);
        }
      }
    }

    // Wait end of each slave process
    for (unsigned int i = 1; i < nb_process; ++i) {
      wait_finished_from(i);

      const std::set<nat_type> new_bad_table = wait_bad_table_from(i);

      send_first_last_bad_bad_to(0, 0, 0, 0, i);  // finish the slave

      // Update bad_table
      bad_table.insert(new_bad_table.cbegin(), new_bad_table.cend());
      if (print_bad) {
        sequential::sequential_print_in_order(new_bad_table);
      }
    }

    delete[] bad_tables;
    delete[] first_ns;

    return bad_table;
  }


  std::set<nat_type>
  mpi_check_gentle_varsigma_odd__one_by_one(nat_type first_n, nat_type last_n,
                                            const std::set<nat_type> &previous_bad_table,
                                            bool print_bad) {
    assert(sigmaodd::is_odd(first_n));
    assert(3 <= first_n);
    assert(first_n <= last_n);
    assert(last_n <= sigmaodd::MAX_POSSIBLE_N);
#ifdef PRIME16
    assert(n < 65536);
#endif

    const unsigned int nb_process = mpi_nb_process();

    const nat_type bad_first_n = (previous_bad_table.empty()
                                  ? first_n
                                  : 0);

    std::set<nat_type> bad_table(previous_bad_table);

    std::set<nat_type>* bad_tables = new std::set<nat_type>[nb_process]();
    bool* is_lowers = new bool[nb_process];
    nat_type* ns = new nat_type[nb_process];

    for (nat_type n = first_n; n <= last_n; ) {
      unsigned int nb_process_required = 0;

      // Assign one number for each process
      // and start each slave process
      for ( ; (nb_process_required < nb_process) && (n <= last_n); n += 2) {
        if (!sigmaodd::is_first_mersenne_prime_unitary_divide_or_square(n)) {
          ns[nb_process_required] = n;

          if (nb_process_required > 0) {  // if not master process
            send_n_bad_bad_to(ns[nb_process_required],
                              bad_first_n, ns[0] - 1,
                              nb_process_required);

            // Send new bad numbers
            std::set<nat_type> diff;

            std::set_difference(bad_table.cbegin(), bad_table.cend(),
                                bad_tables[nb_process_required].cbegin(),
                                bad_tables[nb_process_required].cend(),
                                std::inserter(diff, diff.begin()));
            bad_tables[nb_process_required].insert(diff.cbegin(), diff.cend());
            send_bad_table_to(diff, nb_process_required);
          }

          ++nb_process_required;
        }
      }

      // Run on master process
      is_lowers[0]
        = sequential::sequential_is_varsigma_odd_lower(ns[0],
                                                       bad_table,
                                                       bad_first_n, ns[0] - 1);

      // Wait end of each slave process
      for (unsigned int i = 1; i < nb_process_required; ++i) {
        is_lowers[i] = wait_bool_from(i);
      }

      // Update bad_table
      for (unsigned int i = 0; i < nb_process_required; ++i) {
        if (!is_lowers[i]) {  // new bad number identified
          bad_table.insert(ns[i]);
          if (print_bad) {
            std::cout << ns[i] << std::endl;
          }
        }
      }
      if (print_bad) {
        std::cout.flush();
      }
    }

    for (unsigned int i = 1; i < nb_process; ++i) {
      send_n_bad_bad_to(0, 0, 0, i);  // finish the slave
    }

    delete[] bad_tables;
    delete[] is_lowers;
    delete[] ns;

    return bad_table;
  }


  bool
  mpi_slave_wait_compute_n() {
    static std::set<nat_type> static_bad_table;  // accumulate all bad numbers required

    // Wait n, first_n and last_n
    const n_bad_bad_type nfl = wait_n_bad_bad_from_master();

    if (nfl.n == 0) {  // finish
      return false;
    }

    // Wait new bad numbers (since previous call)
    const std::set<nat_type> bad_table = wait_bad_table_from(0);

    static_bad_table.insert(bad_table.cbegin(), bad_table.cend());


    // Compute n
    send_bool_to_master
      (sequential::sequential_is_varsigma_odd_lower(nfl.n,
                                                    static_bad_table,
                                                    nfl.bad_first_n, nfl.bad_last_n));

    // Continue
    return true;
  }


  bool
  mpi_slave_wait_compute_range() {
    static std::set<nat_type> static_bad_table;  // accumulate all bad numbers required

    const first_last_bad_bad_type flb = wait_first_last_bad_bad_from_master();

    if (flb.first_n == 0) {  // finish
      return false;
    }

    std::set<nat_type> new_bad_table;  // bad numbers will be found during this call

    if (flb.first_n != 1) {  // real value to compute (1 is to active the slave)
      // Wait new bad numbers (since previous call)
      const std::set<nat_type> bad_table = wait_bad_table_from(0);

      static_bad_table.insert(bad_table.cbegin(), bad_table.cend());


      // Compute range
      new_bad_table
        = sequential::sequential_check_gentle_varsigma_odd(flb.first_n, flb.last_n,
                                                           static_bad_table,
                                                           flb.bad_first_n, flb.bad_last_n,
                                                           false);
    }

    send_finished_to_master();
    send_bad_table_to(new_bad_table, 0);

    // Continue
    return true;
  }


  void
  print_mpi_versions() {
    int subversion;
    int version;
    char version_str[MPI_MAX_LIBRARY_VERSION_STRING];
    int version_str_len;

    MPI_Get_version(&version, &subversion);
    MPI_Get_library_version(version_str, &version_str_len);

    std::cout << "Open MPI standard version: " << version << "." << subversion
              << "\tLibrary version: " << version_str << std::endl;
  }


  void
  send_bad_table_to(const std::set<nat_type> &bad_table, rank_type to_rank) {
    assert(sizeof(nat_type) == 8);

    const uint32_t size = static_cast<uint32_t>(bad_table.size());

    send_size_to(size, to_rank);

    const std::vector<nat_type> bad_table_vector(bad_table.cbegin(), bad_table.cend());

#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wold-style-cast"
    MPI_Send(bad_table_vector.data(), size, MPI_UINT64_T, to_rank, 0, MPI_COMM_WORLD);
#pragma GCC diagnostic pop
  }


  std::set<nat_type>
  wait_bad_table_from(rank_type from_rank) {
    assert(sizeof(nat_type) == 8);

    const unsigned int size = wait_size_from(from_rank);

    std::vector<nat_type> bad_table_vector(size);

#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wold-style-cast"
    MPI_Recv(bad_table_vector.data(), size, MPI_UINT64_T, from_rank, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
#pragma GCC diagnostic pop

    const std::set<nat_type> bad_table(bad_table_vector.cbegin(), bad_table_vector.cend());

    return bad_table;
  }

}  // namespace mpi