STM Journals Peer-reviewed research from Consortium e-Learning Network

Recent Trends in Parallel Computing Review Article

Polyhedral Compilation for Imperative Loops: Foundations, Advances, and Emerging Frontiers

  1. Manas Kumar Yogi Department of CSE, Pragati Engineering College (A

Abstract

Polyhedral compilation is a mathematically rigorous framework that models imperative loop nests as sets of integer points constrained by affine inequalities, enabling precise reasoning about data dependences and the legality of complex program transformations. Over the past decade, this framework has evolved from an academic formalism into a practical compiler technology deployed in production compilers, high-performance computing libraries, and machine learning acceleration toolchains. This review surveys the theoretical underpinnings of the polyhedral model, with particular emphasis on the representation of static control parts, affine scheduling, and dependence-driven transformation legality. We examine how modern polyhedral tools—including Pluto, PPCG, Tiramisu, and the Integer Set Library—address the twin objectives of exploiting parallelism and maximizing memory locality in loop-intensive computations. We further analyze extensions of the classical framework to parametric loop bounds, non-affine array accesses, sparse computations, and deep-learning tensor workloads, discussing the algorithmic innovations that bridge the gap between theoretical tractability and practical applicability. Benchmark evidence from PolyBench, MLPerf, and NAS parallel suites demonstrates consistent speedups ranging from 3.6× to 14.2× relative to baseline sequential code. Open challenges, including automated SCoP detection, compiler scalability, and integration with machine learning-guided search, are discussed to delineate productive research directions.

Keywords

References (19)

  1. Lee MK, Cui Y, Somu T, Luo T, Zhou J, Tang WT, et al. A system-level simulator for RRAM-based neuromorphic computing chips. ACM Trans Archit Code Optim. 2018;15(4):1–24.
  2. Liu J, Wickerson J, Bayliss S, Constantinides GA. Polyhedral-based dynamic loop pipelining for high-level synthesis. IEEE Trans Comput Aided Des Integr Circuits Syst. 2018;37(9):1802–1815.
  3. VenkataKeerthy S, Aggarwal R, Jain S, Desarkar MS, Upadrasta R, Srikant YN. Ir2vec: LLVM IR based scalable program embeddings. ACM Trans Archit Code Optim. 2020;17(4):1–27.
  4. Parsa S, Hamzei M. Nested-loops tiling for parallelization and locality optimization. Comput Inform. 2017;36(3):566.
  5. Zhao Y, Sharif H, Adve V, Misailovic S. Felix: optimizing tensor programs with gradient descent. In: Proceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems. 2024 Apr 27. p. 367–381.
  6. Alavi HS, Lalanne D, Rogers Y. The five strands of living lab: a literature study of the evolution of living lab concepts in HCI. ACM Trans Comput Hum Interact. 2020;27(2):1–26.
  7. Xiao J, Chen S, He Q, Feng Z, Xue X. An Android application risk evaluation framework based on minimum permission set identification. J Syst Softw. 2020;163:110533.
  8. Grosser T, Zheng H, Aloor R, Simbürger A, Größlinger A, Pouchet LN. Polly—polyhedral optimization in LLVM. In: Proceedings of the First International Workshop on Polyhedral Compilation Techniques (IMPACT). 2011 Apr 2;2011:1.
  9. Henretty T, Stock K, Pouchet LN, Franchetti F, Ramanujam J, Sadayappan P. Data layout transformation for stencil computations on short-vector SIMD architectures. In: International Conference on Compiler Construction. Berlin: Springer; 2011. p. 225–245.
  10. Kritikakou A, Catthoor F, Kelefouras V, Goutis C. A systematic approach to classify design-time global scheduling techniques. ACM Comput Surv. 2013;45(2):1–30.
  11. Li C, Song M, Zhang M, Luo Y. Effective replica management for improving reliability and availability in edge-cloud computing environment. J Parallel Distrib Comput. 2020;143:107–128.
  12. Park H, Kim S, Park JG, Moon SM. Reusing the optimized code for JavaScript ahead-of-time compilation. ACM Trans Archit Code Optim. 2018;15(4):1–20.
  13. Pouchet LN, Zhang P, Sadayappan P, Cong J. Polyhedral-based data reuse optimization for configurable computing. In: Proceedings of the ACM/SIGDA International Symposium on Field Programmable Gate Arrays. 2013 Feb 11. p. 29–38.
  14. Dathathri R, Reddy C, Ramashekar T, Bondhugula U. Generating efficient data movement code for heterogeneous architectures with distributed-memory. In: Proceedings of the 22nd International Conference on Parallel Architectures and Compilation Techniques. 2013 Sep 7. p. 375–386.
  15. Huang B, Zhang R, Lu Z, Zhang Y, Wu J, Zhan L, et al. BPS: a reliable and efficient pub/sub communication model with blockchain-enhanced paradigm in multi-tenant edge cloud. J Parallel Distrib Comput. 2020;143:167–178.
  16. Upadrasta R, Cohen A. Sub-polyhedral scheduling using (unit-) two-variable-per-inequality polyhedra. ACM SIGPLAN Not. 2013;48(1):483–496.
  17. Vasilache N, Zinenko O, Theodoridis T, Goyal P, DeVito Z, Moses WS, et al. Tensor comprehensions: framework-agnostic high-performance machine learning abstractions [Preprint]. 2018. arXiv:1802.04730.
  18. Garfinkel S, Stewart J. Sharpening your tools: updating bulk_extractor for the 2020s. Queue. 2023;21(1):30–56.
  19. Zinenko O, Verdoolaege S, Reddy C, Shirako J, Grosser T, Sarkar V, et al. Modeling the conflicting demands of parallelism and temporal/spatial locality in affine scheduling. In: Proceedings of the 27th International Conference on Compiler Construction. 2018 Feb 24. p. 3–13.
Support