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
jordens opened this issue Sep 20, 2019 · 13 comments
Open

flow graph analysis and automation #213

jordens opened this issue Sep 20, 2019 · 13 comments
Labels

Comments

@jordens
Copy link
Member

jordens commented Sep 20, 2019

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.
@whitequark
Copy link
Contributor

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.

@jordens
Copy link
Member Author

jordens commented Sep 20, 2019

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

@whitequark
Copy link
Contributor

whitequark commented Sep 20, 2019

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?

@jordens
Copy link
Member Author

jordens commented Sep 20, 2019

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.

@whitequark
Copy link
Contributor

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

@jordens
Copy link
Member Author

jordens commented Sep 20, 2019

Or a different constructor to make this usage explicit.

@mithro
Copy link

mithro commented Sep 30, 2019

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

@whitequark
Copy link
Contributor

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

@mithro
Copy link

mithro commented Sep 30, 2019

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

@whitequark
Copy link
Contributor

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

@daveshah1
Copy link

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.

@whitequark
Copy link
Contributor

Sweet!

@mithro
Copy link

mithro commented Nov 28, 2019

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
Labels
Projects
None yet
Development

No branches or pull requests

4 participants