title: CUDA An algorithm to partition an array into blocks based on sum of elements
body: <p>Here is the problem: I have an array containing random numbers. I am supposed to partition them into blocks, such that in each block, sum of all elements is no bigger than a given N. I thought I can simply solve this with scan, but there is a nasty bug that I don't know how to solve efficiently</p>
  
  <p>So for example, I try as follow: <code>N=8</code>, the array is:</p>
  
  <pre><code>{2, 3, 1, 4, 4, 1, 6}
  </code></pre>
  
  <p>Performing an inclusive sum scan:</p>
  
  <pre><code>{2, 5, 6, 10, 14, 15, 21}
  </code></pre>
  
  <p>and then do a simple integer division by <code>N=8</code> and result in the following partition:</p>
  
  <pre><code>{0, 0, 0, 1, 1, 1, 2}
  </code></pre>
  
  <p>And then I realized there is a bug that the sum of all elements in the second block is <code>4+4+1=9</code> instead of <code>8</code>, because by using the integer division, I assumes that the sum of all elements in the first block has to be 8. </p>
  
  <p>The correct partition is supposed to be:</p>
  
  <pre><code>{0, 0, 0, 1, 1, 2, 2}
  </code></pre>
  
  <p>I tried to loop through the list and re-partition the boundary points, but my parallel implementation becomes slower than the serial implementation. Do you happen to know an efficient parallel algorithm for this problem?</p>