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.
Monday, 10 March 2014
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.
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.
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.
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.
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.
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
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
|
Subscribe to:
Posts (Atom)
