1

I'm trying to implement the Merge Sort algorithm on CUDA which is mentioned on the Designing Efficient Sorting Algorithms for Manycore GPUs.

For this as in the intermediate level, It has suggested to assign a thread block to merge two sorted arrays (say A and B) to a single array. And the idea is to assign a thread to data - a_i on the array A and find its location on B array using Binary Search. and if the position of a_i on B is j the a_i's position on new array is (i+j)

But when I implemented this (or tried to), I found a scenario that above method doesn't seems to work. For example if the two arrays that need to be merged are as follows,

enter image description here

and

enter image description here

So that the 53 on the first array (shaded in gray one) will find that its respective position on the second array is 11, So its position on the final array is (11 + 11 = 22). And likewise position of 53 on the first array which is shaded in blue is (11 + 12 = 23).

If we take the 53 of the second array its final position is also given as (11 + 11 = 22). Which conflicts with the grey color 53 on the first array.

So according to my understanding a simple binary search algorithm cannot be used to merge these two arrays. Is there a known or easier method to resolve this conflict?

Improve this question

2 Answers 2

Reset to default
1

In the paper, I read:

Given the sorted sequences A and B, we want to compute the sorted sequence C = merge(A, B). If these sequences are sufficiently small, say of size no greater than t = 256 elements each, we can merge them using a single t-thread block. For an element ai ∈ A, we need only compute rank(ai , C), which is the position of element ai in the merged sequence C. Because both A and B are sorted, we know that rank(ai , C) = i + rank(ai , B), where rank(ai , B) is simply the count of elements bj ∈ B with bj < ai and which we compute efficiently using binary search. Elements of B can obviously be treated in the same way.

You have to deal with duplicates in the binary search, when you are looking for rank(ai, B). Imagine B as a BST, rank(ai, B) = max of j {bj <= ai} +1 should work well.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

Okay, even if we used that, wouldn't we still get the conflict when we try to find the final locations of the grey colored 53's given that the blue colored 53 is some other value?
We wouldn't. Let's take the example of an array A, such that A = 78,73,63,53,53, ... 53. Should we have a conflict with another ai in A? No, as rank(ai, C) = i + rank(ai, B), i is in fact the position of ai in the array A. i is actually different for each 53 in A. Hence, for a constant rank(ai, B), no conflict with other ai is possible. Futhermore, let's take an array B, such that B = 84,58,58,53,53, binary search easily ensures rank(ai, B) is no other 53 in B. Hence, rank(53, C) will be no other rank(xi, C), with xi in A U B and xi = 53
I was referring to an example like this, A = 78,73,53,49,45 and B = 84,58,58,53,40. So as per your rank(ai,B) function, rank(53_A, B) = 3 (where 53_A is 53 in the array A) thus giving rank(53_A,C) = 2 + 3 = 5. Similarly, rank(53_B, A) = 2 giving rank(53_B, C) = 3 + 2 = 5. So we have a situation where rank(53_A,C) = rank(53_B, C) which writes the both 53 of each array A and array B into the 5th location of C, which is a conflict
0

Sorry I'm a bit late, but I just try to implement the same algorithm on a FPGA.

It should work if you just use <= comparison to binary sort A into B and < comparison if you sort B into A. That way you have a guaranteed order that elements from A will always be lower in the index than elements from B even if they are the same.

In your example the positions would be:

  • Grey A 11 + 11 = 22
  • Blue A 12 + 11 = 23
  • Grey B 11 + 13 = 24

Sidenote: I would recommend start counting from 0 for the indexing (I choose the same counting as you for clarity). Like this the first index in the Array C is 1 + 1 = 2

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.