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