Showing posts with label Meetings. Show all posts
Showing posts with label Meetings. Show all posts

Thursday, 10 April 2014

Poster Presentation 9th April 2014


The video below is a small demo which shows the difference in paths between diffusion and dijkstra. The green paths represent diffusion while the purple paths represent dijkstra. 


Monday, 24 March 2014

Meetings: Monday 24th March 2014

Discussed the poster presentation and what needs to be included in the poster. The aim is to have an initial draft by Monday 31st March.

Also need to revise the initial questions outlined during the background. Possible questions are.

1. Find a suitable algorithm for path finding on the GPU.
2. Quantify in terms of
     a) speed
     b) Layout of path - scalability
     c) trade-off : Speed vs Path style
3. What contributes to the GPU - Mapping of algorithms to the GPU

Also need a section for contributions.

Monday, 17 March 2014

Meetings: Monday 17th March

Discussed the results obtained from last weeks experiments and concluded that all the implementation, results and testing have all been completed. The remainder of the project will be focused on the write up and the poster session.

Discussed that it should be possible to use the coursework for computational intelligence to show a robot moving through the maze using collaborative diffusion.

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.

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.

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, 10 February 2014

Meetings: Monday 10th February 2014

The tesla K40 donated by nvidia arrived last friday and was fitted into the testing hardware, we discussed the results from the initial tests which were carried which involved running the parallel diffusion for a range of graph sizes and discussed the results of the survey that was handed out to several students asking them which path they felt was the most 'realistic' for an agent to take through a map.

The aim for the remaining 7 weeks of the project is to implement and test a parallel dijkstra and finish writing up the report.

Monday, 27 January 2014

Meetings: Monday 27th January

Until the new GPU arrives the aim is to continue writing up the methodology and the experiments that have been carried out with the current complete applications. Discussed ways that experiments should be presented and how the results should be analysed.

Monday, 20 January 2014

Meetings: Monday 20/01/14

Discussed the work that has been carried out during the winter break.

During the holidays i applied for an academic hardware donation from Nvidia, they have kindly agreed to donate a Tesla K40 to help with the project. This will provide the power of dynamic parallelism which should simplify the parallel Dijkstra application and provide a significant speed up. However the card will not be arriving until February which adds an extra time pressure to the project.

Currently have the following applications completed

  • Sequential Diffusion
  • Parallel Diffusion
  • Sequential Dijkstra
  • Sequential A* 
  • Parallel Euclidean Distance
Until the card arrives the time will be spent writing up the methodology and the implementation for the applications which have been completed. Once the card has arrived the planned tests can be carried out and the results written up. 


Tuesday, 10 December 2013

Meetings: Friday 6th December

Looked at some of the results from Nsights performance analysis tools for CUDA and looked at how they could be used within the project to give an insight into how well the application is performing in terms of branching and memory usage.

Also decided to look at a parallel implementation of Dijkstra as well, having a quick look around Google there appear to be lots of example implementations where people have attempted to parallelize the algorithm.

Aim for this week is to read over some of the existing work that has been done using parallel Dijkstra implementations.

Monday, 2 December 2013

Meetings: Friday 29th November

Discussed the list of tests that were outlined in the testing plan and went over what measurements should be recorded from the tests.

Not a lot of work has been completed on the project over the last week due to upcoming coursework and exams.

Saturday, 23 November 2013

Meetings: Friday 22nd November 2013

Discussed the technical work that has been done so far and went over the initial timings that were taken for both the sequential and parallel versions of the diffusion application. 

Agreed that due to the nature of the diffusion pathfinding it would be unfair to compare to A* as the diffusion process returns all paths to a goal node whereas A* only returns a single path. Due to this it may be better to compare against an implementation of Dijkstra instead. 

Need to come up with a plan of tests which need to be run that includes a range of challenges for the algorithm to deal with such as static and dynamically changing goals etc. 

Friday, 8 November 2013

Meetings: Week 9 Review

Had the week 9 review with the second marker. Discussed the lit review and aims of the project and received feedback on the project.

Feedback

  • Changes heading on lit review section Artificial intelligence in  games to pathfinding algorithms in games. 
  • Add a section on dijkstra's algorithm. 
  • Test cases need to be well designed, Take as many timings as possible and get an average and use t testing to determine if the data sets are significantly different from one another. 
Overall the feedback was positive and constructive, the project is on track and has clear goals about what needs to be achieved for the project to be successful. 

Friday, 1 November 2013

Meetings: Friday 1st November 2013

Not much work was done on the background for the project this week due to other coursework deadlines.

Went over techniques that could help with the flow of the document as it is felt that this could be better. This includes writing everything up and then going back at the end and adding in a couple sentences to each section to help with the flow. It may also be helpful to create a flow diagram for each section and follow this.

Also discussed the existing work chapter, rather than having a heading for each paper instead talk about the main points of the paper and use the paper as a reference. For example talk about parallel AI and some of the considerations that need to be taking into account as referenced in the paper by Timothy Johnson and John Rankin and then talk about a* pathfinding and reference the paper by Owen Mcnally. Rather than talking about the paper on collaborative diffusion in this section, discuss it in the section on diffusion.

