X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/blobdiff_plain/c5ad8ca1a68bbaa9152471c8d0eeb99d762f0d86..fff8fc755939b0f3fbb3fd62cf3cc5f83aa05c5b:/src/xbt/parmap.c diff --git a/src/xbt/parmap.c b/src/xbt/parmap.c index 13c7baf7d0..c7592a044a 100644 --- a/src/xbt/parmap.c +++ b/src/xbt/parmap.c @@ -3,7 +3,7 @@ /* This program is free software; you can redistribute it and/or modify it * under the terms of the license (GNU LGPL) which comes with this package. */ -#include "gras_config.h" +#include "internal_config.h" #include #ifndef _XBT_WIN32 @@ -12,6 +12,7 @@ #ifdef HAVE_FUTEX_H #include +#include #endif #include "xbt/parmap.h" @@ -20,45 +21,47 @@ #include "xbt/dynar.h" #include "xbt/xbt_os_thread.h" #include "xbt/sysdep.h" +#include "simix/smx_private.h" 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,12 +75,22 @@ 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; +/** + * \brief Thread data transmission structure + */ +typedef struct s_xbt_parmap_thread_data{ + xbt_parmap_t parmap; + int worker_id; +} s_xbt_parmap_thread_data_t; + +typedef s_xbt_parmap_thread_data_t *xbt_parmap_thread_data_t; + /** * \brief Creates a parallel map object * \param num_workers number of worker threads to create @@ -99,11 +112,14 @@ 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++) { - worker = xbt_os_thread_create(NULL, xbt_parmap_worker_main, parmap, NULL); + xbt_parmap_thread_data_t data; + for (i = 1; i < num_workers; i++) { + data = xbt_new0(s_xbt_parmap_thread_data_t, 1); + data->parmap = parmap; + data->worker_id = i; + worker = xbt_os_thread_create(NULL, xbt_parmap_worker_main, data, NULL); xbt_os_thread_detach(worker); } - parmap->start_f(parmap); return parmap; } @@ -118,7 +134,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 +164,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 +178,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 +193,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 +222,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,47 +244,57 @@ 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 */ static void *xbt_parmap_worker_main(void *arg) { - xbt_parmap_t parmap = (xbt_parmap_t) arg; + xbt_parmap_thread_data_t data = (xbt_parmap_thread_data_t) arg; + xbt_parmap_t parmap = data->parmap; + unsigned round = 0; + smx_context_t context = SIMIX_context_new(NULL, 0, NULL, NULL, NULL); + SIMIX_context_set_current(context); 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"); + XBT_DEBUG("Worker %d got a job", data->worker_id); - 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"); + XBT_DEBUG("Worker %d has finished", data->worker_id); /* We are destroying the parmap */ } else { - parmap->end_f(parmap); + xbt_free(data); + 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 +308,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 +326,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 +343,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 +360,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 +380,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 +398,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, INT_MAX); } } @@ -410,29 +414,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, INT_MAX); } /** @@ -442,22 +429,16 @@ 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); + while (work != round) { + futex_wait(&parmap->work, work); + work = parmap->work; + } } #endif @@ -468,9 +449,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 +463,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 +475,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,58 +488,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(); } } - -#ifdef SIMGRID_TEST -#include "xbt.h" -#include "xbt/ex.h" - -XBT_TEST_SUITE("parmap", "Parallel Map"); -XBT_LOG_EXTERNAL_DEFAULT_CATEGORY(xbt_parmap_unit); - -xbt_parmap_t parmap; - -void fun(void *arg); - -void fun(void *arg) -{ - //XBT_INFO("I'm job %lu", (unsigned long)arg); -} - -XBT_TEST_UNIT("basic", test_parmap_basic, "Basic usage") -{ - xbt_test_add("Create the parmap"); - - unsigned long i, j; - xbt_dynar_t data = xbt_dynar_new(sizeof(void *), NULL); - - /* Create the parallel map */ -#ifdef HAVE_FUTEX_H - parmap = xbt_parmap_new(10, XBT_PARMAP_FUTEX); -#else - parmap = xbt_parmap_new(10, XBT_PARMAP_BUSY_WAIT); -#endif - for (j = 0; j < 100; j++) { - xbt_dynar_push_as(data, void *, (void *)j); - } - - for (i = 0; i < 5; i++) { - xbt_parmap_apply(parmap, fun, data); - } - - /* Destroy the parmap */ - xbt_parmap_destroy(parmap); - xbt_dynar_free(&data); -} - -#endif /* SIMGRID_TEST */