Close

Ring de-buffering

A project log for PEAC Pisano with End-Around Carry algorithm

Add X to Y and Y to X, says the song. And carry on.

yann-guidon-ygdesYann Guidon / YGDES 07/23/2021 at 16:206 Comments

The last log The train of thoughts and the red tail light introduced the principles for adapting a "token ring" idea to a JTAG-like chain. At the end, a major issue is identified: the host is slower and the nodes risk overflowing the output buffers. The protocol must be solid and needs to consider all corner cases...

And then I realised it was ridiculous to waste memory (that will always be too small or too large) to have a copy of all the states. No FIFO is required because the chain is the (variable length) FIFO itself: it must be flushed by the host anyway, at its own pace (10MHz is fine).

So all the nodes and the intercom are still synchronous to the computations, but the chain may only "shift" if the host requests to read one word. This is where it gets fun...

First, there must be a backwards signal from one node to the previous to enable the shifting of one position. This means that the "ready" signal will ripple through the chain in reverse direction. Several simultaneous signals may be present at the same time in the chain because the ripple takes at least 2µs to propagate through the whole chain (for 1000 nodes for example).

Second, the "ready" signals may stall when/where a node wants to insert data in the chain. There is no need to check that the X previous nodes are not intending to speak at the same time: if one node wants to speak it must wait for the condition of a "empty" type word in its own buffer, and the presence of the "ready signal". That's it. Of course the node must send contiguous words because otherwise its message might be "interrupted".

Commands (write packets are inserted in a special buffer at the start of the chain, which will be shifted any time the host reads the end.

To ease the management, the status of all the nodes can get condensed into a word (or a few) that counts how many nodes are waiting to send data. The host must read many, many empty words before one useful message appears at the end. To reduce the latency, the host should "poll" the chain by reading as often as possible, allowing data to move towards the output before the host knows something arrives. Smaller subchains reduce the latency/wait. Any node that remains idle is useless...

Maybe the "ready token" can be automatically generated by the end of the chain when it receives an empty word, allowing the chain to move forward by itself and reduce the latency.

I should draw diagrams and think further, but I am glad this roadblock is getting solved appropriately.

Discussions

Thomas wrote 07/24/2021 at 05:46 point

The auto-forward idea is nice. What if there were a small ring buffer at the end that collects all the useful tokens? In that case the host would be virtually de-coupled from the "token-ring", right?

Likewise even a single result buffer to receive the output of each node would de-couple production from transport...

  Are you sure? yes | no

Yann Guidon / YGDES wrote 07/24/2021 at 13:54 point

Since writing that log I've been thinking of one simple and major enhancement, where the token and the latency disappear. The topology remains the same but the host does not have to actively poll the output to shift the ring.

I'm working on this right now, the next log is in preparation :-)

  Are you sure? yes | no

Yann Guidon / YGDES wrote 07/24/2021 at 14:12 point

"Likewise even a single result buffer to receive the output of each node would de-couple production from transport..."

That extra buffer increases the gate count hence reduces the total number of nodes that fit in the FPGA.
With the 300K LUT chip, and with a rough estimate of 200 LUT per node, I can fit 1500 nodes. If the node uses 199 LUT, I increase the density to 1507 nodes.

Every LUT counts :-)

  Are you sure? yes | no

Thomas wrote 07/24/2021 at 16:08 point

I'm looking forward to the next log!

  Are you sure? yes | no

Yann Guidon / YGDES wrote 07/24/2021 at 16:16 point

I'm writing it :-)

  Are you sure? yes | no

Yann Guidon / YGDES wrote 07/25/2021 at 00:19 point

And now I'm adding a video.

  Are you sure? yes | no