| @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{http://barvinok.gforge.inria.fr/}}, |
| 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 = {http://impact.gforge.inria.fr/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", |
| } |
