Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
18bf58d4962883f83cd38c5b391c159adca27bf2
[simgrid.git] / 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   /**
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;                   /**< is the parmap being destroyed? */
142   std::atomic_uint work_round;       /**< 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;               /**< 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->destroying  = false;
164   this->work_round  = 0;
165   this->workers.resize(num_workers);
166   this->num_workers = num_workers;
167   this->synchro     = new_synchro(mode);
168
169   /* Create the pool of worker threads (the caller of apply() will be worker[0]) */
170   this->workers[0] = nullptr;
171   XBT_ATTRIB_UNUSED unsigned int core_bind = 0;
172
173   for (unsigned i = 1; i < num_workers; i++) {
174     ThreadData* data = new ThreadData(*this, i);
175     this->workers[i] = new std::thread(worker_main, data);
176
177     /* Bind the worker to a core if possible */
178 #if HAVE_PTHREAD_SETAFFINITY
179 #if HAVE_PTHREAD_NP_H /* FreeBSD ? */
180     cpuset_t cpuset;
181     size_t size = sizeof(cpuset_t);
182 #else /* Linux ? */
183     cpu_set_t cpuset;
184     size_t size = sizeof(cpu_set_t);
185 #endif
186     pthread_t pthread = this->workers[i]->native_handle();
187     CPU_ZERO(&cpuset);
188     CPU_SET(core_bind, &cpuset);
189     pthread_setaffinity_np(pthread, size, &cpuset);
190     if (core_bind != std::thread::hardware_concurrency() - 1)
191       core_bind++;
192     else
193       core_bind = 0;
194 #endif
195   }
196 }
197
198 /**
199  * @brief Destroys a parmap
200  */
201 template <typename T> Parmap<T>::~Parmap()
202 {
203   destroying = true;
204   synchro->master_signal();
205
206   for (unsigned i = 1; i < num_workers; i++) {
207     workers[i]->join();
208     delete workers[i];
209   }
210   delete synchro;
211 }
212
213 /**
214  * @brief Applies a list of tasks in parallel.
215  * @param fun the function to call in parallel
216  * @param data each element of this vector will be passed as an argument to fun
217  */
218 template <typename T> void Parmap<T>::apply(std::function<void(T)>&& fun, const std::vector<T>& data)
219 {
220   /* Assign resources to worker threads (we are maestro here)*/
221   this->fun   = std::move(fun);
222   this->data  = &data;
223   this->index = 0;
224   this->synchro->master_signal(); // maestro runs futex_wake to wake all the minions (the working threads)
225   this->work();                   // maestro works with its minions
226   this->synchro->master_wait();   // When there is no more work to do, then maestro waits for the last minion to stop
227   XBT_CDEBUG(xbt_parmap, "Job done"); //   ... and proceeds
228 }
229
230 /**
231  * @brief Returns a next task to process.
232  *
233  * Worker threads call this function to get more work.
234  *
235  * @return the next task to process, or throws a std::out_of_range exception if there is no more work
236  */
237 template <typename T> boost::optional<T> Parmap<T>::next()
238 {
239   unsigned index = this->index.fetch_add(1, std::memory_order_relaxed);
240   if (index < this->data->size())
241     return (*this->data)[index];
242   else
243     return boost::none;
244 }
245
246 /**
247  * @brief Main work loop: applies fun to elements in turn.
248  */
249 template <typename T> void Parmap<T>::work()
250 {
251   unsigned length = this->data->size();
252   unsigned index  = this->index.fetch_add(1, std::memory_order_relaxed);
253   while (index < length) {
254     this->fun((*this->data)[index]);
255     index = this->index.fetch_add(1, std::memory_order_relaxed);
256   }
257 }
258
259 /**
260  * Get a synchronization object for given mode.
261  * @param mode the synchronization mode
262  */
263 template <typename T> typename Parmap<T>::Synchro* Parmap<T>::new_synchro(e_xbt_parmap_mode_t mode)
264 {
265   if (mode == XBT_PARMAP_DEFAULT) {
266 #if HAVE_FUTEX_H
267     mode = XBT_PARMAP_FUTEX;
268 #else
269     mode = XBT_PARMAP_POSIX;
270 #endif
271   }
272   Synchro* res;
273   switch (mode) {
274     case XBT_PARMAP_POSIX:
275       res = new PosixSynchro(*this);
276       break;
277     case XBT_PARMAP_FUTEX:
278 #if HAVE_FUTEX_H
279       res = new FutexSynchro(*this);
280 #else
281       xbt_die("Futex is not available on this OS.");
282 #endif
283       break;
284     case XBT_PARMAP_BUSY_WAIT:
285       res = new BusyWaitSynchro(*this);
286       break;
287     default:
288       THROW_IMPOSSIBLE;
289   }
290   return res;
291 }
292
293 /** @brief Main function of a worker thread */
294 template <typename T> void Parmap<T>::worker_main(ThreadData* data)
295 {
296   Parmap<T>& parmap     = data->parmap;
297   unsigned round        = 0;
298   kernel::context::Context* context = simix_global->context_factory->create_context(std::function<void()>(), nullptr);
299   kernel::context::Context::set_current(context);
300
301   XBT_CDEBUG(xbt_parmap, "New worker thread created");
302
303   /* Worker's main loop */
304   while (1) {
305     round++; // New scheduling round
306     parmap.synchro->worker_wait(round);
307     if (parmap.destroying)
308       break;
309
310     XBT_CDEBUG(xbt_parmap, "Worker %d got a job", data->worker_id);
311     parmap.work();
312     parmap.synchro->worker_signal();
313     XBT_CDEBUG(xbt_parmap, "Worker %d has finished", data->worker_id);
314   }
315   /* We are destroying the parmap */
316   delete context;
317   delete data;
318 }
319
320 template <typename T> Parmap<T>::PosixSynchro::PosixSynchro(Parmap<T>& parmap) : Synchro(parmap)
321 {
322 }
323
324 template <typename T> Parmap<T>::PosixSynchro::~PosixSynchro()
325 {
326 }
327
328 template <typename T> void Parmap<T>::PosixSynchro::master_signal()
329 {
330   std::unique_lock<std::mutex> lk(ready_mutex);
331   this->parmap.thread_counter = 1;
332   this->parmap.work_round++;
333   /* wake all workers */
334   ready_cond.notify_all();
335 }
336
337 template <typename T> void Parmap<T>::PosixSynchro::master_wait()
338 {
339   std::unique_lock<std::mutex> lk(done_mutex);
340   while (this->parmap.thread_counter < this->parmap.num_workers) {
341     /* wait for all workers to be ready */
342     done_cond.wait(lk);
343   }
344 }
345
346 template <typename T> void Parmap<T>::PosixSynchro::worker_signal()
347 {
348   std::unique_lock<std::mutex> lk(done_mutex);
349   this->parmap.thread_counter++;
350   if (this->parmap.thread_counter == this->parmap.num_workers) {
351     /* all workers have finished, wake the controller */
352     done_cond.notify_one();
353   }
354 }
355
356 template <typename T> void Parmap<T>::PosixSynchro::worker_wait(unsigned round)
357 {
358   std::unique_lock<std::mutex> lk(ready_mutex);
359   /* wait for more work */
360   while (this->parmap.work_round != round) {
361     ready_cond.wait(lk);
362   }
363 }
364
365 #if HAVE_FUTEX_H
366 template <typename T> inline void Parmap<T>::FutexSynchro::futex_wait(std::atomic_uint* uaddr, unsigned val)
367 {
368   XBT_CVERB(xbt_parmap, "Waiting on futex %p", uaddr);
369   syscall(SYS_futex, uaddr, FUTEX_WAIT_PRIVATE, val, nullptr, nullptr, 0);
370 }
371
372 template <typename T> inline void Parmap<T>::FutexSynchro::futex_wake(std::atomic_uint* uaddr, unsigned val)
373 {
374   XBT_CVERB(xbt_parmap, "Waking futex %p", uaddr);
375   syscall(SYS_futex, uaddr, FUTEX_WAKE_PRIVATE, val, nullptr, nullptr, 0);
376 }
377
378 template <typename T> void Parmap<T>::FutexSynchro::master_signal()
379 {
380   this->parmap.thread_counter.store(1);
381   this->parmap.work_round.fetch_add(1);
382   /* wake all workers */
383   futex_wake(&this->parmap.work_round, std::numeric_limits<int>::max());
384 }
385
386 template <typename T> void Parmap<T>::FutexSynchro::master_wait()
387 {
388   unsigned count = this->parmap.thread_counter.load();
389   while (count < this->parmap.num_workers) {
390     /* wait for all workers to be ready */
391     futex_wait(&this->parmap.thread_counter, count);
392     count = this->parmap.thread_counter.load();
393   }
394 }
395
396 template <typename T> void Parmap<T>::FutexSynchro::worker_signal()
397 {
398   unsigned count = this->parmap.thread_counter.fetch_add(1) + 1;
399   if (count == this->parmap.num_workers) {
400     /* all workers have finished, wake the controller */
401     futex_wake(&this->parmap.thread_counter, std::numeric_limits<int>::max());
402   }
403 }
404
405 template <typename T> void Parmap<T>::FutexSynchro::worker_wait(unsigned round)
406 {
407   unsigned work_round = this->parmap.work_round.load();
408   /* wait for more work */
409   while (work_round != round) {
410     futex_wait(&this->parmap.work_round, work_round);
411     work_round = this->parmap.work_round.load();
412   }
413 }
414 #endif
415
416 template <typename T> void Parmap<T>::BusyWaitSynchro::master_signal()
417 {
418   this->parmap.thread_counter.store(1);
419   this->parmap.work_round.fetch_add(1);
420 }
421
422 template <typename T> void Parmap<T>::BusyWaitSynchro::master_wait()
423 {
424   while (this->parmap.thread_counter.load() < this->parmap.num_workers) {
425     std::this_thread::yield();
426   }
427 }
428
429 template <typename T> void Parmap<T>::BusyWaitSynchro::worker_signal()
430 {
431   this->parmap.thread_counter.fetch_add(1);
432 }
433
434 template <typename T> void Parmap<T>::BusyWaitSynchro::worker_wait(unsigned round)
435 {
436   /* wait for more work */
437   while (this->parmap.work_round.load() != round) {
438     std::this_thread::yield();
439   }
440 }
441
442 /** @} */
443 }
444 }
445
446 #endif