src/include/xbt/parmap.hpp

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