FPGA Central - World's 1st FPGA / CPLD Portal

FPGA Central

World's 1st FPGA Portal

 

Go Back   FPGA Groups > NewsGroup > FPGA

FPGA comp.arch.fpga newsgroup (usenet)

Reply
 
LinkBack Thread Tools Display Modes
  #1 (permalink)  
Old 01-20-2004, 11:04 PM
Patrick Klacka
Guest
 
Posts: n/a
Default changing values in a fifo

Hello

Given two values, compare_value and change_value, is it possible to
simultaneously update all values within a fifo that equal
compare_value to change_value without having to devote a number of
clock cycles proportional to the depth of the fifo?

The memory storage need not be a fifo, but that is how it should
function when reading and writing to it. Also, a value will only be
pulled off the fifo when another values is inserted, thus ensuring
that the fifo will always remain full. The simultaneous update of the
values will only happen at the time that a new value is inserted. I am
currently using an Altera Stratix 1S10, and could take advantage of
one or more of its features, but I'm hoping for a solution that is not
device dependent.

Thanks in advance for any help or suggestions that may lead to a
solution to this problem.

Patrick
Reply With Quote
  #2 (permalink)  
Old 01-20-2004, 11:39 PM
Eric Crabill
Guest
 
Posts: n/a
Default Re: changing values in a fifo


Hello,

Yes, you can do this in a single cycle. Is this a homework
question? You never know these days!

Instead of "clock cycles proportional to the depth" you will
end up with "hardware proportional to the depth". Also, I
think you would have a hard time using any kind of RAM to
implement the FIFO. This sounds "expensive"...

I prefer the brute force method. You could start by designing
a FIFO using standard D flip flops, using the same type of design
model that is used with RAMs (circular buffer with two pointers,
move the pointers, not the data -- otherwise the problem gets more
complicated).

You would then add an identity comparator and some muxing logic
for each FIFO word. When you present compare_value, the change
value, and some kind of enable signal, all words are evaluated
concurrently and updated at the next rising edge of the clock.

Eric

Patrick Klacka wrote:
>
> Hello
>
> Given two values, compare_value and change_value, is it possible to
> simultaneously update all values within a fifo that equal
> compare_value to change_value without having to devote a number of
> clock cycles proportional to the depth of the fifo?
>
> The memory storage need not be a fifo, but that is how it should
> function when reading and writing to it. Also, a value will only be
> pulled off the fifo when another values is inserted, thus ensuring
> that the fifo will always remain full. The simultaneous update of the
> values will only happen at the time that a new value is inserted. I am
> currently using an Altera Stratix 1S10, and could take advantage of
> one or more of its features, but I'm hoping for a solution that is not
> device dependent.
>
> Thanks in advance for any help or suggestions that may lead to a
> solution to this problem.
>
> Patrick

Reply With Quote
  #3 (permalink)  
Old 01-21-2004, 12:43 AM
Mike Treseler
Guest
 
Posts: n/a
Default Re: changing values in a fifo

Patrick Klacka wrote:
>
> Given two values, compare_value and change_value, is it possible to
> simultaneously update all values within a fifo that equal
> compare_value to change_value without having to devote a number of
> clock cycles proportional to the depth of the fifo?


Save some sort of CRC hash with each value push.
Apply correction(hash) when a value is popped.

> The memory storage need not be a fifo, but that is how it should
> function when reading and writing to it. Also, a value will only be
> pulled off the fifo when another values is inserted, thus ensuring
> that the fifo will always remain full.


That would mean only the first fifo location is ever used.

Maybe you mean a two port buffer.

-- Mike Treseler

Reply With Quote
  #4 (permalink)  
Old 01-21-2004, 01:46 AM
Peter Alfke
Guest
 
Posts: n/a
Default Re: changing values in a fifo

Patrick, you seem to be describing a Content-Addressable Memory ( a
CAM), which is notoriously difficult to implement and inefficient,
especially when it is to operate at a high rate.
Think about how you can (or cannot) compare and modify the content of
multiple locations simultaneously...

