search

llvm / circt

Circuit IR Compilers and Tools
https://circt.org
Other
1.63k stars 283 forks source link

Investigate using the simplex solver in MLIR's Presburger library for scheduling #2791

Open jopperm opened 2 years ago

jopperm commented 2 years ago

@makslevental pointed out that the Fast Presburger Library upstream contains a simplex solver. This could be a valuable middle ground between the scheduling-specific implementation in SimplexSchedulers.cpp and kicking off LP solving to a generic, external solver.

makslevental commented 2 years ago

re our convo this morning, just dropping some links for future reference on potentially getting something polyhedral in CIRCT

Polyhedral-based Dynamic Loop Pipelining for High-Level Synthesis

Improving Polyhedral Code Generation for High-Level Synthesis

and in particular generating systolic arraysusing polyhedral compilation

AutoSA: A Polyhedral Compiler for High-Performance Systolic Arrays on FPGA

PolySA: Polyhedral-Based Systolic Array Auto-Compilation

mikeurbach commented 2 years ago

Regarding "getting something polyhedral into CIRCT", we do have something, and it is here: https://github.com/llvm/circt/blob/main/lib/Conversion/AffineToStaticLogic/AffineToStaticLogic.cpp. So I'd hope to use that as a foothold to expand to some of the interesting/advanced techniques. Implementing something along the lines of AutoSA has been on my radar for the last year, and would be cool to intercept some of the systolic array modeling work @teqdruid has mentioned.

About this specific issue, I agree that using the upstream modeling/solver directly might be a good avenue to explore.

mikeurbach commented 2 years ago

While we are dropping references, @jopperm has previously pointed to Clockwork, and applying those techniques in CIRCT seems like a well-scoped project to tackle. There are lots of helpers with MLIR (unroll, unroll-and-jam, tile, fuse, etc) that can make this easier.

https://ieeexplore.ieee.org/document/9444097

makslevental commented 2 years ago

Regarding "getting something polyhedral into CIRCT", we do have something, and it is here: https://github.com/llvm/circt/blob/main/lib/Conversion/AffineToStaticLogic/AffineToStaticLogic.cpp. So I'd hope to use that as a foothold to expand to some of the interesting/advanced techniques. Implementing something along the lines of AutoSA has been on my radar for the last year, and would be cool to intercept some of the systolic array modeling work @teqdruid has mentioned.

About this specific issue, I agree that using the upstream modeling/solver directly might be a good avenue to explore.

ah yes I did remember you mentioning that there was code to pipeline loops but I didn't realize it was a polyhedral thing (which does make sense in retrospect).

jopperm commented 1 year ago

Update: @Groverkss started working on this.

makslevental commented 1 year ago

Regarding use of the upstream simplex solver:

@mikeurbach and i and @Superty discussed this at the LLVM meeting (or at least they discussed and I eavesdropped). I might be mistaken but I don't think this is feasible (no pun intended). @Superty's own assessment is that the simplex solver in FPL is specifically designed for 1) feasibility checks 2) small instances. Indeed it doesn't even do optimization of wrt objectives https://github.com/llvm/llvm-project/issues/55554. But @Groverkss et al can comment more authoritatively.

EDIT: after offline discussion with @Groverkss, I retract my doubts.