Modern Electronics (was Re: List charter mods & headcount... ;

From: Paul Koning <pkoning_at_equallogic.com>
Date: Fri Jun 25 08:22:40 2004

>>>>> "William" == William Donzelli <aw288_at_osfn.org> writes:

>> There are faster divide routines that calculate more than a bit at
>> a time (SRT dividers for example)

 William> Probably, as I remember multiplying can be done in a number
 William> of odd ways, some of which can speed up things quite a
 William> lot. I remember from the old 100K ECL books the strange
 William> "Wallace Tree" adder chip, specifically designed to add nine
 William> bits all at once. This was part of a 64 bit multiplier.

 William> I always assumed there were equally odd way of doing
 William> division.

I don't think so. Multiplication can be optimized lots of ways.
Division has always been the annoying exception that refuses to go
much faster no matter how hard you beat on it.

The standard algorithm is essentially classic elementary school long
division, in base 2 -- which means you get one bit of result per
cycle. Some implementations, going back at least as far as the CDC
6600 in 1964, add a pile of extra logic to compute multiple bits of
result per cycle -- 2 bits in the case of the 6600, which doubles the
speed at a cost of MORE than 2x in logic.

Then there are special cases: the Cray and Alpha integer units, which
don't offer divide at all. Instead, you're supposed to multiply by
the reciprocal of the divisor. This works well, because you can
actually do that faster than the straightforward one bit at a time
division even if you have to calculate the reciprocal at runtime.

In the Alpha case at least, the system library divide routine would
find the reciprocal by table lookup for small divisors, and the
compiler would find it for any divisor if it's a compile time
constant. GCC (in recent versions) does the same for any processor.

           paul
Received on Fri Jun 25 2004 - 08:22:40 BST

This archive was generated by hypermail 2.3.0 : Fri Oct 10 2014 - 23:37:00 BST