flow graph analysis and automation

[nmigen-issue-migration]

Issue by jordens Friday Sep 20, 2019 at 12:09 GMT Originally opened as https://github.com/m-labs/nmigen/issues/213

---

Develop tooling to help with non-trivial flow graphs. Somewhat like the old migen.flow scheme.

Features

• pipelining the components to get maximum throughput and minimum delay
• handle stb-style interfaces where data is not constantly streamed but "blanked"
• handle framed data that spans multiple clock cycles (eof a.k.a. sop/eop): determine overall cycle periods
• handle interfaces where different components in the graph need exclusive access to a shared resource (memory, shared data workspace) and access needs to be controlled by proper timing of the activity of a component.
• maybe handle stb/ack-style interfaces and implement back-pressure to dynamically pace upstream components
• maybe handle dynamically changing latencies

Implementation aspects/questions

• Each component (naming: block/actor/node?) would need to provide a latency matrix from its input to its output ports (group delay)
• Insert delays where required to compensate for unmatched latencies along different edges
• Framing: require constant frame size for the entire graph?
• Calculate cycle period for framed data (for constant frame size this is the slowest component in the graph) and generate counter(s) to trigger source components at the proper interval
• Provide verification processes for simulation that assert the correct timing pattern (of e.g. the stb signals) at the module boundaries. I.e. allow verification of the specified latency matrices.
• "Latency" may be hard to define for some components. E.g. an IIR filter. Interpretation of latency matching can be very context dependent.

Use cases, prior art:

• migen.flow
• SAWG: composes dozens of DSP blocks (spline interpolators, CORDICs, FIR filters, limiters etc) into a RF flow graph. Annotates latencies manually, and compensates for them so that every closed path in the graph (consisting of directed and latency-annotated edges) has zero total latency.
• SU-Servo: pipelines the ADC sampling/transfer, the IIR processing and the DDS SPI transfer stages manually and inserts "restart" counters so that the entire pipeline restarts automatically at the right time. Uses tokens that get passed along with data to signal activity.
• c.f. RFNoC: RF network on a chip for the USRP SDR hardware, mixed with gnuradio.

[nmigen-issue-migration]

Comment by whitequark Friday Sep 20, 2019 at 12:18 GMT

---

One thing to add is that for a while I wanted to add some first-class interface for specifying port directions, essentially the same thing as describing something as Signal(8), in in documentation but in code. Python type annotations might be helpful here.

• Provide verification processes for simulation that assert the correct timing pattern (of e.g. the stb signals) at the module boundaries. I.e. allow verification of the specified latency matrices.

Not just simulation; assertions for property testing ("formal verification") are much more valuable for this, since they are better at discovering edge cases.

• handle framed data that spans multiple clock cycles (eof a.k.a. sop/eop): determine overall cycle periods

There has been interest in having an AXI4-Stream-like interface in nMigen core (from @lambdaconcept, and it also exists in LiteX, showing substantial interest), so I think such stream interface should be added first.

[nmigen-issue-migration]

Comment by jordens Friday Sep 20, 2019 at 12:21 GMT

---

Right. A good stream interface is the foundation for all this.

[nmigen-issue-migration]

Comment by whitequark Friday Sep 20, 2019 at 12:26 GMT

---

My proposal for the stream interface is to use four signals: data, ack (aka tready in AXI4), stb (aka tvalid in AXI4), and eop (aka tlast in AXI4), all with AXI4-Stream semantics. Any objections?

[nmigen-issue-migration]

Comment by jordens Friday Sep 20, 2019 at 12:34 GMT

---

Perfect. It would be great if we can make this interface so smooth that the even the dumb usage (data in every cycle, no handshaking, always valid) requires no additional manual strapping of signals and is just as easy to use and always preferable over self.data = Signal(). That would preempt lots of adapter boilerplate when reusing components.

[nmigen-issue-migration]

Comment by whitequark Friday Sep 20, 2019 at 12:34 GMT

---

We can make ack, rdy and eop be Signal(reset=1), that should do the trick.

[nmigen-issue-migration]

Comment by jordens Friday Sep 20, 2019 at 18:45 GMT

---

Or a different constructor to make this usage explicit.

[nmigen-issue-migration]

Comment by mithro Monday Sep 30, 2019 at 20:40 GMT

---

Would be good to understand how this might match wishbone too?

[nmigen-issue-migration]

Comment by whitequark Monday Sep 30, 2019 at 20:41 GMT

---

I don't think this is relevant to Wishbone, since it does not have a streaming interface.

[nmigen-issue-migration]

Comment by mithro Monday Sep 30, 2019 at 20:47 GMT

---

I believe that @wallento was claiming otherwise at OrConf. Maybe he can confirm or deny that?

[nmigen-issue-migration]

Comment by whitequark Thursday Nov 28, 2019 at 19:53 GMT

---

I believe that an implementation of Rigel would provide every single feature @jordens requested.

[nmigen-issue-migration]

Comment by daveshah1 Thursday Nov 28, 2019 at 20:03 GMT

---

I would love something like that in nMigen, and might even be able to help next year. My past experience of line-buffer based video processing with moving windows has been very enjoyable, it would be interesting to work with something like that again.

[nmigen-issue-migration]

Comment by whitequark Thursday Nov 28, 2019 at 20:06 GMT

---

Sweet!

[nmigen-issue-migration]

Comment by mithro Thursday Nov 28, 2019 at 21:22 GMT

---

That paper is super interesting! This stuff is something that I could potentially look at providing funding around. I'm more interested in actually using it for graphics related stuff.