src/include/xbt/parmap.hpp

   1 /* A thread pool (C++ version).                                             */
   2
   3 /* Copyright (c) 2004-2022 The SimGrid Team. All rights reserved.           */
   4
   5 /* This program is free software; you can redistribute it and/or modify it
   6  * under the terms of the license (GNU LGPL) which comes with this package. */
   7
   8 #ifndef XBT_PARMAP_HPP
   9 #define XBT_PARMAP_HPP
  10
  11 #include "src/internal_config.h" // HAVE_FUTEX_H
  12 #include "src/kernel/EngineImpl.hpp"
  13 #include "src/kernel/context/Context.hpp"
  14
  15 #include <boost/optional.hpp>
  16 #include <condition_variable>
  17 #include <functional>
  18 #include <mutex>
  19 #include <thread>
  20
  21 #if HAVE_FUTEX_H
  22 #include <linux/futex.h>
  23 #include <sys/syscall.h>
  24 #endif
  25
  26 #if HAVE_PTHREAD_NP_H
  27 #include <pthread_np.h>
  28 #endif
  29
  30 XBT_LOG_EXTERNAL_CATEGORY(xbt_parmap);
  31
  32 namespace simgrid {
  33 namespace xbt {
  34
  35 /** @addtogroup XBT_parmap
  36  * @ingroup XBT_misc
  37  * @brief Parallel map class
  38  * @{
  39  */
  40 template <typename T> class Parmap {
  41 public:
  42   Parmap(unsigned num_workers, e_xbt_parmap_mode_t mode);
  43   Parmap(const Parmap&) = delete;
  44   Parmap& operator=(const Parmap&) = delete;
  45   ~Parmap();
  46   void apply(std::function<void(T)>&& fun, const std::vector<T>& data);
  47   boost::optional<T> next();
  48
  49 private:
  50   /**
  51    * @brief Thread data transmission structure
  52    */
  53   class ThreadData {
  54   public:
  55     ThreadData(Parmap<T>& parmap, int id) : parmap(parmap), worker_id(id) {}
  56     Parmap<T>& parmap;
  57     int worker_id;
  58   };
  59
  60   /**
  61    * @brief Synchronization object (different specializations).
  62    */
  63   class Synchro {
  64   public:
  65     explicit Synchro(Parmap<T>& parmap) : parmap(parmap) {}
  66     virtual ~Synchro() = default;
  67     /**
  68      * @brief Wakes all workers and waits for them to finish the tasks.
  69      *
  70      * This function is called by the controller thread.
  71      */
  72     virtual void master_signal() = 0;
  73     /**
  74      * @brief Starts the parmap: waits for all workers to be ready and returns.
  75      *
  76      * This function is called by the controller thread.
  77      */
  78     virtual void master_wait() = 0;
  79     /**
  80      * @brief Ends the parmap: wakes the controller thread when all workers terminate.
  81      *
  82      * This function is called by all worker threads when they end (not including the controller).
  83      */
  84     virtual void worker_signal() = 0;
  85     /**
  86      * @brief Waits for some work to process.
  87      *
  88      * This function is called by each worker thread (not including the controller) when it has no more work to do.
  89      *
  90      * @param expected_round  the expected round number
  91      */
  92     virtual void worker_wait(unsigned) = 0;
  93
  94     Parmap<T>& parmap;
  95   };
  96
  97   class PosixSynchro : public Synchro {
  98   public:
  99     explicit PosixSynchro(Parmap<T>& parmap) : Synchro(parmap) {}
 100     void master_signal() override;
 101     void master_wait() override;
 102     void worker_signal() override;
 103     void worker_wait(unsigned expected_round) override;
 104
 105   private:
 106     std::condition_variable ready_cond;
 107     std::mutex ready_mutex;
 108     std::condition_variable done_cond;
 109     std::mutex done_mutex;
 110   };
 111
 112 #if HAVE_FUTEX_H
 113   class FutexSynchro : public Synchro {
 114   public:
 115     explicit FutexSynchro(Parmap<T>& parmap) : Synchro(parmap) {}
 116     void master_signal() override;
 117     void master_wait() override;
 118     void worker_signal() override;
 119     void worker_wait(unsigned) override;
 120
 121   private:
 122     static void futex_wait(std::atomic_uint* uaddr, unsigned val);
 123     static void futex_wake(std::atomic_uint* uaddr, unsigned val);
 124   };
 125 #endif
 126
 127   class BusyWaitSynchro : public Synchro {
 128   public:
 129     explicit BusyWaitSynchro(Parmap<T>& parmap) : Synchro(parmap) {}
 130     void master_signal() override;
 131     void master_wait() override;
 132     void worker_signal() override;
 133     void worker_wait(unsigned) override;
 134   };
 135
 136   static void worker_main(ThreadData* data);
 137   Synchro* new_synchro(e_xbt_parmap_mode_t mode);
 138   void work();
 139
 140   bool destroying = false;           /**< is the parmap being destroyed? */
 141   std::atomic_uint work_round{0};    /**< index of the current round */
 142   std::vector<std::thread*> workers; /**< worker thread handlers */
 143   unsigned num_workers;     /**< total number of worker threads including the controller */
 144   Synchro* synchro;         /**< synchronization object */
 145
 146   std::atomic_uint thread_counter{0};   /**< number of workers that have done the work */
 147   std::function<void(T)> worker_fun;    /**< function to run in parallel on each element of data */
 148   const std::vector<T>* common_data = nullptr; /**< parameters to pass to fun in parallel */
 149   std::atomic_uint common_index{0};            /**< index of the next element of data to pick */
 150 };
 151
 152 /**
 153  * @brief Creates a parallel map object
 154  * @param num_workers number of worker threads to create
 155  * @param mode how to synchronize the worker threads
 156  */
 157 template <typename T>
 158 Parmap<T>::Parmap(unsigned num_workers, e_xbt_parmap_mode_t mode)
 159     : workers(num_workers), num_workers(num_workers), synchro(new_synchro(mode))
 160 {
 161   XBT_CDEBUG(xbt_parmap, "Create new parmap (%u workers)", num_workers);
 162
 163   /* Create the pool of worker threads (the caller of apply() will be worker[0]) */
 164   workers[0] = nullptr;
 165
 166   for (unsigned i = 1; i < num_workers; i++) {
 167     auto* data = new ThreadData(*this, i);
 168     workers[i] = new std::thread(worker_main, data);
 169
 170     /* Bind the worker to a core if possible */
 171 #if HAVE_PTHREAD_SETAFFINITY
 172 #if HAVE_PTHREAD_NP_H /* FreeBSD ? */
 173     cpuset_t cpuset;
 174     size_t size = sizeof(cpuset_t);
 175 #else /* Linux ? */
 176     cpu_set_t cpuset;
 177     size_t size = sizeof(cpu_set_t);
 178 #endif
 179     pthread_t pthread = workers[i]->native_handle();
 180     int core_bind     = (i - 1) % std::thread::hardware_concurrency();
 181     CPU_ZERO(&cpuset);
 182     CPU_SET(core_bind, &cpuset);
 183     pthread_setaffinity_np(pthread, size, &cpuset);
 184 #endif
 185   }
 186 }
 187
 188 /**
 189  * @brief Destroys a parmap
 190  */
 191 template <typename T> Parmap<T>::~Parmap()
 192 {
 193   destroying = true;
 194   synchro->master_signal();
 195
 196   for (unsigned i = 1; i < num_workers; i++) {
 197     workers[i]->join();
 198     delete workers[i];
 199   }
 200   delete synchro;
 201 }
 202
 203 /**
 204  * @brief Applies a list of tasks in parallel.
 205  * @param fun the function to call in parallel
 206  * @param data each element of this vector will be passed as an argument to fun
 207  */
 208 template <typename T> void Parmap<T>::apply(std::function<void(T)>&& fun, const std::vector<T>& data)
 209 {
 210   /* Assign resources to worker threads (we are maestro here)*/
 211   worker_fun   = std::move(fun);
 212   common_data  = &data;
 213   common_index = 0;
 214   synchro->master_signal(); // maestro runs futex_wake to wake all the minions (the working threads)
 215   work();                   // maestro works with its minions
 216   synchro->master_wait();   // When there is no more work to do, then maestro waits for the last minion to stop
 217   XBT_CDEBUG(xbt_parmap, "Job done"); //   ... and proceeds
 218 }
 219
 220 /**
 221  * @brief Returns a next task to process.
 222  *
 223  * Worker threads call this function to get more work.
 224  *
 225  * @return the next task to process, or throws a std::out_of_range exception if there is no more work
 226  */
 227 template <typename T> boost::optional<T> Parmap<T>::next()
 228 {
 229   unsigned index = common_index.fetch_add(1, std::memory_order_relaxed);
 230   if (index < common_data->size())
 231     return (*common_data)[index];
 232   else
 233     return boost::none;
 234 }
 235
 236 /**
 237  * @brief Main work loop: applies fun to elements in turn.
 238  */
 239 template <typename T> void Parmap<T>::work()
 240 {
 241   unsigned length = static_cast<unsigned>(common_data->size());
 242   unsigned index  = common_index.fetch_add(1, std::memory_order_relaxed);
 243   while (index < length) {
 244     worker_fun((*common_data)[index]);
 245     index = common_index.fetch_add(1, std::memory_order_relaxed);
 246   }
 247 }
 248
 249 /**
 250  * Get a synchronization object for given mode.
 251  * @param mode the synchronization mode
 252  */
 253 template <typename T> typename Parmap<T>::Synchro* Parmap<T>::new_synchro(e_xbt_parmap_mode_t mode)
 254 {
 255   if (mode == XBT_PARMAP_DEFAULT) {
 256 #if HAVE_FUTEX_H
 257     mode = XBT_PARMAP_FUTEX;
 258 #else
 259     mode = XBT_PARMAP_POSIX;
 260 #endif
 261   }
 262   Synchro* res;
 263   switch (mode) {
 264     case XBT_PARMAP_POSIX:
 265       res = new PosixSynchro(*this);
 266       break;
 267     case XBT_PARMAP_FUTEX:
 268 #if HAVE_FUTEX_H
 269       res = new FutexSynchro(*this);
 270 #else
 271       xbt_die("Futex is not available on this OS.");
 272 #endif
 273       break;
 274     case XBT_PARMAP_BUSY_WAIT:
 275       res = new BusyWaitSynchro(*this);
 276       break;
 277     default:
 278       THROW_IMPOSSIBLE;
 279   }
 280   return res;
 281 }
 282
 283 /** @brief Main function of a worker thread */
 284 template <typename T> void Parmap<T>::worker_main(ThreadData* data)
 285 {
 286   auto engine                       = simgrid::kernel::EngineImpl::get_instance();
 287   Parmap<T>& parmap     = data->parmap;
 288   unsigned round        = 0;
 289   kernel::context::Context* context = engine->get_context_factory()->create_context(std::function<void()>(), nullptr);
 290   kernel::context::Context::set_current(context);
 291
 292   XBT_CDEBUG(xbt_parmap, "New worker thread created");
 293
 294   /* Worker's main loop */
 295   while (true) {
 296     round++; // New scheduling round
 297     parmap.synchro->worker_wait(round);
 298     if (parmap.destroying)
 299       break;
 300
 301     XBT_CDEBUG(xbt_parmap, "Worker %d got a job", data->worker_id);
 302     parmap.work();
 303     parmap.synchro->worker_signal();
 304     XBT_CDEBUG(xbt_parmap, "Worker %d has finished", data->worker_id);
 305   }
 306   /* We are destroying the parmap */
 307   delete context;
 308   delete data;
 309 }
 310
 311 template <typename T> void Parmap<T>::PosixSynchro::master_signal()
 312 {
 313   std::unique_lock<std::mutex> lk(ready_mutex);
 314   this->parmap.thread_counter = 1;
 315   this->parmap.work_round++;
 316   /* wake all workers */
 317   ready_cond.notify_all();
 318 }
 319
 320 template <typename T> void Parmap<T>::PosixSynchro::master_wait()
 321 {
 322   std::unique_lock<std::mutex> lk(done_mutex);
 323   /* wait for all workers to be ready */
 324   done_cond.wait(lk, [this]() { return this->parmap.thread_counter >= this->parmap.num_workers; });
 325 }
 326
 327 template <typename T> void Parmap<T>::PosixSynchro::worker_signal()
 328 {
 329   std::unique_lock<std::mutex> lk(done_mutex);
 330   this->parmap.thread_counter++;
 331   if (this->parmap.thread_counter == this->parmap.num_workers) {
 332     /* all workers have finished, wake the controller */
 333     done_cond.notify_one();
 334   }
 335 }
 336
 337 template <typename T> void Parmap<T>::PosixSynchro::worker_wait(unsigned expected_round)
 338 {
 339   std::unique_lock<std::mutex> lk(ready_mutex);
 340   /* wait for more work */
 341   ready_cond.wait(lk, [this, expected_round]() { return this->parmap.work_round == expected_round; });
 342 }
 343
 344 #if HAVE_FUTEX_H
 345 template <typename T> inline void Parmap<T>::FutexSynchro::futex_wait(std::atomic_uint* uaddr, unsigned val)
 346 {
 347   XBT_CVERB(xbt_parmap, "Waiting on futex %p", uaddr);
 348   syscall(SYS_futex, uaddr, FUTEX_WAIT_PRIVATE, val, nullptr, nullptr, 0);
 349 }
 350
 351 template <typename T> inline void Parmap<T>::FutexSynchro::futex_wake(std::atomic_uint* uaddr, unsigned val)
 352 {
 353   XBT_CVERB(xbt_parmap, "Waking futex %p", uaddr);
 354   syscall(SYS_futex, uaddr, FUTEX_WAKE_PRIVATE, val, nullptr, nullptr, 0);
 355 }
 356
 357 template <typename T> void Parmap<T>::FutexSynchro::master_signal()
 358 {
 359   this->parmap.thread_counter.store(1);
 360   this->parmap.work_round.fetch_add(1);
 361   /* wake all workers */
 362   futex_wake(&this->parmap.work_round, std::numeric_limits<int>::max());
 363 }
 364
 365 template <typename T> void Parmap<T>::FutexSynchro::master_wait()
 366 {
 367   unsigned count = this->parmap.thread_counter.load();
 368   while (count < this->parmap.num_workers) {
 369     /* wait for all workers to be ready */
 370     futex_wait(&this->parmap.thread_counter, count);
 371     count = this->parmap.thread_counter.load();
 372   }
 373 }
 374
 375 template <typename T> void Parmap<T>::FutexSynchro::worker_signal()
 376 {
 377   unsigned count = this->parmap.thread_counter.fetch_add(1) + 1;
 378   if (count == this->parmap.num_workers) {
 379     /* all workers have finished, wake the controller */
 380     futex_wake(&this->parmap.thread_counter, std::numeric_limits<int>::max());
 381   }
 382 }
 383
 384 template <typename T> void Parmap<T>::FutexSynchro::worker_wait(unsigned expected_round)
 385 {
 386   unsigned round = this->parmap.work_round.load();
 387   /* wait for more work */
 388   while (round != expected_round) {
 389     futex_wait(&this->parmap.work_round, round);
 390     round = this->parmap.work_round.load();
 391   }
 392 }
 393 #endif
 394
 395 template <typename T> void Parmap<T>::BusyWaitSynchro::master_signal()
 396 {
 397   this->parmap.thread_counter.store(1);
 398   this->parmap.work_round.fetch_add(1);
 399 }
 400
 401 template <typename T> void Parmap<T>::BusyWaitSynchro::master_wait()
 402 {
 403   while (this->parmap.thread_counter.load() < this->parmap.num_workers) {
 404     std::this_thread::yield();
 405   }
 406 }
 407
 408 template <typename T> void Parmap<T>::BusyWaitSynchro::worker_signal()
 409 {
 410   this->parmap.thread_counter.fetch_add(1);
 411 }
 412
 413 template <typename T> void Parmap<T>::BusyWaitSynchro::worker_wait(unsigned round)
 414 {
 415   /* wait for more work */
 416   while (this->parmap.work_round.load() != round) {
 417     std::this_thread::yield();
 418   }
 419 }
 420
 421 /** @} */
 422 }
 423 }
 424
 425 #endif