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} 23 24@inproceedings{Beletska2009, 25 author = {Beletska, Anna and Barthou, Denis and Bielecki, Wlodzimierz and Cohen, Albert}, 26 title = {Computing the Transitive Closure of a Union of Affine Integer Tuple Relations}, 27 booktitle = {COCOA '09: Proceedings of the 3rd International Conference on Combinatorial Optimization and Applications}, 28 year = {2009}, 29 isbn = {978-3-642-02025-4}, 30 pages = {98--109}, 31 location = {Huangshan, China}, 32 doi = {10.1007/978-3-642-02026-1_9}, 33 publisher = {Springer-Verlag}, 34 address = {Berlin, Heidelberg}, 35} 36 37@book{Schrijver1986, 38 author = "Schrijver, Alexander", 39 title = "Theory of Linear and Integer Programming", 40 publisher = "John Wiley \& Sons", 41 year = 1986 42} 43 44@article{Tarjan1972, 45 author = {Tarjan, Robert}, 46 journal = {SIAM Journal on Computing}, 47 number = {2}, 48 pages = {146--160}, 49 publisher = {SIAM}, 50 title = {Depth-First Search and Linear Graph Algorithms}, 51 volume = {1}, 52 year = {1972} 53} 54 55@TechReport{ Omega_calc, 56 author = "Wayne Kelly and Vadim Maslov and William Pugh and Evan Rosser and Tatiana Shpeisman and Dave Wonnacott", 57 title = "The {Omega} Calculator and Library", 58 month = nov, 59 institution = "University of Maryland", 60 year = 1996 61} 62 63@TechReport{ Omega_lib, 64 author = "Wayne Kelly and Vadim Maslov and William Pugh and Evan Rosser and Tatiana Shpeisman and Dave Wonnacott", 65 title = "The {Omega} Library", 66 month = nov, 67 institution = "University of Maryland", 68 year = 1996 69} 70 71@unpublished{Verdoolaege2009isl, 72 author = "Verdoolaege, Sven", 73 title = "An integer set library for program analysis", 74 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", 75 month = Apr, 76 year = "2009", 77 url = "https://lirias.kuleuven.be/handle/123456789/228373", 78} 79 80@article{Barthou2000MSE, 81 author = {Barthou, Denis and Cohen, Albert and Collard, Jean-Fran\c{c}ois}, 82 title = {Maximal Static Expansion}, 83 journal = {Int. J. Parallel Program.}, 84 volume = {28}, 85 number = {3}, 86 year = {2000}, 87 issn = {0885-7458}, 88 pages = {213--243}, 89 doi = {10.1023/A:1007500431910}, 90 publisher = {Kluwer Academic Publishers}, 91 address = {Norwell, MA, USA}, 92} 93 94@article{ Feautrier88parametric, 95 author = "P. Feautrier", 96 title = "Parametric Integer Programming", 97 journal = "RAIRO Recherche Op\'erationnelle", 98 volume = "22", 99 number = "3", 100 pages = "243--268", 101 year = "1988", 102} 103 104@Article{ Fea91, 105 author = {Feautrier, P.}, 106 title = {Dataflow analysis of array and scalar references}, 107 journal = {International Journal of Parallel Programming}, 108 year = {1991}, 109 OPTkey = {}, 110 volume = {20}, 111 number = {1}, 112 OPTmonth = {}, 113 pages = {23--53}, 114 OPTnote = {}, 115 OPTannote = {}, 116} 117 118@INPROCEEDINGS{BouletRe98, 119 AUTHOR = {Pierre Boulet and Xavier Redon}, 120 TITLE = {Communication Pre-evaluation in {HPF}}, 121 BOOKTITLE = {EUROPAR'98}, 122 PAGES = {263--272}, 123 YEAR = 1998, 124 VOLUME = 1470, 125 series = {Lecture Notes in Computer Science}, 126 PUBLISHER = {Springer-Verlag, Berlin}, 127 ABSTRACT = { Parallel computers are difficult to program efficiently. We believe 128 that a good way to help programmers write efficient programs is to 129 provide them with tools that show them how their programs behave on 130 a parallel computer. Data distribution is the major performance 131 factor of data-parallel programs and so automatic data layout for 132 HPF programs has been studied by many researchers recently. The 133 communication volume induced by a data distribution is a good 134 estimator of the efficiency of this data distribution. 135 136 We present here a symbolic method to compute the communication 137 volume generated by a given data distribution during the program 138 writing phase (before compilation). We stay machine-independent to 139 assure portability. Our goal is to help the programmer understand 140 the data movements its program generates and thus find a good data 141 distribution. Our method is based on parametric polyhedral 142 computations. It can be applied to a large class of regular codes.}, 143} 144 145@INPROCEEDINGS {Verdoolaege2005experiences, 146 AUTHOR = "Verdoolaege, Sven and Beyls, Kristof and Bruynooghe, Maurice and Catthoor, Francky", 147 TITLE = {{E}xperiences with enumeration of integer projections of parametric polytopes}, 148 BOOKTITLE = {{P}roceedings of 14th {I}nternational {C}onference on {C}ompiler {C}onstruction, {E}dinburgh, {S}cotland}, 149 YEAR = {2005}, 150 EDITOR = {Bodik, R.}, 151 VOLUME = 3443, 152 pages = "91-105", 153 series = "Lecture Notes in Computer Science", 154 publisher = "Springer-Verlag", 155 address = "Berlin", 156 doi = "10.1007/b107108", 157} 158 159@article{Detlefs2005simplify, 160 author = {David Detlefs and Greg Nelson and James B. Saxe}, 161 title = {Simplify: a theorem prover for program checking}, 162 journal = {J. ACM}, 163 volume = {52}, 164 number = {3}, 165 year = {2005}, 166 issn = {0004-5411}, 167 pages = {365--473}, 168 doi = {10.1145/1066100.1066102}, 169 publisher = {ACM}, 170 address = {New York, NY, USA}, 171 } 172 173@phdthesis{Nelson1980phd, 174 author = {Charles Gregory Nelson}, 175 title = {Techniques for program verification}, 176 year = {1980}, 177 order_no = {AAI8011683}, 178 school = {Stanford University}, 179 address = {Stanford, CA, USA}, 180 } 181 182@article{Woods2003short, 183 year = 2003, 184 Journal = "J. Amer. Math. Soc.", 185 volume = 16, 186 pages = "957--979", 187 month = apr, 188 title = {{Short rational generating functions for lattice point 189 problems}}, 190 author = {Alexander Barvinok and Kevin Woods}, 191} 192 193@misc{barvinok-0.22, 194 author = {Sven Verdoolaege}, 195 title = {{\texttt{barvinok}}, version 0.22}, 196 howpublished = {Available from \url{http://freshmeat.net/projects/barvinok/}}, 197 year = 2006 198} 199 200@inproceedings{DeLoera2004Three, 201 title = "Three Kinds of Integer Programming Algorithms based on Barvinok's Rational Functions", 202 author = "De Loera, J. A. and D. Haws and R. Hemmecke and P. Huggins and R. Yoshida", 203 booktitle = "Integer Programming and Combinatorial Optimization: 10th International IPCO Conference", 204 year = "2004", 205 month = jan, 206 series = "Lecture Notes in Computer Science", 207 Volume = 3064, 208 Pages = "244-255", 209} 210 211@TechReport{Feautrier02, 212 author = {P. Feautrier and J. Collard and C. Bastoul}, 213 title = {Solving systems of affine (in)equalities}, 214 institution = {PRiSM, Versailles University}, 215 year = 2002 216} 217 218@article{ Feautrier92multi, 219 author = "Paul Feautrier", 220 title = "Some Efficient Solutions to the Affine Scheduling Problem. {P}art {II}. Multidimensional Time", 221 journal = "International Journal of Parallel Programming", 222 volume = "21", 223 number = "6", 224 pages = "389--420", 225 year = "1992", 226 month = dec, 227 url = "citeseer.nj.nec.com/article/feautrier92some.html", 228} 229 230@misc{Bygde2010licentiate, 231 author = {Stefan Bygde}, 232 title = {Static {WCET} Analysis based on Abstract Interpretation and Counting of Elements}, 233 month = {March}, 234 year = {2010}, 235 howpublished = {Licentiate thesis}, 236 publisher = {M{\"{a}}lardalen University Press}, 237 url = {http://www.mrtc.mdh.se/index.php?choice=publications&id=2144}, 238} 239 240@phdthesis{Meister2004PhD, 241 title = {Stating and Manipulating Periodicity in the Polytope Model. Applications to Program Analysis and Optimization}, 242 author= {Beno\^it Meister}, 243 school = {Universit\'e Louis Pasteur}, 244 month = Dec, 245 year = {2004}, 246} 247 248@inproceedings{Meister2008, 249 author = {Beno\^it Meister and Sven Verdoolaege}, 250 title = {Polynomial Approximations in the Polytope Model: Bringing the Power 251 of Quasi-Polynomials to the Masses}, 252 year = {2008}, 253 booktitle = {Digest of the 6th Workshop on Optimization for DSP and Embedded Systems, ODES-6}, 254 editor = "Jagadeesh Sankaran and Vander Aa, Tom", 255 month = apr, 256} 257 258@misc{Galea2009personal, 259 author = "Fran\c{c}ois Galea", 260 title = "personal communication", 261 year = 2009, 262 month = nov, 263} 264 265@misc{PPL, 266 author = "R. Bagnara and P. M. Hill and E. Zaffanella", 267 title = "The {Parma Polyhedra Library}", 268 howpublished = {\url{http://www.cs.unipr.it/ppl/}}, 269} 270 271@TECHREPORT{Cook1991implementation, 272AUTHOR={William Cook and Thomas Rutherford and Herbert E. Scarf and David F. Shallcross}, 273TITLE={An Implementation of the Generalized Basis Reduction Algorithm for Integer Programming}, 274YEAR=1991, 275MONTH=Aug, 276INSTITUTION={Cowles Foundation, Yale University}, 277TYPE={Cowles Foundation Discussion Papers}, 278NOTE={available at \url{http://ideas.repec.org/p/cwl/cwldpp/990.html}}, 279NUMBER={990}, 280} 281 282 @article{Karr1976affine, 283author={ Michael Karr}, 284title={ Affine Relationships Among Variables of a Program }, 285journal={Acta Informatica}, 286Volume={6}, 287pages={133-151}, 288year={1976}, 289publisher={Springer-Verlag}, 290ignore={ }, 291} 292 293@PhdThesis{Verhaegh1995PhD, 294 title = "Multidimensional Periodic Scheduling", 295 author = "Wim F. J. Verhaegh", 296 school = "Technische Universiteit Eindhoven", 297 year = 1995, 298} 299 300@INPROCEEDINGS{Seghir2006minimizing, 301 AUTHOR = "Rachid Seghir and Vincent Loechner", 302 TITLE = {Memory Optimization by Counting Points in Integer Transformations of Parametric Polytopes}, 303 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}, 304 month = oct, 305 YEAR = {2006} 306} 307 308@misc{DeSmet2010personal, 309 author = "De Smet, Sven", 310 title = "personal communication", 311 year = 2010, 312 month = apr, 313} 314