Parallel Programming With CUDA Tutorial (Part-4: The Floyd-Warshall Algorithm)

The Floyd–Warshall algorithm (Single Thread):

FloydWarshall(dis)
{
for (int k = 0; k < |V|; k++)
{
for (int i = 0; i < |V|; i++)
{
for (int j = 0; j < |V|; j++)
{
if(dis[i][j]<dis[i][k] + dis[k][j])
dis[i][j] = dis[i][k] + dis[k][j];
}
}
}
}

Step 1:

InnerLoops(dis,k) 
{
for (int i = 0; i < |V|; i++)
{
for (int j = 0; j < |V|; j++)
{
if(dis[i][j]<dis[i][k] + dis[k][j])
dis[i][j] = dis[i][k] + dis[k][j];
}
}
}
FloydWarshall(dis)
{
for (int k = 0; k < |V|; k++)
{
InnerLoops(dis,k);
}
}

Step 2:

InnerLoops(dis,k)
{
for (int i = 0; i < |V|; i++)
{
for (int j = 0; j < |V|; j++)
{
t=dis[i][k] + dis[k][j];
dis[i][j]=t*(t<dis[i][j])+dis[i][j]*(t>=dis[i][j]);
}
}
}
FloydWarshall(dis)
{
for (int k = 0; k < |V|; k++)
{
InnerLoops(dis,k);
}
}

Step 3:

__global__
void GPUInnerLoops(dis,k)
{
//calculates unique thread ID in the block
int t= (blockDim.x*blockDim.y)*threadIdx.z+ (threadIdx.y*blockDim.x)+(threadIdx.x);

//calculates unique block ID in the grid
int b= (gridDim.x*gridDim.y)*blockIdx.z+(blockIdx.y*gridDim.x)+(blockIdx.x);

//block size (this is redundant though)
int T= blockDim.x*blockDim.y*blockDim.z;

//grid size (this is redundant though)
int B= gridDim.x*gridDim.y*gridDim.z;

int t;
/*
* Each cell in the matrix is assigned to a different thread.
* Each thread do O(number of asssigned cell) computation.
* Assigned cells of different threads does not overlape with
* each other. And so no need for synchronization.
*/
for (int i=b; i<|V|; i+=B)
{
for(int j=t; j<|V|; j+=T)
{
t=dis[i*V+k]+dis[k*V+j];
dis[i*V+j]=t*(t<dis[i*V+j])+dis[i*V+j]*(tm>= dis[i*V+j]);
}
}
}
FloydWarshall(dis)
{

for (int k = 0; k < |V|; k++)
{
GPUInnerLoops<<<dim3(x,y,z),dim3(a,b,c)>>>(dis,k);
cudaDeviceSynchronize();
}
}
t=dis[i*V+k]+dis[k*V+j];
dis[i*V+j]=t*(t<dis[i*V+j])+dis[i*V+j]*(tm>= dis[i*V+j]);

Benchmark

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store