Linked lists in Verilog

[kb33]

Hi,

Is it possible (and has such a thing been done) to implement the
concept of linked lists in Verilog? Wouldn't it require something like
dynamic memory allocation (as opposed to static memory definition,
which is usually done)?

Thanks
Kanchan

 

[Jonathan Bromley]

On 22 Oct 2006 22:29:42 -0700, "kb33"
<kanchan.devarakonda@gmail.com> wrote:

Is it possible (and has such a thing been done) to implement the
concept of linked lists in Verilog? Wouldn't it require something like
dynamic memory allocation (as opposed to static memory definition,
which is usually done)?

Regular Verilog has no concept either of pointers or of dynamically
allocated memory. (I suppose that isn't strictly true in
Verilogs >=2001, because they have automatic storage for
tasks and functions; but there is still no notion of a free
store or heap, and no pointers.)

You can create a fixed-size array that is a pool
of free objects, and use link values (typically containing array
subscripts) within those objects to form a linked list - that brings
back happy memories of doing linked data structures in BASIC,
vintage 1975 But you may prefer to consider using the PLI
so that you can build your linked data structure in C, and access
it via function calls in Verilog.

SystemVerilog allows you to create arbitrary structures using
classes, and also has some special built-in data structures
(queues, associative arrays) that may solve your problem
without you having to write any linked-list code.

If you give some more details of your problem, you may get
alternative suggestions for solutions that use the standard
features of Verilog.
--
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.

 

[Jason Agron]

Yes, this is perfectly possible...

The term "pointer" is just a pseudonym for "address", and the typical
"addressable" block in hardware is memory. It is very easy to take a
chunk of memory and create an FSM to wrap around it that controls
adding and removing items from the "list". You can't dynamically
allocate hardware unless you are using some sort of partial
reconfiguration, but you can pre-allocate a bank of memory that is big
enough for your list to fit into, and when it is full, the FSM should
tell the "caller" in the form on an error.

Adding to the list may just involve writing to the next free address
and incrementing the tail "pointer", and removing from the list may
just involve decrementing the "head" pointer. This is analogous to the
way CPUs manage their internal stacks and queues.

-Jason Agron
University of Kansas


Jonathan Bromley wrote:

On 22 Oct 2006 22:29:42 -0700, "kb33"
kanchan.devarakonda@gmail.com> wrote:

Is it possible (and has such a thing been done) to implement the
concept of linked lists in Verilog? Wouldn't it require something like
dynamic memory allocation (as opposed to static memory definition,
which is usually done)?

Regular Verilog has no concept either of pointers or of dynamically
allocated memory. (I suppose that isn't strictly true in
Verilogs >=2001, because they have automatic storage for
tasks and functions; but there is still no notion of a free
store or heap, and no pointers.)

You can create a fixed-size array that is a pool
of free objects, and use link values (typically containing array
subscripts) within those objects to form a linked list - that brings
back happy memories of doing linked data structures in BASIC,
vintage 1975 But you may prefer to consider using the PLI
so that you can build your linked data structure in C, and access
it via function calls in Verilog.

SystemVerilog allows you to create arbitrary structures using
classes, and also has some special built-in data structures
(queues, associative arrays) that may solve your problem
without you having to write any linked-list code.

If you give some more details of your problem, you may get
alternative suggestions for solutions that use the standard
features of Verilog.
--
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.