Monday, 10 March 2014

Meetings: Monday 10th March 2014

Discussed the results from the following set of tests and concluded that there is not much other work that can be done on this area at this time. http://10004794-honours-project.blogspot.co.uk/2014/03/streams-vs-device-functions-2.html

All that is really left to do is test the parallel implementation on the 5 test maps and then continue writing up the results. This week will most likely be the final week of coding for the project.

Wednesday, 5 March 2014

Streams vs Device Functions 2

In the previous post we looked at using device functions and evaluating each of the neighbours sequentially compared to using streams and evaluating each of the neighbours concurrently.

Interestingly we found that performing the check sequentially was actually faster than using streams, this post attempts to determine why this is.

Map
Sequential Time
Device functions
Streams
32x32
1
8.341714
21.75491
64x64
3.8
16.37582
47.9231
128x128
16.2
32.52248
133.1749
256x256
68.01
65.31222
409.7781
512x512
277.07
140.5209
19658.81
1024x1024
1146.38
399.7442
144157.2
2048x2048
4954.72
1745.794
462554.9
Device Functions vs Streams

Evaluate Neighbours Device Function

Evaluate Neighbours Kernel

Looking at the code snippets above they are both almost identical, the only real difference is that one is tagged with the __device__ keyword while the other is tagged with __global__, however this seems to make a big difference.

Map
Device Function
Create streams
Kernel with Streams
Kernel without streams
32x32
0.014075
0.017313
0.284529
0.262266
64x64
0.014052
0.017732
0.315197
0.297716
128x128
0.014728
0.018648
0.308442
0.400251
Time for different methods of evaluating neighbours


When we call a device function from within a thread we are not actually creating a new parallel block and thread to handle the process we are simply just calling a function in the same manner we could from the host. However when we use a kernel to handle the evaluation we need to launch a block and thread to handle the process, when using streams to launch the kernels concurrently we also have an extra overhead of having to create the streams.

Looking at the graph above we can see that we can call the device function to evaluate all 8 of our nodes neighbours quicker than we can create 8 streams to handle the neighbours. On top of the stream creating we also have to launch 8 kernels creating 8 blocks and threads to process the neighbors, this process in itself is extremely slow taking almost 18X longer than it does to call our device function. 

Interestingly however it appears that using streams is potentially faster than not using streams, however this would really need to be tested for more graph sizes to get a fair results, this was not possible at the time due to errors in the timing code for large graph sizes.

The next change that was attempted involved each node storing a list of its neighbours in global memory on the device. In doing this it meant that it would be possible to call a single kernel which could be used to evaluate all of the 8 neighbours at the same time rather than calling an individual kernel for each neighbour as is needed when storing the nodes neighbours in local memory.

Evaluate all neighbours kernel

This resulted in a large speed up when compared to calling an individual kernel for each neighbour when using streams, however it is still slower than calling device functions. There was very little difference between calling the device functions when storing the neighbours in local memory compared to global memory. 

Map
Device Local Mem
Device Global Mem
Kernel Local Mem
Kernel Global Mem
32x32
8.341714
8.41365
21.75491
14.15247
64x64
16.37582
16.51353
47.9231
29.25797
128x128
32.52248
32.9504
133.1749
61.81864
256x256
65.31222
65.97365
409.7781
138.1582
512x512
140.5209
142.72
19658.81
345.5626
1024x1024
399.7442
410.5048
144157.2
1094.155
2048x2048
1745.794
1777.783
462554.9
4441.894

Map
Call device function
Call kernel
32x32
0.007322
0.034438
64x64
0.007232
0.035898
128x128
0.007338
0.037483
256x256
0.007511
0.040405
512x512
0.007879
0.047797
1024x1024
0.008057
0.04972
2048x2048
0.008066
0.051512

Tuesday, 25 February 2014

Meetings: Tuesday 25th February 2014

Discussed the results from attempting to parallelize the inner loop of the dijkstra application. Using cuda streams has resulted in a slow down of the application so further tests to determine why this is happening need to be carried out. Possible reason for this is that to simply create the streams on the GPU takes much longer than it does to simply evaluate an individual neighbour.

The paper 'A New GPU-based Approach to the shortest path problem' uses a similar method and reported a speedup of 220x, it may be worth while emailing and asking to see the source code to perform a comparison between their implementation and my own.

Monday, 24 February 2014

Streams vs Device Functions

Map
Sequential Time
Device functions
Streams
32x32
1
8.341714
21.75491
64x64
3.8
16.37582
47.9231
128x128
16.2
32.52248
133.1749
256x256
68.01
65.31222
409.7781
512x512
277.07
140.5209
19658.81
1024x1024
1146.38
399.7442
144157.2
2048x2048
4954.72
1745.794
462554.9


Cuda streams are a sequence of operations that execute in issue-order on the GPU. CUDA operations in different streams may run concurrently. 

Device functions are functions which can be called from within kernel code and are executed on the GPU, they cannot be called from the host. 


Sunday, 23 February 2014

780 vs Titan vs K40

Thanks to the help of some friends i was able to run the parallel dijkstra implementation on some different hardware all based on the kepler architecture.

Map
K40
780
Titan
32x32
8.341714
8.057811
8.645273
64x64
16.37582
15.68679
15.75337
128x128
32.52248
28.07575
28.05111
256x256
65.31222
54.97772
55.49513
512x512
140.5209
119.8173
119.7446
1024x1024
399.7442
355.7623
338.7315
2048x2048
1745.794
1589.061
1449.108


Tuesday, 18 February 2014

Meetings: Tuesday 18th February 2014

Went over the initial results from the parallel Dijkstra where the outer loop of the algorithm has been parallelized. The initial results are promising having seen a speed up of about 60% for the larger graph sizes.

Further work can be done to parallelize dijsktra through parallelization of the inner loop which should allow for a greater speed up.

Work can also be done to improve the frontier set selection process which could result in better performance.

The dates for the honours project have now changed as well. The poster presentation is now the Wednesday of week 13 and the hand in of the report is the 28th of April.

Monday, 17 February 2014

Parallel Dijkstra

The initial version has only parallelized the outer loop of the algorithm and has not been done in the most efficient way however has provided a significant speed up for the larger graph sizes.

For each graph the source node was the top left and the goal node was the bottom right, both the parallel and sequential implementations found the same path

map
Sequential Dijkstra (ms)
Parallel Dijkstra (ms)
32x32
1
8.49
64x64
3.8
16.73
128x128
16.2
33.20
256x256
68.01
66.38
512x512
277.07
142.77
1024x1024
1146.38
405.50
2048x2048
4954.72
1763.95