Neon-ized Math.h Like Library

[darkblu]

great thread, Adventus!

It appears the range reduction and quadrant checking are much more significant than the polynomial evaluation. Using some bit manipulation I managed to get the quadrant checking to a branchless 10 instructions, however i haven't been able to parallelize anything yet. From what I've read, it seems avoiding branches in NEON / VFP is crucial, Every time you do a comparison you have to stall and send the flags to the ARM flag register....

hmm, do you mean that for branching or predicate execution? i thought the latter was carried on-board? if not i can see why you'd want to avoid predicates if those get carried on the main unit.

 

[andys]

great thread, Adventus!

It appears the range reduction and quadrant checking are much more significant than the polynomial evaluation. Using some bit manipulation I managed to get the quadrant checking to a branchless 10 instructions, however i haven't been able to parallelize anything yet. From what I've read, it seems avoiding branches in NEON / VFP is crucial, Every time you do a comparison you have to stall and send the flags to the ARM flag register....

hmm, do you mean that for branching or predicate execution? i thought the latter was carried on-board? if not i can see why you'd want to avoid predicates if those get carried on the main unit.

Predicate execution is dependant upon the ARM bits from my reading, and predicated instructions are squashed before they hit NEON. Of course, not a CPU designer, so I may have understood wrong. The NEON bit has arbitary permute and comparison functions, so you can simulate predication on NEON by using VTBX though. I think Not tried it - don't have an beagleboard, but it looks plausible

 

[hlidegp2x]

Predicate execution is dependant upon the ARM bits from my reading, and predicated instructions are squashed before they hit NEON. Of course, not a CPU designer, so I may have understood wrong. The NEON bit has arbitary permute and comparison functions, so you can simulate predication on NEON by using VTBX though. I think Not tried it - don't have an beagleboard, but it looks plausible

If I remember well you cannot issue in the same cycle two instructions having predicates so they must be used with attention.

@andys: VTBX "uses byte indexes in a control vector to look up byte values in a table and generate a new vector. Indexes out of range leave the destination element unchanged". I'm not sure to understand what you want to do here.

 

[darkblu]

Predicate execution is dependant upon the ARM bits from my reading, and predicated instructions are squashed before they hit NEON.

doh, you're right - ARM does the predicating, of course. i don't know why i was left with that impression of NEON.

 

[andys]

Predicate execution is dependant upon the ARM bits from my reading, and predicated instructions are squashed before they hit NEON. Of course, not a CPU designer, so I may have understood wrong. The NEON bit has arbitary permute and comparison functions, so you can simulate predication on NEON by using VTBX though. I think Not tried it - don't have an beagleboard, but it looks plausible

If I remember well you cannot issue in the same cycle two instructions having predicates so they must be used with attention.

@andys: VTBX "uses byte indexes in a control vector to look up byte values in a table and generate a new vector. Indexes out of range leave the destination element unchanged". I'm not sure to understand what you want to do here.

Well, I'm not an assembly programmer, so you might want to check that I am sane.

So, my idea is that VTBX takes an array looking something like

[0,1,2,3,4,5,6,7] and then will select the 0th byte, etc upwards of the target. (Obviously for a q register it would go up to 15).

So if you wanted to do an ADD on the first and third elements of a 64bit vector containing 16 bit elements, you could fill it with

[0,1,-1,-1,4,5,-1,-1].

Perform the ADD on the full vector, then use VTBX to select out the first and third of the changed set - thus leaving 2 and 4 unchanged and copying 1 and 3. I assume this is how it works, it's not exactly the best documented instruction ever.

If this is the case, and I'm not insane, then you can do predication by using the compare instructions - the compare instructions leave a 1 in the areas where it matches, and a 0 where it doesn't match. If you do an inverted comparison (if you want all the ones that are greater than a number, you do less than or equal to), and then subtract 1 from all lanes, you would end up with 0 where you want the value and -1 where you don't want the value. If you then or that against the mask [0,1,2,3,4,5,6,7] - you would wind up with the lanes you don't want switched off.

I might be completely barking up the wrong tree, but it seems like this might work. Of course, it's not as cheap as dedicated predication because VTBX takes 2 cycles on a D register, and you'd need to issue two of them for a Q register, as well as a compare, a subtract and an OR, thus costing you at least 4 cycles assuming you were actually able to interleave them, but it strikes me that it would be a lot cheaper than a 20 cycle + stall.

Anyway, am happy to be proved wrong - I don't have hardware to try it with!

For anybody who hasn't read the docs:

VTBX : http://infocenter.arm.com/help/topic/com.arm.doc.dui0204i/CIHCFEBA.html#id6764875

VCGE (and friends) : http://infocenter.arm.com/help/topic/com.arm.doc.dui0204i/CIHGAGID.html