Peter Alfke, Xilinx Applications
==============================
Patrick Klacka wrote:
>
> Hello
>
> Given two values, compare_value and change_value, is it possible to
> simultaneously update all values within a fifo that equal
> compare_value to change_value without having to devote a number of
> clock cycles proportional to the depth of the fifo?
>
> The memory storage need not be a fifo, but that is how it should
> function when reading and writing to it. Also, a value will only be
> pulled off the fifo when another values is inserted, thus ensuring
> that the fifo will always remain full. The simultaneous update of the
> values will only happen at the time that a new value is inserted. I am
> currently using an Altera Stratix 1S10, and could take advantage of
> one or more of its features, but I'm hoping for a solution that is not
> device dependent.
>
> Thanks in advance for any help or suggestions that may lead to a
> solution to this problem.
>
> Patrick

Reply With Quote
  #5 (permalink)  
Old 01-21-2004, 03:14 AM
Patrick Klacka
Guest
 
Posts: n/a
Default Re: changing values in a fifo

"Mike Treseler" <[email protected]> wrote in message
news:[email protected]

> Save some sort of CRC hash with each value push.
> Apply correction(hash) when a value is popped.


I applied this method in the original design (on a pc), but it is not
deterministic - a value could change several times before it emerges from
the fifo, resulting in multiple indexes into an array to find the ultimate
answer. I can e-mail or post snippets of code to explain this better.

I tried building my own fifo, which took an input value, compare value, and
change value. Upon inserting the input value in the fifo, if any of the
values in the fifo were equal to the compare value, they were updated to the
change value. Given the depth requirements of the fifo, this implementation
will not fit in the fpga I am currently using.

I like the idea of not indexing into the fifo, and just applying some sort
of correction to the value that is removed, but there will need to be some
way of correcting that value in one cycle, to maintain deterministic
performance.

Patrick


Reply With Quote
  #6 (permalink)  
Old 01-21-2004, 05:08 AM
jim granville
Guest
 
Posts: n/a
Default Re: changing values in a fifo

Patrick Klacka wrote:

> "Mike Treseler" <[email protected]> wrote in message
> news:[email protected]
>
>
>>Save some sort of CRC hash with each value push.
>>Apply correction(hash) when a value is popped.

>
>
> I applied this method in the original design (on a pc), but it is not
> deterministic - a value could change several times before it emerges from
> the fifo, resulting in multiple indexes into an array to find the ultimate
> answer. I can e-mail or post snippets of code to explain this better.
>
> I tried building my own fifo, which took an input value, compare value, and
> change value. Upon inserting the input value in the fifo, if any of the
> values in the fifo were equal to the compare value, they were updated to the
> change value. Given the depth requirements of the fifo, this implementation
> will not fit in the fpga I am currently using.
>
> I like the idea of not indexing into the fifo, and just applying some sort
> of correction to the value that is removed, but there will need to be some
> way of correcting that value in one cycle, to maintain deterministic
> performance.


Yes, this would avoid the many-compares needed on change in-situ,
and could suit FPGA structures.
Assuming a byte wide FIFO, you could use 256 x 8 SyncRAM as the
check/replace -> init to Value==Index for nochange, and then
change contents as needed.

It does presume only one replace value is valid/alive for all
FIFO content.
( ie a delta to 'Change-to' applies from that instant, to all
FIFO change-froms.)

-jg



Reply With Quote
  #7 (permalink)  
Old 01-21-2004, 07:36 AM
Blake Henry
Guest
 
Posts: n/a
Default Re: changing values in a fifo

