Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uwm.edu!zaphod.mps.ohio-state.edu!rpi!sarah!bingnews!kym
From: kym@bingvaxu.cc.binghamton.edu (R. Kym Horsell)
Newsgroups: comp.arch
Subject: Divide in 1 cycle (was Re: standard extensions)
Message-ID: <1991Feb28.010339.20055@bingvaxu.cc.binghamton.edu>
Date: 28 Feb 91 01:03:39 GMT
References: <2124@cluster.cs.su.oz.au> <1991Feb27.021435.11296@bingvaxu.cc.binghamton.edu> <1991Feb27.183718.638@jetsun.weitek.COM>
Organization: State University of New York at Binghamton
Lines: 34

In article <1991Feb27.183718.638@jetsun.weitek.COM> weaver@jetsun.WEITEK.COM (Michael Weaver) writes:
>Does anyone know of a pipelined divider that gives a result every cycle?

I've read of at least one real product. No ref -- memory fault.

>As far as I know, they exist only on paper, and for good reason:
>every algorithm I have heard of for an 'array' divider starts with
							^^^^^^^^^^^
>an iterative algorithm, and simply repeats the hardware for each 
^^^^^^^^^^^^^^^^^^^^^^^
>iteration. This means that the amount hardware is increased by 

I thought they started with a good table lookup. I seem to remember
that it's been shown that a good initial approx is more important
than the actual iterative scheme.

>the same factor as the increase in throughput, and the latency 
>remains the same, which is not very attractive. Also, the actual
>number of transistors is horrendous -- it would take perhaps
>ten times as many transistors as an array multiplier, which
>is a large thing.

I don't know about the order of magnitude difference, but I'll agree I 
wouldn't usually build such things on the basis of economics.

It always seemed like nature has it in for (integer) division --
from a stats perspective many of the answers will be 0 yet we
have to wait much longer (i.e. O(n^k) or O(n log n) as opposed to O(1))
in the worst case. If the numerator & denom are taken from uniform 
distibutions (which is pretty much the case in modular arithmetic & a 
few other realms) 1/2 the time num < denom and this is obviously
reasonably quick. A reconfiguring pipe anyone?

-kym