[VHDL PROCEDURE] Recursion possible?

[Linh T. Tran]

I am toying with the idea of writing recursive code in VHDL.
Let me explain why somebody wants to write recursive code: Many
algorithm to structural design are inherantly recursive in nature.
For instance, if you want to write a structural code that generate
parametrized carry-look-ahead adder with multilevel carry-look-ahead,
a recursive method cuts the coding down to a few procedures, while
a straight forward method needs to code each level of the carry-look-
ahead tree separately.

My question is: anyone tried to write that sort of code
before? Is it legal VHDL? What about consequences in synthesis?

I guess I can answer partially those questions in a few weeks,
after I finished my experiment. However, if somebody could point
out right away that it is a not so good idea, the community
would benefit.

Linh T. Tran
MOS Digital Analog Division
Motorola Inc.
e-mail: vo...@bga.com
e-mail: tr...@auscsmp.sps.mot.com

[John A. Evans]

vo...@bga.com (Linh T. Tran) writes:

> I am toying with the idea of writing recursive code in VHDL.

>before? Is it legal VHDL? What about consequences in synthesis?

> Linh T. Tran
> MOS Digital Analog Division
> Motorola Inc.
> e-mail: vo...@bga.com
> e-mail: tr...@auscsmp.sps.mot.com

Recursive code is perfectly legal. In fact, I have used it to generate
more regular structure in the circuits synthesized than would have been
generated using iterative structures. Try it yourself for a simple
parity generator. Each recursive call will address the left branch and
the right branch of the structure, with the terminating case being when
each branch has only one element.

If absolutely necessary, I can post some code later as an example.

john
-------------------------------------------------------------------------------
John A. Evans, Capt, USAF "My number one goal as a
VHDL/EDA Engineer runner is to live long enough
N3QOO Tech Plus !!! to place in my age group!!!"

jae...@clark.net Linux - the OS of choice !!
-------------------------------------------------------------------------------
Once data encryption is outlawed, only outlaws will have data encryption !!!
-------------------------------------------------------------------------------

[Paul Menchini]

In article <2mjvr1$r...@explorer.clark.net>, jae...@clark.net (John A. Evans)
writes:

>vo...@bga.com (Linh T. Tran) writes:
>> I am toying with the idea of writing recursive code in VHDL.
>>before? Is it legal VHDL? What about consequences in synthesis?
>

>Recursive code is perfectly legal. In fact, I have used it to generate
>more regular structure in the circuits synthesized than would have been
>generated using iterative structures. Try it yourself for a simple
>parity generator. Each recursive call will address the left branch and
>the right branch of the structure, with the terminating case being when
>each branch has only one element.

There are two ways of recursing in VHDL.

1. First, and most familiar, is recursive subprogram invocation. It is legal
in VHDL, although I know of no synthesizer that can handle arbitrary recursive
code. No commercial ones that I know of can even handle tail recursion (by
turning it into iteration. I think this is what the original poster was
speaking of, given the subject heading.

2. Recursive binding is legal, although some VHDL systems don't accept it in
their 1987 versions. (It clearly must be supported in '93.) This is what
Capt. Evans was speaking of. I don't know if synthesis tools are smart
enough to handle it, but (in principle) there should be few problems.

--
Paul Menchini
Menchini & Associates Temporarily at: Digital Equipment Corporation
me...@mercury.interpath.net menc...@nacto.lkg.dec.com
919-990-9506 508-486-7448

[Paul Menchini]

In article <Cn44t...@dit.upm.es>, lsan...@dit.upm.es (Luis Sanchez Fernandez)
writes:
>menc...@forb.nacto.lkg.dec.com (Paul Menchini) writes:
>:
>: 2. Recursive binding is legal, although some VHDL systems don't accept it in

>: their 1987 versions. (It clearly must be supported in '93.) This is what
>: Capt. Evans was speaking of. I don't know if synthesis tools are smart
>: enough to handle it, but (in principle) there should be few problems.
>

>I'm not sure about how looks like this second kind of recursivity.
>Are you talking about something like this?:
>
>********************************************************
>entity myself is
> port (x: in bit; y: out bit);
>end myself;
>
>architecture beh of myself is
>begin
> process(x)
> begin
> y <= x after 1 ns;
> end process;
>end beh;
>
>entity test_bench is
>end test_bench;
>
>architecture struc of test_bench is
> component myself
> port (x: in bit; y: out bit);
> end component;
>
> signal fb: bit;
>begin
> C1: myself
> port map(fb,fb);
>end struc;
>*********************************************************
>
>If not I would like to see an example.

Nope, there's nothing recursive about this example. Here's an example of what I
mean:

entity ParityTree is
port (Inputs: in Bit_Vector;
Output: out Bit);
end entity ParityTree;

architecture Recursive of ParityTree is

component ParitySubTree
port (Inputs: in Bit_Vector;
Output: out Bit);
end component;

alias MyInput: Bit_Vector (1 TO Inputs'Length) IS Inputs;

signal LowerHalfParity: Bit;
signal UpperHalfParity: Bit;

for all:ParitySubTree use entity Work.ParitySubTree(Recursive); -- See below!
begin

GeneralCase:
if MyInput'Length > 1 generate
LowerSubTree:
ParitySubTree
port map (MyInput (1 TO MyInput'Length/2),
LowerHalfParity);
UpperSubTree:
ParitySubTree
port map (MyInput (MyInput'Length/2 + 1 TO MyInput'Length ),
UpperHalfParity);
PullItAllTogether:
Output <= LowerHalfParity xor UpperHalfParity;
end generate;

BaseCase:
if MyInput'Length = 1 generate
PassThrough:
Output <= MyInput(1);
end generate;
end Recursive;

The key is the configuration specification marked with the comment "See below!"
This configuration specification binds all instances of the ParitySubTree
component to the design entity found in library Work whose entity interface
is named ParitySubTree and whose architecture is named Recursive.

("But wait a minute! This configuration specification *occurs within the
architecture of very the design entity it binds to the component instances*!",
they say....)

This example is the VHDL implementation of:

"To make an n-bit parity generator, take two n/2-bit parity generators
and connect their outputs with an xor gate. A one-bit parity generator
is a piece of wire."

Hope this helps,

--Paul