"Patrick Klacka" <[email protected]> wrote in message
news:[email protected] om...
> Hello
>
> Given two values, compare_value and change_value, is it possible to
> simultaneously update all values within a fifo that equal
> compare_value to change_value without having to devote a number of
> clock cycles proportional to the depth of the fifo?
>
> The memory storage need not be a fifo, but that is how it should
> function when reading and writing to it. Also, a value will only be
> pulled off the fifo when another values is inserted, thus ensuring
> that the fifo will always remain full. The simultaneous update of the
> values will only happen at the time that a new value is inserted. I am
> currently using an Altera Stratix 1S10, and could take advantage of
> one or more of its features, but I'm hoping for a solution that is not
> device dependent.
>
> Thanks in advance for any help or suggestions that may lead to a
> solution to this problem.
>
> Patrick


Nice problem, Patrick

I think I see two problems:
1) Store/retrieve data like a FIFO.
2) Conditionally replace all values.

So its like you need a FIFO that stores indexes into a table, then if you
receive a value that's already in the table, you do a compare and if there's
a match, you update the table with the new value. This way all other index
values in the table will all be replaced. Does this describe a viable
solution? If so, then it seems to me, the best way to do this is with a
CAM, a FIFO and a RAM. Input data goes into CAM and if you get a hit, you
save the CAM address into the FIFO. If not, you add the new value to the
CAM and the RAM at the same new address and store the address to the FIFO.
When data is read from the FIFO, you use the FIFO output to index into the
RAM to retrieve the value. If the compare matches, you write the new value
to the address in the CAM and the RAM.

The timing might be a little hairy, but I think this will work.

Hope this makes sense,
Blake


Reply With Quote
  #8 (permalink)  
Old 01-21-2004, 01:51 PM
Marc Randolph
Guest
 
Posts: n/a
Default Re: changing values in a fifo

Patrick Klacka wrote:
>>Save some sort of CRC hash with each value push.
>>Apply correction(hash) when a value is popped.

>
>
> I applied this method in the original design (on a pc), but it is not
> deterministic - a value could change several times before it emerges from
> the fifo, resulting in multiple indexes into an array to find the ultimate
> answer. I can e-mail or post snippets of code to explain this better.
>
> I tried building my own fifo, which took an input value, compare value, and
> change value. Upon inserting the input value in the fifo, if any of the
> values in the fifo were equal to the compare value, they were updated to the
> change value. Given the depth requirements of the fifo, this implementation
> will not fit in the fpga I am currently using.
>
> I like the idea of not indexing into the fifo, and just applying some sort
> of correction to the value that is removed, but there will need to be some
> way of correcting that value in one cycle, to maintain deterministic
> performance.


Howdy Patrick,

What is the size of compare_value, change_value, and most importantly,
how deep does the FIFO need to be?

Good luck,

Marc

Reply With Quote
  #9 (permalink)  
Old 01-21-2004, 07:37 PM
PO Laprise
Guest
 
Posts: n/a
Default Re: changing values in a fifo

Eric Crabill wrote:
> I prefer the brute force method. You could start by designing
> a FIFO using standard D flip flops, using the same type of design
> model that is used with RAMs (circular buffer with two pointers,
> move the pointers, not the data -- otherwise the problem gets more
> complicated).


If the FIFO is always full, does he even need to keep pointers? Why not
just a sort of "vector shift-register"?

--
Pierre-Olivier

-- to email me directly, remove all _N0SP4M_ from my address --

Reply With Quote
  #10 (permalink)  
Old 01-22-2004, 12:03 AM
Patrick Klacka
Guest
 
Posts: n/a
Default Re: changing values in a fifo

Thank you everyone for your suggestions thus far. It's clear that more
details are needed in order to better explore this problem. Please see
http://www.trexenterprises.com/~pklacka/fifo.html for implementations in C
code.

It seems that all the solutions favor one change to a particular value, but
do not consider the case of the changed value being changed. For example,
the value of 5 is changed to 6. Now a 5 is retrieved from the fifo. We know
through the Blake's CAM implementation and Jim's SyncRAM implementation that
the value of 5 will be transformed to a 6. Now the 6 is changed to a 7. When
we retrieve a 6 from the fifo, we get a 7 as intented. But should a 5 come
off the fifo, we still get a 6, unless some sort of recursion is used. The
recursion is what I am attempting to avoid. If all the 5's in the fifo could
be changed to 6's before the 6's get changed to 7's, then I have a working
solution.

