1 /* A thread pool (C++ version). */
3 /* Copyright (c) 2004-2018 The SimGrid Team. All rights reserved. */
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. */
11 #include "src/internal_config.h" // HAVE_FUTEX_H
12 #include "src/kernel/context/Context.hpp"
13 #include "xbt/xbt_os_thread.h"
15 #include <boost/optional.hpp>
18 #include <linux/futex.h>
19 #include <sys/syscall.h>
22 XBT_LOG_EXTERNAL_CATEGORY(xbt_parmap);
27 /** @addtogroup XBT_parmap
29 * @brief Parallel map class
32 template <typename T> class Parmap {
34 Parmap(unsigned num_workers, e_xbt_parmap_mode_t mode);
35 Parmap(const Parmap&) = delete;
36 Parmap& operator=(const Parmap&) = delete;
38 void apply(void (*fun)(T), const std::vector<T>& data);
39 boost::optional<T> next();
42 enum Flag { PARMAP_WORK, PARMAP_DESTROY };
45 * @brief Thread data transmission structure
49 ThreadData(Parmap<T>& parmap, int id) : parmap(parmap), worker_id(id) {}
55 * @brief Synchronization object (different specializations).
59 explicit Synchro(Parmap<T>& parmap) : parmap(parmap) {}
60 virtual ~Synchro() = default;
62 * @brief Wakes all workers and waits for them to finish the tasks.
64 * This function is called by the controller thread.
66 virtual void master_signal() = 0;
68 * @brief Starts the parmap: waits for all workers to be ready and returns.
70 * This function is called by the controller thread.
72 virtual void master_wait() = 0;
74 * @brief Ends the parmap: wakes the controller thread when all workers terminate.
76 * This function is called by all worker threads when they end (not including the controller).
78 virtual void worker_signal() = 0;
80 * @brief Waits for some work to process.
82 * This function is called by each worker thread (not including the controller) when it has no more work to do.
84 * @param round the expected round number
86 virtual void worker_wait(unsigned) = 0;
91 class PosixSynchro : public Synchro {
93 explicit PosixSynchro(Parmap<T>& parmap);
98 void worker_wait(unsigned round);
101 xbt_os_cond_t ready_cond;
102 xbt_os_mutex_t ready_mutex;
103 xbt_os_cond_t done_cond;
104 xbt_os_mutex_t done_mutex;
108 class FutexSynchro : public Synchro {
110 explicit FutexSynchro(Parmap<T>& parmap) : Synchro(parmap) {}
111 void master_signal();
113 void worker_signal();
114 void worker_wait(unsigned);
117 static void futex_wait(unsigned* uaddr, unsigned val);
118 static void futex_wake(unsigned* uaddr, unsigned val);
122 class BusyWaitSynchro : public Synchro {
124 explicit BusyWaitSynchro(Parmap<T>& parmap) : Synchro(parmap) {}
125 void master_signal();
127 void worker_signal();
128 void worker_wait(unsigned);
131 static void* worker_main(void* arg);
132 Synchro* new_synchro(e_xbt_parmap_mode_t mode);
135 Flag status; /**< is the parmap active or being destroyed? */
136 unsigned work_round; /**< index of the current round */
137 xbt_os_thread_t* workers; /**< worker thread handlers */
138 unsigned num_workers; /**< total number of worker threads including the controller */
139 Synchro* synchro; /**< synchronization object */
141 unsigned thread_counter = 0; /**< number of workers that have done the work */
142 void (*fun)(const T) = nullptr; /**< function to run in parallel on each element of data */
143 const std::vector<T>* data = nullptr; /**< parameters to pass to fun in parallel */
144 std::atomic<unsigned> index; /**< index of the next element of data to pick */
148 * @brief Creates a parallel map object
149 * @param num_workers number of worker threads to create
150 * @param mode how to synchronize the worker threads
152 template <typename T> Parmap<T>::Parmap(unsigned num_workers, e_xbt_parmap_mode_t mode)
154 XBT_CDEBUG(xbt_parmap, "Create new parmap (%u workers)", num_workers);
156 /* Initialize the thread pool data structure */
157 this->status = PARMAP_WORK;
158 this->work_round = 0;
159 this->workers = new xbt_os_thread_t[num_workers];
160 this->num_workers = num_workers;
161 this->synchro = new_synchro(mode);
163 /* Create the pool of worker threads */
164 this->workers[0] = nullptr;
165 #if HAVE_PTHREAD_SETAFFINITY
168 for (unsigned i = 1; i < num_workers; i++) {
169 ThreadData* data = new ThreadData(*this, i);
170 this->workers[i] = xbt_os_thread_create(nullptr, worker_main, data, nullptr);
171 #if HAVE_PTHREAD_SETAFFINITY
172 xbt_os_thread_bind(this->workers[i], core_bind);
173 if (core_bind != xbt_os_get_numcores() - 1)
182 * @brief Destroys a parmap
184 template <typename T> Parmap<T>::~Parmap()
186 status = PARMAP_DESTROY;
187 synchro->master_signal();
189 for (unsigned i = 1; i < num_workers; i++)
190 xbt_os_thread_join(workers[i], nullptr);
197 * @brief Applies a list of tasks in parallel.
198 * @param fun the function to call in parallel
199 * @param data each element of this vector will be passed as an argument to fun
201 template <typename T> void Parmap<T>::apply(void (*fun)(T), const std::vector<T>& data)
203 /* Assign resources to worker threads (we are maestro here)*/
207 this->synchro->master_signal(); // maestro runs futex_wake to wake all the minions (the working threads)
208 this->work(); // maestro works with its minions
209 this->synchro->master_wait(); // When there is no more work to do, then maestro waits for the last minion to stop
210 XBT_CDEBUG(xbt_parmap, "Job done"); // ... and proceeds
214 * @brief Returns a next task to process.
216 * Worker threads call this function to get more work.
218 * @return the next task to process, or throws a std::out_of_range exception if there is no more work
220 template <typename T> boost::optional<T> Parmap<T>::next()
222 unsigned index = this->index.fetch_add(1, std::memory_order_relaxed);
223 if (index < this->data->size())
224 return (*this->data)[index];
230 * @brief Main work loop: applies fun to elements in turn.
232 template <typename T> void Parmap<T>::work()
234 unsigned length = this->data->size();
235 unsigned index = this->index.fetch_add(1, std::memory_order_relaxed);
236 while (index < length) {
237 this->fun((*this->data)[index]);
238 index = this->index.fetch_add(1, std::memory_order_relaxed);
243 * Get a synchronization object for given mode.
244 * @param mode the synchronization mode
246 template <typename T> typename Parmap<T>::Synchro* Parmap<T>::new_synchro(e_xbt_parmap_mode_t mode)
248 if (mode == XBT_PARMAP_DEFAULT) {
250 mode = XBT_PARMAP_FUTEX;
252 mode = XBT_PARMAP_POSIX;
257 case XBT_PARMAP_POSIX:
258 res = new PosixSynchro(*this);
260 case XBT_PARMAP_FUTEX:
262 res = new FutexSynchro(*this);
264 xbt_die("Futex is not available on this OS.");
267 case XBT_PARMAP_BUSY_WAIT:
268 res = new BusyWaitSynchro(*this);
277 * @brief Main function of a worker thread.
279 template <typename T> void* Parmap<T>::worker_main(void* arg)
281 ThreadData* data = static_cast<ThreadData*>(arg);
282 Parmap<T>& parmap = data->parmap;
284 smx_context_t context = SIMIX_context_new(std::function<void()>(), nullptr, nullptr);
285 SIMIX_context_set_current(context);
287 XBT_CDEBUG(xbt_parmap, "New worker thread created");
289 /* Worker's main loop */
292 parmap.synchro->worker_wait(round);
293 if (parmap.status == PARMAP_DESTROY)
296 XBT_CDEBUG(xbt_parmap, "Worker %d got a job", data->worker_id);
298 parmap.synchro->worker_signal();
299 XBT_CDEBUG(xbt_parmap, "Worker %d has finished", data->worker_id);
301 /* We are destroying the parmap */
307 template <typename T> Parmap<T>::PosixSynchro::PosixSynchro(Parmap<T>& parmap) : Synchro(parmap)
309 ready_cond = xbt_os_cond_init();
310 ready_mutex = xbt_os_mutex_init();
311 done_cond = xbt_os_cond_init();
312 done_mutex = xbt_os_mutex_init();
315 template <typename T> Parmap<T>::PosixSynchro::~PosixSynchro()
317 xbt_os_cond_destroy(ready_cond);
318 xbt_os_mutex_destroy(ready_mutex);
319 xbt_os_cond_destroy(done_cond);
320 xbt_os_mutex_destroy(done_mutex);
323 template <typename T> void Parmap<T>::PosixSynchro::master_signal()
325 xbt_os_mutex_acquire(ready_mutex);
326 this->parmap.thread_counter = 1;
327 this->parmap.work_round++;
328 /* wake all workers */
329 xbt_os_cond_broadcast(ready_cond);
330 xbt_os_mutex_release(ready_mutex);
333 template <typename T> void Parmap<T>::PosixSynchro::master_wait()
335 xbt_os_mutex_acquire(done_mutex);
336 while (this->parmap.thread_counter < this->parmap.num_workers) {
337 /* wait for all workers to be ready */
338 xbt_os_cond_wait(done_cond, done_mutex);
340 xbt_os_mutex_release(done_mutex);
343 template <typename T> void Parmap<T>::PosixSynchro::worker_signal()
345 xbt_os_mutex_acquire(done_mutex);
346 this->parmap.thread_counter++;
347 if (this->parmap.thread_counter == this->parmap.num_workers) {
348 /* all workers have finished, wake the controller */
349 xbt_os_cond_signal(done_cond);
351 xbt_os_mutex_release(done_mutex);
354 template <typename T> void Parmap<T>::PosixSynchro::worker_wait(unsigned round)
356 xbt_os_mutex_acquire(ready_mutex);
357 /* wait for more work */
358 while (this->parmap.work_round != round) {
359 xbt_os_cond_wait(ready_cond, ready_mutex);
361 xbt_os_mutex_release(ready_mutex);
365 template <typename T> inline void Parmap<T>::FutexSynchro::futex_wait(unsigned* uaddr, unsigned val)
367 XBT_CVERB(xbt_parmap, "Waiting on futex %p", uaddr);
368 syscall(SYS_futex, uaddr, FUTEX_WAIT_PRIVATE, val, nullptr, nullptr, 0);
371 template <typename T> inline void Parmap<T>::FutexSynchro::futex_wake(unsigned* uaddr, unsigned val)
373 XBT_CVERB(xbt_parmap, "Waking futex %p", uaddr);
374 syscall(SYS_futex, uaddr, FUTEX_WAKE_PRIVATE, val, nullptr, nullptr, 0);
377 template <typename T> void Parmap<T>::FutexSynchro::master_signal()
379 __atomic_store_n(&this->parmap.thread_counter, 1, __ATOMIC_SEQ_CST);
380 __atomic_add_fetch(&this->parmap.work_round, 1, __ATOMIC_SEQ_CST);
381 /* wake all workers */
382 futex_wake(&this->parmap.work_round, std::numeric_limits<int>::max());
385 template <typename T> void Parmap<T>::FutexSynchro::master_wait()
387 unsigned count = __atomic_load_n(&this->parmap.thread_counter, __ATOMIC_SEQ_CST);
388 while (count < this->parmap.num_workers) {
389 /* wait for all workers to be ready */
390 futex_wait(&this->parmap.thread_counter, count);
391 count = __atomic_load_n(&this->parmap.thread_counter, __ATOMIC_SEQ_CST);
395 template <typename T> void Parmap<T>::FutexSynchro::worker_signal()
397 unsigned count = __atomic_add_fetch(&this->parmap.thread_counter, 1, __ATOMIC_SEQ_CST);
398 if (count == this->parmap.num_workers) {
399 /* all workers have finished, wake the controller */
400 futex_wake(&this->parmap.thread_counter, std::numeric_limits<int>::max());
404 template <typename T> void Parmap<T>::FutexSynchro::worker_wait(unsigned round)
406 unsigned work_round = __atomic_load_n(&this->parmap.work_round, __ATOMIC_SEQ_CST);
407 /* wait for more work */
408 while (work_round != round) {
409 futex_wait(&this->parmap.work_round, work_round);
410 work_round = __atomic_load_n(&this->parmap.work_round, __ATOMIC_SEQ_CST);
415 template <typename T> void Parmap<T>::BusyWaitSynchro::master_signal()
417 __atomic_store_n(&this->parmap.thread_counter, 1, __ATOMIC_SEQ_CST);
418 __atomic_add_fetch(&this->parmap.work_round, 1, __ATOMIC_SEQ_CST);
421 template <typename T> void Parmap<T>::BusyWaitSynchro::master_wait()
423 while (__atomic_load_n(&this->parmap.thread_counter, __ATOMIC_SEQ_CST) < this->parmap.num_workers) {
424 xbt_os_thread_yield();
428 template <typename T> void Parmap<T>::BusyWaitSynchro::worker_signal()
430 __atomic_add_fetch(&this->parmap.thread_counter, 1, __ATOMIC_SEQ_CST);
433 template <typename T> void Parmap<T>::BusyWaitSynchro::worker_wait(unsigned round)
435 /* wait for more work */
436 while (__atomic_load_n(&this->parmap.work_round, __ATOMIC_SEQ_CST) != round) {
437 xbt_os_thread_yield();