Article

The potential of polyhedral optimization: an empirical study

Authors:

Andreas Simbürger,

Armin Größlinger,

Christian LengauerAuthors Info & Claims

ASE '13: Proceedings of the 28th IEEE/ACM International Conference on Automated Software Engineering

Pages 508 - 518

https://doi.org/10.1109/ASE.2013.6693108

Published: 11 November 2013 Publication History

Publisher Site Get Access

Abstract

Present-day automatic optimization relies on powerful static (i.e., compile-time) analysis and transformation methods. One popular platform for automatic optimization is the polyhedron model. Yet, after several decades of development, there remains a lack of empirical evidence of the model's benefits for real-world software systems. We report on an empirical study in which we analyzed a set of popular software systems, distributed across various application domains. We found that polyhedral analysis at compile time often lacks the information necessary to exploit the potential for optimization of a program's execution. However, when conducted also at run time, polyhedral analysis shows greater relevance for real-world applications. On average, the share of the execution time amenable to polyhedral optimization is increased by a factor of nearly 3. Based on our experimental results, we discuss the merits and potential of polyhedral optimization at compile time and run time.

References

[1]

P. Feautrier and C. Lengauer, "Polyhedron model," in Encyclopedia of Parallel Computing. Springer, 2011, pp. 1581-1592.

[2]

L. Rauchwerger, N. M. Amato, and D. A. Padua, "A scalable method for run-time loop parallelization," Int'l J. Parallel Programming, vol. 23, no. 6, pp. 537-576, 1995.

Digital Library

[3]

R. Asenjo, R. Castillo, F. Corbera, A. G. Navarro, A. Tineo, and E. L. Zapata, "Parallelizing irregular C codes assisted by interprocedural shape analysis," in Proc. Int'l Symp. Parallel and Distributed Processing (IPDPS). IEEE CS, 2008, pp. 1-12.

[4]

J.-F. Collard, "Automatic parallelization of while-loops using speculative execution," Int'l J. Parallel Programming, vol. 23, no. 2, pp. 191-219, 1995.

Digital Library

[5]

A. Größlinger, "The challenges of non-linear parameters and variables in automatic loop parallelisation," Doctoral thesis, Department of Informatics and Mathematics, University of Passau, 2009.

[6]

T. Grosser, H. Zheng, R. Alor, A. Simbürger, A. Größlinger, and L.-N. Pouchet, "Polly - polyhedral optimization in LLVM," in Proc. Int'l Workshop Polyhedral Compilation Techniques (IMPACT), 2011.

[7]

T. Grosser, A. Größlinger, and C. Lengauer, "Polly - performing polyhedral optimizations on a low-level intermediate representation," Parallel Processing Letters, vol. 22, no. 4, 2012, 28 pp.

[8]

K. Trifunovic, A. Cohen, D. Edelsohn, F. Li, T. Grosser, H. Jagasia, R. Ladelsky, S. Pop, J. Sjödin, and R. Upadrasta, "GRAPHITE two years after: First lessons learned from real-world polyhedral compilation," in Proc. Int'l Workshop GCC Research Opportunities (GROW), 2010, pp. 1-13, http://ctuning.org/workshop-grow10.

[9]

C. Lattner and V. Adve, "LLVM: A compilation framework for lifelong program analysis & transformation," in Proc. Int'l Symp. Code Generation and Optimization (CGO). IEEE CS, 2004, pp. 75-86.

Digital Library

[10]

C. Bastoul, "Code generation in the polyhedral model is easier than you think," in Proc. Int'l Conf. Parallel Architectures and Compilation Techniques (PACT). IEEE CS, 2004, pp. 7-16.

Digital Library

[11]

M. Davis, "Hilbert's tenth problem is unsolvable," American Mathematical Monthly, vol. 80, pp. 233-269, 1973.

[12]

"Clang: A C language family frontend for LLVM," http://clang.llvm.org.

[13]

"Rubinius: An environment for the Ruby programming language," http://rubini.us.

[14]

C. F. Bolz, A. Cuni, M. Fijalkowski, M. Leuschel, S. Pedroni, and A. Rigo, "Allocation removal by partial evaluation in a tracing JIT," in Proc. Int'l Workshop Partial Evaluation and Program Manipulation (PEPM). ACM, 2011, pp. 43-52.

Digital Library

[15]

R. Johnson, D. Pearson, and K. Pingali, "The program structure tree: Computing control regions in linear time," in Proc. Int'l Conf. Programming Language Design and Implementation (PLDI). ACM, 1994, pp. 171-185.

Digital Library

[16]

