diff options
author | Haibo Huang <hhb@google.com> | 2020-12-07 21:08:05 -0800 |
---|---|---|
committer | Haibo Huang <hhb@google.com> | 2020-12-07 21:08:05 -0800 |
commit | 2b982031b6c5feb9ae114ed4beff79c56a6f53d0 (patch) | |
tree | 11027206af1a9373daa4f403ac1e670a52108462 | |
parent | de8e443ece92f9eb80c341b69501932a03ed8ff6 (diff) | |
parent | 344531b40881b1ee41508a9c70c8fbbef3bd6cad (diff) | |
download | pthreadpool-2b982031b6c5feb9ae114ed4beff79c56a6f53d0.tar.gz |
Upgrade pthreadpool to 344531b40881b1ee41508a9c70c8fbbef3bd6cad
Test: make
Change-Id: I526bb8a53935fa2b150dc1e7c42a044e74ae8e9c
-rw-r--r-- | METADATA | 6 | ||||
-rw-r--r-- | bench/throughput.cc | 322 | ||||
-rw-r--r-- | include/pthreadpool.h | 108 | ||||
-rw-r--r-- | src/fastpath.c | 157 | ||||
-rw-r--r-- | src/portable-api.c | 271 | ||||
-rw-r--r-- | src/shim.c | 55 | ||||
-rw-r--r-- | src/threadpool-atomics.h | 106 | ||||
-rw-r--r-- | src/threadpool-object.h | 72 | ||||
-rw-r--r-- | test/pthreadpool.cc | 731 |
9 files changed, 1817 insertions, 11 deletions
@@ -9,11 +9,11 @@ third_party { type: GIT value: "https://github.com/Maratyszcza/pthreadpool" } - version: "029c88620802e1361ccf41d1970bd5b07fd6b7bb" + version: "344531b40881b1ee41508a9c70c8fbbef3bd6cad" license_type: NOTICE last_upgrade_date { year: 2020 - month: 7 - day: 10 + month: 12 + day: 7 } } diff --git a/bench/throughput.cc b/bench/throughput.cc index 2242ccb..47c8da7 100644 --- a/bench/throughput.cc +++ b/bench/throughput.cc @@ -7,7 +7,7 @@ static void compute_1d(void*, size_t) { } static void pthreadpool_parallelize_1d(benchmark::State& state) { - pthreadpool_t threadpool = pthreadpool_create(0); + pthreadpool_t threadpool = pthreadpool_create(2); const size_t threads = pthreadpool_get_threads_count(threadpool); const size_t items = static_cast<size_t>(state.range(0)); while (state.KeepRunning()) { @@ -30,7 +30,7 @@ static void compute_1d_tile_1d(void*, size_t, size_t) { } static void pthreadpool_parallelize_1d_tile_1d(benchmark::State& state) { - pthreadpool_t threadpool = pthreadpool_create(0); + pthreadpool_t threadpool = pthreadpool_create(2); const size_t threads = pthreadpool_get_threads_count(threadpool); const size_t items = static_cast<size_t>(state.range(0)); while (state.KeepRunning()) { @@ -49,11 +49,11 @@ static void pthreadpool_parallelize_1d_tile_1d(benchmark::State& state) { BENCHMARK(pthreadpool_parallelize_1d_tile_1d)->UseRealTime()->RangeMultiplier(10)->Range(10, 1000000); -static void compute_2d(void* context, size_t x, size_t y) { +static void compute_2d(void*, size_t, size_t) { } static void pthreadpool_parallelize_2d(benchmark::State& state) { - pthreadpool_t threadpool = pthreadpool_create(0); + pthreadpool_t threadpool = pthreadpool_create(2); const size_t threads = pthreadpool_get_threads_count(threadpool); const size_t items = static_cast<size_t>(state.range(0)); while (state.KeepRunning()) { @@ -72,17 +72,41 @@ static void pthreadpool_parallelize_2d(benchmark::State& state) { BENCHMARK(pthreadpool_parallelize_2d)->UseRealTime()->RangeMultiplier(10)->Range(10, 1000000); -static void compute_2d_tiled(void* context, size_t x0, size_t y0, size_t xn, size_t yn) { +static void compute_2d_tile_1d(void*, size_t, size_t, size_t) { +} + +static void pthreadpool_parallelize_2d_tile_1d(benchmark::State& state) { + pthreadpool_t threadpool = pthreadpool_create(2); + const size_t threads = pthreadpool_get_threads_count(threadpool); + const size_t items = static_cast<size_t>(state.range(0)); + while (state.KeepRunning()) { + pthreadpool_parallelize_2d_tile_1d( + threadpool, + compute_2d_tile_1d, + nullptr /* context */, + threads, items, + 1, + 0 /* flags */); + } + pthreadpool_destroy(threadpool); + + /* Do not normalize by thread */ + state.SetItemsProcessed(int64_t(state.iterations()) * items); +} +BENCHMARK(pthreadpool_parallelize_2d_tile_1d)->UseRealTime()->RangeMultiplier(10)->Range(10, 1000000); + + +static void compute_2d_tile_2d(void*, size_t, size_t, size_t, size_t) { } static void pthreadpool_parallelize_2d_tile_2d(benchmark::State& state) { - pthreadpool_t threadpool = pthreadpool_create(0); + pthreadpool_t threadpool = pthreadpool_create(2); const size_t threads = pthreadpool_get_threads_count(threadpool); const size_t items = static_cast<size_t>(state.range(0)); while (state.KeepRunning()) { pthreadpool_parallelize_2d_tile_2d( threadpool, - compute_2d_tiled, + compute_2d_tile_2d, nullptr /* context */, threads, items, 1, 1, @@ -96,4 +120,288 @@ static void pthreadpool_parallelize_2d_tile_2d(benchmark::State& state) { BENCHMARK(pthreadpool_parallelize_2d_tile_2d)->UseRealTime()->RangeMultiplier(10)->Range(10, 1000000); +static void compute_3d(void*, size_t, size_t, size_t) { +} + +static void pthreadpool_parallelize_3d(benchmark::State& state) { + pthreadpool_t threadpool = pthreadpool_create(2); + const size_t threads = pthreadpool_get_threads_count(threadpool); + const size_t items = static_cast<size_t>(state.range(0)); + while (state.KeepRunning()) { + pthreadpool_parallelize_3d( + threadpool, + compute_3d, + nullptr /* context */, + 1, threads, items, + 0 /* flags */); + } + pthreadpool_destroy(threadpool); + + /* Do not normalize by thread */ + state.SetItemsProcessed(int64_t(state.iterations()) * items); +} +BENCHMARK(pthreadpool_parallelize_3d)->UseRealTime()->RangeMultiplier(10)->Range(10, 1000000); + + +static void compute_3d_tile_1d(void*, size_t, size_t, size_t, size_t) { +} + +static void pthreadpool_parallelize_3d_tile_1d(benchmark::State& state) { + pthreadpool_t threadpool = pthreadpool_create(2); + const size_t threads = pthreadpool_get_threads_count(threadpool); + const size_t items = static_cast<size_t>(state.range(0)); + while (state.KeepRunning()) { + pthreadpool_parallelize_3d_tile_1d( + threadpool, + compute_3d_tile_1d, + nullptr /* context */, + 1, threads, items, + 1, + 0 /* flags */); + } + pthreadpool_destroy(threadpool); + + /* Do not normalize by thread */ + state.SetItemsProcessed(int64_t(state.iterations()) * items); +} +BENCHMARK(pthreadpool_parallelize_3d_tile_1d)->UseRealTime()->RangeMultiplier(10)->Range(10, 1000000); + + +static void compute_3d_tile_2d(void*, size_t, size_t, size_t, size_t, size_t) { +} + +static void pthreadpool_parallelize_3d_tile_2d(benchmark::State& state) { + pthreadpool_t threadpool = pthreadpool_create(2); + const size_t threads = pthreadpool_get_threads_count(threadpool); + const size_t items = static_cast<size_t>(state.range(0)); + while (state.KeepRunning()) { + pthreadpool_parallelize_3d_tile_2d( + threadpool, + compute_3d_tile_2d, + nullptr /* context */, + 1, threads, items, + 1, 1, + 0 /* flags */); + } + pthreadpool_destroy(threadpool); + + /* Do not normalize by thread */ + state.SetItemsProcessed(int64_t(state.iterations()) * items); +} +BENCHMARK(pthreadpool_parallelize_3d_tile_2d)->UseRealTime()->RangeMultiplier(10)->Range(10, 1000000); + + +static void compute_4d(void*, size_t, size_t, size_t, size_t) { +} + +static void pthreadpool_parallelize_4d(benchmark::State& state) { + pthreadpool_t threadpool = pthreadpool_create(2); + const size_t threads = pthreadpool_get_threads_count(threadpool); + const size_t items = static_cast<size_t>(state.range(0)); + while (state.KeepRunning()) { + pthreadpool_parallelize_4d( + threadpool, + compute_4d, + nullptr /* context */, + 1, 1, threads, items, + 0 /* flags */); + } + pthreadpool_destroy(threadpool); + + /* Do not normalize by thread */ + state.SetItemsProcessed(int64_t(state.iterations()) * items); +} +BENCHMARK(pthreadpool_parallelize_4d)->UseRealTime()->RangeMultiplier(10)->Range(10, 1000000); + + +static void compute_4d_tile_1d(void*, size_t, size_t, size_t, size_t, size_t) { +} + +static void pthreadpool_parallelize_4d_tile_1d(benchmark::State& state) { + pthreadpool_t threadpool = pthreadpool_create(2); + const size_t threads = pthreadpool_get_threads_count(threadpool); + const size_t items = static_cast<size_t>(state.range(0)); + while (state.KeepRunning()) { + pthreadpool_parallelize_4d_tile_1d( + threadpool, + compute_4d_tile_1d, + nullptr /* context */, + 1, 1, threads, items, + 1, + 0 /* flags */); + } + pthreadpool_destroy(threadpool); + + /* Do not normalize by thread */ + state.SetItemsProcessed(int64_t(state.iterations()) * items); +} +BENCHMARK(pthreadpool_parallelize_4d_tile_1d)->UseRealTime()->RangeMultiplier(10)->Range(10, 1000000); + + +static void compute_4d_tile_2d(void*, size_t, size_t, size_t, size_t, size_t, size_t) { +} + +static void pthreadpool_parallelize_4d_tile_2d(benchmark::State& state) { + pthreadpool_t threadpool = pthreadpool_create(2); + const size_t threads = pthreadpool_get_threads_count(threadpool); + const size_t items = static_cast<size_t>(state.range(0)); + while (state.KeepRunning()) { + pthreadpool_parallelize_4d_tile_2d( + threadpool, + compute_4d_tile_2d, + nullptr /* context */, + 1, 1, threads, items, + 1, 1, + 0 /* flags */); + } + pthreadpool_destroy(threadpool); + + /* Do not normalize by thread */ + state.SetItemsProcessed(int64_t(state.iterations()) * items); +} +BENCHMARK(pthreadpool_parallelize_4d_tile_2d)->UseRealTime()->RangeMultiplier(10)->Range(10, 1000000); + + +static void compute_5d(void*, size_t, size_t, size_t, size_t, size_t) { +} + +static void pthreadpool_parallelize_5d(benchmark::State& state) { + pthreadpool_t threadpool = pthreadpool_create(2); + const size_t threads = pthreadpool_get_threads_count(threadpool); + const size_t items = static_cast<size_t>(state.range(0)); + while (state.KeepRunning()) { + pthreadpool_parallelize_5d( + threadpool, + compute_5d, + nullptr /* context */, + 1, 1, 1, threads, items, + 0 /* flags */); + } + pthreadpool_destroy(threadpool); + + /* Do not normalize by thread */ + state.SetItemsProcessed(int64_t(state.iterations()) * items); +} +BENCHMARK(pthreadpool_parallelize_5d)->UseRealTime()->RangeMultiplier(10)->Range(10, 1000000); + + +static void compute_5d_tile_1d(void*, size_t, size_t, size_t, size_t, size_t, size_t) { +} + +static void pthreadpool_parallelize_5d_tile_1d(benchmark::State& state) { + pthreadpool_t threadpool = pthreadpool_create(2); + const size_t threads = pthreadpool_get_threads_count(threadpool); + const size_t items = static_cast<size_t>(state.range(0)); + while (state.KeepRunning()) { + pthreadpool_parallelize_5d_tile_1d( + threadpool, + compute_5d_tile_1d, + nullptr /* context */, + 1, 1, 1, threads, items, + 1, + 0 /* flags */); + } + pthreadpool_destroy(threadpool); + + /* Do not normalize by thread */ + state.SetItemsProcessed(int64_t(state.iterations()) * items); +} +BENCHMARK(pthreadpool_parallelize_5d_tile_1d)->UseRealTime()->RangeMultiplier(10)->Range(10, 1000000); + + +static void compute_5d_tile_2d(void*, size_t, size_t, size_t, size_t, size_t, size_t, size_t) { +} + +static void pthreadpool_parallelize_5d_tile_2d(benchmark::State& state) { + pthreadpool_t threadpool = pthreadpool_create(2); + const size_t threads = pthreadpool_get_threads_count(threadpool); + const size_t items = static_cast<size_t>(state.range(0)); + while (state.KeepRunning()) { + pthreadpool_parallelize_5d_tile_2d( + threadpool, + compute_5d_tile_2d, + nullptr /* context */, + 1, 1, 1, threads, items, + 1, 1, + 0 /* flags */); + } + pthreadpool_destroy(threadpool); + + /* Do not normalize by thread */ + state.SetItemsProcessed(int64_t(state.iterations()) * items); +} +BENCHMARK(pthreadpool_parallelize_5d_tile_2d)->UseRealTime()->RangeMultiplier(10)->Range(10, 1000000); + + +static void compute_6d(void*, size_t, size_t, size_t, size_t, size_t, size_t) { +} + +static void pthreadpool_parallelize_6d(benchmark::State& state) { + pthreadpool_t threadpool = pthreadpool_create(2); + const size_t threads = pthreadpool_get_threads_count(threadpool); + const size_t items = static_cast<size_t>(state.range(0)); + while (state.KeepRunning()) { + pthreadpool_parallelize_6d( + threadpool, + compute_6d, + nullptr /* context */, + 1, 1, 1, 1, threads, items, + 0 /* flags */); + } + pthreadpool_destroy(threadpool); + + /* Do not normalize by thread */ + state.SetItemsProcessed(int64_t(state.iterations()) * items); +} +BENCHMARK(pthreadpool_parallelize_6d)->UseRealTime()->RangeMultiplier(10)->Range(10, 1000000); + + +static void compute_6d_tile_1d(void*, size_t, size_t, size_t, size_t, size_t, size_t, size_t) { +} + +static void pthreadpool_parallelize_6d_tile_1d(benchmark::State& state) { + pthreadpool_t threadpool = pthreadpool_create(2); + const size_t threads = pthreadpool_get_threads_count(threadpool); + const size_t items = static_cast<size_t>(state.range(0)); + while (state.KeepRunning()) { + pthreadpool_parallelize_6d_tile_1d( + threadpool, + compute_6d_tile_1d, + nullptr /* context */, + 1, 1, 1, 1, threads, items, + 1, + 0 /* flags */); + } + pthreadpool_destroy(threadpool); + + /* Do not normalize by thread */ + state.SetItemsProcessed(int64_t(state.iterations()) * items); +} +BENCHMARK(pthreadpool_parallelize_6d_tile_1d)->UseRealTime()->RangeMultiplier(10)->Range(10, 1000000); + + +static void compute_6d_tile_2d(void*, size_t, size_t, size_t, size_t, size_t, size_t, size_t, size_t) { +} + +static void pthreadpool_parallelize_6d_tile_2d(benchmark::State& state) { + pthreadpool_t threadpool = pthreadpool_create(2); + const size_t threads = pthreadpool_get_threads_count(threadpool); + const size_t items = static_cast<size_t>(state.range(0)); + while (state.KeepRunning()) { + pthreadpool_parallelize_6d_tile_2d( + threadpool, + compute_6d_tile_2d, + nullptr /* context */, + 1, 1, 1, 1, threads, items, + 1, 1, + 0 /* flags */); + } + pthreadpool_destroy(threadpool); + + /* Do not normalize by thread */ + state.SetItemsProcessed(int64_t(state.iterations()) * items); +} +BENCHMARK(pthreadpool_parallelize_6d_tile_2d)->UseRealTime()->RangeMultiplier(10)->Range(10, 1000000); + + BENCHMARK_MAIN(); diff --git a/include/pthreadpool.h b/include/pthreadpool.h index 6a7d61f..59c4abf 100644 --- a/include/pthreadpool.h +++ b/include/pthreadpool.h @@ -20,6 +20,8 @@ typedef void (*pthreadpool_task_4d_tile_2d_t)(void*, size_t, size_t, size_t, siz typedef void (*pthreadpool_task_5d_t)(void*, size_t, size_t, size_t, size_t, size_t); typedef void (*pthreadpool_task_5d_tile_1d_t)(void*, size_t, size_t, size_t, size_t, size_t, size_t); typedef void (*pthreadpool_task_5d_tile_2d_t)(void*, size_t, size_t, size_t, size_t, size_t, size_t, size_t); +typedef void (*pthreadpool_task_6d_t)(void*, size_t, size_t, size_t, size_t, size_t, size_t); +typedef void (*pthreadpool_task_6d_tile_1d_t)(void*, size_t, size_t, size_t, size_t, size_t, size_t, size_t); typedef void (*pthreadpool_task_6d_tile_2d_t)(void*, size_t, size_t, size_t, size_t, size_t, size_t, size_t, size_t); typedef void (*pthreadpool_task_1d_with_id_t)(void*, uint32_t, size_t); @@ -908,6 +910,112 @@ void pthreadpool_parallelize_5d_tile_2d( uint32_t flags); /** + * Process items on a 6D grid. + * + * The function implements a parallel version of the following snippet: + * + * for (size_t i = 0; i < range_i; i++) + * for (size_t j = 0; j < range_j; j++) + * for (size_t k = 0; k < range_k; k++) + * for (size_t l = 0; l < range_l; l++) + * for (size_t m = 0; m < range_m; m++) + * for (size_t n = 0; n < range_n; n++) + * function(context, i, j, k, l, m, n); + * + * When the function returns, all items have been processed and the thread pool + * is ready for a new task. + * + * @note If multiple threads call this function with the same thread pool, the + * calls are serialized. + * + * @param threadpool the thread pool to use for parallelisation. If threadpool + * is NULL, all items are processed serially on the calling thread. + * @param function the function to call for each tile. + * @param context the first argument passed to the specified function. + * @param range_i the number of items to process along the first dimension + * of the 6D grid. + * @param range_j the number of items to process along the second dimension + * of the 6D grid. + * @param range_k the number of items to process along the third dimension + * of the 6D grid. + * @param range_l the number of items to process along the fourth dimension + * of the 6D grid. + * @param range_m the number of items to process along the fifth dimension + * of the 6D grid. + * @param range_n the number of items to process along the sixth dimension + * of the 6D grid. + * @param tile_n the maximum number of items along the sixth dimension of + * the 6D grid to process in one function call. + * @param flags a bitwise combination of zero or more optional flags + * (PTHREADPOOL_FLAG_DISABLE_DENORMALS or PTHREADPOOL_FLAG_YIELD_WORKERS) + */ +void pthreadpool_parallelize_6d( + pthreadpool_t threadpool, + pthreadpool_task_6d_t function, + void* context, + size_t range_i, + size_t range_j, + size_t range_k, + size_t range_l, + size_t range_m, + size_t range_n, + uint32_t flags); + +/** + * Process items on a 6D grid with the specified maximum tile size along the + * last grid dimension. + * + * The function implements a parallel version of the following snippet: + * + * for (size_t i = 0; i < range_i; i++) + * for (size_t j = 0; j < range_j; j++) + * for (size_t k = 0; k < range_k; k++) + * for (size_t l = 0; l < range_l; l++) + * for (size_t m = 0; m < range_m; m++) + * for (size_t n = 0; n < range_n; n += tile_n) + * function(context, i, j, k, l, m, n, min(range_n - n, tile_n)); + * + * When the function returns, all items have been processed and the thread pool + * is ready for a new task. + * + * @note If multiple threads call this function with the same thread pool, the + * calls are serialized. + * + * @param threadpool the thread pool to use for parallelisation. If threadpool + * is NULL, all items are processed serially on the calling thread. + * @param function the function to call for each tile. + * @param context the first argument passed to the specified function. + * @param range_i the number of items to process along the first dimension + * of the 6D grid. + * @param range_j the number of items to process along the second dimension + * of the 6D grid. + * @param range_k the number of items to process along the third dimension + * of the 6D grid. + * @param range_l the number of items to process along the fourth dimension + * of the 6D grid. + * @param range_m the number of items to process along the fifth dimension + * of the 6D grid. + * @param range_n the number of items to process along the sixth dimension + * of the 6D grid. + * @param tile_n the maximum number of items along the sixth dimension of + * the 6D grid to process in one function call. + * @param flags a bitwise combination of zero or more optional flags + * (PTHREADPOOL_FLAG_DISABLE_DENORMALS or PTHREADPOOL_FLAG_YIELD_WORKERS) + */ +void pthreadpool_parallelize_6d_tile_1d( + pthreadpool_t threadpool, + pthreadpool_task_6d_tile_1d_t function, + void* context, + size_t range_i, + size_t range_j, + size_t range_k, + size_t range_l, + size_t range_m, + size_t range_n, + size_t tile_n, + uint32_t flags); + +/** * Process items on a 6D grid with the specified maximum tile size along the * last two grid dimensions. * diff --git a/src/fastpath.c b/src/fastpath.c index 6abbebe..b914ff0 100644 --- a/src/fastpath.c +++ b/src/fastpath.c @@ -1085,6 +1085,163 @@ PTHREADPOOL_INTERNAL void pthreadpool_thread_parallelize_5d_tile_2d_fastpath( pthreadpool_fence_release(); } +PTHREADPOOL_INTERNAL void pthreadpool_thread_parallelize_6d_fastpath( + struct pthreadpool* threadpool, + struct thread_info* thread) +{ + assert(threadpool != NULL); + assert(thread != NULL); + + const pthreadpool_task_6d_t task = (pthreadpool_task_6d_t) pthreadpool_load_relaxed_void_p(&threadpool->task); + void *const argument = pthreadpool_load_relaxed_void_p(&threadpool->argument); + + const size_t threads_count = threadpool->threads_count.value; + const size_t range_threshold = -threads_count; + + /* Process thread's own range of items */ + const size_t range_start = pthreadpool_load_relaxed_size_t(&thread->range_start); + const struct fxdiv_divisor_size_t range_lmn = threadpool->params.parallelize_6d.range_lmn; + const struct fxdiv_result_size_t index_ijk_lmn = fxdiv_divide_size_t(range_start, range_lmn); + const struct fxdiv_divisor_size_t range_k = threadpool->params.parallelize_6d.range_k; + const struct fxdiv_result_size_t index_ij_k = fxdiv_divide_size_t(index_ijk_lmn.quotient, range_k); + const struct fxdiv_divisor_size_t range_n = threadpool->params.parallelize_6d.range_n; + const struct fxdiv_result_size_t index_lm_n = fxdiv_divide_size_t(index_ijk_lmn.remainder, range_n); + const struct fxdiv_divisor_size_t range_j = threadpool->params.parallelize_6d.range_j; + const struct fxdiv_result_size_t index_i_j = fxdiv_divide_size_t(index_ij_k.quotient, range_j); + const struct fxdiv_divisor_size_t range_m = threadpool->params.parallelize_6d.range_m; + const struct fxdiv_result_size_t index_l_m = fxdiv_divide_size_t(index_lm_n.quotient, range_m); + size_t i = index_i_j.quotient; + size_t j = index_i_j.remainder; + size_t k = index_ij_k.remainder; + size_t l = index_l_m.quotient; + size_t m = index_l_m.remainder; + size_t n = index_lm_n.remainder; + + const size_t range_l = threadpool->params.parallelize_6d.range_l; + while (pthreadpool_decrement_fetch_relaxed_size_t(&thread->range_length) < range_threshold) { + task(argument, i, j, k, l, m, n); + if (++n == range_n.value) { + n = 0; + if (++m == range_m.value) { + m = 0; + if (++l == range_l) { + l = 0; + if (++k == range_k.value) { + k = 0; + if (++j == range_j.value) { + j = 0; + i += 1; + } + } + } + } + } + } + + + /* There still may be other threads with work */ + const size_t thread_number = thread->thread_number; + for (size_t tid = modulo_decrement(thread_number, threads_count); + tid != thread_number; + tid = modulo_decrement(tid, threads_count)) + { + struct thread_info* other_thread = &threadpool->threads[tid]; + while (pthreadpool_decrement_fetch_relaxed_size_t(&other_thread->range_length) < range_threshold) { + const size_t linear_index = pthreadpool_decrement_fetch_relaxed_size_t(&other_thread->range_end); + const struct fxdiv_result_size_t index_ijk_lmn = fxdiv_divide_size_t(linear_index, range_lmn); + const struct fxdiv_result_size_t index_ij_k = fxdiv_divide_size_t(index_ijk_lmn.quotient, range_k); + const struct fxdiv_result_size_t index_lm_n = fxdiv_divide_size_t(index_ijk_lmn.remainder, range_n); + const struct fxdiv_result_size_t index_i_j = fxdiv_divide_size_t(index_ij_k.quotient, range_j); + const struct fxdiv_result_size_t index_l_m = fxdiv_divide_size_t(index_lm_n.quotient, range_m); + task(argument, index_i_j.quotient, index_i_j.remainder, index_ij_k.remainder, index_l_m.quotient, index_l_m.remainder, index_lm_n.remainder); + } + } + + /* Make changes by this thread visible to other threads */ + pthreadpool_fence_release(); +} + +PTHREADPOOL_INTERNAL void pthreadpool_thread_parallelize_6d_tile_1d_fastpath( + struct pthreadpool* threadpool, + struct thread_info* thread) +{ + assert(threadpool != NULL); + assert(thread != NULL); + + const pthreadpool_task_6d_tile_1d_t task = (pthreadpool_task_6d_tile_1d_t) pthreadpool_load_relaxed_void_p(&threadpool->task); + void *const argument = pthreadpool_load_relaxed_void_p(&threadpool->argument); + + const size_t threads_count = threadpool->threads_count.value; + const size_t range_threshold = -threads_count; + + /* Process thread's own range of items */ + const size_t range_start = pthreadpool_load_relaxed_size_t(&thread->range_start); + const struct fxdiv_divisor_size_t tile_range_lmn = threadpool->params.parallelize_6d_tile_1d.tile_range_lmn; + const struct fxdiv_result_size_t tile_index_ijk_lmn = fxdiv_divide_size_t(range_start, tile_range_lmn); + const struct fxdiv_divisor_size_t range_k = threadpool->params.parallelize_6d_tile_1d.range_k; + const struct fxdiv_result_size_t index_ij_k = fxdiv_divide_size_t(tile_index_ijk_lmn.quotient, range_k); + const struct fxdiv_divisor_size_t tile_range_n = threadpool->params.parallelize_6d_tile_1d.tile_range_n; + const struct fxdiv_result_size_t tile_index_lm_n = fxdiv_divide_size_t(tile_index_ijk_lmn.remainder, tile_range_n); + const struct fxdiv_divisor_size_t range_j = threadpool->params.parallelize_6d_tile_1d.range_j; + const struct fxdiv_result_size_t index_i_j = fxdiv_divide_size_t(index_ij_k.quotient, range_j); + const struct fxdiv_divisor_size_t range_m = threadpool->params.parallelize_6d_tile_1d.range_m; + const struct fxdiv_result_size_t index_l_m = fxdiv_divide_size_t(tile_index_lm_n.quotient, range_m); + const size_t tile_n = threadpool->params.parallelize_6d_tile_1d.tile_n; + size_t i = index_i_j.quotient; + size_t j = index_i_j.remainder; + size_t k = index_ij_k.remainder; + size_t l = index_l_m.quotient; + size_t m = index_l_m.remainder; + size_t start_n = tile_index_lm_n.remainder * tile_n; + + const size_t range_n = threadpool->params.parallelize_6d_tile_1d.range_n; + const size_t range_l = threadpool->params.parallelize_6d_tile_1d.range_l; + while (pthreadpool_decrement_fetch_relaxed_size_t(&thread->range_length) < range_threshold) { + task(argument, i, j, k, l, m, start_n, min(range_n - start_n, tile_n)); + start_n += tile_n; + if (start_n >= range_n) { + start_n = 0; + if (++m == range_m.value) { + m = 0; + if (++l == range_l) { + l = 0; + if (++k == range_k.value) { + k = 0; + if (++j == range_j.value) { + j = 0; + i += 1; + } + } + } + } + } + } + + + /* There still may be other threads with work */ + const size_t thread_number = thread->thread_number; + for (size_t tid = modulo_decrement(thread_number, threads_count); + tid != thread_number; + tid = modulo_decrement(tid, threads_count)) + { + struct thread_info* other_thread = &threadpool->threads[tid]; + while (pthreadpool_decrement_fetch_relaxed_size_t(&other_thread->range_length) < range_threshold) { + const size_t linear_index = pthreadpool_decrement_fetch_relaxed_size_t(&other_thread->range_end); + const struct fxdiv_result_size_t tile_index_ijk_lmn = fxdiv_divide_size_t(linear_index, tile_range_lmn); + const struct fxdiv_result_size_t index_ij_k = fxdiv_divide_size_t(tile_index_ijk_lmn.quotient, range_k); + const struct fxdiv_result_size_t tile_index_lm_n = fxdiv_divide_size_t(tile_index_ijk_lmn.remainder, tile_range_n); + const struct fxdiv_result_size_t index_i_j = fxdiv_divide_size_t(index_ij_k.quotient, range_j); + const struct fxdiv_result_size_t index_l_m = fxdiv_divide_size_t(tile_index_lm_n.quotient, range_m); + const size_t start_n = tile_index_lm_n.remainder * tile_n; + task(argument, index_i_j.quotient, index_i_j.remainder, index_ij_k.remainder, index_l_m.quotient, index_l_m.remainder, + start_n, min(range_n - start_n, tile_n)); + } + } + + /* Make changes by this thread visible to other threads */ + pthreadpool_fence_release(); +} + PTHREADPOOL_INTERNAL void pthreadpool_thread_parallelize_6d_tile_2d_fastpath( struct pthreadpool* threadpool, struct thread_info* thread) diff --git a/src/portable-api.c b/src/portable-api.c index ef36578..42d0369 100644 --- a/src/portable-api.c +++ b/src/portable-api.c @@ -1002,6 +1002,153 @@ static void thread_parallelize_5d_tile_2d(struct pthreadpool* threadpool, struct pthreadpool_fence_release(); } +static void thread_parallelize_6d(struct pthreadpool* threadpool, struct thread_info* thread) { + assert(threadpool != NULL); + assert(thread != NULL); + + const pthreadpool_task_6d_t task = (pthreadpool_task_6d_t) pthreadpool_load_relaxed_void_p(&threadpool->task); + void *const argument = pthreadpool_load_relaxed_void_p(&threadpool->argument); + + /* Process thread's own range of items */ + const size_t range_start = pthreadpool_load_relaxed_size_t(&thread->range_start); + const struct fxdiv_divisor_size_t range_lmn = threadpool->params.parallelize_6d.range_lmn; + const struct fxdiv_result_size_t index_ijk_lmn = fxdiv_divide_size_t(range_start, range_lmn); + const struct fxdiv_divisor_size_t range_k = threadpool->params.parallelize_6d.range_k; + const struct fxdiv_result_size_t index_ij_k = fxdiv_divide_size_t(index_ijk_lmn.quotient, range_k); + const struct fxdiv_divisor_size_t range_n = threadpool->params.parallelize_6d.range_n; + const struct fxdiv_result_size_t index_lm_n = fxdiv_divide_size_t(index_ijk_lmn.remainder, range_n); + const struct fxdiv_divisor_size_t range_j = threadpool->params.parallelize_6d.range_j; + const struct fxdiv_result_size_t index_i_j = fxdiv_divide_size_t(index_ij_k.quotient, range_j); + const struct fxdiv_divisor_size_t range_m = threadpool->params.parallelize_6d.range_m; + const struct fxdiv_result_size_t index_l_m = fxdiv_divide_size_t(index_lm_n.quotient, range_m); + size_t i = index_i_j.quotient; + size_t j = index_i_j.remainder; + size_t k = index_ij_k.remainder; + size_t l = index_l_m.quotient; + size_t m = index_l_m.remainder; + size_t n = index_lm_n.remainder; + + const size_t range_l = threadpool->params.parallelize_6d.range_l; + while (pthreadpool_try_decrement_relaxed_size_t(&thread->range_length)) { + task(argument, i, j, k, l, m, n); + if (++n == range_n.value) { + n = 0; + if (++m == range_m.value) { + m = 0; + if (++l == range_l) { + l = 0; + if (++k == range_k.value) { + k = 0; + if (++j == range_j.value) { + j = 0; + i += 1; + } + } + } + } + } + } + + + /* There still may be other threads with work */ + const size_t thread_number = thread->thread_number; + const size_t threads_count = threadpool->threads_count.value; + for (size_t tid = modulo_decrement(thread_number, threads_count); + tid != thread_number; + tid = modulo_decrement(tid, threads_count)) + { + struct thread_info* other_thread = &threadpool->threads[tid]; + while (pthreadpool_try_decrement_relaxed_size_t(&other_thread->range_length)) { + const size_t linear_index = pthreadpool_decrement_fetch_relaxed_size_t(&other_thread->range_end); + const struct fxdiv_result_size_t index_ijk_lmn = fxdiv_divide_size_t(linear_index, range_lmn); + const struct fxdiv_result_size_t index_ij_k = fxdiv_divide_size_t(index_ijk_lmn.quotient, range_k); + const struct fxdiv_result_size_t index_lm_n = fxdiv_divide_size_t(index_ijk_lmn.remainder, range_n); + const struct fxdiv_result_size_t index_i_j = fxdiv_divide_size_t(index_ij_k.quotient, range_j); + const struct fxdiv_result_size_t index_l_m = fxdiv_divide_size_t(index_lm_n.quotient, range_m); + task(argument, index_i_j.quotient, index_i_j.remainder, index_ij_k.remainder, index_l_m.quotient, index_l_m.remainder, index_lm_n.remainder); + } + } + + /* Make changes by this thread visible to other threads */ + pthreadpool_fence_release(); +} + +static void thread_parallelize_6d_tile_1d(struct pthreadpool* threadpool, struct thread_info* thread) { + assert(threadpool != NULL); + assert(thread != NULL); + + const pthreadpool_task_6d_tile_1d_t task = (pthreadpool_task_6d_tile_1d_t) pthreadpool_load_relaxed_void_p(&threadpool->task); + void *const argument = pthreadpool_load_relaxed_void_p(&threadpool->argument); + + /* Process thread's own range of items */ + const size_t range_start = pthreadpool_load_relaxed_size_t(&thread->range_start); + const struct fxdiv_divisor_size_t tile_range_lmn = threadpool->params.parallelize_6d_tile_1d.tile_range_lmn; + const struct fxdiv_result_size_t tile_index_ijk_lmn = fxdiv_divide_size_t(range_start, tile_range_lmn); + const struct fxdiv_divisor_size_t range_k = threadpool->params.parallelize_6d_tile_1d.range_k; + const struct fxdiv_result_size_t index_ij_k = fxdiv_divide_size_t(tile_index_ijk_lmn.quotient, range_k); + const struct fxdiv_divisor_size_t tile_range_n = threadpool->params.parallelize_6d_tile_1d.tile_range_n; + const struct fxdiv_result_size_t tile_index_lm_n = fxdiv_divide_size_t(tile_index_ijk_lmn.remainder, tile_range_n); + const struct fxdiv_divisor_size_t range_j = threadpool->params.parallelize_6d_tile_1d.range_j; + const struct fxdiv_result_size_t index_i_j = fxdiv_divide_size_t(index_ij_k.quotient, range_j); + const struct fxdiv_divisor_size_t range_m = threadpool->params.parallelize_6d_tile_1d.range_m; + const struct fxdiv_result_size_t index_l_m = fxdiv_divide_size_t(tile_index_lm_n.quotient, range_m); + const size_t tile_n = threadpool->params.parallelize_6d_tile_1d.tile_n; + size_t i = index_i_j.quotient; + size_t j = index_i_j.remainder; + size_t k = index_ij_k.remainder; + size_t l = index_l_m.quotient; + size_t m = index_l_m.remainder; + size_t start_n = tile_index_lm_n.remainder * tile_n; + + const size_t range_n = threadpool->params.parallelize_6d_tile_1d.range_n; + const size_t range_l = threadpool->params.parallelize_6d_tile_1d.range_l; + while (pthreadpool_try_decrement_relaxed_size_t(&thread->range_length)) { + task(argument, i, j, k, l, m, start_n, min(range_n - start_n, tile_n)); + start_n += tile_n; + if (start_n >= range_n) { + start_n = 0; + if (++m == range_m.value) { + m = 0; + if (++l == range_l) { + l = 0; + if (++k == range_k.value) { + k = 0; + if (++j == range_j.value) { + j = 0; + i += 1; + } + } + } + } + } + } + + + /* There still may be other threads with work */ + const size_t thread_number = thread->thread_number; + const size_t threads_count = threadpool->threads_count.value; + for (size_t tid = modulo_decrement(thread_number, threads_count); + tid != thread_number; + tid = modulo_decrement(tid, threads_count)) + { + struct thread_info* other_thread = &threadpool->threads[tid]; + while (pthreadpool_try_decrement_relaxed_size_t(&other_thread->range_length)) { + const size_t linear_index = pthreadpool_decrement_fetch_relaxed_size_t(&other_thread->range_end); + const struct fxdiv_result_size_t tile_index_ijk_lmn = fxdiv_divide_size_t(linear_index, tile_range_lmn); + const struct fxdiv_result_size_t index_ij_k = fxdiv_divide_size_t(tile_index_ijk_lmn.quotient, range_k); + const struct fxdiv_result_size_t tile_index_lm_n = fxdiv_divide_size_t(tile_index_ijk_lmn.remainder, tile_range_n); + const struct fxdiv_result_size_t index_i_j = fxdiv_divide_size_t(index_ij_k.quotient, range_j); + const struct fxdiv_result_size_t index_l_m = fxdiv_divide_size_t(tile_index_lm_n.quotient, range_m); + const size_t start_n = tile_index_lm_n.remainder * tile_n; + task(argument, index_i_j.quotient, index_i_j.remainder, index_ij_k.remainder, index_l_m.quotient, index_l_m.remainder, + start_n, min(range_n - start_n, tile_n)); + } + } + + /* Make changes by this thread visible to other threads */ + pthreadpool_fence_release(); +} + static void thread_parallelize_6d_tile_2d(struct pthreadpool* threadpool, struct thread_info* thread) { assert(threadpool != NULL); assert(thread != NULL); @@ -2043,6 +2190,130 @@ void pthreadpool_parallelize_5d_tile_2d( } } +void pthreadpool_parallelize_6d( + pthreadpool_t threadpool, + pthreadpool_task_6d_t task, + void* argument, + size_t range_i, + size_t range_j, + size_t range_k, + size_t range_l, + size_t range_m, + size_t range_n, + uint32_t flags) +{ + size_t threads_count; + if (threadpool == NULL || (threads_count = threadpool->threads_count.value) <= 1 || (range_i | range_j | range_k | range_l | range_m | range_n) <= 1) { + /* No thread pool used: execute task sequentially on the calling thread */ + struct fpu_state saved_fpu_state = { 0 }; + if (flags & PTHREADPOOL_FLAG_DISABLE_DENORMALS) { + saved_fpu_state = get_fpu_state(); + disable_fpu_denormals(); + } + for (size_t i = 0; i < range_i; i++) { + for (size_t j = 0; j < range_j; j++) { + for (size_t k = 0; k < range_k; k++) { + for (size_t l = 0; l < range_l; l++) { + for (size_t m = 0; m < range_m; m++) { + for (size_t n = 0; n < range_n; n++) { + task(argument, i, j, k, l, m, n); + } + } + } + } + } + } + if (flags & PTHREADPOOL_FLAG_DISABLE_DENORMALS) { + set_fpu_state(saved_fpu_state); + } + } else { + const size_t range_lmn = range_l * range_m * range_n; + const size_t range = range_i * range_j * range_k * range_lmn; + const struct pthreadpool_6d_params params = { + .range_l = range_l, + .range_j = fxdiv_init_size_t(range_j), + .range_k = fxdiv_init_size_t(range_k), + .range_lmn = fxdiv_init_size_t(range_lmn), + .range_m = fxdiv_init_size_t(range_m), + .range_n = fxdiv_init_size_t(range_n), + }; + thread_function_t parallelize_6d = &thread_parallelize_6d; + #if PTHREADPOOL_USE_FASTPATH + const size_t range_threshold = -threads_count; + if (range < range_threshold) { + parallelize_6d = &pthreadpool_thread_parallelize_6d_fastpath; + } + #endif + pthreadpool_parallelize( + threadpool, parallelize_6d, ¶ms, sizeof(params), + task, argument, range, flags); + } +} + +void pthreadpool_parallelize_6d_tile_1d( + pthreadpool_t threadpool, + pthreadpool_task_6d_tile_1d_t task, + void* argument, + size_t range_i, + size_t range_j, + size_t range_k, + size_t range_l, + size_t range_m, + size_t range_n, + size_t tile_n, + uint32_t flags) +{ + size_t threads_count; + if (threadpool == NULL || (threads_count = threadpool->threads_count.value) <= 1 || ((range_i | range_j | range_k | range_l | range_m) <= 1 && range_n <= tile_n)) { + /* No thread pool used: execute task sequentially on the calling thread */ + struct fpu_state saved_fpu_state = { 0 }; + if (flags & PTHREADPOOL_FLAG_DISABLE_DENORMALS) { + saved_fpu_state = get_fpu_state(); + disable_fpu_denormals(); + } + for (size_t i = 0; i < range_i; i++) { + for (size_t j = 0; j < range_j; j++) { + for (size_t k = 0; k < range_k; k++) { + for (size_t l = 0; l < range_l; l++) { + for (size_t m = 0; m < range_m; m++) { + for (size_t n = 0; n < range_n; n += tile_n) { + task(argument, i, j, k, l, m, n, min(range_n - n, tile_n)); + } + } + } + } + } + } + if (flags & PTHREADPOOL_FLAG_DISABLE_DENORMALS) { + set_fpu_state(saved_fpu_state); + } + } else { + const size_t tile_range_n = divide_round_up(range_n, tile_n); + const size_t tile_range_lmn = range_l * range_m * tile_range_n; + const size_t tile_range = range_i * range_j * range_k * tile_range_lmn; + const struct pthreadpool_6d_tile_1d_params params = { + .range_l = range_l, + .range_n = range_n, + .tile_n = tile_n, + .range_j = fxdiv_init_size_t(range_j), + .range_k = fxdiv_init_size_t(range_k), + .tile_range_lmn = fxdiv_init_size_t(tile_range_lmn), + .range_m = fxdiv_init_size_t(range_m), + .tile_range_n = fxdiv_init_size_t(tile_range_n), + }; + thread_function_t parallelize_6d_tile_1d = &thread_parallelize_6d_tile_1d; + #if PTHREADPOOL_USE_FASTPATH + const size_t range_threshold = -threads_count; + if (tile_range < range_threshold) { + parallelize_6d_tile_1d = &pthreadpool_thread_parallelize_6d_tile_1d_fastpath; + } + #endif + pthreadpool_parallelize( + threadpool, parallelize_6d_tile_1d, ¶ms, sizeof(params), + task, argument, tile_range, flags); + } +} + void pthreadpool_parallelize_6d_tile_2d( pthreadpool_t threadpool, pthreadpool_task_6d_tile_2d_t task, @@ -383,6 +383,61 @@ void pthreadpool_parallelize_5d_tile_2d( } } +void pthreadpool_parallelize_6d( + pthreadpool_t threadpool, + pthreadpool_task_6d_t task, + void* argument, + size_t range_i, + size_t range_j, + size_t range_k, + size_t range_l, + size_t range_m, + size_t range_n, + uint32_t flags) +{ + for (size_t i = 0; i < range_i; i++) { + for (size_t j = 0; j < range_j; j++) { + for (size_t k = 0; k < range_k; k++) { + for (size_t l = 0; l < range_l; l++) { + for (size_t m = 0; m < range_m; m++) { + for (size_t n = 0; n < range_n; n++) { + task(argument, i, j, k, l, m, n); + } + } + } + } + } + } +} + +void pthreadpool_parallelize_6d_tile_1d( + pthreadpool_t threadpool, + pthreadpool_task_6d_tile_1d_t task, + void* argument, + size_t range_i, + size_t range_j, + size_t range_k, + size_t range_l, + size_t range_m, + size_t range_n, + size_t tile_n, + uint32_t flags) +{ + for (size_t i = 0; i < range_i; i++) { + for (size_t j = 0; j < range_j; j++) { + for (size_t k = 0; k < range_k; k++) { + for (size_t l = 0; l < range_l; l++) { + for (size_t m = 0; m < range_m; m++) { + for (size_t n = 0; n < range_n; n += tile_n) { + task(argument, i, j, k, l, m, n, min(range_n - n, tile_n)); + } + } + } + } + } + } +} + void pthreadpool_parallelize_6d_tile_2d( pthreadpool_t threadpool, pthreadpool_task_6d_tile_2d_t task, diff --git a/src/threadpool-atomics.h b/src/threadpool-atomics.h index f0ddd89..23f943a 100644 --- a/src/threadpool-atomics.h +++ b/src/threadpool-atomics.h @@ -130,7 +130,7 @@ static inline void pthreadpool_fence_release() { __c11_atomic_thread_fence(__ATOMIC_RELEASE); } -#elif defined(__STDC_VERSION__) && (__STDC_VERSION__ >= 201112L) +#elif defined(__STDC_VERSION__) && (__STDC_VERSION__ >= 201112L) && !defined(__STDC_NO_ATOMICS__) #include <stdatomic.h> typedef _Atomic(uint32_t) pthreadpool_atomic_uint32_t; @@ -247,6 +247,110 @@ static inline void pthreadpool_fence_release() { atomic_thread_fence(memory_order_release); } +#elif defined(__GNUC__) + typedef uint32_t volatile pthreadpool_atomic_uint32_t; + typedef size_t volatile pthreadpool_atomic_size_t; + typedef void* volatile pthreadpool_atomic_void_p; + + static inline uint32_t pthreadpool_load_relaxed_uint32_t( + pthreadpool_atomic_uint32_t* address) + { + return *address; + } + + static inline size_t pthreadpool_load_relaxed_size_t( + pthreadpool_atomic_size_t* address) + { + return *address; + } + + static inline void* pthreadpool_load_relaxed_void_p( + pthreadpool_atomic_void_p* address) + { + return *address; + } + + static inline uint32_t pthreadpool_load_acquire_uint32_t( + pthreadpool_atomic_uint32_t* address) + { + return *address; + } + + static inline size_t pthreadpool_load_acquire_size_t( + pthreadpool_atomic_size_t* address) + { + return *address; + } + + static inline void pthreadpool_store_relaxed_uint32_t( + pthreadpool_atomic_uint32_t* address, + uint32_t value) + { + *address = value; + } + + static inline void pthreadpool_store_relaxed_size_t( + pthreadpool_atomic_size_t* address, + size_t value) + { + *address = value; + } + + static inline void pthreadpool_store_relaxed_void_p( + pthreadpool_atomic_void_p* address, + void* value) + { + *address = value; + } + + static inline void pthreadpool_store_release_uint32_t( + pthreadpool_atomic_uint32_t* address, + uint32_t value) + { + *address = value; + } + + static inline void pthreadpool_store_release_size_t( + pthreadpool_atomic_size_t* address, + size_t value) + { + *address = value; + } + + static inline size_t pthreadpool_decrement_fetch_relaxed_size_t( + pthreadpool_atomic_size_t* address) + { + return __sync_sub_and_fetch(address, 1); + } + + static inline size_t pthreadpool_decrement_fetch_release_size_t( + pthreadpool_atomic_size_t* address) + { + return __sync_sub_and_fetch(address, 1); + } + + static inline bool pthreadpool_try_decrement_relaxed_size_t( + pthreadpool_atomic_size_t* value) + { + size_t actual_value = *value; + while (actual_value != 0) { + const size_t new_value = actual_value - 1; + const size_t expected_value = actual_value; + actual_value = __sync_val_compare_and_swap(value, expected_value, new_value); + if (actual_value == expected_value) { + return true; + } + } + return false; + } + + static inline void pthreadpool_fence_acquire() { + __sync_synchronize(); + } + + static inline void pthreadpool_fence_release() { + __sync_synchronize(); + } #elif defined(_MSC_VER) && defined(_M_X64) typedef volatile uint32_t pthreadpool_atomic_uint32_t; typedef volatile size_t pthreadpool_atomic_size_t; diff --git a/src/threadpool-object.h b/src/threadpool-object.h index 9870e8a..590dc96 100644 --- a/src/threadpool-object.h +++ b/src/threadpool-object.h @@ -476,6 +476,68 @@ struct pthreadpool_5d_tile_2d_params { struct fxdiv_divisor_size_t tile_range_m; }; +struct pthreadpool_6d_params { + /** + * Copy of the range_l argument passed to the pthreadpool_parallelize_6d function. + */ + size_t range_l; + /** + * FXdiv divisor for the range_j argument passed to the pthreadpool_parallelize_6d function. + */ + struct fxdiv_divisor_size_t range_j; + /** + * FXdiv divisor for the range_k argument passed to the pthreadpool_parallelize_6d function. + */ + struct fxdiv_divisor_size_t range_k; + /** + * FXdiv divisor for the range_l * range_m * range_n value. + */ + struct fxdiv_divisor_size_t range_lmn; + /** + * FXdiv divisor for the range_m argument passed to the pthreadpool_parallelize_6d function. + */ + struct fxdiv_divisor_size_t range_m; + /** + * FXdiv divisor for the range_n argument passed to the pthreadpool_parallelize_6d function. + */ + struct fxdiv_divisor_size_t range_n; +}; + +struct pthreadpool_6d_tile_1d_params { + /** + * Copy of the range_l argument passed to the pthreadpool_parallelize_6d_tile_1d function. + */ + size_t range_l; + /** + * Copy of the range_n argument passed to the pthreadpool_parallelize_6d_tile_1d function. + */ + size_t range_n; + /** + * Copy of the tile_n argument passed to the pthreadpool_parallelize_6d_tile_1d function. + */ + size_t tile_n; + /** + * FXdiv divisor for the range_j argument passed to the pthreadpool_parallelize_6d_tile_1d function. + */ + struct fxdiv_divisor_size_t range_j; + /** + * FXdiv divisor for the range_k argument passed to the pthreadpool_parallelize_6d_tile_1d function. + */ + struct fxdiv_divisor_size_t range_k; + /** + * FXdiv divisor for the range_l * range_m * divide_round_up(range_n, tile_n) value. + */ + struct fxdiv_divisor_size_t tile_range_lmn; + /** + * FXdiv divisor for the range_m argument passed to the pthreadpool_parallelize_6d_tile_1d function. + */ + struct fxdiv_divisor_size_t range_m; + /** + * FXdiv divisor for the divide_round_up(range_n, tile_n) value. + */ + struct fxdiv_divisor_size_t tile_range_n; +}; + struct pthreadpool_6d_tile_2d_params { /** * Copy of the range_k argument passed to the pthreadpool_parallelize_6d_tile_2d function. @@ -575,6 +637,8 @@ struct PTHREADPOOL_CACHELINE_ALIGNED pthreadpool { struct pthreadpool_5d_params parallelize_5d; struct pthreadpool_5d_tile_1d_params parallelize_5d_tile_1d; struct pthreadpool_5d_tile_2d_params parallelize_5d_tile_2d; + struct pthreadpool_6d_params parallelize_6d; + struct pthreadpool_6d_tile_1d_params parallelize_6d_tile_1d; struct pthreadpool_6d_tile_2d_params parallelize_6d_tile_2d; } params; /** @@ -735,6 +799,14 @@ PTHREADPOOL_INTERNAL void pthreadpool_thread_parallelize_5d_tile_2d_fastpath( struct pthreadpool* threadpool, struct thread_info* thread); +PTHREADPOOL_INTERNAL void pthreadpool_thread_parallelize_6d_fastpath( + struct pthreadpool* threadpool, + struct thread_info* thread); + +PTHREADPOOL_INTERNAL void pthreadpool_thread_parallelize_6d_tile_1d_fastpath( + struct pthreadpool* threadpool, + struct thread_info* thread); + PTHREADPOOL_INTERNAL void pthreadpool_thread_parallelize_6d_tile_2d_fastpath( struct pthreadpool* threadpool, struct thread_info* thread); diff --git a/test/pthreadpool.cc b/test/pthreadpool.cc index f822506..c9592ec 100644 --- a/test/pthreadpool.cc +++ b/test/pthreadpool.cc @@ -68,6 +68,19 @@ const size_t kParallelize5DTile2DRangeL = 23; const size_t kParallelize5DTile2DRangeM = 29; const size_t kParallelize5DTile2DTileL = 3; const size_t kParallelize5DTile2DTileM = 2; +const size_t kParallelize6DRangeI = 3; +const size_t kParallelize6DRangeJ = 5; +const size_t kParallelize6DRangeK = 7; +const size_t kParallelize6DRangeL = 11; +const size_t kParallelize6DRangeM = 13; +const size_t kParallelize6DRangeN = 17; +const size_t kParallelize6DTile1DRangeI = 5; +const size_t kParallelize6DTile1DRangeJ = 7; +const size_t kParallelize6DTile1DRangeK = 11; +const size_t kParallelize6DTile1DRangeL = 13; +const size_t kParallelize6DTile1DRangeM = 17; +const size_t kParallelize6DTile1DRangeN = 19; +const size_t kParallelize6DTile1DTileN = 5; const size_t kParallelize6DTile2DRangeI = 7; const size_t kParallelize6DTile2DRangeJ = 11; const size_t kParallelize6DTile2DRangeK = 13; @@ -6267,6 +6280,724 @@ TEST(Parallelize5DTile2D, MultiThreadPoolWorkStealing) { EXPECT_EQ(num_processed_items.load(std::memory_order_relaxed), kParallelize5DTile2DRangeI * kParallelize5DTile2DRangeJ * kParallelize5DTile2DRangeK * kParallelize5DTile2DRangeL * kParallelize5DTile2DRangeM); } +static void ComputeNothing6D(void*, size_t, size_t, size_t, size_t, size_t, size_t) { +} + +TEST(Parallelize6D, SingleThreadPoolCompletes) { + auto_pthreadpool_t threadpool(pthreadpool_create(1), pthreadpool_destroy); + ASSERT_TRUE(threadpool.get()); + + pthreadpool_parallelize_6d(threadpool.get(), + ComputeNothing6D, + nullptr, + kParallelize6DRangeI, kParallelize6DRangeJ, kParallelize6DRangeK, kParallelize6DRangeL, kParallelize6DRangeM, kParallelize6DRangeN, + 0 /* flags */); +} + +TEST(Parallelize6D, MultiThreadPoolCompletes) { + auto_pthreadpool_t threadpool(pthreadpool_create(0), pthreadpool_destroy); + ASSERT_TRUE(threadpool.get()); + + if (pthreadpool_get_threads_count(threadpool.get()) <= 1) { + GTEST_SKIP(); + } + + pthreadpool_parallelize_6d( + threadpool.get(), + ComputeNothing6D, + nullptr, + kParallelize6DRangeI, kParallelize6DRangeJ, kParallelize6DRangeK, kParallelize6DRangeL, kParallelize6DRangeM, kParallelize6DRangeN, + 0 /* flags */); +} + +static void CheckBounds6D(void*, size_t i, size_t j, size_t k, size_t l, size_t m, size_t n) { + EXPECT_LT(i, kParallelize6DRangeI); + EXPECT_LT(j, kParallelize6DRangeJ); + EXPECT_LT(k, kParallelize6DRangeK); + EXPECT_LT(l, kParallelize6DRangeL); + EXPECT_LT(m, kParallelize6DRangeM); + EXPECT_LT(n, kParallelize6DRangeN); +} + +TEST(Parallelize6D, SingleThreadPoolAllItemsInBounds) { + auto_pthreadpool_t threadpool(pthreadpool_create(1), pthreadpool_destroy); + ASSERT_TRUE(threadpool.get()); + + pthreadpool_parallelize_6d( + threadpool.get(), + CheckBounds6D, + nullptr, + kParallelize6DRangeI, kParallelize6DRangeJ, kParallelize6DRangeK, kParallelize6DRangeL, kParallelize6DRangeM, kParallelize6DRangeN, + 0 /* flags */); +} + +TEST(Parallelize6D, MultiThreadPoolAllItemsInBounds) { + auto_pthreadpool_t threadpool(pthreadpool_create(0), pthreadpool_destroy); + ASSERT_TRUE(threadpool.get()); + + if (pthreadpool_get_threads_count(threadpool.get()) <= 1) { + GTEST_SKIP(); + } + + pthreadpool_parallelize_6d( + threadpool.get(), + CheckBounds6D, + nullptr, + kParallelize6DRangeI, kParallelize6DRangeJ, kParallelize6DRangeK, kParallelize6DRangeL, kParallelize6DRangeM, kParallelize6DRangeN, + 0 /* flags */); +} + +static void SetTrue6D(std::atomic_bool* processed_indicators, size_t i, size_t j, size_t k, size_t l, size_t m, size_t n) { + const size_t linear_idx = ((((i * kParallelize6DRangeJ + j) * kParallelize6DRangeK + k) * kParallelize6DRangeL + l) * kParallelize6DRangeM + m) * kParallelize6DRangeN + n; + processed_indicators[linear_idx].store(true, std::memory_order_relaxed); +} + +TEST(Parallelize6D, SingleThreadPoolAllItemsProcessed) { + std::vector<std::atomic_bool> indicators(kParallelize6DRangeI * kParallelize6DRangeJ * kParallelize6DRangeK * kParallelize6DRangeL * kParallelize6DRangeM * kParallelize6DRangeN); + + auto_pthreadpool_t threadpool(pthreadpool_create(1), pthreadpool_destroy); + ASSERT_TRUE(threadpool.get()); + + pthreadpool_parallelize_6d( + threadpool.get(), + reinterpret_cast<pthreadpool_task_6d_t>(SetTrue6D), + static_cast<void*>(indicators.data()), + kParallelize6DRangeI, kParallelize6DRangeJ, kParallelize6DRangeK, kParallelize6DRangeL, kParallelize6DRangeM, kParallelize6DRangeN, + 0 /* flags */); + + for (size_t i = 0; i < kParallelize6DRangeI; i++) { + for (size_t j = 0; j < kParallelize6DRangeJ; j++) { + for (size_t k = 0; k < kParallelize6DRangeK; k++) { + for (size_t l = 0; l < kParallelize6DRangeL; l++) { + for (size_t m = 0; m < kParallelize6DRangeM; m++) { + for (size_t n = 0; n < kParallelize6DRangeN; n++) { + const size_t linear_idx = ((((i * kParallelize6DRangeJ + j) * kParallelize6DRangeK + k) * kParallelize6DRangeL + l) * kParallelize6DRangeM + m) * kParallelize6DRangeN + n; + EXPECT_TRUE(indicators[linear_idx].load(std::memory_order_relaxed)) + << "Element (" << i << ", " << j << ", " << k << ", " << l << ", " << m << ", " << n << ") not processed"; + } + } + } + } + } + } +} + +TEST(Parallelize6D, MultiThreadPoolAllItemsProcessed) { + std::vector<std::atomic_bool> indicators(kParallelize6DRangeI * kParallelize6DRangeJ * kParallelize6DRangeK * kParallelize6DRangeL * kParallelize6DRangeM * kParallelize6DRangeN); + + auto_pthreadpool_t threadpool(pthreadpool_create(0), pthreadpool_destroy); + ASSERT_TRUE(threadpool.get()); + + if (pthreadpool_get_threads_count(threadpool.get()) <= 1) { + GTEST_SKIP(); + } + + pthreadpool_parallelize_6d( + threadpool.get(), + reinterpret_cast<pthreadpool_task_6d_t>(SetTrue6D), + static_cast<void*>(indicators.data()), + kParallelize6DRangeI, kParallelize6DRangeJ, kParallelize6DRangeK, kParallelize6DRangeL, kParallelize6DRangeM, kParallelize6DRangeN, + 0 /* flags */); + + for (size_t i = 0; i < kParallelize6DRangeI; i++) { + for (size_t j = 0; j < kParallelize6DRangeJ; j++) { + for (size_t k = 0; k < kParallelize6DRangeK; k++) { + for (size_t l = 0; l < kParallelize6DRangeL; l++) { + for (size_t m = 0; m < kParallelize6DRangeM; m++) { + for (size_t n = 0; n < kParallelize6DRangeN; n++) { + const size_t linear_idx = ((((i * kParallelize6DRangeJ + j) * kParallelize6DRangeK + k) * kParallelize6DRangeL + l) * kParallelize6DRangeM + m) * kParallelize6DRangeN + n; + EXPECT_TRUE(indicators[linear_idx].load(std::memory_order_relaxed)) + << "Element (" << i << ", " << j << ", " << k << ", " << l << ", " << m << ", " << n << ") not processed"; + } + } + } + } + } + } +} + +static void Increment6D(std::atomic_int* processed_counters, size_t i, size_t j, size_t k, size_t l, size_t m, size_t n) { + const size_t linear_idx = ((((i * kParallelize6DRangeJ + j) * kParallelize6DRangeK + k) * kParallelize6DRangeL + l) * kParallelize6DRangeM + m) * kParallelize6DRangeN + n; + processed_counters[linear_idx].fetch_add(1, std::memory_order_relaxed); +} + +TEST(Parallelize6D, SingleThreadPoolEachItemProcessedOnce) { + std::vector<std::atomic_int> counters(kParallelize6DRangeI * kParallelize6DRangeJ * kParallelize6DRangeK * kParallelize6DRangeL * kParallelize6DRangeM * kParallelize6DRangeN); + + auto_pthreadpool_t threadpool(pthreadpool_create(1), pthreadpool_destroy); + ASSERT_TRUE(threadpool.get()); + + pthreadpool_parallelize_6d( + threadpool.get(), + reinterpret_cast<pthreadpool_task_6d_t>(Increment6D), + static_cast<void*>(counters.data()), + kParallelize6DRangeI, kParallelize6DRangeJ, kParallelize6DRangeK, kParallelize6DRangeL, kParallelize6DRangeM, kParallelize6DRangeN, + 0 /* flags */); + + for (size_t i = 0; i < kParallelize6DRangeI; i++) { + for (size_t j = 0; j < kParallelize6DRangeJ; j++) { + for (size_t k = 0; k < kParallelize6DRangeK; k++) { + for (size_t l = 0; l < kParallelize6DRangeL; l++) { + for (size_t m = 0; m < kParallelize6DRangeM; m++) { + for (size_t n = 0; n < kParallelize6DRangeN; n++) { + const size_t linear_idx = ((((i * kParallelize6DRangeJ + j) * kParallelize6DRangeK + k) * kParallelize6DRangeL + l) * kParallelize6DRangeM + m) * kParallelize6DRangeN + n; + EXPECT_EQ(counters[linear_idx].load(std::memory_order_relaxed), 1) + << "Element (" << i << ", " << j << ", " << k << ", " << l << ", " << m << ", " << n << ") was processed " + << counters[linear_idx].load(std::memory_order_relaxed) << " times (expected: 1)"; + } + } + } + } + } + } +} + +TEST(Parallelize6D, MultiThreadPoolEachItemProcessedOnce) { + std::vector<std::atomic_int> counters(kParallelize6DRangeI * kParallelize6DRangeJ * kParallelize6DRangeK * kParallelize6DRangeL * kParallelize6DRangeM * kParallelize6DRangeN); + + auto_pthreadpool_t threadpool(pthreadpool_create(0), pthreadpool_destroy); + ASSERT_TRUE(threadpool.get()); + + if (pthreadpool_get_threads_count(threadpool.get()) <= 1) { + GTEST_SKIP(); + } + + pthreadpool_parallelize_6d( + threadpool.get(), + reinterpret_cast<pthreadpool_task_6d_t>(Increment6D), + static_cast<void*>(counters.data()), + kParallelize6DRangeI, kParallelize6DRangeJ, kParallelize6DRangeK, kParallelize6DRangeL, kParallelize6DRangeM, kParallelize6DRangeN, + 0 /* flags */); + + for (size_t i = 0; i < kParallelize6DRangeI; i++) { + for (size_t j = 0; j < kParallelize6DRangeJ; j++) { + for (size_t k = 0; k < kParallelize6DRangeK; k++) { + for (size_t l = 0; l < kParallelize6DRangeL; l++) { + for (size_t m = 0; m < kParallelize6DRangeM; m++) { + for (size_t n = 0; n < kParallelize6DRangeN; n++) { + const size_t linear_idx = ((((i * kParallelize6DRangeJ + j) * kParallelize6DRangeK + k) * kParallelize6DRangeL + l) * kParallelize6DRangeM + m) * kParallelize6DRangeN + n; + EXPECT_EQ(counters[linear_idx].load(std::memory_order_relaxed), 1) + << "Element (" << i << ", " << j << ", " << k << ", " << l << ", " << m << ", " << n << ") was processed " + << counters[linear_idx].load(std::memory_order_relaxed) << " times (expected: 1)"; + } + } + } + } + } + } +} + +TEST(Parallelize6D, SingleThreadPoolEachItemProcessedMultipleTimes) { + std::vector<std::atomic_int> counters(kParallelize6DRangeI * kParallelize6DRangeJ * kParallelize6DRangeK * kParallelize6DRangeL * kParallelize6DRangeM * kParallelize6DRangeN); + + auto_pthreadpool_t threadpool(pthreadpool_create(1), pthreadpool_destroy); + ASSERT_TRUE(threadpool.get()); + + for (size_t iteration = 0; iteration < kIncrementIterations6D; iteration++) { + pthreadpool_parallelize_6d( + threadpool.get(), + reinterpret_cast<pthreadpool_task_6d_t>(Increment6D), + static_cast<void*>(counters.data()), + kParallelize6DRangeI, kParallelize6DRangeJ, kParallelize6DRangeK, kParallelize6DRangeL, kParallelize6DRangeM, kParallelize6DRangeN, + 0 /* flags */); + } + + for (size_t i = 0; i < kParallelize6DRangeI; i++) { + for (size_t j = 0; j < kParallelize6DRangeJ; j++) { + for (size_t k = 0; k < kParallelize6DRangeK; k++) { + for (size_t l = 0; l < kParallelize6DRangeL; l++) { + for (size_t m = 0; m < kParallelize6DRangeM; m++) { + for (size_t n = 0; n < kParallelize6DRangeN; n++) { + const size_t linear_idx = ((((i * kParallelize6DRangeJ + j) * kParallelize6DRangeK + k) * kParallelize6DRangeL + l) * kParallelize6DRangeM + m) * kParallelize6DRangeN; + EXPECT_EQ(counters[linear_idx].load(std::memory_order_relaxed), kIncrementIterations6D) + << "Element (" << i << ", " << j << ", " << k << ", " << l << ", " << m << ", " << n << ") was processed " + << counters[linear_idx].load(std::memory_order_relaxed) << " times " + << "(expected: " << kIncrementIterations6D << ")"; + } + } + } + } + } + } +} + +TEST(Parallelize6D, MultiThreadPoolEachItemProcessedMultipleTimes) { + std::vector<std::atomic_int> counters(kParallelize6DRangeI * kParallelize6DRangeJ * kParallelize6DRangeK * kParallelize6DRangeL * kParallelize6DRangeM * kParallelize6DRangeN); + + auto_pthreadpool_t threadpool(pthreadpool_create(0), pthreadpool_destroy); + ASSERT_TRUE(threadpool.get()); + + if (pthreadpool_get_threads_count(threadpool.get()) <= 1) { + GTEST_SKIP(); + } + + for (size_t iteration = 0; iteration < kIncrementIterations6D; iteration++) { + pthreadpool_parallelize_6d( + threadpool.get(), + reinterpret_cast<pthreadpool_task_6d_t>(Increment6D), + static_cast<void*>(counters.data()), + kParallelize6DRangeI, kParallelize6DRangeJ, kParallelize6DRangeK, kParallelize6DRangeL, kParallelize6DRangeM, kParallelize6DRangeN, + 0 /* flags */); + } + + for (size_t i = 0; i < kParallelize6DRangeI; i++) { + for (size_t j = 0; j < kParallelize6DRangeJ; j++) { + for (size_t k = 0; k < kParallelize6DRangeK; k++) { + for (size_t l = 0; l < kParallelize6DRangeL; l++) { + for (size_t m = 0; m < kParallelize6DRangeM; m++) { + for (size_t n = 0; n < kParallelize6DRangeN; n++) { + const size_t linear_idx = ((((i * kParallelize6DRangeJ + j) * kParallelize6DRangeK + k) * kParallelize6DRangeL + l) * kParallelize6DRangeM + m) * kParallelize6DRangeN + n; + EXPECT_EQ(counters[linear_idx].load(std::memory_order_relaxed), kIncrementIterations6D) + << "Element (" << i << ", " << j << ", " << k << ", " << l << ", " << m << ", " << n << ") was processed " + << counters[linear_idx].load(std::memory_order_relaxed) << " times " + << "(expected: " << kIncrementIterations6D << ")"; + } + } + } + } + } + } +} + +static void IncrementSame6D(std::atomic_int* num_processed_items, size_t i, size_t j, size_t k, size_t l, size_t m, size_t n) { + num_processed_items->fetch_add(1, std::memory_order_relaxed); +} + +TEST(Parallelize6D, MultiThreadPoolHighContention) { + std::atomic_int num_processed_items = ATOMIC_VAR_INIT(0); + + auto_pthreadpool_t threadpool(pthreadpool_create(0), pthreadpool_destroy); + ASSERT_TRUE(threadpool.get()); + + if (pthreadpool_get_threads_count(threadpool.get()) <= 1) { + GTEST_SKIP(); + } + + pthreadpool_parallelize_6d( + threadpool.get(), + reinterpret_cast<pthreadpool_task_6d_t>(IncrementSame6D), + static_cast<void*>(&num_processed_items), + kParallelize6DRangeI, kParallelize6DRangeJ, kParallelize6DRangeK, kParallelize6DRangeL, kParallelize6DRangeM, kParallelize6DRangeN, + 0 /* flags */); + EXPECT_EQ(num_processed_items.load(std::memory_order_relaxed), kParallelize6DRangeI * kParallelize6DRangeJ * kParallelize6DRangeK * kParallelize6DRangeL * kParallelize6DRangeM * kParallelize6DRangeN); +} + +static void WorkImbalance6D(std::atomic_int* num_processed_items, size_t i, size_t j, size_t k, size_t l, size_t m, size_t n) { + num_processed_items->fetch_add(1, std::memory_order_relaxed); + if (i == 0 && j == 0 && k == 0 && l == 0 && m == 0 && n == 0) { + /* Spin-wait until all items are computed */ + while (num_processed_items->load(std::memory_order_relaxed) != kParallelize6DRangeI * kParallelize6DRangeJ * kParallelize6DRangeK * kParallelize6DRangeL * kParallelize6DRangeM * kParallelize6DRangeN) { + std::atomic_thread_fence(std::memory_order_acquire); + } + } +} + +TEST(Parallelize6D, MultiThreadPoolWorkStealing) { + std::atomic_int num_processed_items = ATOMIC_VAR_INIT(0); + + auto_pthreadpool_t threadpool(pthreadpool_create(0), pthreadpool_destroy); + ASSERT_TRUE(threadpool.get()); + + if (pthreadpool_get_threads_count(threadpool.get()) <= 1) { + GTEST_SKIP(); + } + + pthreadpool_parallelize_6d( + threadpool.get(), + reinterpret_cast<pthreadpool_task_6d_t>(WorkImbalance6D), + static_cast<void*>(&num_processed_items), + kParallelize6DRangeI, kParallelize6DRangeJ, kParallelize6DRangeK, kParallelize6DRangeL, kParallelize6DRangeM, kParallelize6DRangeN, + 0 /* flags */); + EXPECT_EQ(num_processed_items.load(std::memory_order_relaxed), kParallelize6DRangeI * kParallelize6DRangeJ * kParallelize6DRangeK * kParallelize6DRangeL * kParallelize6DRangeM * kParallelize6DRangeN); +} + +static void ComputeNothing6DTile1D(void*, size_t, size_t, size_t, size_t, size_t, size_t, size_t) { +} + +TEST(Parallelize6DTile1D, SingleThreadPoolCompletes) { + auto_pthreadpool_t threadpool(pthreadpool_create(1), pthreadpool_destroy); + ASSERT_TRUE(threadpool.get()); + + pthreadpool_parallelize_6d_tile_1d(threadpool.get(), + ComputeNothing6DTile1D, + nullptr, + kParallelize6DTile1DRangeI, kParallelize6DTile1DRangeJ, kParallelize6DTile1DRangeK, kParallelize6DTile1DRangeL, kParallelize6DTile1DRangeM, kParallelize6DTile1DRangeN, + kParallelize6DTile1DTileN, + 0 /* flags */); +} + +TEST(Parallelize6DTile1D, MultiThreadPoolCompletes) { + auto_pthreadpool_t threadpool(pthreadpool_create(0), pthreadpool_destroy); + ASSERT_TRUE(threadpool.get()); + + if (pthreadpool_get_threads_count(threadpool.get()) <= 1) { + GTEST_SKIP(); + } + + pthreadpool_parallelize_6d_tile_1d( + threadpool.get(), + ComputeNothing6DTile1D, + nullptr, + kParallelize6DTile1DRangeI, kParallelize6DTile1DRangeJ, kParallelize6DTile1DRangeK, kParallelize6DTile1DRangeL, kParallelize6DTile1DRangeM, kParallelize6DTile1DRangeN, + kParallelize6DTile1DTileN, + 0 /* flags */); +} + +static void CheckBounds6DTile1D(void*, size_t i, size_t j, size_t k, size_t l, size_t m, size_t start_n, size_t tile_n) { + EXPECT_LT(i, kParallelize6DTile1DRangeI); + EXPECT_LT(j, kParallelize6DTile1DRangeJ); + EXPECT_LT(k, kParallelize6DTile1DRangeK); + EXPECT_LT(l, kParallelize6DTile1DRangeL); + EXPECT_LT(m, kParallelize6DTile1DRangeM); + EXPECT_LT(start_n, kParallelize6DTile1DRangeN); + EXPECT_LE(start_n + tile_n, kParallelize6DTile1DRangeN); +} + +TEST(Parallelize6DTile1D, SingleThreadPoolAllItemsInBounds) { + auto_pthreadpool_t threadpool(pthreadpool_create(1), pthreadpool_destroy); + ASSERT_TRUE(threadpool.get()); + + pthreadpool_parallelize_6d_tile_1d( + threadpool.get(), + CheckBounds6DTile1D, + nullptr, + kParallelize6DTile1DRangeI, kParallelize6DTile1DRangeJ, kParallelize6DTile1DRangeK, kParallelize6DTile1DRangeL, kParallelize6DTile1DRangeM, kParallelize6DTile1DRangeN, + kParallelize6DTile1DTileN, + 0 /* flags */); +} + +TEST(Parallelize6DTile1D, MultiThreadPoolAllItemsInBounds) { + auto_pthreadpool_t threadpool(pthreadpool_create(0), pthreadpool_destroy); + ASSERT_TRUE(threadpool.get()); + + if (pthreadpool_get_threads_count(threadpool.get()) <= 1) { + GTEST_SKIP(); + } + + pthreadpool_parallelize_6d_tile_1d( + threadpool.get(), + CheckBounds6DTile1D, + nullptr, + kParallelize6DTile1DRangeI, kParallelize6DTile1DRangeJ, kParallelize6DTile1DRangeK, kParallelize6DTile1DRangeL, kParallelize6DTile1DRangeM, kParallelize6DTile1DRangeN, + kParallelize6DTile1DTileN, + 0 /* flags */); +} + +static void CheckTiling6DTile1D(void*, size_t i, size_t j, size_t k, size_t l, size_t m, size_t start_n, size_t tile_n) { + EXPECT_GT(tile_n, 0); + EXPECT_LE(tile_n, kParallelize6DTile1DTileN); + EXPECT_EQ(start_n % kParallelize6DTile1DTileN, 0); + EXPECT_EQ(tile_n, std::min<size_t>(kParallelize6DTile1DTileN, kParallelize6DTile1DRangeN - start_n)); +} + +TEST(Parallelize6DTile1D, SingleThreadPoolUniformTiling) { + auto_pthreadpool_t threadpool(pthreadpool_create(1), pthreadpool_destroy); + ASSERT_TRUE(threadpool.get()); + + pthreadpool_parallelize_6d_tile_1d( + threadpool.get(), + CheckTiling6DTile1D, + nullptr, + kParallelize6DTile1DRangeI, kParallelize6DTile1DRangeJ, kParallelize6DTile1DRangeK, kParallelize6DTile1DRangeL, kParallelize6DTile1DRangeM, kParallelize6DTile1DRangeN, + kParallelize6DTile1DTileN, + 0 /* flags */); +} + +TEST(Parallelize6DTile1D, MultiThreadPoolUniformTiling) { + auto_pthreadpool_t threadpool(pthreadpool_create(0), pthreadpool_destroy); + ASSERT_TRUE(threadpool.get()); + + if (pthreadpool_get_threads_count(threadpool.get()) <= 1) { + GTEST_SKIP(); + } + + pthreadpool_parallelize_6d_tile_1d( + threadpool.get(), + CheckTiling6DTile1D, + nullptr, + kParallelize6DTile1DRangeI, kParallelize6DTile1DRangeJ, kParallelize6DTile1DRangeK, kParallelize6DTile1DRangeL, kParallelize6DTile1DRangeM, kParallelize6DTile1DRangeN, + kParallelize6DTile1DTileN, + 0 /* flags */); +} + +static void SetTrue6DTile1D(std::atomic_bool* processed_indicators, size_t i, size_t j, size_t k, size_t l, size_t m, size_t start_n, size_t tile_n) { + for (size_t n = start_n; n < start_n + tile_n; n++) { + const size_t linear_idx = ((((i * kParallelize6DTile1DRangeJ + j) * kParallelize6DTile1DRangeK + k) * kParallelize6DTile1DRangeL + l) * kParallelize6DTile1DRangeM + m) * kParallelize6DTile1DRangeN + n; + processed_indicators[linear_idx].store(true, std::memory_order_relaxed); + } +} + +TEST(Parallelize6DTile1D, SingleThreadPoolAllItemsProcessed) { + std::vector<std::atomic_bool> indicators(kParallelize6DTile1DRangeI * kParallelize6DTile1DRangeJ * kParallelize6DTile1DRangeK * kParallelize6DTile1DRangeL * kParallelize6DTile1DRangeM * kParallelize6DTile1DRangeN); + + auto_pthreadpool_t threadpool(pthreadpool_create(1), pthreadpool_destroy); + ASSERT_TRUE(threadpool.get()); + + pthreadpool_parallelize_6d_tile_1d( + threadpool.get(), + reinterpret_cast<pthreadpool_task_6d_tile_1d_t>(SetTrue6DTile1D), + static_cast<void*>(indicators.data()), + kParallelize6DTile1DRangeI, kParallelize6DTile1DRangeJ, kParallelize6DTile1DRangeK, kParallelize6DTile1DRangeL, kParallelize6DTile1DRangeM, kParallelize6DTile1DRangeN, + kParallelize6DTile1DTileN, + 0 /* flags */); + + for (size_t i = 0; i < kParallelize6DTile1DRangeI; i++) { + for (size_t j = 0; j < kParallelize6DTile1DRangeJ; j++) { + for (size_t k = 0; k < kParallelize6DTile1DRangeK; k++) { + for (size_t l = 0; l < kParallelize6DTile1DRangeL; l++) { + for (size_t m = 0; m < kParallelize6DTile1DRangeM; m++) { + for (size_t n = 0; n < kParallelize6DTile1DRangeN; n++) { + const size_t linear_idx = ((((i * kParallelize6DTile1DRangeJ + j) * kParallelize6DTile1DRangeK + k) * kParallelize6DTile1DRangeL + l) * kParallelize6DTile1DRangeM + m) * kParallelize6DTile1DRangeN + n; + EXPECT_TRUE(indicators[linear_idx].load(std::memory_order_relaxed)) + << "Element (" << i << ", " << j << ", " << k << ", " << l << ", " << m << ", " << n << ") not processed"; + } + } + } + } + } + } +} + +TEST(Parallelize6DTile1D, MultiThreadPoolAllItemsProcessed) { + std::vector<std::atomic_bool> indicators(kParallelize6DTile1DRangeI * kParallelize6DTile1DRangeJ * kParallelize6DTile1DRangeK * kParallelize6DTile1DRangeL * kParallelize6DTile1DRangeM * kParallelize6DTile1DRangeN); + + auto_pthreadpool_t threadpool(pthreadpool_create(0), pthreadpool_destroy); + ASSERT_TRUE(threadpool.get()); + + if (pthreadpool_get_threads_count(threadpool.get()) <= 1) { + GTEST_SKIP(); + } + + pthreadpool_parallelize_6d_tile_1d( + threadpool.get(), + reinterpret_cast<pthreadpool_task_6d_tile_1d_t>(SetTrue6DTile1D), + static_cast<void*>(indicators.data()), + kParallelize6DTile1DRangeI, kParallelize6DTile1DRangeJ, kParallelize6DTile1DRangeK, kParallelize6DTile1DRangeL, kParallelize6DTile1DRangeM, kParallelize6DTile1DRangeN, + kParallelize6DTile1DTileN, + 0 /* flags */); + + for (size_t i = 0; i < kParallelize6DTile1DRangeI; i++) { + for (size_t j = 0; j < kParallelize6DTile1DRangeJ; j++) { + for (size_t k = 0; k < kParallelize6DTile1DRangeK; k++) { + for (size_t l = 0; l < kParallelize6DTile1DRangeL; l++) { + for (size_t m = 0; m < kParallelize6DTile1DRangeM; m++) { + for (size_t n = 0; n < kParallelize6DTile1DRangeN; n++) { + const size_t linear_idx = ((((i * kParallelize6DTile1DRangeJ + j) * kParallelize6DTile1DRangeK + k) * kParallelize6DTile1DRangeL + l) * kParallelize6DTile1DRangeM + m) * kParallelize6DTile1DRangeN + n; + EXPECT_TRUE(indicators[linear_idx].load(std::memory_order_relaxed)) + << "Element (" << i << ", " << j << ", " << k << ", " << l << ", " << m << ", " << n << ") not processed"; + } + } + } + } + } + } +} + +static void Increment6DTile1D(std::atomic_int* processed_counters, size_t i, size_t j, size_t k, size_t l, size_t m, size_t start_n, size_t tile_n) { + for (size_t n = start_n; n < start_n + tile_n; n++) { + const size_t linear_idx = ((((i * kParallelize6DTile1DRangeJ + j) * kParallelize6DTile1DRangeK + k) * kParallelize6DTile1DRangeL + l) * kParallelize6DTile1DRangeM + m) * kParallelize6DTile1DRangeN + n; + processed_counters[linear_idx].fetch_add(1, std::memory_order_relaxed); + } +} + +TEST(Parallelize6DTile1D, SingleThreadPoolEachItemProcessedOnce) { + std::vector<std::atomic_int> counters(kParallelize6DTile1DRangeI * kParallelize6DTile1DRangeJ * kParallelize6DTile1DRangeK * kParallelize6DTile1DRangeL * kParallelize6DTile1DRangeM * kParallelize6DTile1DRangeN); + + auto_pthreadpool_t threadpool(pthreadpool_create(1), pthreadpool_destroy); + ASSERT_TRUE(threadpool.get()); + + pthreadpool_parallelize_6d_tile_1d( + threadpool.get(), + reinterpret_cast<pthreadpool_task_6d_tile_1d_t>(Increment6DTile1D), + static_cast<void*>(counters.data()), + kParallelize6DTile1DRangeI, kParallelize6DTile1DRangeJ, kParallelize6DTile1DRangeK, kParallelize6DTile1DRangeL, kParallelize6DTile1DRangeM, kParallelize6DTile1DRangeN, + kParallelize6DTile1DTileN, + 0 /* flags */); + + for (size_t i = 0; i < kParallelize6DTile1DRangeI; i++) { + for (size_t j = 0; j < kParallelize6DTile1DRangeJ; j++) { + for (size_t k = 0; k < kParallelize6DTile1DRangeK; k++) { + for (size_t l = 0; l < kParallelize6DTile1DRangeL; l++) { + for (size_t m = 0; m < kParallelize6DTile1DRangeM; m++) { + for (size_t n = 0; n < kParallelize6DTile1DRangeN; n++) { + const size_t linear_idx = ((((i * kParallelize6DTile1DRangeJ + j) * kParallelize6DTile1DRangeK + k) * kParallelize6DTile1DRangeL + l) * kParallelize6DTile1DRangeM + m) * kParallelize6DTile1DRangeN + n; + EXPECT_EQ(counters[linear_idx].load(std::memory_order_relaxed), 1) + << "Element (" << i << ", " << j << ", " << k << ", " << l << ", " << m << ", " << n << ") was processed " + << counters[linear_idx].load(std::memory_order_relaxed) << " times (expected: 1)"; + } + } + } + } + } + } +} + +TEST(Parallelize6DTile1D, MultiThreadPoolEachItemProcessedOnce) { + std::vector<std::atomic_int> counters(kParallelize6DTile1DRangeI * kParallelize6DTile1DRangeJ * kParallelize6DTile1DRangeK * kParallelize6DTile1DRangeL * kParallelize6DTile1DRangeM * kParallelize6DTile1DRangeN); + + auto_pthreadpool_t threadpool(pthreadpool_create(0), pthreadpool_destroy); + ASSERT_TRUE(threadpool.get()); + + if (pthreadpool_get_threads_count(threadpool.get()) <= 1) { + GTEST_SKIP(); + } + + pthreadpool_parallelize_6d_tile_1d( + threadpool.get(), + reinterpret_cast<pthreadpool_task_6d_tile_1d_t>(Increment6DTile1D), + static_cast<void*>(counters.data()), + kParallelize6DTile1DRangeI, kParallelize6DTile1DRangeJ, kParallelize6DTile1DRangeK, kParallelize6DTile1DRangeL, kParallelize6DTile1DRangeM, kParallelize6DTile1DRangeN, + kParallelize6DTile1DTileN, + 0 /* flags */); + + for (size_t i = 0; i < kParallelize6DTile1DRangeI; i++) { + for (size_t j = 0; j < kParallelize6DTile1DRangeJ; j++) { + for (size_t k = 0; k < kParallelize6DTile1DRangeK; k++) { + for (size_t l = 0; l < kParallelize6DTile1DRangeL; l++) { + for (size_t m = 0; m < kParallelize6DTile1DRangeM; m++) { + for (size_t n = 0; n < kParallelize6DTile1DRangeN; n++) { + const size_t linear_idx = ((((i * kParallelize6DTile1DRangeJ + j) * kParallelize6DTile1DRangeK + k) * kParallelize6DTile1DRangeL + l) * kParallelize6DTile1DRangeM + m) * kParallelize6DTile1DRangeN + n; + EXPECT_EQ(counters[linear_idx].load(std::memory_order_relaxed), 1) + << "Element (" << i << ", " << j << ", " << k << ", " << l << ", " << m << ", " << n << ") was processed " + << counters[linear_idx].load(std::memory_order_relaxed) << " times (expected: 1)"; + } + } + } + } + } + } +} + +TEST(Parallelize6DTile1D, SingleThreadPoolEachItemProcessedMultipleTimes) { + std::vector<std::atomic_int> counters(kParallelize6DTile1DRangeI * kParallelize6DTile1DRangeJ * kParallelize6DTile1DRangeK * kParallelize6DTile1DRangeL * kParallelize6DTile1DRangeM * kParallelize6DTile1DRangeN); + + auto_pthreadpool_t threadpool(pthreadpool_create(1), pthreadpool_destroy); + ASSERT_TRUE(threadpool.get()); + + for (size_t iteration = 0; iteration < kIncrementIterations6D; iteration++) { + pthreadpool_parallelize_6d_tile_1d( + threadpool.get(), + reinterpret_cast<pthreadpool_task_6d_tile_1d_t>(Increment6DTile1D), + static_cast<void*>(counters.data()), + kParallelize6DTile1DRangeI, kParallelize6DTile1DRangeJ, kParallelize6DTile1DRangeK, kParallelize6DTile1DRangeL, kParallelize6DTile1DRangeM, kParallelize6DTile1DRangeN, + kParallelize6DTile1DTileN, + 0 /* flags */); + } + + for (size_t i = 0; i < kParallelize6DTile1DRangeI; i++) { + for (size_t j = 0; j < kParallelize6DTile1DRangeJ; j++) { + for (size_t k = 0; k < kParallelize6DTile1DRangeK; k++) { + for (size_t l = 0; l < kParallelize6DTile1DRangeL; l++) { + for (size_t m = 0; m < kParallelize6DTile1DRangeM; m++) { + for (size_t n = 0; n < kParallelize6DTile1DRangeN; n++) { + const size_t linear_idx = ((((i * kParallelize6DTile1DRangeJ + j) * kParallelize6DTile1DRangeK + k) * kParallelize6DTile1DRangeL + l) * kParallelize6DTile1DRangeM + m) * kParallelize6DTile1DRangeN + n; + EXPECT_EQ(counters[linear_idx].load(std::memory_order_relaxed), kIncrementIterations6D) + << "Element (" << i << ", " << j << ", " << k << ", " << l << ", " << m << ", " << n << ") was processed " + << counters[linear_idx].load(std::memory_order_relaxed) << " times " + << "(expected: " << kIncrementIterations6D << ")"; + } + } + } + } + } + } +} + +TEST(Parallelize6DTile1D, MultiThreadPoolEachItemProcessedMultipleTimes) { + std::vector<std::atomic_int> counters(kParallelize6DTile1DRangeI * kParallelize6DTile1DRangeJ * kParallelize6DTile1DRangeK * kParallelize6DTile1DRangeL * kParallelize6DTile1DRangeM * kParallelize6DTile1DRangeN); + + auto_pthreadpool_t threadpool(pthreadpool_create(0), pthreadpool_destroy); + ASSERT_TRUE(threadpool.get()); + + if (pthreadpool_get_threads_count(threadpool.get()) <= 1) { + GTEST_SKIP(); + } + + for (size_t iteration = 0; iteration < kIncrementIterations6D; iteration++) { + pthreadpool_parallelize_6d_tile_1d( + threadpool.get(), + reinterpret_cast<pthreadpool_task_6d_tile_1d_t>(Increment6DTile1D), + static_cast<void*>(counters.data()), + kParallelize6DTile1DRangeI, kParallelize6DTile1DRangeJ, kParallelize6DTile1DRangeK, kParallelize6DTile1DRangeL, kParallelize6DTile1DRangeM, kParallelize6DTile1DRangeN, + kParallelize6DTile1DTileN, + 0 /* flags */); + } + + for (size_t i = 0; i < kParallelize6DTile1DRangeI; i++) { + for (size_t j = 0; j < kParallelize6DTile1DRangeJ; j++) { + for (size_t k = 0; k < kParallelize6DTile1DRangeK; k++) { + for (size_t l = 0; l < kParallelize6DTile1DRangeL; l++) { + for (size_t m = 0; m < kParallelize6DTile1DRangeM; m++) { + for (size_t n = 0; n < kParallelize6DTile1DRangeN; n++) { + const size_t linear_idx = ((((i * kParallelize6DTile1DRangeJ + j) * kParallelize6DTile1DRangeK + k) * kParallelize6DTile1DRangeL + l) * kParallelize6DTile1DRangeM + m) * kParallelize6DTile1DRangeN + n; + EXPECT_EQ(counters[linear_idx].load(std::memory_order_relaxed), kIncrementIterations6D) + << "Element (" << i << ", " << j << ", " << k << ", " << l << ", " << m << ", " << n << ") was processed " + << counters[linear_idx].load(std::memory_order_relaxed) << " times " + << "(expected: " << kIncrementIterations6D << ")"; + } + } + } + } + } + } +} + +static void IncrementSame6DTile1D(std::atomic_int* num_processed_items, size_t i, size_t j, size_t k, size_t l, size_t m, size_t start_n, size_t tile_n) { + for (size_t n = start_n; n < start_n + tile_n; n++) { + num_processed_items->fetch_add(1, std::memory_order_relaxed); + } +} + +TEST(Parallelize6DTile1D, MultiThreadPoolHighContention) { + std::atomic_int num_processed_items = ATOMIC_VAR_INIT(0); + + auto_pthreadpool_t threadpool(pthreadpool_create(0), pthreadpool_destroy); + ASSERT_TRUE(threadpool.get()); + + if (pthreadpool_get_threads_count(threadpool.get()) <= 1) { + GTEST_SKIP(); + } + + pthreadpool_parallelize_6d_tile_1d( + threadpool.get(), + reinterpret_cast<pthreadpool_task_6d_tile_1d_t>(IncrementSame6DTile1D), + static_cast<void*>(&num_processed_items), + kParallelize6DTile1DRangeI, kParallelize6DTile1DRangeJ, kParallelize6DTile1DRangeK, kParallelize6DTile1DRangeL, kParallelize6DTile1DRangeM, kParallelize6DTile1DRangeN, + kParallelize6DTile1DTileN, + 0 /* flags */); + EXPECT_EQ(num_processed_items.load(std::memory_order_relaxed), kParallelize6DTile1DRangeI * kParallelize6DTile1DRangeJ * kParallelize6DTile1DRangeK * kParallelize6DTile1DRangeL * kParallelize6DTile1DRangeM * kParallelize6DTile1DRangeN); +} + +static void WorkImbalance6DTile1D(std::atomic_int* num_processed_items, size_t i, size_t j, size_t k, size_t l, size_t m, size_t start_n, size_t tile_n) { + num_processed_items->fetch_add(tile_n, std::memory_order_relaxed); + if (i == 0 && j == 0 && k == 0 && l == 0 && m == 0 && start_n == 0) { + /* Spin-wait until all items are computed */ + while (num_processed_items->load(std::memory_order_relaxed) != kParallelize6DTile1DRangeI * kParallelize6DTile1DRangeJ * kParallelize6DTile1DRangeK * kParallelize6DTile1DRangeL * kParallelize6DTile1DRangeM * kParallelize6DTile1DRangeN) { + std::atomic_thread_fence(std::memory_order_acquire); + } + } +} + +TEST(Parallelize6DTile1D, MultiThreadPoolWorkStealing) { + std::atomic_int num_processed_items = ATOMIC_VAR_INIT(0); + + auto_pthreadpool_t threadpool(pthreadpool_create(0), pthreadpool_destroy); + ASSERT_TRUE(threadpool.get()); + + if (pthreadpool_get_threads_count(threadpool.get()) <= 1) { + GTEST_SKIP(); + } + + pthreadpool_parallelize_6d_tile_1d( + threadpool.get(), + reinterpret_cast<pthreadpool_task_6d_tile_1d_t>(WorkImbalance6DTile1D), + static_cast<void*>(&num_processed_items), + kParallelize6DTile1DRangeI, kParallelize6DTile1DRangeJ, kParallelize6DTile1DRangeK, kParallelize6DTile1DRangeL, kParallelize6DTile1DRangeM, kParallelize6DTile1DRangeN, + kParallelize6DTile1DTileN, + 0 /* flags */); + EXPECT_EQ(num_processed_items.load(std::memory_order_relaxed), kParallelize6DTile1DRangeI * kParallelize6DTile1DRangeJ * kParallelize6DTile1DRangeK * kParallelize6DTile1DRangeL * kParallelize6DTile1DRangeM * kParallelize6DTile1DRangeN); +} + static void ComputeNothing6DTile2D(void*, size_t, size_t, size_t, size_t, size_t, size_t, size_t, size_t) { } |