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

[leothaud]

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?

[leothaud]

In my opinion, the current implementation of the simplex scheduling for the ChainingCyclicProblem is missing some constraints. The ChainingCyclicProblem was made by merging the ChainingProblem and the CyclicProblem. It was decided that back edges should not propagate delays.
The implementation lacks constraints to break the dependences chain on back edges (as in the function computeChainBreakingDependences). I think missing dependences would be something like: "For every backedge, either the predecessor ends at the beginning of the cycle, or the dependences chain has to be broken".
The problem with such constraints is that the start and end times in the cycle are not computed, which works great for the CyclicProblem. However, I am unsure how to represent it in a way that is acceptable to the Simplex scheduler. @jopperm, as you reviewed the pull request and implemented the ChainingSimplexScheduler, do you have an idea on how to represent the missing constraints, or do you think the ChainingCyclicSimplexScheduler should be removed until a proper implementation of a modulo scheduler for this problem is available?

[jopperm]

Thanks for reporting @leothaud, I think your analysis is correct, but on the other hand the limitatation is documented for the ChainingCyclicProblem in the design document:

circt/docs/Scheduling.md

Lines 276 to 283 in aa0a07d

	- [ChainingCyclicProblem](https://circt.llvm.org/doxygen/classcirct_1_1scheduling_1_1ChainingCyclicProblem.html):
	Extends `ChainingProblem` and `CyclicProblem` to consider the accumulation
	of physical propagation delays on combinational paths along SSA dependences
	on a cyclic scheduling problem. Note that the problem does not model
	propagation delays along inter-iteration dependences. These are commonly
	represented as auxiliary dependences, which are already excluded in the
	parent ChainingProblem. In addition, the ChainingCyclicProblem explicitly
	prohibits the use of def-use dependences with a non-zero distance.

NB: The class comment is less clear, as it just says delays are propagated along the SSA edges, and you cannot have SSA-backedges in the problem:

circt/include/circt/Scheduling/Problems.h

Lines 544 to 545 in aa0a07d

	/// This class models the accumulation of physical propagation delays on
	/// combinational paths along SSA dependences on a cyclic scheduling problem.

Hence I don't see an immediate need to remove the ChainingCyclicSimplexScheduler, as it works for the problem as documented.

As for lifting the limitation (TBD if that should be a new problem definition, or modification of the existing one):

• I don't recall having seen a formulation to extend the simplex scheduler accordingly in literature (sorry, it's been awhile...).
• "For every backedge, either the predecessor ends at the beginning of the cycle, or the dependences chain has to be broken" sounds promising, but it's not immediately obvious if that's too conservative/preventing optimal solutions. It might also be that the precomputing-chain-breaking-edges-approach doesn't work for delays on cycles, and therefore the startTimeInCycles must be computed by the scheduler directly.

NB 2: Your example also highlights that we don't model blocking times yet: The CyclicProblem and its descendants in-tree assume the operator types are fully-pipelined themselves, i.e. they have an "internal II=1" and can accept new data in every cycle. With the characteristics in your example, I believe this doesn't hold for @operator. The maximum blocking time across operator types is also a lower bound for the achievable II.