Lack of Branch Prediction for CELL SPE's..no problem?

[scooby_dooby]

How big of an issue is this?

i've read the SPE's have no branch preditcion, but instead "branch hinting"

How do these 2 compare, and what are the effects of no branch prediction on development time and development costs?

Is it as big a deal as some people are saying, or will simply be something dev's get used to, but not really a big deal...

 

[one]

It depends on how good the compiler is, how efficient the 128 registers are, and how developers can split their programs to exploit parallelism.

 

[Bobbler]

I'm pretty sure this topic has been flogged to death, not only on these forums but everywhere else.

But... Branch hinting is done in software -- the developer flags a piece of code which tells the compiler that it will be the most used case (or most likely used case) which essentially does what a branch prediction algorithm does (some differences) -- it has the disadvantage of the developer needing to do it but it also can be more accurate in some cases.

The lack of branch prediction is pretty significant in some cases and certain types of code will either need to be rethought out or require the ability to run fast enough even with. It's not the end of the world -- programmers are a sneaky bunch.

Supposedly the branch prediction on the PPE (and XCPU) isn't all that hot anyways, so developers will, regardless, have to alter some of the ways they do things normally.

We'll have to wait and see -- I'm sure some of the devs around here can give better input. I've never touched a PS2/Xbox/GC dev kit, let alone a PS3/X2.

 

[DudeMiester]

Couldn't you make some kind of automatic profiling tool which precomputes probabilties of each branch, then instert a random number function in your code for the hint?

 

[ERP]

OK here is some code where hints are as effective as branch prediction


for (int i = 0; i<100; i++)
Do Something


and now some code that static hints can't help you with

if (x>y)
do something
else
do something else

The point is the secod example branches based on data that isn't available at compile time, so you can't give any sort of useful hint.

Good real examples of things you can't usefully hint are searches, or tree walks.

 

[darkblu]

The point is the secod example branches based on data that isn't available at compile time, so you can't give any sort of useful hint.

Good real examples of things you can't usefully hint are searches, or tree walks.

not that branch predictors are that good at it either. unless there's a distinctive pattern in the behaviour of a particular branch point, the predictions for it would be as good as a blind guess. in this regard random searches do not rank very high.

 

[Titanio]

You could profile it and work out the probabilities I guess, like DudeMiester suggests?

It may end up that there's an equal probability for either branch, but even then with a simple guess half the time you should be right..?

 

[Mefisutoferesu]

What exactly (just an educated guess is enough) is the average ratio of branching code to the overall code??

What I mean to say is... what is the ratio in terms of physical code and the time spent in branch code vs non? More over, within that branch code how much is an issue that can't easily be resolved within software (like a simple loop as per ERP's example)?

Physical will give us an idea of whether it'll be extensive work to add branch "hinting" in code... that is if 80% of the code is going to be needing branching then it'll ad dev. time.

Time in execution will give us an idea of how problematic it could be in term of efficiency and so on.

The ratio of code where hints are effective vs not will should give us a clearer picture in relation to above.

Or so I would think...

Anyway, the question remains... anyone, got a clue about the values?

 

[Titanio]

What exactly (just an educated guess is enough) is the average ratio of branching code to the overall code??

What I mean to say is... what is the ratio in terms of physical code and the time spent in branch code vs non? More over, within that branch code how much is an issue that can't easily be resolved within software (like a simple loop as per ERP's example)?

Physical will give us an idea of whether it'll be extensive work to add branch "hinting" in code... that is if 80% of the code is going to be needing branching then it'll ad dev. time.

Time in execution will give us an idea of how problematic it could be in term of efficiency and so on.

The ratio of code where hints are effective vs not will should give us a clearer picture in relation to above.

Or so I would think...

Anyway, the question remains... anyone, got a clue about the values?

I'd caution against drawing conclusions based on code from other platforms - code tends to mutate, for want of a better word, to fit the platform it's running on.

 

[Mefisutoferesu]

True enough, code does "mutate" as you say to better conform to it's platform... however, knowing how current coding methods handle will give insight into how things will develop in the future... if we some serious problems we can except a serious change in design... which could lead to issues like devs complaining it's a hard to program for or a slow in releases and so on or we might find little to worry about.

I'm sure devs. themselves are doing this as well... trying to figure out how things are gonna change, and more likely than not they will. I'm just trying to see how things will change more than if they will change...

I dunno maybe this is too basic for seeing that sort of thing? Though, you gotta start somewhere, right?

 

[Shifty Geezer]

