Lpc2000

Hi everybody,

i'm currently working with the LPC2136 and the latest KEIL C-compiler. 
Does anybody know some functions that provide a (much) faster 16-bit 
unsigned integer division than KEIL currently has? I have ~58MHz and 
the division currently needs about 2us.
I would even prefer some 32-Bit unsigned integer divisions but these 
run totaly out of my available timing (KEIL needs ~3.9us for that).

Does anybody know about specialised unsigned integer division 
functions, e.g. 24bit/16bit or 16bit/8bit?

Unfortunately i'm not familiar with the ARM assembler code. So if 
anyone can provide code then it would be helpful if it can be simply 
implemented with the KEIL compiler.

Thanks a lot,
Uenal

Hi,
an example division procedure (unsigned 32-bit) is described in ARM's 
application note named

ARM DDI 0029E.

I've tried this with ARM-GCC as separated assembly module (hybryd C-
asm) - function written in asm called from main program written in C. 
Works well, but I didn't check how fast.

On Tuesday 13 December 2005 11:36, uedogan wrote:
> Hi everybody,
>
> i'm currently working with the LPC2136 and the latest KEIL C-compiler.
> Does anybody know some functions that provide a (much) faster 16-bit
> unsigned integer division than KEIL currently has? I have ~58MHz and
> the division currently needs about 2us.
> I would even prefer some 32-Bit unsigned integer divisions but these
> run totaly out of my available timing (KEIL needs ~3.9us for that).

OK, I have not tried this out, but I'm quite surprised  it takes soooooo long. 
Keil have a good reputation and I would have expected a better result than 
this.

I looked at the gcc code for divi3 and it is approx 256 bytes long, but not 
all of that is getting executed. I would expect this to run faster than the 
numbers you give.

Curious how are you doing the measurement?

You probably already know this.... ARM does not have a built-in divide 
instruction so it uses a funky multiply instead. Most of execution goes into 
calculating the multipliers.

Shifting is very cheap on ARM, so if you're doing a lot of divisions by a 
shiftable number (eg. power of 2), then use shifts instead. The compiler 
should be able to figure this out itself for constants (eg. x = y / 16; ==> x 
= y >> 4;).

Since remainder (x = y % z) also uses a division, you should also consider 
using and masking  instead (x = y % 8; ==> x = y & 7;)

uedogan wrote:

>Hi everybody,
>
>i'm currently working with the LPC2136 and the latest KEIL C-compiler. 
>Does anybody know some functions that provide a (much) faster 16-bit 
>unsigned integer division than KEIL currently has? I have ~58MHz and 
>the division currently needs about 2us.
>I would even prefer some 32-Bit unsigned integer divisions but these 
>run totaly out of my available timing (KEIL needs ~3.9us for that).
>
>Does anybody know about specialised unsigned integer division 
>functions, e.g. 24bit/16bit or 16bit/8bit?
>
>Unfortunately i'm not familiar with the ARM assembler code. So if 
>anyone can provide code then it would be helpful if it can be simply 
>implemented with the KEIL compiler.
>
>  
>
At some point in time, the rubber has to meet the road...  Assembler is 
about as fast as you get, division + multiplication is a series of 
iterative shifting + adding / substracts.   Various algorithms have been 
devised over the years to produce fast General Purpose multiply & divide 
routines.

The key is "general purposed". If you wish to ONLY multiply or divide by 
a FIXED CONSTANT, then you can futher optimize performance.  BUT, you 
have to write your own assembly language routine(s).  To do so, first 
you have to understand how such operations work in the first place.

In example.  You know that by shifting left one bit you can multiply by 
a power of two?  Ok then, to build a routine that only multiplies by 10:

unsigned multiplyByTen (unsigned foo)
{
    return (foo << 1) + (foo << 3);
}

Division is a wee bit more involved, as there is a remainder (modulus).  
_Good_ books on assembly language would outline these types of operations...

That being said, you now know what a Floating Point Unit is good for: 
hardware acceleration of math calculations...

Regards

TomW



-- 
Tom Walsh - WN3L - Embedded Systems Consultant
http://openhardware.net, http://cyberiansoftware.com
"Windows? No thanks, I have work to do..."
----------------------------------------------------

At 01:35 PM 12/13/05 +1300, Charles Manning wrote:
>On Tuesday 13 December 2005 11:36, uedogan wrote:
> > Hi everybody,
> >
> > i'm currently working with the LPC2136 and the latest KEIL C-compiler.
> > Does anybody know some functions that provide a (much) faster 16-bit
> > unsigned integer division than KEIL currently has? I have ~58MHz and
> > the division currently needs about 2us.
> > I would even prefer some 32-Bit unsigned integer divisions but these
> > run totaly out of my available timing (KEIL needs ~3.9us for that).
>
>OK, I have not tried this out, but I'm quite surprised  it takes soooooo 
>long.
>Keil have a good reputation and I would have expected a better result than
>this.
>
>I looked at the gcc code for divi3 and it is approx 256 bytes long, but not
>all of that is getting executed. I would expect this to run faster than the
>numbers you give.

