1@inproceedings{Kelly1996closure, 2 author = {Wayne Kelly and 3 William Pugh and 4 Evan Rosser and 5 Tatiana Shpeisman}, 6 title = {Transitive Closure of Infinite Graphs and Its Applications}, 7 pages = {126-140}, 8 editor = {Chua-Huang Huang and 9 P. Sadayappan and 10 Utpal Banerjee and 11 David Gelernter and 12 Alexandru Nicolau and 13 David A. Padua}, 14 booktitle = {Languages and Compilers for Parallel Computing, 8th International 15 Workshop, LCPC'95, Columbus, Ohio, USA, August 10-12, 1995, 16 Proceedings}, 17 publisher = {Springer}, 18 series = {Lecture Notes in Computer Science}, 19 volume = {1033}, 20 year = {1996}, 21 isbn = {3-540-60765-X}, 22 doi = "10.1007/BFb0014196", 23} 24 25@inproceedings{Beletska2009, 26 author = {Beletska, Anna and Barthou, Denis and Bielecki, Wlodzimierz and Cohen, Albert}, 27 title = {Computing the Transitive Closure of a Union of Affine Integer Tuple Relations}, 28 booktitle = {COCOA '09: Proceedings of the 3rd International Conference on Combinatorial Optimization and Applications}, 29 year = {2009}, 30 isbn = {978-3-642-02025-4}, 31 pages = {98--109}, 32 location = {Huangshan, China}, 33 doi = {10.1007/978-3-642-02026-1_9}, 34 publisher = {Springer-Verlag}, 35 address = {Berlin, Heidelberg}, 36} 37 38@book{Schrijver1986, 39 author = "Schrijver, Alexander", 40 title = "Theory of Linear and Integer Programming", 41 publisher = "John Wiley \& Sons", 42 year = 1986 43} 44 45@article{Tarjan1972, 46 author = {Tarjan, Robert}, 47 journal = {SIAM Journal on Computing}, 48 number = {2}, 49 pages = {146--160}, 50 publisher = {SIAM}, 51 title = {Depth-First Search and Linear Graph Algorithms}, 52 volume = {1}, 53 year = {1972}, 54 doi = "10.1137/0201010", 55} 56 57@TechReport{ Omega_calc, 58 author = "Wayne Kelly and Vadim Maslov and William Pugh and Evan Rosser and Tatiana Shpeisman and Dave Wonnacott", 59 title = "The {Omega} Calculator and Library", 60 month = nov, 61 institution = "University of Maryland", 62 year = 1996 63} 64 65@TechReport{ Omega_lib, 66 author = "Wayne Kelly and Vadim Maslov and William Pugh and Evan Rosser and Tatiana Shpeisman and Dave Wonnacott", 67 title = "The {Omega} Library", 68 month = nov, 69 institution = "University of Maryland", 70 year = 1996 71} 72 73@unpublished{Verdoolaege2009isl, 74 author = "Verdoolaege, Sven", 75 title = "An integer set library for program analysis", 76 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", 77 month = Apr, 78 year = "2009", 79 url = "https://lirias.kuleuven.be/handle/123456789/228373", 80} 81 82@article{Barthou2000MSE, 83 author = {Barthou, Denis and Cohen, Albert and Collard, Jean-Fran\c{c}ois}, 84 title = {Maximal Static Expansion}, 85 journal = {Int. J. Parallel Program.}, 86 volume = {28}, 87 number = {3}, 88 year = {2000}, 89 issn = {0885-7458}, 90 pages = {213--243}, 91 doi = {10.1023/A:1007500431910}, 92 publisher = {Kluwer Academic Publishers}, 93 address = {Norwell, MA, USA}, 94} 95 96@article{ Feautrier88parametric, 97 author = "P. Feautrier", 98 title = "Parametric Integer Programming", 99 journal = "RAIRO Recherche Op\'erationnelle", 100 volume = "22", 101 number = "3", 102 pages = "243--268", 103 year = "1988", 104} 105 106@Article{ Fea91, 107 author = {Feautrier, P.}, 108 title = {Dataflow analysis of array and scalar references}, 109 journal = {International Journal of Parallel Programming}, 110 year = {1991}, 111 OPTkey = {}, 112 volume = {20}, 113 number = {1}, 114 OPTmonth = {}, 115 pages = {23--53}, 116 OPTnote = {}, 117 OPTannote = {}, 118 doi = "10.1007/BF01407931", 119} 120 121@INPROCEEDINGS{BouletRe98, 122 AUTHOR = {Pierre Boulet and Xavier Redon}, 123 TITLE = {Communication Pre-evaluation in {HPF}}, 124 BOOKTITLE = {EUROPAR'98}, 125 PAGES = {263--272}, 126 YEAR = 1998, 127 VOLUME = 1470, 128 series = {Lecture Notes in Computer Science}, 129 PUBLISHER = {Springer-Verlag, Berlin}, 130 ABSTRACT = { Parallel computers are difficult to program efficiently. We believe 131 that a good way to help programmers write efficient programs is to 132 provide them with tools that show them how their programs behave on 133 a parallel computer. Data distribution is the major performance 134 factor of data-parallel programs and so automatic data layout for 135 HPF programs has been studied by many researchers recently. The 136 communication volume induced by a data distribution is a good 137 estimator of the efficiency of this data distribution. 138 139 We present here a symbolic method to compute the communication 140 volume generated by a given data distribution during the program 141 writing phase (before compilation). We stay machine-independent to 142 assure portability. Our goal is to help the programmer understand 143 the data movements its program generates and thus find a good data 144 distribution. Our method is based on parametric polyhedral 145 computations. It can be applied to a large class of regular codes.}, 146 doi = "10.1007/BFb0057861", 147} 148 149@INPROCEEDINGS {Verdoolaege2005experiences, 150 AUTHOR = "Verdoolaege, Sven and Beyls, Kristof and Bruynooghe, Maurice and Catthoor, Francky", 151 TITLE = {{E}xperiences with enumeration of integer projections of parametric polytopes}, 152 BOOKTITLE = {{P}roceedings of 14th {I}nternational {C}onference on {C}ompiler {C}onstruction, {E}dinburgh, {S}cotland}, 153 YEAR = {2005}, 154 EDITOR = {Bodik, R.}, 155 VOLUME = 3443, 156 pages = "91-105", 157 series = "Lecture Notes in Computer Science", 158 publisher = "Springer-Verlag", 159 address = "Berlin", 160 doi = "10.1007/b107108", 161} 162 163@article{Detlefs2005simplify, 164 author = {David Detlefs and Greg Nelson and James B. Saxe}, 165 title = {Simplify: a theorem prover for program checking}, 166 journal = {J. ACM}, 167 volume = {52}, 168 number = {3}, 169 year = {2005}, 170 issn = {0004-5411}, 171 pages = {365--473}, 172 doi = {10.1145/1066100.1066102}, 173 publisher = {ACM}, 174 address = {New York, NY, USA}, 175 } 176 177@phdthesis{Nelson1980phd, 178 author = {Charles Gregory Nelson}, 179 title = {Techniques for program verification}, 180 year = {1980}, 181 order_no = {AAI8011683}, 182 school = {Stanford University}, 183 address = {Stanford, CA, USA}, 184 } 185 186@article{Woods2003short, 187 year = 2003, 188 Journal = "J. Amer. Math. Soc.", 189 volume = 16, 190 pages = "957--979", 191 month = apr, 192 title = {{Short rational generating functions for lattice point 193 problems}}, 194 author = {Alexander Barvinok and Kevin Woods}, 195 doi = "10.1090/S0894-0347-03-00428-4", 196} 197 198@misc{barvinok-0.22, 199 author = {Sven Verdoolaege}, 200 title = {{\texttt{barvinok}}, version 0.22}, 201 howpublished = {Available from \url{http://barvinok.gforge.inria.fr/}}, 202 year = 2006 203} 204 205@inproceedings{DeLoera2004Three, 206 title = "Three Kinds of Integer Programming Algorithms based on Barvinok's Rational Functions", 207 author = "De Loera, J. A. and D. Haws and R. Hemmecke and P. Huggins and R. Yoshida", 208 booktitle = "Integer Programming and Combinatorial Optimization: 10th International IPCO Conference", 209 year = "2004", 210 month = jan, 211 series = "Lecture Notes in Computer Science", 212 Volume = 3064, 213 Pages = "244-255", 214 doi = "10.1007/978-3-540-25960-2_19", 215} 216 217@TechReport{Feautrier02, 218 author = {P. Feautrier and J. Collard and C. Bastoul}, 219 title = {Solving systems of affine (in)equalities}, 220 institution = {PRiSM, Versailles University}, 221 year = 2002 222} 223 224@article{ Feautrier92multi, 225 author = "Paul Feautrier", 226 title = "Some Efficient Solutions to the Affine Scheduling Problem. {P}art {II}. Multidimensional Time", 227 journal = "International Journal of Parallel Programming", 228 volume = "21", 229 number = "6", 230 pages = "389--420", 231 year = "1992", 232 month = dec, 233 url = "citeseer.nj.nec.com/article/feautrier92some.html", 234 doi = "10.1007/BF01379404", 235} 236 237@misc{Bygde2010licentiate, 238 author = {Stefan Bygde}, 239 title = {Static {WCET} Analysis based on Abstract Interpretation and Counting of Elements}, 240 month = {March}, 241 year = {2010}, 242 howpublished = {Licentiate thesis}, 243 publisher = {M{\"{a}}lardalen University Press}, 244 url = {http://www.mrtc.mdh.se/index.php?choice=publications&id=2144}, 245} 246 247@phdthesis{Meister2004PhD, 248 title = {Stating and Manipulating Periodicity in the Polytope Model. Applications to Program Analysis and Optimization}, 249 author= {Beno\^it Meister}, 250 school = {Universit\'e Louis Pasteur}, 251 month = Dec, 252 year = {2004}, 253} 254 255@inproceedings{Meister2008, 256 author = {Beno\^it Meister and Sven Verdoolaege}, 257 title = {Polynomial Approximations in the Polytope Model: Bringing the Power 258 of Quasi-Polynomials to the Masses}, 259 year = {2008}, 260 booktitle = {Digest of the 6th Workshop on Optimization for DSP and Embedded Systems, ODES-6}, 261 editor = "Jagadeesh Sankaran and Vander Aa, Tom", 262 month = apr, 263} 264 265@misc{Galea2009personal, 266 author = "Fran\c{c}ois Galea", 267 title = "personal communication", 268 year = 2009, 269 month = nov, 270} 271 272@misc{PPL, 273 author = "R. Bagnara and P. M. Hill and E. Zaffanella", 274 title = "The {Parma Polyhedra Library}", 275 howpublished = {\url{http://www.cs.unipr.it/ppl/}}, 276} 277 278@TECHREPORT{Cook1991implementation, 279AUTHOR={William Cook and Thomas Rutherford and Herbert E. Scarf and David F. Shallcross}, 280TITLE={An Implementation of the Generalized Basis Reduction Algorithm for Integer Programming}, 281YEAR=1991, 282MONTH=Aug, 283INSTITUTION={Cowles Foundation, Yale University}, 284TYPE={Cowles Foundation Discussion Papers}, 285NOTE={available at \url{http://ideas.repec.org/p/cwl/cwldpp/990.html}}, 286NUMBER={990}, 287} 288 289 @article{Karr1976affine, 290author={ Michael Karr}, 291title={ Affine Relationships Among Variables of a Program }, 292journal={Acta Informatica}, 293Volume={6}, 294pages={133-151}, 295year={1976}, 296publisher={Springer-Verlag}, 297ignore={ }, 298 doi = "10.1007/BF00268497", 299} 300 301@PhdThesis{Verhaegh1995PhD, 302 title = "Multidimensional Periodic Scheduling", 303 author = "Wim F. J. Verhaegh", 304 school = "Technische Universiteit Eindhoven", 305 year = 1995, 306} 307 308@INPROCEEDINGS{Seghir2006minimizing, 309 AUTHOR = "Rachid Seghir and Vincent Loechner", 310 TITLE = {Memory Optimization by Counting Points in Integer Transformations of Parametric Polytopes}, 311 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}, 312 month = oct, 313 YEAR = {2006}, 314 doi = {10.1145/1176760.1176771}, 315} 316 317@misc{DeSmet2010personal, 318 author = "De Smet, Sven", 319 title = "personal communication", 320 year = 2010, 321 month = apr, 322} 323 324@inproceedings{Verdoolaege2015impact, 325 author = {Verdoolaege, Sven}, 326 title = {Integer Set Coalescing}, 327 booktitle = {Proceedings of the 5th International Workshop on 328 Polyhedral Compilation Techniques}, 329 year = 2015, 330 month = Jan, 331 address = {Amsterdam, The Netherlands}, 332 abstract = { 333In polyhedral compilation, various core concepts such as the set 334of statement instances, the access relations, the dependences and 335the schedule are represented or approximated using sets and binary 336relations of sequences of integers bounded by (quasi-)affine constraints. 337When these sets and relations are represented in disjunctive normal form, 338it is important to keep the number of disjuncts small, both for efficiency 339and to improve the computation of transitive closure overapproximations 340and AST generation. This paper describes the set coalescing operation 341of isl that looks for opportunities to combine several disjuncts into 342a single disjunct without affecting the elements in the set. The main 343purpose of the paper is to explain the various heuristics and to prove 344their correctness. 345 }, 346 doi = "10.13140/2.1.1313.6968", 347} 348 349@misc{Verdoolaege2016tutorial, 350 author = "Sven Verdoolaege", 351 title = "Presburger Formulas and Polyhedral Compilation", 352 year = 2016, 353 doi = "10.13140/RG.2.1.1174.6323", 354} 355 356@inproceedings{Verdoolaege2009equivalence, 357 author = "Sven Verdoolaege and Gerda Janssens and Maurice Bruynooghe", 358 title = "Equivalence checking of static affine programs using widening to handle recurrences", 359 booktitle = "Computer Aided Verification 21", 360 month = Jun, 361 year = 2009, 362 pages = "599--613", 363 publisher = "Springer", 364 doi = "10.1007/978-3-642-02658-4_44", 365} 366 367@incollection{Verdoolaege2010isl, 368 author = {Verdoolaege, Sven}, 369 title = {isl: An Integer Set Library for the Polyhedral Model}, 370 booktitle = {Mathematical Software - ICMS 2010}, 371 series = {Lecture Notes in Computer Science}, 372 editor = {Fukuda, Komei and Hoeven, Joris and Joswig, Michael and Takayama, Nobuki}, 373 publisher = {Springer}, 374 isbn = {}, 375 pages = {299-302}, 376 volume = {6327}, 377 year = {2010}, 378 doi = {10.1007/978-3-642-15582-6_49}, 379} 380 381@incollection{Verdoolaege2010networks, 382 author = "Verdoolaege, Sven", 383 title = "Polyhedral process networks", 384 editor = "Bhattacharrya, Shuvra and Deprettere, Ed and Leupers, Rainer and Takala, Jarmo", 385 publisher = "Springer", 386 year = "2010", 387 doi = "10.1007/978-1-4419-6345-1\_{}33", 388 pages = "931--965", 389 booktitle = "Handbook of Signal Processing Systems", 390 url = "https://lirias.kuleuven.be/handle/123456789/235370", 391 doi = "10.1007/978-1-4419-6345-1_33", 392} 393 394@InProceedings{Verdoolaege2011iscc, 395 author = {Sven Verdoolaege}, 396 title = {Counting Affine Calculator and Applications}, 397 booktitle = { First International Workshop on Polyhedral Compilation Techniques (IMPACT'11)}, 398 address = { Chamonix, France}, 399 month = apr, 400 year = {2011}, 401 doi = "10.13140/RG.2.1.2959.5601", 402} 403 404@inproceedings{Verdoolaege2011closure, 405 author = {Verdoolaege, Sven and Cohen, Albert and Beletska, Anna}, 406 title = {Transitive Closures of Affine Integer Tuple Relations and Their Overapproximations}, 407 booktitle = {Proceedings of the 18th International Conference on Static Analysis}, 408 series = {SAS'11}, 409 year = {2011}, 410 isbn = {978-3-642-23701-0}, 411 location = {Venice, Italy}, 412 pages = {216--232}, 413 numpages = {17}, 414 acmid = {2041570}, 415 publisher = {Springer-Verlag}, 416 address = {Berlin, Heidelberg}, 417 doi = "10.1007/978-3-642-23702-7_18", 418} 419 420@article{Verdoolaege2013PPCG, 421 title={Polyhedral parallel code generation for {CUDA}}, 422 author={Verdoolaege, Sven and Juega, Juan Carlos and Cohen, Albert and G{\'o}mez, Jos{\'e} Ignacio and Tenllado, Christian and Catthoor, Francky}, 423 journal = {ACM Trans. Archit. Code Optim.}, 424 volume={9}, 425 number={4}, 426 pages={54}, 427 year={2013}, 428 publisher={ACM}, 429 doi = {10.1145/2400682.2400713}, 430} 431 432@inproceedings{Verdoolaege2014impact, 433 author = {Verdoolaege, Sven and Guelton, Serge and 434 Grosser, Tobias and Cohen, Albert}, 435 title = {Schedule Trees}, 436 booktitle = {Proceedings of the 4th International Workshop on Polyhedral Compilation Techniques}, 437 year = 2014, 438 month = Jan, 439 address = {Vienna, Austria}, 440 url = {http://impact.gforge.inria.fr/impact2014/papers/impact2014-verdoolaege.pdf}, 441 abstract = { 442 Schedules in the polyhedral model, both those that represent the original 443execution order and those produced by scheduling algorithms, naturally have the 444form of a tree. Generic schedule representations proposed in the literature 445encode this tree structure such that it is only implicitly available. 446Following the internal representation of isl , we propose to represent 447schedules as explicit trees and further extend the concept by introducing 448different kinds of nodes. We compare our schedule trees to other 449representations in detail and illustrate how they have been successfully used 450to simplify the implementation of a non-trivial polyhedral compiler. 451 }, 452 DOI = {10.13140/RG.2.1.4475.6001}, 453} 454 455@article{Grosser2015AST, 456 author = "Tobias Grosser and Sven Verdoolaege and Albert Cohen", 457 title = "Polyhedral {AST} generation is more than scanning polyhedra", 458 journal = "ACM Transactions on Programming Languages and Systems", 459 issue_date = {August 2015}, 460 volume = {37}, 461 number = {4}, 462 month = jul, 463 year = {2015}, 464 issn = {0164-0925}, 465 pages = {12:1--12:50}, 466 articleno = {12}, 467 numpages = {50}, 468 url = {http://doi.acm.org/10.1145/2743016}, 469 doi = {10.1145/2743016}, 470 acmid = {2743016}, 471 publisher = {ACM}, 472 address = {New York, NY, USA}, 473 keywords = {Polyhedral compilation, Presburger relations, code generation, index set splitting, unrolling}, 474} 475 476@inproceedings{Verdoolaege2016reordering, 477 author = {Sven Verdoolaege and Albert Cohen}, 478 title = "Live-Range Reordering", 479 booktitle = {Proceedings of the sixth International Workshop on 480 Polyhedral Compilation Techniques}, 481 year = 2016, 482 month = Jan, 483 address = {Prague, Czech Republic}, 484 doi = "10.13140/RG.2.1.3272.9680", 485} 486