linked list in verilog

[Amir]

Hi,
I am looking for a linked list in Verilog, do you have an idea where
can I find one?
or do you have any implementation tips for it?


thanks
-Amir

 

[glen herrmannsfeldt]

Amir <sting.t2@gmail.com> wrote:

I am looking for a linked list in Verilog, do you have an idea where
can I find one?
or do you have any implementation tips for it?

What should the hardware look like? That will give you a
hint as to what you want in verilog.

I can imagine a RAM containing index values to itself.
(Either one or more for single or multiply linked lists.)

-- glen

 

[Jonathan Bromley]

On Sat, 20 Dec 2008 23:19:28 -0800 (PST), Amir wrote:

I am looking for a linked list in Verilog

The real question here is "why?"

Presumably this is for testbench code, rather
than for an RTL design?

It's worth asking what features of a linked
list are useful/good for you. Linked lists
provide:
- constant-time insert/delete at the head end
- constant-time append at the tail end
- linear-time (O(N)) search, insert, delete
at arbitrary positions in the list
What are you trying to do that needs these properties
and doesn't care about other things like faster
searching?

But the majority of traditional implementations
of linked lists assume the existence of dynamic
memory allocation and pointers, which don't exist
in Verilog. There is no practical way to implement
linked lists in Verilog in a way that preserves all
their desirable features, unless you do it in C and
use the Verilog PLI to get at the resulting
list structures.

You can get similar behaviour in Verilog using the
built-in $queue system functions. Don't forget that
almost all Verilog simulators also offer sparse
memory modelling, which is one of the things that
people often try to do with linked lists.

In SystemVerilog there is the "queue" construct,
which is like a linked list but MUCH better; and
there is the "associative array" construct which
offers very efficient searching.
--
Jonathan Bromley, Consultant

DOULOS - Developing Design Know-how
VHDL * Verilog * SystemC * e * Perl * Tcl/Tk * Project Services

Doulos Ltd., 22 Market Place, Ringwood, BH24 1AW, UK
jonathan.bromley@MYCOMPANY.com
http://www.MYCOMPANY.com

The contents of this message may contain personal views which
are not the views of Doulos Ltd., unless specifically stated.

 

[glen herrmannsfeldt]

Jonathan Bromley <jonathan.bromley@mycompany.com> wrote:

The real question here is "why?"

I agree, that is a good question.

(snip)

But the majority of traditional implementations
of linked lists assume the existence of dynamic
memory allocation and pointers, which don't exist
in Verilog.

It doesn't really have to be dynamic, as long as
there is enough of it. You could use a large
static array in Fortran 77 for example.

In verilog a RAM array could be used. It would
work for some pattern matching problems, for example.

-- glen

 

[Jonathan Bromley]

On Sun, 21 Dec 2008 22:40:27 +0000 (UTC),
glen herrmannsfeldt wrote:

But the majority of traditional implementations
of linked lists assume the existence of dynamic
memory allocation and pointers, which don't exist
in Verilog.

It doesn't really have to be dynamic, as long as
there is enough of it. You could use a large
static array in Fortran 77 for example.
In verilog a RAM array could be used.

Certainly true, but "enough of it" is tricky to
get right - it's doomed to be either wasteful or
limiting. Given the ready availability of access
to C via the PLI, it seems fairly futile to fake-up
data structures in Verilog arrays when you can do
the same stuff so much more elegantly in C.

Speaking as one whose first fumbling steps in
programming involved creating linked and stack
data structures using the static arrays of
BASIC and FOCAL (remember that, anyone?),
I have no desire to go back to that sort
of stuff if I can possibly avoid it.
--
Jonathan Bromley, Consultant

DOULOS - Developing Design Know-how
VHDL * Verilog * SystemC * e * Perl * Tcl/Tk * Project Services

Doulos Ltd., 22 Market Place, Ringwood, BH24 1AW, UK
jonathan.bromley@MYCOMPANY.com
http://www.MYCOMPANY.com

The contents of this message may contain personal views which
are not the views of Doulos Ltd., unless specifically stated.

 

[glen herrmannsfeldt]

Jonathan Bromley <jonathan.bromley@mycompany.com> wrote:
(snip, I wrote regarding linked lists)

It doesn't really have to be dynamic, as long as
there is enough of it. You could use a large
static array in Fortran 77 for example.
In verilog a RAM array could be used.

Certainly true, but "enough of it" is tricky to
get right - it's doomed to be either wasteful or
limiting.

I was assuming the OP wanted something that could
be done using real logic. RAM tends to come in fixed
sizes, and yes they are often either wasteful or
limiting, or both.

Given the ready availability of access
to C via the PLI, it seems fairly futile to fake-up
data structures in Verilog arrays when you can do
the same stuff so much more elegantly in C.

No idea what synthesis tools will do with that.

-- glen