Division

[hamster]

What algorithm is used internally within the Epiphany to implement divide? Radix 2? Radix 4? SRT?

How expensive is division in comparison to multiplication and addition - is there a table of cycles required per instruction anywhere?

[ysapir]

Whatever algorithm implemented in newlib (the standard C library - libc - implementation). Epiphany does not have a native division instruction.

[piotr5]

I already talked of this topic. basically for division of integers take a look at gcc/libgcc/config/epiphany/divsi3.c in the eSDK from the public repository. if you find a faster algorithm than the assembler-version of this bit-by-bit division (after the overhead it takes 4 cycles for each bit in the result), an algorithm that uses up less memory, you are welcome to post it. you know, memory is limited to 32k, among this is at least 8k reserved for stack and heap and whatever (because the rest can be protected against writing), so every byte wasted for a division algorithm is precious...

as for counting cycles, as a rule of thumb every assembler instruction takes up 1 cycle. multiplication and float take up 2 more cycles but isn't blocking the program flow (i.e. also 1 cycle if the result isn't needed immediately). branching also takes up 3 cycles and is always blocking if the branch is being taken. no cache, no predictions, all these you must implement yourself -- access beyond those 32k is easily possible but it is alike to accessing stuff outside of a cache, like in level2 cache (whenever it's memory of another core) or raw memory access (much much slower)...

[timpart]

I think it is possible to speed up the bit at the front where it calculates the difference in leading bit positions. This would reduce the overhead.

After calculating the absolute values of the dividend and divisor, use the FLOAT machine code instruction to convert them to floating point. Logical right shifting each by an appropriate amount (23?) will leave you with the exponent of each floating point number. (Since the integers are both positive there is no leading sign bit to worry about.) Subtract one exponent from the other to find the "S0" difference wanted.

Tim

[piotr5]

agreed, I wrote of that too. actually FLOAT is what the code is doing here, except it acts as if that command wouldn't exist. still, only saves about 20 ticks, compared with the up to 128 ticks in the loop...

[timpart]

@piotr5 Must have missed that post when you wrote it

Still 20 ticks is better than nothing. As you say 128 for worst case loop. I've no idea what typical number of ticks would be, depends on the application, but I'd still think those 20 ticks might be at least 10% of routine time?

[amylaar]

When you look at gcc/libgcc/config/epiphany/t-epiphany, you'll see that neither divsi3.c nor divsi3.S are used;
instead, divsi3-float.S is used. Likewise for udiv/mod/umod.

So, you see, we are already using the float instruction. It's not quite as simple as you sketched it, though,
because we have to take account of different rounding modes and range overflows.

[piotr5]

I know assembler-files are what's used.
guess the c-files get compiled and then hand-optimized.
however, if rounding and overflow needs to be taken care of, maybe there should be multiple versions?
sometimes it is known what rounding-mode is used, at compile-time.
similarily for 8-bit operations overflow usually is no issue...

[shodruk]

By the way, how many divsi opcodes are there in a typical program?

[hamster]

Of course it depends on your application... most scientific and graphics computation require you divide every now an then. At the time I asked I was looking at it for simulating particle systems and computing the time of intersection with a boundary.

Of course when working with floating point you don't use integer division, but you still have to somehow either divide the mantissa portion of the numbers, or calculate the inverse of the numerator. For example, this could be done using Newton–Raphson division, which for double precision number requires 10 multiplies, 9 adds, and 2 shifts - and that is considered fast!

The intel FDIV bug was caused by an error in the lookup table used for it's SRT algorithm (which can also be used for integer division too).

I've been playing with Radix2 and Radix4 division implementations within FPGAs and was interested to see what was being used...