hpx icon indicating copy to clipboard operation
hpx copied to clipboard

Published 20 hours ago • verified publisher icon STEllAR-GROUP

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

Open hkaiser opened this issue 10 years ago • 10 comments

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:

  • [x] adjacent_difference (see #2859, #3525)
  • [x] adjacent_find (see #2859, #3525)
  • [x] all_of any_of none_of (see #2859, #3525)
  • [x] copy (see #1346) copy_n
  • [ ] copy_if
  • [x] move (see #2010)
  • [x] count count_if (see #1340)
  • [ ] equal mismatch
  • [x] exclusive_scan inclusive_scan (see #2287)
  • [x] reduce transform (see #2725)
  • [x] fill (#2202)
  • [ ] fill_n
  • [x] find find_if find_if_not (see #2792)
  • [ ] find_end find_first_of (see #2793)
  • [x] for_each
  • [x] for_each_n (see #2725)
  • [x] generate (see #1968)
  • [ ] generate_n
  • [ ] inner_product inplace_merge merge
  • [ ] is_heap is_heap_until
  • [ ] is_partitioned is_sorted is_sorted_until
  • [ ] lexicographical_compare
  • [x] max_element min_element minmax_element (#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:

  • [x] transform_reduce (see #1333, #2859, #3525)
  • [x] transform_exclusive_scan transform_inclusive_scan (see #2725)

hkaiser avatar Dec 25 '14 20:12 hkaiser

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

taeguk avatar Mar 28 '17 01:03 taeguk

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

hkaiser avatar Mar 28 '17 02:03 hkaiser

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

taeguk avatar Mar 28 '17 05:03 taeguk

@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.

hkaiser avatar Mar 28 '17 11:03 hkaiser

@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.

mcopik avatar Mar 31 '17 19:03 mcopik

@mcopik Thanks, I fixed the list above.

hkaiser avatar Mar 31 '17 20:03 hkaiser

Actually, copy_n already seems to work: https://github.com/brjsp/hpx/commit/694c72515f06dcc303468511d53ec0ae6825f5d0

brjsp avatar Apr 02 '18 19:04 brjsp

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

tapaswenipathak avatar Sep 04 '19 11:09 tapaswenipathak

@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.

hkaiser avatar Sep 04 '19 12:09 hkaiser

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

tapaswenipathak avatar Sep 04 '19 12:09 tapaswenipathak