Article

The Z-polyhedral model

Authors:

Sanjay RajopadhyeAuthors Info & Claims

PPoPP '07: Proceedings of the 12th ACM SIGPLAN symposium on Principles and practice of parallel programming

Pages 237 - 248

https://doi.org/10.1145/1229428.1229478

Published: 14 March 2007 Publication History

Abstract

The polyhedral model is a well developed formalism and has been extensively used in a variety of contexts viz. the automatic parallelization of loop programs, program verification, locality, hardware generationand more recently, in the automatic reduction of asymptotic program complexity. Such analyses and transformations rely on certain closure properties. However, the model is limited in expressivity and the need for a more general class of programs is widely known.

We provide the extension to ⁰-polyhedra which are the intersection of polyhedra and lattices. We prove the required closure properties using a novel representation and interpretation of ⁰-polyhedra. In addition, we also prove closure in the ⁰-polyhedral model under images by dependence functions---thereby proving that unions of LBLs, widely assumedto be a richer class of sets, is equal to unions of ⁰-polyhedra. Another corollary of this result is the equivalence of the unions of ⁰-polyhedraand Presburger sets. Our representation and closure properties constitute the foundations of the ⁰-polyhedral model. As an example, we presentthe transformation for automatic reduction of complexity in the ⁰-polyhedral model.

References

[1]

C. Bastoul. Generating loops for scanning polyhedra. Technical Report 2002/23, PRiSM, Versailles University, 2002.

[2]

Cédric Bastoul. Code generation in the polyhedral model is easier than you think. In IEEE PACT, pages 7--16, 2004.

Digital Library

[3]

T. Cormen, C. Leiserson, and R. Rivest. Introduction to Algorithms. McGraw-Hill, 1990.

Digital Library

[4]

A. Darte, Y. Robert, and F. Vivien. Scheduling and Automatic Parallelization. Birkhäuser, 2000.

Digital Library

[5]

Paul Feautrier. Dataflow analysis of array and scalar references. International Journal of Parallel Programming, 20(1):23--53, 1991.

Digital Library

[6]

Agustin Fernández, José M. Llabería, and Miguel Valero-García. Loop transformation using nonunimodular matrices. IEEE Trans. Parallel Distrib. Syst., 6(8):832--840, 1995.

Digital Library

[7]

Gautam, DaeGon Kim, and S. Rajopadhye. Scheduling in the ⁰--polyhedral model. In IPDPS'07: International Parallel and Distributed Processing Symposium. (accepted), 2007.

[8]

Gautam and S. Rajopadhye. Simplifying reductions. In POPL '06: Symposium on Principles of programming languages, pages 30--41, New York, NY, USA, 2006. ACM Press.

Digital Library

[9]

C. Hermite. Sur l'introduction des variables continues dans la theorie des nombres. J. Reine Angew. Math., 41:191--216, 1851.

[10]

H. Le Verge. Un environnement de transformations de programmmes pour la synthèse d'architectures régulières. PhD thesis, L'Universit& 233; de Rennes I, IRISA, Campus de Beaulieu, Rennes, France, Oct 1992.

[11]

H. Le Verge. Recurrences on lattice polyhedra and their applications. April 1995 (Based on a manuscript written by H. Le Verge just before his untimely death in 1994).

[12]

P. Lenders and S. Rajopadhye. Multirate VLSI arrays and their synthesis. IEEE Transactions on Computers, 46(5):515--529, May 1997.

Digital Library

[13]

Wei Li and Keshav Pingali. A singular loop transformation framework based on non-singular matrices. Int. J. Parallel Program., 22(2):183-- 205, 1994.

Digital Library

[14]

C. Mauras. ALPHA: un langage équationnel pour la conception et la programmation d'architectures parallèles synchrones. PhD thesis, L'Université de Rennes I, Rennes, France, December 1989.

[15]

S. P. K Nookala and T. Risset. A library for z-polyhedral operations. Technical Report PI 1330, IRISA, Rennes, France, 2000.