That is not be the worst of it.  I did some indirect measurements of 
division time when working up the second revision of the timing support in 
the newlib-lpc library.  (See 
http://www.aeolusdevelopment.com/AppNotes/LPC210X/an-timerperformance.pdf 
for some of the details if you're interested)  Not only does the division 
take a significant amount of time but the length of time it takes varies 
significantly depending on the values used.  Clearly the algorithm is 
optimized to shortcut out quickly.  Normally that's a good thing but 
sometimes....

Robert

" 'Freedom' has no meaning of itself.  There are always restrictions,   be 
they legal, genetic, or physical.  If you don't believe me, try to chew a 
radio signal. "  -- Kelvin Throop, III
http://www.aeolusdevelopment.com/

Hi,

Is the divisor a constant or is it variable?

> -----Original Message-----
> From: uedogan [mailto:uedogan@...] 
> Sent: 12 December 2005 22:37
> To: lpc2000@yahoogroups.com
> Subject: [lpc2000] Faster integer division with KEIL
> 
> Hi everybody,
> 
> i'm currently working with the LPC2136 and the latest KEIL 
> C-compiler. 
> Does anybody know some functions that provide a (much) faster 16-bit 
> unsigned integer division than KEIL currently has? I have ~58MHz and 
> the division currently needs about 2us.
> I would even prefer some 32-Bit unsigned integer divisions but these 
> run totaly out of my available timing (KEIL needs ~3.9us for that).
> 
> Does anybody know about specialised unsigned integer division 
> functions, e.g. 24bit/16bit or 16bit/8bit?
> 
> Unfortunately i'm not familiar with the ARM assembler code. So if 
> anyone can provide code then it would be helpful if it can be simply 
> implemented with the KEIL compiler.
> 
> Thanks a lot,
> Uenal
> 
> 
> 
> 
> 
> 
> ------------------------ Yahoo! Groups Sponsor 
> --------------------~--> 
> Get Bzzzy! (real tools to help you find a job). Welcome to 
> the Sweet Life.
> http://us.click.yahoo.com/KIlPFB/vlQLAA/TtwFAA/dN_tlB/TM
> --------------------------------------------------------------
> ------~-> 
> 
>  
> Yahoo! Groups Links
> 
> 
> 
>  
> 
> 
> 
>

For my website (online soon) I've made some C compiler benchmark.
Measurements with ARMulator (in AXD) to have cycle number needed.

My results for basic mathematic operations:


               divi      mulf      divf
GCC 3.4.3      76        49        142
GCC 4.0.2      76        38        130      
EWARM 4.30     72        50        135
ADS 1.2        44        36        76
Keil 2.41      103       36        214


As you can see, Keil is simply the worst for 32 bits integer division.

Hi,

First question I'd ask is what are you trying to do? 

To get more "bang per buck", I'd be inclined to follow the following 
strategy:

1. Re-work whatever algorithm you're using, or use a completely 
different one. Check out sources of numerical algorithms and DSP 
forums etc. for some ideas here.

2. As others have suggested, try and use special characteristics of 
the numbers you're using to optimise. Apart from the obvious (shift 
for divide by factors of two), there's limited scope here though. 
There might be scope for using look-up tables of pre-computed 
results, though.

3. Look for some good assembler functions if the built-in compiler's 
implementations aren't up to scratch.

In general, (fixed-point) division is a lot slower than 
multipication. Because of this, most algorithm work that's out there 
tends to avoid it. 

Changing algorithm (if possible) to minimise divisions will almost 
certainly give you the best results.

Brendan

--- In lpc2000@yahoogroups.com, "uedogan" <uedogan@g...> wrote:
>
> Hi everybody,
> 
> i'm currently working with the LPC2136 and the latest KEIL C-
compiler. 
> Does anybody know some functions that provide a (much) faster 16-
bit 
> unsigned integer division than KEIL currently has? I have ~58MHz 
and 
> the division currently needs about 2us.
> I would even prefer some 32-Bit unsigned integer divisions but 
these 
> run totaly out of my available timing (KEIL needs ~3.9us for that).
> 
> Does anybody know about specialised unsigned integer division 
> functions, e.g. 24bit/16bit or 16bit/8bit?
> 
> Unfortunately i'm not familiar with the ARM assembler code. So if 
> anyone can provide code then it would be helpful if it can be 
simply 

> implemented with the KEIL compiler.
> 
> Thanks a lot,
> Uenal
>

