Parallized algorithm for getting the frequencies of numbers in an array

Question

I have an array $A$ of length $n$, containing integers between $0$ and $n-1$ inclusively. I would like to convert this to an array of frequencies $F$, that is, $F[i]$ should be the number of times $i$ appears in the array $A$. For example, $A=[1,3,1,1,0]$ would be mapped to $F=[1,3,0,1,0]$. There is an easy algorithm for this, however I would like to do this efficiently in parallel. Here is my first attempt at doing so:

Let $n = p*k$ where $p$ is the number of threads, $k$ is the number of indices each thread will process and $n$ is the total number of indices (length of A). Each thread is given a range containing $k$ indices and all threads have access to an array $F$ that will be the frequency list. $F[i]$ starts off containing $0$ but after successfully running the algorithm, will contain the frequency of index $i$ in the array $A$.

Each thread runs the following pseudo code:

for i in given range:
  F[A[i]] += 1

Assuming a mutex is used, I think this algorithm works fine, however it runs into efficiency problems because all threads may want to increase the same index of $F$ at the same time. For example, this would happen if every index of $A$ contains the same number.

I would like an algorithm which avoids this problem and is deterministic. Ideally the time complexity should be something like $O(n/p)$. This is probably not possible of course, but I would like to be able to take at least some advantage of the parallelism, even when assuming a worst case input.

Answer 1

It is common problem in parallel computing. Many parallel framework have "reduction operator" for such processing. Idea is simple.

Use separate local copies of F[A[i]] in each threads. Calculate frequency in parallel for each sub-array block in parallel. Now since each thread is updating only its local copy of frequency array F[A[i]], no mutex is required. After the completion of all threads, join all the per thread F[[A]] array's into a single application array, i.e., reduce. You will get almost O(n/p) time complexity. The actual time complexity will depend on Size of your array (larger, the better) and the number of threads (creating and joining threads takes time).

Answer 2

One option would be to sort the data and then compute offsets where runs of equal integers appear in the sorted array. Then, the frequencies are just differences in these offsets.

Computing the offsets can be done with a parallel "filter", sometimes also called "compaction" or "packing". For the sorting step, you could do a parallel radix sort. A semisort (e.g. https://people.csail.mit.edu/jshun/semisort.pdf) would work too. With the semisort, you get a total of O(n) work and polylog depth, which when scheduled onto p processors comes out to O(n/p + polylog(n)) time.

You won't be able to get down to exactly O(n/p) time, because at the very least you have to do a parallel summation, which for realistic computation models takes at least Ω(log(n)) time.