Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

flow graph analysis and automation #213

Open
nmigen-issue-migration opened this issue Sep 20, 2019 · 13 comments
Open

flow graph analysis and automation #213

nmigen-issue-migration opened this issue Sep 20, 2019 · 13 comments

Comments

@nmigen-issue-migration
Copy link

Issue by jordens
Friday Sep 20, 2019 at 12:09 GMT
Originally opened as m-labs/nmigen#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
Copy link
Author

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
Copy link
Author

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
Copy link
Author

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
Copy link
Author

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
Copy link
Author

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
Copy link
Author

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


Or a different constructor to make this usage explicit.

@nmigen-issue-migration
Copy link
Author

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
Copy link
Author

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
Copy link
Author

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
Copy link
Author

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
Copy link
Author

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
Copy link
Author

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


Sweet!

@nmigen-issue-migration
Copy link
Author

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Development

No branches or pull requests

2 participants