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

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 meth-ods in which polyhedral schedulers can beat the scalability chal-lenge by using sub-polyhedral under-aproximations of the polyhe-dra 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 approxima-tion algorithms in a modified PLuTo, and show that for a major-ity 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 paralleliza-tion prototype matches the performance of PLuTo-optimized code when the under-approximation preserves feasibility