src/include/xbt/parmap.hpp

   1 /* A thread pool (C++ version).                                             */
   2
   3 /* Copyright (c) 2004-2020 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 "src/simix/smx_private.hpp" /* simix_global */
  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 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);
 100     ~PosixSynchro();
 101     void master_signal() override;
 102     void master_wait() override;
 103     void worker_signal() override;
 104     void worker_wait(unsigned round) override;
 105
 106   private:
 107     std::condition_variable ready_cond;
 108     std::mutex ready_mutex;
 109     std::condition_variable done_cond;
 110     std::mutex done_mutex;
 111   };
 112
 113 #if HAVE_FUTEX_H
 114   class FutexSynchro : public Synchro {
 115   public:
 116     explicit FutexSynchro(Parmap<T>& parmap) : Synchro(parmap) {}
 117     void master_signal() override;
 118     void master_wait() override;
 119     void worker_signal() override;
 120     void worker_wait(unsigned) override;
 121
 122   private:
 123     static void futex_wait(std::atomic_uint* uaddr, unsigned val);
 124     static void futex_wake(std::atomic_uint* uaddr, unsigned val);
 125   };
 126 #endif
 127
 128   class BusyWaitSynchro : public Synchro {
 129   public:
 130     explicit BusyWaitSynchro(Parmap<T>& parmap) : Synchro(parmap) {}
 131     void master_signal() override;
 132     void master_wait() override;
 133     void worker_signal() override;
 134     void worker_wait(unsigned) override;
 135   };
 136
 137   static void worker_main(ThreadData* data);
 138   Synchro* new_synchro(e_xbt_parmap_mode_t mode);
 139   void work();
 140
 141   bool destroying = false;           /**< is the parmap being destroyed? */
 142   std::atomic_uint work_round{0};    /**< index of the current round */
 143   std::vector<std::thread*> workers; /**< worker thread handlers */
 144   unsigned num_workers;     /**< total number of worker threads including the controller */
 145   Synchro* synchro;         /**< synchronization object */
 146
 147   std::atomic_uint thread_counter{0};   /**< number of workers that have done the work */
 148   std::function<void(T)> fun;           /**< function to run in parallel on each element of data */
 149   const std::vector<T>* data = nullptr; /**< parameters to pass to fun in parallel */
 150   std::atomic_uint index{0};            /**< index of the next element of data to pick */
 151 };
 152
 153 /**
 154  * @brief Creates a parallel map object
 155  * @param num_workers number of worker threads to create
 156  * @param mode how to synchronize the worker threads
 157  */
 158 template <typename T> Parmap<T>::Parmap(unsigned num_workers, e_xbt_parmap_mode_t mode)
 159 {
 160   XBT_CDEBUG(xbt_parmap, "Create new parmap (%u workers)", num_workers);
 161
 162   /* Initialize the thread pool data structure */
 163   this->workers.resize(num_workers);
 164   this->num_workers = num_workers;
 165   this->synchro     = new_synchro(mode);
 166
 167   /* Create the pool of worker threads (the caller of apply() will be worker[0]) */
 168   this->workers[0] = nullptr;
 169
 170   for (unsigned i = 1; i < num_workers; i++) {
 171     ThreadData* data = new ThreadData(*this, i);
 172     this->workers[i] = new std::thread(worker_main, data);
 173
 174     /* Bind the worker to a core if possible */
 175 #if HAVE_PTHREAD_SETAFFINITY
 176 #if HAVE_PTHREAD_NP_H /* FreeBSD ? */
 177     cpuset_t cpuset;
 178     size_t size = sizeof(cpuset_t);
 179 #else /* Linux ? */
 180     cpu_set_t cpuset;
 181     size_t size = sizeof(cpu_set_t);
 182 #endif
 183     pthread_t pthread = this->workers[i]->native_handle();
 184     int core_bind     = (i - 1) % std::thread::hardware_concurrency();
 185     CPU_ZERO(&cpuset);
 186     CPU_SET(core_bind, &cpuset);
 187     pthread_setaffinity_np(pthread, size, &cpuset);
 188 #endif
 189   }
 190 }
 191
 192 /**
 193  * @brief Destroys a parmap
 194  */
 195 template <typename T> Parmap<T>::~Parmap()
 196 {
 197   destroying = true;
 198   synchro->master_signal();
 199
 200   for (unsigned i = 1; i < num_workers; i++) {
 201     workers[i]->join();
 202     delete workers[i];
 203   }
 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(std::function<void(T)>&& fun, const std::vector<T>& data)
 213 {
 214   /* Assign resources to worker threads (we are maestro here)*/
 215   this->fun   = std::move(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(ThreadData* data)
 289 {
 290   Parmap<T>& parmap     = data->parmap;
 291   unsigned round        = 0;
 292   kernel::context::Context* context = simix_global->context_factory->create_context(std::function<void()>(), nullptr);
 293   kernel::context::Context::set_current(context);
 294
 295   XBT_CDEBUG(xbt_parmap, "New worker thread created");
 296
 297   /* Worker's main loop */
 298   while (1) {
 299     round++; // New scheduling round
 300     parmap.synchro->worker_wait(round);
 301     if (parmap.destroying)
 302       break;
 303
 304     XBT_CDEBUG(xbt_parmap, "Worker %d got a job", data->worker_id);
 305     parmap.work();
 306     parmap.synchro->worker_signal();
 307     XBT_CDEBUG(xbt_parmap, "Worker %d has finished", data->worker_id);
 308   }
 309   /* We are destroying the parmap */
 310   delete context;
 311   delete data;
 312 }
 313
 314 template <typename T> Parmap<T>::PosixSynchro::PosixSynchro(Parmap<T>& parmap) : Synchro(parmap)
 315 {
 316 }
 317
 318 template <typename T> Parmap<T>::PosixSynchro::~PosixSynchro()
 319 {
 320 }
 321
 322 template <typename T> void Parmap<T>::PosixSynchro::master_signal()
 323 {
 324   std::unique_lock<std::mutex> lk(ready_mutex);
 325   this->parmap.thread_counter = 1;
 326   this->parmap.work_round++;
 327   /* wake all workers */
 328   ready_cond.notify_all();
 329 }
 330
 331 template <typename T> void Parmap<T>::PosixSynchro::master_wait()
 332 {
 333   std::unique_lock<std::mutex> lk(done_mutex);
 334   while (this->parmap.thread_counter < this->parmap.num_workers) {
 335     /* wait for all workers to be ready */
 336     done_cond.wait(lk);
 337   }
 338 }
 339
 340 template <typename T> void Parmap<T>::PosixSynchro::worker_signal()
 341 {
 342   std::unique_lock<std::mutex> lk(done_mutex);
 343   this->parmap.thread_counter++;
 344   if (this->parmap.thread_counter == this->parmap.num_workers) {
 345     /* all workers have finished, wake the controller */
 346     done_cond.notify_one();
 347   }
 348 }
 349
 350 template <typename T> void Parmap<T>::PosixSynchro::worker_wait(unsigned round)
 351 {
 352   std::unique_lock<std::mutex> lk(ready_mutex);
 353   /* wait for more work */
 354   while (this->parmap.work_round != round) {
 355     ready_cond.wait(lk);
 356   }
 357 }
 358
 359 #if HAVE_FUTEX_H
 360 template <typename T> inline void Parmap<T>::FutexSynchro::futex_wait(std::atomic_uint* uaddr, unsigned val)
 361 {
 362   XBT_CVERB(xbt_parmap, "Waiting on futex %p", uaddr);
 363   syscall(SYS_futex, uaddr, FUTEX_WAIT_PRIVATE, val, nullptr, nullptr, 0);
 364 }
 365
 366 template <typename T> inline void Parmap<T>::FutexSynchro::futex_wake(std::atomic_uint* uaddr, unsigned val)
 367 {
 368   XBT_CVERB(xbt_parmap, "Waking futex %p", uaddr);
 369   syscall(SYS_futex, uaddr, FUTEX_WAKE_PRIVATE, val, nullptr, nullptr, 0);
 370 }
 371
 372 template <typename T> void Parmap<T>::FutexSynchro::master_signal()
 373 {
 374   this->parmap.thread_counter.store(1);
 375   this->parmap.work_round.fetch_add(1);
 376   /* wake all workers */
 377   futex_wake(&this->parmap.work_round, std::numeric_limits<int>::max());
 378 }
 379
 380 template <typename T> void Parmap<T>::FutexSynchro::master_wait()
 381 {
 382   unsigned count = this->parmap.thread_counter.load();
 383   while (count < this->parmap.num_workers) {
 384     /* wait for all workers to be ready */
 385     futex_wait(&this->parmap.thread_counter, count);
 386     count = this->parmap.thread_counter.load();
 387   }
 388 }
 389
 390 template <typename T> void Parmap<T>::FutexSynchro::worker_signal()
 391 {
 392   unsigned count = this->parmap.thread_counter.fetch_add(1) + 1;
 393   if (count == this->parmap.num_workers) {
 394     /* all workers have finished, wake the controller */
 395     futex_wake(&this->parmap.thread_counter, std::numeric_limits<int>::max());
 396   }
 397 }
 398
 399 template <typename T> void Parmap<T>::FutexSynchro::worker_wait(unsigned round)
 400 {
 401   unsigned work_round = this->parmap.work_round.load();
 402   /* wait for more work */
 403   while (work_round != round) {
 404     futex_wait(&this->parmap.work_round, work_round);
 405     work_round = this->parmap.work_round.load();
 406   }
 407 }
 408 #endif
 409
 410 template <typename T> void Parmap<T>::BusyWaitSynchro::master_signal()
 411 {
 412   this->parmap.thread_counter.store(1);
 413   this->parmap.work_round.fetch_add(1);
 414 }
 415
 416 template <typename T> void Parmap<T>::BusyWaitSynchro::master_wait()
 417 {
 418   while (this->parmap.thread_counter.load() < this->parmap.num_workers) {
 419     std::this_thread::yield();
 420   }
 421 }
 422
 423 template <typename T> void Parmap<T>::BusyWaitSynchro::worker_signal()
 424 {
 425   this->parmap.thread_counter.fetch_add(1);
 426 }
 427
 428 template <typename T> void Parmap<T>::BusyWaitSynchro::worker_wait(unsigned round)
 429 {
 430   /* wait for more work */
 431   while (this->parmap.work_round.load() != round) {
 432     std::this_thread::yield();
 433   }
 434 }
 435
 436 /** @} */
 437 }
 438 }
 439
 440 #endif