J. Levon, "OProfile - a system profiler for linux," http://oprofile.sourceforge.net/doc/, 2007.

[17]

J. Fenlason and R. Stallman, "GNU gprof," http://www.gnu.org/manual/gprof-2.9, 1988.

[18]

S. Browne, J. Dongarra, N. Garner, G. Ho, and P. Mucci, "A portable programming interface for performance evaluation on modern processors," Int'l J. High Performance Computing Applications, vol. 14, no. 3, pp. 189-204, 2000.

Digital Library

[19]

J. L. Hintze and R. D. Nelson, "Violin plots: A box plot-density trace synergism," The American Statistician, vol. 52, no. 2, pp. 181-184, 1998.

[20]

S. Shapiro and M. Wilk, "An analysis of variance test for normality (complete samples)," Biometrika, vol. 52, no. 3/4, pp. 591-611, 1965.

[21]

H. Mann and D. Whitney, "On a test of whether one of two random variables is stochastically larger than the other," Annals of Mathematical Statistics, vol. 18, no. 1, pp. 50-60, 1947.

[22]

W. Kruskal and W. Wallis, "Use of ranks in one-criterion variance analysis," J. of the American Statistical Association, vol. 47, no. 260, pp. 583-621, 1952.

[23]

"SunSpider: JavaScript Benchmark," http://www.webkit.org/perf/sunspider/sunspider.html, 2012.

[24]

A. Simbürger, S. Apel, A. Größlinger, and C. Lengauer, "The potential of polyhedral optimization," University of Passau, Tech. Rep. MIP-1301, 2013.

[25]

S. M. Alnaeli, A. Alali, and J. I. Maletic, "Empirically examining the parallelizability of open source software systems," in Proc. Int'l Conf. Working Conference Reverse Engineering (WCRE). IEEE CS, 2012, pp. 377-386.

Digital Library

[26]

M.-W. Benabderrahmane, L.-N. Pouchet, A. Cohen, and C. Bastoul, "The polyhedral model is more widely applicable than you think," in Proc. Int'l Conf. Compiler Construction (CC), ser. LNCS, vol. 6011. Springer, 2010, pp. 283-303.

Digital Library

[27]

M. Griebl and C. Lengauer, "On the space-time mapping of while-loops," Parallel Processing Letters, vol. 4, no. 3, pp. 221-232, 1994.

[28]

M. Griebl and C. Lengauer, "The loop parallelizer LooPo--Announcement," in Proc. Int'l Workshop Languages and Compilers for Parallel Computing (LCPC), ser. LNCS. Springer, 1997, vol. 1239, pp. 603-604.

Digital Library

[29]

L.-N. Pouchet, U. Bondhugula, C. Bastoul, A. Cohen, J. Ramanujam, and P. Sadayappan, "Combined iterative and model-driven optimization in an automatic parallelization framework," in Proc. Int'l Conf. High Performance Computing Networking, Storage and Analysis (SC). IEEE CS, 2010, pp. 1-11.

Digital Library

[30]

U. Bondhugula, A. Hartono, J. Ramanujam, and P. Sadayappan, "A practical automatic polyhedral parallelizer and locality optimizer," in Proc. Int'l Conf. Programming Language Design and Implementation (PLDI). ACM, 2008, pp. 101-113.

Digital Library

[31]

U. Bondhugula, M. Baskaran, S. Krishnamoorthy, J. Ramanujam, A. Rountev, and P. Sadayappan, "Automatic transformations for communication-minimized parallelization and locality optimization in the polyhedral model," in Proc. Int'l Conf. Compiler Construction (CC), ser. LNCS, vol. 4959. Springer, 2008, pp. 132-146.

Digital Library

[32]

L.-N. Pouchet, C. Bastoul, A. Cohen, and N. Vasilache, "Iterative optimization in the polyhedral model: Part I, one-dimensional time," in Proc. Int'l Symp. Code Generation and Optimization (CGO). IEEE CS, 2007, pp. 144-156.

Digital Library

[33]

L.-N. Pouchet, C. Bastoul, A. Cohen, and J. Cavazos, "Iterative optimization in the polyhedral model: Part II, multidimensional time," in Proc. Int'l Conf. Programming Language Design and Implementation (PLDI). ACM, 2008, pp. 90-100.

Digital Library

[34]

S. Girbal, N. Vasilache, C. Bastoul, A. Cohen, D. Parello, M. Sigler, and O. Temam, "Semi-automatic composition of loop transformations for deep parallelism and memory hierarchies," Int'l J. Parallel Programming, vol. 34, pp. 261-317, 2006.

Digital Library

[35]

