A batch of insertions on hash table

[Isaias Frederick]

Hello, guys!

I'm brazilian student and  i've to implement a simples hashtable in GPUs for my research in Msc degree project. I'm looking for features of cudpp library and i wanna to know if this library can perform a lot of insertions in a batch mode avoiding the costs of transfer invocation. I need to implement this feature somehow and use some policies to avoid collisions too.

About parallelism, any parallelism key-level exists?

Thank's so much

[John Owens]

cudpp_hash will take a list of keys (or a list of key-value pairs) on the GPU and create a GPU hash table from it. It requires no data transfer to/from the CPU. It does leverage data parallelism across keys (many keys are inserted simultaneously). 

What it doesn't do is incremental inserts. You can't first build a hash table and then want to put more items into it after it's built.

JDO

[Isaias Frederick]

I haven't understand the idea about of data already located on GPU. If i wanna insert a colection of data  in a <key: value (int list)> structure i'll not need alocate data in CPU-side and make a transfer the batch of <key: value> pairs?

Other information: if my value will be a linear structure of each pair i've to pass a parameter of a worst case of all list-values length inserted. Right?

I just wanna use a algorithm that seems like a bucketsort to use the collisions to concatenate lists of equal keys using workloads that can be splitted on a N batches.

I think which this new asks are more clear.

thank for your patience, John.

[John Owens]

On Saturday, May 7, 2016 at 4:09:47 PM UTC-7, Isaias Frederick wrote:

I haven't understand the idea about of data already located on GPU. If i wanna insert a colection of data  in a <key: value (int list)> structure i'll not need alocate data in CPU-side and make a transfer the batch of <key: value> pairs?

Depends on where your data is. If it's on the CPU, then yes, as you say, you will have to transfer it first from CPU to GPU. However, if you have a GPU kernel that produces the key-value pairs in GPU memory, you can then build the hash table from those pairs directly without having to transfer any data between CPU and GPU.

 

Other information: if my value will be a linear structure of each pair i've to pass a parameter of a worst case of all list-values length inserted. Right?

I don't understand what you're asking here.

 

I just wanna use a algorithm that seems like a bucketsort to use the collisions to concatenate lists of equal keys using workloads that can be splitted on a N batches.

Again, sorry to say I don't understand what you're asking here.

JDO

[Isaias Frederick]

Example:

My hash on CPU:

1 -> 1,2,3,4,5,6  (length = 6)

7 -> 1,2, 5 (length = 3)

9 -> 3,9 (length = 2)

I wanna insert a <7 : {6, 9, 10}> on hash and append a list of key 7 already inserted.

[John Owens]

Are you suggesting that you have multiple values stored per key? In the example below, you have 3 keys, 1 7 9, and key 1 has 6 entries in it etc.?

CUDPP_MULTIVALUE_HASH_TABLE handles this case. But in CUDPP, you can't build the hash table from a set of key-value pairs THEN LATER insert more key-value pairs into. No CUDPP hash table (and to the best of my knowledge, no GPU hash table at all) supports incremental updates to existing hash tables.

JDO