Parallel sorting algorithm that compares all elements

Question

I'm implementing an algorithm that needs to

1. Sort elements, in parallel (this will be done on a GPU, but that doesn't matter much)
2. Compute a comparison metric for every pair of elements. This comparison metric is the identical to the one used in a sorting.

My initial plan was to use bitonic sort for step 1 but I don't think bitonic sort compares every pair of elements. Also, first doing a bitonic sort and then computing the metric for every pair of elements seems a tad inefficient because ALL the comparisons computed during the bitonic sort would be repeated in the second step.

I suppose there is a third option. I sort (taking note of computations performed) and subsequently compute any remaining comparisons, but I'm concerned about the overhead of tracking uncomputed comparisons.

Update

It appears some additional information is necessary. My elements are in fact integer n-tuples and there are elements that are neither greater or less than each other. See SO post from several moons ago. In this case a stable sorting algorithm would preserve the order of two n-tuples that are neither greater or less than each other.

Answer 1

If the comparison metric is a boolean (as indicated in the comments), then there are two possibilities.

1. The metric is transitive (if comp(A, B) yields true and comp(B, C) yields true, then comp(A, C) must also yield true). In this case, the comparison metric for any two random elements follows almost trivially from where those elements ended up in the sorted sequence. The only complication could come from elements that should be considered equal.

2. The metric is not transitive (if comp(A, B) yields true and comp(B, C) yields true, then comp(A, C) does not by definition yield true). In this case, the metric is actually unsuitable for sorting the elements, because it does not properly define a order for the elements.

Answer 2

I'm implementing an algorithm that needs to [implement sort and comprehensive set comparison in parallel]

No what you need to do is implement this in serial first then you figure out how to translate that to parallel. You don't start out the gate with an algorithm developed in parallel with out first making one that works in serial.

The reason you don't start out in parallel is for a very large list of reasons, but I'll give you some of the most important ones off the top of my head:

• You don't know if your program will actually translate in parallel unless you actually write your program in serial first

• You don't know if your program will perform better/any part that actually will perform better in parallel with out actually writing your program in serial first

• You won't be able to test your program well with out having a program that actually works in serial first

In general there are too many questions if you don't actually implement your program serially first, so do it, don't skip it and assume everything will be better in parallel, it likely wont.

(this will be done on a GPU, but that doesn't matter much)

Yes, yes it will matter a lot. CPU parallel has completely different boundaries than GPU parallel, threads are completely independent and won't serialize your program if one thread happens to hit a divergent instruction.

On the other hand, you typically will have to copy over data for CPU to share it if you are working on the same task, and ram cannot actually be access in parallel in DDRN for large cases, unlike GDDRN. And unlike GPUs you can't assume O(N) tasks that can be evenly split up are O(N/N) tasks and instead have to assume O(N/(small constant)) (which, while also not a valid assumption on GPUs, this is the kind of thinking you have to have when processing data, since it looks more like O(N/20,000)).

in short, CPU parallel operations can handle Multiple Instruction, Multiple Data (MIMD) tasks very well,

GPUs will handle Single Instruction Multiple Data (SIMD) tasks very well.

Your problem may like one architecture better than the other, or may not work/ give a speed up in one over the other (either because of context switching on CPU, or implicit serialization in GPU).

My initial plan was to use bitonic sort for step 1 but I don't think bitonic sort compares every pair of elements. Also, first doing a bitonic sort and then computing the metric for every pair of elements seems a tad inefficient because ALL the comparisons computed during the bitonic sort would be repeated in the second step.

Bitonic sort has a serial runtime complexity of O(n log^2(n)), this is the number of comparisons that must be done, in parallel, the run time is O(log^2(n)), which is the number of comparisons made for each element.

Now, you are saying you require all comparisons to be done. if your N is, lets say 256, then for each element, you will have exactly 64 comparison out of your 256 elements that are actually compared.... So no matter what, only 1/4 of your comparison can ever be made with bitonic sort, so if you went a head and did the comparisons with every element, you would at most be gaining 25% efficiency, but only on that part of your entire program (though per element comparison would be O(N) instead of O(log^2(n)) and O(N) > O(log^2(n)) by a lot).

That might seem like a lot to you but now lets move it up to 4096. Now you are doing 12^2 = 144 comparisons at for each element ... out of a total needed 4096...

You would be saving... 3% on comparisons... is that really worth saving that much? you might even have to make it slower...

But now lets look at the problem, think about it for a second... if you are going to need to do N^2 comparisons no matter what, because you need each pair wise comparison... you could even get rid of bitonic sort entirely and find the position of that item by adding up the comparisons to other items, assuming you have a deterministic tie breaking mechanism in your comparison.

EDIT: Your comparison metric is actually dominance of a set, but you also want to preserve ordering (sorting must be stable in other words), so if you are doing max sorting, you will have to take the index into account as well of each element. Because of this, you will need to change your comparison metric in a way that will not actually match dominance, as Bitonic sort is not stable

You will also likely have to include a way to encode not dominated

class DominationEnum(Enum):
    DOMINATES = 1
    DOMINATED = 0
    NODOMINATION = -1


def foo(items)
    n = len(items);
    items_sorted= [null * n]
    items_dominance= [[false for j in range(n)] for i in range(n)]
    number_better_than = 0
    for i_index, i in enumerate(items):
        for j_index, j in enumerate(items):
            domination = is_dominant(i, j)
            items_dominance[i][j] = domination == DominationEnum.DOMINATES
            number_better_than += int(items_dominance[i][j]  or ((domination == DominationEnum.NODOMINATION) and (i_index < j_index))

        items_sorted[number_better_than] = i

The above is the serial code for such an algorithm, to make it parallel you remove the outer loop and run it per thread instance.

#i_index is thread index
def foo(items, items_sorted, items_dominance, i_index)
    number_better_than = 0
    for j_index, j in enumerate(items):
            domination = is_dominant(i, j)
            items_dominance[i][j] = domination == DominationEnum.DOMINATES
            number_better_than += int(items_dominance[i][j]  or ((domination == DominationEnum.NODOMINATION) and (i_index < j_index)))

    items_sorted[number_better_than] = i

Or change your bitonic sort comparison metric to

( i dominates j ) or (if neither i nor j dominates on another and index of i is before index of j) 

then run:

def foo(items, items_dominance, i_index)
    number_better_than = 0
    for j_index, j in enumerate(items):
         domination = is_dominant(i, j)
         items_dominance[i][j] = domination == DominationEnum.DOMINATES

Additionally you may halve the number of operations needed by finding the domination for [i][j] and using that to determine what the other domination would be (you can figure out if i dominates j, is dominated, or is not dominated nor dominates j, which also gives you the result for [j][i])