( ESNUG 372 Item 12 ) ------------------------------------------- [05/31/01]
Subject: ( ESNUG 370 #12 ) How To Design A Synthesizable Link List FIFO?
> Do you know anybody who has designed a synthesizable link-list FIFO?
> Would they like to share your code with me? I would also like to know
> how a link-list FIFO is different from a regular FIFO and their
> advantages/disadvantages.
>
> - Kusuma Arkalgud
> Jasmine Networks
From: Tom Coonan <Thomas.Coonan@Sciatl.com>
Hi, John,
We have such beasts here at Scientific Atlanta, but I don't think I can
share them. Sorry. I think the idea in our case was how to efficiently
deal with many multiple channels of data that all need a FIFO. For example,
imagine a DMA type of module that supports 32 channels. A FIFO is required
for each channel. The straight-forward tact is a dedicated FIFO RAM per
channel which probably means 32 RAMs all sized to handle the maximum
conceivable depth. This is perhaps wasteful and you end up with a lot of
distinct RAMs which may have layout or test implications. Alternatively,
use a single RAM and linked-lists for sharing the storage on an as-needed
basis. You literally implement a FREE list and a USED list and your FIFO
ADD/GET operations translate into list insertion and removal operations.
Each "channel" has its own registers pointing to the FREE/USED lists. Not
much different from the SW-based linked list code. State machine logic is
perfectly capable of doing all this.
If you can statistically garuntee that the sum total "depth" across all
channels is much less than the sum of all your worst-case FIFO depths; then
maybe you have saved a lot of RAM. There is data overhead in the RAM for
all the pointers and flags. You also are sharing/arbitrating access to the
single RAM, of course. This adds significant complexity and is much more
slippery to analyse from a systems perspective, so I'd recommend you
consider this very, very critically. You may be trading something
deterministic for something statistical. Sort of like how many Embedded
Systems programmers tend to shy away from using the heap unless absolutely
necessary. Good luck.
- Tom Coonan
Scientific Atlanta
---- ---- ---- ---- ---- ---- ----
From: [ A Synopsys DW AE ]
Hi John,
There is a synthesizable Linked-List FIFO controller in the DesignWare
Foundation library (DW_llfifocntl_s1_df). It can support up to 16
independent queues in the same physical memory. Hopefully this saves
Kusuma a considerable amount of design effort.
If he doesn't have the online docs handy, he can access SOLD (Synopsys
On-Line Documentation) from SolvNET. Just log into
http://solvnet.synopsys.com/
and click on "Search Documentation" in the upper right. He wants the
DesignWare document collection, under "2000.11/Other Manuals/DesignWare".
- [ A Synopsys DW AE ]
---- ---- ---- ---- ---- ---- ----
From: Atul Bhalla <atul@0-in.com>
Hello John,
Regarding Kusuma'a request for a Linked List FIFO, he may be able to find
something at http://www.opencores.com/projects.shtml
In order to verify his Linked List FIFO, try one of our monitors at:
http://www.0-in.com/subpages/prodtech/0in_cw_monitors.html
- Atul Bhalla
0-In Design Automation San Jose, CA
|
|
