Honours project I/O

Drafting

2009-05-18T09:11:00.003+01:00

I'll be getting the comments on my first draft today and then doing alterations to get it all fixed up for wed. I'd hope to be able to bind and burn all CDs required tomorrow and then hand in so its not pushing on the snarling at anyone near a printer.
Layout is mostly done just all the corrections and alterations to some of the references. CD is mostly compiled but I'm going to have to change a couple of comments, minor changes so it won't require the application to be recompiled.
The altered version of TBB and the vector class is already on the CD and ready to go along with all source and results. Apart from checking that all the pdfs I can get my hands on are on the CD and adding the poster this will be the biggest CD I've ever had to burn excluding the group project. A whole 50Mb! Not just 7Kb worth of code!

Anyway I'll also quickly need to check the formatting as if all of the appendices need to be 1.5 line spaced the whole thing is going to be more pages.
Also got to take a trip down to the copy shop today to pick up some CD sleeves and check if they can print an A2 poster on 4 A4 bits if they can then it will save me getting expensive printing somewhere else.
Last thing I'm hoping is that there isn't too many corrections or alterations I need to make.

Maths

2009-05-11T10:12:00.003+01:00

I've spent thurs/fri last week attempting to do maths revision as the exam is on wed. So for the first pat of this week I'm probably not going to have much time to work on my dissertation (probably work on it when it gets late and my concentration is virtually 0). From the last list:

To Do

Conclusion (Further work section)
More pruning required
Formula/Figure page numbers done on final pass
Bibliography/References done on final pass

Which means that mostly now its tiding up and then compiling the CD, I've already got some of that done but whats going to take the most time is obtaining copies of all research papers that I used/consulted. The very last thing to do will be to grab a XML backup of this blog and sling it on the disc. As well as I'll need to reread the style guide again just to make sure all the margins are correct and the figures are used correctly.

First Draft

2009-05-05T20:12:00.004+01:00

Just got the conclusion to write.
But first I'm going to put together what I've got at the moment because its not the writing and rework that's going to take ages its getting MS word to format everything the way that is required. That's going to be the main problem.
I've mostly got it set up but I've no real idea on how to stop the front page getting numbered it even is ignoring the page break.

Already with the problems I had getting the table of contents to work correctly I consider it might be best to manually add and maintain the formula and figure list because of the lack of changes that will be done to them.

To Do:

Conclusion
Rework the rest
List formula page numbers
List figure page numbers
Full bibliography
Check how to handle multiple use age of the same reference
Check if figures in appendices need figure numbers
Alter the appendix numbers in the methodology section to reflect new appendix numbers
Fix page numbering
Tech Poster
Discover how the hell your supposed to attach a CD to the back cover
Compile more information for the CD

I'll do some more of the tech poster tomorrow after checking I can actually do my slides in the right amount of time.

I'd like to work directly with the first draft document the problem is making sure that things like the abstract are correctly updated.

Those const errors

2009-05-01T20:38:00.004+01:00

Think I've just realised why I was getting such major const errors when trying to modify the objects stored within the table:

The entirety of the body passed into the parallel_for, any of the variables that are stored locally inside the helper class are declared constant.

This is to make sure anything passed into the Body is uniform between all threads. Could have possibly fixed it in a few seconds by just passing the pointer to the concurrent hash map into a local variable of the CollisionHelper::operator ().

Oh well too late now I went and hacked up the = operator to do my dirty bidding and that fixed it.

Graphs!Graphs!Graphs!Graphs!Graphs!Graphs!

2009-05-01T20:06:00.001+01:00

Really the number of slides I've got for the conclusive presentation is spiraling out of control. I can add more graphs showing the information with what % of the program collision detection and the overheads take. But I have to stop it, with over 20 pages for a 5-7 min presentation I'm already pushing to get all the information in.
Getting into the realm of slides full of recorded values.

Estimated speed up

2009-04-30T17:30:00.002+01:00

Applying Amdahl's Law to the outputs I got for the serial application altered to obtain maximum estimated speed up for the following number of processor cores:

Processors: 1 Speed Up: 1
Processors: 2 Speed Up: 1.081558752
Processors: 4 Speed Up: 1.127539093
Processors: 8 Speed Up: 1.152027177
Processors: 16 Speed Up: 1.164674475
Processors: 32 Speed Up: 1.171102833
Processors: 64 Speed Up: 1.174343696
Processors: 128 Speed Up: 1.175970864
Processors: 256 Speed Up: 1.176786139
Processors: 512 Speed Up: 1.177194201
Processors: 1024 Speed Up: 1.177398339
Processors: 2048 Speed Up: 1.177500434

Pretty much at most we get a speed up of 1.177 estimated on a huge number of processors meaning that the size of the problem domain will need to be expanded in order to exploit parallelism in order to achieve greater speed up.

Write up progress

2009-04-30T14:24:00.003+01:00

Currently I've mostly been collecting results and doing write up. So far with the final dissertation:

Abstract done (first draft)
Acknowledgements (adding as I remember something someone did)
Figure List(will be updated after each major draft)
Formula List (updating as I go final check after each major draft)
Introduction (50%ish probably needs entirely rewritten)
Lit Review (90%ish needs a conclusion in order to move into methodology)
Methodology (90%ish touch ups needed)
Results (40%ish, discussed all things effecting results, which results to benchmark and how they are used. Still needs metric reasoning, results tables and discussion)
Conclusion(0%)
Bibliography/Reference (10%, will do a final pass after each draft in order to update it)
Appendices (50% need to finish off both results appendices and add the collision helper appendix)

Apart from that the main thing to do is to collate the parallel and serial results and then find the benchmarks required. After that the next important thing is the presentation which I need to find out if it is a conclusive presentation or an overview of the entire project.

Again Noticed

2009-04-29T11:15:00.003+01:00

I just noticed that when I build the collision sets for the maximum range using the wrap around ability of the variable type that after a collision set has finished processing it does not reset this variable to allow the calculation of the maximum hash value.

It will probably have a trivial impact on the application however I must fix it, this means I'll need to retake the parallel metrics again to make sure, thankfully I hadn't started benchmarking just yet. Was planning to do it today thought.
Anyway its a minor edit that will just be needed for prosperity overall. So better go and record all the new variables.

Slice of time

2009-04-27T17:49:00.004+01:00

Time slicing keeps cropping up when talking about scalability, really need to add a bit about that to the lit review at this rate.

Currently decently through the presentation still need to get the parallel benchmarks in order to wrap that up.

Man thats not pretty

2009-04-27T15:31:00.002+01:00

I just collated the results from the parallel metrics and it goes like so:

Average Un-hashed objects:797.76
Average collision Tests: 15235.2
Average collisions: 69.765
Average hash table hits: 15245.3
Average hash table misses: 14476624.37
Effective Collision tests: 0.46%
Effective Hash Usage: 0.1%

Compared to the serial metric results:

Average bodies without BSP allocation: 1.01
Average collision Tests: 3400.67
Average collisions: 33.8
Effective Collision tests: 0.9%

Well overall in a collision set directly the parallel application finds more collisions but in the grand scheme of things performs far less useful tests. Additionally the serial application has a step up as it has all of the base object collisions.

More results

2009-04-27T11:35:00.003+01:00

I spent some of the weekend benchmarking the serial application.
I've taken three functions from it as part of the benchmarking:

Time spent traversing BSP nodes
Time spent processing object to bound collisions
Time spent processing object to object collisions
Total time the application spent in the actual program module (and not in some back end dll)

Because I had to estimate run times for all tests I'll have to convert all of the values to % of total run time and then average them.

For the parallel app:

Time spent in the parallel_for
Time spent layering to the hash table
Time spent reading back
Total time the application spent in the program module

Vtune is verrrrrry nice and all that but not being able to cut of a call graph test after a certain amount of time is annoying.

Apart from that I have all serial metrics and currently I'm finishing up taking the parallel ones (using 10 objects over a range in the hash table, gives a test time of ~5 mins instead of 5hrs ).

This week I need to finish:

Presentation
Methodology

I need to make a better start on:

Results
Introduction

Needs a conclusion:

Lit review

Final pass after all other documentation is finished:

References
Anything not referenced becomes a bibliography entry
Figure list
Formula list

Late on Friday I quickly sketched up most of an abstract which can be touched up later.

Parallel Application Super last ditch day

2009-04-24T14:53:00.005+01:00

Well it appears the rework of the parallel app is deadlocked somewhere.
As usual Visual Studio 2005 is totally useless at thread debugging so I can't really discern where the deadlock is. Highest possibility it is something to do with the object iterator.
A single iterator to the start of the list is passed into the initialisation of the collision helper, this single iterator is then copied to all of the working sets and each one stores it locally using the local iterator to increment through the list.
The amount to increment the iterator by is the current top level loop value. It hash to lock the iterator into a tight loop as I can't just add the total number of increments required onto it.
I could wait and then try and use Intel's thread checker at home (came with the Vtune trial) to see if I can find the problem using that. I had really planned to use his weekend for getting the serial benchmarks.

Ah here we go it seems like the Collision Set loop is tripping the size_t boundary and wrapping it round to 0. That makes more sense so I'll probably need to alter how the loop increments to stop that.

Parallel benchmarking

2009-04-23T19:22:00.003+01:00

I've thought a bit about the parallel benchmarking. After talking to my technical supervisor I could make a case that the application does not deliver the ability to render real time graphics thus benchmarking it will provide vastly differing results from the serial system.
Or there is another way to consider. Instead of performing the benchmark for all objects in the scene it may be possible to do collision for one object and then project for performing collision detection on all of them.

Apart from that I should have the AI coursework ready to be handed in soon clearing some time for maths revision.
Currently the methodology has been dragging on far too long I really need to finish that. While the methodology has been dragging I've started the results section along with the appendices and final presentation. Really need to start doing the poster session stuff and the presentation. Oh and I've got to print it and get it bound.....

Final CD List

2009-04-22T17:35:00.003+01:00

Better make a list of things and such that should be on the CD + printed out.

On the CD

Application logs (Serial & Parallel)
Results spreadsheets (Serial/Parallel metrics, Average results, benchmarking, hash key comparison)
Proposal Presentation
Modified TBB
Modified Vector class
Serial application
Collision library +tester
Parallel application
Hash key testers
Poster session documents
Serial and Parallel executable (with batch files to run them while logging, ++ TBB libraries for Parallel app)
Any research papers I can get my hands on
Dissertation
Separate Abstract
All Appendices

Printed

Dissertation
Front Page
Contents Page
Figure list
Formula list
Abstract
Introduction
Lit Review
Methodology
Results
Conclusion
Bibliography
References
Appendix 1 Original Proposal
Appendix 2 Hash Key Comparison
Appendix 3 TBB Alterations
Appendix 4 Collision Helper code
Appendix 5 Serial Results
Appendix 6 Parallel Results

Right think that about covers it.

I'll need 3 copies of the whole Dissertation (2 to the office one to hang onto) same for the CDs. The cost in printing is going to be insane if the printers are not out of paper, which is likely to happen bets I'll probably whack someone to get to a printer.

Serial Metrics

2009-04-22T17:08:00.002+01:00

I've just finished obtaining and collating the serial metrics:

20 Tests taking the first 100 frames of data:

Average Collisions Occurred: 33.83
Average Collision Tests: 3400.67
Average number of Objects Un-hashed: 1.01

Right now I need to get the averages by benchmarking each function over several tests. I'll do that tomorrow.

What did that do?

2009-04-22T15:43:00.002+01:00

The alterations to the program seem to make it run for even longer. Oh well it was worth a try.

One final alteration before I start to record results from the serial application:

Start the serial application with a BSP volume active

Easily done just grab the cameras start pos and move it slightly. Apart from that it means unless I spend a hell of a lot of time to record values from the parallel application I'll have to leave them as undefined. Means that the only metric I can get back from my parallel application will be un-hashed objects.

Grim Rework

2009-04-22T13:43:00.003+01:00

Actually reworking this is starting to look like its not going to happen. Again I'm having trouble with const variables.
This means that I cannot modify the iterators within the body of each chunk effectively killing any chance of alteration without altering some of the iterator STL types.
I'm going to keep trying until I need to go and eat after that I'll call it at this point it can be added as a further work problem. Because of this I will need to log from the parallel application without the collision function thus we will only get an estimated number of un-hashed objects.
All of the uses of the const type make sense it's just I'd like to do dangerous things with them. When the body of the parallel algorithm is initialised for all working sets it makes the body const meaning that manipulating anything without using new const constructed ver.

Switching the current chunk iterator to local has enabled this to go ahead still might fail horribly but even it it does at least I tried to fix it.

Inital VTune stuff

2009-04-21T14:29:00.004+01:00

