Implemented segmented algorithms for partitioned vector #2725

ghost · 2017-06-29T13:21:06Z

Tasks completed as part of GSoC project (See: #1338) -

Moved unit tests for segmented algorithms from component to
parallel/segmented_algorithms
Implemented segmented for_each_n using existing segmented for_each
Implemented segmented unary transform
Implemented 2 versions of segmented binary transform with 4 and 5
iterators as arguments
Implemented segmented reduce
Implemented segmented transform_inclusive/exclusive_scan by
modifying existing inclusive/exculsive_scan to accept one more
default parameter (unary operator) as input
modified dispatch.hpp in both algorithms/detail and
segmented_algorithms/detail to add helper functions for output type
inference and casting

All algorithms have associated passing tests in the unit/parallel/segmented_algorithms folder.
Inspect shows 0 errors
This branch has been updated with the almost latest hpx/master and only one test unrelated to my code fails (68 - tests.regressions.lcos_dir.wait_for_1751), which has been fixed in later commits.

Tasks completed as part of GSoC project - - Moved unit tests for segmented algorithms from component to parallel/segmented_algorithms - Implemented segmented for_each_n using existing segmented for_each along with test - Implemented segmented unary transform along with test - Implemented 2 versions of segmented binary transform with 4 and 5 iterators as parameters along with tests for both - Implemented segmented reduce along with test - Implemented segmented transform_inclusive/exclusive_scan by modifying existing inclusive/exculsive_scan to accept one more default parameter (unary operator) as input, along with tests both - modified dispatch in both algorithms/detail and segmented_algorithms/detail to add helper functions for output inference and casting See: #1338

commit 1c28b70 Author: Ajai V George <ajaivgeorgedev@gmail.com> Date: Wed Jun 21 18:50:46 2017 +0530 Updated tests for other algorithms for multiple localities commit 16a3660 Author: Ajai V George <ajaivgeorgedev@gmail.com> Date: Wed Jun 21 18:25:42 2017 +0530 Updated tests for for_each to run on multiple localities

Updated file headers with last updated date and also changed the copyright for new files

Fixed 5 Inspect errors related to missing includes

…lAR-GROUP-master

…lgorithms merge error

…lAR-GROUP-master

hkaiser · 2017-06-29T13:56:50Z

hpx/include/parallel_for_each.hpp

-#if !defined(HPX_PARALLEL_FOREACH_JUN_28_2014_0827AM)
-#define HPX_PARALLEL_FOREACH_JUN_28_2014_0827AM
+#if !defined(HPX_PARALLEL_FOREACH_JUN_21_2017_0827AM)
+#define HPX_PARALLEL_FOREACH_JUN_21_2017_0827AM



Why this change?

I think it's simply a misunderstanding between me and the student. I told him to modify include guards but I meant only files he has created.

@ajaivgeorge could you revert those changes in files which have not been created by you?

hkaiser · 2017-06-29T13:57:01Z

hpx/include/parallel_reduce.hpp

-#if !defined(HPX_PARALLEL_REDUCE_JUN_28_2014_0827AM)
-#define HPX_PARALLEL_REDUCE_JUN_28_2014_0827AM
+#if !defined(HPX_PARALLEL_REDUCE_JUN_21_2017_0827AM)
+#define HPX_PARALLEL_REDUCE_JUN_21_2017_0827AM



Why this change?

hkaiser · 2017-06-29T13:59:57Z

hpx/parallel/algorithms/detail/dispatch.hpp

@@ -18,7 +18,7 @@
 #include <hpx/parallel/executors/execution.hpp>
 #include <hpx/parallel/util/detail/algorithm_result.hpp>
 #include <hpx/parallel/util/detail/scoped_executor_parameters.hpp>
-
+#include <hpx/util/tuple.hpp>
 #include <string>


Please keep an empty line between the HPX headers and the std headers. This prevents clang-format from sorting those two groups of headers files into one block.

hkaiser · 2017-06-29T14:00:31Z

hpx/include/parallel_transform.hpp

-#if !defined(HPX_PARALLEL_TRANSFORM_JUN_28_2014_0827AM)
-#define HPX_PARALLEL_TRANSFORM_JUN_28_2014_0827AM
+#if !defined(HPX_PARALLEL_TRANSFORM_JUN_21_2017_0827AM)
+#define HPX_PARALLEL_TRANSFORM_JUN_21_2017_0827AM



There is no need to modify the include guards on every edit.

hkaiser · 2017-06-29T14:05:51Z

hpx/parallel/algorithms/for_each.hpp

+            std::true_type, Proj && proj = Proj())
+        {
+            auto last = first;
+            detail::advance(last,std::size_t(count));


Please try to conform to our code formatting style. In particular we normally place a space after commas separating arguments.

This comment applies to many spots in the code, btw. Clang-format will help with that as well (at least for the files you created).

hkaiser · 2017-06-29T14:07:07Z

hpx/parallel/algorithms/for_each.hpp

@@ -463,7 +510,7 @@ namespace hpx { namespace parallel { inline namespace v1
    >
    typename util::detail::algorithm_result<ExPolicy, InIter>::type
    for_each(ExPolicy && policy, InIter first, InIter last, F && f,
-        Proj && proj = Proj())
+        Proj && proj)


Why did you remove the default argument value?

for_each is forward declared above, so no default argument here.

Ok, I missed that. Sorry.

hkaiser · 2017-06-29T14:08:00Z

hpx/parallel/algorithms/inclusive_scan.hpp

-            T const& init, Op && op, std::true_type);
+        inclusive_scan_(ExPolicy&& policy, InIter first, InIter last, OutIter
+            dest, T const& init, Op && op, std::true_type, Conv && conv =
+            Conv());
        /// \endcond


Please try not to separate argument type and argument name onto different lines.

hkaiser · 2017-06-29T14:23:22Z

hpx/parallel/segmented_algorithms/detail/dispatch.hpp

@@ -17,6 +17,8 @@
 #include <hpx/parallel/execution_policy.hpp>
 #include <hpx/parallel/util/detail/algorithm_result.hpp>
 #include <hpx/parallel/util/detail/handle_remote_exceptions.hpp>
+#include <hpx/util/tuple.hpp>
+#include <exception>


This header is duplicated.

Updated the Iterator Types from InIter and OutIter to FwdIter Conflicts: hpx/parallel/algorithms/exclusive_scan.hpp hpx/parallel/algorithms/for_each.hpp hpx/parallel/algorithms/inclusive_scan.hpp hpx/parallel/algorithms/reduce.hpp hpx/parallel/algorithms/transform.hpp hpx/parallel/algorithms/transform_exclusive_scan.hpp hpx/parallel/algorithms/transform_inclusive_scan.hpp tests/unit/parallel/segmented_algorithms/partitioned_vector_transform_reduce.cpp

ghost · 2017-07-17T09:48:20Z

@hkaiser , @mcopik please have a look and see if this PR is ready for merging.

mcopik · 2017-07-17T10:28:16Z

@ajaivgeorge Have you fixed the issue with ctest and verified that all tests are passing on multiple localities?

ghost · 2017-07-17T10:47:31Z

@mcopik, yes (going by the CI test below). I have modified the CMakeLists file in the segmented_algorithms test folder. Please check that. I am no longer trusting the results from my laptop. Running on Rostam right now.

ghost · 2017-07-17T21:38:59Z

@mcopik, Only, transform fails on rostam. I forgot that CI wasn't running the tests. I will fix this first and then get back to find_end/first_of. Are you sure find test fails? I ran it on rostam and there was no SegFault. Find end failed as expected.

ghost · 2017-07-19T12:00:06Z

@mcopik Errors have been fixed. Please review.

hkaiser · 2017-07-21T13:44:54Z

Is this ready to be reviewed now?

ghost · 2017-07-21T15:01:21Z

@hkaiser Yes it is ready to be reviewed.

hkaiser · 2017-07-21T15:03:51Z

hpx/parallel/algorithms/exclusive_scan.hpp

-#if !defined(HPX_PARALLEL_ALGORITHM_EXCLUSIVE_SCAN_DEC_30_2014_1236PM)
-#define HPX_PARALLEL_ALGORITHM_EXCLUSIVE_SCAN_DEC_30_2014_1236PM
+#if !defined(HPX_PARALLEL_ALGORITHM_EXCLUSIVE_SCAN_JUN_21_2017_1236PM)
+#define HPX_PARALLEL_ALGORITHM_EXCLUSIVE_SCAN_JUN_21_2017_1236PM


There is no need to change the include guards.

hkaiser · 2017-07-21T15:06:02Z

hpx/parallel/algorithms/exclusive_scan.hpp

                    {
-                        T part_init = get<0>(*part_begin++);
+                        T part_init = hpx::util::invoke(conv, get<0>(*part_begin++));


This additionally requires a check whether part_begin has not reached the end after the increment.

I am not sure what the lambda should return if part_begin has reached the end. The only scenario where that happens is if there is a partition with two elements. I looked at an example from algorithms/reduce.hpp L72, and even here there is no such check.

I think it should return part_init.

I looked at an example from algorithms/reduce.hpp L72, and even here there is no such check.

There it is not a problem as part_size would drop to zero, thus avoiding to dereference the iterator produced by ++part_begin inside accumulate_n.

hkaiser · 2017-07-21T15:07:30Z

hpx/parallel/algorithms/inclusive_scan.hpp

-#if !defined(HPX_PARALLEL_ALGORITHM_INCLUSIVE_SCAN_JAN_03_2015_0136PM)
-#define HPX_PARALLEL_ALGORITHM_INCLUSIVE_SCAN_JAN_03_2015_0136PM
+#if !defined(HPX_PARALLEL_ALGORITHM_INCLUSIVE_SCAN_JUN_21_2017_0136PM)
+#define HPX_PARALLEL_ALGORITHM_INCLUSIVE_SCAN_JUN_21_2017_0136PM


There is no need to change the include guards.

hkaiser · 2017-07-21T15:08:23Z

hpx/parallel/algorithms/inclusive_scan.hpp

                    {
-                        T part_init = get<0>(*part_begin);
+                        T part_init = hpx::util::invoke(conv, get<0>(*part_begin));
                        get<1>(*part_begin++) = part_init;


This requires an additional check that part_begin has not reached the end after the increment.

hkaiser · 2017-07-21T15:10:01Z

hpx/parallel/algorithms/transform.hpp

+                (hpx::traits::is_forward_iterator<FwdIter1>::value),
+                "Requires at least forward iterator.");
+            static_assert(
+                (hpx::traits::is_input_iterator<FwdIter2>::value),


Shouldn't this check for forward_iterator_tag instead?

hkaiser · 2017-07-21T15:15:31Z

hpx/parallel/segmented_algorithms/detail/reduce.hpp

+                },
+                hpx::util::unwrapped([r](std::vector<T> && results)
+                {
+                    auto rfirst = std::begin(results);


Please use hpx::util::begin/hpx::util::end instead of the standard versions.

hkaiser · 2017-07-21T15:16:53Z

hpx/parallel/segmented_algorithms/detail/scan.hpp

@@ -637,14 +651,14 @@ namespace hpx { namespace parallel { inline namespace v1
                    hpx::dataflow(
                        policy.executor(),
                        hpx::util::unwrapped(
-                            [=, &op](T last_value, T)
+                            [=, &op, &conv](T last_value, T)


Please add an explicit return type to this lambda.

The return of segmented_scan_void function object is hpx::util::unused. Should this be the return of he lambda or should it be blank for void?

The lambda returns void.

hkaiser · 2017-07-21T15:20:13Z

hpx/parallel/segmented_algorithms/transform.hpp

+            typedef util::detail::algorithm_result<ExPolicy,
+            hpx::util::tagged_tuple<
+                tag::in1(InIter1), tag::in2(InIter2), tag::out(OutIter)>
+            > result;


Ahh, the indentation is confusing, I see this now.

hkaiser · 2017-07-21T15:20:43Z

hpx/parallel/segmented_algorithms/transform.hpp

+            typedef util::detail::algorithm_result<ExPolicy,
+            hpx::util::tagged_tuple<
+                tag::in1(InIter1), tag::in2(InIter2), tag::out(OutIter)>
+            > result;


Same here, strange indentation...

hkaiser · 2017-07-21T15:22:28Z

hpx/parallel/util/loop.hpp

+        {
+            val = hpx::util::invoke(r, val, *iter);
+            iter++;
+        };


Stray semicolon, also - why don't you use first for the iteration?

hkaiser · 2017-07-21T15:25:47Z

@ajaivgeorge Overall, very nice job - thanks for your effort!

mcopik · 2017-07-23T10:28:08Z

@ajaivgeorge I don't see any other problems besides those mentioned by Hartmut already. For the scan, it makes sense to verify if part_begin is not equal to end after an incrementation. Indentation in typedefs should be consistent and it's not, e.g. compare lines 818, 829 and 832 in transform.hpp; sometimes you use indentation for template parameters and sometimes not, sometimes the indentation is used in the last line and sometimes not.

@hkaiser can we enforce a CI build on AppVeyor? It seems it failed due to a network problem.

hkaiser · 2017-07-23T11:37:41Z

can we enforce a CI build on AppVeyor? It seems it failed due to a network problem.

AppVeyor seems to have problems to pull from repository forks... I can try rebuilding, though.

ghost · 2017-07-23T23:39:44Z

@hkaiser, @mcopik. I have improved the indentation in segmented/transform.hpp and have added the required checks to the part_begin in the scans. Do let me know if any more changes are required.

hkaiser

LGTM, thanks!

hkaiser · 2017-07-24T15:03:49Z

@mcopik: are you fine with going ahead and merging this?

mcopik · 2017-07-24T15:11:18Z

@hkaiser Yes, let's do it :)

hkaiser · 2017-07-25T15:48:03Z

@ajaivgeorge, @mcopik: two of the new tests are failing in distributed runs, see here for an example: http://rostam.cct.lsu.edu/builders/hpx_gcc_4_9_4_boost_1_56_centos_x86_64_release/builds/126/steps/run_unit_tests/logs/stdio

Could you fix those asap, please?

aserio · 2017-07-25T18:25:48Z

@ajaivgeorge, congratulations on your commit to HPX. Once you get the Buildbot issues sorted out, contact me so that we can send you a T-Shirt

ghost · 2017-07-26T05:45:50Z

@hkaiser @mcopik, The error has been fixed in my master branch. The issue was with the util/loop accumulate function that I added. During the PR review when i changed from using a temp iterator to using first iterator directly i forgot to add a ++first. Hadn't run the test after this change.

I have tested the algorithm upto localities=5. The other algorithms like transform_scan test and for_each and transform also work for localities > 2. But the following tests fail for localities > 2

handle_values
iter
fill
inclusive/exclusive_scan - I thought that this might be because of the changes I made but the transform_scan test works so I am not sure.

These might be failing because the tests are designed for localities=2 (especially the extensive tests for the scans) or because of something fundamental with the algorithm. I will look into this once I am done with the find algorithms.

hkaiser · 2017-07-26T13:28:09Z

@ajaivgeorge: please create a new PR for the algorithm fixes.

Ajai V George added 16 commits June 21, 2017 17:59

Updated file headers

49b92cc

Updated file headers with last updated date and also changed the copyright for new files

Fixed Inspect errors

2f08111

Fixed 5 Inspect errors related to missing includes

Merge branch 'master' of git://github.com/STEllAR-GROUP/hpx into STEl…

ced4b85

…lAR-GROUP-master

Merge branch 'STEllAR-GROUP-master'

183c99c

Minor fix to for_Each to fix merge error

289f19a

Minor fix to all algorithms to fix merge error

29985e0

Minor fix to transform to fix merge error

3bf5560

Minor fix to transform to fix merge error

7d25ce9

Minor fix to related to inline namespace merge error

20d0e95

Minor fix to related to with handle exception in parallel segmented a…

412b047

…lgorithms merge error

Merge branch 'master' of git://github.com/STEllAR-GROUP/hpx into STEl…

2ba4c23

…lAR-GROUP-master

Merge branch 'STEllAR-GROUP-master'

c0e46ce

Fixed Inspect errors related to missing or deprecated includes

de95410

Refixed Inspect errors related to missing includes

b296c2e

ghost changed the title ~~Implemented segmented algorithms extending existing parallel algorithms~~ Implemented segmented algorithms for partitioned vector Jun 29, 2017

hkaiser added category: algorithms category: data-structures type: enhancement labels Jun 29, 2017

hkaiser added this to the 1.1.0 milestone Jun 29, 2017

hkaiser mentioned this pull request Jun 29, 2017

Extend parallel algorithms to work with hpx::partitioned_vector et.al. #1338

Open

36 tasks

hkaiser reviewed Jun 29, 2017

View reviewed changes

Ajai V George added 2 commits July 17, 2017 09:39

Fixed merge errors

a73f70c

Errors with segmented transform and transform_scan fixed

079c201

Ajai V George added 2 commits July 19, 2017 17:30

Merge branch 'master' into master

1da3b95

Changed auto p to auto && p in segmented dispatch

566a3b1

hkaiser reviewed Jul 21, 2017

View reviewed changes

Ajai V George added 2 commits July 21, 2017 22:46

Changes according to PR review

10df23f

Merge branch 'master' into master

e1a9128

Ajai V George added 2 commits July 24, 2017 05:07

part iterator end check indentation changes

0547a23

Merge branch 'master' of github.com:ajaivgeorge/hpx

a513cde

hkaiser approved these changes Jul 24, 2017

View reviewed changes

Merge branch 'master' into master

db2111d

hkaiser merged commit 0f46913 into STEllAR-GROUP:master Jul 24, 2017

Implemented segmented algorithms for partitioned vector #2725

Implemented segmented algorithms for partitioned vector #2725

Conversation

ghost commented Jun 29, 2017

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

ghost commented Jul 17, 2017

mcopik commented Jul 17, 2017

ghost commented Jul 17, 2017 • edited by ghost

ghost commented Jul 17, 2017

ghost commented Jul 19, 2017

hkaiser commented Jul 21, 2017

ghost commented Jul 21, 2017

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

ghost Jul 21, 2017 • edited by ghost

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

hkaiser commented Jul 21, 2017

mcopik commented Jul 23, 2017

hkaiser commented Jul 23, 2017

ghost commented Jul 23, 2017

hkaiser left a comment

Choose a reason for hiding this comment

hkaiser commented Jul 24, 2017

mcopik commented Jul 24, 2017

hkaiser commented Jul 25, 2017

aserio commented Jul 25, 2017

ghost commented Jul 26, 2017 • edited by ghost

hkaiser commented Jul 26, 2017

ghost commented Jul 17, 2017 •

edited by ghost

ghost Jul 21, 2017 •

edited by ghost

ghost commented Jul 26, 2017 •

edited by ghost