[16]

Fabien Quilleré, Sanjay Rajopadhye, and Doran Wilde. Generation of efficient nested loops from polyhedra. Int. J. Parallel Program., 28(5):469--498, 2000.

Digital Library

[17]

P. Quinton, S. Rajopadhye, and T. Risset. Extension of the alpha language to recurrences on sparse periodic domains. In ASAP '96: International Conference on Application-Specific Systems, Architectures, and Processors, page 391, 1996.

Digital Library

[18]

P. Quinton, S. V. Rajopadhye, and T. Risset. On manipulating !- polyhedra using a canonical representation. Parallel Processing Letters, 7(2):181--194, June 1997.

[19]

J. Ramanujam. Beyond unimodular transformations. J. Supercomput., 9(4):365--389, 1995.

Digital Library

[20]

Rachid Seghir and Vincent Loechner. Memory optimization by counting points in integer transformations of parametric polytopes. In CASES'06: International Conference on Compilers, Architectures, and Synthesis for Embedded Systems, pages 74--82, 2006.

Digital Library

[21]

H. J. S. Smith. On systems of linear indeterminate equations and congruences. Phil. Trans. Roy. Soc. London, 151:293--326, 1861.

[22]

J. Teich and L. Thiele. Partitioning of processor arrays: A piecewise regular approach. INTEGRATION: The VLSI Journal, 14(3):297--332, Feb 1993.

Digital Library

[23]

Jingling Xue. Automating non-unimodular loop transformations for massive parallelism. Parallel Computing, 20(5):711--728, 1994.

Digital Library

Cited By

Javanmard MAhmad ZKong MPouchet LChowdhury RHarrison RMars JTang LXue JWu P(2020)Deriving parametric multi-way recursive divide-and-conquer dynamic programming algorithms using polyhedral compilersProceedings of the 18th ACM/IEEE International Symposium on Code Generation and Optimization10.1145/3368826.3377916(317-329)Online publication date: 22-Feb-2020
https://dl.acm.org/doi/10.1145/3368826.3377916
Maiza CRihani HRivas JGoossens JAltmeyer SDavis R(2019)A Survey of Timing Verification Techniques for Multi-Core Real-Time SystemsACM Computing Surveys10.1145/332321252:3(1-38)Online publication date: 18-Jun-2019
https://dl.acm.org/doi/10.1145/3323212
Augustine TSarma JPouchet LRodríguez GMcKinley KFisher K(2019)Generating piecewise-regular code from irregular structuresProceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/3314221.3314615(625-639)Online publication date: 8-Jun-2019
https://dl.acm.org/doi/10.1145/3314221.3314615
Show More Cited By

Index Terms

The Z-polyhedral model
1. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language types
        Functional languages
2. Theory of computation
  1. Semantics and reasoning
    1. Program reasoning
      1. Program specifications

Recommendations

Distributing and Parallelizing Non-canonical Loops
Verification, Model Checking, and Abstract Interpretation
Abstract
This work leverages an original dependency analysis to parallelize loops regardless of their form in imperative programs. Our algorithm distributes a loop into multiple parallelizable loops, resulting in gains in execution time comparable to state-...
Simplifying reductions
POPL '06: Conference record of the 33rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages

We present optimization techniques for high level equational programs that are generalizations of affine control loops (ACLs). Significant parts of the SpecFP and PerfectClub benchmarks are ACLs. They often contain reductions: associative and ...
Complexity of Multi-dimensional Loop Alignment
STACS '02: Proceedings of the 19th Annual Symposium on Theoretical Aspects of Computer Science

