@inproceedings{Kelly1996closure,
author = {Wayne Kelly and
William Pugh and
Evan Rosser and
Tatiana Shpeisman},
title = {Transitive Closure of Infinite Graphs and Its Applications},
pages = {126-140},
editor = {Chua-Huang Huang and
P. Sadayappan and
Utpal Banerjee and
David Gelernter and
Alexandru Nicolau and
David A. Padua},
booktitle = {Languages and Compilers for Parallel Computing, 8th International
Workshop, LCPC'95, Columbus, Ohio, USA, August 10-12, 1995,
Proceedings},
publisher = {Springer},
series = {Lecture Notes in Computer Science},
volume = {1033},
year = {1996},
isbn = {3-540-60765-X},
doi = "10.1007/BFb0014196",
}
@inproceedings{Beletska2009,
author = {Beletska, Anna and Barthou, Denis and Bielecki, Wlodzimierz and Cohen, Albert},
title = {Computing the Transitive Closure of a Union of Affine Integer Tuple Relations},
booktitle = {COCOA '09: Proceedings of the 3rd International Conference on Combinatorial Optimization and Applications},
year = {2009},
isbn = {978-3-642-02025-4},
pages = {98--109},
location = {Huangshan, China},
doi = {10.1007/978-3-642-02026-1_9},
publisher = {Springer-Verlag},
address = {Berlin, Heidelberg},
}
@book{Schrijver1986,
author = "Schrijver, Alexander",
title = "Theory of Linear and Integer Programming",
publisher = "John Wiley \& Sons",
year = 1986
}
@article{Tarjan1972,
author = {Tarjan, Robert},
journal = {SIAM Journal on Computing},
number = {2},
pages = {146--160},
publisher = {SIAM},
title = {Depth-First Search and Linear Graph Algorithms},
volume = {1},
year = {1972},
doi = "10.1137/0201010",
}
@TechReport{ Omega_calc,
author = "Wayne Kelly and Vadim Maslov and William Pugh and Evan Rosser and Tatiana Shpeisman and Dave Wonnacott",
title = "The {Omega} Calculator and Library",
month = nov,
institution = "University of Maryland",
year = 1996
}
@TechReport{ Omega_lib,
author = "Wayne Kelly and Vadim Maslov and William Pugh and Evan Rosser and Tatiana Shpeisman and Dave Wonnacott",
title = "The {Omega} Library",
month = nov,
institution = "University of Maryland",
year = 1996
}
@unpublished{Verdoolaege2009isl,
author = "Verdoolaege, Sven",
title = "An integer set library for program analysis",
note = "Advances in the Theory of Integer Linear Optimization and its Extensions,AMS 2009 Spring Western Section Meeting, San Francisco, California, 25-26 April 2009",
month = Apr,
year = "2009",
url = "https://lirias.kuleuven.be/handle/123456789/228373",
}
@article{Barthou2000MSE,
author = {Barthou, Denis and Cohen, Albert and Collard, Jean-Fran\c{c}ois},
title = {Maximal Static Expansion},
journal = {Int. J. Parallel Program.},
volume = {28},
number = {3},
year = {2000},
issn = {0885-7458},
pages = {213--243},
doi = {10.1023/A:1007500431910},
publisher = {Kluwer Academic Publishers},
address = {Norwell, MA, USA},
}
@article{ Feautrier88parametric,
author = "P. Feautrier",
title = "Parametric Integer Programming",
journal = "RAIRO Recherche Op\'erationnelle",
volume = "22",
number = "3",
pages = "243--268",
year = "1988",
}
@Article{ Fea91,
author = {Feautrier, P.},
title = {Dataflow analysis of array and scalar references},
journal = {International Journal of Parallel Programming},
year = {1991},
OPTkey = {},
volume = {20},
number = {1},
OPTmonth = {},
pages = {23--53},
OPTnote = {},
OPTannote = {},
doi = "10.1007/BF01407931",
}
@INPROCEEDINGS{BouletRe98,
AUTHOR = {Pierre Boulet and Xavier Redon},
TITLE = {Communication Pre-evaluation in {HPF}},
BOOKTITLE = {EUROPAR'98},
PAGES = {263--272},
YEAR = 1998,
VOLUME = 1470,
series = {Lecture Notes in Computer Science},
PUBLISHER = {Springer-Verlag, Berlin},
ABSTRACT = { Parallel computers are difficult to program efficiently. We believe
that a good way to help programmers write efficient programs is to
provide them with tools that show them how their programs behave on
a parallel computer. Data distribution is the major performance
factor of data-parallel programs and so automatic data layout for
HPF programs has been studied by many researchers recently. The
communication volume induced by a data distribution is a good
estimator of the efficiency of this data distribution.
We present here a symbolic method to compute the communication
volume generated by a given data distribution during the program
writing phase (before compilation). We stay machine-independent to
assure portability. Our goal is to help the programmer understand
the data movements its program generates and thus find a good data
distribution. Our method is based on parametric polyhedral
computations. It can be applied to a large class of regular codes.},
doi = "10.1007/BFb0057861",
}
@INPROCEEDINGS {Verdoolaege2005experiences,
AUTHOR = "Verdoolaege, Sven and Beyls, Kristof and Bruynooghe, Maurice and Catthoor, Francky",
TITLE = {{E}xperiences with enumeration of integer projections of parametric polytopes},
BOOKTITLE = {{P}roceedings of 14th {I}nternational {C}onference on {C}ompiler {C}onstruction, {E}dinburgh, {S}cotland},
YEAR = {2005},
EDITOR = {Bodik, R.},
VOLUME = 3443,
pages = "91-105",
series = "Lecture Notes in Computer Science",
publisher = "Springer-Verlag",
address = "Berlin",
doi = "10.1007/b107108",
}
@article{Detlefs2005simplify,
author = {David Detlefs and Greg Nelson and James B. Saxe},
title = {Simplify: a theorem prover for program checking},
journal = {J. ACM},
volume = {52},
number = {3},
year = {2005},
issn = {0004-5411},
pages = {365--473},
doi = {10.1145/1066100.1066102},
publisher = {ACM},
address = {New York, NY, USA},
}
@phdthesis{Nelson1980phd,
author = {Charles Gregory Nelson},
title = {Techniques for program verification},
year = {1980},
order_no = {AAI8011683},
school = {Stanford University},
address = {Stanford, CA, USA},
}
@article{Woods2003short,
year = 2003,
Journal = "J. Amer. Math. Soc.",
volume = 16,
pages = "957--979",
month = apr,
title = {{Short rational generating functions for lattice point
problems}},
author = {Alexander Barvinok and Kevin Woods},
doi = "10.1090/S0894-0347-03-00428-4",
}
@misc{barvinok-0.22,
author = {Sven Verdoolaege},
title = {{\texttt{barvinok}}, version 0.22},
howpublished = {Available from \url{https://barvinok.sourceforge.io/}},
year = 2006
}
@inproceedings{DeLoera2004Three,
title = "Three Kinds of Integer Programming Algorithms based on Barvinok's Rational Functions",
author = "De Loera, J. A. and D. Haws and R. Hemmecke and P. Huggins and R. Yoshida",
booktitle = "Integer Programming and Combinatorial Optimization: 10th International IPCO Conference",
year = "2004",
month = jan,
series = "Lecture Notes in Computer Science",
Volume = 3064,
Pages = "244-255",
doi = "10.1007/978-3-540-25960-2_19",
}
@TechReport{Feautrier02,
author = {P. Feautrier and J. Collard and C. Bastoul},
title = {Solving systems of affine (in)equalities},
institution = {PRiSM, Versailles University},
year = 2002
}
@article{ Feautrier92multi,
author = "Paul Feautrier",
title = "Some Efficient Solutions to the Affine Scheduling Problem. {P}art {II}. Multidimensional Time",
journal = "International Journal of Parallel Programming",
volume = "21",
number = "6",
pages = "389--420",
year = "1992",
month = dec,
url = "citeseer.nj.nec.com/article/feautrier92some.html",
doi = "10.1007/BF01379404",
}
@misc{Bygde2010licentiate,
author = {Stefan Bygde},
title = {Static {WCET} Analysis based on Abstract Interpretation and Counting of Elements},
month = {March},
year = {2010},
howpublished = {Licentiate thesis},
publisher = {M{\"{a}}lardalen University Press},
url = {http://www.mrtc.mdh.se/index.php?choice=publications&id=2144},
}
@phdthesis{Meister2004PhD,
title = {Stating and Manipulating Periodicity in the Polytope Model. Applications to Program Analysis and Optimization},
author= {Beno\^it Meister},
school = {Universit\'e Louis Pasteur},
month = Dec,
year = {2004},
}
@inproceedings{Meister2008,
author = {Beno\^it Meister and Sven Verdoolaege},
title = {Polynomial Approximations in the Polytope Model: Bringing the Power
of Quasi-Polynomials to the Masses},
year = {2008},
booktitle = {Digest of the 6th Workshop on Optimization for DSP and Embedded Systems, ODES-6},
editor = "Jagadeesh Sankaran and Vander Aa, Tom",
month = apr,
}
@misc{Galea2009personal,
author = "Fran\c{c}ois Galea",
title = "personal communication",
year = 2009,
month = nov,
}
@misc{PPL,
author = "R. Bagnara and P. M. Hill and E. Zaffanella",
title = "The {Parma Polyhedra Library}",
howpublished = {\url{http://www.cs.unipr.it/ppl/}},
}
@TECHREPORT{Cook1991implementation,
AUTHOR={William Cook and Thomas Rutherford and Herbert E. Scarf and David F. Shallcross},
TITLE={An Implementation of the Generalized Basis Reduction Algorithm for Integer Programming},
YEAR=1991,
MONTH=Aug,
INSTITUTION={Cowles Foundation, Yale University},
TYPE={Cowles Foundation Discussion Papers},
NOTE={available at \url{http://ideas.repec.org/p/cwl/cwldpp/990.html}},
NUMBER={990},
}
@article{Karr1976affine,
author={ Michael Karr},
title={ Affine Relationships Among Variables of a Program },
journal={Acta Informatica},
Volume={6},
pages={133-151},
year={1976},
publisher={Springer-Verlag},
ignore={ },
doi = "10.1007/BF00268497",
}
@PhdThesis{Verhaegh1995PhD,
title = "Multidimensional Periodic Scheduling",
author = "Wim F. J. Verhaegh",
school = "Technische Universiteit Eindhoven",
year = 1995,
}
@INPROCEEDINGS{Seghir2006minimizing,
AUTHOR = "Rachid Seghir and Vincent Loechner",
TITLE = {Memory Optimization by Counting Points in Integer Transformations of Parametric Polytopes},
BOOKTITLE = {{P}roceedings of the {I}nternational {C}onference on {C}ompilers, {A}rchitectures, and {S}ynthesis for {E}mbedded Systems, CASES 2006, {S}eoul, {K}orea},
month = oct,
YEAR = {2006},
doi = {10.1145/1176760.1176771},
}
@misc{DeSmet2010personal,
author = "De Smet, Sven",
title = "personal communication",
year = 2010,
month = apr,
}
@inproceedings{Verdoolaege2015impact,
author = {Verdoolaege, Sven},
title = {Integer Set Coalescing},
booktitle = {Proceedings of the 5th International Workshop on
Polyhedral Compilation Techniques},
year = 2015,
month = Jan,
address = {Amsterdam, The Netherlands},
abstract = {
In polyhedral compilation, various core concepts such as the set
of statement instances, the access relations, the dependences and
the schedule are represented or approximated using sets and binary
relations of sequences of integers bounded by (quasi-)affine constraints.
When these sets and relations are represented in disjunctive normal form,
it is important to keep the number of disjuncts small, both for efficiency
and to improve the computation of transitive closure overapproximations
and AST generation. This paper describes the set coalescing operation
of isl that looks for opportunities to combine several disjuncts into
a single disjunct without affecting the elements in the set. The main
purpose of the paper is to explain the various heuristics and to prove
their correctness.
},
doi = "10.13140/2.1.1313.6968",
}
@misc{Verdoolaege2016tutorial,
author = "Sven Verdoolaege",
title = "Presburger Formulas and Polyhedral Compilation",
year = 2016,
doi = "10.13140/RG.2.1.1174.6323",
}
@inproceedings{Verdoolaege2009equivalence,
author = "Sven Verdoolaege and Gerda Janssens and Maurice Bruynooghe",
title = "Equivalence checking of static affine programs using widening to handle recurrences",
booktitle = "Computer Aided Verification 21",
month = Jun,
year = 2009,
pages = "599--613",
publisher = "Springer",
doi = "10.1007/978-3-642-02658-4_44",
}
@incollection{Verdoolaege2010isl,
author = {Verdoolaege, Sven},
title = {isl: An Integer Set Library for the Polyhedral Model},
booktitle = {Mathematical Software - ICMS 2010},
series = {Lecture Notes in Computer Science},
editor = {Fukuda, Komei and Hoeven, Joris and Joswig, Michael and Takayama, Nobuki},
publisher = {Springer},
isbn = {},
pages = {299-302},
volume = {6327},
year = {2010},
doi = {10.1007/978-3-642-15582-6_49},
}
@incollection{Verdoolaege2010networks,
author = "Verdoolaege, Sven",
title = "Polyhedral process networks",
editor = "Bhattacharrya, Shuvra and Deprettere, Ed and Leupers, Rainer and Takala, Jarmo",
publisher = "Springer",
year = "2010",
doi = "10.1007/978-1-4419-6345-1\_{}33",
pages = "931--965",
booktitle = "Handbook of Signal Processing Systems",
url = "https://lirias.kuleuven.be/handle/123456789/235370",
doi = "10.1007/978-1-4419-6345-1_33",
}
@InProceedings{Verdoolaege2011iscc,
author = {Sven Verdoolaege},
title = {Counting Affine Calculator and Applications},
booktitle = { First International Workshop on Polyhedral Compilation Techniques (IMPACT'11)},
address = { Chamonix, France},
month = apr,
year = {2011},
doi = "10.13140/RG.2.1.2959.5601",
}
@inproceedings{Verdoolaege2011closure,
author = {Verdoolaege, Sven and Cohen, Albert and Beletska, Anna},
title = {Transitive Closures of Affine Integer Tuple Relations and Their Overapproximations},
booktitle = {Proceedings of the 18th International Conference on Static Analysis},
series = {SAS'11},
year = {2011},
isbn = {978-3-642-23701-0},
location = {Venice, Italy},
pages = {216--232},
numpages = {17},
acmid = {2041570},
publisher = {Springer-Verlag},
address = {Berlin, Heidelberg},
doi = "10.1007/978-3-642-23702-7_18",
}
@article{Verdoolaege2013PPCG,
title={Polyhedral parallel code generation for {CUDA}},
author={Verdoolaege, Sven and Juega, Juan Carlos and Cohen, Albert and G{\'o}mez, Jos{\'e} Ignacio and Tenllado, Christian and Catthoor, Francky},
journal = {ACM Trans. Archit. Code Optim.},
volume={9},
number={4},
pages={54},
year={2013},
publisher={ACM},
doi = {10.1145/2400682.2400713},
}
@inproceedings{Verdoolaege2014impact,
author = {Verdoolaege, Sven and Guelton, Serge and
Grosser, Tobias and Cohen, Albert},
title = {Schedule Trees},
booktitle = {Proceedings of the 4th International Workshop on Polyhedral Compilation Techniques},
year = 2014,
month = Jan,
address = {Vienna, Austria},
url = {https://acohen.gitlabpages.inria.fr/impact/impact2014/papers/impact2014-verdoolaege.pdf},
abstract = {
Schedules in the polyhedral model, both those that represent the original
execution order and those produced by scheduling algorithms, naturally have the
form of a tree. Generic schedule representations proposed in the literature
encode this tree structure such that it is only implicitly available.
Following the internal representation of isl , we propose to represent
schedules as explicit trees and further extend the concept by introducing
different kinds of nodes. We compare our schedule trees to other
representations in detail and illustrate how they have been successfully used
to simplify the implementation of a non-trivial polyhedral compiler.
},
DOI = {10.13140/RG.2.1.4475.6001},
}
@article{Grosser2015AST,
author = "Tobias Grosser and Sven Verdoolaege and Albert Cohen",
title = "Polyhedral {AST} generation is more than scanning polyhedra",
journal = "ACM Transactions on Programming Languages and Systems",
issue_date = {August 2015},
volume = {37},
number = {4},
month = jul,
year = {2015},
issn = {0164-0925},
pages = {12:1--12:50},
articleno = {12},
numpages = {50},
url = {http://doi.acm.org/10.1145/2743016},
doi = {10.1145/2743016},
acmid = {2743016},
publisher = {ACM},
address = {New York, NY, USA},
keywords = {Polyhedral compilation, Presburger relations, code generation, index set splitting, unrolling},
}
@inproceedings{Verdoolaege2016reordering,
author = {Sven Verdoolaege and Albert Cohen},
title = "Live-Range Reordering",
booktitle = {Proceedings of the sixth International Workshop on
Polyhedral Compilation Techniques},
year = 2016,
month = Jan,
address = {Prague, Czech Republic},
doi = "10.13140/RG.2.1.3272.9680",
}
Codebase Browser
llvm