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" <pklacka@trexenterprises.com> wrote in message news:501364cc437d0c00562c49ae102caf01@news.teranews.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. Weknow> through the Blake's CAM implementation and Jim's SyncRAM implementationthat> 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 fifocould> 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 mightshed> 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 isa> 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 theexact> same length that flowed in the opposite direction which contains thecompare> 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 willbe> 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. > >
changing values in a fifo
Started by ●January 20, 2004
Reply by ●January 22, 20042004-01-22
Reply by ●January 25, 20042004-01-25
"Patrick Klacka" <pklacka@trexenterprises.com> writes: Build with FFs? What's the depth X width? Homann -- Magnus Homann, M.Sc. CS & E d0asta@dtek.chalmers.se
Reply by ●January 25, 20042004-01-25
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 by ●January 26, 20042004-01-26
jim granville <no.spam@designtools.co.nz> 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.