Sub-polyhedral scheduling using (unit-)two-variable-per-inequality polyhedra

Ramakrishna Upadrasta 1, 2 Albert Cohen 1
1 Parkas - Parallélisme de Kahn Synchrone
DI-ENS - Département d'informatique de l'École normale supérieure, ENS Paris - École normale supérieure - Paris, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR 8548
Abstract : Polyhedral compilation has been successful in the design and implementation of complex loop nest optimizers and parallelizing compilers. The algorithmic complexity and scalability limitations remain one important weakness. We address it using sub-polyhedral under-aproximations of the systems of constraints resulting from affine scheduling problems. We propose a sub-polyhedral scheduling technique using (Unit-)Two-Variable-Per-Inequality or (U)TVPI Polyhedra. This technique relies on simple polynomial time algorithms to under-approximate a general polyhedron into (U)TVPI polyhedra. We modify the state-of-the-art PLuTo compiler using our scheduling technique, and show that for a majority of the Polybench (2.0) kernels, the above under-approximations yield polyhedra that are non-empty. Solving the under-approximated system leads to asymptotic gains in complexity, and shows practically significant improvements when compared to a traditional LP solver. We also verify that code generated by our sub-polyhedral parallelization prototype matches the performance of PLuTo-optimized code when the under-approximation preserves feasibility.
Type de document :
Communication dans un congrès
POPL'13 - 40th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, Jan 2013, Rome, Italy. ACM, pp.483-496, 2013, <10.1145/2429069.2429127>
Liste complète des métadonnées


https://hal.inria.fr/hal-00911888
Contributeur : Albert Cohen <>
Soumis le : dimanche 1 décembre 2013 - 01:15:46
Dernière modification le : mercredi 4 janvier 2017 - 16:19:56
Document(s) archivé(s) le : lundi 3 mars 2014 - 20:45:54

Fichier

popl070-upadrasta.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Ramakrishna Upadrasta, Albert Cohen. Sub-polyhedral scheduling using (unit-)two-variable-per-inequality polyhedra. POPL'13 - 40th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, Jan 2013, Rome, Italy. ACM, pp.483-496, 2013, <10.1145/2429069.2429127>. <hal-00911888>

Partager

Métriques

Consultations de
la notice

211

Téléchargements du document

505