GPGPU Programming for Games and Science

376 GPGPU Programming for Games and Science

if ( dcandidate < dmin )

{

dmin = dcandidate ;

previousmin = (x−1, y −1);

}

d(x,y) = dmin;

previous(x,y) = previousmin ;

Once the distances have been computed, the path is generated by

stack<intpair> path ;

x=S− 1; y = S − 1;

while (x != −1&&y != −1)

{

path . push ( x , y ) ;

(x, y) = previous(x, y);

}

and you can pop the stack to visit the path nodes from (0, 0) to (S −1,S−1).

The algorithm for shortest path is straightforward to implement for the

CPU. However, implementing a GPU version that has decent performance

is more difficult. The first problem is implementing the partial sums via the

loops for d(x, 0) and d(0,y). A single GPU thread could be dedicated per

loop, but that sequential operation is not efficient. Instead, ...