Here is another idea that may be impossible to implement, but it might shed
some more light on what I am trying to achieve. Consider a full fifo that
expects a value to be inserted every time you remove a value. So there is a
constant flow from one side to the other. (I think this was correctly
likened to a vector shift-register) Could there be another fifo of the exact
same length that flowed in the opposite direction which contains the compare
and the change values. Each time a new value is inserted/removed from the
primary fifo, the secondary fifo compares register values at the same
location in the primary fifo, makes the appropriate change if necessary,
then shifts itself with a new value. Using this idea, all of the 5's will be
changed to 6's before the 6's get changed to 7's, but I think it uses the
same amount of resources as my original solution.


Reply With Quote
  #11 (permalink)  
Old 01-22-2004, 08:03 AM
Blake Henry
Guest
 
Posts: n/a
Default Re: changing values in a fifo

Patrick,

The solution I proposed would address changes to all occurances in the FIFO.
See, the FIFO only stores the address of an entry in the CAM/RAM. If the
value changes, the address remains the same, just the value in the CAM/RAM
gets changed. Unfortunately, Altera's CAM Megafunctions don't allow direct
reading of the CAM entries by address thus necessitating the RAM. The CAM
is simply used to determine whether a value has been submitted before or
not. The RAM stores the same value as the CAM except you can read it out by
indexing into the RAM using the FIFO output.

Blake

"Patrick Klacka" <[email protected]> wrote in message
news:[email protected] s.com...
> Thank you everyone for your suggestions thus far. It's clear that more
> details are needed in order to better explore this problem. Please see
> http://www.trexenterprises.com/~pklacka/fifo.html for implementations in C
> code.
>
> It seems that all the solutions favor one change to a particular value,

but
> do not consider the case of the changed value being changed. For example,
> the value of 5 is changed to 6. Now a 5 is retrieved from the fifo. We

know
> through the Blake's CAM implementation and Jim's SyncRAM implementation

that
> the value of 5 will be transformed to a 6. Now the 6 is changed to a 7.

When
> we retrieve a 6 from the fifo, we get a 7 as intented. But should a 5 come
> off the fifo, we still get a 6, unless some sort of recursion is used. The
> recursion is what I am attempting to avoid. If all the 5's in the fifo

could
> be changed to 6's before the 6's get changed to 7's, then I have a working
> solution.
>
> Here is another idea that may be impossible to implement, but it might

shed
> some more light on what I am trying to achieve. Consider a full fifo that
> expects a value to be inserted every time you remove a value. So there is

a
> constant flow from one side to the other. (I think this was correctly
> likened to a vector shift-register) Could there be another fifo of the

exact
> same length that flowed in the opposite direction which contains the

compare
> and the change values. Each time a new value is inserted/removed from the
> primary fifo, the secondary fifo compares register values at the same
> location in the primary fifo, makes the appropriate change if necessary,
> then shifts itself with a new value. Using this idea, all of the 5's will

be
> changed to 6's before the 6's get changed to 7's, but I think it uses the
> same amount of resources as my original solution.
>
>



Reply With Quote
  #12 (permalink)  
Old 01-25-2004, 09:07 PM
Magnus Homann
Guest
 
Posts: n/a
Default Re: changing values in a fifo

"Patrick Klacka" <[email protected]> writes:


Build with FFs? What's the depth X width?

Homann
--
Magnus Homann, M.Sc. CS & E
[email protected]
Reply With Quote
  #13 (permalink)  
Old 01-25-2004, 11:05 PM
jim granville
Guest
 
Posts: n/a
Default Re: changing values in a fifo

