GSoC 17: Final documentation for Parallel algorithms 1

By Ajai V George under the supervision of Marcin Copik

Abstract

My proposal was to implement distributed versions of STL parallel algorithms. The main focus has been on resolving as much of the pending work in  #1338 , which is about ensuring that these algorithms work seamlessly with distributed data structures like hpx::partitioned_vector. I have implemented for_each_n, unary and binary transform, reduce, transform_inclusive/ exclusive_scan, find, find_if, find_if_not, any_of, all_of, none_of, binary transform_reduce, adjacent_find, and adjacent_difference. A complex algorithm has been implemented to find sequences spanning multiple segments in a distributed data structure. This works for almost all the test cases except the corner case of searching for repeating sequences (like 123123123) across segments. The implementations of the transform scans use  the existing distributed implementation of scans. The implementation of find and its variations use a common intermediate function for handling the distribution of work among segments. Adequate test cases have been provided for all of the implemented functions.

Project Status

As part of the Project the following PRs were raised –

  1. #2725 Implementation of for_each_n, unary and binary transform, reduce, transform_inclusive_scan, and transform_exclusive_scan
  2. #2792 Implementation of find, find_if, and find_if_not
  3. #2793 Implementation of find_end and find_first_of
  4. #2859 Implementation of any_of/all_of/none_of, binary_transform_reduce, adjacent_find, adjacent_difference

PRs #2725 and #2792 have been accepted and merged. #2793 is almost complete, but some changes are required in the implementation to handle a specific case (discussed below). #2859 is under review.

Work to be done

The distributed find_end and find_first_of algorithms are not complete. The current implementation works for most of the possible cases but it fails for the specific corner case of overlapping sequence across segments. An example of this corner case is searching for  {123123123123} in {…123123|123123|123123…}, where | represents segments distributed across different process or nodes.

Also, there are many algorithms (like sort, merge) in #1338 issue which are left to be implemented. These were not part of the final GSoC proposal but I will continue working on them.

Leave a Reply

Your email address will not be published. Required fields are marked *