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

[hkaiser]

The existing parallel algorithms should be extended to seamlessly work with distributed data structures like hpx::partitioned_vector. Unfortunately this requires additional code for each specific algorithms.

For more information about the parallel algorithms already implemented see #1141.

Here is the list of algorithms mandated by N4310 which should be ported to the distributed case:

• adjacent_difference (see Implemented a variety of segmented algorithms #2859, Segmented algorithms #3525)
• adjacent_find (see Implemented a variety of segmented algorithms #2859, Segmented algorithms #3525)
• all_of any_of none_of (see Implemented a variety of segmented algorithms #2859, Segmented algorithms #3525)
• copy (see Segmented copy #1346) copy_n
• copy_if
• move (see Segmented move implemented for hpx::vector #2010)
• count count_if (see Adding parallel::count for distributed data structures, adding tests #1340)
• equal mismatch
• exclusive_scan inclusive_scan (see Segmented inclusive_scan and exclusive_scan implementation #2287)
• reduce transform (see Implemented segmented algorithms for partitioned vector #2725)
• fill (Added segmented fill for hpx::vector #2202)
• fill_n
• find find_if find_if_not (see Implemented segmented find and its variations for partitioned vector #2792)
• find_end find_first_of (see Implemented segmented find_end and find_first_of for partitioned vector #2793)
• for_each
• for_each_n (see Implemented segmented algorithms for partitioned vector #2725)
• generate (see More segmented algorithms #1968)
• generate_n
• inner_product inplace_merge merge
• is_heap is_heap_until
• is_partitioned is_sorted is_sorted_until
• lexicographical_compare
• max_element min_element minmax_element (More segmented algorithms #1968)
• partial_sort partial_sort_copy partition partition_copy nth_element sort stable_partition stable_sort
• remove remove_copy remove_copy_if remove_if
• replace replace_copy replace_copy_if replace_if
• reverse reverse_copy
• rotate rotate_copy
• search search_n
• set_difference set_intersection set_symmetric_difference set_union includes
• swap_ranges
• uninitialized_copy uninitialized_copy_n
• uninitialized_fill uninitialized_fill_n
• unique unique_copy

These were added by N4310:

• transform_reduce (see Distributed transform reduce #1333, Implemented a variety of segmented algorithms #2859, Segmented algorithms #3525)
• transform_exclusive_scan transform_inclusive_scan (see Implemented segmented algorithms for partitioned vector #2725)

[taeguk]

@hkaiser exclusive_scan and inclusive_scan is not checked although these are already implemented.

[hkaiser]

@taeguk right, thanks for the heads-up. Should be fine now.

[taeguk]

@hkaiser It seems that there are only two distributed data structures. (hpx::partitioned_vector and hpx::unordered_map). Is it right?

[hkaiser]

@hkaiser It seems that there are only two distributed data structures. ( hpx::partitioned_vector and hpx::unordered_map ). Is it right?

Yes. hpx::unordered_map has no iterators implemented yet, however.

[mcopik]

@hkaiser According to the issue progress tracker, transform_*_scan have been added with PR #2287 but it looks that only regular scans have been added there. I don't see transform scans in hpx/parallel/segmented_algorithms.

[hkaiser]

@mcopik Thanks, I fixed the list above.

[brjsp]

Actually, copy_n already seems to work: brjsp@694c725

[tapaswenipathak]

Hi @hkaiser: Is the task list is most recent? Can I PR or is the ticket for internal folks?

[hkaiser]

@tapaswenipathak I think the list above reflects the current state. Please feel free to work on this! Also, please don't hesitate to ask, though - this might be slightly more complex than the average 'run of the mill' ticket. The iterative, non-modifying algorithms (equal, mismatch) might be a good starting point.

[tapaswenipathak]

oh lol, ok. sure. thanks for specifying. 😄