Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
cosmetics
[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 "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.resize(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 #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   status = PARMAP_DESTROY;
204   synchro->master_signal();
205
206   for (unsigned i = 1; i < num_workers; i++)
207     workers[i]->join();
208
209   delete synchro;
210 }
211
212 /**
213  * @brief Applies a list of tasks in parallel.
214  * @param fun the function to call in parallel
215  * @param data each element of this vector will be passed as an argument to fun
216  */
217 template <typename T> void Parmap<T>::apply(void (*fun)(T), const std::vector<T>& data)
218 {
219   /* Assign resources to worker threads (we are maestro here)*/
220   this->fun   = fun;
221   this->data  = &data;
222   this->index = 0;
223   this->synchro->master_signal(); // maestro runs futex_wake to wake all the minions (the working threads)
224   this->work();                   // maestro works with its minions
225   this->synchro->master_wait();   // When there is no more work to do, then maestro waits for the last minion to stop
226   XBT_CDEBUG(xbt_parmap, "Job done"); //   ... and proceeds
227 }
228
229 /**
230  * @brief Returns a next task to process.
231  *
232  * Worker threads call this function to get more work.
233  *
234  * @return the next task to process, or throws a std::out_of_range exception if there is no more work
235  */
236 template <typename T> boost::optional<T> Parmap<T>::next()
237 {
238   unsigned index = this->index.fetch_add(1, std::memory_order_relaxed);
239   if (index < this->data->size())
240     return (*this->data)[index];
241   else
242     return boost::none;
243 }
244
245 /**
246  * @brief Main work loop: applies fun to elements in turn.
247  */
248 template <typename T> void Parmap<T>::work()
249 {
250   unsigned length = this->data->size();
251   unsigned index  = this->index.fetch_add(1, std::memory_order_relaxed);
252   while (index < length) {
253     this->fun((*this->data)[index]);
254     index = this->index.fetch_add(1, std::memory_order_relaxed);
255   }
256 }
257
258 /**
259  * Get a synchronization object for given mode.
260  * @param mode the synchronization mode
261  */
262 template <typename T> typename Parmap<T>::Synchro* Parmap<T>::new_synchro(e_xbt_parmap_mode_t mode)
263 {
264   if (mode == XBT_PARMAP_DEFAULT) {
265 #if HAVE_FUTEX_H
266     mode = XBT_PARMAP_FUTEX;
267 #else
268     mode = XBT_PARMAP_POSIX;
269 #endif
270   }
271   Synchro* res;
272   switch (mode) {
273     case XBT_PARMAP_POSIX:
274       res = new PosixSynchro(*this);
275       break;
276     case XBT_PARMAP_FUTEX:
277 #if HAVE_FUTEX_H
278       res = new FutexSynchro(*this);
279 #else
280       xbt_die("Futex is not available on this OS.");
281 #endif
282       break;
283     case XBT_PARMAP_BUSY_WAIT:
284       res = new BusyWaitSynchro(*this);
285       break;
286     default:
287       THROW_IMPOSSIBLE;
288   }
289   return res;
290 }
291
292 /** @brief Main function of a worker thread */
293 template <typename T> void* Parmap<T>::worker_main(void* arg)
294 {
295   ThreadData* data      = static_cast<ThreadData*>(arg);
296   Parmap<T>& parmap     = data->parmap;
297   unsigned round        = 0;
298   smx_context_t context = SIMIX_context_new(std::function<void()>(), nullptr, 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.status == PARMAP_DESTROY)
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   return nullptr;
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(unsigned* 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(unsigned* 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   __atomic_store_n(&this->parmap.thread_counter, 1, __ATOMIC_SEQ_CST);
382   __atomic_add_fetch(&this->parmap.work_round, 1, __ATOMIC_SEQ_CST);
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 = __atomic_load_n(&this->parmap.thread_counter, __ATOMIC_SEQ_CST);
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 = __atomic_load_n(&this->parmap.thread_counter, __ATOMIC_SEQ_CST);
394   }
395 }
396
397 template <typename T> void Parmap<T>::FutexSynchro::worker_signal()
398 {
399   unsigned count = __atomic_add_fetch(&this->parmap.thread_counter, 1, __ATOMIC_SEQ_CST);
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 = __atomic_load_n(&this->parmap.work_round, __ATOMIC_SEQ_CST);
409   /* wait for more work */
410   while (work_round != round) {
411     futex_wait(&this->parmap.work_round, work_round);
412     work_round = __atomic_load_n(&this->parmap.work_round, __ATOMIC_SEQ_CST);
413   }
414 }
415 #endif
416
417 template <typename T> void Parmap<T>::BusyWaitSynchro::master_signal()
418 {
419   __atomic_store_n(&this->parmap.thread_counter, 1, __ATOMIC_SEQ_CST);
420   __atomic_add_fetch(&this->parmap.work_round, 1, __ATOMIC_SEQ_CST);
421 }
422
423 template <typename T> void Parmap<T>::BusyWaitSynchro::master_wait()
424 {
425   while (__atomic_load_n(&this->parmap.thread_counter, __ATOMIC_SEQ_CST) < this->parmap.num_workers) {
426     std::this_thread::yield();
427   }
428 }
429
430 template <typename T> void Parmap<T>::BusyWaitSynchro::worker_signal()
431 {
432   __atomic_add_fetch(&this->parmap.thread_counter, 1, __ATOMIC_SEQ_CST);
433 }
434
435 template <typename T> void Parmap<T>::BusyWaitSynchro::worker_wait(unsigned round)
436 {
437   /* wait for more work */
438   while (__atomic_load_n(&this->parmap.work_round, __ATOMIC_SEQ_CST) != round) {
439     std::this_thread::yield();
440   }
441 }
442
443 /** @} */
444 }
445 }
446
447 #endif