title: Small sized binary searches on CUDA GPUs
body: <p>I have a large device array <code>inputValues</code> of <code>int64_t</code> type. Every 32 elements of this array are sorted in an ascending order. I have an unsorted search array <code>removeValues</code>.</p>
  
  <p>My intention is to look for all the elements in <code>removeValues</code> inside <code>inputValues</code> and mark them as <code>-1</code>. What is the most efficient method to achieve this? I am using a 3.5 cuda device if that helps.</p>
  
  <p>I am not looking for a higher level solution, i.e. I do not want to use thrust or cub, but I want to write this using cuda kernels.</p>
  
  <p>My initial approach was to load every <code>32</code> values in shared memory in a thread block. Every thread also loads a single value from <code>removeValues</code> and does an independent binary search on the shared memory array. If found, the value is set according by using an if condition.</p>
  
  <p>Wouldn't this approach involve a lot of bank conflicts and branch divergence? Do you think that branch divergence can be addressed by using ternary operators while implementing the binary search? Even if that is solved, how can bank conflict be eliminated? Since the size of sorted arrays is 32, would it be possible to implement a binary search using shuffle instructions? Would that help?</p>
  
  <p>EDIT : I have added an example to show what I intend to achieve.</p>
  
  <p>Let's say that <code>inputValues</code> is a vector where every 32 elements are sorted:<br>
  <code>[2, 4, 6, ... , 64], [95, 97, ... , 157], [1, 3, ... , 63], [...]</code></p>
  
  <p>The typical size for this array can range between 32*2 to 32*32. The values could range from <code>0</code> to <code>INT64_MAX</code>.</p>
  
  <p>An example of <code>removeValues</code> would be:<br>
  <code>[7, 75, 95, 106]</code></p>
  
  <p>The typical size for this array could range from <code>1</code> to <code>1024</code>.</p>
  
  <p>After the operation <code>removeValues</code> would be:
  [-1, 75, -1, 106]</p>
  
  <p>The values in <code>inputValues</code> remain unchanged.</p>