[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
Re: [f-cpu] magnetude comparison
Hi F-gang,
On Sun, Feb 29, 2004 at 07:13:16PM +0100, Yann Guidon wrote:
> hi !
>
> gaetan@xeberon.net wrote:
>
> > Hello F-people!
> >
> > i'm looking for a fast magnitude comparison for unsigned numbers
> > i need to know exactly which one of the mantissa (24 bits or 53 bits)
> > is the largest to feed the LOP with.
> > I was planing puting a comparator in the first stage of the adder, but
> > the obvious method is too long
> > (comparison from the last bit to the first). I wonder if such a
> > comparator exists with d<8...
> > In fact, i only need one bit result:
> > 0 : A >= B
> > 1 : A < B
> >
> > Does anyone have an idea for it :) ?
>
> this idea was investigated in the INC unit.
>
> it's a sort of cascade/tree of ANDN or something like that.
Yep. But its latency is too high if you realize it the standard way:
-- d=0 t=0
tmp := A xor B;
-- d=1 t=2
tmp := bit_reverse(cascade_or(bit_reverse(tmp)));
-- d=4 t=5
tmp := tmp xor rshift(tmp, 1); -- "and not" would also be possible
-- d=5 t=7
tmp := A and tmp;
-- d=6 t=8
A_is_greater := reduce_or(tmp);
-- d=9 t=11
The final reduce_or tree doesn't fit. That's the reason why EU_CMP
has two stages instead of one.
Note that it may be possible to speed this up with a big MUX:
function unsigned_greater (A, B : std_ulogic_vector) return std_ulogic is
constant L : natural := A'length;
variable aa, bb, tmp : std_ulogic_vector(L-1 downto 0);
begin
--pragma synthesis_off
assert L = A'length;
assert L = B'length;
--pragma synthesis_on
aa := to_X01(A);
bb := to_X01(B);
tmp := aa xor bb;
for i in L-1 downto 0 loop
if tmp(i) = '1' then
return aa(i);
end if;
end loop;
return '0';
end unsigned_greater;
but I do not consider that a portable solution. Besides that, its
latency can not be estimated before the circuit is synthesized.
My solution still is the compound adder. Since it calculates both A-B
and B-A in parallel (at the cost of an additional row of inverters),
you can select the correct value in any case and don't need a mantissa
comparator at all (only effective subtraction shown):
if Ea >= Eb then
Sy := Sa; -- sign bit
Ey := Ea;
Ma := not Ma;
Mb := right_shift(Mb, Ea - Eb);
elsif Ea < Eb then
Sy := Sb; -- sign bit
Ey := Eb;
Ma := right_shift(Ma, Eb - Ea);
Mb := not Mb;
end if;
CSAdd(Ma, Mb, My, Mz, G, P);
if Ea /= Eb then
if rounding = '1' then
-- rounded result
-- Note: this may return an inexact zero
-- which has to be handled during normalization
My := not Mz; -- Ma-Mb-1 or Mb-Ma-1
else
-- truncated result
My := not My; -- Ma-Mb or Mb-Ma
end if;
else
My := not My; -- Ma - Mb
if G = '1' then -- Mb > Ma
My := Mz; -- Mb - Ma
Sy := not Sy; -- change sign of result
elsif P = '1' then -- Ma = Mb, another special case!
Ey := (others => '0');
if rounding_mode = ROUND_FLOOR then
Sy := '1'; -- -0.0
else
Sy := '0'; -- +0.0
end if;
end if;
end if;
Note that the result of the subtraction is exact when Ea = Eb.
Therefore, you never have to round in that case. In the other cases,
rounding depends solely on the right-shifted operand (and of course
the rounding mode).
--
Michael "Tired" Riepe <Michael.Riepe@stud.uni-hannover.de>
"All I wanna do is have a little fun before I die"
*************************************************************
To unsubscribe, send an e-mail to majordomo@seul.org with
unsubscribe f-cpu in the body. http://f-cpu.seul.org/