How to make a string histogram in CUDA

[rafaelgov95]

I need to create a histogram. The problem would be to create a SETMAP.

struct Elo {
    char ItemId[MAX_STR_SIZE];
    int indexArrayMap;
    int suporte;
 }

kerenel_histograma(Elo* data_bin,Elo* data_gerations){
atomiccAdd(&(data_bin[data_gerations[i].ItemId].suporte),data_gerations[i].suporte);
}

The problem is how to build Elo struct for such a purpose. I believe the operator should be rewritten.

Every time atomicAdd and invoked should query data_bin on the existence of data_gerations[i].ItemId which is a string, whether to add support.

[cbuchner1]

Hash tables could work for this purpose. You need a fast hash function (not necessarily with cryptographic strength). Then do the atomic counts based on a resulting integer hash. If you use e.g. 24 bit hashes, the entire table would still fit nicely into global memory. Hash bins that result in a collision will require special handling though.

Another idea may be to construct a tree from all the unique strings. The tree maps each string to an index stored in the leaf nodes and the atomic counting of the string histogram will be based on this index. The tree will be traversed like a decision tree: each level n of the tree corresponds to the n’th character of a string. The terminating null character of each string also has to be considered in the tree. Whenever a new string is encountered that differs at the given character (or level), you open up a new branch with a new index at the leaf node (use another atomic counter to generate a unique, incremental index)

General advice: before trying anything in CUDA, you should be able to solve the same problem in C or C++. It does not look like you have a concept of how to address the problem yet. So going to CUDA is too early at this stage.

[rafaelgov95]

Hash tables could work for this purpose. You need a fast hash function (not necessarily with cryptographic strength). Then do the atomic counts based on a resulting integer hash. If you use e.g. 24 bit hashes, the entire table would still fit nicely into global memory. Hash bins that result in a collision will require special handling though.

Another idea may be to construct a tree from all the unique strings. The tree maps each string to an index stored in the leaf nodes and the atomic counting of the string histogram will be based on this index. The tree will be traversed like a decision tree: each level n of the tree corresponds to the n’th character of a string. The terminating null character of each string also has to be considered in the tree. Whenever a new string is encountered that differs at the given character (or level), you open up a new branch with a new index at the leaf node (use another atomic counter to generate a unique, incremental index)

General advice: before trying anything in CUDA, you should be able to solve the same problem in C or C++. It does not look like you have a concept of how to address the problem yet. So going to CUDA is too early at this stage.

I have a CPU implementation.

void frequencia_x1(Elo** new_canditatos_cont_suporte, int *new_canditatos_cont_suporte_size , Elo** new_canditatos, int new_canditatos_size){
	        for (int i = 0; i < new_canditatos_size; ++i){

	            int index = 0;
	            bool newFlag = true;
	            while (newFlag ) {
	            	 if (0 == compare(new_canditatos_cont_suporte[index]->ItemId, "")) {
	            		                	(*new_canditatos_cont_suporte_size)++;
	            		                	my_strcpy(new_canditatos_cont_suporte[index]->ItemId,new_canditatos[i]->ItemId);
	            		                	new_canditatos_cont_suporte[index]->indexArrayMap = new_canditatos[i]->indexArrayMap;
	            		                	new_canditatos_cont_suporte[index]->suporte = new_canditatos[i]->suporte;
	            		                    newFlag = false;
	                } else if (0 == compare(new_canditatos_cont_suporte[index]->ItemId, new_canditatos[i]->ItemId)) {
	            	    	                new_canditatos_cont_suporte[index]->suporte += new_canditatos[i]->suporte;
	            		                    newFlag = false;
	                }else{
	           	               index++;
	                }
	            }
	   }
}

Could you tell me some material to study?