title: Is it possible to use CUDA in order to compute the frequency of elements inside a sorted array efficiently?
body: <p>I'm very new to Cuda, I've read a few chapters from books and read a lot of tutorials online. I have made my own implementations on vector addition and multiplication.</p>
  
  <p>I would like to move a little further, so let's say we want to implement a function that takes as an input a sorted array of integers.</p>
  
  <p>Our goal is to find the frequencies of each integer that is in the array. </p>
  
  <p>Sequentially we could scan the array one time in order to produce the output. The time complexity would be <code>O(n)</code>.</p>
  
  <p>Since the groups are different, I guess it must be possible to take advantage of CUDA.</p>
  
  <p>Suppose this is the array</p>
  
  <pre><code>   1
     1
     1
     1
     2
     2
     3
     3
     5
     5
     6
     7
  </code></pre>
  
  <p>In order to achieve full parallelism, each thread would have to know exactly which part of the array it has to scan in order to find the sum. This can only be achieved if we use another array called <code>int dataPosPerThread[]</code> which for each thread id the <code>dataPosPerThread[threadId]</code> would have as value the starting position on the initial array. So, that would mean that each thread would know where to start and where to finish.</p>
  
  <p>However in this way we won't gain anything, because it would take us <code>O(n)</code> time in order to find the positions. Eventually the total cost would be <code>O(n) + cost_to_transfer_the_data_to_the_gpu + O(c) + cost_to_transfer_the_results_to_the_gpu</code>
  where <code>O(c)</code> is the constant time it would take for the threads to find the final output, assuming of course that we have many different integers inside the initial array.</p>
  
  <p>I would like to avoid the extra <code>O(n)</code> cost.</p>
  
  <p>What I've thought so far is, having an array of size <code>arraySize</code>, we specify the total amount of threads that will be used, let's say <code>totalAmountOfThreads</code> which means that each thread will have to scan <code>totalAmountOfThreads/arraySize</code> values.</p>
  
  <p>The first thread(id 0) would start scanning from position 0 until position <code>totalAmountOfThreads/arraySize</code>.</p>
  
  <p>The second thread would start from <code>totalAmountOfThreads/arraySize + 1</code> and so on.</p>
  
  <p>The problem is though that some thread might be working with different integer groups or with one group that has more values being processed by other threads. For instance in the above example if we suppose that we will have 6 threads, each thread will take 2 integers of the array, so we will have something like this:</p>
  
  <pre><code>   1     &lt;-------- thread 0
     1
     1     &lt;-------- thread 1
     1
     2     &lt;-------- thread 2
     2
     3     &lt;-------- thread 3
     3
     5     &lt;-------- thread 4
     5
     6     &lt;-------- thread 5
     7
  </code></pre>
  
  <p>As you can see thread 0 has only <code>1</code> values, however there are other <code>1</code> values that are being processed by thread 2. In order to achieve parallelism though, these threads have to be working on unrelated data. Assuming that we will use this logic, each thread will compute the following results:</p>
  
  <pre><code>   thread 0 =&gt; {value=1, total=2}
     thread 1 =&gt; {value=1, total=2}
     thread 2 =&gt; {value=2, total=2}
     thread 3 =&gt; {value=3, total=2}
     thread 4 =&gt; {value=5, total=2}
     thread 5 =&gt; {{value=6, total=1}, {value=7, total=1}}
  </code></pre>
  
  <p>By having this result what can be further achieved? Someone could suggest using an extra hash_map, like <code>unordered_map</code> which can efficiently update for each value computed by a single thread the total variable. However</p>
  
  <ol>
  <li><p><code>Unordered_map</code> is not supported by cuda compiler</p></li>
  <li><p>This would mean that the threads would not be able to take advantage of shared memory because two threads from different blocks could be working with the same values, so the hash map would have to be in the global memory.</p></li>
  <li><p>Even if the above two weren't a problem, we would still have race conditions between threads when updating the hash map.</p></li>
  </ol>
  
  <p>What would be a good way in order to approach this problem?</p>
  
  <p>Thank you in advance</p>