3 ms·

A survey of general-purpose polyhedral compilers

32 points by matt_d 2y ago

rurban 2y ago
The pdf crashes my Android 12, but good to hear that gcc-graphite is still doing good, and there exist exciting new projects for the new LLVM MLIR target.
lupire 2y ago
Polyhedral compiling is apparently something to do with optimizing execution ordering in high-dimensional loops and other data structure traversals, to improve parallelization (parallelipipedization?) https://en.m.wikipedia.org/wiki/Polytope_model https://en.m.wikipedia.org/wiki/Polytope_model http://polyhedral.info/ http://polyhedral.info/
- deredede 2y ago
  Original focus was on parallelization, but nowadays polyhedral compilers also optimize for (cache) locality and reuse.
sjkoelle 2y ago
is this like https://icps.u-strasbg.fr/people/bastoul/public_html/research/papers/VBC06-CC.pdf https://icps.u-strasbg.fr/people/bastoul/public_html/researc...?
- deredede 2y ago
  No, "Polyhedral Code Generation in the Real World" (the paper you just linked) describes the code generation process of polyhedral compilers. Code generation is the last step of polyhedral compilation: first you model code using polyhedra, then you optimize in the polyhedral representation, and finally you generate new code from the optimized polyhedral representation. The survey paper in the OP compares different state-of-the art polyhedral compilers on full benchmarks (the complete process described above), not just code generation.
  - almostgotcaught 2y ago
    > No I don't understand the force of this no when the question is "is this like...". That's a solid yes as far as I can tell since the two papers are about the same general area. > first you model code using polyhedra No one does this - if your code is already known to be a "polyhedron" (a set of inequalities) then you would optimize like everyone else does: using simplex. In polyhedral compilers the hard part is finding the implicit polyhedra in loop nests. Optimization is also hard (np- hard) but there's no way around that so it doesn't matter and so everyone just uses ISL.
    - deredede 2y ago
      > I don't understand the force of this no when the question is "is this like...". That's a solid yes as far as I can tell since the two papers are about the same general area. I understood the question as asking whether the two papers contain similar content (which they do not) and replied in kind. You are right of course that they deal with the same general concept. > In polyhedral compilers the hard part is finding the implicit polyhedra in loop nests I was not very clear; this is what I had in mind when writing "you model code using polyhedra". I meant that the polyhedral compiler builds a model of the code using polyhedra as the first step of the compilation, not that the user would do it.

32 points by matt_d 2y ago

The pdf crashes my Android 12, but good to hear that gcc-graphite is still doing good, and there exist exciting new projects for the new LLVM MLIR target.

lupire 2y ago

Polyhedral compiling is apparently something to do with optimizing execution ordering in high-dimensional loops and other data structure traversals, to improve parallelization (parallelipipedization?) https://en.m.wikipedia.org/wiki/Polytope_model https://en.m.wikipedia.org/wiki/Polytope_model http://polyhedral.info/ http://polyhedral.info/

deredede 2y ago
Original focus was on parallelization, but nowadays polyhedral compilers also optimize for (cache) locality and reuse.

sjkoelle 2y ago

is this like https://icps.u-strasbg.fr/people/bastoul/public_html/research/papers/VBC06-CC.pdf https://icps.u-strasbg.fr/people/bastoul/public_html/researc...?

deredede 2y ago
No, "Polyhedral Code Generation in the Real World" (the paper you just linked) describes the code generation process of polyhedral compilers. Code generation is the last step of polyhedral compilation: first you model code using polyhedra, then you optimize in the polyhedral representation, and finally you generate new code from the optimized polyhedral representation. The survey paper in the OP compares different state-of-the art polyhedral compilers on full benchmarks (the complete process described above), not just code generation.
- almostgotcaught 2y ago
  > No I don't understand the force of this no when the question is "is this like...". That's a solid yes as far as I can tell since the two papers are about the same general area. > first you model code using polyhedra No one does this - if your code is already known to be a "polyhedron" (a set of inequalities) then you would optimize like everyone else does: using simplex. In polyhedral compilers the hard part is finding the implicit polyhedra in loop nests. Optimization is also hard (np- hard) but there's no way around that so it doesn't matter and so everyone just uses ISL.
  - deredede 2y ago
    > I don't understand the force of this no when the question is "is this like...". That's a solid yes as far as I can tell since the two papers are about the same general area. I understood the question as asking whether the two papers contain similar content (which they do not) and replied in kind. You are right of course that they deal with the same general concept. > In polyhedral compilers the hard part is finding the implicit polyhedra in loop nests I was not very clear; this is what I had in mind when writing "you model code using polyhedra". I meant that the polyhedral compiler builds a model of the code using polyhedra as the first step of the compilation, not that the user would do it.