Parallelism

Table of contents

1. Longest sequence
2. Multi-pass filtering

Pull the skeleton repository to get the para assignment. Commit and push your changes to GitLab before submitting your homework to Gradescope.

Note

There is no autograder for this assignment. Make sure that your implementation is correctly parallelized; it can pass the tests even if there is no parallelism.

Longest sequence

Use the fork/join framework to implement getLongestSequence. Given an int val, int[] arr, and an int sequentialCutoff, getLongestSequence returns the length of the longest consecutive sequence of val in arr.

For example, if arr is [2, 17, 17, 8, 17, 17, 17, 0, 17, 1], then getLongestSequence(17, arr) should return 3 and getLongestSequence(35, arr) should return 0.

Your code must have O(N) work, O(log N) span, where N is the length of arr, and use the sequentialCutoff argument. You may use the SequenceRange class to carry the return value.

Multi-pass filtering

Use the fork/join framework to implement filterEmpty. Given a String[] arr, filterEmpty returns an array with the lengths of the non-empty strings in arr in order.

For example, if arr is ["", "", "cse", "332", "", "hw", "", "7", "rox"], then filterEmpty(arr) should return [3, 3, 2, 1, 3].

A parallel algorithm for solving this problem in O(N) work and O(log N) span is as follows.

1. Parallel map to produce a bit set.
2. Parallel prefix over the bit set. (Implementation provided in the skeleton.)
3. Parallel map to produce the output.

Do not bother with a sequential cutoff for this exercise. Your base case may process a single element.