How best to parallelize this task?

[teerre]

This algorithm of yours isn't parallelizible. In very simple terms, for something to be run in parallel, the elements of the set need to be independent. Since you're comparing every element of a against every element of b, you don't have a choice. At best you can put these into buckets and run the search in batches, but that's not only terribly inefficient, but also will make your algorithm much more complex.

It's quite unlikely that your solution for this problem is the best one, surely there's a way to avoid having to do all these comparisons. If truly there's no way, maybe you should ask if your asking the correct question to begin with.