Seeing as the serial application is basically finished(enable logging mode and we're set for getting additional benchmarks). I've spent the last while playing with VTune learning how it works.
Firstly a major note is the differing linker command /fixed:no if this isn't set VTune can only grab the call graphs for the other libraries
So after a quick look over a 120 second test:

TraverseNode comes out on top with 1,217,739 calls taking 123,520 micro seconds
Understandable considering that the application traverses to all root nodes per frame
This point is one of the first serial application overheads. Setting the BSP allocation does use the same function but will give a very small error ratio.

ext_RadialCollision is the next important function 174,00 calls taking 6,855 micro seconds

ext_AABBCollision is next 20,054 calls taking 713 micro seconds.

The lower number of AABB calls is because of how the BSP volume needs to be activated by the user, might change that so one of the BSP volumes is set as active should take barely any time because of how large each BSP volume is.
Ideally once there is an inital BSP voulme I can set the desired test time so I have an exact number on how long the application was benchmarked for.
Also the free trial came with the thread checker so I'll run the parallel application throught that and see what happens

Plumbing Orz

2009-04-21T12:34:00.002+01:00

Well we've had some plumbing problems with the flat downstairs so I probably won't get the chance to implement

the altered parallel algorithm today. Mostly because of my preference for not working at home.

Away way while I'm waiting for this to get fixed I suppose I'll crack open the Intel Vtune trial and do some more of the

final presentation.

On another note Google Chrome is useless at formatting blogger posts correctly

Parallel changes

2009-04-20T15:34:00.006+01:00

Alterations for the parallel application will be as follows:

Alteration from a size_t^size_t iteration space to ~3000^((max hash - min hash)/ Working set no)

One of the major goals is to parallelise the outer most loop (the reference objects) although this is not totally possible without using the simple partitioner and a grain size of 1 thus there will still be a loop all be it over a much smaller range.

Pseudo code for the following:

1. For top level range chunk (Range objects 0-3000) split by TBB

2. Add current loop variable onto passed in iterator (iterator non thread safe, iterator must point to the beginning of the object list and only be used to index the table)

3. Attempt to retrieve this reference object from the hash table, if it fails chalk up a hash miss

4. With this object const_accessor retrieved from the hash table perform object to bound collision

5. Set bound hit if collision occurs and increment successful collisions, increment number of overall collision tests regardless of success

6. Construct a range based on the hash value for the reference object (range min= ref hash value -((max hash - min hash)/ Working set no), range max = ref hash value + ((max hash - min hash)/ Working set no)) check for out of bounds problems at the same time

7. Attempt to get the test object at this hash value if no object try for the next one

8. Perform object to object collision

9. If object to object collision occurred release the test objects const_accessor and obtain accessor to this object.

10. With the accessor perform vector of separation on the test object

11. Get next test object

12. After the range has been iterate through check for object to bound and object to object collision. Perform collision response if needed

13. Next object in this work chunk

The justification for ((max hash - min hash)/ Working set no) is perhaps slightly hazy. Currently it is defined because of the smaller number of working sets the greater the chance of overlap being required. Using the overall hash range means that all objects within it can be encompassed. The other way would be ((max hash - min hash)/object number) dividing the range equally between all objects.

Sure it is still quite a number of iterations but it is significantly less (I hope) than size_t^size_t. Means I could still have a turn around of 5-10 mins per frame but its an improvement.

Any reduction in the time taken per frame is a plus.

Again the only problem with this is that any un-hashed objects will not undergo object to bound collision testing meaning it causes even more problems. Performing the collision on spec with a non thread safe resource (the iterators each working set will use to obtain reference objects) is far too dangerous at this point in the project thus will be left another acceptable loss described before the results section.

Loggers in

2009-04-20T13:48:00.005+01:00

I've just got both sets of loggers working on the serial and parallel application.
Serial application logs per frame values for:

Total Collisions occurred
Total Collision tests
Number of objects not allocated a BSP Volume (BSP allocation equals 0)

Parallel Application logs per "Frame":

Total Collisions occurred
Total Collision tests
Number of un-hashed objects
Number of times a hash look up was successful
Number of times a hash look up failed

Additionally all alterations to the serial application have been made meaning that effectively all that is needed is for the serial app to be benchmarked and the results logged from it.

So we have the following VS metrics:

Serial Collision time VS parallel collision time
Serial overhead time VS parallel overhead time
Objects w/o BSP allocation VS un-hashed objects
Parallel overhead critique based on hash look ups vs hash misses

Basically increased performance will be considered as:

Smaller collision time per frame with overheads having a bearing
Less objects missed by the storage containers the better
Greater hash hits than misses indicates successful implementation

Right I'm a gonna go have some lunch and then plan the parallel application rework. On another note I've had to alter what is considered an un-hashed object instead of checking the accessor is empty the return from the insert command is used. The application seemed to be producing larger hash misses than was possible because I was logging the wrong variable. This change makes certain that a object was not hashed.

Last ditch

2009-04-20T11:54:00.003+01:00

This week is mostly a last ditch attempt at trying to get the parallel application running somewhat close to real time graphics. Apart from that there are other tasks to be performed with the serial application:

To do:

Add Counter for number of collision tests performed
Add Counter for number of objects not allocated a BSP volume
Alter serial app render so it mirrors the parallel application
Add logger system to both the serial and parallel application
Finish up the methodology
AI Report at some point
More additions to the Appendices
Presentation + degree show poster
Benchmark and get results

Today I'm going to implement a number of the serial application alterations and plan the parallel rework. Firstly because last nights headache hasn't gone away and secondly because these are the major parts to allow lines to be drawn between each section of both applications.

For benchmarking I'll maybe run each application 20 times and collect at least 100 frames worth of data from each application (its going to be fun writing up it all into an excel spreadsheet). If the Parallel application still takes 20 mins to process all collisions after the alterations I'll take a single benchmark from it and argue that proper benchmarking and testing software would be required. By the end of this week the key thing is getting the results so I can package up the coding portion of this and focus on writing and doing maths revision.

Benchmarking

2009-04-16T15:22:00.003+01:00

Just had a quick conversation with my technical supervisor about benchmarking all the other metrics from the program. Problem is that they are time sensitive because of how the bodies in the scene are moved.
Best bet I've been told is to log all information to file. From that I'll run the application for a certain amount of time and then take the first 50 (or 10 which ever) and average those over that number of frames. Mention somewhere in the report as well that a proper tool would be used to benchmark these results correctly.
If I'm still looking at a 25 min parallel application per frame I'll take one result and call it as unworkable thus a threading failure.

So that's another task to add next week.

I remembered that break point this time

2009-04-15T12:52:00.004+01:00

Parallel Application start time: ~12:26
End time: ~12:51

So about 25 mins per frame.
Definitely not real time graphics, but it does mean I will be able to benchmark times less than 5hrs.

Some Time later, wait,wait did I forget something?

2009-04-14T18:18:00.003+01:00

Just to see how long it would take to iterate over unsigned int ^ unsigned int I decided to requisition another computer today and let the parallel application run putting a break point after the collision had finished. Well I forgot the break point so its been running for close to 6 hours now. Still it looked like not even a single frame had been rendered.
I'll try again tomorrow

Its gotta stop somewhere

2009-04-13T14:06:00.004+01:00

Just thinking I could record the number of objects in the serial application that have a null BSP node name. Would provide an exact comparison between that and the parallel model. But I have to stop adding metrics to compare the applications on. Really this is getting out of hand, provides a damn good comparison but still. I'm taking the advice given to me about being quantifiable pretty far.
So either way if I decide to alter my threading system or not I need to alter the rendering system of the serial application to model that of the parallel (alteration of the GLU objects) and add the number of collision tests. Along with the number of null BSP node objects. These fixes are minor and low risk.
With this I have a direct comparison with almost every aspect of both applications.

On another node I have to stop writing objects in my dissertation as that describes this application as an N body simulation, they are bodies not objects. Doesn't help that all my classes name them as objects. Either way at the end of writing I need to do a search through the entire document and stamp out calling any of the bodies objects. It means the same thing to me but for reader the semantic change will get confusing.

This week

2009-04-13T11:54:00.003+01:00

As I already stated in a previous post I am going to spent this week on the impending AI coursework. Most of the mornings (time dependant on when I actually wake up) will be devoted to writing more of the dissertation while the afternoons will be taken over by AI.

Depending on how the AI coursework goes this week will effect if I am to try and change the iteration space of my parallel application. Basically how demoralised and fraught am I going to be after getting the AI coursework working. If I can get it all done this week then I'll spend the first two days of next week altering the parallel application. If that fails I'm just going to crack open the V-tune trial and benchmark over several frames recording all of the data required.
That will wrap up the practical part of the project and then I can start producing the poster session/final presentation.

If I cannot change the parallel application then the other approach goes under further work. I should have enough metrics to make a worthwhile comparison. Conclusion might be lacking slightly but that's a trade off.

Parallel Application Week 4

2009-04-10T19:43:00.004+01:00

To do

Finish off the collision helper
Synchronisation implementation

Removed

Synchronisation implementation

Because of the way Intel TBB blocks while doing the parallel_for synchronisation is not needed.

Achieved

Finish off the collision helper

The collision helper is finished and currently runs using the parallel_for. The iteration space as already reported creates a size_t^size_t problem meaning the application is virtually unworkable.

Due to extern locations I've had to place the atomic variables in the main file to allow the collision helper instances increment them without much trouble. It means the headers are a bit all over the place but it works. With the current placement of all the atomic variables I can gain all of the metrics mentioned previously and would need to update the serial application in order to get the same.

Rework of the parallel routine

I briefly described another way to use the parallel routine which would use the non thread safe object list in order to use working sets this would mean that the top level loop for reference objects would be from 0-~3000 and then the lower level loop for test objects would be based on the hash ranges (basically a secondary grain size).

If time permits this would probably be a better application reducing the hash look ups and the number of iterations. It would also mean that the collision helper requires a iterator passed to it preloaded with the beginning of the list.

1.1 For range begin to range end (Object range 0-~3000)

1.2 Check this object exists in the hash table (ref object)

1.3 Do Object to Bound collision

1.4 Get the hash value of this object

1.5 Construct a max and min hash value range

1.6 For range begin to end (hash value range)

1.7 Find if this hash value exists in the table (test object)

1.8 perform object to object collision

So instead of a size_t^size_t space we're looking at a ~3000^(hash range/grain size)

Depending on how next week goes will really decide if this alteration will be made.

If not then the times for both overheads and collision will have to be listed as unknown as the current implementation currently takes over 20 minuets (I had to leave it after taking so long). From there I can break point to obtain some suitable metrics.

Either way I will probably need to make the rendering adjustments to how the serial application renders objects and record the number of collision tests.

Where to now?

2009-04-10T15:25:00.004+01:00

Currently the deadlocking problem seems to be fixed.
Now the only problem is the iteration range an insane 0 to a possible 4294967295. Combine the fact that for each working set I'm comparing each object with every other object meaning the application dies horribly. With ~3000 objects (some do not get hashed correctly) there are also a large number of hash misses in this iteration space. Thankfully the searches in the hash may use the hash key and some bitwise logic in order to cut down the search space to a smaller chunk.
With this there are still a massive number of hash misses. What is really needed is an ordered hash table effectively cutting out all of the hash misses and providing a direct ~3000 iteration space.
For this approach to maybe be worth it we a hell of a lot more cores in order to process all the working sets faster. Really shows that trying to avoid memory management of working sets is pointless.

So the ultimate question is do I stop programming here and collect benchmarks that I need or do I keep fighting with this current implementation which is probably flawed from the ground up?

Salvaging this implementation may be possible through the use of the object list.
It does mean manipulating a non thread safe resource that would not be modified in anyway.
Instead of using the hash key range we use the object range (0-~3000).
Each working set uses an object in this range and obtains the hash value for the object.
Depending on the working set size (or hash table range) we then search using this object as the center of the working set. This may reduce the exponential hash map misses.

Anyway I think I need to put up some dates and do some decisions.
Writing the dissertation: idealistically finish a week before the hand in or earlier
Poster session: Can be started around the same time as results/final presentation
Presentation: needs to start week of the 20th April
Results benchmarking: again needs to start the week 20th April

Most important and pending is the final presentation.

I'm taking next week off coding honour stuff in order to do the AI coursework. Hopefully I can get most of that done during this coming week. Apart from that the week beginning the 20th will see if I will bother to try and implement this alternate method. Its more than likely though I will just need to leave it and list the processing and over head times as undefined.
Still to do today is get all of the atomic counters in the right place and I doubt I'm going to have time to do synchronisation (But from the TBB implementation the parallel for blocks until done so synchronisation is in fact useless). The excuse that I didn't know exactly how some of TBBs templates and systems worked is really pathetic as an excuse. Still I need to back up my choice no matter how shallow it was.

Deadlocking

2009-04-10T14:11:00.004+01:00

One of the main reasons the application is using 99% of processing power is because the thread is deadlocking itself (seems the task manager has only allocated one thread) every time it attempts to obtain a read/write accessor to a object within the hash map.
I've quick fixed this by storing the hash values that are used when obtaining a read/write accessor and then releasing the read accessor for the object.

Makes sense why to disallow a read/write accessor until a read accessor is finished.
Anyway with that fixed the highest possibility is that the problem is now the memory thrash and the size of the range that I'm iterating over.

Let the Hilarity begin!

2009-04-10T12:27:00.005+01:00

Just started to try and use my parallel template (w/o synchronisation), well, according to the task manager 3 threads (one main, one render and one task manager I assume) churning the CPU at 99%. Oh yeah.

On the plus side it seems like memory is staying constant. Which means there may not be any memory leaks.

Additionally I've had a quick look at the task manager system, looks like I can set the number of threads, would be a good scalability test but that can be done later. Ideally the task manager should choose the number of available threads as to maximise the usage of all CPUs.

Anyway I'm going to have to add all of the counters and synchronisation. And then I'll play around with the grain size a bit and see what happens.
On another note it is not even hitting the break point I put in the main thread. Well this was expected so its not like I'm that devastated.

Also apparently part of the code is stuck in an infinite loop this would also explain the 99% CPU usage. Possibilities are I've deadlocked a thread somewhere. But because of the lack of standardised threading debug tools trying to use the standard VS2k5 debugger switches between threads from what I can see at the moment.

Needless to say: I Win!

Stuff compiles, no idea if it will work

2009-04-08T15:36:00.005+01:00

I just overrode the standard class definition for the = operator in my object class. Apparently I'm now able to perform the STD::Pair swap function with a < const Key, T > type.
This means that I can de-reference the const Key type to a new object, manipulate that object and then create a new pair. Finally swapping in the new pair. It compiles but because I'm still about half way through coding up the collision response I cannot test it just yet.
The main thing I'm not happy about is the additional memory allocation and destruction per frame but its the only way I can see to get around this without hacking up more of the template. With the additional memory alterations the application could also start memory leaking like an incontinent puppy.

I've had to override the = like so:

const Cobject& operator=(const Cobject &obj) const

and within the function body strip the const correctness from the object that the keyword "this" points to, using const_cast <Cobject* >() to perform this operation. Before altering all the values based on the address of a Cobject passed in.

From the amount of memory thrashing that the application will do per frame this is going to be crawling along compared to the serial version.

I Atomic

2009-04-07T18:28:00.006+01:00

Because I woke up late today and had other pressing matters to attend to I've only had time today to look at the thread synchronisation as well as some information about collecting metrics from threads.

So firstly I thought using mutexes in some way to control the synchronisation of the parallel application so that after rendering the main thread waits for the threaded system to finish processing before continuing.
Ideally some sort of mutex that allows multiple locks to be acquired and then the main thread continues if no locks are present on that mutex. The problem is that it needs to wait for N number of lock releases before continuing. The lock also has to yield to other processes if the lock cannot be obtained. The current plan is to make a call to the object manager when parallel collisions starts and that in turn will make the call to the collision helper using the parallel_for implementation within TBB.
With this I can do a pre collision test metrics reset and it also avoids having to make the collision manager model the parallel_for body concepts which would be a lot harder and more memory intensive (Basically would be using the Copy constructor to build several copies which would then destroy concurrency when one as destructed as it would try and destroy the master object list). Its currently uncertain which of the mutexes would be best to use.
With this problem another way might be to use an atomic variable that performs what seems like instantaneous actions on a possible shared variable. So when a thread starts processing a working set it increments an atomic variable and then decrements it when all processing is finished. The problem with that is the actual test in the main program, if two threads finish at the same time decrementing the atomic variable using -- notation (this basically blocks all access to the variable) meaning that if the main thread gets time sliced onto a processor and the atomic is tested then before the next thread receives the next working set then the program will continue and start the next frame.

Apart from this atomic variables declared as externs (have to check the program to make sure of no naming clashes) will be ideal to store all the metrics I need to get from all of the threads. Because the bodies of the parallel_for types do not need to model a join concept that would allow for a summation of local variables storing the required metrics. Still wondering if I should return direct atomic vars or dereference them to their actual values and return them. Dereferencing them would lower the proliferation in the program of the tbb atomic header files (to an already complex inclusion model here and there). On that note I'll probably need to go draw another inclusion and communication map and see how much crossover there is. Hopefully by the time I get out of here tonight I'll have an idea of what synchronisation method to use and can implement that.

There is still one underlying problem with my modifications to the hash table that could bring the entire project down in how the hash code is used in order to search for the underlying segment of the hash map:

my_segment[hashcode&(n_segment-1)];

My concern is what happens if I try doing a bitwise AND with a hashcode that doesn't exist on the hash map. But after looking at the definition it seems that segments are designed to hold a maximum amount of data thus anything from between the max and min will not cause any problems. Thus the segment return will be checked based if the node exists and as the altered functions cannot insert new nodes this will return a false value. However because the size of the segments is based upon a size_t value any other of template type T may cause problems.

Additionally since I'm not used to template coding I've just noticed in a few places I have made functions specific to my hash table implementation which will need fixed.

Thinking the second

2009-04-06T17:03:00.008+01:00

I've had another look at the TBB implementation. Currently from what I've just noticed in the header file the std::pairs returned from a hash key search do not contain the hash value of the object instead including the t value that is passed in which for inserting for anything but a STD:: is set to null. Meaning that I need to write another template so that the last value that will be passed into the STD::pair while storing will be the hash value.
New templates will look like so modeling from the standard TBB ones:

write accessor

bool insert( accessor& result, const Key& key, const T& t) {
return lookup</*INSERT*/ true>(&result, key, /*write=*/true, &t);

read accessor

bool insert( const_accessor& result, const Key& key, const T& t) {
return lookup</*INSERT*/ true>(&result, key, /*write=*/false, &t);
}

This will make each hash object return it's hash value as well and thus my edit of the find function (therefore the lookup and search_list function) will work as intended. I'm slightly miffed why the template doesn't do this inherently as the definition is that of type < const Key, T>. Currently in the code when a new node is allocated to the map it just sets the T type value to 0 no matter what and only the STD::pair input templates take in a second value. Just noticed as well that my previously changed functions do not conform to standard template style, so I'll change need to change them.

Because when an object to object collision occurs I need to be able to manipulate the direction and position I can not just simply sacrifice the second pair variable to store either of these. Additionally the hash value contained within the second variable needs to be set as the hash value otherwise I can not search the table via the hash key.

I still have the const problem when editing the actual objects that get returned and I have no idea how to get round this. Frankly if this doesn't get fixed that's it for the project.

Ultimatum
If by mid week I still can not figure out how to manipulate the values in those const accessors I'll put together a struct and have to totally mess up the edited search function by editing it so it is a fixed function (I'll need to include the struct def within the concurrent_hash_map template). By doing this I have a write able struct that I can perform complex manipulation on. The more I hack at the concurrent hash map definition the more likely a deadlock, race condition or other threading problem is likely to occur. Use of the template to reduce problems such as this was the main reason for using intel TBB over Boost. Might have been better using Boost but then concurrency would have become a large issue a with the internal locks not being present within the standard hash table.

Parallel Application Week 3

2009-04-03T16:25:00.004+01:00

To Do

Hash table read back
Object to Bound collisions
Object to object collisions in parallel
Synchronisation concept

Removed Tasks

Concurrency Implemented

Removed because the concurrent hash map will be used to control concurrency.

Achieved

Hash table read back
Collision helper implemented with object to bound collisions
Collisions helper with object to object collisions almost complete

Most of the collision helper that will be used to parallel process tasks has been created after having to hack up the concurrent_hash_map definitions so that there is a new find function that uses a hash key to obtain a writer or reader lock on an element in the map. Here's where the current problem comes in.

After upgrading from read only access to write access (using the accessors) so that I can start the vector of separation for one of the objects the write accessor only allows me to modify the second value of the STD::pair (the hash value) because the typedef within the accessor that contains defines the pair is:

typedef std::pair < const Cobject,size_t > value_type; (Taking into account the class type I'm hashing)

So there has to be some sort of conversion so that I can alter this standard pair otherwise I have no idea why it is worth acquiring a write lock to only be able to modify the hash value. Chances are I'm missing somthing what thought I'm unsure.

From attempts to modify the key using the STD:Pair swap function seems to have yielded the best results but I do not have an operator to handle a left value of const Cobject thus compilation fails. Soon as this is fixed theres the massive problem of actually debugging any thread errors. A perceived problem is upgrading an acessor to have write access while still retaining the read accessor from earlier.

Next Week

Finish off the collision helper along with a check for altering the directions
Synchronisation implementation

I'm really going to have to get synchronisation theorised next week and implemented, currently there's a chance that this application will be a week over the estimated deadline. This means the week starting the 13Th will probably be used to finish off the parallel application if it works.

From there the next two weeks will be spent on the AI coursework (due 1st May), application testing and writing the final presentation. Somewhere within all this I have to have my methodology and introduction written. By the start of May I should only have to write the analysis and conclusion. Oh and some maths revision has to happen.

TBB Hackup stage one aftermath

2009-04-02T17:22:00.004+01:00

Currently the new concurrent_hash_map template compiles cleanly (well mostly the same conversion warnings are there and they have been there since I started using it). Here's the current pseudo code for the section to be run over splittable ranges:

Iterate through the Min to Max hash keys for this range
Find an object to use for the reference object
Check that the object is exists in the const_accessor
Get all information required from the reference object
Perform collision test with the bounding area set a Boolean if a hit occurs
Iterate through the Min to Max hash keys again to find a test object
Check the const_accessor contains a test object
Check the ID of the reference and test object are not the same, if so release the test object and get the next one in the list
Get all information required for from the test object
Perform Object to Object collision setting a bool id a hit occurs
Perform vector of separation if a hit occurred obtaining a write accessor on the test object to set the new position
If a hit occurred increment the object to object hit counter
Check if either a collision between the object and bounds or object to object occurred (object to object if the object to object hit counter is greater than 0)
Depending on the collision that occurred obtain write accessors and invert the movement direction
Clear both Boolean hit variables
Iterate to test the reference object over the Max to Min range
Set object to object collision counter to 0 for next reference object
Get next reference object
Free up all accessors

Somewhat colossal at the moment.

Few Notes about this:

Directions must be inverted at the end of each iteration due because if they are not then there is the possibility of the direction being constantly flipped creating multiple collisions
Obtaining write accessors is minimised as much as possible and the time they are active is as small as possible to avoid the chance of threads spinning waiting to acquire an accessor to the same data location as the write accessor.
Currently no way to obtain the number of collisions that occur without some sort of atomic variable or other counter

Currently I'm in the middle of performing the vector of separation section, altering the value in the table using the write accessor seems to be causing some problems. Apart from that once this is somewhat working I need to look at the rehashing of objects based on a hash key, which will involve hacking up the template even more to bend it to my will.

Current foreseeable problems:

Collision accuracy with the working sets in this condition (crisp sets with no overlap)
Hashing objects based on a hash key
concurrent_hash_map may have a massive number of misses to find objects
Major problem with thrashing memory

If hashing objects based on a hash key is unworkable then it will be left, considered a viable concession and a number of the un-hashed object will be recorded.

Ideally for a decent conclusion and analysis I need the following metrics:

Serial Collision time (+time for BSP tree traversal)
Parallel Collision time (+time for hashing and read back)
Serial number of actual collisions VS number of tests
Parallel number of actual collisions VS number of tests
Parallel hash table hits/misses
Parallel number of objects not hashed (if applicable)

Both sets of time benchmarks will allow the Ahmdahl's and Gustafson's law comparisons and comments on why they either do meet the theorised times or do not meed the theorised times.

The number of actual collisions VS number of tests provides a throughput metric allowing clarification if times are very similar to be explained and considered.

The last two metrics allow further discussion and critique on the parallel implementation.

And with this I've got some control back over the project.

TBB Hackup

2009-04-02T15:04:00.005+01:00

I've started to hack up the concurrent_hash_map headers in order to shoehorn it into using the method I require. This is really where it gets complex so I'll list the changes:

Create two template functions that take in an acessor (const or normal) and a T type that call a specialist look up function
Rework Search_list so instead of checking for equal hash keys for two objects it uses the passed in T type and compares a the T type with a hashed value based on an object retrieved from a node list.
Alter the Look Up function so that it takes the hash value directly from the t input. All calls to this altered function will not attempt to add any nodes to the table.

This should take care of using a hash value to find an object within the hash map. The problem then is to create a function that will hash an object to a location based on a hash key. This will be needed to deal with objects possibly hashing to the same values.

Mostly what I'm really doing is reducing the re usability of most functions. The current templates use a number of state variables in order to utilise a single Loop Up function to do a large number of operations from finding objects to inserting them into the table.

I'm just about to insert the altered Loop Up function and compile, this should be somewhat fun.

Life would also be easier if performing any access to the intelisense database did not hang visual studio for about 5-10 mins each time.

Hash Map Range

2009-04-01T18:30:00.004+01:00

I've had a look at the single example that provides the same sort of method that I was planning to use here. Using this may fix the problem but because the hash map is unsorted this still may not be feasible to use.
If this will not work I'm going to have to ask on the forum for advice there is no other way I can see about getting access to the table via the max and min hash values.

Hacking things up

2009-04-01T16:33:00.003+01:00

I've had a quick attempt at implementing the apply a range over a body concept.
This has thrown up a few problems, most importantly I can not access the hash table directly with a hash value. Unless one of the public types contained in the concurrent_hash_map can perform the task I require, somehow a function needs written that will cut out the step based on hashing a Object into a size_t value and just do the look up based on the size_t value. The lookup function within the template would be best to override somehow as it takes one of the accessor (or const_accessors) and finds he object based on the hash key. But the find lookup function is internal and calculates a hash value before finding the object.

And I've still got to have a clear look at the task manager system that will allocate working sets to threads.

Without this access I've hit a brick wall, best thing I can think of is going and grabbing the associated book from the library if it has it and until 7:30 the catalogue system is down.

Noticed

2009-04-01T14:18:00.005+01:00

I've noticed that most of the time I'm not writing up anything in my notebook and simply charging into attempting to use TBB, which frankly is killing me. So based on what I have to do this week I'll quickly throw up a new to do list:

Collision helper class to model the pseudo-signatures for the Body concept
Object class modeling all of the copy constructable concepts
Working set thoughts with respect to extending the working sets to overlap
Object to bound collision
Synchronisation concept

Object class modeling

Currently the object class models three of the copy constructable concepts:

Copy constructor
Destructor (naturally)
Copy via taking address of an object

Currently it does not model one concept:

Const copy via taking the address off a const object

Collision class modeling

The collision class needs to model three concepts:

Copy constructor
Destructor
Apply body to range

Of these three the hardest to implement will be to apply the body to range. The copy constructor is basically the same idea as used for the object class.

It's possible that I can pre-load this class with the hash map and bounding volume metrics. Because of how this is all implemented with the copy constructors the collision helper can not delete either of these two objects, thus using a pointer approach would be best and only null the pointers at deconstruction of collision helper classes.

The other problem with this class is reading the number of collisions processed. Because all of these classes will be copied several times in order to create discreet working sets the problem about amalgamating all of the collision counts together as a parallel_for does not need the join concept modeled.

A possible way round it may be to use an atomic variable that can only incremented by one thread at a time but this is currently uncertain.

Working sets

The current problem with the working sets is the fact that it will be a range of hash values creating a large number of table look ups that do not return objects to test for collisions. This will go two fold as first a reference object needs to be found and then a test object needs to be found checking that it is not the same object.

As for extending the range this will cause more misses from the hash table increasing serial overhead time.

Frankly what is happening is that the UMA model I've proposed is falling prey to the fact that the PRAM system it is based off assumes no communication overhead whatsoever. So the communication overhead (memory access) will slowly grind the application to a halt. The problem then is what to do in this case, the threading methodology will work but at debatable performance due to memory consideration. It is possible that memory access overhead could be reduced by using the affinity partitoner within TBB in order to preserve cache concurrency speeding up any accesses to main memory.

Synchronisation

Ideally some sort of mutex that would wait until a certain number of attempts to aquire it have been made the problem is the location of the synchronisation concept in relation to the rendering functions. An approach might be to make the mutex within the object manager that would block until the conditions have been met.

Currently the estimated synchronisation point is after the the frame limited draw section. It may in fact be better to alter it so that the program blocks before the next game loop starts so that windows can process messages while the collision is finishing up. The change would look like so:

Wait for mutex to be acquired
Read back from hash table
Perform time based movement
Hash all objects to the table
Start collision testing
Render
Swap Frame buffers

The only problem with this is for the first frame the mutex would have to be pre-acquired otherwise the program would block and not continue.

Addendum

I've also just had my first set of hash collisions (two objects hashing to the same value) which will NEED to be handled by either adding them to a hash value above or below the hash collision point.

Copy Constructable

2009-03-31T16:28:00.005+01:00

I think I've almost got the copy constructable concept down, of course if the code I've got is working correctly is an entirely different matter.
The only pseudo-signature I'm having trouble with now is:

const T* operator&() const Take address of const T

using the this keyword seems problematic meaning I can't do any assignments like:
const Cobject *tempobj = new Cobject(obj); //where obj the address using the copy constructor

this=tempobj;

which would be like the non const version of this signature. The next thing is to build a class which will perform all of the collisions and model the Body concept provided by TBB.

Additionally there is another problem with the grain size using the number of objects is pointless as the table is not sorted. This means that the range of all objects iterated over will have to be:

Max hash key - Min hash key

Meaning that the grain size will also change. Additionally to address the lack of working set overlap adding a certain % of the total range to the maximum and minimum (to a absolute minimum of 0) in order to increase the range is also possible. This should reduce collision misses hopefully.

The problem with this approach is its possible that there will be a stupidly high number of hash map accesses most of them which may return no results as we iterate from the lower end of the range to the top end.
To a degree the threading approach is falling apart majorly due to a mix of uncertainty about how the library works and oversight. Already with the reading to and from the parallel hash map slows the application significantly. As well with the amount of memory allocation and destruction that is being done per frame as soon as the collision helper is implemented the application will simply grind to a halt. Each object needs to be rehashed per frame in order to preserve the spatial locality for each object.
If this application is completed there is a high chance there will be no time for optimisation of any kind due to the amount of time it is taking me to model concepts that are required.

Additionally its still uncertain about how the threading system will be synchronised with the main application thread.

Leakage

2009-03-30T17:35:00.005+01:00

After somehow managing to model the basic Copy Constructor method the hash map quickly jumped on this and started using it causing a memory leak where GLU quadratic objects are used but not destroyed (was mainly because the appropriate OpenGL function was not used but became more noticeable then).
Deleting the GLU object in the destructor using the appropriate OpenGL function causes stack corruption because its possible that the object was copied from another causing more problems. Thus copy constructable objects cannot have the model pointer handled to them. Another fix might be to indicate internally that the object is a copy and thus skip erasing the GLU object.

Currently if the object is created with the copy constructable method then the GLU pointer is nulled. Of course this may cascade into the list implementation and I'll definitely need to indicate if objects are copies or not.

At the moment the current problem is an illegal indirection on the list iterator which will need to be looked at. After this the objects will read back the position and direction of their object in the hash map as replacing the entire class with the hash map one erases the pointer to the object.

Either way this is really the first time I actually fixed a memory leak instead of just panicking and hitting rebuild all hoping the problem will go away.

Edit:
Because of the current problems with the copy constructable and the stack frame I will need to abstract the representitive object to the Object Manager in order to preserve the stack frame for each copied object. Effectively Object classes will become empty shells but this will also lower memory usage slightly.
The modularity of my code is also coming into question.

Shooting off Target

2009-03-30T14:56:00.003+01:00

If what I've theorised about how TBB splits working sets using the range concepts it is highly possible that spatially close objects will be separated from each other. Thus they will not be collision tested.
This causes a problem in that collisions could be missed because working sets for threads do not overlap. A fix to this might be when splitting a working set to add a certain amount of the grain size to the maximum and subtract the same value from the minimum.
This would be quite a hack increasing the chance that threads would try and access the same elements of the hash table but would provide a more accurate result.

Parallel Application week 2

2009-03-27T17:05:00.005Z

To Do List

Parallel hash table implemented with objects being placed in the table pre-graphics frame and then read back after being collision tested at the end of the frame possibly before rendering or after depending on the synchronisation method chosen
Working set system implemented if applicable
Object to bound collision implemented in parallel.

Overflow tasks

Hash table key theorised
Initial synchronisation concept
Working set initial thoughts

Removed tasks

Decide what level to add the copyable and splittable constructors to the Object manager (possible copyable at the object level and Splittable at the object manager level)
Change the level of collision detection response so instead of the object manager calling a single function and iterating through testing all the objects, the collision test function then funnels sets of objects down into a function that will call the collision routine

It is now known that the helper and object classes will need to model the concepts defined by TBB. And with the level of collision detection response the functions do not need changed simply altering the current functions to indicate they are serial is more than enough.

Achieved

Hash table key theorised (First choice Key: ((X ^ ID)+(Y ^ ~ID) + (Z ^ ID))=Hash key int) Signed/unsigned problems may become apparent
Objects layered into a hash table but not read back yet.
Working set initial thoughts

Currently there are some major problems with the concurrent hash table definition that are throwing warnings from the template library. Because of these reasons I can only speculate that objects are being hashes correctly based on the fact that the accessor is never empty after hashing an object. The only reason I can think of is that currently the object class does not model the copy constructable concept and because of the use of pseudo-signatures I'm really no closer to understanding how to implement the concept correctly. The example using the concurrent hash map hashes strings to ints so I have to assume that the STL string class models the copy constructable concept.

With the working sets from what I can make out of TBB is that after giving it a fixed range (max hash key no to min hash key no) it will split the range until it is less than or the same size as the grain size. Then a thread pool approach will be used to assign tasks to a number of worker threads. This means that the grain size is important thus with a problem domain of 3000 objects:

Grain size 3000 gives 1 working set
Grain size 1500 gives 2 working sets
Grain size 750 gives 4 working sets

That is if I correctly understand the concepts explained by the TBB documentation and additionally it recommends that there are more working sets than threads. Because of this with the assumed one thread per physical CPU for the lab computers a grain size of 750 would be ideal.

The current big glaring problem is that objects in one working set cannot overlap with any from another at the moment if splitting the problem domain to the working set as I understand.

Overflow into next week

Reading back from the hash table once fixed
Object to bound collision
Synchronisation concept

Adding object to bound collisions seems like it should be quite easy in that before each reference object undergoes testing it will be tested once for collision with the boundaries.

Next Weeks Tasks

Concurrency implemented
Object to Object Collisions in parallel
Debugging

Concurrency is forced via the shared concurrent hash map currently.

Write up status

Currently I've got the first draft of my literature review off to my technical supervisor for checking and within the next week I should have started the methodology section.

Refined hash key

2009-03-26T17:49:00.005Z

I just integrated the object manager into the hash key tester and reran the key for all the objects within a single object manager. And then counted the duplicates the same way. Before the hash key is calculated objects are moved using a delta T value of 3.0f.

IDs from 1-3000
X,Y,Z position as ((-BOUNDSSIZE/2)+(rand()%(int)BOUNDSSIZE))

Thus I need to recheck the hash key metrics from the last post using actual values that could turn up in the program.

((X ^ ID)+(Y ^ ~ID) + (Z & ID))=Hash key int

Real World Duplicates: 7290

((X ^ ID)+(Y ^ ~ID) + (Z ^ ID))=Hash key int

Real World Duplicates: 1020

((X ^ ID)+(Y ~ID) + (Z & ID))=Hash key int (Y value is bitwise ORed with the Inverted ID)

Real World Duplicates: 6194

((X ^ ID)+(Y ~ID) + (Z & ~ID))=Hash key int (Y value is bitwise ORed with the Inverted ID)

Real World Duplicates: 5636

((X ^ ~ID)+(Y ~ID) + (Z & ~ID))=Hash key int (Y value is bitwise ORed with the Inverted ID)

Real World Duplicates: 5674

((X ^ ID)-(Y ~ID) + (Z & ~ID))=Hash key int (Y value is bitwise ORed with the Inverted ID)

Real World Duplicates: 7844

((X ^ ID)+(Y ~ID) -(Z & ~ID))=Hash key int (Y value is bitwise ORed with the Inverted ID)

Real World Duplicates: 7822

(((X ^ ID) ^ (Y ~ID) )-(Z & ~ID))=Hash key int (Y value is bitwise ORed with the Inverted ID)

Real World Duplicates: 12548

(((X ^ ID) ^ (Y ~ID) ) ^ (Z & ~ID))=Hash key int (Y value is bitwise ORed with the Inverted ID)

Real World Duplicates: 19150

(((X ^ ID) + ~(Y ~ID) ) + (Z & ~ID))=Hash key int (Y value is bitwise ORed with the Inverted ID)

Real World Duplicates: 7844

From the new estimates using real values that the program could possibly have now:

((X ^ ID)+(Y ^ ~ID) + (Z ^ ID))=Hash key int

Seems like the key that will produce the lowest number of duplicate hashes.

Hash key a result

2009-03-26T13:28:00.012Z

Simply created, counted using a nested loop discarding any comparisons with the object itself (means duplicates will occasionally be already counted, IE object ID 1 having the same hash as object ID 300 will count one as well as the reverse comparison).
3000 Hashed objects each time. Does not take into account fixing duplicate keys. Because of this there will be some quite high numbers but because all are counted a lower duplicates number indicates a more unique hash. If theres somthing wrong somwhere please say.

defining X, Y, Z as (-1/2 bound size + rand()%bound size)>>1)

((X ^ ID)+(Y ^ ~ID) + (Z & ID))=Hash key int

Duplicates: 2844

((X ^ ID)+(Y ^ ~ID) + (Z ^ ID))=Hash key int

Duplicates: 3018

((X ^ ID)+(Y ~ID) + (Z & ID))=Hash key int (Y value is bitwise ORed with the Inverted ID)

Duplicates: 239176

((X ^ ID)+(Y ~ID) + (Z & ~ID))=Hash key int (Y value is bitwise ORed with the Inverted ID)

Duplicates: 1414

((X ^ ~ID)+(Y ~ID) + (Z & ~ID))=Hash key int (Y value is bitwise ORed with the Inverted ID)

Duplicates: 20124

((X ^ ID)-(Y ~ID) + (Z & ~ID))=Hash key int (Y value is bitwise ORed with the Inverted ID)

Duplicates: 1724

((X ^ ID)+(Y ~ID) -(Z & ~ID))=Hash key int (Y value is bitwise ORed with the Inverted ID)

Duplicates: 235230

(((X ^ ID) ^ (Y ~ID) )-(Z & ~ID))=Hash key int (Y value is bitwise ORed with the Inverted ID)

Duplicates: 1630

(((X ^ ID) ^ (Y ~ID) ) ^ (Z & ~ID))=Hash key int (Y value is bitwise ORed with the Inverted ID)

Duplicates: 301560

(((X ^ ID) + ~(Y ~ID) ) + (Z & ~ID))=Hash key int (Y value is bitwise ORed with the Inverted ID)

Duplicates: 1724

Current Best bet:

((X ^ ID)+(Y ~ID) + (Z & ~ID))=Hash key int (Y value is bitwise ORed with the Inverted ID)

Duplicates: 1414

Additional
I'm also currently considering changing the recorded collision numbers from number of collisions occurred to number of collisions tested.
It would be ideal have both to give a hit/miss ratio for both applications.

Hash keyed?

2009-03-26T13:01:00.003Z

New Idea for the hash key:

((X ^ ID)+(Y ^ ~ID) + (Z & ID))=Hash key int (or unsigned int)

For samples where X,Y & Z equal 5
With sample IDs of: 30, 128 & 200

Object ID 30 Hashes to 257
Object ID 128 Hashes to 255
Object ID 200 Hashes to 255 (will be handled and incremented to 256)

I'll build a quick test application that hashes objects ID from 1 to 3000 at random positions and check the output.

Apart from that I'm currently having trouble with the TBB libraries its currently throwing a warning about a conversion from size_t to unsigned int which is problematic but the only explanation I can find is either something in one of the other names spaces is overwriting the TBB definition of size_t or really I have no idea of how the templates work.
At this rate it is going to be hard enough making the Objects and the collision helper class model the Pseudo signatures without the template library throwing warnings.

Currently it seems to work but its possible that due to the conversion warning that memory is either being allocated (all the warnings are library internal with the table memory allocation) incorrectly which might cause a memory leak or some more interesting undefined behaviour.

Pesduo-Signatures Crash course

2009-03-24T15:32:00.012Z

Apart from learning what Pseudo-Signatures are when it comes to using template libraries I've had another think about the hash key to be used for the parallel application.

Fourth Iteration:

((X+Y+Z)<<ID) | Object Memory Location = Hash key int

Well this was totally out there in terms of thought and planning and it could really give some crazy numbers.

Fifth Iteration:

(X+Y+Z) ^ ID = Hash key int

Using bitwise logic may provide a better number of keys with each ID being unchanging and object unique.

But still perhaps using an XOR may not be best as the following values were found for considering the hash key as a 16 bit int:

Object positions (X+Y+Z)=12

Object IDs: 3000, 1758 (Maximum value and random value)

Object 3000 hashes to 2996

Object 1758 hashes to 978

This means that the working set range for the parallel hash table might be huge but the bitwise operation seems to provide better values perhaps an AND may give better results. Inverting either of the values would possibly give a large number.

Perhaps part of the problem is that I constantly consider X+Y+Z as a single entity and might need to perform a bitwise operator on them before adding or subtracting them from each other.

Apart from the problems with this I've started implementing the parallel hash table into the object manager first of all creating the structure that describes how to hash objects to int keys and key comparisons.

Current Template for the hash map:

typedef tbb::concurrent_hash_map < cobject,int,colhashkey> CollisionHashMap;

In order to obtain the total range that the hash map spans as objects are layered into the table it is possibly to record the maximum and minimum has values which can then be passed onto TBB as the maximums and minimums of the overall blocked range.

From what I can understand now the blocked range will be split until it mirrors the grain size set for the application meaning that starting at the lower end of a split range and iterating towards the end of the range would provide a working set without defining the middle of the working set. the problem then is defining the grain size. Chances are that TBB works on the one thread per physical CPU theory meaning that with this example a 1500 grain size will split the problem domain directly in two. As the TBB documentation says thought to play around with the grain size in order to find whats correct for your application.

The next major problem after defining the hash key is to model a collision function that will embody all the concepts for a parallel for template.

For now I'm going to try and finish more of the literature review as usual its dragging on and on.

Week 1 Update

2009-03-20T17:25:00.004Z

Done so Far:

Hash key basic theorising
Concurrency theorising
Serial Application strip down

Still needing done:

Working set initial thoughts
Synchronisation initial concept
Adding copy and split constructors to the serial application classes
Changing the level of collision detection response (Possibly not needed)

Hash key

Looking at the hash key yesterday threw up some major problems where several objects could hash to the same value, this really needs some more thought into it before starting to implement seriously.

Concurrency

Because of the differing types of accessors that are used to access the parallel hash table it is possible to start off using a read only accessor and then escalate it to that of a read and write accessor. With the read and write accessor it means that any other thread trying to access that element of the table will be blocked.

Serial application strip down

Removed the BSP system and altered the Object Manager collision calls to indicate that they are serial.

Working set initial thoughts

If all of the objects can be hashed uniquely into the parallel hash table then a centre of a working set can be chosen and given a range over which to test objects with spatial locality to the centre. The problem is then the number of working sets and how to chose the centre of the working set. With 3000 objects layered into the hash table there is the additional problem for making sure each of them is collision tested.

Synchronisation initial concept

Realistically for benchmarking the application will need to run in Lock Step so that at the end of a graphical frame the system waits for the collision system to finish parallel processing all of the working sets. This could be achieved using a lock or semaphore of some sort and the main thread would wait until it has been signaled in order to read back information from the parallel hash table ready for the next frame.

Copy and Splittable constructors

Currently it could be likely that these are not needed to be implemented within any of the existing classes instead they would be applied to a helper class that would process a working set of course this is thinking in a purely serial manner thus may not be effective.

No matter what a few of these initial theories will continue over into week 2.

Hash Keys

2009-03-19T18:13:00.007Z

I just attempted to build the hash key for the parallel hash table, based on objects position in 3D space.
Initial Thought:

(X+Y+Z)=Hash key int

Problems:

Negative values may also give the same hash values as positive ones
Possibility that different combinations give the same hash value
Possible round up errors

Second Iteration:

(X+Y+Z)/ID=Hash key int

Problems:

Gives a float value that is extremely small
Would need to bit shift significantly to find a working integer

Third Iteration:

(X+Y+Z)*ID=Hash key int

Problems:

Same as the first iteration just the numbers come out bigger

So from there this seems like it may take a lot more time to find a unique hash key and because of how uniform all of the objects are the Position and ID are about the only two things that are unique to an object and each object has.

Additional ideas could be to use the address of the pointer to the GLU object that represents the object or the time that the hashing action occurred.

Either way this has the possibility of dragging on far longer and causing all sorts of problems if I don't seek some advice on the subject. As well as this having the possibility to delay things greatly and combined with the estimated problems obtaining concurrency its possible that the application will have to make an accuracy concession.

Parallel Application start

2009-03-17T16:38:00.003Z

Currently I've just stripped out all of the BSP system and renamed the collision methods to indicate that they are serial.

Its still slightly uncertain if the object and object manager classes will need to be converted to accommodate some of the TBB concepts. But if not then its possible that a few helper classes could be created in order to be used by the task scheduler included in TBB.
From the initial concept it collision would be performed like so:

Pre collision test
Layer Objects into parallel hash table using hashing function
Split number to obtain a number of blocked ranges (basically the number of working sets)
Select the centre of each working set (in a linear hash table objects spatially close to each other will be layered on either side of a central object)
Load blocked ranges and working set centres into parallel processing instances
Process in parallel
Read back from the parallel hash table into each object (due to memory accesses and how objects are stored this may not be required as object may still be linked back into the linked list, if the read back takes far too much time it may be feasible to force using the addresses in memory)

If each object had no effect on any other then it would be feasible to choose working sets and split them arbitrarily but because of this we need to control how they are split and where the data starts for each this brings in the following problems:

Culling collision numbers via spatial locality in a different way as this may deviate from the proposal to process all collisions but may still be feasible because of the greater thread throughput.
Concurrency on the parallel hash table
Splitting the object manager or the object manager containing a number of splittable collision processing classes?

So far the only one that can be answered at this time is hash table concurrency.

Access to a parallel hash table requires an accessor of which there are two types:

accessor
const_accessor

The accessor type defines an access into the hash table that locks that element so that no other table look up can access that element blocking until the accessor has finished, basically giving write access to the table. The const_accessor however only represents read access from the table so if you consider the serial object to object function you can set read only access until you require to write to data.

Get const_accessors to both the test and reference object
Perform collision test
Collision occurs
Obtain accessors to test and reference object
Perform collision response
release both accessors
release test object accessor
repeat over blocked range

So its possible that the hash table itself will force concurrency over the reading and writing meaning the code is not lock free but it definitely will be minimised.

So from there the only explicit locking may be that to synchronise the collision threads with the main application.

Parallel Application

2009-03-13T18:28:00.002Z

Firstly with the parallel application it seems to be a functional parallelism approach as only the collision testing will be paralleled. Only separating the collision detection from the main application thread will mean that the collision detection is still processes serially giving little increase in performance. If collisions were still being culled based on the BSP volume that they are in then its possible that this would provide far better performance but for the parallel application all collisions will be processed in order to provide a more accurate simulation. With this functional parallelism model processing a possible n^(n-1) collisions in a serial manner is the problem so it would be ideal to break down the collision function thread into a smaller granularity data driven model.

From this the problem is then splitting each object that collides between the worker threads. With the serial application the BSP system culls collisions that the camera cannot theoretically see (for all intents an purpose the serial application is only estimating a possible splitting of level geometry) yet if we consider the fact that a set of objects cannot collide with others on the opposite side of the room then their spatial locality could be used to construct working sets of objects. With this there is the possibility for overlap between working sets, the other problem is with the number of working sets if we have 200 objects then can we feasibly have 200 working sets, more likely than not that will not be possible and overlap between the working sets may be quite high. Using the idea of spatial locality in order to define working sets means the less working sets the greater the size of each set in order to make sure all objects are collision tested.

With these working sets each worker thread can test each object for collision with the bounding area before testing the object with all of the other objects.
The problem then is concurrency between overlapping objects in working sets and synchronisation with the main game thread.

Initial Plan
With this in mind its possible to estimate that using a parallel read serial write hash table keyed with the spatial locality could be used to store all the objects pre-collision tests. From there a parallel for loop that operates over a blocked range of the hash table can be used to process all collisions based on a central object of the working set. Because of the hash table objects that are spatially close to each other will be estimated near each other in a linear hash table (current thought may need to be changed depending on the key calculation).

Parallel Application main sections

Stripping down the serial application, removing the BSP system
Converting the classes within the program to be compatible with the TBB splittable and copyable concepts
Threading system
Working set creation
Synchronisation with the main application thread (mostly likely will run in lock step)
Concurrency

Again this application development is expected to last at least four weeks leaving two weeks at the end of April to write the dissertation and in the last week of April finish up the AGT AI coursework.

Week 1

Serial application strip down
Decide what level to add the copyable and splittable constructors to the Object manager (possible copyable at the object level and Splittable at the object manager level)
Initial Concurrency concept
Initial synchronisation concept
Working set initial thoughts
Hash table key theorised
Change the level of collision detection response so instead of the object manager calling a single function and iterating through testing all the objects, the collision test function then funnels sets of objects down into a function that will call the collision routine

Week 2

Parallel hash table implemented with objects being placed in the table pre-graphics frame and then read back after being collision tested at the end of the frame possibly before rendering or after depending on the synchronisation method chosen
Working set system implemented if applicable
Object to bound collision implemented in parallel.

Week 3

Concurrency implemented
Object to Object Collisions in parallel
Debugging

Week 4

Synchronisation with the main thread
Debugging

Literature review

Currently the literature review is still running on as I'm lacking a few bits of information on current implementations. After finishing up discussing the current generation of consoles hardware, it will move onto multi threaded pc software considering game engines as the main source of threaded software. After that the analyses of past parallel collision projects and proof of the comparison will be done.

Serial Application Final Concession

2009-03-13T15:42:00.002Z

I've more or less just fixed the frame limiter of the serial application so it is serviceable but not fully accurate (timeGetTime() vs queryPerformanceCounter()).
The last concession is that the collision with objects and the bounding volume will not use the vector of separation method meaning that when the application starts a number of objects will be in constant collision with the bounding volume. A major part of the application is culling complex collisions in order to speed up the application the simple collisions will have little effect on the final performance and were going to be used as a benchmark. Additionally moving the objects using the time between frames is more important for the parallel application as the main game thread will be separate from the collision threads.
With this concession the parallel application can begin next week. I should have a plan for that by the end of today but current projections are to have the parallel application finished by mid April.

Whats left of this weeks to do list

2009-03-11T17:21:00.005Z

To Do

Get the vector of separation in for the Object to bounding volume
Get the graphics frame limiter working
Finish literature review first draft

I'm more or less going to call the AABB collision working ok now that the reference object is centred around the origin and the test object translated to compliment.

Current problems with the frame limiter is mostly with the logic and where to put the last frame time.

Lowering the speed as recommended by my technical supervisor has removed some of the problems of Objects overshooting the collision with the bounding volume and then being stuck in collision limbo. But still if for some reason the applications slows to a crawl because of another system process then its possible everything will end up outside of the bounding volume.

Apart from that one problem it may be worth while even if only the graphics frame limiter to works to use this application and take note that its possible collision numbers reported onto the screen will be offset slightly.

On another note I've been reading this article

Limiters

2009-03-11T12:40:00.005Z

Today I've been messing around with limiters to limit the number of graphical frames.

Currently limiting the number of graphical frames is like so:

1.1 Time difference = Current Time - Time the last frame started
1.2 if Time difference < (MAX FPS X 1000)
1.3 render
1.4 else update last frame time

Currently it seems the else is never hit so there's a chance that its not actually limiting the frame properly and current editing of the if statement is causing the application to try and force a frame to be rendered in a small amount of time. So this will need looked at.

This brings three different concepts of frames:

Graphics Frame: how long it takes to render the applications 3D graphics and associated functions, begins before rendering and ends after the frame buffers have been swapped.
Processing Frame: each processing frame is defined as when the application has no windows messages to process thus performs all of the main application code.
Physics Update: how long it takes for an entire windows message loop starting after the previous update and having delta T calculated before the next call.

Currently Limited by the Graphics Frame limiter

Resetting the number of collisions
Collision testing
Updating on screen metrics every 10 graphics frames
Graphics

Currently Limited by the time it takes for a single processing frame

Movement updates based on a delta T value

Unlimited

Camera Control
BSP allocation, because the movement is based on time and will always update each processing frame the BSP allocations need to be updated constantly

After the frame limiters the main problem is the collision response and the AABB algorithm uncertainty.

Currently collision response for object to object collision is that of the previous post although I'm wondering if the separation vector from the reference object to the test object should be normalised and then scaled by both the half widths of both objects (basically the width of one object). Currently with the metrics update it seems that when the a BSP area is activated the number of object to object collisions constantly rise.

The problem is then getting the vector of retraction (if that's the right word) for the bounding volume and objects. I've worked out a couple of different ways to do this but none of them have provided working results when applied to a 3D vector.

Initial Object to Object separation better explained:

Find the vector between the centres of the object and bounding area:

Separation vect = O(Reference) - O(Test) (Vector subtraction)

For a collision:

Length of Separation vect < (O(Reference) radius + O(Test) radius)

Here's the uncertain point should the Separation vect be normalised before being multiplied by the (O(Reference) radius + O(Test) radius) so it scales properly?

Then as already stated:

Move to Separate = Separation vect X (O(Reference) radius + O(Test) radius)

Then as the first object is the Reference we move the Test object by:

Test object centre + Move to Separate

This will move the test object to a maximum boundary so it is possible that when the Test object becomes the Reference object another collision will occur.

Perhaps the problem is that instead of moving the centre by the Move to Separate vector it should be the inverted direction vector that is moved along (remember basic collision response was to invert the direction vector). The separation vector may not necessarily be the same as the direction vector yet it will guarantee that the objects no not overlap on any axis.

But anyway the next problem is the separation of objects with the limits of the bounding volume.

If you apply most of the Object to Object collisions with the exception of instead of multiplying by (O(Reference) radius + O(Test) radius) you multiply by

1/ (Bound Radius - Object Radius)

Basically we're trying to get:

Length of Separation vect < (Bound Radius - Object Radius)

So this provides the idea that:

Bound Radius in the X axis- Object Radius in the X axis

Bound Radius in the Y axis- Object Radius in the Y axis

Bound Radius in the Z axis- Object Radius in the Z axis

Gives a vector multiplication along which to scale a normalised vector of separation.

Normalising the vector of separation gives the direction in which to move the object to bring it back inside the bounding area.

The problem with this method is that is scales positions that are within the bounds meaning that the object will not be in a position that could have been along the movement direction. This differing approach is due to the fact that a point on the extremity of the bounding box is unknown and some complex logic might be required in order to discern along which axis the object has exceeded the bound maximum.

Needless to say I'm currently quite confused.

Delta T

2009-03-10T12:37:00.011Z

I've pretty much been putting off calling the serial application done mostly due to the uncertainty about the validity of the AABB algorithm but really I cannot afford much more time messing around with this. The only justification for this procrastination is that the serial application is the base of the parallel application but after looking at the TBB documentation its clear that I could simply shift into using the inherent timing functions.

The current thing that I want to know from TBB is if I can when using the task manager and templates get the actual number of working threads, would be nice to be able to see the number of collision threads to proof the scaling of the system.

One of the main problems if the limiting of the movement updates which has been discussed a small amount with my tech supervisor, one approach would be to multiply the movement speed by a delta T value that is calculated from the current time - start of the previous frame.

Pseudo code looks something like this:

1.1 Calculate delta T current time -previous frame start time

1.2 Move based on delta T

1.3 Update the previous frame start time

This means that a single frame for the physics system would start after the movement has been performed while a graphics frame would start after the pre-frame movement and collision has been done, its uncertain if this would cause any problems apart from the slight increase in complexity. When the frame rate is limited when the maximum number of frames per second is reached the frame time for a physics update will be small and thus move the objects appropriately.

Because of the movement change the collision response will also need altered to encompass the vector of separation in order to move the two colliding object apart (note to self need a reference for this).

Basically during the collision detection response the vector of separation would be found using the centre of both objects and then move the object by this vector scaled by the minimum length that allows the objects to not collide and then add it to the position of object 2 as object 1 is translated the reference object.

Thus:

Vector of Separation * Minimum Length in order for objects to not collide = Move vector

and then

Object 2 Position + Move Vector

Performing the vector of separation on the object to bounding area collision may be slightly different as care must be taken not to move the object outside the bounding area. Of course this may automatically correct itself within a few frames but it is something that needs looked into.

Current Example of moving by delta T movement where 500 objects are moving at 96 world units per second:

Each of the objects outside the bounding area are simply vibrating back and forward because of the inadequate collision response. If this doesn't work I can roll back to the previous version backed up today. The start of next week would be the best time to have a final verdict.

Notes if I roll back to the previous version:

Stack overflow problem with the BSP system if the area to be split is less than the minimum area. BSP termination was based upon == when it should be <=
Additional comments for the block of temp variables used for updating the screen metrics and timers

Extra

If the collision system is not fixed to use the vector of separation then the averaged amount over 10 frames will always be quite high as collisions are sampled each time the windows message loop has nothing to process.

Serial Application Finale?

2009-03-05T14:25:00.006Z

Serial Application Main Sections

Object system
BSP System
Collision
Graphics System
Camera Control

Object system achieved

Basic object Storage Including position, Direction, Colour, ID and BSP allocation volume
Each object has its own pointer to a GLU Quadratic
Object controller system encapsulating all objects in the scenes within a linked list
Object controller controls all Object movement
Object controller performs collision detection with the bounding volume
Object controller system performs the rendering of all objects
AABB collision between Objects
Collision response is simply to reverse the direction of the objects concerned
Collision metrics can be reported from the class

BSP system achieved

Recursive BSP creation and naming
Recursiven BSP destruction
Splits a known area (the bounding area)
Splits until a terminal node contains an area of 12x12x12
Splits in a single axis for each tier of the tree (Rotates X->Y->Z)
The splitting plane normal points along the splitting axis in the positive direction
Point on the plane is considered (0,0,0), thus the plane constant d is 0
Because of this point on the plane it is only possible to split the bounding area into eight discreet areas

Collision achieved

Bound collision over a fixed area taking input metrics for an object Position, Height, Width and Depth as well as the Bounding area Position, Height, Width and Depth
AABB Collision taking Position, Height, Width and Depth for two objects
With AABB collision the first object is considered the reference object to be tested against
First passed in object is translated to the origin and the second object translated to compliment
AABB Collision needs checked in order to verify it is working correctly

Graphics archived

OpenGL initialisation packed into its own class
Split into pre,post and Frame sections
Bitmap Fonts can be printed out onto screen to display collision metrics
Bounding area complied into a display list for easy usage

Camera control achieved

Camera implemented
Camera controls its own look at function
The position of the camera is sampled upon a left mouse click in order to define the current BSP volume

Class linkages

BSP tree obtains the position of each Object by retrieving an iterator to the list contained within the Object Controller. It then sets the BSP area of the object and the next call to the Object Controller updates the colour of each of the objects.
Collision is currently performed per frame
Each class is constructed at run time and destroyed upon application exit
Update of collision metrics averaged over the last 10 frames for object to bound, object to object and total collisions

Lingering Problems

Uncertain if the AABB algorithm is correctly working
Main render section not frame limited
Physics update and collision not limited meaning on a machine with a faster CPU the simulation will run faster

Acceptable losses

Loss in resolution of BSP tree, collisions are still culled but not as aggressively
The circumstance where the point that the BSP tree is being traversed for is on the plane is undefined and returns an undefined value for the BSP volume
There is nothing to stop unneeded collision testing with objects I.E. object 1 as reference will be tested against object 2 and when object 2 is the reference object it will be checked again with object 1
Because of uncertainty with the state of the benchmarking software the application has not allowed to obtain the theorised speed up for the parallel application and the complexity of the overheads

Finalised metrics

Frame Rate capped at 60 frames per second
Collision metrics sampled and averaged every 10 frames
Physics updating only once per second
3000 Objects in the scene at any one time
Objects have a diameter of 5
Objects currently move 0.1 world units per frame
Bounding area being centred around the origin with Height, Width and Depth of 96
Minimum BSP volume being of Height, Width and Depth 12

Because the parallel application will use the base of this application without the BSP system and with an altered collision system the lingering problems will need to be tackled in order to correctly finish the parallel application.

The few problems with the BSP system have to be left as they are now as currently this section of the project has run out of time.

Initial Parallel application thoughts

One of the main things that has been estimated so far is using the idea of one thread per physical processor in order to process all collisions. This would mean the application for a PC with a dual core processor has a total of 3 threads. Additionally in order to reduce any usage of locks it may be possible use a hash table that can be accessed by all of the collision processing threads at the same time.

With this system there will need to be some sort of working sets created thus using a principle of locality as the key to the hash table would allow the threads to access areas of the hash table in parallel when the hash keys are significantly different although its possible this may not be suitable.

For the past few days I have been attempting to write the literature review section of the dissertation, currently it seems like a parallel processing primer describing base ideas and concepts of parallel processing. Still to be discussed is the applications of dedicated hardware parallel processing along with a classification of the current generation if applicable to a few of these models. Additionally before the literature review can move onto the research the current state of threading PC games needs discussed currently the only game engine there there is solid documentation on the threaded rendering system is the Unreal engine.

From there the planned discussion will move onto the current research in these fields and the justification for benchmarking the applications and estimating parallel performance using Amdahl's law and Gustafson's laws.

Week 4 Current State

2009-02-26T18:12:00.006Z

Currently the application looks like so:

Where red coloured objects are having full collision testing performed on them.

To get the application to this state there are a few things to note:

BSP Tree traversal assumes that the point on all planes is (0,0,0) which is of course not true and also limits the possible BSP areas to four meaning effectively that traversing the tree to a terminal node would give the same result as traversing three tiers of the tree.
For the BSP Tree the point on the plane problem is still undefined and if this occurs the object is assigned a null name for its BSP volume.
BSP naming fixed by performing a naming pass after building the tree naming the node if it is a terminal node or has children of its own.
Object size needed to be increased to 5.0f in order for some collision to occur.
AABB collision still seems to be inaccurate missing a few collisions.
No frame rate limiter is in place yet
Also there is no minimisation of variable retrieval from classes during render.
There is nothing to stop unneeded collision testing with objects I.E. object 1 as reference will be tested against object 2 and when object 2 is the reference object it will be checked again with object 1

Because this portion of the project is fast running out of time the reduction in BSP Tree sections is an acceptable loss overall as it was proving extremely hard to define a point on the plane.

Accurate AABB collisions however is a major point and needs to be fixed, this will probably cause a lot of overrun but because of the lack of learning the threading library that I've had the chance to do the first one to two weeks may be wasted catching up and fixing the AABB algorithm.

The increase of object size is of little concern although it makes it quite hard to spot any missed collisions.

The next step for tomorrow in order to prepare the program to be stripped down for the parallel version would be:

Frame limit rendering
Only sample collision numbers every 10 frames and give an average over those frames
Clean and simplify the windows message loop into Frame,Pre-Frame and Post Frame functions.

Emerging thoughts

Time Based Movement if the rendering is being limited, as currently a better processor will allow this application to run the simulation faster.

Week 4 Major Points

2009-02-25T16:44:00.005Z

Current Major Concerns are:

BSP Tree Traversal
BSP Terminal Node names
Undefined Point on the Plane BSP Tree Traversal problem

Minor Concerns

Frame limiter so that only the rendering is limited at ~60fps or so
Number of collisions/objects are sampled every 10 frames
Minimal variable retrieval during render

Currently the render loop is starting to look like so:

Reset collision counters
Take mouse input for camera position and look at
Update position of all objects
Traverse BSP tree to assign BSP volumes to objects
Objects to bound collision test
Object to object collision test

Reset OpenGL scene
Render Text to screen displaying collision numbers
Update Camera
Render Bounding area
Render all collide-able objects
Swap frame buffers

Post frame operations go here

Week 3 Serial Application

2009-02-20T13:13:00.006Z

Week 3 Tasks

BSP implementation (if applicable)
Collide-able Objects linked in some way to the BSP system
Debugging

Tasks done

BSP implimentation started (recursive tree building and destructrion)

Because of several things this week I've been unable to do much in the way of debugging the AABB algrothim. Currently this is the main area where problems are occouring because of as stated before each object can be in any octet around the origin. A quick fix to this may be to translate one of the objects to the origin (probably the object used as reference) and translating the other object by the same amount from there the test would be more or less the same as that between the bounding volume and each object.

Currently there is a minor problem with the terminal nodes of the BSP tree (child nodes at the bottom of the tree that do not have any other children) being named incorrectly, this is due to how the nodes are named by the recursive algorthim.

Additionally there is a problem with how to traverse the BSP tree.

Currently the algorthim to be used is: N . P + d = 0

Where N is the normal to the plane, P the point to be tested and d is a constant calculated using a point on the plane.

When the answer is 0 then the point is on the plane, >0 point is in the positive half-space, <0 point is in negative half-space.

Which means d can be calculated using -N . P0 = d

Where P0 is a known point on the plane

This is where the problem lies it would be beneficial to calculate d at the tree compile time,where to obtain the point P0.

P0 could be represented as a point defined by the current height,width and depth of the BSP volume but this would only work if the bounding box had its lower left hand corner at the origin. Because the bounding volume is centered round the origin this becomes more complex but it is possible that as with the AABB algorithm simple translating the lower left if the bounding volume to the origin may fix this problem. If it doesn't then there is a problem defining a point on the plane for calculating d.

Along with this its questionable that the BSP tree is being used correctly as per frame each object will need to be used to traverse the tree in order to obtain the BSP volume it is in.

In a previous post there was some pseudo-code for the object to object collision on second thought it may be best if a list of colliding objects can be built and somehow can be linked back to the master object list but this may not be possible without some complex pointer usage.

The current way to set the BSP area would be to use the position of the camera and when a mouse button is pressed check that the camera is within the bounding area and then traverse the BSP tree to find which volume to consider the active area.

Week 4 tasks

BSP tree Traversal
AABB algorithm debugged and working
Frame limiter
Possible on screen display of frame rate and collision numbers print out (object system will need modified to return these metrics)
Collision for objects in the current BSP volume working

Benchmarking has been removed at the moment due to the uncertainty with the benchmarking application that was added as part of the project proposal. There is trial versions of the software but I'd rather not waste the 30 days trial if I do not have both the applications ready to be used.

After this serial application is finished a large amount of the base application can be removed and used for the parallel application as only the collision section of the system will be parallel. Chances are that mainly the BSP tree system and some minor changes to the object controller will be made.

Week 3 BSP

2009-02-17T16:07:00.005Z

I've currently been reading this article on BSP trees from 1995: http://www.faqs.org/faqs/graphics/bsptree-faq/

Inital impimentation ideas

Splitting a known area of width X height X depth
Planes that split the area will be split each axis in this order X->Y->Z so that the first node will split the along the X axis using the plane normal to determine if the object is in the positive or negative half space
Minimum BSP area size of 12 X 12 X 12 meaning that there is a possibility of 9 recursive iterations to split the area appropriately (possible tree of 81 nodes)
Traversing the tree will take in a position which will then be used to traverse the tree to a terminal child node, the name of this child node will be the allocated BSP volume
Objects that are on the plane will be classified using the width ,height and depth of the object dependant on which axis the plane is splitting.

Currently I am considering each Node of the BSP Tree to have the following:

Current split of the bounding area (X,Y,Z)
Normal vector to the plane
Name of this node
State of the plane (Which axis it will be splitting)
Pointer to the two child nodes (if both are null then its a terminal Node)

Current problems

How to name each node: numbers, letters?
How to destroy the BSP tree when the application shuts down safely?
Slightly confused on where to start splitting at the maximum of the boundary or 1/2 way in
Is my plane splitting approach appropriate? Because there is a possibility that there will be no actual plane equation and it will be built from the current split positions for each axis and the normal
Traverses will always be the full tree (minimal problem but its something to think about)
How do I concurrently split nodes as in how can I build nodes on the positive side of the tree and the negative tree at the same time?

Currently this week I have lost one day waiting for an engineer to fix the boiler out at my flat and I will not be able to work on Thursday due to family commitments (but I'll still drag my notebook and such with me). Additionally I'm not feeling 100% so it may be that a minimal amount of debugging will be done on the AABB algorithm this week meaning that it is highly possible I may lose a maximum of two weeks of next month which should be implementation of the threading system. On the bright side it may be possible to use this tutorial to display information about frame rate and collisions on screen.

Serial Program Week 2

2009-02-13T15:42:00.008Z

Tasks for week 2

BSP research (implementation if applicable)

Class interactions (collision algorithms meshed with the object system)

Camera

Fixing the AABB collision algorithm

Bounding area rendered

Minor tweaks to the basic object storage so that a colour of each object can be changed depending if they are being tested for AABB collisions

Emergent tasks and concerns

Each colliding object now needs a position and movement direction, currently it is based on the half width of the bounding area divided by the number of the current object, the best possibility for this may be using a Monte Carlo method for both

It is possible that each object will need an ID so that the objects loaded into the AABB algorithm will not collision test themselves

Starting to need a frame limiter on the application

Would be nice to be able to count all of the collisions occurring and have the number print out to the screen

Collision response at the moment is dirt simple: just reverse the direction vector. If the objects could be of differing sizes or speeds then this would cause a major problem and could or should be adapted to find the Vector of separation as described by N Tutorials Collision Detection and response and then move them apart based on that

BSP research is currently small to non existent, currently the best bet is a worked example that I'm still to read through and decide if its applicable

Objects are perhaps too small to view properly

The radial collision between colliding objects and the bounding geometry is starting to become very close to that of the standard AABB algorithm

Uncertain about how to store each of the representations of the colliding objects into the object controller, linked list sounds like the best approach but there are questions with how the memory is allocated and destroyed

Creating a BSP tree using a simple algorithm might mean that a BSP tree for each axis is required to provide an accurate representation (so each object has a BSP X, Y and Z partition)

Attained

Object control class can access all collision functions as needed

AABB algorithm works but will need debugged next week because of inadequate implementation

Bounding area up and being used to test initial collisions with all scene objects

Colour system implemented (will be active and used once the BSP system is included)

Emerging Tasks and concerns addressed

Monte Carlo method used to generate both the initial position and direction like so: Position (X,Y,Z) set as ((-Bounding area size/2)+ rand()%Bounding area size), Direction (X,Y,Z) unit vector ((-100)+rand()%200), for the direction the numbers do not matter as it will be normalised. Additional code is currently in place to make sure that an object is not given an initial position outside the bounding area

ID system implemented to avoid testing the object with itself when performing AABB collision between objects

Need help implementing a frame limiter correctly

Getting the metrics to display is easy enough its printing them out to screen that's the problem

Collision response may be changed depending on the problems encountered within the next week

Both types of collisions are similar but the AABB between objects is more complex due to the nature that objects can be in any octet around around the 3D origin (this is also one of the major problems with the implimentation)

Object size is a minor problem

Memory and collision testing only the objects within the current BSP volume will be checked next week

BSP research goes on

Metrics

Currently the sizes and speed for everything in the scene are as follows:

Colliding spheres: Radius 0f 0.2f. Bounding box width, height and depth of 0.4f

Bounding area: centred around the origin. Bounds the are of height,width and depth of 96.0f

Colliding object speed of 1.01f

200 Colliding spheres

Current Screenshot

Week 3 Tasks

BSP implementation (if applicable)
Collide-able Objects linked in some way to the BSP system
Debugging

Debugging this week will mostly consist of fixing the AABB algorithm and the extension of the collision response. Implementing the AABB algorithm into the program may be as follows:

1.1 Get an Iterator to the first object in the list

1.2 For all objects in the list

1.2.1 Get another Iterator to the first object in the list
1.2.3 For all objects in the list (using the second Iterator)
1.2.3.1 Check that the ID of the objects do not match
1.2.3.2(Check the BSP volume of the object matches the currently set one)
1.2.3.3 Perform collision detection with the first iterator as object 1 and
the
second as object 2
1.2.3.4.1 Perform collision response
1.2.4 Increment the second Iterator

1.3 Increment first Iterator

On another note I had thought about using Doxygen to generate documentation from the project directly so I'll maybe have a better look at that this weekend.

Something a bit more visual

2009-02-12T18:00:00.007Z

Screen shot of the current state of the project but still a few things are to be done before the end of this week.

Week 2 Tasks +Over spill tasks

BSP research (implementation if applicable)
Class interactions (collision algorithms meshed with the object system)
Camera
Fixing the AABB collision algorithm
Bounding area rendered
Minor tweaks to the basic object storage so that a colour of each object can be changed depending if they are being tested for AABB collisions

Current Achievement

Class interaction with Bounding volume collision algorithm
Camera implemented
Bounding area rendered can also be set to any size that is defined at compile time
Red coloured objects under go AABB testing between themselves and the bounding volume while white objects only undergo testing with the bounding volume
AABB Algorithm 'works'

Emerging problems

Each colliding object now needs a position and movement direction, currently it is based on the half width of the bounding area divided by the number of the current object, the best possibility for this may be using a Monte Carlo method for both
It is possible that each object will need an ID so that the objects loaded into the AABB algorithm will not collision test themselves
Starting to need a frame limiter on the application
Would be nice to be able to count all of the collisions occurring and have the number print out to the screen
Collision response at the moment is dirt simple: just reverse the direction vector. If the objects could be of differing sizes or speeds then this would cause a major problem and could or should be adapted to find the Vector of separation as described by N Tutorials Collision Detection and response and then move them apart based on that
BSP research is currently small to non existent, currently the best bet is a worked example that I'm still to read through and decide if its applicable
Objects are perhaps too small to view properly

Serial Program Week 1

2009-02-06T17:25:00.005Z

Tasks for week 1:

Initial Thoughts on BSP system + research on the implementation
Collide-able object system and storage to be created
Initial version of the application independent collision algorithms (Static Library)
Basic framework that will initialise the graphical system and be portable in its base state to the parallel application.

Attained

Basic application frame work with graphics initialisation
Collision with a bounding geometry and an object algorithm working
Basic Object storage and Object controller class created

Overlap Tasks

Fixing the AABB collision algorithm
Bounding area rendered
Minor tweaks to the basic object storage so that a colour of each object can be changed depending if they are being tested for AABB collisions

Meta Tasks

Collision needs to be finished before being implemented in the Object controller
Current implementation of collision algorithms considers that all heights, widths and depths are divided by 2 in order to find the extremity of the edge of the object
Collision algorithms have an unwieldy number of input variables
More complex object initialisation to spread objects equally
Need to define how large the bounding geometry will be

Fixes from previous concerns

Vector4 class from the PS2 Framework is being used for now until an alternative becomes available
Colliding objects are currently stored in a linked list within the object controller
Radial collision is still very close to the inverse of the AABB collision algorithm
Better abstraction to Objects have them as classes also means that the pointer to the GLU object representing the collision objects is wrapped within the class
Objects will have their Orientation vector normalised before any calculations, if not normalised by the user it will be performed when moving the object
Implement the colour of the objects next week
After getting the final version the collision library project file will be linked into the serial application which will then become dependant on its build

Thankfully next week does not have much in the way of complex tasks so the tasks left over from week 1 should be quick to complete before week 2 tasks are to be done. At most the overlap will cause about 2 days of delay

Serial Application Plan

2009-02-05T16:32:00.008Z

The current plan for this month is to be spent putting together the serial application.
The main areas of this application are as follows:

Collide-able Objects
BSP System
Collision algorithms and response
Graphics system including camera control

A short overview of each component:

Collide-able Objects

Stores everything that describes a collide-able object (position, height, width, orientation, movement, direction etc).
Performs the actual moving of each object.

BSP System

Splits the bounding geometry into discreet sections.
The BSP tree will be traversed at the start of each collision test in order to cull collisions that are not in the currently set BSP area

Collision algorithms and response

Radial and AABB collision.
Radial collision between the bounding geometry and each colliding object.
AABB collision between each individual objects.
Will return a true or false depending if the objects collide with each other or the bounding geometry. Collision response will then be handled by the main application.
Should be portable as possible for integration into the Parallel application.

Graphics system including camera control

Renders the bounding geometry. Currently bounding geometry will be represented as a large cube rendered as wireframe centred on the origin.
Possible extension to allow the BSP sections to be rendered
Renders all colliding objects.
Camera system controls how the scene is viewed.

Risk Assessment

High Risk

BSP system
Collision algorithms

Medium Risk

Graphics system including camera control
Camera

Low Risk

Collide-able Objects

Projected Time frame

4 Weeks, Start 1st February 2009, End 28th February 2009

Estimated 3-4 days a week spent on the honours project (in-between lectures/tutorials)

Additional 1-2 days a week are set aside for Advanced Games Technology work or learning the first choice library to implement the Parallel application.

Weekly breakdown

Week 1

Initial Thoughts on BSP system + research on the implementation
Collide-able object system and storage to be created
Initial version of the application independent collision algorithms (Static Library)
Basic framework that will initialise the graphical system and be portable in its base state to the parallel application.

Week 2

BSP research (implementation if applicable)
Class interactions (collision algorithms meshed with the object system)
Camera
Any spill over from week 1

Week 3

BSP implementation (if applicable)
Collide-able Objects linked in some way to the BSP system
Debugging

Week 4

Week 3 spill over
Debugging
Benchmarking
With the benchmarked numbers get the theorised speed up for the parallel application

Serial application proposed main loop flow

1.1 Start

1.2 Initialise Graphics

1.3 Initialise Collide-able Object system

1.4 Build BSP Tree(s)

1.5 Main Loop Starts

1.5.1 Take camera input

1.5.2 Collide-able Object system Moves all of the objects

1.5.3 Traverse BSP Tree(s) assigning objects a BSP partition

1.5.4 Collision test all objects with the bounding geometry and collision tests between objects contained within the currently "active" BSP partition

1.5.5 Render Scene

1.6 Application exit

1.7 Clean up all allocated memory

1.8 Close application

Current Progress

Application framework with the graphics system, no camera yet.
Working on collision library.
Storage for the collide-able objects, leaning towards a controller system that will handle all collisions, movement and such.
Bit of a vague idea on BSP, Each node may contain a Plane that is used to find out if the object is in the positive or negative half space.

Current Problems

No implemented Vector class yet meaning that positions are currently a set of three floats, making the code somewhat unwieldy to read
The radial collision between colliding objects and the bounding geometry is starting to become very close to that of the standard AABB algorithm
Uncertain about how to store each of the representations of the colliding objects into the object controller, linked list sounds like the best approach but there are questions with how the memory is allocated and destroyed
Creating a BSP tree using a simple algorithm might mean that a BSP tree for each axis is required to provide an accurate representation (so each object has a BSP X, Y and Z partition)
Simplicity of the current collide-able object class means that it may be better represented as a structure and then the overreaching object controller class would perform what little methods are within the collide-able object class
Movement for the colliding objects needs to be confirmed (new position= Old position + (Orientation * scalar speed)?)
Perhaps a good idea to colour all objects in the "active" BSP area?
As usual the application has a large run up time in terms of code before any proper testing can be done

The good the bad and the ugly

2009-01-28T15:46:00.013Z

Currently I am looking at three different ways in order to implement the threaded aspect of the parallel application. Firstly thought I have been occasionally changing terminology when talking about the application to be created.

Multi-threading
Multi-Processing

Both of these terms can have a lot of the same concurrency problems and paradigms applied to them but are fundamentally different.

Multi-threaded refers to the operating system (OS) construct of a thread that is shared between one or more processors, the OS controls which processor the thread executes on and when it executes.

Multi-Processing refers to using multiple of perhaps small inexpensive processors in order to batch process data. The best example of a system like this is the PS3 where the Power Processor Element (PPE) is the centre of the system sending tasks to the Synergistic Processor Elements (SPEs) (http://www.blachford.info/computer/Cell/Cell1_v2.html); the parallel task is being executed on physical hardware rather than being multiplexed across one or more CPUs dependant the operating system control. The additional consideration that Multi-Processing has is that of processor cache concurrency.

The three ways that the parallel application could be implemented are broken up like so:

Multi-Threading:

Intel Threading Building Blocks (TBB) (http://www.threadingbuildingblocks.org/)
Boost C++ Libraries, Specifically the Thread Library (http://www.boost.org/)

Multi-Processing:

nVidia CUDA General Purpose GPU language (GPGPU) (http://www.nvidia.com/object/cuda_home.html)

Depending on the chosen implementation will change the semantics of the language used and how the application is benchmarked.

First impressions

After looking at the introductory documentation for each of these approaches here are the first impressions for each of them. At the end of the week after a discussion with my technical supervisor I should have a definite hold on what approach to use.

Intel Threading Building Blocks

This library set is currently the base of the SMOKE framework uses for concurrency and parallel implementation. The library focuses on scalability of the parallelised code across N number of processors future proofing any increase in the number of possible processes with additional options to set the size of granularity for a specific operation. Threads are abstracted away so that the user defines tasks that will be processed by a task manager (although the task manager is designed for algorithms that will not block), the section to parallel process defined by a blocked range template from the library. Additionally it has a number of differing types of mutual exclusion primitives that can be used in conjunction with these methods in order to control data concurrency. Because of the STL style of each of the operations all can be extended and customised to suit the current task.

With this approach the focus of the project may shift slightly more towards the study of creating the working sets.

Advantages:

Lowers risk with creating deadlocks in threads due to the wide array of templates
Variable granularity size for tasks including optimisations for the cache

Disadvantages:

Granularity of the task may need to be either found from checking code performance or another way
May end up too reliant on the low level feature set meaning that no templates will be used

Boost C++ Thread Library

The Boost library contains a large number of extensions to C++ but the only one that will be used would be that of the Thread library. Working on the OS level of thread constructs this allows the creation of thread objects that when destroyed will not necessarily end the thread it is associated with but provided the user knows the ID of the thread they can join a new Thread object to that running thread to either terminate its operation or change the working set that the thread is processing. Calling a number of standard thread functions will interrupt the thread if that thread is interruptible. The Thread object being a template class can be customised to the task. Also a wide array of lock and mutex objects are used to control concurrency.

Advantages:

High amount of customisability
No need for a concurrent list of all Thread objects running at any time a single Thread object can be joined to any thread as long as the ID is known

Disadvantages:

No Inherent system t0 define the maximum number of threads that a system might use, meaning a possibility of flooding the OS with threads
A personal gripe with this is the size of the Boost library overall although it is currently uncertain if the Thread library is without attachment to any other Boost Library.

nVidia CUDA GPGPU

The CUDA implementation uses the GPU to accelerate calculation of large scale tasks. nVidia's 8000 and above series are compatible with this system using the parallel nature of a graphics card to process C style functions called Kernels. Each kernel will be run N times on a number of N CUDA threads. Memory is can be organised as thread local, N by N shared block or as global memory across all processes. Designed as an extension to the C language this system is reliant on the number of multi-processors on the graphics card, the current nVidia graphics card in the university computers are 8600 GTs and my own computer at home is the mobile version of these graphics cards, this gives a compute compatibility of 1.1 according to the specifications published by nVidia effecting the number of thread blocks that can be processed.

Advantages:

Gives a real parallel processing environment
Eliminates a lot of overhead associated with OS threads
Removes the possibility of flooding the system with OS threads

Disadvantages:

C style, somewhere in the program the relevant information about the colliding objects would need to be extracted from their encapsulation and then processed into a structure that a kernel could use
CUDA assigned memory does not have equal priority with that of graphics memory meaning that the standard graphics card drivers may overwrite CUDA memory if needed
Specialist CUDA drivers and tool kit need to be installed on the machine additionally to use the graphics card drivers need to be greater than a certain version
Benchmarking this application will be vastly different from benchmarking the serial application

Apart from these three implementation approaches the graphics API to display the world where all objects are colliding will be OpenGL due to the low priority nature of the graphics display and the greater familiarity with OpenGL at the moment. Additionally setting up OpenGL will be faster and removes the centralised Device that DirectX uses as well as my only experience with DirectX being that of the programmable (shader) pipeline.

Intel TBB

2009-01-19T16:08:00.004Z

Bit before Christmas I had a quick conversation with AIK about using SMOKE for the threading implementation for this project. He muted the point that its possible that benchmarking the application with this framework may make it harder to obtain accurate results. He also suggested to try using the Intel Threading Building Blocks Libraries. Currently I'm looking at the open source version of them and will probably try and create a few examples within the next week.
Even if I do decide not to use the SMOKE framework the Ideals behind its operation are more than noteworthy for different approaches and extensions of the project material.

By the end of this month I should have at least an idea of what system I will use to implement the threaded portion of the research project, along with the graphics API that will be used to display the world where the collisions are taking place.
On the code side of things possibly an application base that can be used for the single threaded application and the multi threaded application, that will create a basic window ready to start the main section of the project.

Gold Master

2008-12-15T11:44:00.002Z

Final Project proposal:

Introduction

Up until recently the computing industry has been governed by Moore’s law stating that:
Every two years the number of transistors on an integrated circuit (IC) will double (Moore 1965)

This is attributed to the falling cost of each transistor over these two year periods and has held reasonably true over the past forty years. Although not thought of at when it was theorised in 1965 there is a major limiting factor in this exponential rule:

· The size of a transistor on a silicone wafer (Dubash 2005)

As the size of a transistor approaches the size of an atom electrical current will cease to flow through the transistor. Other considerations such as the amount of heat generated from an IC will increase in line with the number of transistors etched onto the single silicone wafer at the core of the IC also plays a major role in creating the limit of this law (Sutter 2005).
In order to extent the life of the current fabrication process until other fabrication processes or ICs that operate on an entirely different principal become cost effective as the current process the industry is changing.

These physical limits are causing the industry to shift towards multiple processor architectures (Sutter 2005). Because of this shift the industry becomes controlled by another rule: Amdahl’s Law

Amdahl’s Law gives the expected speed up of a system when one or more parts of it are parallelised base upon the amount of time that it takes for a sequential operation. It also assumes that there is no change in the actual size of the problem when converted to run on a parallelised system (Hill & Marty 2008).

The most recent generation of games consoles all exploit parallelism to some degree in an attempt to push higher technical specifications that its competitors. However personal computers have been utilising parallel processing since 2004 but as Granatir (2008) states:

“Game development is one area that has lagged behind in the progression of multi-threaded software”

With most games collision detection plays an important part in either game mechanics or making the world the player is immersed in seem more realistic yet in creating a more realistic simulation more collisions may have to occur.A current approach such as space partitioning is used to cut down the number of actual collisions that will be calculated (Bobic 2000). But with parallelisation becoming more apparent within the industry can these collision culling approaches become less imperative meaning that a more realistic simulation of collision in the player’s world can take place?

Research Topic

The core of this project is researching how all collision detection in a world can be processed by a parallel system and if the resulting parallel system can then compare performance wise to a non parallel system processing collision detection using a collision culling technique. Specifically the technique used to cull collisions for the non parallel system will be Binary Space Partitioning (BSP).

This comparative study of both applications will have conclusions drawn from the results gained from profiling the operation of each program under a number of different circumstances. These circumstances will range from varying the number of objects that can possibly collide in the scene to altering the number of volumes that they collide in. The greater the number of volumes that they can collide in the more spread out all of the objects will be.These two changing variables would provide adequate simulation of the number of collisions that could possibly take place in different game environments creating different variations on which to gauge the results.

Research Question

With respect to Overhead and parallelised performance can a multithreaded application outperform a single threaded application where both are processing the same 3D scene where a large number of collisions are occurring?

Project Execution

Two applications will be created:
· One multithreaded application that will use a threading methodology gained from research.
· A single threaded application that will use BSP to cull the number of collision tests happening per time sampled.

Both of these applications will render a 3D scene. This 3D scene will have several bounding volumes with a number of objects colliding within them. The bounding volumes will represent possible level geometry and be shown as simple wireframe cubes and the objects will be spheres (very low complexity as a large number of them may be rendered on screen at any one time).

Two types of collision will take place in this scene:
· Radial collision between each sphere and the boundaries of the volume containing it
· Axis Aligned Bounding Box collision (AABB) between spheres

At all times the radial collision between the spheres and the bounding of the containing volume will occur. This means that regardless of what is culled in the single threaded example there will always be a benchmark between both applications at a base level. This base level of collisions will also preserve visual continuity for the BSP example, as only the BSP area that the camera is within will have the AABB collision calculated for it. Defining each BSP area will be either done by a 3rd party library or hard coded for ease depending on the complexity of the scene.

Each object after colliding with either the bounding of the area or another object will pick a semi realistic direction to rebound from the collision. Each collision will be elastic for each of the objects colliding meaning that objects in the scene should never stop moving. Collision detection will be performed after a certain number of frames.

To profile the applications the internal profiling tool included within Visual Studio 2005 will be used. To accurately obtain the time taken per frame to process collision detection within the single threaded application collision detection will be performed each frame, lowering the frame rate but providing a stable result which to use as the basis of the conclusion.
The multithreaded application will require two sets of time profiled:

· One frame where collision detection is taking place in parallel
· The total time over which all collision detection is processed.

The first result will give the overall speed up per frame while the 2nd result may not actually give a speed up but an increased time for processing all collisions; this is one of the overheads that will be discussed in the conclusion Additionally the amount time required to processes overhead required producing the working sets that the threaded system will processes will be profiled and it will have a bearing on the final conclusion. Also the overhead from the single threaded application namely the classification of objects that will be culled by BSP as described by Shimer (1997) will also be profiled and compared against its multithreaded counterpart in order to draw an adequate conclusion to answer the research question.

Evaluation

The main area of evaluation will be comparing the two applications based on Amdahl’s Law (Hill & Marty 2008).
The theorised performance improvement will be obtained from the single threaded application like so:

Find how much of the program is performed in serial order by doing:

Serial= (1-(Time for collision processing/Time for single frame))

Where (Time for collision processing/Time for single frame) will give the percentage of the program that can be parallelised

And applying Amdahl's law to achieve maximum speed up using N processors gives:

Max Speed Up= ((Time for collision processing /Time for single frame)/N)

Therefore:

Speed up ((Time for Collisions/Time for Single frame), N)

= 1/ (Serial + Max Speed Up)

This is where N equals the number of processors on the machine designated to process the multithreaded application.

This will then be compared to the actual speed up of the application gained through profiling the multithreaded application and calculated like so:

Obtain the amount that the application has been speeded up by:

Speed Multiplier= (Time for collision processing /Multithreaded collision time)

Therefore you can find the amount of time for the multithreaded part of the program:

Multithreaded part time= ((Time for collision processing/Time for single frame))/Speed Multiplier)

(Where the Time for collisions and Time for single frame are from the single threaded application)

And then applying Amdahl's law gives:

Speed up ((Time for collisions/Time for single frame, Speed Multiplier)

= 1/ (Serial+ Multithreaded part time)

Additional considerations with respect to the amount of overhead for each application will also be taken into account when writing the conclusion as well as the differing conditions such as the number of colliding objects and the number of volumes collisions occur in. This will provide a wide spectrum of conditions on which to asses the multithreaded application.

Equipment

At minimum a single core PC to test the single threaded application and a multiple core machine to process the multithreaded application. Ideally the machine processing the multithreaded application should have a quad core processor. Both should have the same type of graphics hardware in order to eliminate any discrepancy in performance while rendering the 3D scenes.
Additionally depending on the limits of the Visual Studio profiler a copy of Intel VTune may be required for accurate profiling due to its ability to show detailed thread information (Intel 2008).

Issues

Two main issues will have a major impact on this project:
How the parallelism of the multithreaded application is handled
How the working sets for the multithreaded application are created

Currently there are three main ways that could be used to handle the parallelism of the multithreaded application:

· Programming in C# (Albahari 2006-2007)
· Using an OpenMP compliant Compiler (Pas 2008)
· Using Intel’s SMOKE Framework (Grantir 2008)

As it is highly possible that implementing this in C++ would be far too complex due to the lack of standardised support as described by Sutter (2005), these are the most likely candidates to be used. Each one of them will have an effect at some level on overheads.
The implementation with the largest amount of overhead requiring a system that is heavily parallel would be using the SMOKE Framework but due to its basic design being for Computer Game applications it would be the most ideal. Programming the application in C# may remove the threading overhead meaning that the comparison of the overhead may be more straightforward than using another method. Compiling the application with an OpenMP compiler can give access to “Hardware Threads” which means that any overhead between the operating system and the application is effectively eliminated as for each physical processor there is a single thread (Chapman 2008).

Depending on what system is used to implement the multithreaded system there is also the problem with Amdahl’s Law in that it is theorised that the application being parallelised will have exclusive access to each of the processing cores. With threads being handled by windows there will always be other processes using the processor (Albahari 2006-2007). Additionally Amdahl’s law was re-evaluated as Gustafson (1988) states that Amdahl’s law may be better represented as:
Totally Work= Serial Amount + No Processors X parallel amount
Giving another metric on which the project could be gauged on.

The other main consideration is the creation of the working sets, based on the paper by Lewis & Massingill (2006), depending on the number of collision samples per second will depend on the size of each working set. Additionally if there is a large amount of spheres overlapping into many different working sets the multithreaded application could become even less efficient than the single threaded application.

Conclusion

“Your free lunch will soon be over” (Sutter 2005)
In order to continue for a personal computer to continue to be a platform for high performance computer games the game software developed for it must continue to adapt to the current techniques of programming on a multi-processor architecture.

Bibliography

Turley, J.2006.A Glimpse Inside The Cell Processor. [Online] Gamasutra.com. Available from: http://www.gamasutra.com/view/feature/2759/a_glimpse_inside_the_cell_processor.php [Accessed 15th October 2008]

Gabb, H & Lake, A. 2005. Threading 3D Game Engine Basics. [Online]. Gamasutra.com. Available from: http://www.gamasutra.com/features/20051117/gabb_01.shtm [Accessed 20th October 2008]

Mönkkönen, V. 2006. Multithreaded Game Engine Architectures. [Online]. Gamasutra.com. Available from: http://www.gamasutra.com/view/feature/1830/multithreaded_game_engine_.php [Accessed 20th October 2008]

Paquet, P. 2006. Programming Multi-threaded Architectures: Interlocked Operations. [Online]. Gamasutra.com. Available from: http://www.gamasutra.com/view/feature/2745/programming_multithreaded_.php [Accessed 07th October 2008]

Sutter, H. 2008. Break Amdahl’s Law!.[Online]. Dr Dobb’s Portal. Available from: http://www.ddj.com/cpp/205900309 [Accessed 8th December 2008]

Sutter, H. 2007. Avoid Calling Unknown Code While Inside a Critical Section, [Online]. Dr Dobb’s Portal. Available from: http://www.ddj.com//architect/202802983 [Accessed 8th December 2008]

Sutter, H. 2008. Understanding Parallel Performance. [Online]. Dr Dobb’s Portal. Available from: http://www.ddj.com/cpp/211800538 [Accessed 3rd December 2008]

Sutter, H. 2007. The Pillars of Concurrency: Building a consistent mental model for reasoning about concurrency. [Online]. Dr Dobb’s Portal. Available from: http://www.ddj.com/architect/200001985 [Accessed 20th October 2008]

Lander, J.2000. When Two hearts Collide: Axis-Aligned Bounding Boxes. [Online]. Gamasutra.com. Available from: http://www.gamasutra.com/view/feature/3426/when_two_hearts_collide_.php [Accessed 07th October 2008]

Wilson, K. 2006. Managing Concurrency: Latent Futures, Parallel Lives. [Online]. GameArchitect.net Available from: http://www.gamearchitect.net/Articles/ManagingConcurrency1.html [Accessed 20th October 2008]

Chalmers, A & Tidmus, J 1996, Practical Parallel Processing, International Thomson Computing Press, London, UK

References

Moore, G.E. 1965. Cramming more components onto integrated circuits. [Online]. Intel Museum Available from: ftp://download.intel.com/museum/Moores_Law/Articles-Press_Releases/Gordon_Moore_1965_Article.pdf [Accessed 20th October 2008]

Sutter, H. 2005. A Fundamental Turn Toward Concurrency in Software. [Online]. Dr Dobb’s Portal. Available from: http://www.ddj.com/architect/184405990 [Accessed 20th October 2008]

Dubash,M. 2005. Moore’s law is dead, says Gordon Moore. [Online] Techworld. Available from: http://www.techworld.com/opsys/news/index.cfm?NewsID=3477 [Accessed 20th October 2008]

Hill, M.D. & Marty M.R. 2008. Amdahl’s Law in the Multicore Era. [Online]. IEEE Computer Society Digital Library. Available from: http://www2.computer.org/portal/web/csdl/doi/10.1109/MC.2008.209 [Accessed 30th October 2008]

Granatir, O. 2008. Performance Scaling With cores: Introducing the SMOKE Framework. [Online]. Gamasutra.com. Available from: http://www.gamasutra.com/view/feature/3861/performance_scaling_with_cores_.php [Accessed 28th November 2008]

Granatir, O. 2008. SMOKE-Game technology Demo. [Online]. Intel What IF. Available from: http://software.intel.com/en-us/articles/smoke-game-technology-demo [Accessed 28th November 2008, from]

Pas, R V D 2008. An Overview of OpenMP 2.5. [Online]. IWOMP Workshop. Available from: http://cobweb.ecn.purdue.edu/ParaMount/iwomp2008/documents/3.Overview_OpenMP_HO.pdf [Accessed 1st December 2008]

Lewis, M.C & Massingill, B.L. 2006. Multithreaded Collision Detection in Java. [Online]. World Congress in Computer Science, Computer Engineering and Applied Computing. Available from: http://ww1.ucmss.com/books/LFS/CSREA2006/PDP4236.pdf [Accessed 15th October 2008]

Shimer, C. 1997. Binary Space Partition Trees. [Online]. Worcester Polytechnic Institute Computer Science CS 563 '99 - Advanced Topics in Computer Graphics. Available from: http://web.cs.wpi.edu/~matt/courses/cs563/talks/bsp/bsp.html [Accessed 05th November 2008]

Gustafson, J.L. 1988. Reevaluating Amdahl’s Law. Communications of the ACM. vol. 31. May Issue 5. p 532 – 533. [Online]. Available from: http://doi.acm.org/10.1145/42411.42415 [Accessed 24th November 2008]

Albahari, J. 2006-2007. Threading in C#. [online]. O’Reilly. Available from: http://www.albahari.com/threading/ . [Accessed 8th December 2008]

Intel. 2008. Intel VTune. Available Online. From: http://www.intel.com/cd/software/products/asmo-na/eng/239144.htm . Intel[011]

Chapman, B. 2008. How OpenMP is compiled. [Online]. in IWOMP Workshop. Available from: http://cobweb.ecn.purdue.edu/ParaMount/iwomp2008/documents/chapman-underthehood . [Accessed 8th December 2008]

Bobic, N. 2000. Advanced Collision Detection techniques. [Online] Gamasutra.com. Available from: http://www.gamasutra.com/view/feature/3190/advanced_collision_detection_.php [Accessed 10th October 2008]

Now I can go off and panic about my exams and other coursework.

Proposal Draft

2008-12-01T15:54:00.009Z

First draft of the project Proposal, well over the word limit and missing some references and proofs.

Introduction

Up until recently the computing industry has been governed by Moore’s law stating that:
Every two years the number of transistors on an integrated circuit (IC) will double (Moore 1965)

This is attributed to the falling cost of each transistor over these two year periods and has held reasonably true over the past forty years. Although not thought of at when it was theorised in 1965 there is a major limiting factor in this exponential rule:

· The size of a transistor on a silicone wafer (Dubash 2005)

As the size of a transistor approaches the size of an atom electrical current will cease to flow through the transistor. Other considerations such as the amount of heat generated from an IC will increase in line with the number of transistors etched onto the single silicone wafer at the core of the IC also plays a major role in creating the limit of this law.
In order to extent the life of the current fabrication process until other fabrication processes such as ICs operating on the nano scale or quantum computing become cost effective as the current process the industry is changing.

These physical limits are causing the industry to shift towards multiple processor architectures (Sutter 2005). Because of this shift the industry becomes controlled by another rule: Amdahl’s Law

Amdahl’s Law gives the expected speed up of a system when one or more parts of it are parallelised base upon the amount of time that it takes for a sequential operation. It also assumes that there is no change in the actual size of the problem when converted to run on a parallelised system (Hill & Marty 2008).

The most recent generation of games consoles all exploit parallelism to some degree in an attempt to push higher technical specifications that its competitors. However personal computers have been utilising parallel processing since 2004 but as (Granatir 2008) states:

“Game development is one area that has lagged behind in the progression of multi-threaded software”

With most games collision detection plays an important part in either game mechanics or making the world the player is immersed in seem more realistic yet in creating a more realistic simulation more collisions may have to occur. Current approaches such as space partitioning or use of the rules of the game are used to cut down the number of actual collisions that will be calculated. But with parallelisation becoming more apparent within the industry can these collision culling approaches become less imperative meaning that a more realistic simulation of collision in the player’s world can take place?

Research Topic

The core of this project is researching how all collision detection in a world can be processed by a parallel system and if the resulting parallel system can then compare performance wise to a non parallel system processing collision detection using a collision culling technique. Specifically the technique used to cull collisions for the non parallel system will be Binary Space Partitioning (BSP).

This comparative study of both applications will have conclusions drawn from the results gained from profiling the operation of each program under a number of different circumstances. These circumstances will range from varying the number of objects that can possibly collide in the scene to altering the number of volumes that they collide in. The greater the number of volumes that they can collide in the more spread out all of the objects will be. These two changing variables would provide adequate simulation of the number of collisions that could possibly take place in different game environments.

Research Question

What are the Considerations with respect to Overhead and serialisation performance between a single threaded application and a multithreaded application where both are processing the same 3D scene where a large number of collisions are occurring?

Project Execution

Two applications will be created:
· One multithreaded application that will use a threading methodology gained from research.
· A single threaded application that will use BSP to cull the number of collision tests happening per time sampled.
Both of these applications will render a 3D scene. This 3D scene will have several bounding volumes with a number of objects colliding within them. The bounding volumes will represent possible level geometry and be shown as simple wireframe cubes and the objects will be spheres (very low complexity as a large number of them may be rendered on screen at any one time).

Two types of collision will take place in this scene:
· Radial collision between each sphere and the boundaries of the volume containing it
· Axis Aligned Bounding Box collision (AABB) between spheres
At all times the radial collision between the spheres and the bounding of the containing volume will occur. This means that regardless of what is culled in the single threaded example there will always be a benchmark between both applications at a base level. This base level of collisions will also preserve visual continuity for the BSP example, as only the BSP area that the camera is within will have the AABB collision calculated for it. Defining each BSP area will be either done by a 3rd party library or hard coded for ease depending on the complexity of the scene.

Each object after colliding with either the bounding of the area or another object will pick a semi realistic direction to rebound from the collision. Each collision will be elastic for each of the objects colliding meaning that objects in the scene should never stop moving. Collision detection will be performed after a certain number of frames.

To profile the applications the internal profiling tool included within Visual Studio 2005 will be used. To accurately obtain the time taken per frame to process collision detection within the single threaded application collision detection will be performed each frame, lowering the frame rate but providing a stable result which to use as the basis of the conclusion.
The multithreaded application will require two sets of time profiled:

· One frame where collision detection is taking place in parallel
· The total time over which all collision detection is processed.

The first result will give the overall speed up per frame while the 2nd result may not actually give a speed up but an increased time for processing all collisions; this is one of the overheads that will be discussed in the conclusion. Additionally the amount time required to processes overhead required producing the working sets that the threaded system will processes will be found and it will have a bearing on the final conclusion. Also the overhead from the single threaded application namely the classification of objects that will be culled by BSP will also be profiled and compared against its multithreaded counterpart.

Evaluation

The main area of evaluation will be comparing the two applications based on Amdahl’s Law (Hill & Marty 2008).
The theorised performance improvement will be obtained from the single threaded application like so:

Find how much of the program is performed in serial order by doing:

Serial= (1-(Time for collision processing/Time for single frame))

Where (Time for collision processing/Time for single frame) will give the percentage of the program that can be parallelised

And applying Amdahl's law to achieve maximum speed up using N processors gives:

Max Speed Up= ((Time for collision processing /Time for single frame)/N)

Therefore:

Speed up ((Time for Collisions/Time for Single frame), N)

= 1/ (Serial + Max Speed Up)

This is where N equals the number of processors on the machine designated to process the multithreaded application.

This will then be compared to the actual speed up of the application gained through profiling the multithreaded application and calculated like so:

Obtain the amount that the application has been speeded up by:

Speed Multiplier= (Time for collision processing /Multithreaded collision time)

Therefore you can find the amount of time for the multithreaded part of the program:

Multithreaded part time= ((Time for collision processing/Time for single frame))/Speed Multiplier)

(Where the Time for collisions and Time for single frame are from the single threaded application)

And then applying Amdahl's law gives:

Speed up ((Time for collisions/Time for single frame, Speed Multiplier)

= 1/ (Serial+ Multithreaded part time)

Additional considerations with respect to the amount of overhead for each application will also be taken into account when writing the conclusion.

Equipment

At minimum a single core PC to test the single threaded application and a multiple core machine to process the multithreaded application. Ideally the machine processing the multithreaded application should have a quad core processor.
Additionally depending on the limits of the Visual Studio profiler a copy of Intel VTune may be required for accurate profiling.

Issues

Two main issues will have a major impact on this project:
How the parallelism of the multithreaded application is handled
How the working sets for the multithreaded application are created
Currently there are three main ways that could be used to handle the parallelism of the multithreaded application:

· Programming in C#
· Using an OpenMP compliant Compiler (Pas 2008)
· Using Intel’s SMOKE Framework (Grantir 2008)

As it is highly possible that implementing this in C++ will be far too complex, these are the most likely candidates to be used. Each one of them will have an effect at some level on overheads.
The implementation with the largest amount of overhead requiring a system that is heavily parallel would be using the SMOKE Framework but due to its basic design being for Computer Game applications it would be the most ideal. Programming the application in C# may remove the threading overhead meaning that the comparison of the overhead may be more straightforward than using another method. Compiling the application with an OpenMP compiler can give access to “Hardware Threads” which means that any overhead between the operating system and the application is effectively eliminated as these threads are run directly on the processor.

Depending on what system is used to implement the multithreaded system there is also the problem with Amdahl’s Law in that it is theorised that the application being parallelised will have exclusive access to each of the processing cores. With threads being handled by windows there will always be other processes using the processor.

The other main consideration is the creation of the working sets, based on the paper by Lewis & Massingill (2006); depending on the number of collision samples per second will depend on the size of each working set. Additionally if there is a large amount of spheres overlapping into many different working sets the multithreaded application could become even less efficient than the single threaded application.

Bibliography

Turley, J 2006, ‘A Glimpse Inside The Cell Processor’, in Gamasutra, accessed 15th October 2008, from < http://www.gamasutra.com/view/feature/2759/a_glimpse_inside_the_cell_processor.php>

Gabb, H & Lake, A 2005, ‘Threading 3D Game Engine Basics’, in Gamasutra, accessed 20th October 2008, from < http://www.gamasutra.com/features/20051117/gabb_01.shtml>

Mönkkönen, V 2006, ‘Multithreaded Game Engine Architectures, in Gamasutra, accessed 20th October 2008, from < http://www.gamasutra.com/view/feature/1830/multithreaded_game_engine_.php>

Paquet, P 2006, ‘Programming Multi-threaded Architectures: Interlocked Operations’, in Gamasutra, accessed 07th October 2008, from < http://www.gamasutra.com/view/feature/2745/programming_multithreaded_.php>

Chalmers, A & Tidmus, J 1996, Practical Parallel Processing, International Thomson Computing Press, London, UK

Shimer, C, Binary Space Partition Trees, in Worcester Polytechnic Institute Computer Science CS 563 '99 - Advanced Topics in Computer Graphics, accessed 05th November 2008 from < http://web.cs.wpi.edu/~matt/courses/cs563/talks/bsp/bsp.html >

References

Moore, G.E 1965, ‘Cramming more components onto integrated circuits’, from Intel Museum, accessed 20th October 2008, from < ftp://download.intel.com/museum/Moores_Law/Articles-Press_Releases/Gordon_Moore_1965_Article.pdf >

Sutter, H 2005, ‘A Fundamental Turn Toward Concurrency in Software’, in Dr. Dobb’s Portal, accessed 20th October 2008, from < http://www.ddj.com/architect/184405990>

Dubash, M 2005, ‘Moore’s Law is dead, says Gordon Moore’, from Techworld, accessed 20th October 2008, from < http://www.techworld.com/opsys/news/index.cfm?NewsID=3477 >

Hill, M.D. & Marty M.R. 2008, ‘Amdahl’s Law in the Multicore Era’, in IEEE Computer Society Digital Library, accessed 30th October 2008, from < http://www2.computer.org/portal/web/csdl/doi/10.1109/MC.2008.209 >

Granatir, O 2008, ‘Performance Scaling With Cores: Introducing the SMOKE Framework’, in Gamasutra, accessed 28th November 2008, from < http://www.gamasutra.com/view/feature/3861/performance_scaling_with_cores_.php >

Granatir, O 2008, ‘SMOKE – Game technology Demo’, in Intel what IF Experimental Software, accessed 28th November 2008, from < http://software.intel.com/en-us/articles/smoke-game-technology-demo >

Pas, R V D 2008, ‘An Overview of OpenMP 2.5’ in IWOMP Workshop, accessed 1st December 2008, from < http://cobweb.ecn.purdue.edu/ParaMount/iwomp2008/documents/3.Overview_OpenMP_HO.pdf >

Lewis, M.C & Massingill, B.L, 2006, ‘Multithreaded Collision Detection in Java’, from World Congress in Computer Science, Computer Engineering and Applied Computing, accessed 15th October 2008, from < http://ww1.ucmss.com/books/LFS/CSREA2006/PDP4236.pdf >

SMOKE Test

2008-12-01T13:31:00.002Z

On saturday I went and downloaded the source for SMOKE in order to see how it worked. 4Gbs of tech demo later along with a copy of Havok 5.5 Programmer tools SDK it is finally working.

On a Intel Dual Core 2.4 Ghz with an 86ooM GT graphics card with maximum threads running (two physical "hardware" threads) average FPS is around 15 or so. Cutting down to one thread further drops the frame rate to 8 or so. But heres the thing even at 8 FPS the camera and all controls were still responsive and the 3D scene was smoothe to navigate throught making the visibly apparent low frame rate in the scene bearable. From personal experence of using a PC with lower end graphics and processor harware a single threaded application that experiences a large scale frame rate drop like this can almost become unresponsive as input is only sampled once linking to how fast each frame can be completed.

The Intel test rig from the stated requirements:

CPU: Intel® Core™ 2 Quad Processor or better (Intel® Core™> i7 recommend)
GFX: NVIDIA 8800 GTS or better (Smoke was developed using 8800 GTS cards)
OS: 32-bit Windows XP or Vista
MEM: 2 GB of RAM of better
Optional: Stereo speakers, Xbox 360 controller for Windows
Software: Latest version of DirectX and .NET

From the SMOKE overview video avaliable from http://software.intel.com/en-us/articles/smoke-game-technology-demo
on that test rig it runs around 60 FPS. The problem here is determining how much of the application is bottlenecked by either the graphics card or the CPU.
Probably the next think that should be done with the Framework demo is to compile it in profiled mode on my own machine and find out where the bottleneck is.

SMOKE N-way threading for games

2008-11-28T16:27:00.004Z

Found an interesting article up on Gamasutra: Performance Scaling With Cores: Introducing the SMOKE Framework

Overall intel's SMOKE framework is somewhat like the current application conjecture on the Threading Manager Post. Partially the article is to push intel's newly released core i7 processor and show off its performance but depending on how complex or complete the framework is it may prove to be an alternative to using OpenMP for creating the multithreaded application.
The framework at a first glance from the website seems that it will take care of discerning the maximum number of threads and physical processing cores which was a consideration if the system would need to be programmed from scratch. Additionally it also at first glance seems to adhere to the pillars of concurrency.

Depending on how invasive the framework is its an ideal candidtate to handle all threaded processing for each of the applications that this research question will require. Its a factor that using this framework may take away a lot of the depth presented by this research question but on the other side of that would be a justification of why this framework was used over OpenMP to produce the multithreaded application. A framework such as this would introduce a large amount of overhead when compaired to a single threaded application but it may be possible to argue that overheads such as this will become a necessity.

Additional considerations from the research Presentation

2008-11-24T13:55:00.009Z

After performing the research presentation the following issues were asked about in the Q&A session:

How can you directly compare both the applications?
Are you aware of the overhead associated with building the working set for each thread?
Area or a volume, are you meaning a 2D or 3D simulation?

How can you directly compare both the applications?

I fumbled this question badly saying that it would all narrow down at some point. This was probably because the slides did not clearly explain how the applications would be compared.

Are you aware of the overhead associated with building the working set for each thread?

Before the presentation I had spent time thinking about this so the questions wasn't too troublesome, there wasn't time to answer the question in as much detail as the blog post but hopefully the problems I had found were apparent.

Area or a volume, are you meaning a 2D or 3D simulation?

This was purely my own fault for mixing up terminology. But this was covered easily by saying that if it was needed the application could be scaled back into 2D if the 3D approach caused too many problems.

Alterations

It is clear from this I may need to rethink a few parts of my research question and clarify how the applications would be compared.

In the presentation slides it states that the applications would be compared on theorised speed up obtained from the single threaded graphics application.

In order to find the percentage of the program that would be parallelised over one frame the code would be profiled to find out how long it spent calculating collisions on that frame. And the percentage of the program that would be parallelised would be found by dividing the time it took to process collision by the amount of time for one frame.

This can then be used to find how much of the program is performed in serial orderby doing:

Serial=(1-(Time for collisions/Time for single frame))

And applying Amdahl's law to achieve maximum speed up using N processors:

Max Speed Up=((Time for collisions/Time for single frame)/N)

Therefore:

Speed up( (Time for Collisions/Time for Single frame), N)

= 1/(Serial+Max Speed Up)

The problem when comparing is that unless collision is sampled every frame (highly unlikely, but it is usually the stance I take due to inexperience) it makes comparisons very difficult.

Assume that both applications are limited to 60 frames per second (in the multithreaded application only the main thread doing the rendering and such is frame limited).

Consider the single threaded application sampling collisions once every 10 frames and that there are no high speed collision problems (in that a collision could take place in-between collision samples). Every 10 frames there will be a performance spike in which the collision detections takes place, ideally this is the frame that would be sampled to give the amount of time that is spent calculating collision detection.

Now consider the multithreaded application that will sample at the same rate again with no high speed collision problems. Now instead of a single frame the multithreaded application will process collisions over a maximum of 10 frames before the next sample is due. Is it then fair to take a single frame when the collisions are being calculated in parallel and use that to calculate the speed up and thus give the performance or take the sum of the time spend on multithreaded calculations over the 10 frames?

Taking the time in one frame spent on multithreaded collision calculations here means that only a fraction of the calculations will be done this would be considered fair if all of the calculations could possibly be done by the multithreading system within this one frame but that cannot be guaranteed. Taking the time over all of the frames until either the multithreaded system signals that its finished or the next collision sample starts may mean with the working set of each thread possibly containing duplicates as explained in the blog post that was stated above may increase overall calculation time giving the impression that the multithreaded program is actually less efficient than the single threaded one.

Calculating the improvement would be:

The Serial part of the program will be as before in getting the expected performance improvement from the single threaded application.

Then obtain the amount that the application has been speeded up by:

Speed Multiplier= (Time for collisions/Multithreaded collision time)

Therefore you can find the amount of time for the multithreaded part of the program:

Multithreaded part time= ((Time for collisions/Time for single frame))/Speed Multiplier)

(Where the Time for collisions and Time for single frame are from the single threaded application)

And then applying Amdahl's law gives:

Speed up((Time for collisions/Time for single frame, Speed Multiplier)

= 1/(Serial+Multithreaded part time)

One of the most major considerations is that most of the material on parallel processing consider that the users program has exclusive access to the processor(s) at all times where with threading in windows all of the threads are handled by the operating system meaning that they are not strictly "Hardware Threads" (in that its a direct instruction pipeline like in the PS2 there are 3 possible Hardware Threads each with their own set of instructions on the EE) meaning that the operating system will handle any load imbalances between processing cores increasing overhead. OpenMP may provide access to a hardware thread but it is currently still being looked into.

Overheads

Each of the applications will have some overhead, the single threaded application overhead being discerning which object is within the current BSP volume (fixed terminology there) and the multithreaded overhead being building the working set for each thread as well as the overhead associated with windows controlling the threads.

This would be a possible area of comparison as regardless of what is happening per frame the overhead is always there.

As objects move on the single threaded application they may move into different BSP volumes thus need to be reclassified so that more detailed collision detection will occur for this object
Windows will always be managing the threading overhead (if the first frame starts a collision detection sample) with an additional overhead spike when the working sets for the next collision detection sample are created

Conclusion

With these two considerations taking into account it may be best to change the research question to something along these lines:

What are the Considerations with respect to Overhead and serialisation
performance between a single threaded application and a multithreaded
application where both are processing the same 3D scene where a large number of
collisions are occurring?

The problem with this like with my previous is that it is not clear that the single threaded application is using BSP to cull collisions and the multithreaded application processing collisions without any culling.

Research Presentation

2008-11-17T11:33:00.008Z

Today is the research presentations, heres the most recent version of what I will present along with the notes: [Link Removed, somone churned up all my bandwidth]

After doing some dry runs of the project presentation as a group on friday from the presentation of http://yeraveragejoe.blogspot.com/ hightlitghted somthing that hadn't been considered yet:

How to split up the collisions between various threads

Initially it was hoped that reading on multithreaded theroy may provide a difinitve answer as how to split up all of the collision tasks but after hearing the project presentation from http://yeraveragejoe.blogspot.com/ it may not be so straightforward as to pick one strategy as it seems to be highly situational depending on the application it is to be applied to. It also highlights that Collision Detection may not be inherently parallel but may require additional considerations for each application.

Multithreaded Collision Detection in Java (Lewis & Massingill 2006) highlights this problem stating that collision detection is sequential based on the time meaning that at any given time any object can collide with any other and is dependant on the previous collisions. This is then used to create the working set for each thread by finding all the particles that could collide within one time step and segregating them into different cells. Each cell is then processed by the threaded system.

The problem for porting this approach to the current project is that applying Callahan's first pillar of concurrency (Sutter 2007): that the application must be responsive to the user at all times means that collision detection parralelisation must allow the program to continue operation. This means that the size of each working set would be directly linked to how often collision detection is sampled. The lower the collision detection samples per frame the larger each working set for each thread would be.

An example:

A high volume of objects that can collide with each other in a 3D enviroment (assume that collision with the boundaries is inherent at the moment) each moving along a vector at 0.1 per frame on a 60 FPS application. That means in one second each object has the possibility of moving 6 units in any direction. Momentum is also preserved after each collision.

If collison detection is sampled every 10 frames that means that each working set will include anything within a 1 cubed area (with additional objects that could cross into the area such as objects that are not quite fully within the area). The more frequent the samples the smaller each working set. Sampling ever 5 frames would mean that each working set would contain everything within a 0.5 cubed area. Preserving momentum for each collision means that working sets will be a constant size at all times during the application.

This also assumes that a thread per object which upon using a high volume of objects would overwhelm the system with overhead. Additionally this assumes that collision detection processing will finish before or as the next sample interval starts.

It then may be possible to create processing cells for each object based on a certain interval based on inital position but then it is possible that objects that are far away from any other may be missed.

From this working set will become a major consideration and impact on performance depending on the amount of overhead used to create each threads working sets.

References

Lewis, M.C & Massingill, B.L, 2006, ‘Multithreaded Collision Detection in Java’, from World Congress in Computer Science, Computer Engineering and Applied Computing, accessed 15th October 2008, from < http://ww1.ucmss.com/books/LFS/CSREA2006/PDP4236.pdf >

Sutter, H 2007, ‘The Pillars of Concurrency: Building a consistent mental model for reasoning about concurrency’, in Dr. Dobb’s Portal, accessed 20th October 2008, from < http://www.ddj.com/architect/200001985 >

Worksheet 4 feedback

2008-11-13T13:40:00.003Z

CS1004A-Honours Project Planning and Reporting
Worksheet 4

Introduction

With the current generation of game consoles and personal computers multiple processing cores are a standard but currently the industry is still adapting to the new technology. Collision detection can be one of the most time consuming processes within a computer game due to the number of objects that could be in a scene at any time that could collide with others, currently advanced algorithms are used to reduce the number of collision tests that may have to be performed at any point during the game but can the current expansion into multi-processor architecture make these techniques obsolete and provide more accurate collision simulation?

The main focus of this research project will be on the ways to process collision detection in a multi-processor architecture using the threading system provided within windows. A performance comparison will be made between the multi-threaded application and the single threaded one to discern which one performs better.

Issues

Concurrency between threads processing large volumes of data
Theorised speedup of the multi-threaded application defined by Ahmdal’s law compared to the actual application performance increase and reasons why this is the same or less than estimated.
Scalability of large volume data processing over several threads
Processing of exponential explosion of possible colliding objects

Research question

In comparison can a multi-threaded application outperform a single threaded application when both are rendering the same 3D scene where there are a large number of collision tests occurring?

Addressing the Question

Two graphics applications need to be created:
One single threaded application that will cull the number of collisions occurring in the scene to be processed using BSP
A multi-threaded application that will process all collisions in the scene no matter their location
Each will process a large number of collision tests using the methods described above, the objects colliding will be simple primitives. Colliding objects will be spaced equally through the scene.
An external 3rd party library will be used to build the BSP trees required by the single threaded application. Because of how BSP will be used to cull collisions the area that the objects will collide in will have to be split into discreet areas that can be isolated into different sections of BSP. The area that will not cull any collisions will be defined by the location of the camera/viewer; any collisions outside this area will only collide with the external bounding of the area. Collision of the objects with the bounding of the areas will be defined by radial collision providing a quick calculation, collision between objects will be defined by axis aligned bounding boxes. As objects no matter of their location will collide with the bounding of each area there will be a constant number of collisions to server as a basic benchmark for each application. Each object after colliding with either the bounding of the area or another object will pick a semi realistic direction to rebound from the collision. Each collision will be elastic for each of the objects colliding meaning that objects in the scene should never stop moving. Collision detection will be performed after a certain number of frames

From this application an average frame rate will be obtained and this frame rate used to obtain how long a single frame takes to process all the collision detection and rendering of the scene. Also the amount of time within one frame that is spent on processing collision detection will need to be found possibly by profiling the code. The amount of time for collision processing will be considered the % of the application per frame that the application can be parallelised. Thus the theorised speedup of the parallelisation of this application can be estimated using Ahmdal's Law (Hill & Marty 2008).

After obtaining the theorised speed up the creation of the multi-threaded application will start. This will create the same scene as the multi-threaded application yet processes all of the collisions using a multi-threaded methodology obtained from research. The multi-threaded system should be scaleable to different processor configurations and be able to effectively split up the collisions into separate threads while preserving concurrency between them. Collisions will be processed after the same number of frames as the single threaded application but if by the next collision detection sample the application will either block and wait for all threads to finish processing the collision detection or will be discarded and start again with the current object positions (probably not advisable on discarding the current collision detection calculations).

The time that it takes per frame will be obtained from the multi-threaded application and compared to the theorised speed up from the single threaded application depending on the results returned from the programs will answer the research questions taking into account the overhead, flexibility and feasibility over the BSP collision culling method.

Additionally if time permits other testing scenarios could be devised in order to provide more situations where it may be possible that either application will perform better than the other. Examples with the areas that the objects are colliding in could be:
Where all the collisions are happening in a single BSP area
Where collisions are more wide spread over a larger number of BSP areas
As well as these changes to the area that the objects are colliding in also the number of colliding objects could be varied between a low, medium and high number of collision detections that could happen in the scene.

I was wondering if you might want to investigate whether more complicated/accurate collision detection algorithms make an impact. They might make a difference in terms of altering the working set of the thread. I am sure there are well documented implementations available on the internet. Would things like scale of objects possibly make a difference as well?

Progress

Currently a major amount of the multi-threading/parallel processing theory has been from online journal articles. This material (Sutter 2005) has lead to the theorisation of a threading manager system that would be used for the multi-threaded application that would handle:
· Creation and destruction of threads
· Keeping track of all running threads
· Splitting scaleable tasks into separate threads
· Returning the results of the processed threads to the main application

Although this threading manager system provides a viable solution to the problem more research is required into the concurrency factor of this program as if each thread has a chance of locking data that could cause major performance problems making it pointless to parallelise the application. A possibly stumbling block may be the fact that within windows it will discern the best way to process the threads that the application creates and also that most parallel processing theory is based on that a single application has exclusive access to all of the CPU(s) on a system.
At the moment there is only once source that states that a threading manager of this nature would be the best implementation for solving the problems thus more research needs to be done to finalise this approach.

Have you considered using the OpenMP (http://openmp.org/wp/) library, it provides a a variety of useful multithreading primitives. Might save you a bit of development time on the lower level stuff.

A 3rd party library needs to be chosen for the single threaded application and depending of the BSP implementation may define the graphics API to be used to render the scene and the collisions.

Current factors to answer the research questions (the amount of time required per frame and the theorised speed up using Amdahl’s Law) will need to be discussed with a technical supervisor in order to discern if they would carry enough weighting to answer the question to a satisfactory level. Additionally it will need to be taken into consideration the time to build the BSP trees and that the threaded application will be processing collision detection over a number of frames.

Bibliography

Sutter, H 2005, ‘A Fundamental Turn Towards Concurrency in Software’, in Dr. Dobb’s Portal, accessed 20th October 2008, from < http://www.ddj.com/architect/184405990>

Hill, M.D. & Marty M.R. 2008, ‘Amdahl’s Law in the Multicore Era’, in IEEE Computer Society Digital Library, accessed 30th October 2008, from < http://www2.computer.org/portal/web/csdl/doi/10.1109/MC.2008.209 >

I’m not familiar with the BSP technique but conceptually it does seem like collision detection is something that should scale well across multiple cores.

Currently the only thought to how the threads would be handled was the possiblity of using C# but an additional implimentation using OpenMP might allow for the first iteration of the current concept discussed previously to be easily tested.
As for more accurate collision detection a hight speed collision problem may be a worthwhile example to look into

Worksheet 4

2008-11-10T17:26:00.005Z

CS1004A-Honours Project Planning and Reporting
Worksheet 4

Introduction

With the current generation of game consoles and personal computers multiple processing cores are a standard but currently the industry is still adapting to the new technology. Collision detection can be one of the most time consuming processes within a computer game due to the number of objects that could be in a scene at any time that could collide with others, currently advanced algorithms are used to reduce the number of collision tests that may have to be performed at any point during the game but can the current expansion into multi-processor architecture make these techniques obsolete and provide more accurate collision simulation?

The main focus of this research project will be on the ways to process collision detection in a multi-processor architecture using the threading system provided within windows. A performance comparison will be made between the multi-threaded application and the single threaded one to discern which one performs better.

Issues

Concurrency between threads processing large volumes of data
Theorised speedup of the multi-threaded application defined by Ahmdal’s law compared to the actual application performance increase and reasons why this is the same or less than estimated.
Scalability of large volume data processing over several threads
Processing of exponential explosion of possible colliding objects

Research question

In comparison can a multi-threaded application outperform a single threaded application when both are rendering the same 3D scene where there are a large number of collision tests occurring?

Addressing the Question

Two graphics applications need to be created:

One single threaded application that will cull the number of collisions occurring in the scene to be processed using BSP
A multi-threaded application that will process all collisions in the scene no matter their location

Each will process a large number of collision tests using the methods described above, the objects colliding will be simple primitives. Colliding objects will be spaced equally through the scene.
An external 3rd party library will be used to build the BSP trees required by the single threaded application. Because of how BSP will be used to cull collisions the area that the objects will collide in will have to be split into discreet areas that can be isolated into different sections of BSP. The area that will not cull any collisions will be defined by the location of the camera/viewer; any collisions outside this area will only collide with the external bounding of the area. Collision of the objects with the bounding of the areas will be defined by radial collision providing a quick calculation, collision between objects will be defined by axis aligned bounding boxes. As objects no matter of their location will collide with the bounding of each area there will be a constant number of collisions to server as a basic benchmark for each application. Each object after colliding with either the bounding of the area or another object will pick a semi realistic direction to rebound from the collision. Each collision will be elastic for each of the objects colliding meaning that objects in the scene should never stop moving. Collision detection will be performed after a certain number of frames

From this application an average frame rate will be obtained and this frame rate used to obtain how long a single frame takes to process all the collision detection and rendering of the scene. Also the amount of time within one frame that is spent on processing collision detection will need to be found possibly by profiling the code. The amount of time for collision processing will be considered the % of the application per frame that the application can be parallelised. Thus the theorised speedup of the parallelisation of this application can be estimated using Ahmdal's Law (Hill & Marty 2008).

After obtaining the theorised speed up the creation of the multi-threaded application will start. This will create the same scene as the multi-threaded application yet processes all of the collisions using a multi-threaded methodology obtained from research. The multi-threaded system should be scaleable to different processor configurations and be able to effectively split up the collisions into separate threads while preserving concurrency between them. Collisions will be processed after the same number of frames as the single threaded application but if by the next collision detection sample the application will either block and wait for all threads to finish processing the collision detection or will be discarded and start again with the current object positions (probably not advisable on discarding the current collision detection calculations).

The time that it takes per frame will be obtained from the multi-threaded application and compared to the theorised speed up from the single threaded application depending on the results returned from the programs will answer the research questions taking into account the overhead, flexibility and feasibility over the BSP collision culling method.

Additionally if time permits other testing scenarios could be devised in order to provide more situations where it may be possible that either application will perform better than the other. Examples with the areas that the objects are colliding in could be:

Where all the collisions are happening in a single BSP area
Where collisions are more wide spread over a larger number of BSP areas

As well as these changes to the area that the objects are colliding in also the number of colliding objects could be varied between a low, medium and high number of collision detections that could happen in the scene.

Progress

Currently a major amount of the multi-threading/parallel processing theory has been from online journal articles. This material (Sutter 2005) has lead to the theorisation of a threading manager system that would be used for the multi-threaded application that would handle:
· Creation and destruction of threads
· Keeping track of all running threads
· Splitting scaleable tasks into separate threads
· Returning the results of the processed threads to the main application

Although this threading manager system provides a viable solution to the problem more research is required into the concurrency factor of this program as if each thread has a chance of locking data that could cause major performance problems making it pointless to parallelise the application. A possibly stumbling block may be the fact that within windows it will discern the best way to process the threads that the application creates and also that most parallel processing theory is based on that a single application has exclusive access to all of the CPU(s) on a system.
At the moment there is only once source that states that a threading manager of this nature would be the best implementation for solving the problems thus more research needs to be done to finalise this approach.

A 3rd party library needs to be chosen for the single threaded application and depending of the BSP implementation may define the graphics API to be used to render the scene and the collisions.

Current factors to answer the research questions (the amount of time required per frame and the theorised speed up using Amdahl’s Law) will need to be discussed with a technical supervisor in order to discern if they would carry enough weighting to answer the question to a satisfactory level. Additionally it will need to be taken into consideration the time to build the BSP trees and that the threaded application will be processing collision detection over a number of frames.

Bibliography

Sutter, H 2005, ‘A Fundamental Turn Towards Concurrency in Software’, in Dr. Dobb’s Portal, accessed 20th October 2008, from < http://www.ddj.com/architect/184405990>

Hill, M.D. & Marty M.R. 2008, ‘Amdahl’s Law in the Multicore Era’, in IEEE Computer Society Digital Library, accessed 30th October 2008, from < http://www2.computer.org/portal/web/csdl/doi/10.1109/MC.2008.209 >

Deliverables thoughts

2008-11-10T16:35:00.009Z

Something to think about would be the minimum deliverables required to submit at the end of this research project first thoughts would be as follows:

Minimum submission: Single threaded application with theorised application performance increase upon parallelisation of collision detection. As well as possible non working multi-threaded application.

Mid range submission: Single threaded application and multi-threaded application along with a comparison between theorised increase in performance against actual performance increase (or decrease)

High range submission: Single threaded application and multi-threaded application complete. A comparison between theorised performance increase against actual performance increase under different circumstances (different scenes and number of collisions occurring) providing an overall view of where its possible that multi-threading may have advantages over a more complex culling technique or vies-versa.

Worksheet 4 is also currently done and will be up after a re-read

Worksheet 3 feedback

2008-11-05T14:59:00.003Z

CS1004-Honours Project Planning and Reporting
Worksheet 3

Introduction
[Jonathon 1] To discern if more complex collision culling techniques can be made obsolete by the current generation of multiple processor architectures.

Motivation
The current generation of home computer processors and games consoles all make extended use of multiple processor computer architectures yet within the PC market computer applications are only just beginning to take full advantage of this. The current shift into parallel processing has been triggered by the industry starting to reach the limits of Moore’s law (Dubash 2005), in a multiple processor architecture Moore’s law does not apply and instead the limitations of a multi-processor architecture are governed by Amdahl’s law (Hill & Marty 2008). This shift in processor architectures changes the entire way that applications that are designed. Collision detection is possibly one of the best examples of an operation that would be easily offloaded and scaled to multiple processor architecture through using one of the base principles of concurrency of scaling small repetitive tasks that are not essential to program operation (Sutter 2007). Removing the culling of collisions based on certain conditions would increase the accuracy of simulations making them seem more realistic.

Research question
[Jonathon 2] In comparison can a multi-threaded application on a multiple processor architecture processing a large volume of collisions in a brute force method out perform a single threaded application processing the same number of collisions using a more advanced collision culling technique?

Addressing the Question
[Jonathon 3]

Two applications will be created:
One multi-threaded application using a threading methodology created through research of multi-threading theory
A single threaded application that will use BSP to cull the number of collisions tests happening.

Each application will render an area with different sections each with a high number of collision detections happening within them. The different areas are to allow the single threaded application to effectively use BSP collision culling.
Collision occurring will be simple radius collision or axis aligned bounding box collision. The multi-threaded application will process all collisions at all times while the single threaded application will only process collisions between the separate objects when in the same BSP area as the viewer. If the objects are out with the BSP area of the viewer only collision with the bounding of the area the object is in will occur.
The applications will be assessed on their performance under these conditions; additionally a system may be created to allow the user to see the thread utilisation and additional information that will be used to make the comparison.
It’s undecided at the moment if Direct X D3D or Open GL will be used to display the graphics side of the application.

Resource Requirements
At minimum a single core machine about the level of a mid range P4 and a dual core machine to ensure that the single threaded application’s operations are only being processed on a single core.

References and Bibliography

Wilson, K 2006, ‘Managing Concurrency: Latent Futures, Parallel Lives’; from Game Architect.net, accessed 20th October 2008, from < http://www.gamearchitect.net/Articles/ManagingConcurrency1.html >

Moore, G.E 1965, ‘Cramming more components onto integrated circuits’, from Intel Museum, accessed 20th October 2008, from < ftp://download.intel.com/museum/Moores_Law/Articles-Press_Releases/Gordon_Moore_1965_Article.pdf >

Dubash, M 2005, ‘Moore’s Law is dead, says Gordon Moore’, from Techworld, accessed 20th October 2008, from < http://www.techworld.com/opsys/news/index.cfm?NewsID=3477 >

Hill, M.D. & Marty M.R. 2008, ‘Amdahl’s Law in the Multicore Era’, in IEEE Computer Society Digital Library, accessed 30th October 2008, from < http://www2.computer.org/portal/web/csdl/doi/10.1109/MC.2008.209 >

Sutter, H 2007, ‘The Pillars of Concurrency: Building a consistent mental model for reasoning about concurrency’, in Dr. Dobb’s Portal, accessed 20th October 2008, from < http://www.ddj.com/architect/200001985 >

Gabb, H & Lake, A 2005, ‘Threading 3D Game Engine Basics’, in Gamasutra, accessed 20th October 2008, from < http://www.gamasutra.com/features/20051117/gabb_01.shtml>

Mönkkönen, V 2006, ‘Multithreaded Game Engine Architectures, in Gamasutra, accessed 20th October 2008, from < http://www.gamasutra.com/view/feature/1830/multithreaded_game_engine_.php>

[Jonathon 1]Nice. Definitely a good idea

[Jonathon 2]The idea behind the question is sound but the wording is pretty jumbled. Might be an idea to completely re-structure the question to make it easier to read.

[Jonathon 3]I don't know if you've already thought of this but to save time you could use some form of library (DLL ?) for the collision routines and just load in either the multi-threaded or single threaded versions depending on the system. Just a suggestion.

So the main points I need to think about is restructuring the question and creating a DLL or Lib in order to cut creation time. I was hoping to be able to use a library for the collision culling technique but hadn't actualy thought too much about doing the same for the collision which ofcourse will be the same accross both applications.

Worksheet 3

2008-11-03T12:02:00.001Z

Introduction
To discern if more complex collision culling techniques can be made obsolete by the current generation of multiple processor architectures.

Motivation
The current generation of home computer processors and games consoles all make extended use of multiple processor computer architectures yet within the PC market computer applications are only just beginning to take full advantage of this. The current shift into parallel processing has been triggered by the industry starting to reach the limits of Moore’s law (Dubash 2005), in a multiple processor architecture Moore’s law does not apply and instead the limitations of a multi-processor architecture are governed by Amdahl’s law (Hill & Marty 2008). This shift in processor architectures changes the entire way that applications that are designed. Collision detection is possibly one of the best examples of an operation that would be easily offloaded and scaled to multiple processor architecture through using one of the base principles of concurrency of scaling small repetitive tasks that are not essential to program operation (Sutter 2007). Removing the culling of collisions based on certain conditions would increase the accuracy of simulations making them seem more realistic.

Research question
In comparison can a multi-threaded application on a multiple processor architecture processing a large volume of collisions in a brute force method out perform a single threaded application processing the same number of collisions using a more advanced collision culling technique?

Addressing the Question
Two applications will be created:

One multi-threaded application using a threading methodology created through research of multi-threading theory
A single threaded application that will use BSP to cull the number of collisions tests happening.

Each application will render an area with different sections each with a high number of collision detections happening within them. The different areas are to allow the single threaded application to effectively use BSP collision culling.
Collision occurring will be simple radius collision or axis aligned bounding box collision. The multi-threaded application will process all collisions at all times while the single threaded application will only process collisions between the separate objects when in the same BSP area as the viewer. If the objects are out with the BSP area of the viewer only collision with the bounding of the area the object is in will occur.
The applications will be assessed on their performance under these conditions; additionally a system may be created to allow the user to see the thread utilisation and additional information that will be used to make the comparison.
It’s undecided at the moment if Direct X D3D or Open GL will be used to display the graphics side of the application.

Resource Requirements
At minimum a single core machine about the level of a mid range P4 and a dual core machine to ensure that the single threaded application’s operations are only being processed on a single core.

References and Bibliography

Wilson, K 2006, ‘Managing Concurrency: Latent Futures, Parallel Lives’; from Game Architect.net, accessed 20th October 2008, from < http://www.gamearchitect.net/Articles/ManagingConcurrency1.html >

Moore, G.E 1965, ‘Cramming more components onto integrated circuits’, from Intel Museum, accessed 20th October 2008, from < ftp://download.intel.com/museum/Moores_Law/Articles-Press_Releases/Gordon_Moore_1965_Article.pdf >

Dubash, M 2005, ‘Moore’s Law is dead, says Gordon Moore’, from Techworld, accessed 20th October 2008, from < http://www.techworld.com/opsys/news/index.cfm?NewsID=3477 >

Hill, M.D. & Marty M.R. 2008, ‘Amdahl’s Law in the Multicore Era’, in IEEE Computer Society Digital Library, accessed 30th October 2008, from < http://www2.computer.org/portal/web/csdl/doi/10.1109/MC.2008.209 >

Sutter, H 2007, ‘The Pillars of Concurrency: Building a consistent mental model for reasoning about concurrency’, in Dr. Dobb’s Portal, accessed 20th October 2008, from < http://www.ddj.com/architect/200001985 >

Gabb, H & Lake, A 2005, ‘Threading 3D Game Engine Basics’, in Gamasutra, accessed 20th October 2008, from < http://www.gamasutra.com/features/20051117/gabb_01.shtml>

Mönkkönen, V 2006, ‘Multithreaded Game Engine Architectures, in Gamasutra, accessed 20th October 2008, from < http://www.gamasutra.com/view/feature/1830/multithreaded_game_engine_.php>

Worksheet 3 and Research Questions

2008-10-30T14:17:00.004Z

Currently doing Worksheet 3 in preperation for the Research Question presentations within the next two weeks.

One thing that has come up from writing the worksheet is a more solid research question:

In comparison can a multi-threaded application on a multiple processor architecture processing a large volume of collisions in a brute force method out perform a single threaded application processing collisions using a more advanced collision culling technique?

Worksheet 3 should be up on here in the next couple of days as well as sent off for annotation.
My most recent meeting with my technical supervisor has confirmed ideas that I thought of to define my areas of research.
Additionally our blogs are shifting internal into webspace provided by the university so no idea whats going to happen to this blog once that happens.

Speculation on a possible application

2008-10-27T15:20:00.005Z

After reading Dr Dobb's Journal: The Pillars of Concurrency I've been thinking about the actualy application that will be created to proof the multithreading aspect of this research project. Possibly quite a lot of this is speculation along with the small amount of knowledge on the subject from a 2nd year module: Computer Operating Enviroments. As well as this may be getting too far ahead of where the current focus should be: defining the research question and topics.

The original idea for the application was that collision would be split from the main thread of the application (rendering,AI, game logic) and processed by threads based on a method obtained from research.
The article above states there are three main aspecs of multithreaded applications:

The application is always responsive to the user
Aspects of the application are scaleable over multiple processors/threads to increase throughput
Application resources are shaired safely between threads

The original idea above would only cover two of these aspects 1 and 3. Application responsiveness is gained throught extracting the possible and the shairing of resources safely must be planned for inhernetly between threads otherwise the application will run into major problems.

Aspect 2 is not catered for in this application. For a PC with a dual core processor this approach fufills aspect 2 but if more than two cores are present on the system the application will not take advantage of the additional cores itself. Alterting the application so that the collision is processed by a Threading Manager would help to solve this problem.

A Threading Manager would allow the application to scale to multiple processors inherently but comes with its own problems.

Capabilites of a Threading Manager (assuming that each thread will be processing the same sort of data) :

Creation and destruction of threads
Keep track of all running threads
Splitting scaleable tasks into seperate threads
Returning the results of the processed threads to the main application

Things that need to be thought about for a Threading Manager:

What is the goal of each thread?
How can the maximum number of threads be defined?
How can scaleable jobs be split into threads?
How will data be returned to the main application thread?
How will concurrency be preserved between the main application thread and the Threading Manager's thread pool?

Programming characteristics :

Portable
Adaptable for different tasks

In order to be adaptable for different tasks it will be necessary to have the user program small protable functions to load, process the data and then pass the data back to the main program. From there the Threading Manager would utilise those functions to process all of the scaleable tasks. Additionally this may mean that it would be possible to have the Threading Manager process many different types of scaleable tasks in different ways at the same time.

In order to refocus after this detour I will need to read the article that inspired this project again and reconsider how to define the reasons that collision would be suitable as the a scaleable part of the application.

Some reasons why

2008-10-20T13:24:00.003+01:00

As part of the proposal I will need to justify my research topic.
Essentially my topic requires two areas to be justified:

Why Multiprocessor architecture?
Why Collision?

The first is easily justified through looking at Moore's Law (http://en.wikipedia.org/wiki/Moores_law) which states that the number of transistors on a microchip will increase exponentially doulbing the number every two years. This has mostly stayed true since it was theorised in a paper in 1965(ftp://download.intel.com/museum/Moores_Law/Articles-Press_Releases/Gordon_Moore_1965_Article.pdf).

The problem occurs when the limits of this law are reached and the size of transistors on a microchip are on the atomic scale with the current chip fabrication process. This means that making the transistors any smaller will impede the electric current meaning that electrons can not flown throught the microchip. Until another fabrication process becomes cost effective comparied to the current one ,once the limit is reached , multiple microchip architectures will be one of the ways to increase performance. Already the current generation of microprocessor chips consist of two or more seperate processing 'cores'.

But increasing the number of processing 'cores' on a microchip creates its own problems with concurrency and organisation of data. This is one of the problems that will need to be addressed in the creation of the test applications.

Collision detection still needs defined as this will be the first thing that will be questioned.

Additionally the research question still needs to be looked at and changed from an aim to be more focused as a question.

Worksheet 2 Initial comments

2008-10-15T13:35:00.004+01:00

Just got the first set of comments back on worksheet 2:
On the research Question:

Good but this seems more of an aim rather than a research question. Try and see if you could possible reduce it down a bit more.

On the Project focus, infomation and experemental work:

Seems all ok. You know what information you need to research up on and how to implement this information into an application.

On interperting the results:

Sounds good. Like the idea of having the two applications so you can compare the differences between the two. Also gives you something to write up on in your report.

So the main thing I need to concetrate on is fixing the research question.

Reading material

2008-10-14T15:59:00.004+01:00

It looks like that there may not be many articles dedicated to multi threading the processing of collision detection. This means that standard multithreading theroy should be researched and then applied to processing collision detection.

The other glaring problem is when presenting to the panel for the proposal the first thing they will question is "Why Collision Detection processing?". There really needs to be a good reason for doing this approach.

Worksheet 2

2008-10-12T14:01:00.000+01:00

1. Formulate a research question for your project. Details on the research question can be found in presentation 1 in the module folder.
With the current generation of game consoles and personal computers multiple processing cores are a standard but currently the industry is still adapting to the new technology. Collision detection can be one of the most time consuming processes within a computer game due to the number of objects that could be in a scene at any time that could collide with others, currently advanced algorithms are used to reduce the number of collision tests that may have to be performed at any point during the game but can the current expansion into multi-processor architecture make these techniques obsolete?

2. When developing a research question you must produce a question that can be answered by performing literature research, practical experimentation and critical analysis. The question should also focus the activities of your project.

a) What is the focus of your project?
The processing (threading in this case) of collision detection within a game engine
b) What information do you need to find out about?
Are there any current threading methodologies that have been used to perform this? Different collision culling techniques to compare to.
c) What Experimental work do you need to perform?
Create a multi threaded application that tests every object in the scene for collision creating an exponential amount of collision tests. Two or three different approaches will be considered but its possible only one approach will be created. Also create a single threaded application that uses a more complex collision culling method.

3. How will the information that you obtain in 2 allow you to answer the research question?
The research into different threading methodologies will allow view of what is possible but from there either thought reading on other peoples work on implementing these methodologies or actually attempting to prototype them before creating the final multi threaded application will allow me to answer the question. Between the threaded and non-threaded version a comparison will be possible comparing CPU usage and frame rate of the each application. Other criteria for assessing both applications will be needed, this may include considering the overhead required for each method and other requirements. It may be best to set a scenario first of all with certain criteria such as a game engine that will be handling a high number of collisions per frame, the target platform is a standard users PC which will use an average price dual core processor and 2Gb of RAM. Problems will be apparent with simulation of the resources used by additional processes such as AI and Rendering.

Provisional Research Question v0.5

2008-10-08T16:37:00.007+01:00

Currently running through worksheet 2 at the moment after having a meeting with Mr Bett about proposed research for my honours project.
The research topic seems to be ok with the only glaring problem may be that its too clean cut to provide an interesting discussion.
Additional things I have to think about that might have a major impact on the probject would be

The effects of other game processes on the collision threading (AI/Rendering/ect)
C# may be preferable if C++ proves too complex with the concurency
PS3 a large chance is that this would be an example of further research but depending on how the research and creation of the proof tests it may be a point to think about

Things still to think about:

What approaches to multi-threading? (2-3 possibly)
What collision culling technique to use for the single threaded model
How many collision tests per frame would be considered "High Volume"

Hopfully during the research it will narrow down to a single viable threaded approach so that the comparison will be between that approach and the single threaded more complex algorithm.

On some thought to the collision culling technique for the single threaded model, it may be best to research a technique and then use an open source library that will perform this function in order to reduce the amount of time spent creating the single threaded application.

Another thing to rember that the main body of research is not into collision techniques but into how that a multi-processor architecture can process a large number of operations without effecting performance too drasticly.

Should have an actual Provisional Research Question later on this week.

Additional thought 1: Why Collision? Why not rendering or AI?

Worksheet 1 Final Feedback

2008-10-06T14:37:00.004+01:00

Finaly I got the final feeback from worksheet 1. Its as Follows:
I think this has been well commented. I like the first topic certainly sounds very interesting. Can you talk to Mr Bett/Dr H Fortuna about the first and the second one please. I am not too sure about the third one though.

Definiately the first issue was the most thought throught and would be the one I would possibly push for creating a question for as much as possible. The second issue would be the less interesting but possible easier to discern whats quantifiable from the project. As for the third issue it was rushed and wasn't really considered as a possibilty, it was mostly there to flesh out the worksheet and give a third option that was hugely different from the other two.

Next thing to do would be to get in touch with one of my provisional technical supervisors with a selection of questions about each of the first two issues. Hopfuly I can get a meeting quickly and then begin to form the questions for the basis of worksheet 2. As well as this Friday the internet should be restored at my flat allowing easier searching for technical papers on the subject in my own time.

Issue 1 Resolver

2008-10-03T14:07:00.003+01:00

I've been thinking about issue one on worksheet 1 (see prev posts) and have thought of a way to extend it.

A comparison between two methods of optimising collision detection. Both applications will have to process a high number of collision tests within either 2d or 3d space. One application will use a brure force approach checking every object against every other object, the collision of the objects will be processed by a threaded system and then be returned to the main program. The other application will use a more complex collision culling algorithm such as BSP trees before performing the collision tests. The main research areas of this project would be into creating a multi threaded system for a collision engine and different types of collision culling. Factors contributing to the evaluation of each approach would be : application performace defined by the number of frames rendered per second, ease of implimentation, overhead required required for each approach and technical considerations.

Of course it may not be feasable to compair these two implimentations and thus it may be better to compair several different types of collision culling but worksheet 2 is due in by the 12th oct and I'm still to get additional feedback on worksheet one from my lecturer

Worksheet 1 Feedback

2008-10-01T14:18:00.006+01:00

Just got feedback from my worksheet from the other member of my class.
On part 2 Issues surrounding the topic, my third options:

This should be expanded a bit more, event programming is a bit vague. It would have to be explored more to see if there was enough for the project.

And the final overall comment:

The issues surrounding the topic look fine and there are a few issues defined within each of the possible areas to perform an investigation into. However a good bit more research into some of these specific issues would have to be conducted to see if they are viable options for an honors project.

It may be worth while to think about what sort of demo application you would want to create for your project as this may help to give a better insight into what could be done in the time scale.

As commented above viability is a large issue here as well as it is possible I may be stepping outwith the bounds of a CGT honours project. Initaly the first idea was almost not used as it creates a problem with what is quantifiable with the results and this is also true for the other two issues. For the first and the thrid there is a chance that the quantifiable results would be a comparison of different implimentations based on either speed or lateny, the dissertation being based on comparing several models to solve the problem. The second however causes more of a problem being quite vauge althought explaining it like the Ogre 3D engine handles all in game resources makes the research area a bit clearer, creating a test for this issue would possibly be the most challenging and depending on how the game resources would be stored and accessed that was decided on may be problematic to produce within the timescale.

The first issue has the most potential to sprial out of control into somthing too large for a research project but also would possibly provide the most depth.

Worksheet #1

2008-09-29T15:19:00.000+01:00

Currently I'm trying to find a question or hypothesis on which to base my honours project around. As part of the planning and reporting module everyone has been asked to fill in a worksheet and then forward it to another member of the class for critque. Here's my first draft of the worksheet thats been sent on already:

1. State the topic of interest that you may wish to take forward into a project
Topics within the area of Games programming interest me.

2. Indicate the issues surrounding this topic that you may wish to investigate
There are three main areas of this topic interest me:
Use of collision detection within a multi threaded game engine, how would collision detection be split between or assigned its own thread, what are the considerations performance wise with waiting for the collision thread(s) to finish processing their data and what are the possible synchronisation problems between the graphics representation and the collision detection results.
Inspired by: http://www.gamasutra.com/view/feature/3782/sponsored_feature_multithreading_.php

The Serialisation and persistence of art assets within a game engine, how does the game engine store and render these objects as well as catalogue them for instancing and other graphical techniques.
Inspired by: http://www.gamasutra.com/view/feature/3683/a_templated_c_attribute_library_.php

Issues surrounding input lag with respect to programming logic, attempting to minimise the input lag through event programming.
Inspired by: http://www.gamasutra.com/view/feature/1942/programming_responsiveness.php

3. Outline your initial ideas about how you would carry out the practical aspects of the project.
Mainly the objective and what is quantifiable with each of these areas needs to be defined first either through research of the topic or discussion with my technical advisor/lecturers. From there either the final topic to be developed into a research project would be chosen or a new topic posed. Once the research question is finalised background reading would begin along with basic planning of the test required to prove or disprove the research question. Each question may have several different approaches these may be used as the basis for the dissertation write up discussing the differences and advantages of each approach.