PS: After reading the second one - I don't think you need a subtract, it seems to imply it sets the lane to -1 - which would save you a register and an op, although the VTBX would still dominate, depending upon the other instructions you had to execute. Also, does anybody know HOW the dual issue works - can it back to back dual issue multi-cycle instructions? For example, could it execute VTBX and Qword floating point ops simultaneously, just interleaved? Or does it only work with single cycle ops?

 

[andys]

If this is the case, and I'm not insane, then you can do predication by using the compare instructions - the compare instructions leave a 1 in the areas where it matches, and a 0 where it doesn't match. If you do an inverted comparison (if you want all the ones that are greater than a number, you do less than or equal to), and then subtract 1 from all lanes, you would end up with 0 where you want the value and -1 where you don't want the value. If you then or that against the mask [0,1,2,3,4,5,6,7] - you would wind up with the lanes you don't want switched off.

I'm tired, so obviously this doesn't make perfect sense - but the gist should be there at least! (you do do an inverted comparison if the instruction does insert -1 when it matches, and then you OR - but if it worked as I described you would do a straightforward comparison - but reading it carefully... yeah,

 

[andys]

Predicate execution is dependant upon the ARM bits from my reading, and predicated instructions are squashed before they hit NEON. Of course, not a CPU designer, so I may have understood wrong. The NEON bit has arbitary permute and comparison functions, so you can simulate predication on NEON by using VTBX though. I think Not tried it - don't have an beagleboard, but it looks plausible

If I remember well you cannot issue in the same cycle two instructions having predicates so they must be used with attention.

Sorry for the extra post - my reading of the ARM docs indicates this is only where there is a destination hazard - if you have an IF and the ELSE part right next to each other

"Instructions with the same destination cannot be issued in the same cycle. This can happen with conditional code."

From : http://infocenter.arm.com/help/topic/com.arm.doc.ddi0344b/BABHEFAJ.html

 

[ldesnogu]

NEON instructions cannot be predicated.

 

[darkblu]

NEON instructions cannot be predicated.

and that, kids, is what you get for not clicking the goddamed '{cond}' link on the goddamned online doc.

 

[andys]

NEON instructions cannot be predicated.

I thought they could be predicated based upon the ARM flags? The documentation seems to imply this is the case, at least in Thumb2.

The (somewhat sick) approach I was suggesting earlier was attempting to abuse permute to achieve "simulated" predication in NEON, although obviously at a higher cost than proper predicated instructions. I really must get a BB and see if it would work.

 

[ldesnogu]

Thumb2 instructions aren't predicated

 

[andys]

Thumb2 instructions aren't predicated

What about the IT instruction?

http://infocenter.arm.com/help/topic/com.arm.doc.dui0204i/Cjabicci.html

My understanding was that this was used instead of predicate bits in the instruction itself.

 

[ldesnogu]

Yes, you can consider an IT block as being predicated. But not all instructions can be put in an IT block.

And please, don't use Thumb2, it triggers too many problems including some nasty errata.

 

[andys]

Yes, you can consider an IT block as being predicated. But not all instructions can be put in an IT block.

And please, don't use Thumb2, it triggers too many problems including some nasty errata.

Interesting... is the errata list available? Seems a bit of a pain. Of course, if we don't use Thumb-2 then NEON ops can't be predicated, although that's not exactly the worst thing in the world.

 

[hlidegp2x]

NEON instructions cannot be predicated.

really ? I can see in the doc some NEON instructions having <cond> though : VADDEQ, VADDNE, etc.

unless you're speaking about IFxxx instruction ?

EDIT:

In ARM state, except for the instructions that are common to both VFP and NEON, you cannot use a condition code to control the execution of NEON instructions.

In Thumb® state on a Thumb‑2 processor, you can use an IT instruction to set condition codes on up to four following NEON or VFP instructions. See IT for details.

The only VFP instruction that can be used to update the status flags is VCMP. It does not update the flags in the APSR directly, but updates a separate set of flags in the FPSCR

 

[hlidegp2x]

BTW i think there is a slight error in your code, The 2nd last line should read: VMLA.F32 D0, D2, D1.

yes you're right.

Just a suggestion, don't try to write simple function like sinf, cosf, etc. in NEON to use them as such. It is extremely unefficient to do so.

If you need to rotate a vector, you may want to compute SIN and COS in parallel.

 

[Adventus]

Just a suggestion, don't try to write simple function like sinf, cosf, etc. in NEON to use them as such. It is extremely unefficient to do so.

Yea good point, to make it easy for the developer i will write drop in replacements for cmath.... but i'll add additional functions suited to the NEON. Presumably vector versions of the base functions would be a good optimisation, like a sinfv_neon(float *x, int n) that's unrolled to calculate two, or four, sinfs in parallel. Any other ideas?

Predicated execution on the NEON isn't too hard to get around. As in the code i posted you can translate:

if (cond) x = x1
else x = x0

To:

dx = x1 - x0;
x = x0;
x = x + (cond > 0) * dx;

Which is probably 2-3 cycles, the mov and sub can be issued in parallel. The problem is large branches where both paths are long and independent, you'll either have to; calculate both paths, send the flags from NEON to ARM, or calculate the conditions on the ARM. Each of these have positives and negatives. The last is best if you can precalculate the condition.

 

[darkblu]

Predicated execution on the NEON isn't too hard to get around.

it's not about how hard it is to deal without predicates, it's that a few of us were fooled by the ingeniously structured NEON doc. well, at least i was : )

