src/include/xbt/parmap.hpp

   1 /* A thread pool (C++ version).                                             */
   2
   3 /* Copyright (c) 2004-2019 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/context/Context.hpp"
  13 #include "xbt/xbt_os_thread.h"
  14
  15 #include <boost/optional.hpp>
  16 #include <condition_variable>
  17 #include <mutex>
  18 #include <thread>
  19
  20 #if HAVE_FUTEX_H
  21 #include <linux/futex.h>
  22 #include <sys/syscall.h>
  23 #endif
  24
  25 XBT_LOG_EXTERNAL_CATEGORY(xbt_parmap);
  26
  27 namespace simgrid {
  28 namespace xbt {
  29
  30 /** @addtogroup XBT_parmap
  31  * @ingroup XBT_misc
  32  * @brief Parallel map class
  33  * @{
  34  */
  35 template <typename T> class Parmap {
  36 public:
  37   Parmap(unsigned num_workers, e_xbt_parmap_mode_t mode);
  38   Parmap(const Parmap&) = delete;
  39   Parmap& operator=(const Parmap&) = delete;
  40   ~Parmap();
  41   void apply(void (*fun)(T), const std::vector<T>& data);
  42   boost::optional<T> next();
  43
  44 private:
  45   enum Flag { PARMAP_WORK, PARMAP_DESTROY };
  46
  47   /**
  48    * @brief Thread data transmission structure
  49    */
  50   class ThreadData {
  51   public:
  52     ThreadData(Parmap<T>& parmap, int id) : parmap(parmap), worker_id(id) {}
  53     Parmap<T>& parmap;
  54     int worker_id;
  55   };
  56
  57   /**
  58    * @brief Synchronization object (different specializations).
  59    */
  60   class Synchro {
  61   public:
  62     explicit Synchro(Parmap<T>& parmap) : parmap(parmap) {}
  63     virtual ~Synchro() = default;
  64     /**
  65      * @brief Wakes all workers and waits for them to finish the tasks.
  66      *
  67      * This function is called by the controller thread.
  68      */
  69     virtual void master_signal() = 0;
  70     /**
  71      * @brief Starts the parmap: waits for all workers to be ready and returns.
  72      *
  73      * This function is called by the controller thread.
  74      */
  75     virtual void master_wait() = 0;
  76     /**
  77      * @brief Ends the parmap: wakes the controller thread when all workers terminate.
  78      *
  79      * This function is called by all worker threads when they end (not including the controller).
  80      */
  81     virtual void worker_signal() = 0;
  82     /**
  83      * @brief Waits for some work to process.
  84      *
  85      * This function is called by each worker thread (not including the controller) when it has no more work to do.
  86      *
  87      * @param round  the expected round number
  88      */
  89     virtual void worker_wait(unsigned) = 0;
  90
  91     Parmap<T>& parmap;
  92   };
  93
  94   class PosixSynchro : public Synchro {
  95   public:
  96     explicit PosixSynchro(Parmap<T>& parmap);
  97     ~PosixSynchro();
  98     void master_signal();
  99     void master_wait();
 100     void worker_signal();
 101     void worker_wait(unsigned round);
 102
 103   private:
 104     std::condition_variable ready_cond;
 105     std::mutex ready_mutex;
 106     std::condition_variable done_cond;
 107     std::mutex done_mutex;
 108   };
 109
 110 #if HAVE_FUTEX_H
 111   class FutexSynchro : public Synchro {
 112   public:
 113     explicit FutexSynchro(Parmap<T>& parmap) : Synchro(parmap) {}
 114     void master_signal();
 115     void master_wait();
 116     void worker_signal();
 117     void worker_wait(unsigned);
 118
 119   private:
 120     static void futex_wait(unsigned* uaddr, unsigned val);
 121     static void futex_wake(unsigned* uaddr, unsigned val);
 122   };
 123 #endif
 124
 125   class BusyWaitSynchro : public Synchro {
 126   public:
 127     explicit BusyWaitSynchro(Parmap<T>& parmap) : Synchro(parmap) {}
 128     void master_signal();
 129     void master_wait();
 130     void worker_signal();
 131     void worker_wait(unsigned);
 132   };
 133
 134   static void* worker_main(void* arg);
 135   Synchro* new_synchro(e_xbt_parmap_mode_t mode);
 136   void work();
 137
 138   Flag status;              /**< is the parmap active or being destroyed? */
 139   unsigned work_round;      /**< index of the current round */
 140   std::vector<std::thread*> workers; /**< worker thread handlers */
 141   unsigned num_workers;     /**< total number of worker threads including the controller */
 142   Synchro* synchro;         /**< synchronization object */
 143
 144   unsigned thread_counter    = 0;       /**< number of workers that have done the work */
 145   void (*fun)(const T)       = nullptr; /**< function to run in parallel on each element of data */
 146   const std::vector<T>* data = nullptr; /**< parameters to pass to fun in parallel */
 147   std::atomic<unsigned> index;          /**< index of the next element of data to pick */
 148 };
 149
 150 /**
 151  * @brief Creates a parallel map object
 152  * @param num_workers number of worker threads to create
 153  * @param mode how to synchronize the worker threads
 154  */
 155 template <typename T> Parmap<T>::Parmap(unsigned num_workers, e_xbt_parmap_mode_t mode)
 156 {
 157   XBT_CDEBUG(xbt_parmap, "Create new parmap (%u workers)", num_workers);
 158
 159   /* Initialize the thread pool data structure */
 160   this->status      = PARMAP_WORK;
 161   this->work_round  = 0;
 162   this->workers.reserve(num_workers);
 163   this->num_workers = num_workers;
 164   this->synchro     = new_synchro(mode);
 165
 166   /* Create the pool of worker threads (the caller of apply() will be worker[0]) */
 167   this->workers[0] = nullptr;
 168   XBT_ATTRIB_UNUSED unsigned int core_bind = 0;
 169
 170   for (unsigned i = 1; i < num_workers; i++) {
 171     this->workers[i] = new std::thread(worker_main, new ThreadData(*this, i));
 172
 173     /* Bind the worker to a core if possible */
 174 #if HAVE_PTHREAD_SETAFFINITY
 175     pthread_t pthread = this->workers[i]->native_handle();
 176     cpu_set_t cpuset;
 177     CPU_ZERO(&cpuset);
 178     CPU_SET(core_bind, &cpuset);
 179     pthread_setaffinity_np(pthread, sizeof(cpu_set_t), &cpuset);
 180     if (core_bind != std::thread::hardware_concurrency() - 1)
 181       core_bind++;
 182     else
 183       core_bind = 0;
 184 #endif
 185   }
 186 }
 187
 188 /**
 189  * @brief Destroys a parmap
 190  */
 191 template <typename T> Parmap<T>::~Parmap()
 192 {
 193   status = PARMAP_DESTROY;
 194   synchro->master_signal();
 195
 196   for (unsigned i = 1; i < num_workers; i++)
 197     workers[i]->join();
 198
 199   workers.clear();
 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(void (*fun)(T), const std::vector<T>& data)
 209 {
 210   /* Assign resources to worker threads (we are maestro here)*/
 211   this->fun   = fun;
 212   this->data  = &data;
 213   this->index = 0;
 214   this->synchro->master_signal(); // maestro runs futex_wake to wake all the minions (the working threads)
 215   this->work();                   // maestro works with its minions
 216   this->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 = this->index.fetch_add(1, std::memory_order_relaxed);
 230   if (index < this->data->size())
 231     return (*this->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 = this->data->size();
 242   unsigned index  = this->index.fetch_add(1, std::memory_order_relaxed);
 243   while (index < length) {
 244     this->fun((*this->data)[index]);
 245     index = this->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(void* arg)
 285 {
 286   ThreadData* data      = static_cast<ThreadData*>(arg);
 287   Parmap<T>& parmap     = data->parmap;
 288   unsigned round        = 0;
 289   smx_context_t context = SIMIX_context_new(std::function<void()>(), nullptr, 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 (1) {
 296     round++; // New scheduling round
 297     parmap.synchro->worker_wait(round);
 298     if (parmap.status == PARMAP_DESTROY)
 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   return nullptr;
 310 }
 311
 312 template <typename T> Parmap<T>::PosixSynchro::PosixSynchro(Parmap<T>& parmap) : Synchro(parmap)
 313 {
 314 }
 315
 316 template <typename T> Parmap<T>::PosixSynchro::~PosixSynchro()
 317 {
 318 }
 319
 320 template <typename T> void Parmap<T>::PosixSynchro::master_signal()
 321 {
 322   std::unique_lock<std::mutex> lk(ready_mutex);
 323   this->parmap.thread_counter = 1;
 324   this->parmap.work_round++;
 325   /* wake all workers */
 326   ready_cond.notify_all();
 327 }
 328
 329 template <typename T> void Parmap<T>::PosixSynchro::master_wait()
 330 {
 331   std::unique_lock<std::mutex> lk(done_mutex);
 332   while (this->parmap.thread_counter < this->parmap.num_workers) {
 333     /* wait for all workers to be ready */
 334     done_cond.wait(lk);
 335   }
 336 }
 337
 338 template <typename T> void Parmap<T>::PosixSynchro::worker_signal()
 339 {
 340   std::unique_lock<std::mutex> lk(done_mutex);
 341   this->parmap.thread_counter++;
 342   if (this->parmap.thread_counter == this->parmap.num_workers) {
 343     /* all workers have finished, wake the controller */
 344     done_cond.notify_one();
 345   }
 346 }
 347
 348 template <typename T> void Parmap<T>::PosixSynchro::worker_wait(unsigned round)
 349 {
 350   std::unique_lock<std::mutex> lk(ready_mutex);
 351   /* wait for more work */
 352   while (this->parmap.work_round != round) {
 353     ready_cond.wait(lk);
 354   }
 355 }
 356
 357 #if HAVE_FUTEX_H
 358 template <typename T> inline void Parmap<T>::FutexSynchro::futex_wait(unsigned* uaddr, unsigned val)
 359 {
 360   XBT_CVERB(xbt_parmap, "Waiting on futex %p", uaddr);
 361   syscall(SYS_futex, uaddr, FUTEX_WAIT_PRIVATE, val, nullptr, nullptr, 0);
 362 }
 363
 364 template <typename T> inline void Parmap<T>::FutexSynchro::futex_wake(unsigned* uaddr, unsigned val)
 365 {
 366   XBT_CVERB(xbt_parmap, "Waking futex %p", uaddr);
 367   syscall(SYS_futex, uaddr, FUTEX_WAKE_PRIVATE, val, nullptr, nullptr, 0);
 368 }
 369
 370 template <typename T> void Parmap<T>::FutexSynchro::master_signal()
 371 {
 372   __atomic_store_n(&this->parmap.thread_counter, 1, __ATOMIC_SEQ_CST);
 373   __atomic_add_fetch(&this->parmap.work_round, 1, __ATOMIC_SEQ_CST);
 374   /* wake all workers */
 375   futex_wake(&this->parmap.work_round, std::numeric_limits<int>::max());
 376 }
 377
 378 template <typename T> void Parmap<T>::FutexSynchro::master_wait()
 379 {
 380   unsigned count = __atomic_load_n(&this->parmap.thread_counter, __ATOMIC_SEQ_CST);
 381   while (count < this->parmap.num_workers) {
 382     /* wait for all workers to be ready */
 383     futex_wait(&this->parmap.thread_counter, count);
 384     count = __atomic_load_n(&this->parmap.thread_counter, __ATOMIC_SEQ_CST);
 385   }
 386 }
 387
 388 template <typename T> void Parmap<T>::FutexSynchro::worker_signal()
 389 {
 390   unsigned count = __atomic_add_fetch(&this->parmap.thread_counter, 1, __ATOMIC_SEQ_CST);
 391   if (count == this->parmap.num_workers) {
 392     /* all workers have finished, wake the controller */
 393     futex_wake(&this->parmap.thread_counter, std::numeric_limits<int>::max());
 394   }
 395 }
 396
 397 template <typename T> void Parmap<T>::FutexSynchro::worker_wait(unsigned round)
 398 {
 399   unsigned work_round = __atomic_load_n(&this->parmap.work_round, __ATOMIC_SEQ_CST);
 400   /* wait for more work */
 401   while (work_round != round) {
 402     futex_wait(&this->parmap.work_round, work_round);
 403     work_round = __atomic_load_n(&this->parmap.work_round, __ATOMIC_SEQ_CST);
 404   }
 405 }
 406 #endif
 407
 408 template <typename T> void Parmap<T>::BusyWaitSynchro::master_signal()
 409 {
 410   __atomic_store_n(&this->parmap.thread_counter, 1, __ATOMIC_SEQ_CST);
 411   __atomic_add_fetch(&this->parmap.work_round, 1, __ATOMIC_SEQ_CST);
 412 }
 413
 414 template <typename T> void Parmap<T>::BusyWaitSynchro::master_wait()
 415 {
 416   while (__atomic_load_n(&this->parmap.thread_counter, __ATOMIC_SEQ_CST) < this->parmap.num_workers) {
 417     std::this_thread::yield();
 418   }
 419 }
 420
 421 template <typename T> void Parmap<T>::BusyWaitSynchro::worker_signal()
 422 {
 423   __atomic_add_fetch(&this->parmap.thread_counter, 1, __ATOMIC_SEQ_CST);
 424 }
 425
 426 template <typename T> void Parmap<T>::BusyWaitSynchro::worker_wait(unsigned round)
 427 {
 428   /* wait for more work */
 429   while (__atomic_load_n(&this->parmap.work_round, __ATOMIC_SEQ_CST) != round) {
 430     std::this_thread::yield();
 431   }
 432 }
 433
 434 /** @} */
 435 }
 436 }
 437
 438 #endif