How do I run this function with GPU.js?

Question

I want to run this permutations function on GPU.

function* permute(permutation) {
  var length = permutation.length;
  var c = Array(length).fill(0);
  var i = 1;
  var k;
  var p;

  yield permutation.slice();
  while (i < length) {
    if (c[i] < i) {
      k = i % 2 && c[i];
      p = permutation[i];
      permutation[i] = permutation[k];
      permutation[k] = p;
      ++c[i];
      i = 1;
      yield permutation.slice();
    } else {
      c[i] = 0;
      ++i;
    }
  }
}

To run this on GPU I try to use https://gpu.rocks/ but I do not understand their example of how to setup the threads. How should I write this permutations function so I can run it in the browser on GPU?

Answer 1

The GPU.js supports only a few operations, because it is translate to shaders. In the tests here you cannot use it to produce outputs longer than 100k elements.

The operations supported are very limited, you cannot assign to array elements for instance, and this is due to the nature of the underlying computation unit. Also you have to be aware of branch divergence.

Two steps were required to implement your function in a way that it could be used in a kernel.

1. make it parallel: Your implementation is iterative and each iteration builds a new result based on the result of the previous iteration. What I created instead is a function that given the iteration number J can produce a permutation.
2. make it scalar and without array modification: The function to compute permutation swaps elements on an array, thus requires assigning to array elements. To prevent that what I created is a loop where I track the locations of each the elements. If a given element ends at position I that element is returned. Notice that this function must be called once for each element in each permutation.

const gpu = new GPU();
// For reference
// This is the function to compute the J'th permutation
// of N elements. Rewrited to create the kernel.
function permutation(J, N) {
  const arr = []
  for(let i = 0; i < N; ++i)arr[i] = i;
  let j = J;
  for(let i = 2; i <= N; ++i){
    let e1 = j % i;
    const t = arr[e1];
    arr[e1] = arr[i-1];
    arr[i-1] = t;
    j = (j - e1) / i;
  }
  return arr;
}

function permuteAt() {
  const N = this.constants.length;
  let I = N - this.thread.x - 1;
  let J = this.thread.y;
  
  for(let d = 0; d < N; ++d){
    // check if the I'th element of the J'th permutation is d
    let dPos = d;
    let j = J;
    let i = 0;
    for(let i = 2; i <= N; ++i){
      let e1 = j % i;
      let e2 = i - 1;
      // track the movements element d
      if(e1 == dPos){
        dPos = e2;
      }else if(e2 == dPos){
        dPos = e1;
      }
      j = (j - e1) / i;
    }
    // element d ended at position i
    // console.log(JSON.stringify({dPos, I, J, N, t: this.thread}))
    if(dPos == I){
      return d;
    }
  }
  return -1;
}

// Run it in javascript
let result;
const t0Js = Date.now()
for(let i = 0; i < 1000; ++i){
  result = [0,1,2,3,4,5,6,7,8,9].map(v => permuteAt.apply({
  thread: {x: i, y: v}, 
  constants: {length: 10}
  }))
}
const tfJs = Date.now();
console.log('time spend in javascript: ', (tfJs - t0Js)/10000);

const generatePermutations = gpu.createKernel(permuteAt).setOutput([10, 10000]).setConstants({length: 10});

const t0GPU = Date.now()
for(let i = 0; i < 100; ++i){
  const c = generatePermutations();
}
const tfGPU = Date.now();
console.log('time spend in gpu: ', (tfGPU - t0GPU)/10000/100);

<script src="https://unpkg.com/gpu.js@latest/dist/gpu-browser.min.js"></script>