Is it possible to process an array of Binary tree parallelly in CUDA?

Question

I have a tree Node whose data is a string.

class node{
private:
    string data;
    node *left,*right;
}

And now i have an array of tree nodes where I have appended the contents of multiple file into the an array of Binary Tree.

Now I want to perform a Binary Search of a key Paralyze. Is it possible ?? As I'm aware that only the address of the root is stored in the elements of the array. Is it possible to copy the contents of the tree to the Device.?? Please do suggest me a search algorithm that is efficient than 2D array linear search . If i copy the whole array of tree would it still be efficient?

What do you mean by array of tree? An array which consists of roots of many trees? — Dani Grosu
– Dani Grosu, Commented Apr 16, 2016 at 14:09

Dani Grosu · Accepted Answer · 2016-04-16 14:19:38Z

1

As I understand from your question, you have an array of elements that represent the roots of many binary trees. If you want to send this array to your device, I would suggest to transform each tree in a sorted vector and perform binary search on each vector. That is, you will have an array of sorted arrays.
Now you can perform parallel binary search on all sub-arrays. You even can split each sorted array into groups and perform binary search on each group.

answered Apr 16, 2016 at 14:19

Dani Grosu

5542 gold badges4 silver badges24 bronze badges

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

Comments

Community · Accepted Answer · 2017-05-23 10:33:55Z

Depending on the use-case, the memory transfer might be the bottleneck, much more expensive than the search. Hence, you want to be very careful in the way you allocate memory. Using a node allocator that arranges nodes and pointers in arrays is good idea. Though, you may enter the following issues:

pointer may not be valid in both address spaces, you hence want to either use indices in arrays or unified memory to do this on a GPU.
to my knowledge, std::string is not supported in CUDA as discussed here, you then might prefer char* to point to string data (which should also be available in GPU memory space, hence a dedicated string storage system).

It is then possible to parallelize your search but the benefits will strongly depend on the number of trees you want to search. If it is small compared to the number of CUDA threads running on GPU (i.e. thousands), benefits are uncertain.

Searching some value in a small set might be better on GPU using technique similar to reduce (see scalar prod example in CUDA GPU Computing SDK), rather than actually building a tree.

Collectives™ on Stack Overflow

Is it possible to process an array of Binary tree parallelly in CUDA?

2 Answers 2

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related