# Parallel sorting algorithm that compares all elements

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.

• Gonna need you to define this "comparison metric". For example, if I compare 3 to 1 is the comparison metric `True` or is it `2`? Commented Oct 1, 2017 at 0:03
• The comparison returns a boolean. Commented Oct 1, 2017 at 0:32
• In that case all you have to do is sort in any way you like. After that you can get the "comparison metric" by comparing the indexes. Commented Oct 1, 2017 at 0:35

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.

• This analysis is correct. The optimization I suggested of using the indexes after the sort only works if no two elements are equal. Commented Oct 1, 2017 at 14:13
• It seems my array may exhibit the complication that you hinted at in the first possibility. Please refer to my updated comments. Commented Oct 1, 2017 at 22:35
• @Olumide: If to elements are neither smaller nor greater, what should their comparison metric be? Commented Oct 2, 2017 at 8:59
• Bart I'm clearly using the wrong terminology. The comparison is based on dominance as explained in my SO post. The metric I'm looking to cache in step 2 is the dominance. Commented Oct 2, 2017 at 9:08
• @Olumide Does your metric output something else besides a boolean value? If not this has nothing to do with you "using the wrong terminology" and you need to refer back to what Bart said. You say you are looking to "cache the dominance" but you don't explain how that is different from recording a boolean value. If recording the dominance means recording a single boolean value, then Bart has sufficiently answered your question period. If not, you have not adequately explained what you want to cache and you absolutely need to explain it Commented Oct 6, 2017 at 14:53

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]`)