Re: [f-cpu] magnetude comparison

[Michael Riepe <michael+fcpu@stud.uni-hannover.de>]

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/