but even if predicating worked, it'd still be a no-no due to reasons we all know (tm).

 

[Adventus]

it's not about how hard it is to deal without predicates, it's that a few of us were fooled by the ingeniously structured NEON doc. well, at least i was : )

Yea i know, my comment wasn't directed at anyone in particular. I'm basically using this thread to document what i learn as a go.

One question that is crucial to how i implement my functions, is what's an acceptable accuracy? 0.5% ?

Not sure if this is of any interest but I'll document some of my functions, how I've implemented them and some of the theory. So far I've written in c: sinf, cosf, tanf, atanf, expf, logf, powf. I've made sure they'll be very easy to translate to NEON assembly (no branches, etc). I used Mathematica to get nice Minimax Polynomials when they were needed.

TANF
The typical implementation of tanf involves approximating it by tan(x > a) = 1/(x - a) and tan(x < a) = Poly(x, x^2, ..., x^n), without this splitting of the domain you cannot get decent accuracy. Since it requires a branch and both paths are fairly significant it was not a great candidate for the NEON. I implemented tanf using the identity tan(x) = sin(x) / sqrt(1 - sin(x)^2). With this implementation you can also simplify some of the quadrant checking of the sinf. Usually this method is far too slow, sqrt takes the VFP 19 - 33 cycles then a divide would take another 20 - 37 cycles, but because we don't need full accuracy it can be done quite quickly using some of the nifty functions provided by the NEON. You may remember the fast invsqrt in the quake3 sourcecode, well the NEON can do it, or something similar to it, in about 4 instructions.

The fast invsqrt source is something like:

float invsqrt(float x){
	union {
		float f;
		int i;
	} r;

	r.f = x;
	r.i = 0x5F3759DF - (c.i >> 1);
	r.f = r.f * (3.0f - r.f * r.f * x) / 2;		
	return r.f;
}

I won't go too much into how it works (look up wikipedia if your interested), but it basically recognizes that in ieee754: 1.0 / sqrt(x) = 1.0 / sqrt((1.0 + m) * (2 ^ n)) = (1.0 / sqrt(1 + m)) * (2 ^ ( - n / 2))

The 2nd term can be calculated by extracting the exponent from x, dividing by two and negating. This is roughly whats occurring in the "0x5F3759DF - (c.i >> 1)" code. This estimate gets you an accuracy within ~4%. The next bit of code uses a Newton-Raphson iteration that, using your estimate as a seed, quickly converges to the actual value. After one iteration your within ~0.15% accuracy. Heres what the pseudo NEON code looks like:

VRSQRTE D1, D0        //performs fast invsqrt estimate assuming D0 contains x
VMUL    D2, D1, D0    //D2 = D1 * D0
VRSQRTS D2, D2, D1    //D2 = (3.0 - D2 * D1) / 2
VMUL    D1, D1, D2    //D1 = D1 * D2

Since my sinf isn't completely accurate i decided to do two iterations so that adds another 3 instructions and gains much more accuracy. Compared to the inbuilt tanf I get an accuracy around 0.0005% except very near PI/2 where Tan -> Infinity so no polynomial will be an accurate fit.

I might add some of the other functions when i get some more energy. Tell me to shut up if its boring.

 

[Exophase]

Yes, you can consider an IT block as being predicated. But not all instructions can be put in an IT block.

And please, don't use Thumb2, it triggers too many problems including some nasty errata.

Most instructions that matter (IMO) can be put in an IT.

Don't you think this kind of statement is a little unsatisfying?

"There's this instruction set that has much better code density in addition to some nice instructions and operand forms that are not normally in ARM but please don't use it for reasons I won't disclose."

I use a Cortex-M3 at work so I must use Thumb-2 there, but naturally it can be useful on Cortex-A8 too.

So of course I want to know the nature of these problems. Are you talking about compiler bugs in CodeSourcery? Bugs specific to OMAP35xx? Bugs specific to Cortex-A8 that have not been resolved? Or are you just uncomfortable about people using it because you're concerned about implementation costs in future CPUs due to the mixed length decoding?