Parallelize task 1D with thread id support
diff --git a/include/pthreadpool.h b/include/pthreadpool.h
index 2e20b66..993204a 100644
--- a/include/pthreadpool.h
+++ b/include/pthreadpool.h
@@ -7,6 +7,7 @@
typedef struct pthreadpool* pthreadpool_t;
typedef void (*pthreadpool_task_1d_t)(void*, size_t);
+typedef void (*pthreadpool_task_1d_with_thread_t)(void*, size_t, size_t);
typedef void (*pthreadpool_task_1d_tile_1d_t)(void*, size_t, size_t);
typedef void (*pthreadpool_task_2d_t)(void*, size_t, size_t);
typedef void (*pthreadpool_task_2d_tile_1d_t)(void*, size_t, size_t, size_t);
@@ -122,6 +123,36 @@
uint32_t flags);
/**
+ * Process items on a 1D grid passing along the current thread id.
+ *
+ * The function implements a parallel version of the following snippet:
+ *
+ * for (size_t i = 0; i < range; i++)
+ * function(context, thread_index, i);
+ *
+ * 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 item.
+ * @param context the first argument passed to the specified function.
+ * @param range the number of items on the 1D grid to process. The
+ * specified function will be called once for each item.
+ * @param flags a bitwise combination of zero or more optional flags
+ * (PTHREADPOOL_FLAG_DISABLE_DENORMALS or PTHREADPOOL_FLAG_YIELD_WORKERS)
+ */
+void pthreadpool_parallelize_1d_with_thread(
+ pthreadpool_t threadpool,
+ pthreadpool_task_1d_with_thread_t function,
+ void* context,
+ size_t range,
+ uint32_t flags);
+
+/**
* Process items on a 1D grid using a microarchitecture-aware task function.
*
* The function implements a parallel version of the following snippet:
diff --git a/src/fastpath.c b/src/fastpath.c
index 0ccda96..e698af8 100644
--- a/src/fastpath.c
+++ b/src/fastpath.c
@@ -58,6 +58,42 @@
pthreadpool_fence_release();
}
+PTHREADPOOL_INTERNAL void pthreadpool_thread_parallelize_1d_with_thread_fastpath(
+ struct pthreadpool* threadpool,
+ struct thread_info* thread)
+{
+ assert(threadpool != NULL);
+ assert(thread != NULL);
+
+ const pthreadpool_task_1d_with_thread_t task = (pthreadpool_task_1d_with_thread_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 thread_number = thread->thread_number;
+ size_t range_start = pthreadpool_load_relaxed_size_t(&thread->range_start);
+ while (pthreadpool_decrement_fetch_relaxed_size_t(&thread->range_length) < range_threshold) {
+ task(argument, thread_number, range_start++);
+ }
+
+ /* There still may be other threads with work */
+ 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 index = pthreadpool_decrement_fetch_relaxed_size_t(&other_thread->range_end);
+ task(argument, thread_number, index);
+ }
+ }
+
+ /* Make changes by this thread visible to other threads */
+ pthreadpool_fence_release();
+}
+
PTHREADPOOL_INTERNAL void pthreadpool_thread_parallelize_1d_with_uarch_fastpath(
struct pthreadpool* threadpool,
struct thread_info* thread)
diff --git a/src/portable-api.c b/src/portable-api.c
index 4cb0cd9..3b905da 100644
--- a/src/portable-api.c
+++ b/src/portable-api.c
@@ -60,6 +60,37 @@
pthreadpool_fence_release();
}
+static void thread_parallelize_1d_with_thread(struct pthreadpool* threadpool, struct thread_info* thread) {
+ assert(threadpool != NULL);
+ assert(thread != NULL);
+
+ const pthreadpool_task_1d_with_thread_t task = (pthreadpool_task_1d_with_thread_t) pthreadpool_load_relaxed_void_p(&threadpool->task);
+ void *const argument = pthreadpool_load_relaxed_void_p(&threadpool->argument);
+
+ const size_t thread_number = thread->thread_number;
+ /* Process thread's own range of items */
+ size_t range_start = pthreadpool_load_relaxed_size_t(&thread->range_start);
+ while (pthreadpool_try_decrement_relaxed_size_t(&thread->range_length)) {
+ task(argument, thread_number, range_start++);
+ }
+
+ /* There still may be other threads with work */
+ 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 index = pthreadpool_decrement_fetch_relaxed_size_t(&other_thread->range_end);
+ task(argument, thread_number, index);
+ }
+ }
+
+ /* Make changes by this thread visible to other threads */
+ pthreadpool_fence_release();
+}
+
static void thread_parallelize_1d_with_uarch(struct pthreadpool* threadpool, struct thread_info* thread) {
assert(threadpool != NULL);
assert(thread != NULL);
@@ -1547,6 +1578,41 @@
}
}
+void pthreadpool_parallelize_1d_with_thread(
+ struct pthreadpool* threadpool,
+ pthreadpool_task_1d_with_thread_t task,
+ void* argument,
+ size_t range,
+ uint32_t flags)
+{
+ size_t threads_count;
+ if (threadpool == NULL || (threads_count = threadpool->threads_count.value) <= 1 || range <= 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++) {
+ task(argument, 0, i);
+ }
+ if (flags & PTHREADPOOL_FLAG_DISABLE_DENORMALS) {
+ set_fpu_state(saved_fpu_state);
+ }
+ } else {
+ thread_function_t parallelize_1d_with_thread = &thread_parallelize_1d_with_thread;
+ #if PTHREADPOOL_USE_FASTPATH
+ const size_t range_threshold = -threads_count;
+ if (range < range_threshold) {
+ parallelize_1d_with_thread = &pthreadpool_thread_parallelize_1d_with_thread_fastpath;
+ }
+ #endif
+ pthreadpool_parallelize(
+ threadpool, parallelize_1d_with_thread, NULL, 0,
+ (void*) task, argument, range, flags);
+ }
+}
+
void pthreadpool_parallelize_1d_with_uarch(
pthreadpool_t threadpool,
pthreadpool_task_1d_with_id_t task,
diff --git a/src/shim.c b/src/shim.c
index 6a7c8f6..f0b2d0c 100644
--- a/src/shim.c
+++ b/src/shim.c
@@ -38,6 +38,18 @@
}
}
+void pthreadpool_parallelize_1d_with_thread(
+ struct pthreadpool* threadpool,
+ pthreadpool_task_1d_with_thread_t task,
+ void* argument,
+ size_t range,
+ uint32_t flags)
+{
+ for (size_t i = 0; i < range; i++) {
+ task(argument, 0, i);
+ }
+}
+
void pthreadpool_parallelize_1d_with_uarch(
pthreadpool_t threadpool,
pthreadpool_task_1d_with_id_t task,
diff --git a/src/threadpool-object.h b/src/threadpool-object.h
index 93e5619..2ef12f5 100644
--- a/src/threadpool-object.h
+++ b/src/threadpool-object.h
@@ -786,6 +786,10 @@
struct pthreadpool* threadpool,
struct thread_info* thread);
+PTHREADPOOL_INTERNAL void pthreadpool_thread_parallelize_1d_with_thread_fastpath(
+ struct pthreadpool* threadpool,
+ struct thread_info* thread);
+
PTHREADPOOL_INTERNAL void pthreadpool_thread_parallelize_1d_with_uarch_fastpath(
struct pthreadpool* threadpool,
struct thread_info* thread);
diff --git a/test/pthreadpool.cc b/test/pthreadpool.cc
index 5cd31a6..5806eaa 100644
--- a/test/pthreadpool.cc
+++ b/test/pthreadpool.cc
@@ -369,6 +369,281 @@
EXPECT_EQ(num_processed_items.load(std::memory_order_relaxed), kParallelize1DRange);
}
+static void ComputeNothing1DWithThread(void*, size_t, size_t) {
+}
+
+TEST(Parallelize1DWithThread, SingleThreadPoolCompletes) {
+ auto_pthreadpool_t threadpool(pthreadpool_create(1), pthreadpool_destroy);
+ ASSERT_TRUE(threadpool.get());
+
+ pthreadpool_parallelize_1d_with_thread(threadpool.get(),
+ ComputeNothing1DWithThread,
+ nullptr,
+ kParallelize1DRange,
+ 0 /* flags */);
+}
+
+TEST(Parallelize1DWithThread, 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_1d_with_thread(
+ threadpool.get(),
+ ComputeNothing1DWithThread,
+ nullptr,
+ kParallelize1DRange,
+ 0 /* flags */);
+}
+
+static void CheckBounds1DWithThread(void*, size_t, size_t i) {
+ EXPECT_LT(i, kParallelize1DRange);
+}
+
+TEST(Parallelize1DWithThread, SingleThreadPoolAllItemsInBounds) {
+ auto_pthreadpool_t threadpool(pthreadpool_create(1), pthreadpool_destroy);
+ ASSERT_TRUE(threadpool.get());
+
+ pthreadpool_parallelize_1d_with_thread(
+ threadpool.get(),
+ CheckBounds1DWithThread,
+ nullptr,
+ kParallelize1DRange,
+ 0 /* flags */);
+}
+
+TEST(Parallelize1DWithThread, 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_1d_with_thread(
+ threadpool.get(),
+ CheckBounds1DWithThread,
+ nullptr,
+ kParallelize1DRange,
+ 0 /* flags */);
+}
+
+static void SetTrue1DWithThread(std::atomic_bool* processed_indicators, size_t, size_t i) {
+ processed_indicators[i].store(true, std::memory_order_relaxed);
+}
+
+TEST(Parallelize1DWithThread, SingleThreadPoolAllItemsProcessed) {
+ std::vector<std::atomic_bool> indicators(kParallelize1DRange);
+
+ auto_pthreadpool_t threadpool(pthreadpool_create(1), pthreadpool_destroy);
+ ASSERT_TRUE(threadpool.get());
+
+ pthreadpool_parallelize_1d_with_thread(
+ threadpool.get(),
+ reinterpret_cast<pthreadpool_task_1d_with_thread_t>(SetTrue1DWithThread),
+ static_cast<void*>(indicators.data()),
+ kParallelize1DRange,
+ 0 /* flags */);
+
+ for (size_t i = 0; i < kParallelize1DRange; i++) {
+ EXPECT_TRUE(indicators[i].load(std::memory_order_relaxed))
+ << "Element " << i << " not processed";
+ }
+}
+
+TEST(Parallelize1DWithThread, MultiThreadPoolAllItemsProcessed) {
+ std::vector<std::atomic_bool> indicators(kParallelize1DRange);
+
+ 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_1d_with_thread(
+ threadpool.get(),
+ reinterpret_cast<pthreadpool_task_1d_with_thread_t>(SetTrue1DWithThread),
+ static_cast<void*>(indicators.data()),
+ kParallelize1DRange,
+ 0 /* flags */);
+
+ for (size_t i = 0; i < kParallelize1DRange; i++) {
+ EXPECT_TRUE(indicators[i].load(std::memory_order_relaxed))
+ << "Element " << i << " not processed";
+ }
+}
+
+static void Increment1DWithThread(std::atomic_int* processed_counters, size_t, size_t i) {
+ processed_counters[i].fetch_add(1, std::memory_order_relaxed);
+}
+
+TEST(Parallelize1DWithThread, SingleThreadPoolEachItemProcessedOnce) {
+ std::vector<std::atomic_int> counters(kParallelize1DRange);
+
+ auto_pthreadpool_t threadpool(pthreadpool_create(1), pthreadpool_destroy);
+ ASSERT_TRUE(threadpool.get());
+
+ pthreadpool_parallelize_1d_with_thread(
+ threadpool.get(),
+ reinterpret_cast<pthreadpool_task_1d_with_thread_t>(Increment1DWithThread),
+ static_cast<void*>(counters.data()),
+ kParallelize1DRange,
+ 0 /* flags */);
+
+ for (size_t i = 0; i < kParallelize1DRange; i++) {
+ EXPECT_EQ(counters[i].load(std::memory_order_relaxed), 1)
+ << "Element " << i << " was processed " << counters[i].load(std::memory_order_relaxed) << " times (expected: 1)";
+ }
+}
+
+TEST(Parallelize1DWithThread, MultiThreadPoolEachItemProcessedOnce) {
+ std::vector<std::atomic_int> counters(kParallelize1DRange);
+
+ 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_1d_with_thread(
+ threadpool.get(),
+ reinterpret_cast<pthreadpool_task_1d_with_thread_t>(Increment1DWithThread),
+ static_cast<void*>(counters.data()),
+ kParallelize1DRange,
+ 0 /* flags */);
+
+ for (size_t i = 0; i < kParallelize1DRange; i++) {
+ EXPECT_EQ(counters[i].load(std::memory_order_relaxed), 1)
+ << "Element " << i << " was processed " << counters[i].load(std::memory_order_relaxed) << " times (expected: 1)";
+ }
+}
+
+TEST(Parallelize1DWithThread, SingleThreadPoolEachItemProcessedMultipleTimes) {
+ std::vector<std::atomic_int> counters(kParallelize1DRange);
+
+ auto_pthreadpool_t threadpool(pthreadpool_create(1), pthreadpool_destroy);
+ ASSERT_TRUE(threadpool.get());
+
+ for (size_t iteration = 0; iteration < kIncrementIterations; iteration++) {
+ pthreadpool_parallelize_1d_with_thread(
+ threadpool.get(),
+ reinterpret_cast<pthreadpool_task_1d_with_thread_t>(Increment1DWithThread),
+ static_cast<void*>(counters.data()),
+ kParallelize1DRange,
+ 0 /* flags */);
+ }
+
+ for (size_t i = 0; i < kParallelize1DRange; i++) {
+ EXPECT_EQ(counters[i].load(std::memory_order_relaxed), kIncrementIterations)
+ << "Element " << i << " was processed " << counters[i].load(std::memory_order_relaxed) << " times "
+ << "(expected: " << kIncrementIterations << ")";
+ }
+}
+
+TEST(Parallelize1DWithThread, MultiThreadPoolEachItemProcessedMultipleTimes) {
+ std::vector<std::atomic_int> counters(kParallelize1DRange);
+
+ 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 < kIncrementIterations; iteration++) {
+ pthreadpool_parallelize_1d_with_thread(
+ threadpool.get(),
+ reinterpret_cast<pthreadpool_task_1d_with_thread_t>(Increment1DWithThread),
+ static_cast<void*>(counters.data()),
+ kParallelize1DRange,
+ 0 /* flags */);
+ }
+
+ for (size_t i = 0; i < kParallelize1DRange; i++) {
+ EXPECT_EQ(counters[i].load(std::memory_order_relaxed), kIncrementIterations)
+ << "Element " << i << " was processed " << counters[i].load(std::memory_order_relaxed) << " times "
+ << "(expected: " << kIncrementIterations << ")";
+ }
+}
+
+static void IncrementSame1DWithThread(std::atomic_int* num_processed_items, size_t, size_t i) {
+ num_processed_items->fetch_add(1, std::memory_order_relaxed);
+}
+
+TEST(Parallelize1DWithThread, 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_1d_with_thread(
+ threadpool.get(),
+ reinterpret_cast<pthreadpool_task_1d_with_thread_t>(IncrementSame1DWithThread),
+ static_cast<void*>(&num_processed_items),
+ kParallelize1DRange,
+ 0 /* flags */);
+ EXPECT_EQ(num_processed_items.load(std::memory_order_relaxed), kParallelize1DRange);
+}
+
+static void WorkImbalance1DWithThread(std::atomic_int* num_processed_items, size_t, size_t i) {
+ num_processed_items->fetch_add(1, std::memory_order_relaxed);
+ if (i == 0) {
+ /* Spin-wait until all items are computed */
+ while (num_processed_items->load(std::memory_order_relaxed) != kParallelize1DRange) {
+ std::atomic_thread_fence(std::memory_order_acquire);
+ }
+ }
+}
+
+TEST(Parallelize1DWithThread, 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_1d_with_thread(
+ threadpool.get(),
+ reinterpret_cast<pthreadpool_task_1d_with_thread_t>(WorkImbalance1DWithThread),
+ static_cast<void*>(&num_processed_items),
+ kParallelize1DRange,
+ 0 /* flags */);
+ EXPECT_EQ(num_processed_items.load(std::memory_order_relaxed), kParallelize1DRange);
+}
+
+static void CheckThreadIndexValid1DWithThread(const size_t* num_threads, size_t thread_index, size_t) {
+ EXPECT_LE(thread_index, *num_threads);
+}
+
+TEST(Parallelize1DWithThread, MultiThreadPoolThreadIndexValid) {
+ auto_pthreadpool_t threadpool(pthreadpool_create(0), pthreadpool_destroy);
+ ASSERT_TRUE(threadpool.get());
+
+ size_t num_threads = pthreadpool_get_threads_count(threadpool.get());
+ if (num_threads <= 1) {
+ GTEST_SKIP();
+ }
+
+ pthreadpool_parallelize_1d_with_thread(
+ threadpool.get(),
+ reinterpret_cast<pthreadpool_task_1d_with_thread_t>(CheckThreadIndexValid1DWithThread),
+ static_cast<void*>(&num_threads),
+ kParallelize1DRange,
+ 0 /* flags */);
+}
+
static void ComputeNothing1DWithUArch(void*, uint32_t, size_t) {
}
