llvm / llvm/circt

[Handshake] Using `LazyFork` can produce combinatorial cycles.

Open
#3,936 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Handshake
Dominant language
C++
Stars
2.2k
Forks
524
Avg merge
3d 2h
Merged PRs (30d)
46

Description

It seems that handshake's LazyFork violates a required property for composable dataflow circuits:

Consider the following example:

handshake.func @test(%arg0: none) -> (none) {
  %0:2 = lazy_fork [2] %arg0 : none
  %outCtrl = join %0#0, %0#1 : none, none
  return %outCtrl: none
}

when lowering this to FIRRTL and feeding it into firtool it will complain that there is a cycle involving the valid and ready signals of %0. LazyFork will only set the output's valid signal once all of them are ready to receive something. Join on the other hand, waits until all inputs are valid, before it sets their ready signals.

The paper which introduces compositional dataflow circuits states the following:

We avoid combinational cycles by insisting each cycle in the dataflow network have at least one
data and one control buffer (see Section 4) and by insisting no block has a combinational path from
a ready to a valid signal.

While we ensure the first property with buffer insertions, the latter is violated by LazyFork.

It seems that a correct LazyFork implementation requires changes to ensure it can be used correctly. Not sure if it will then still be "cheaper" than a normal/eager fork, though.

Contributor guide

No contributing guide indexed for this repository

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start with the Handshake LazyFork implementation and its lowering to FIRRTL. Reproduce the provided MLIR example and run it through firtool to confirm the valid-ready cycle. Done means LazyFork no longer creates combinational cycles when composed with Join while retaining correct dataflow behavior.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
compilers
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.