Re: Byte Addressability And Beyond

MitchAlsup1 wrote:

Terje Mathisen wrote:
 

MitchAlsup1 wrote:

>
>

I.e. h.264 CABAC decoding has three branches per bit decoded, at least one of them impossible to predict or work around with clever coding.

>
How many instructions in the then-clause and in the else-clause ??
If these are smaller than 8, My 66000 can process them without
"branching" using predication.

 

No, the real problem is the context branching: After doing the 50% branch you pick up one of two alternative contexts and follow totally different paths, i.e. you cannot simply use the branch bit as an index.

 If the number of instructions in the combined then and else clauses is
lower than a certain number, it is equally efficient to deal with the
branch as if it were later nullification rather than a redirection of
the fetch end of the pipeline. Here, NO prediction is required and there is no chance of misprediction without regard to the
predictability
of the control flow point. The whole point is that if the fetch end
of the pipeline will reach the convergence point before the branch
is fully resolved, then "don't branch" nullify. it saves cycles and
keeps unpredictable branches out of the branch predictor--even if the apparent takenness of the branch is completely random--improving
the prediction accuracy of "real branches".
 So, for example, let us postulate a 1-wide machine fetching 4 words per
clock and a then clause of 3 instructions and an else clause of 4 inst.
By the time the pseudo branch instruction enters execution, both the
then and the else have already been fetched, parsed, and are flowing
through decode. The execution of the branch merely decides which inst
survive the pipeline and there are no misprediction stalls. {{On a
wider machine, the fetch is even wider and the parse/decode BW is
still higher, so the mispredicted control flow point does not suffer
misprediction repair costs.}}
 Oddly enough, this is how predication works on My 66000.
 

I found ways to bypass the issues with the other two branches but this one is fundamental.

 It is fundamental only on ISAs that perform predication improperly
or does not have predication, or use the predictor when predicating.
My 66000 is not one of them.
 I return to the question posed earlier::
How many instructions in the then-clause and in the else-clause ??

 From 100++ to 10K+? Effectively no path merge within any kind a visible window.
I.e. decoding CABAC is running a state machine with tens to hundreds (afair) different states, with close to zero commonality between the code for individual paths. There is almost zero if/then/else/endif local branching at this level.
I could see absolutely no way to avoid biting the bullet and actually branch to the relevant code path.
Like I've written before, it is almost as if CABAC was designed to be as hard as possible for a sw decoder.
Terje
--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"