Counting solutions to linear and nonlinear constraints through Ehrhart polynomials

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Counting solutions to linear and nonlinear constraints through Ehrhart polynomials: applications to analyze and transform scientific programs

Full text

Pdf (1.02 MB)

Source

International Conference on Supercomputing archive
Proceedings of the 10th international conference on Supercomputing table of contents

Philadelphia, Pennsylvania, United States

Pages: 278 - 285

Year of Publication: 1996

ISBN:0-89791-803-7

Author

Philippe Clauss

ICPS, Université Louis Pasteur, Strasbourg, Pôle API, Bd Sébastien Brant, 67400 Illkirch, France

Sponsor

SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 19, Citation Count: 31

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/237578.237617 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	A. I. Barvinok. A polynomial-time algorithm for counting integral points in polyhedra when the dimension is fixed. In Proc. of the $Jth Syrup. on the Foundations of Computer Science (FOCS'9$), pages 566-572. IEEE Computer Society Press, New York, 1993.
	2	A. I. Barvinok. Computing the Ehrhart Polynomial of a Convex Lattice Polytope. Discrete Comput. Geom., 12:35-48,1994.
	3	Ph. Clauss. The volume of a lattice polyhedron to enumerate processors and parallelism. Research Report ICPS 95-11, Submitted to publication, 1995. http://icps, u-strasbg, fr/pub-95/pub-95-11, ps. gz
	4	M. E. Dyer , A. M. Frieze, On the complexity of computing the volume of a polyhedron, SIAM Journal on Computing, v.17 n.5, p.967-974, October 1988 [doi>10.1137/0217060]
	5	E. Ehrhart. Sur les poly~dres rationnels homothdtiques n dimensions. C.R. Acad. Sci. Paris, 254:616-618, 1962.
	6	E. Ehrhart. Sur un probl~me de gdomdtrie diophantienne lin~aire I. J. Re~ne Angew. Math., 226:1-29, 1967.
	7	E. Ehrhart. Sur un probl~me de g~om~trie diophantienne lindaire II. J. Reine Angew. Math., 227:25-49, 1967.
	8	E. Ehrhart. Polynt~mes arithm~tiques et M~thode des Poly~dres en Uombznatoire. International Series of Numerical Mathematics, vol.35, Birkh~iuser Verlag, Basel/Stuttgart, 1977.
	9	Jeanne Ferrante , Vivek Sarkar , W. Thrash, On Estimating and Enhancing Cache Effectiveness, Proceedings of the Fourth International Workshop on Languages and Compilers for Parallel Computing, p.328-343, August 07-09, 1991
	10	P.M. Gruber and C.G. Lekkerkerker. Geometry of Numbers. North-Holland, Amsterdam, 1987.
	11	Mohammad R. Haghighat , Constantine D. Polychronopoulos, Symbolic Analysis: A Basis for Parallelization, Optimization, and Scheduling of Programs, Proceedings of the 6th International Workshop on Languages and Compilers for Parallel Computing, p.567-585, August 12-14, 1993
	12	M. Haghighat and C. Polychronopoulos. Symbolic analysis: A basis for parallelization, optimization and scheduling of programs. Technical Report 1317, CSRD, Univ. of Illinois, Aug. 1993.
	13	V. Loechner and D. K. Wilde. Parameterized polyhedra and their vertices. Research Report ICPS 95-16, Submitted to publication, 1995. http://lops, u-strasbg, fr/pub-95/pub-95-16, ps. gz
	14	I. G. Macdonald. The volume of a lattice polyhedron. Proc. Camb. Phil. Soc., 59:719-726, 1963.
	15	I. G. Macdonald. Polynomials associated with finite cell-complexes. J. London Math. Soc., 4(2):181-192, 1971.
	16	William Pugh, Counting solutions to Presburger formulas: how and why, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.121-134, June 20-24, 1994, Orlando, Florida, United States
	17	Alexandeer Schrijver, Theory of linear and integer programming, John Wiley & Sons, Inc., New York, NY, 1986
	18	Harold S. Stone , Dominique Thibaut, Footprints in the cache, Proceedings of the 1986 ACM SIGMETRICS joint international conference on Computer performance modelling, measurement and evaluation, p.4-8, May 1986, Raleigh, North Carolina, United States
	19	R. P. Stanley. Combinatorics and Commutative Algebra. Birkh~iuser, Boston, 1983.
	20	R P Stanley, Enumerative combinatorics, Wadsworth Publ. Co., Belmont, CA, 1986
	21	Nadia Tawbi, Estimation of Nested Loops Execution Time by Integer Arithmetic in Convex Polyhedra, Proceedings of the 8th International Symposium on Parallel Processing, p.217-221, April 01, 1994
	22	Nadia Tawbi , Paul Feautrier, Processor allocation and loop scheduling on multiprocessor computers, Proceedings of the 6th international conference on Supercomputing, p.63-71, July 19-24, 1992, Washington, D. C., United States [doi>10.1145/143369.143387]
	23	D. K. Wilde. A library for doing polyhedral operation~. Master's thesis, Oregon State Univ., Corvallis, Oregon, december 1993. Also published as IRISA technical report PI 785, Rennes, France, dec. 1993.

CITED BY 31

	Vincent Loechner , Catherine Mongenet, Communication Optimization for Affine Recurrence Equations Using Broadcast and Locality, International Journal of Parallel Programming, v.28 n.1, p.47-102, February 2000
	Induprakas Kodukula , Keshav Pingali, Data-Centric Transformations for Locality Enhancement, International Journal of Parallel Programming, v.29 n.3, p.319-364, June 2001
	Siddhartha Chatterjee , Erin Parker , Philip J. Hanlon , Alvin R. Lebeck, Exact analysis of the cache behavior of nested loops, ACM SIGPLAN Notices, v.36 n.5, p.286-297, May 2001
	Paolo D'Alberto , Alexandru Nicolau , Alexander Veidenbaum , Rajesh Gupta, Static analysis of parameterized loop nests for energy efficient use of data caches, Compilers and operating systems for low power, Kluwer Academic Publishers, Norwell, MA, 2003
	Somnath Ghosh , Margaret Martonosi , Sharad Malik, Cache miss equations: an analytical representation of cache misses, Proceedings of the 11th international conference on Supercomputing, p.317-324, July 07-11, 1997, Vienna, Austria
	Induprakas Kodukula , Keshav Pingali , Robert Cox , Dror Maydan, An experimental evaluation of tiling and shackling for memory hierarchy management, Proceedings of the 13th international conference on Supercomputing, p.482-491, June 20-25, 1999, Rhodes, Greece
	J. Ramanujam , Jinpyo Hong , Mahmut Kandemir , A. Narayan, Reducing memory requirements of nested loops for embedded systems, Proceedings of the 38th conference on Design automation, p.359-364, June 2001, Las Vegas, Nevada, United States
	Somnath Ghosh , Margaret Martonosi , Sharad Malik, Cache miss equations: a compiler framework for analyzing and tuning memory behavior, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.4, p.703-746, July 1999
	Kamen Yotov , Xiaoming Li , Gang Ren , Michael Cibulskis , Gerald DeJong , Maria Garzaran , David Padua , Keshav Pingali , Paul Stodghill , Peng Wu, A comparison of empirical and model-driven optimization, ACM SIGPLAN Notices, v.38 n.5, May 2003
	Somnath Ghosh , Margaret Martonosi , Sharad Malik, Precise miss analysis for program transformations with caches of arbitrary associativity, ACM SIGOPS Operating Systems Review, v.32 n.5, p.228-239, Dec. 1998
	Ying Zhao , Sharad Malik, Exact memory size estimation for array computations without loop unrolling, Proceedings of the 36th ACM/IEEE conference on Design automation, p.811-816, June 21-25, 1999, New Orleans, Louisiana, United States
	Rizos Sakellariou , John R. Gurd, Compile-time minimisation of load imbalance in loop nests, Proceedings of the 11th international conference on Supercomputing, p.277-284, July 07-11, 1997, Vienna, Austria
	Björn Franke , Michael O'boyle, Array recovery and high-level transformations for DSP applications, ACM Transactions on Embedded Computing Systems (TECS), v.2 n.2, p.132-162, May 2003
	Nawaaz Ahmed , Nikolay Mateev , Keshav Pingali, Synthesizing Transformations for Locality Enhancement of Imperfectly-Nested Loop Nests, International Journal of Parallel Programming, v.29 n.5, p.493-544, October 2001
	Vincent Loechner , Benoît Meister , Philippe Clauss, Precise Data Locality Optimization of Nested Loops, The Journal of Supercomputing, v.21 n.1, p.37-76, January 2002
	Chung-hsing Hsu , Ulrich Kremer, A Quantitative Analysis of Tile Size Selection Algorithms, The Journal of Supercomputing, v.27 n.3, p.279-294, March 2004
	Jingling Xue , Xavier Vera, Efficient and Accurate Analytical Modeling of Whole-Program Data Cache Behavior, IEEE Transactions on Computers, v.53 n.5, p.547-566, May 2004
	Kristof Beyls , Erik H. D'Hollander, Generating cache hints for improved program efficiency, Journal of Systems Architecture: the EUROMICRO Journal, v.51 n.4, p.223-250, April 2005
	Xavier Vera , Nerina Bermudo , Josep Llosa , Antonio González, A fast and accurate framework to analyze and optimize cache memory behavior, ACM Transactions on Programming Languages and Systems (TOPLAS), v.26 n.2, p.263-300, March 2004
	Paolo D'Alberto , Alexandru Nicolau , Alexander Veidenbaum , Rajesh Gupta, Line Size Adaptivity Analysis of Parameterized Loop Nests for Direct Mapped Data Cache, IEEE Transactions on Computers, v.54 n.2, p.185-197, February 2005
	Xavier Vera , Jaume Abella , Josep Llosa , Antonio González, An accurate cost model for guiding data locality transformations, ACM Transactions on Programming Languages and Systems (TOPLAS), v.27 n.5, p.946-987, September 2005
	Philippe Clauss , Vincent Loechner, Parametric Analysis of Polyhedral Iteration Spaces, Journal of VLSI Signal Processing Systems, v.19 n.2, p.179-194, July 1998
	Lakshminarayanan Renganarayana , Sanjay Rajopadhye, A Geometric Programming Framework for Optimal Multi-Level Tiling, Proceedings of the 2004 ACM/IEEE conference on Supercomputing, p.18, November 06-12, 2004
	Cedric Bastoul, Code Generation in the Polyhedral Model Is Easier Than You Think, Proceedings of the 13th International Conference on Parallel Architectures and Compilation Techniques, p.7-16, September 29-October 03, 2004
	Alexandru Turjan , Bart Kienhuis , Ed Deprettere, Classifying interprocess communication in process network representation of nested-loop programs, ACM Transactions on Embedded Computing Systems (TECS), v.6 n.2, p.13-es, May 2007
	Denis Barthou , Sebastien Donadio , Patrick Carribault , Alexandre Duchateau , William Jalby, Loop Optimization using Hierarchical Compilation and Kernel Decomposition, Proceedings of the International Symposium on Code Generation and Optimization, p.170-184, March 11-14, 2007
	Pascal Fradet , Julien Mallet, Compilation of a specialized functional language for massively parallel computers, Journal of Functional Programming, v.10 n.6, p.561-605, November 2000
	I. Kadayif , M. Kandemir, Tuning In-Sensor Data Filtering to Reduce Energy Consumption in Wireless Sensor Networks, Proceedings of the conference on Design, automation and test in Europe, p.20852, February 16-20, 2004
	William Thies , Frédéric Vivien , Saman Amarasinghe, A step towards unifying schedule and storage optimization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.29 n.6, p.34-es, October 2007
	Muthu Manikandan Baskaran , Uday Bondhugula , Sriram Krishnamoorthy , J. Ramanujam , Atanas Rountev , P. Sadayappan, Automatic data movement and computation mapping for multi-level parallel architectures with explicitly managed memories, Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming, February 20-23, 2008, Salt Lake City, UT, USA
	Lakshminarayanan Renganarayana , Sanjay Rajopadhye, Positivity, posynomials and tile size selection, Proceedings of the 2008 ACM/IEEE conference on Supercomputing, November 15-21, 2008, Austin, Texas