U. Bondhugula, O. Gunluk, S. Dash, and L. Renganarayanan, "A model for fusion and code motion in an automatic parallelizing compiler," in Proc. Int'l Conf. Parallel Architecture and Compilation Techniques (PACT). ACM, 2010, pp. 343-352.

Digital Library

[36]

A. Jimborean, "Adapting the polytope model for dynamic and speculative parallelization," Doctoral thesis, Image Sciences, Computer Sciences and Remote Sensing Laboratory, University of Strasbourg, 2012.

[37]

L. Rauchwerger and D. A. Padua, "The LRPD test: Speculative run-time parallelization of loops with privatization and reduction parallelization," IEEE Trans. Parallel Distrib. Syst., vol. 10, no. 2, pp. 160-180, 1999.

Digital Library

Cited By

Smith GLiu ALyubomirsky SDavidson SMcMahan JTaylor MCeze LTatlock ZSamanta RDillig I(2021)Pure tensor program rewriting via access patterns (representation pearl)Proceedings of the 5th ACM SIGPLAN International Symposium on Machine Programming10.1145/3460945.3464953(21-31)Online publication date: 21-Jun-2021
https://dl.acm.org/doi/10.1145/3460945.3464953
Puthoor SLipasti MEvripidou SStenström PO'Boyle M(2018)Compiler assisted coalescingProceedings of the 27th International Conference on Parallel Architectures and Compilation Techniques10.1145/3243176.3243203(1-11)Online publication date: 1-Nov-2018
https://dl.acm.org/doi/10.1145/3243176.3243203

Recommendations

Relationships Between Polyhedral Convex Sets and Generalized Polyhedral Convex Sets
Abstract
In this paper, we study some relationships between polyhedral convex sets and generalized polyhedral convex sets. In particular, we clarify by a counterexample that the necessary and sufficient conditions for the separation of a convex set and a ...
On the polyhedral complexity of the integer points in a hyperball

Let B^n be a hyperball in R^n, n>=2, and denote B"Z^n=B^n@?Z^n. Define polyhedral facet complexity of B"Z^n as FC(B"Z^n)=min"P{f"n"-"1(P)} where P is an enclosing polyhedron for B"Z^n (i.e., P"Z=P@?Z^n=B"Z^n) and f"n"-"1(P) is the number of the (n-1)-...
Connectivity and $$W_v$$Wv-Paths in Polyhedral Maps on Surfaces

The $$W_v$$Wv-path conjecture due to Klee and Wolfe states that any two vertices of a simple polytope can be joined by a path that does not revisit any facet. This is equivalent to the well-known Hirsch conjecture. Klee proved that the $$W_v$$Wv-path ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ASE '13: Proceedings of the 28th IEEE/ACM International Conference on Automated Software Engineering

November 2013

765 pages

ISBN:9781479902156

General Chair:
Ewen Denney
SGT, NASA, Ames Research Center, Moffett Field
,
Program Chairs:
Tevfik Bultan
University of California, Santa Barbara
,
Andreas Zeller
Saarland University, Saarbrücken, Germany

Sponsors

NASA: National Aeronatics and Space Administration
SIGAI: ACM Special Interest Group on Artificial Intelligence
IEEE: IEEE Computer Society Technical Committee on Design Automation
SIGSOFT: ACM Special Interest Group on Software Engineering
Microsoft: Microsoft

Publisher

IEEE Press

Publication History

Published: 11 November 2013

Check for updates

Qualifiers

Article

Conference

ASE '13

Sponsor:

NASA
SIGAI
IEEE
SIGSOFT
Microsoft

ASE '13: Automated Software Engineering

November 11 - 15, 2013

CA, Silicon Valley, USA

Acceptance Rates

Overall Acceptance Rate 82 of 337 submissions, 24%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
30
Total Downloads

Downloads (Last 12 months)7
Downloads (Last 6 weeks)1

Reflects downloads up to 05 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Smith GLiu ALyubomirsky SDavidson SMcMahan JTaylor MCeze LTatlock ZSamanta RDillig I(2021)Pure tensor program rewriting via access patterns (representation pearl)Proceedings of the 5th ACM SIGPLAN International Symposium on Machine Programming10.1145/3460945.3464953(21-31)Online publication date: 21-Jun-2021
https://dl.acm.org/doi/10.1145/3460945.3464953
Puthoor SLipasti MEvripidou SStenström PO'Boyle M(2018)Compiler assisted coalescingProceedings of the 27th International Conference on Parallel Architectures and Compilation Techniques10.1145/3243176.3243203(1-11)Online publication date: 1-Nov-2018
https://dl.acm.org/doi/10.1145/3243176.3243203

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents