Using an external ILP solver

41 views
Skip to first unread message

Fanqi Yu

unread,
Aug 22, 2021, 10:40:17 AM8/22/21
to isl Development
Hi,

I'm learning about polyhedral compilation just recently. 

I'm wondering if it's possible to use an external MILP solver (e.g. SCIP, GLPK) for ISL. Perhaps there could be performance benefits? I'm trying to do some experiments.

By reading the source code, I figured that it should be sufficient by reimplementing the "solve_ilp" function defined in isl_ilp.c: 
  • "bset" is equivalent to a set of inequalities with the constraint that all variables be integers
  • "f" can be the objective function.
So the function of "solve_ilp" can be formulated into a standard MILP problem solvable by another MILP solver.

My questions are:
  1. Theoretically, is it possible (and beneficial) to use an external MILP solver for ISL?
  2. If so, is reimplementing the "solve_ilp" function sufficient?

Thank you very much!


Sven Verdoolaege

unread,
Aug 22, 2021, 2:47:44 PM8/22/21
to Fanqi Yu, isl Development
On Sun, Aug 22, 2021 at 07:40:17AM -0700, Fanqi Yu wrote:
> Hi,
>
> I'm learning about polyhedral compilation just recently.
>
> I'm wondering if it's possible to use an external MILP solver (e.g. SCIP,
> GLPK) for ISL. Perhaps there could be performance benefits? I'm trying to
> do some experiments.
>
> By reading the source code, I figured that it should be sufficient by
> reimplementing the "solve_ilp" function defined in isl_ilp.c:
>
> - "bset" is equivalent to a set of inequalities with the constraint that
> all variables be integers
> - "f" can be the objective function.
>
> So the function of "solve_ilp" can be formulated into a standard MILP
> problem solvable by another MILP solver.
>
> My questions are:
>
> 1. Theoretically, is it possible (and beneficial) to use an external
> MILP solver for ISL?

For solve_ilp, sure.

> 2. If so, is reimplementing the "solve_ilp" function sufficient?

I don't think this function is used all that much inside isl.


Exactly what performance issue are you trying to solve?

skimo

Fanqi Yu

unread,
Aug 23, 2021, 12:58:26 AM8/23/21
to isl Development
>  Exactly what performance issue are you trying to solve?

"Long scheduling times" mentioned in the Scheduling for PPCG report:

ppcg_known_issue.png


> I don't think this function is used all that much inside isl.

To make full use of an off-the-shelf ILP solver, are there other more frequently-used functions that should be modified too?


Thanks a lot,
Fanqi
 

Sven Verdoolaege

unread,
Aug 23, 2021, 12:30:02 PM8/23/21
to Fanqi Yu, isl Development
On Sun, Aug 22, 2021 at 09:58:26PM -0700, Fanqi Yu wrote:
> > Exactly what performance issue are you trying to solve?
>
> "Long scheduling times" mentioned in the Scheduling for PPCG
> <https://limo.libis.be/primo-explore/fulldisplay?docid=LIRIAS1656797&context=L&vid=Lirias&search_scope=Lirias&tab=default_tab&lang=en_US>
> report:

And on which scheduling problem do you run into this?

> > I don't think this function is used all that much inside isl.
>
> To make full use of an off-the-shelf ILP solver, are there other more
> frequently-used functions that should be modified too?

The report explains in detail where an LP and an ILP solver is used.
As the quoted section itself explains, using an off-the-shelf
(non-lexicographic) solver requires changes to how the solver is used.

skimo

Fanqi Yu

unread,
Aug 24, 2021, 3:13:01 AM8/24/21
to isl Development
在2021年8月24日星期二 UTC+8 上午12:30:02<sven.verdoolaege.isl> 写道:
On Sun, Aug 22, 2021 at 09:58:26PM -0700, Fanqi Yu wrote:
> > Exactly what performance issue are you trying to solve?
>
> "Long scheduling times" mentioned in the Scheduling for PPCG
> <https://limo.libis.be/primo-explore/fulldisplay?docid=LIRIAS1656797&context=L&vid=Lirias&search_scope=Lirias&tab=default_tab&lang=en_US>
> report:

And on which scheduling problem do you run into this?

I don't have a particular problem instance yet. Any suggestions or known problems on that? :-)



> > I don't think this function is used all that much inside isl.
>
> To make full use of an off-the-shelf ILP solver, are there other more
> frequently-used functions that should be modified too?

The report explains in detail where an LP and an ILP solver is used.

If I'm understanding correctly:
  • Pluto, the main scheduler, uses an ILP solver.
  • Feautrier, the fallback scheduler, also needs to solve an ILP problem sometimes "if the solution of the LP problem turns out be non-integral".
So why isn't the solve_ilp function used all that much? Am I missing something?


 
As the quoted section itself explains, using an off-the-shelf
(non-lexicographic) solver requires changes to how the solver is used.

Thanks a lot! I think I need some time to figure that out.




Best,
Fanqi

Sven Verdoolaege

unread,
Aug 24, 2021, 5:39:29 PM8/24/21
to Fanqi Yu, isl Development
On Tue, Aug 24, 2021 at 12:13:01AM -0700, Fanqi Yu wrote:
> 在2021年8月24日星期二 UTC+8 上午12:30:02<sven.verdoolaege.isl> 写道:
>
> > On Sun, Aug 22, 2021 at 09:58:26PM -0700, Fanqi Yu wrote:
> > > > Exactly what performance issue are you trying to solve?
> > >
> > > "Long scheduling times" mentioned in the Scheduling for PPCG
> > > <
> > https://limo.libis.be/primo-explore/fulldisplay?docid=LIRIAS1656797&context=L&vid=Lirias&search_scope=Lirias&tab=default_tab&lang=en_US>
> >
> > > report:
> >
> > And on which scheduling problem do you run into this?
>
>
> I don't have a particular problem instance yet. Any suggestions or known
> problems on that? :-)

Sounds like a solution looking for a problem...

> > > I don't think this function is used all that much inside isl.
> > >
> > > To make full use of an off-the-shelf ILP solver, are there other more
> > > frequently-used functions that should be modified too?
> >
> > The report explains in detail where an LP and an ILP solver is used.
>
>
> If I'm understanding correctly:
>
> - Pluto, the main scheduler, uses an ILP solver.
> - Feautrier, the fallback scheduler, also needs to solve an ILP problem
> sometimes "if the solution of the LP problem turns out be non-integral".
>
> So why isn't the solve_ilp function used all that much? Am I missing
> something?

Because solve_ilp is not a lexicographic solver and is therefore
not used by the scheduler at all.

skimo

Fanqi Yu

unread,
Aug 25, 2021, 1:25:12 PM8/25/21
to isl Development
On Wednesday, August 25, 2021 at 5:39:29 AM UTC+8 sven.verdoolaege.isl wrote:

Because solve_ilp is not a lexicographic solver and is therefore
not used by the scheduler at all.
 
Sad to hear that...
So isl_tab_basic_set_non_trivial_lexmin() looks like a lexicographical solver... Is it the ILP solver used by the scheduler?


Thank you very much,
Fanqi

Sven Verdoolaege

unread,
Aug 29, 2021, 2:03:07 PM8/29/21
to Fanqi Yu, isl Development
On Wed, Aug 25, 2021 at 10:25:12AM -0700, Fanqi Yu wrote:
> So isl_tab_basic_set_non_trivial_lexmin() looks like a lexicographical
> solver... Is it the ILP solver used by the scheduler?

Yes.

skimo

Fanqi Yu

unread,
Aug 30, 2021, 10:22:10 AM8/30/21
to isl Development
Thanks a lot!

Fanqi
Reply all
Reply to author
Forward
0 new messages