Loop alignment is a classical program transformation that can enable the fusion of parallel loops, thereby increasing locality and reducing the number of synchronizations. Although the problem is quite old in the one-dimensional case (i.e., no nested ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PPoPP '07: Proceedings of the 12th ACM SIGPLAN symposium on Principles and practice of parallel programming

March 2007

284 pages

ISBN:9781595936028

DOI:10.1145/1229428

General Chair:
Katherine Yelick
UC Berkeley and Lawrence Berkeley National Lab., USA
,
Program Chair:
John Mellor-Crummey
Rice University, USA

Copyright © 2007 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 March 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

PPoPP07

Sponsor:

PPoPP07: ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming

March 14 - 17, 2007

California, San Jose, USA

Acceptance Rates

PPoPP '07 Paper Acceptance Rate 22 of 65 submissions, 34%;

Overall Acceptance Rate 230 of 1,014 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

20
Total Citations
View Citations
612
Total Downloads

Downloads (Last 12 months)25
Downloads (Last 6 weeks)5

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Javanmard MAhmad ZKong MPouchet LChowdhury RHarrison RMars JTang LXue JWu P(2020)Deriving parametric multi-way recursive divide-and-conquer dynamic programming algorithms using polyhedral compilersProceedings of the 18th ACM/IEEE International Symposium on Code Generation and Optimization10.1145/3368826.3377916(317-329)Online publication date: 22-Feb-2020
https://dl.acm.org/doi/10.1145/3368826.3377916
Maiza CRihani HRivas JGoossens JAltmeyer SDavis R(2019)A Survey of Timing Verification Techniques for Multi-Core Real-Time SystemsACM Computing Surveys10.1145/332321252:3(1-38)Online publication date: 18-Jun-2019
https://dl.acm.org/doi/10.1145/3323212
Augustine TSarma JPouchet LRodríguez GMcKinley KFisher K(2019)Generating piecewise-regular code from irregular structuresProceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/3314221.3314615(625-639)Online publication date: 8-Jun-2019
https://dl.acm.org/doi/10.1145/3314221.3314615
Rodriguez GKandemir MTourino J(2019)Affine Modeling of Program TracesIEEE Transactions on Computers10.1109/TC.2018.285374768:2(294-300)Online publication date: 1-Feb-2019
https://dl.acm.org/doi/10.1109/TC.2018.2853747
Rodríguez GAndión JKandemir MTouriño JFranke BWu YRastello F(2016)Trace-based affine reconstruction of codesProceedings of the 2016 International Symposium on Code Generation and Optimization10.1145/2854038.2854056(139-149)Online publication date: 29-Feb-2016
https://dl.acm.org/doi/10.1145/2854038.2854056
Ravishankar MDathathri RElango VPouchet LRamanujam JRountev ASadayappan P(2015)Distributed memory code generation for mixed Irregular/Regular computationsACM SIGPLAN Notices10.1145/2858788.268851550:8(65-75)Online publication date: 24-Jan-2015
https://dl.acm.org/doi/10.1145/2858788.2688515
Elango VRastello FPouchet LRamanujam JSadayappan P(2015)On Characterizing the Data Access Complexity of ProgramsACM SIGPLAN Notices10.1145/2775051.267701050:1(567-580)Online publication date: 14-Jan-2015
https://dl.acm.org/doi/10.1145/2775051.2677010
Ravishankar MDathathri RElango VPouchet LRamanujam JRountev ASadayappan PCohen AGrove D(2015)Distributed memory code generation for mixed Irregular/Regular computationsProceedings of the 20th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/2688500.2688515(65-75)Online publication date: 24-Jan-2015
https://dl.acm.org/doi/10.1145/2688500.2688515
Elango VRastello FPouchet LRamanujam JSadayappan PRajamani SWalker D(2015)On Characterizing the Data Access Complexity of ProgramsProceedings of the 42nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages10.1145/2676726.2677010(567-580)Online publication date: 14-Jan-2015
https://dl.acm.org/doi/10.1145/2676726.2677010
Cilardo AGallo L(2015)Improving Multibank Memory Access Parallelism with Lattice-Based PartitioningACM Transactions on Architecture and Code Optimization10.1145/267535911:4(1-25)Online publication date: 9-Jan-2015
https://dl.acm.org/doi/10.1145/2675359
Show More Cited By

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