The book "ARM System Developer's Guide" by Sloss, Symes, Wright has 
some really cool, mind-blowing algorithms for divides (and other 
arithmetic functions).  If I understood it correctly, in one section 
it indicates that you can achieve a 16-bit fixed point divide with a 
single 32-bit multiply (using the magic of modulus arithmetic).

See the discussions on division which start on page 140 (in the 
edition/printing of the book that I have) and also the section 
starting on page 216.

Somebody else already asked the question whether you are always 
dividing by the same number (I'm not sure if you have answered that 
yet).  If you always use the same divisor (or some small number of 
known-in-advance divisors), there may be all sorts of opportunities 
for optimizing the code.  If you need a generic divide routine that 
accepts any values, that's another story... (see the book for that)

scsibob


--- In lpc2000@yahoogroups.com, "uedogan" <uedogan@g...> wrote:
>
> Hi everybody,
> 
> i'm currently working with the LPC2136 and the latest KEIL C-
compiler. 
> Does anybody know some functions that provide a (much) faster 16-
bit 
> unsigned integer division than KEIL currently has? I have ~58MHz 
and 
> the division currently needs about 2us.
> I would even prefer some 32-Bit unsigned integer divisions but 
these 
> run totaly out of my available timing (KEIL needs ~3.9us for that).
> 
> Does anybody know about specialised unsigned integer division 
> functions, e.g. 24bit/16bit or 16bit/8bit?
> 
> Unfortunately i'm not familiar with the ARM assembler code. So if 
> anyone can provide code then it would be helpful if it can be 
simply 

> implemented with the KEIL compiler.
> 
> Thanks a lot,
> Uenal
>

Hi,
thanks for the tip of this book!

Unfortunately i just have "normal" numbers in binary format. By the 
way, this are three sensor values which together form a color value. 
Some people gave comments like "try it without division" but i need 
chromaticity. Try to do this without division......

On an LPC2136 with ~58MHz i just have 15us time to sample the three 
16-bit values, check them for over/underflow, limit them, build 
chromaticity and check them against valid ranges. I also have to 
consider a lot of times hich also must be measured. Then set an 
output (if signals are in their ranges) and maybe do "a little" 
communications. Then the next cycle starts. The first goal in this 
project was even to reach a cycle time of 10us! But that is 
impossible or i start writing assembler routines (which i may do with 
the beginning of next year). Now i stay at 19us but not everything is 
done.....

I just need quick "generic" 16-bit (32-bit would be even better 
if "fast enough") unsigned divide routines. Code memory is no 
problem, theres enough. I wonder if it is not possible to use tables. 
Such a table can hold e.g. all possible results of 4-bit divisions 
and the 16-bit division is divided in "actions by 4". But i can not 
find such an algorithm. How do processors like an 8051 or a C166 
divide larger numbers? They have a hardware divider? Does anyone know 
how to divide in such "fractions"?

Ünal


--- In lpc2000@yahoogroups.com, "scsibob" <bobd@a...> wrote:
>
> The book "ARM System Developer's Guide" by Sloss, Symes, Wright has 
> some really cool, mind-blowing algorithms for divides (and other 
> arithmetic functions).  If I understood it correctly, in one 
section 
> it indicates that you can achieve a 16-bit fixed point divide with 
a 
> single 32-bit multiply (using the magic of modulus arithmetic).
> 
> See the discussions on division which start on page 140 (in the 
> edition/printing of the book that I have) and also the section 
> starting on page 216.
> 
> Somebody else already asked the question whether you are always 
> dividing by the same number (I'm not sure if you have answered that 
> yet).  If you always use the same divisor (or some small number of 
> known-in-advance divisors), there may be all sorts of opportunities 
> for optimizing the code.  If you need a generic divide routine that 
> accepts any values, that's another story... (see the book for that)
> 
> scsibob
> 
> 
> --- In lpc2000@yahoogroups.com, "uedogan" <uedogan@g...> wrote:
> >
> > Hi everybody,
> > 
> > i'm currently working with the LPC2136 and the latest KEIL C-
> compiler. 
> > Does anybody know some functions that provide a (much) faster 16-
> bit 
> > unsigned integer division than KEIL currently has? I have ~58MHz 
> and 
> > the division currently needs about 2us.
> > I would even prefer some 32-Bit unsigned integer divisions but 
> these 
> > run totaly out of my available timing (KEIL needs ~3.9us for 
that).

> > 
> > Does anybody know about specialised unsigned integer division 
> > functions, e.g. 24bit/16bit or 16bit/8bit?
> > 
> > Unfortunately i'm not familiar with the ARM assembler code. So if 
> > anyone can provide code then it would be helpful if it can be 
> simply 
> > implemented with the KEIL compiler.
> > 
> > Thanks a lot,
> > Uenal
> >
>