A Case for Strongly Polynomial Time Sub-Polyhedral Scheduling Using Two-Variable-Per-Inequality Polyhedra

Ramakrishna Upadrasta 1 Albert Cohen 1
1 Parkas - Parallélisme de Kahn Synchrone
CNRS - Centre National de la Recherche Scientifique : UMR 8548, Inria Paris-Rocquencourt, DI-ENS - Département d'informatique de l'École normale supérieure
Abstract : We make a case for sub-polyhedral scheduling using (Unit-)Two-Variable-Per-Inequality or (U)TVPI Polyhedra. We empirically show that using general convex polyhedra leads to a scalability problem in a widely used polyhedral scheduler. We propose methods in which polyhedral schedulers can beat the scalability challenge by using sub-polyhedral under-aproximations of the polyhedra resulting from the application of the affine form of the Farkas lemma. We propose simple algorithms that under-approximate a general polyhedra into (U)TVPI polyhedra. These algorithms take worstcase polynomial time. We implement the above approximation algorithms in a modified PLuTo, and show that for a majority of the Polybench 2.0 kernels, the above under-approximation yield polyhedra that are non-empty. We also provide preliminary evidence that code generated by our sub-polyhedral parallelization prototype matches the performance of PLuTo-optimized code when the under-approximation preserves feasibility.
Keywords : Approximation Algorithms Complexity Theory Compilers Optimization Geometric Algorithms
Type de document :
Communication dans un congrès
IMPACT 2012 - 2nd Workshop on Polyhedral Compilation Techniques (associated with HiPEAC), Jan 2012, Paris, France. 2012
Liste complète des métadonnées
https://hal.inria.fr/hal-00786832
Contributeur : Albert Cohen <>
Soumis le : dimanche 10 février 2013 - 20:21:28
Dernière modification le : vendredi 25 mai 2018 - 12:02:06

Identifiants

  • HAL Id : hal-00786832, version 1

Collections

ENS-PARIS | INRIA | PSL | INRIA-ROCQ

Citation

Ramakrishna Upadrasta, Albert Cohen. A Case for Strongly Polynomial Time Sub-Polyhedral Scheduling Using Two-Variable-Per-Inequality Polyhedra. IMPACT 2012 - 2nd Workshop on Polyhedral Compilation Techniques (associated with HiPEAC), Jan 2012, Paris, France. 2012. 〈hal-00786832〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

232

Contact


archive-ouverte@inria.fr