src/include/xbt/parmap.hpp

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