This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH][libstdc++-v3 parallel mode] Better scalability for parallel partition
- From: Johannes Singler <singler at kit dot edu>
- To: libstdc++ <libstdc++ at gcc dot gnu dot org>, gcc-patches at gcc dot gnu dot org
- Date: Wed, 21 Apr 2010 11:30:38 +0200
- Subject: [PATCH][libstdc++-v3 parallel mode] Better scalability for parallel partition
This patch improves scalability for the parallel partitioning algorithm.
Although the acceleration is only about 25%, this means that speedup
goes up from 4 to 5 on eight cores.
I consider the code also more elegant now.
before:
## partition int
# seq 1 2 3 4
5 6 7 8
10000000 0.051112 0.053733 0.030644 0.020897 0.016176
0.013590 0.012479 0.012280 0.012888
after:
10000000 0.051556 0.052810 0.029154 0.020030 0.015668
0.012935 0.011506 0.011265 0.010248
Tested x86_64-unknown-linux-gnu, gcc-4_5-branch: No regressions except
that profile mode and parallel mode do not cooperate.
Please approve for mainline and gcc-4_5-branch.
2010-04-21 Johannes Singler <singler@kit.edu>
* include/parallel/partition.h (__parallel_partition):
Improve performance by:
-introducing new variables __leftold, __rightold, __dist, thus
-getting rid of omp lock by using atomic operations
-getting rid of two omp barriers
Johannes
Index: include/parallel/partition.h
===================================================================
--- include/parallel/partition.h (revision 158518)
+++ include/parallel/partition.h (working copy)
@@ -66,27 +66,26 @@
const _Settings& __s = _Settings::get();
- // Shared.
- _GLIBCXX_VOLATILE _DifferenceType __left = 0, __right = __n - 1;
- _GLIBCXX_VOLATILE _DifferenceType __leftover_left, __leftover_right;
- _GLIBCXX_VOLATILE _DifferenceType __leftnew, __rightnew;
+ // shared
+ _GLIBCXX_VOLATILE _DifferenceType __left = 0, __right = __n - 1,
+ __dist = __n,
+ __leftover_left, __leftover_right,
+ __leftnew, __rightnew;
- bool* __reserved_left = NULL, * __reserved_right = NULL;
+ // just 0 or 1, but int to allow atomic operations
+ int* __reserved_left = NULL, * __reserved_right = NULL;
_DifferenceType __chunk_size = __s.partition_chunk_size;
- omp_lock_t __result_lock;
- omp_init_lock(&__result_lock);
-
//at least two chunks per thread
- if (__right - __left + 1 >= 2 * __num_threads * __chunk_size)
+ if (__dist >= 2 * __num_threads * __chunk_size)
# pragma omp parallel num_threads(__num_threads)
{
# pragma omp single
{
__num_threads = omp_get_num_threads();
- __reserved_left = new bool[__num_threads];
- __reserved_right = new bool[__num_threads];
+ __reserved_left = new int[__num_threads];
+ __reserved_right = new int[__num_threads];
if (__s.partition_chunk_share > 0.0)
__chunk_size = std::max<_DifferenceType>
@@ -96,17 +95,16 @@
__chunk_size = __s.partition_chunk_size;
}
- while (__right - __left + 1 >= 2 * __num_threads * __chunk_size)
+ while (__dist >= 2 * __num_threads * __chunk_size)
{
# pragma omp single
{
- _DifferenceType __num_chunks = ((__right - __left + 1)
- / __chunk_size);
+ _DifferenceType __num_chunks = __dist / __chunk_size;
for (_ThreadIndex __r = 0; __r < __num_threads; ++__r)
{
- __reserved_left[__r] = false;
- __reserved_right[__r] = false;
+ __reserved_left [__r] = 0; // false
+ __reserved_right[__r] = 0; // false
}
__leftover_left = 0;
__leftover_right = 0;
@@ -115,11 +113,13 @@
// Private.
_DifferenceType __thread_left, __thread_left_border,
__thread_right, __thread_right_border;
- __thread_left = __left + 1;
+ __thread_left = __left + 1;
// Just to satisfy the condition below.
__thread_left_border = __thread_left - 1;
+
__thread_right = __n - 1;
+ // Just to satisfy the condition below.
__thread_right_border = __thread_right + 1;
bool __iam_finished = false;
@@ -127,35 +127,42 @@
{
if (__thread_left > __thread_left_border)
{
- omp_set_lock(&__result_lock);
- if (__left + (__chunk_size - 1) > __right)
- __iam_finished = true;
- else
- {
- __thread_left = __left;
- __thread_left_border = __left + (__chunk_size - 1);
- __left += __chunk_size;
- }
- omp_unset_lock(&__result_lock);
+ _DifferenceType __former_dist =
+ __fetch_and_add(&__dist, -__chunk_size);
+ if (__former_dist < __chunk_size)
+ {
+ __fetch_and_add(&__dist, __chunk_size);
+ __iam_finished = true;
+ break;
+ }
+ else
+ {
+ __thread_left =
+ __fetch_and_add(&__left, __chunk_size);
+ __thread_left_border =
+ __thread_left + (__chunk_size - 1);
+ }
}
if (__thread_right < __thread_right_border)
{
- omp_set_lock(&__result_lock);
- if (__left > __right - (__chunk_size - 1))
- __iam_finished = true;
- else
- {
- __thread_right = __right;
- __thread_right_border = __right - (__chunk_size - 1);
- __right -= __chunk_size;
- }
- omp_unset_lock(&__result_lock);
+ _DifferenceType __former_dist =
+ __fetch_and_add(&__dist, -__chunk_size);
+ if (__former_dist < __chunk_size)
+ {
+ __fetch_and_add(&__dist, __chunk_size);
+ __iam_finished = true;
+ break;
+ }
+ else
+ {
+ __thread_right =
+ __fetch_and_add(&__right, -__chunk_size);
+ __thread_right_border =
+ __thread_right - (__chunk_size - 1);
+ }
}
- if (__iam_finished)
- break;
-
// Swap as usual.
while (__thread_left < __thread_right)
{
@@ -188,21 +195,19 @@
# pragma omp barrier
-# pragma omp single
- {
- __leftnew = __left - __leftover_left * __chunk_size;
- __rightnew = __right + __leftover_right * __chunk_size;
- }
+ _DifferenceType
+ __leftold = __left,
+ __leftnew = __left - __leftover_left * __chunk_size,
+ __rightold = __right,
+ __rightnew = __right + __leftover_right * __chunk_size;
-# pragma omp barrier
-
// <=> __thread_left_border + (__chunk_size - 1) >= __leftnew
if (__thread_left <= __thread_left_border
&& __thread_left_border >= __leftnew)
{
// Chunk already in place, reserve spot.
__reserved_left[(__left - (__thread_left_border + 1))
- / __chunk_size] = true;
+ / __chunk_size] = 1;
}
// <=> __thread_right_border - (__chunk_size - 1) <= __rightnew
@@ -211,7 +216,7 @@
{
// Chunk already in place, reserve spot.
__reserved_right[((__thread_right_border - 1) - __right)
- / __chunk_size] = true;
+ / __chunk_size] = 1;
}
# pragma omp barrier
@@ -221,15 +226,13 @@
{
// Find spot and swap.
_DifferenceType __swapstart = -1;
- omp_set_lock(&__result_lock);
- for (_DifferenceType __r = 0; __r < __leftover_left; ++__r)
- if (!__reserved_left[__r])
- {
- __reserved_left[__r] = true;
- __swapstart = __left - (__r + 1) * __chunk_size;
- break;
- }
- omp_unset_lock(&__result_lock);
+ for (int __r = 0; __r < __leftover_left; ++__r)
+ if (__reserved_left[__r] == 0
+ && __compare_and_swap(&(__reserved_left[__r]), 0, 1))
+ {
+ __swapstart = __leftold - (__r + 1) * __chunk_size;
+ break;
+ }
#if _GLIBCXX_ASSERTIONS
_GLIBCXX_PARALLEL_ASSERT(__swapstart != -1);
@@ -246,15 +249,13 @@
{
// Find spot and swap
_DifferenceType __swapstart = -1;
- omp_set_lock(&__result_lock);
- for (_DifferenceType __r = 0; __r < __leftover_right; ++__r)
- if (!__reserved_right[__r])
- {
- __reserved_right[__r] = true;
- __swapstart = __right + __r * __chunk_size + 1;
- break;
- }
- omp_unset_lock(&__result_lock);
+ for (int __r = 0; __r < __leftover_right; ++__r)
+ if (__reserved_right[__r] == 0
+ && __compare_and_swap(&(__reserved_right[__r]), 0, 1))
+ {
+ __swapstart = __rightold + __r * __chunk_size + 1;
+ break;
+ }
#if _GLIBCXX_ASSERTIONS
_GLIBCXX_PARALLEL_ASSERT(__swapstart != -1);
@@ -270,18 +271,15 @@
# pragma omp single
{
for (_DifferenceType __r = 0; __r < __leftover_left; ++__r)
- _GLIBCXX_PARALLEL_ASSERT(__reserved_left[__r]);
+ _GLIBCXX_PARALLEL_ASSERT(__reserved_left[__r] == 1);
for (_DifferenceType __r = 0; __r < __leftover_right; ++__r)
- _GLIBCXX_PARALLEL_ASSERT(__reserved_right[__r]);
+ _GLIBCXX_PARALLEL_ASSERT(__reserved_right[__r] == 1);
}
-
-# pragma omp barrier
#endif
-# pragma omp barrier
-
__left = __leftnew;
__right = __rightnew;
+ __dist = __right - __left + 1;
}
# pragma omp flush(__left, __right)
@@ -313,8 +311,6 @@
delete[] __reserved_left;
delete[] __reserved_right;
- omp_destroy_lock(&__result_lock);
-
// Element "between" __final_left and __final_right might not have
// been regarded yet
if (__final_left < __n && !__pred(__begin[__final_left]))