Sign in to follow this  
  • entries
    375
  • comments
    1136
  • views
    297494

Atomic 'Lectronic Super-super-sonic

Sign in to follow this  
superpig

73 views

In my pursuit of multithreaded execution, I'm paying particular attention to lock-free and wait-free algorithms, and 'atomicity' of operations.

Atomic ops are important because of the nature of the interruption - a context switch. What happens if you're in the middle of modifying something when another thread messes with your data? What if another thread tries reading something that you've made temporarily invalid?

When you're multiprogramming, an individual assembly instruction is atomic. The processor won't switch threads in the middle of an instruction. When you're multiprocessing, things are a little more difficult as two threads (on seperate processors) could access the same memory location simultaneously.

My situation is made a little more complicated by the fact that I'm targetting both Intel/AMD, and Mac G4/5 (PowerPC).

So what are we looking at exactly?

The X86 instruction set includes a few useful compound-operation instructions that can be performed atomically. The most useful of these is CMPXCHG; it compares the accumulator with the first argument, and then either copies the second argument to the first argument, or the first argument into the accumulator, depending on the result of the test. So, you can read a value into the accumulator, calculate some new value into another register, then store the new value if nothing else has changed the original value in the meantime. If the value's been changed, no store occurs, and you can respond accordingly (perhaps starting over with the new value). To be multiprocessor-safe, the LOCK prefix must be used. So it's not all /really/ lock-free, but locking a single instruction is going to be less damaging than locking a whole chunk of code with a mutex or something.

Under PPC, we don't have CMPXCHG as a single instruction; we do, however, have quite a nice mechanism using something called a 'reservation.' Basically, it becomes possible to stamp a memory address with the current thread/processor ID, saying "I'm using this." Stamping a memory address and loading the value from that address is an atomic operation (single instruction 'lwarx'). You can then do whatever you want to the value, taking as long as you need. When it's time to write the result back again, you use a special store instruction called 'stwcx,' which stores the value if the reservation is still present. If anyone else writes to that address, you lose your reservation.

So on both architectures the sequence goes something like this:

  1. Read the original value. (X86: make a copy, PPC: set reservation)
  2. Perform calculations on the value.
  3. Check that the (reservation|value) of the target is correct, and if so, write the value back.
  4. If the write failed, possibly repeat the process.

Sign in to follow this  


1 Comment


Recommended Comments

Good entry and a decent bit of theory, but i'm curious as to why you chose to go so low-level...

I suppose you could go and hand-tune the compiled output (or hope that the compiler does it automagically (pthread support in VC8?)) but surely you're better off working at the algorithmic level.

I can't discuss the full details, but one of the better systems I've worked on involved a very high level scheduling system. It would handle assignment to a given CPU, but more importantly it'd take a batch of commands (say, for a game, a frames worth of stuff) and re-arrange it to make sure that it could get optimal performance.

For example, if you divide your memory up into segments (A,B,C,D...) and you know that a given block of code works on segment B then D then C. You also know that another block works on B and C, but they're not dependent you could reverse the second thread so it does it's block-c work whilst the other is doing block-b.

Jack

Share this comment


Link to comment

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now