FSM for control flow intensive applications

[MD I. Islam - Tamim]

Hi

I'm new to both HLS and XLS. Does XLS create a FSM  (finite state machine) for a control flow intensive application? Or it only generates a data flow graph where a MUX selects the final output? Could you please explain the rational behind the design choice?

Many thanks

Tamim

 

[Mark Heffernan]

Hi,

XLS can generate stateful designs in addition to combinational and pipelined feed-forward designs. The computation model we've chosen for stateful computation in XLS is based on Kahn Process Networks (KPNs). Roughly, a KPN is a collection of nodes, each with some recurrent state, that communicate amongst each other via FIFO channels. The model is fully general and can perform arbitrary computations. KPNs work well for HLS because they are latency insensitive. That is, the results produced by the network are not a function of the time it takes any particular node to execute nor the order in which the nodes execute. This is advantageous because the compiler is free to pipeline and schedule the blocks (KPN nodes) in a way that is best for QoR or performance and the final design will still perform the same computation.

In XLS the KPN nodes are called "procs". Unfortunately at the moment, procs are not well documented. They look roughly like functions which take a state value and produce a next state value. The proc body may contain send and receive nodes which can communicate with the outside world or other procs. Happy to answer any further questions you might have.

Mark

--
You received this message because you are subscribed to the Google Groups "xls-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to xls-dev+u...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/xls-dev/fcf14b25-669f-4242-80ba-395df4ecee11n%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[MD I. Islam - Tamim]

Thanks Mark for the detailed explanation!! Is it possible to set a target clock period and an initiation interval (II) for a 'proc'? Are there particular algorithms XLS is using to achieve that? Also, does XLS support resource sharing inside a 'proc'?

-Tamim

To view this discussion on the web visit https://groups.google.com/d/msgid/xls-dev/CAOi2v%2BSK2WBJbcxEok7nFwq%3DcC8DysGYcftkvdeuwnMzKsYk4g%40mail.gmail.com.

For more options, visit https://groups.google.com/d/optout.

CAUTION: EXTERNAL SENDER Do not click any links, open any attachments, or REPLY to the message unless you trust the sender and know the content is safe.

[zihao....@outlook.com]

I was also very curious about XLS's design decision! And the "procs" has been confusing me for a long time. I am extremely excited to see the final land of related features.

CIRCT's `Handshake` dialect seems to talk about the same topic, I mean the KPN. XLS is more like a lightweight, specialized, and less ambitious version of CIRCT. Many of the efforts are quite similar. For example, both projects deal with the scheduling problem, but the optimization objectives and algorithms are different.

Although a multi-level infrastructure is a heated topic, through XLS's practice, a single-level abstraction IR is expressive enough in a specialized scenario, and it's more lightweight.

- Zihao

[Mark Heffernan]

On Wed, Sep 7, 2022 at 8:52 PM MD I. Islam - Tamim <mis...@kent.edu> wrote:

Thanks Mark for the detailed explanation!! Is it possible to set a target clock period and an initiation interval (II) for a 'proc'? Are there particular algorithms XLS is using to achieve that? Also, does XLS support resource sharing inside a 'proc'?

XLS supports setting a target clock frequency and then pipelining based on that frequency. More details on the scheduler are available here: https://google.github.io/xls/scheduling/.  Under the hood is a system of difference constraints (SDC) solver (https://github.com/google/xls/blob/main/xls/scheduling/sdc_scheduler.h) which finds the schedule which minimizes the number of registers given the delay and pipeline length constraints, Unfortunately our open source delay models are not well developed or tested (https://github.com/google/xls/tree/main/xls/delay_model/models). The delay model's job is estimating the critical path delay for an expression (eg, a 32-bit adder takes X ps) and the model needs to be constructed for each technology node. We have internal delay models for production use but we can't open source them. We are working on improving the open source models for open pdks such as asap7 and sky130. Release isn't imminent, but hopefully it is something that can be done in the next few months.

II > 1 is supported but must be explicitly baked into the design of the proc by the user. That is, in procs we support conditional sends/receives on channels so an II>1 proc might receive data in one execution (tick) of the proc, and then hold off receiving more data while computation is going on. Resource reuse can be similarly expressed explicitly by the user (eg, a single multiplier is used for different computations in separate ticks of the proc by muxing in different operands) . We are working on supporting II > 1 and resource sharing automatically. That is, you can design the proc using unconditional send/receives and XLS will handle smearing that across multiple cycles with opportunistic resource sharing.

Mark

[Mark Heffernan]

On Fri, Sep 9, 2022 at 6:28 AM zihao....@outlook.com <zihao....@outlook.com> wrote:

I was also very curious about XLS's design decision! And the "procs" has been confusing me for a long time. I am extremely excited to see the final land of related features.

We hope to release some documentation about procs. Although they are fully featured and used internally, our documentation on them is very scarce :-(

Although a multi-level infrastructure is a heated topic, through XLS's practice, a single-level abstraction IR is expressive enough in a specialized scenario, and it's more lightweight.

We've tried to have a single IR which is expressive enough to cover the full compilation pipeline. The advantage of a single IR is that most components can be reused throughout the pipeline. The disadvantage is that specialization (for example, a separate high level and low level IR) can often be beneficial by supporting only the abstractions you need at the level you are working at. For XLS our opinion is that the benefits of a single IR outweigh the costs. It helps that the IR is dataflow throughout so there is no need to simultaneously support, say, an instruction/basic block form at the high-level and a dataflow form at the RTL-level.

Mark 

To view this discussion on the web visit https://groups.google.com/d/msgid/xls-dev/a7c62055-e66e-4cab-8d60-292375969581n%40googlegroups.com.

[MD I. Islam - Tamim]

Thanks Mark for the detailed explanation!!!!

-Tamim