Yep. There's a great talk about this by Cliff Click, called A Crash Course in Modern Hardware[1] that I would recommend to everyone. I am no hardware expert, so that talk really enlightened me.
Regarding the issue at hand, I remember Doug Lea saying[2] that some new Intel processors may recognize a loop as the OSs idle loop and power down the core. That's why he computes random numbers in busy-wait loops.
[1] http://www.infoq.com/presentations/click-crash-course-modern...
[2] http://emergingtech.chariotsolutions.com/2013/04/phillyete-s...
In order comes back during strange times. Sun switched back to in-order for Niagara, for instance.
Bottom line is you just have to think about GPUs in a slightly different way - they do have disadvantages (limited register/cache/memory per thread since you need so many of them), but things like branching aren't that big of a deal.
Not necessarily. In the early days of the P6 core, I found a simple loop which would take either 4.0 or 5.33 cycles depending on the internal CPU state -- exactly the same code, but running with an iteration count of 10^6 would take either 4000000 cycles or 5333333 cycles.
I had the good fortune to talk to a member of the team which designed the P6 core, and we concluded that this was due to a quirk of the out-of-order scheduler: In order to reduce circuit depths, the mechanism for finding and dispatching runnable uops wouldn't always dispatch the earliest available uops, and so -- depending on how the incoming uops were aligned within an internal buffer -- the P6 core would sometimes take a stream of instructions which could be executed in-order without pipeline stalls and run them out-of-order with less ILP.
In short, OOO cores are weird and horribly complicated and completely untrustworthy where performance is concerned.