circt
circt copied to clipboard
[Scheduling] Add CPSAT scheduler (via OR-Tools) for `SharedOperatorsProblem`
This a WIP implementation of a scheduler for the SharedOperatorsProblem using a CP-SAT solver, through OR-Tools.
The formulation/model is the Resource Constrained Project Scheduling Problem (but I do not use the formulation from that link).
The current implementation is closely modeled on the OR-Tools example. That example is slightly more general (I think) than applies to CIRCT, namely it allows for multiple "recipes" for satisfying a task/op. Thus, the implementation needed to differ non-trivially. Since I am not a CP/SAT/scheduling/optimization wizard, my approach was to first build a parallel python version of that example, sans recipe functionality, all the while comparing the result of my altered script to the original. Hence all the auxilliary artifacts in test/Scheduling/or-tools/cpsat_scripts/; what you find there are problem instances (kindly provided OR-Tools as well) along with a test.sh that runs OR-Tools python implementation and my python implementation and diffs the results. Once the python version was done, I one for one ported to C++/CIRCT (including naming conventions, to make the porting process more brainless).
I plan to normalize the naming (i.e., switch to using the CIRCT naming schemes) and remove all of the supporting material after in-tree tests are robust (enough coverage) and pass (which they currently do not).
Any and all comments/questions/concerns welcome.
cc @jopperm
Awesome! Looks good on a very quick first glance. I'm currently away from my desk unfortunately, but I will do a detailed review early next week.
This should probably be marked as a draft PR. For actually landing this later, you'll need to split the PR in smaller chunks (e.g. 1: boilerplate, test pass 2: actual implementation). Also, the supplementary scripts will help us review the algorithm, but should probably be dropped before landing as well.
@jopperm this is ready for review but for some reason I can't click the "Request re-review" button.