For newcomers to Parallel Computing/Threading

[Groogy]

Hi!

I've seen pretty many people in this forum having no clue about threading. So I came up with a great idea for you guys to start out somewhere simple before entering the real madness. I am going to share with you, my own homework! Instead of trying to separate your game into different threads try creating this first so you can experience what can go wrong and how to correct it in a more "controlled environment".

Your new homework is to implement 5 sorting algorithms, and have each algorithm run in their own thread and display this visually using SFML. This task requires you to synchronize threads( rendering thread <- algorithm threads ) which is where most people seem to have trouble.



Try to do what I did and you should have a fair understanding of how threading works and how to implement it in a nice way. I'll of course be here to help you out if you get into trouble.

I highly recommend newcomers to try this first. If I find anyone asking again for directions I'll refer back to this post.

@Laurent: Hope you don't mind me putting this here ^^

[Laurent]

@Laurent: Hope you don't mind me putting this here ^^

Of course not

[drakelord]

This looks like an excellent idea.  I might try this when I get home and post my source code as an example, :]

[Groogy]

This looks like an excellent idea.  I might try this when I get home and post my source code as an example, :]

Great ^^
Like I said I'm here if you get into trouble. In my example I used Mutexes which is kind of cheat( also why the algorithm ran so slow ).

Though after talking to some class mates it might not be needed as they experienced that writing to 32 bit int/float was atomic.

[drakelord]

Just a couple of questions about the assignment.  

Do the algorithms need to get their source material from a common pool, or do they just need to be individual materials that need to be sorted?  

And, what do you want displayed exactly?  Like, how far along each algorithm is?  What is being sorted at the current frame?

[Groogy]

What I did was randomize a vector with float values. When I create the threads I give each thread it's own copy of the vector. What the points on screen represents is the vector index and the float value. The x axis being one of the values and the float value can be the other one(which order doesn't matter). So while the algorithm sorts, this is viewed directly on screen and will eventually form a single line across the screen.

Though you can use your imagination, though the more complex data structure you sort, the more complex the synchronization will be.

[drakelord]

So if you gave each thread a copy of the vector, how was it sorting out a common area?  Unless you meant you passed pointers or references to each thread, aren't you sorting out the same vector multiple times for no reason?  o.o  *blinks*

[Groogy]

No no no, the exercise lies in synchronizing the threads with the thread that renders everything You don't want the rendering thread to look at some data at the same time as it's being moved around in the vector(this is also kind of near the renderer-logic thread you always see people talking about for games). Having several algorithms sorting the same vector at the same time would be near, if not totally, impossible(Possibly even useless).

As I said in the original post, this is a place so you have a "controlled environment" where very little can go wrong and it is easy to extend it with experiments. For example: if you start out with mutexes the algorithms run slow, then you remove them and replace it with control-flags instead to make it lock-less, moving deeper and deeper into the things that people always shoot themselves in the foot with. This is a much better way to be introduced into Parallelism than just jumping straight into it that I see a LOT of people doing.

Have you seen this video: http://www.blinkvid.com/video/8345/Sorting-Out-Sorting-mp4
The exercise is inspired by this old relic which is still up to date.

[drakelord]

Okay, yeah, I get it, xD;  The wording confused me a bit, :]

[Dper]

I believe link to "old movie" is broken, although I've found this and I believe THIS is the same