( ESNUG 254 Item 2 ) -------------------------------------------- [11/6/96]
Subject: (ESNUG 253 #10) Does Synopsys Synthesis Support VHDL Recursion ?
> I recently heard that Synopsys supports Recursion in VHDL, and will
> synthesize recursive VHDL code! Recursion is a very powerfull tool, and
> for instantiating highly repetitive blocks it would be very useful. ...
> ... Peter Ashenden of University of Cincinatti has an example of a
> recursive call upon a VHDL entity to generate a buffer tree, the paper is
> called "Recursive and Repetitive Hardware Models in VHDL". ... If at all
> possible I would appreciate a simple example, something like a clock tree
> or priority encoder would be nice.
From: jcooley@world.std.com (John Cooley)
The quick & dirty answer is "Yes, Synopsys does support VHDL recursion in
synthesis." (It could even support Verilog recursion if Verilog had it;
the basic software to do it isn't terribly Verilog/VHDL dependent.) Of
course this is just newly supported by Synopsys so a lot of this is still
very experimental. There are some complex restrictions you have to follow
but the big one is that *everything* must be static at elaboration time.
(i.e. You may design an N-bit priority encoder, but N *must* be given an
exact value at synthesis time.) The N-bit priority encoder bellow will
consistently build a better circuit with better area and timing -- plus
it scales nicely.
package pack is
constant N: integer := 5; -- Note: N is statically defined here!
function log2(A: integer) return integer;
function max(A,B: integer) return integer;
end;
package body pack is
function max(A,B: integer) return integer is
begin
if(A<B) then return(B);
else return(A);
end if;
end;
function log2(A: integer) return integer is
begin
for I in 1 to 30 loop -- Works for up to 32 bit integers
if(2**I > A) then return(I-1);
end if;
end loop;
return(30);
end;
end;
use work.pack.all;
entity priority_tree is
port (A: in bit_vector(2**N - 1 downto 0);
P: out bit_vector(N-1 downto 0);
F: out bit);
end;
architecture a of priority_tree is
procedure priority ( A: in bit_vector; -- Input Vector
P: out bit_vector; -- High Priority Index
F: out bit) is -- Found a one?
constant WIDTH: INTEGER := A'length;
constant LOG_WIDTH: INTEGER := log2(WIDTH);
variable AT: bit_vector(WIDTH-1 downto 0);
variable F1, F0: bit;
variable PRET: bit_vector(LOG_WIDTH-1 downto 0);
variable P1, P0, PT: bit_vector(max(LOG_WIDTH-2,0) downto 0);
begin
AT := A; -- Normalize array indexes
if(WIDTH = 1) then -- Handle Degenerate case of single input
F := AT(0);
elsif(WIDTH = 2) then -- Bottom of the recursion: a two-bit encoder
PRET(0) := AT(0);
F := AT(1) or AT(0);
else -- Recurse on the two halves, and compute combined result
priority ( AT(WIDTH-1 downto WIDTH/2), P1, F1);
priority ( AT(WIDTH/2-1 downto 0), P0, F0);
F := F1 or F0; -- We found a one if either half had a one
if(F1 = '1') then -- If the first half had a one, use it's index
PT := P1;
else
PT := P0; -- Otherwise, us the second half's index
end if;
PRET := F1 & PT; -- The result MSB is one if the first half had a 1
end if;
P := PRET;
end;
begin
process(A)
variable PV: bit_vector(N-1 downto 0);
variable FV: bit;
begin
priority (A, PV, FV);
P <= PV;
F <= FV;
end process;
end;
Another more concise way to do this is with a loop (see below). The
loop architecture is a serial, cascaded circuit which can be optimized
effectively up to N=16. At N=32 you begin to see a small variation in
the results. The tree is always better but in small examples the
optimizer will produce the same result.
package pack is
constant WIDTH: integer := 32;
function log2(A: integer) return integer;
end;
package body pack is
function log2(A: integer) return integer is
begin
for I in 1 to 30 loop -- Works for up to 32 bit integers
if(2**I > A) then
return(I-1);
end if;
end loop;
return(30);
end;
end;
library IEEE;
use IEEE.std_logic_1164.all;
use IEEE.std_logic_arith.all;
use work.pack.all;
entity priority_long is
port (A: in std_logic_vector(WIDTH - 1 downto 0);
P: out std_logic_vector(log2(WIDTH)-1 downto 0));
end;
architecture a of priority_long is
signal PT : std_logic_vector (log2(WIDTH) downto 0);
signal IT : integer;
begin
process(A,PT,IT)
begin
IT <= 0;
for I in 0 to WIDTH-1 loop
if ( A(I) = '1' ) then
IT <= I;
end if;
end loop;
PT <= CONV_STD_LOGIC_VECTOR(IT,log2(WIDTH)+1);
P <= PT(log2(WIDTH)-1 downto 0);
end process;
end;
The final function call shows how to implement the reduction operator
(function call) using recursion to produce a tree. In many cases a
simple loop can produce the same results but the tree is guaranteed to
give you the best synthesized result. (Many times Synopsys can clean up
bad code but this get harder as the circuit gets bigger or more complex.)
function recurse_XOR (data: std_logic_vector) return std_logic is
variable UPPER_TREE, LOWER_TREE : std_logic;
variable L_BOUND, LEN : integer;
variable i_data : std_logic_vector(data'LENGTH-1 downto 0);
variable result : std_logic;
begin
i_data := data;
if i_data'length = 1 then
result := i_data(i_data'LEFT);
elsif i_data'length = 2 then
result := i_data(i_data'LEFT) XOR i_data(i_data'RIGHT);
else
LEN := i_data'LENGTH;
L_BOUND := (LEN + 1)/2 + i_data'RIGHT;
UPPER_TREE := recurse_XOR (i_data(i_data'LEFT downto L_BOUND));
LOWER_TREE := recurse_XOR (i_data(L_BOUND - 1 downto i_data'RIGHT));
result := UPPER_TREE XOR LOWER_TREE;
end if;
return result;
end;
For an interesting discussion of coding priority encoders, I suggest you
check out the paper by Mike Parkin of SUN Microsystems in your Synopsys
Online Documentation titled "Writing Successful RTL Descriptions in
Verilog" or the SolvIt note 019403.
Of course, all this recursion work is cutting edge, so don't be surprised
to see more details (and restrictions) on how to use recursion in Synopsys
synthesis in future ESNUGs.
- John Cooley
the ESNUG guy
|
|