Patrick Klacka wrote:
> Thank you everyone for your suggestions thus far. It's clear that more
> details are needed in order to better explore this problem. Please see
> http://www.trexenterprises.com/~pklacka/fifo.html for implementations in C
> code.
>
> It seems that all the solutions favor one change to a particular value, but
> do not consider the case of the changed value being changed. For example,
> the value of 5 is changed to 6. Now a 5 is retrieved from the fifo. We know
> through the Blake's CAM implementation and Jim's SyncRAM implementation that
> the value of 5 will be transformed to a 6. Now the 6 is changed to a 7. When
> we retrieve a 6 from the fifo, we get a 7 as intented. But should a 5 come
> off the fifo, we still get a 6, unless some sort of recursion is used. The
> recursion is what I am attempting to avoid. If all the 5's in the fifo could
> be changed to 6's before the 6's get changed to 7's, then I have a working
> solution.


We need some more info on peak/average Read and Change stream rates,
and likely 'change depth'.
You can either change on read, and iterate until the change stack
stops changes, which will be HW frugal, but will have a finite settling
time. ( similar to a linked-list in SW )
Or, you can change all in-situ, but that is also likely to have a
finite settling time, as the delta-list will have to arrive
sequentially, but maybe at a much lower average rate.
This will read faster, but consume much more HW.
So it's like any parallel/serial trade off: HW vs bandwidth.

If the change-list stream rate is slow, you could do a combination of
table correct {fast, but one-deep), and interleaved scan change,
(slower, but will recurse).
Thus the FIFO becomes a bit like video memory, where one task
scans/changes and the other reads.
It would need "pause" ability, for when/if too many changes arrive
for the change paths to settle.

-jg

Reply With Quote
  #14 (permalink)  
Old 01-26-2004, 09:16 PM
Patrick Klacka
Guest
 
Posts: n/a
Default Re: changing values in a fifo

jim granville <[email protected]> wrote...

> We need some more info on peak/average Read and Change stream rates,
> and likely 'change depth'.


data is 8 bits, fifo is 512 entries, reading from the fifo happens
once every 10 clock cycles, a change happens approx. every 10th time,
and the average change depth is 2.

> You can either change on read, and iterate until the change stack
> stops changes, which will be HW frugal, but will have a finite settling
> time. ( similar to a linked-list in SW )


Yes, this is what I am currently doing. For situations where change
depth is 2 or less, this works fine. For change depths of 3 or more, I
have to buffer the incoming data.

> Or, you can change all in-situ, but that is also likely to have a
> finite settling time, as the delta-list will have to arrive
> sequentially, but maybe at a much lower average rate.
> This will read faster, but consume much more HW.
> So it's like any parallel/serial trade off: HW vs bandwidth.


I'm hoping for some clever solution that uses this method -
unfortunately the best I could come up with involved too much hardware
- leaving no room for anything else. If there was a way to implement
this smarter, I'm interested!

> If the change-list stream rate is slow, you could do a combination of
> table correct {fast, but one-deep), and interleaved scan change,
> (slower, but will recurse).
> Thus the FIFO becomes a bit like video memory, where one task
> scans/changes and the other reads.
> It would need "pause" ability, for when/if too many changes arrive
> for the change paths to settle.


I've considered this approach, and if you can figure out a way to make
it work, that would be great. The problem I had was that many values
could change to the same value, eliminating the possibility of using
another linked-list (reverse direction from the initial solution) to
iterate through the changes in the lookup-table.
Reply With Quote
Reply

Bookmarks

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are On


Similar Threads
Thread Thread Starter Forum Replies Last Post
Reading values of I/Os at certain times from verilog [email protected] Verilog 2 11-16-2008 06:22 AM
Printing values in uppercase lee nguyen Verilog 4 03-13-2006 12:22 AM
displaying signed values Srinivas Verilog 5 11-15-2004 05:25 AM


All times are GMT +1. The time now is 09:39 PM.


Powered by vBulletin® Version 3.8.0
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.
Search Engine Friendly URLs by vBSEO 3.2.0
Copyright 2008 @ FPGA Central. All rights reserved