From: Arnaud Giersch Date: Wed, 1 Feb 2012 08:21:45 +0000 (+0100) Subject: Parmap review. X-Git-Tag: exp_20120216~97^2~2 X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/commitdiff_plain/bfa784e73f294ed9a40417bfbed3d3d2a76ca86b Parmap review. * synchronizations are made a bit simpler; * helper functions are renamed for more clarity; * synchronization at the end of xbt_parmap_new() is removed; * the working loop is made faster by manually inlining xbt_parmap_next(); * finally, the posix mode is fixed. --- diff --git a/src/xbt/parmap.c b/src/xbt/parmap.c index 13c7baf7d0..fa073e8e2e 100644 --- a/src/xbt/parmap.c +++ b/src/xbt/parmap.c @@ -25,40 +25,41 @@ XBT_LOG_NEW_DEFAULT_SUBCATEGORY(xbt_parmap, xbt, "parmap: parallel map"); XBT_LOG_NEW_SUBCATEGORY(xbt_parmap_unit, xbt_parmap, "parmap unit testing"); typedef enum { - XBT_PARMAP_WORK = 0, + XBT_PARMAP_WORK, XBT_PARMAP_DESTROY } e_xbt_parmap_flag_t; static void xbt_parmap_set_mode(xbt_parmap_t parmap, e_xbt_parmap_mode_t mode); static void *xbt_parmap_worker_main(void *parmap); +static void xbt_parmap_work(xbt_parmap_t parmap); -static void xbt_parmap_posix_start(xbt_parmap_t parmap); -static void xbt_parmap_posix_end(xbt_parmap_t parmap); -static void xbt_parmap_posix_signal(xbt_parmap_t parmap); -static void xbt_parmap_posix_wait(xbt_parmap_t parmap); +static void xbt_parmap_posix_master_wait(xbt_parmap_t parmap); +static void xbt_parmap_posix_worker_signal(xbt_parmap_t parmap); +static void xbt_parmap_posix_master_signal(xbt_parmap_t parmap); +static void xbt_parmap_posix_worker_wait(xbt_parmap_t parmap, unsigned round); #ifdef HAVE_FUTEX_H -static void xbt_parmap_futex_start(xbt_parmap_t parmap); -static void xbt_parmap_futex_end(xbt_parmap_t parmap); -static void xbt_parmap_futex_signal(xbt_parmap_t parmap); -static void xbt_parmap_futex_wait(xbt_parmap_t parmap); -static void futex_wait(int *uaddr, int val); -static void futex_wake(int *uaddr, int val); +static void xbt_parmap_futex_master_wait(xbt_parmap_t parmap); +static void xbt_parmap_futex_worker_signal(xbt_parmap_t parmap); +static void xbt_parmap_futex_master_signal(xbt_parmap_t parmap); +static void xbt_parmap_futex_worker_wait(xbt_parmap_t parmap, unsigned round); +static void futex_wait(unsigned *uaddr, unsigned val); +static void futex_wake(unsigned *uaddr, unsigned val); #endif -static void xbt_parmap_busy_start(xbt_parmap_t parmap); -static void xbt_parmap_busy_end(xbt_parmap_t parmap); -static void xbt_parmap_busy_signal(xbt_parmap_t parmap); -static void xbt_parmap_busy_wait(xbt_parmap_t parmap); +static void xbt_parmap_busy_master_wait(xbt_parmap_t parmap); +static void xbt_parmap_busy_worker_signal(xbt_parmap_t parmap); +static void xbt_parmap_busy_master_signal(xbt_parmap_t parmap); +static void xbt_parmap_busy_worker_wait(xbt_parmap_t parmap, unsigned round); /** * \brief Parallel map structure */ typedef struct s_xbt_parmap { e_xbt_parmap_flag_t status; /**< is the parmap active or being destroyed? */ - int work; /**< index of the current round (1 is the first) */ - int done; /**< number of rounds already done (futexes only) */ - unsigned int thread_counter; /**< number of threads currently working */ + unsigned work; /**< index of the current round */ + unsigned thread_counter; /**< number of workers that have done the work */ + unsigned int num_workers; /**< total number of worker threads including the controller */ void_f_pvoid_t fun; /**< function to run in parallel on each element of data */ xbt_dynar_t data; /**< parameters to pass to fun in parallel */ @@ -72,10 +73,10 @@ typedef struct s_xbt_parmap { /* fields that depend on the synchronization mode */ e_xbt_parmap_mode_t mode; /**< synchronization mode */ - void (*start_f)(xbt_parmap_t); /**< initializes the worker threads */ - void (*end_f)(xbt_parmap_t); /**< finalizes the worker threads */ - void (*signal_f)(xbt_parmap_t); /**< wakes the workers threads to process tasks */ - void (*wait_f)(xbt_parmap_t); /**< waits for more work */ + void (*master_wait_f)(xbt_parmap_t); /**< wait for the workers to have done the work */ + void (*worker_signal_f)(xbt_parmap_t); /**< signal the master that a worker has done the work */ + void (*master_signal_f)(xbt_parmap_t); /**< wakes the workers threads to process tasks */ + void (*worker_wait_f)(xbt_parmap_t, unsigned); /**< waits for more work */ } s_xbt_parmap_t; /** @@ -99,11 +100,10 @@ xbt_parmap_t xbt_parmap_new(unsigned int num_workers, e_xbt_parmap_mode_t mode) xbt_parmap_set_mode(parmap, mode); /* Create the pool of worker threads */ - for (i = 0; i < num_workers - 1; i++) { + for (i = 1; i < num_workers; i++) { worker = xbt_os_thread_create(NULL, xbt_parmap_worker_main, parmap, NULL); xbt_os_thread_detach(worker); } - parmap->start_f(parmap); return parmap; } @@ -118,7 +118,8 @@ void xbt_parmap_destroy(xbt_parmap_t parmap) } parmap->status = XBT_PARMAP_DESTROY; - parmap->signal_f(parmap); + parmap->master_signal_f(parmap); + parmap->master_wait_f(parmap); xbt_os_cond_destroy(parmap->ready_cond); xbt_os_mutex_destroy(parmap->ready_mutex); @@ -147,10 +148,10 @@ static void xbt_parmap_set_mode(xbt_parmap_t parmap, e_xbt_parmap_mode_t mode) switch (mode) { case XBT_PARMAP_POSIX: - parmap->start_f = xbt_parmap_posix_start; - parmap->end_f = xbt_parmap_posix_end; - parmap->signal_f = xbt_parmap_posix_signal; - parmap->wait_f = xbt_parmap_posix_wait; + parmap->master_wait_f = xbt_parmap_posix_master_wait; + parmap->worker_signal_f = xbt_parmap_posix_worker_signal; + parmap->master_signal_f = xbt_parmap_posix_master_signal; + parmap->worker_wait_f = xbt_parmap_posix_worker_wait; parmap->ready_cond = xbt_os_cond_init(); parmap->ready_mutex = xbt_os_mutex_init(); @@ -161,10 +162,10 @@ static void xbt_parmap_set_mode(xbt_parmap_t parmap, e_xbt_parmap_mode_t mode) case XBT_PARMAP_FUTEX: #ifdef HAVE_FUTEX_H - parmap->start_f = xbt_parmap_futex_start; - parmap->end_f = xbt_parmap_futex_end; - parmap->signal_f = xbt_parmap_futex_signal; - parmap->wait_f = xbt_parmap_futex_wait; + parmap->master_wait_f = xbt_parmap_futex_master_wait; + parmap->worker_signal_f = xbt_parmap_futex_worker_signal; + parmap->master_signal_f = xbt_parmap_futex_master_signal; + parmap->worker_wait_f = xbt_parmap_futex_worker_wait; xbt_os_cond_destroy(parmap->ready_cond); xbt_os_mutex_destroy(parmap->ready_mutex); @@ -176,10 +177,10 @@ static void xbt_parmap_set_mode(xbt_parmap_t parmap, e_xbt_parmap_mode_t mode) #endif case XBT_PARMAP_BUSY_WAIT: - parmap->start_f = xbt_parmap_busy_start; - parmap->end_f = xbt_parmap_busy_end; - parmap->signal_f = xbt_parmap_busy_signal; - parmap->wait_f = xbt_parmap_busy_wait; + parmap->master_wait_f = xbt_parmap_busy_master_wait; + parmap->worker_signal_f = xbt_parmap_busy_worker_signal; + parmap->master_signal_f = xbt_parmap_busy_master_signal; + parmap->worker_wait_f = xbt_parmap_busy_worker_wait; xbt_os_cond_destroy(parmap->ready_cond); xbt_os_mutex_destroy(parmap->ready_mutex); @@ -205,7 +206,9 @@ void xbt_parmap_apply(xbt_parmap_t parmap, void_f_pvoid_t fun, xbt_dynar_t data) parmap->fun = fun; parmap->data = data; parmap->index = 0; - parmap->signal_f(parmap); + parmap->master_signal_f(parmap); + xbt_parmap_work(parmap); + parmap->master_wait_f(parmap); XBT_DEBUG("Job done"); } @@ -225,6 +228,14 @@ void* xbt_parmap_next(xbt_parmap_t parmap) return NULL; } +static void xbt_parmap_work(xbt_parmap_t parmap) +{ + unsigned index; + while ((index = __sync_fetch_and_add(&parmap->index, 1)) + < xbt_dynar_length(parmap->data)) + parmap->fun(xbt_dynar_get_as(parmap->data, index, void*)); +} + /** * \brief Main function of a worker thread. * \param arg the parmap @@ -232,40 +243,38 @@ void* xbt_parmap_next(xbt_parmap_t parmap) static void *xbt_parmap_worker_main(void *arg) { xbt_parmap_t parmap = (xbt_parmap_t) arg; + unsigned round = 0; XBT_DEBUG("New worker thread created"); /* Worker's main loop */ while (1) { - parmap->wait_f(parmap); + parmap->worker_wait_f(parmap, ++round); if (parmap->status == XBT_PARMAP_WORK) { XBT_DEBUG("Worker got a job"); - void* work = xbt_parmap_next(parmap); - while (work != NULL) { - parmap->fun(work); - work = xbt_parmap_next(parmap); - } + xbt_parmap_work(parmap); + parmap->worker_signal_f(parmap); XBT_DEBUG("Worker has finished"); /* We are destroying the parmap */ } else { - parmap->end_f(parmap); + parmap->worker_signal_f(parmap); return NULL; } } } #ifdef HAVE_FUTEX_H -static void futex_wait(int *uaddr, int val) +static void futex_wait(unsigned *uaddr, unsigned val) { XBT_VERB("Waiting on futex %p", uaddr); syscall(SYS_futex, uaddr, FUTEX_WAIT_PRIVATE, val, NULL, NULL, 0); } -static void futex_wake(int *uaddr, int val) +static void futex_wake(unsigned *uaddr, unsigned val) { XBT_VERB("Waking futex %p", uaddr); syscall(SYS_futex, uaddr, FUTEX_WAKE_PRIVATE, val, NULL, NULL, 0); @@ -279,13 +288,14 @@ static void futex_wake(int *uaddr, int val) * * \param parmap a parmap */ -static void xbt_parmap_posix_start(xbt_parmap_t parmap) +static void xbt_parmap_posix_master_wait(xbt_parmap_t parmap) { - unsigned int counter = __sync_fetch_and_add(&parmap->thread_counter, 1); - if (counter < parmap->num_workers) { - /* wait for all workers to be initialized */ + xbt_os_mutex_acquire(parmap->done_mutex); + if (parmap->thread_counter < parmap->num_workers) { + /* wait for all workers to be ready */ xbt_os_cond_wait(parmap->done_cond, parmap->done_mutex); } + xbt_os_mutex_release(parmap->done_mutex); } /** @@ -296,14 +306,14 @@ static void xbt_parmap_posix_start(xbt_parmap_t parmap) * * \param parmap a parmap */ -static void xbt_parmap_posix_end(xbt_parmap_t parmap) +static void xbt_parmap_posix_worker_signal(xbt_parmap_t parmap) { - unsigned int counter = __sync_add_and_fetch(&parmap->thread_counter, 1); - XBT_DEBUG("Shutting down worker %d", counter); - if (counter == parmap->num_workers) { + xbt_os_mutex_acquire(parmap->done_mutex); + if (++parmap->thread_counter == parmap->num_workers) { /* all workers have finished, wake the controller */ xbt_os_cond_signal(parmap->done_cond); } + xbt_os_mutex_release(parmap->done_mutex); } /** @@ -313,30 +323,14 @@ static void xbt_parmap_posix_end(xbt_parmap_t parmap) * * \param parmap a parmap */ -static void xbt_parmap_posix_signal(xbt_parmap_t parmap) +static void xbt_parmap_posix_master_signal(xbt_parmap_t parmap) { - parmap->thread_counter = 0; + xbt_os_mutex_acquire(parmap->ready_mutex); + parmap->thread_counter = 1; parmap->work++; - XBT_DEBUG("Starting work %d", parmap->work); - /* wake all workers */ xbt_os_cond_broadcast(parmap->ready_cond); - - if (parmap->status == XBT_PARMAP_WORK) { - /* also work myself */ - void* work = xbt_parmap_next(parmap); - while (work != NULL) { - parmap->fun(work); - work = xbt_parmap_next(parmap); - } - } - - unsigned int counter = __sync_add_and_fetch(&parmap->thread_counter, 1); - if (counter < parmap->num_workers) { - /* some workers have not finished yet */ - XBT_DEBUG("Some workers have not finished yet, waiting for them"); - xbt_os_cond_wait(parmap->done_cond, parmap->done_mutex); - } + xbt_os_mutex_release(parmap->ready_mutex); } /** @@ -346,23 +340,16 @@ static void xbt_parmap_posix_signal(xbt_parmap_t parmap) * when it has no more work to do. * * \param parmap a parmap + * \param round the expected round number */ -static void xbt_parmap_posix_wait(xbt_parmap_t parmap) +static void xbt_parmap_posix_worker_wait(xbt_parmap_t parmap, unsigned round) { - int work = parmap->work; - unsigned int counter = __sync_add_and_fetch(&parmap->thread_counter, 1); - if (counter == parmap->num_workers) { - /* all workers have finished, wake the controller */ - parmap->done++; - XBT_DEBUG("Last worker has finished, waking the controller"); - xbt_os_cond_signal(parmap->done_cond); - } - + xbt_os_mutex_acquire(parmap->ready_mutex); /* wait for more work */ - XBT_DEBUG("Worker %d waiting for more work", counter); - if (parmap->work == work) { + if (parmap->work < round) { xbt_os_cond_wait(parmap->ready_cond, parmap->ready_mutex); } + xbt_os_mutex_release(parmap->ready_mutex); } #ifdef HAVE_FUTEX_H @@ -373,13 +360,13 @@ static void xbt_parmap_posix_wait(xbt_parmap_t parmap) * * \param parmap a parmap */ -static void xbt_parmap_futex_start(xbt_parmap_t parmap) +static void xbt_parmap_futex_master_wait(xbt_parmap_t parmap) { - int myflag = parmap->done; - __sync_fetch_and_add(&parmap->thread_counter, 1); - if (parmap->thread_counter < parmap->num_workers) { + unsigned count = parmap->thread_counter; + while (count < parmap->num_workers) { /* wait for all workers to be ready */ - futex_wait(&parmap->done, myflag); + futex_wait(&parmap->thread_counter, count); + count = parmap->thread_counter; } } @@ -391,15 +378,12 @@ static void xbt_parmap_futex_start(xbt_parmap_t parmap) * * \param parmap a parmap */ -static void xbt_parmap_futex_end(xbt_parmap_t parmap) +static void xbt_parmap_futex_worker_signal(xbt_parmap_t parmap) { - unsigned int mycount; - - mycount = __sync_add_and_fetch(&parmap->thread_counter, 1); - if (mycount == parmap->num_workers) { + unsigned count = __sync_add_and_fetch(&parmap->thread_counter, 1); + if (count == parmap->num_workers) { /* all workers have finished, wake the controller */ - parmap->done++; - futex_wake(&parmap->done, 1); + futex_wake(&parmap->thread_counter, 1); } } @@ -410,29 +394,12 @@ static void xbt_parmap_futex_end(xbt_parmap_t parmap) * * \param parmap a parmap */ -static void xbt_parmap_futex_signal(xbt_parmap_t parmap) +static void xbt_parmap_futex_master_signal(xbt_parmap_t parmap) { - int myflag = parmap->done; - parmap->thread_counter = 0; - parmap->work++; - + parmap->thread_counter = 1; + __sync_add_and_fetch(&parmap->work, 1); /* wake all workers */ - futex_wake(&parmap->work, parmap->num_workers); - - if (parmap->status == XBT_PARMAP_WORK) { - /* also work myself */ - void* work = xbt_parmap_next(parmap); - while (work != NULL) { - parmap->fun(work); - work = xbt_parmap_next(parmap); - } - } - - unsigned int mycount = __sync_add_and_fetch(&parmap->thread_counter, 1); - if (mycount < parmap->num_workers) { - /* some workers have not finished yet */ - futex_wait(&parmap->done, myflag); - } + futex_wake(&parmap->work, parmap->num_workers - 1); } /** @@ -442,22 +409,14 @@ static void xbt_parmap_futex_signal(xbt_parmap_t parmap) * when it has no more work to do. * * \param parmap a parmap + * \param round the expected round number */ -static void xbt_parmap_futex_wait(xbt_parmap_t parmap) +static void xbt_parmap_futex_worker_wait(xbt_parmap_t parmap, unsigned round) { - int myflag; - unsigned int mycount; - - myflag = parmap->work; - mycount = __sync_add_and_fetch(&parmap->thread_counter, 1); - if (mycount == parmap->num_workers) { - /* all workers have finished, wake the controller */ - parmap->done++; - futex_wake(&parmap->done, 1); - } - + unsigned work = parmap->work; /* wait for more work */ - futex_wait(&parmap->work, myflag); + if (work < round) + futex_wait(&parmap->work, work); } #endif @@ -468,9 +427,8 @@ static void xbt_parmap_futex_wait(xbt_parmap_t parmap) * * \param parmap a parmap */ -static void xbt_parmap_busy_start(xbt_parmap_t parmap) +static void xbt_parmap_busy_master_wait(xbt_parmap_t parmap) { - __sync_fetch_and_add(&parmap->thread_counter, 1); while (parmap->thread_counter < parmap->num_workers) { xbt_os_thread_yield(); } @@ -483,7 +441,7 @@ static void xbt_parmap_busy_start(xbt_parmap_t parmap) * * \param parmap a parmap */ -static void xbt_parmap_busy_end(xbt_parmap_t parmap) +static void xbt_parmap_busy_worker_signal(xbt_parmap_t parmap) { __sync_add_and_fetch(&parmap->thread_counter, 1); } @@ -495,25 +453,10 @@ static void xbt_parmap_busy_end(xbt_parmap_t parmap) * * \param parmap a parmap */ -static void xbt_parmap_busy_signal(xbt_parmap_t parmap) +static void xbt_parmap_busy_master_signal(xbt_parmap_t parmap) { - parmap->thread_counter = 0; - parmap->work++; - - if (parmap->status == XBT_PARMAP_WORK) { - /* also work myself */ - void* work = xbt_parmap_next(parmap); - while (work != NULL) { - parmap->fun(work); - work = xbt_parmap_next(parmap); - } - } - - /* I have finished, wait for the others */ - __sync_add_and_fetch(&parmap->thread_counter, 1); - while (parmap->thread_counter < parmap->num_workers) { - xbt_os_thread_yield(); - } + parmap->thread_counter = 1; + __sync_add_and_fetch(&parmap->work, 1); } /** @@ -523,14 +466,12 @@ static void xbt_parmap_busy_signal(xbt_parmap_t parmap) * when it has no more work to do. * * \param parmap a parmap + * \param round the expected round number */ -static void xbt_parmap_busy_wait(xbt_parmap_t parmap) +static void xbt_parmap_busy_worker_wait(xbt_parmap_t parmap, unsigned round) { - int work = parmap->work; - __sync_add_and_fetch(&parmap->thread_counter, 1); - /* wait for more work */ - while (parmap->work == work) { + while (parmap->work < round) { xbt_os_thread_yield(); } }