doc/isl.bib

   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{https://barvinok.sourceforge.io/}},
 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,
 279 AUTHOR={William Cook and Thomas Rutherford and Herbert E. Scarf and David F. Shallcross},
 280 TITLE={An Implementation of the Generalized Basis Reduction Algorithm for Integer Programming},
 281 YEAR=1991,
 282 MONTH=Aug,
 283 INSTITUTION={Cowles Foundation, Yale University},
 284 TYPE={Cowles Foundation Discussion Papers},
 285 NOTE={available at \url{http://ideas.repec.org/p/cwl/cwldpp/990.html}},
 286 NUMBER={990},
 287 }
 288
 289  @article{Karr1976affine,
 290 author={ Michael Karr},
 291 title={ Affine Relationships Among Variables of a Program },
 292 journal={Acta Informatica},
 293 Volume={6},
 294 pages={133-151},
 295 year={1976},
 296 publisher={Springer-Verlag},
 297 ignore={ },
 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 = {
 333 In polyhedral compilation, various core concepts such as the set
 334 of statement instances, the access relations, the dependences and
 335 the schedule are represented or approximated using sets and binary
 336 relations of sequences of integers bounded by (quasi-)affine constraints.
 337 When these sets and relations are represented in disjunctive normal form,
 338 it is important to keep the number of disjuncts small, both for efficiency
 339 and to improve the computation of transitive closure overapproximations
 340 and AST generation.  This paper describes the set coalescing operation
 341 of isl that looks for opportunities to combine several disjuncts into
 342 a single disjunct without affecting the elements in the set.  The main
 343 purpose of the paper is to explain the various heuristics and to prove
 344 their 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 = {https://acohen.gitlabpages.inria.fr/impact/impact2014/papers/impact2014-verdoolaege.pdf},
 441  abstract = {
 442  Schedules in the polyhedral model, both those that represent the original
 443 execution order and those produced by scheduling algorithms, naturally have the
 444 form of a tree. Generic schedule representations proposed in the literature
 445 encode this tree structure such that it is only implicitly available.
 446 Following the internal representation of isl , we propose to represent
 447 schedules as explicit trees and further extend the concept by introducing
 448 different kinds of nodes. We compare our schedule trees to other
 449 representations in detail and illustrate how they have been successfully used
 450 to 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 }