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