The week 9 meeting is scheduled to be for Friday the 8th if the second marker is available. For this the draft of the background is to be sent to the second marker the day before and a 1 to 2 page report on the technical work needs to be written up.

Friday, 25 October 2013

Meetings: Friday 25th October 2013

Went over the current draft of the background. Agreed that this should be completed by Friday 1st of November to be sent to second marker in time for the week 9 review.

For the week 9 review need to complete a report on what other work has been carried out during the project, including any practical work or other research, also need to create a revised plan of what work is to be done and estimated dates of when this will be completed.

Received feedback from IPO. Main feedback was that the project could be too complex a project for honours level, it is important to establish where this project is re-implementing existing algorithms or develops new ones.

Friday, 18 October 2013

Meetings: Friday 18th October 2013

Went over the work that has been done on the lit review, agreed that it is along the right tracks and to continue with it, with the aim to be completed by week 9 review. Agreed that more detail is needed on the working of the GPU as this will be specific to the implementation.

Found an A* CPU implementation that has been used in professional triple A games. This will be modified to suit the needs of the project and used as a benchmark to compare the GPU implementation of a diffusion based algorithm.

Asked to get a copy of the work on pathfinding from the computational intelligence module as this may be helpful.

Still wait on feedback from IPO from second marker.

Friday, 11 October 2013

Meetings: Friday 11th October 2013

Presented a draft of the sections that are to be included in the lit review. Agreed that don't need to go into too much detail about the different types of parallel systems only need to give a brief overview.

Look more closely at why using the GPU and why the particular technology could be useful for running pathfinding algorithms. highlight the differences and the advantages/disadvantages over the CPU.

Look at the different APIs that are available for programming on the GPU and give a justification about the chosen API.

Look at the different types of pathfinding algorithms which are available and what is traditionally used in games.

Highlight the advantages/disadvantages in the context of the project and look at the existing work that has been done and pick out what the findings/conclusions are and how they relate to the current project.

Discussed how the algorithms are going to be compared and what the best method of comparing the algorithms would be. Decided that A* is going to be very difficult to paralyze and that the best method if running a GPU implementation of A* would be to test it for a large number of agents and look at the scalabilty in comparison to the GPU. This has already been a few times in the past so it may be better to compare a CPU implementation of A* for a large number of agents against a GPU implementation of a diffusion based algorithm and see which has the better scalabilty and performance. The reason for this is that a CPU A* implementation is what is traditionally used in games so by comparing it against a different algorithm implemented on the GPU it may be possible to find a better algorithm for performing pathfinding within games?

Discussed how rendering could be effected by running the algorithms on the gpu for a large number of agents. Concluded that rendering is not important as the problems are the same for the CPU and GPU implementation, at this stage is has been decided that no rendering of agents will be carried out however if the project is successful and there is time left over it is something that could be implemented to make the application more visually appealing.

Aims for the coming week are to complete a first draft of the lit review in preparation for the week 9 meeting.

Friday, 4 October 2013

Meetings: Friday 4th October 2013

Went over Gantt chart and reviewed dates and times for each section. Agreed that the write up should be a continual process throughout the entire project and not just at the end of the project. Gantt chart will be updated to reflect this.

Discussed how data structures and the chosen heuristics could affect the implementation of A* if done poorly. One possible solution to this is to find an implementation of A* that is assumed to be efficient and use it for comparisons.

Began a sequential implementation of A* for a 2D map during the week, aim is to complete this for Friday 11th October and then continue work on it to lead to pathfinding over a dynamic 3D map.

Look into papers about parallel AI and continue with writing up lit review.


Friday, 27 September 2013

Meetings: Friday 27th September 2013

Looked over changes made to the IPO and agreed it was ready to be handed in. Submitted it to the school of computing office at 13:30.

Discussed impact that offloading AI onto the GPU may have an effect on rendering if too much of the resource is taken up by the pathfinding. May need to be aware of and test this during the testing and evaluation stage of the project. possibly create a graph showing how much time is taken up by rendering vs pathfinding.

create gantt chart of project plan for next Friday.

Look into implementing terrain, doesn't need to be complicated, don't actually need to render anything at this stage just need to be able to access the data correctly on the GPU with minimal passing of data between the CPU and GPU as this will cause a major slowdown and greatly effect performance. Look into getting interoperability working and storing the data in VBO's etc.

Keep reading papers for the lit and tech review.

Start draft chapters for the week 9 review and keep a log of any technical work done.

Monday, 23 September 2013

Meetings: Friday 20th September 2013

Overview of our meeting on Friday 20th September.

Went over first draft of initial project overview and discussed what changes needed to be made before handing in on Friday 27th September.

Discussed what work needs to be completed for the following week.

Next Steps

  • Create wiki for the project.
  • Create plan for the project.