llvm / llvm/circt

[Scheduling] Problem understanding `incomingDelay` and `outgoingDelay` in a simple example.

Open
#8,506 2 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

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

Description

I'm using the simplex scheduler with a simple example. But I think I misunderstood what the incomingDelay and outgoingDelay are. I understood that the operation must start at least incomingDelay before the next clock tick. After this clock ticks, the results will be available only after outgoingDelay. Am I right?
I have a problem in the following example when I try to schedule it using the simplex scheduler with a cycle-time of 10.0:

ssp.instance of "ChainingCyclicProblem" {
  library {
    operator_type @operator [latency<1>, incDelay<8.0>, outDelay<3.0>]
  }
  graph {
    %0 = operation<@operator> @op0(@op0 [dist<1>])
  }
}

This example represents the following simple circuit :

The operation has to start at 8.0 before the end of the cycle, and the results are available after 3.0 in the next cycle. Having II=1 is impossible as the operation needs the results of its previous iteration. Leads to the following schedule, with II=2 :

But when I use circt-opt with the argument -ssp-schedule="scheduler=simplex options=cycle-time=10.0" the result is :

ssp.instance of "ChainingCyclicProblem" [II<1>] {
  library {
    operator_type @operator [latency<1>, incDelay<8.000000e+00 : f32>, outDelay<3.000000e+00 : f32>]
  }
  graph {
    %0 = operation<@operator> @op0(@op0 [dist<1>]) [t<0>, z<0.000000e+00 : f32>]
  }
}

This means the schedule would look like this:

How is this schedule correct? What did I miss about circt's scheduling problems?

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 simplex scheduler and the circt-opt invocation using scheduler=simplex options=cycle-time=10.0; inspect how incomingDelay, outgoingDelay, and the reported II are interpreted. Compare the example's expected II=2 with the emitted II=1 schedule, and document whether the schedule is valid and what the delay semantics mean.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
compilers
Issue type
Documentation
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.