I think big changes are on the way. Both Cell and XeCPU are going to want careful cache management if performance is to be maintained. The moment either starts thrashing the caches they're gonna come a cropper. Once a new coding mindset kicks in perhaps it won't be too hard to adjust. Not show how the current education is but even basic things like 'put the most likely branch first' doesn't need to be taught on existing PC CPU's. eg. If it's better to code IF(x != 0) DO blah blah ELSE blah instead of IF (x = 0) DO blah blah ELSE blah, current PC code couldn't care less. A more refined understanding of the hardware (like the 16 bitters perhaps?) is going to be needed, but I don't think the end result will be amazingly difficult to implement. That hard part will be the re-education. Like speaking another language. The hard parts learning it, but when you know it, it comes as easy as your first language.

 

[Mefisutoferesu]

Kinda like BNE vs BEQ... ah, the memories are coming back... my whole 2 classes in assembly... ^^

I wonder how much of an effect this will have... do you think we will see as much of a division as we saw with the PS2? Where the games done by teams that understood the PS2 really brought out some great graphics while the others... ehhh, not so great. Granted a lot of that came from dealing with very weird VUs -- it's more conception and way of thought this time around, but could this of sorts be the PS3's "VU"?

I would imagine we'd see a split among previous PS2 devs (since they've probably had a great deal more experience dealing with nitty gritty concepts) as opposed to the PC devs. A split?

 

[JF_Aidan_Pryde]

How about VU code for PS2 when using the scratch pad? Doesn't that require the same degree of care? Or is branch prediction done automatically for the EE?

 

[nAo]

The point is the secod example branches based on data that isn't available at compile time, so you can't give any sort of useful hint.

I thought SPEs have a dynamic branching hint mechanism
From a MPR's article on CELL:

The SPE does have some help for branches that include branch hint instructions,
a three-source bitwise select. The SPE defaults to nottaken
branch prediction without a penalty, and no penalty is
imposed for branches taken and hinted correctly.

 

[JF_Aidan_Pryde]

I think understanding on Cell's branching has been pretty shoddy up to date. I did a presentation on Cell as a uni project a few weeks ago and got asked "so how does Cell work when it doesn't support branching?"

Cell does support branching. It even supports branch prediction -- just a very simple method. (defaults to not taken for example)

What it doesn't have is a massive branch prediction table!

---

Discussing this futher, is the SPE way of doing things really that different from what happens in a PPE or xCPU thread?

For example:
if (userInput > 0)
CodeA
else
CodeB

Input isn't available until say the player presses a button so there's no way to insert useful branch hints.

On SPE it would be like:
1. Evaluate (userInput >0)
2. Returns true, so DMA in "CodeA"
3. Wait wait wait
4. "CodeA" arrives on local store
5. Execute CodeA

On PPE/xCPU it would be like:
1. Evaluate (userInput >0)
2. Returns true, so hardware looks into cache to see if CodeA is there
3. If it's not there, hardware fetches from memory
4. Wait wait wait
5. CodeA arrives on cache
5. Execute CodeA

So in the case that both have to suffer from compulsary cache miss, both architectures have to wait visciously for memory.

Other scenarios:
1. xCPU finds CodeA in L2 cache. Execution is instant. SPE gets wooped in this case. Possible work around is to have a software managed cache for SPE. This would have to do a lot of comparisons but since SPE latency is much better than xCPU L2 latency, this probably wouldn't make things much worse.

2. xCPU loads CodeA into L2. Other threads thrash away much of the coherency. So more fetches to main memory is needed. Locking the cahe would fix.

To me it sounds like the SPE can simulate the cache behavoiur of xCPU and xCPU can simulate the cache behaviour of SPE. But both do this pretty darn awkardly.
[/code]

 

[nAo]

CELL's PPE has branch prediction
CELL's SPEs haven't branch prediction, SPEs have a branch hint instruction, hot it works is still unclear, at least to me

 

[JF_Aidan_Pryde]

CELL's SPEs haven't branch prediction, SPEs have a branch hint instruction, hot it works is still unclear, at least to me

Doesn't SPE default to not taken? Or do you need hints to even do this? If it does default to anything, it's branch prediction isn't it? How sophisticated does branch prediction have to be to count as branch prediction anyway? A massive branch history table?

 

[Gubbi]

CELL's SPEs haven't branch prediction, SPEs have a branch hint instruction, hot it works is still unclear, at least to me

Doesn't SPE default to not taken? Or do you need hints to even do this? If it does default to anything, it's branch prediction isn't it? How sophisticated does branch prediction have to be to count as branch prediction anyway? A massive branch history table?

As I understand it, there's a hint bit that decides if the branch is to be taken or not, which decides if the predicate (condition register) isn't ready yet. A prepare to branch instruction has also been mentioned, whichtells the SPU that it should start to fetch instructions from another address.

Without the prepare to branch instruction a correctly resolved branch taken would still inject a 7 cycle branch bubble (a mispredict: 20 cycles), so seems imperative for good performance.

Cheers
Gubbi