Loop-Block-Level Automatic Parallelization in Compilers
Source abstract
Abstract
To address the issues of coarse-grained thread allocation and difficult load balancing in compiler automatic parallelization for processors, this paper proposes a loop-block-level automatic parallelization method for compilers based on an iterative compilation mode, using the SWGCC compiler on the Sunway platform. An automatic parallelization method that independently sets the number of threads for each loop block is designed within the SWGCC, which allocates threads to each parallelizable loop block in the program at a finer granularity. Meanwhile, iterative compilation is combined with a genetic algorithm to iteratively optimize the optimal thread group. Through operations such as the chromosome encoding of thread allocation schemes, weighted mutation operations based on loop execution proportions, and fitness function-guided population evolution, the optimal thread combination is efficiently searched for the loop block thread allocation algorithm. Experiments are validated on the Sunway processor using the SPEC2006 test suite. The results reveal that the loop-block-level compiler automatic parallelization algorithm combined with the evolutionary algorithm achieves a maximum performance score improvement of 19% and an average performance score improvement of 4% compared to the baseline automatic parallelization algorithm in the tests.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Parallel Computing and Optimization Techniques · Big Data and Digital Economy · Cloud Computing and Resource Management
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
Country School of Computer Science and Artificial Intelligence, Zhengzhou University, Zhengzhou 450001, China
References (26)
Show source-provided references
1. Furthering Moore’s Law Integration Benefits in the Chiplet Era10.1109/MDAT.2023.3302809 ↗
2. Approximate High-Performance Computing: A Fast and Energy-Efficient Computing Paradigm in the Post-Moore Era10.1109/MITP.2023.3254642 ↗
3. Rescue to the Curse of Universality10.1007/s11432-021-3596-x ↗
4. Kadosh, T., Hasabnis, N., Mattson, T., Pinter, Y., and Oren, G. (2023, January 25–29). Quantifying OpenMP: Statistical Insights into Usage and Adoption. Proceedings of the 2023 IEEE High Performance Extreme Computing Conference (HPEC 2023), Boston, MA, USA.10.1109/HPEC58863.2023.10363459 ↗
5. Myths and Legends in High-Performance Computing10.1177/10943420231166608 ↗
6. TOP500 Team (2024, January 14). Frontier Remains No.1 in the TOP500 but Aurora with Intel’s Sapphire Rapids Chips Enters with a Half-Scale System at No. 2. 2023-11-13. Available online: https://www.top500.org/news/frontier-remains-no-1-in-the-top500-but-aurora-with-intels-sapphire-rapids-chips-enters-with-a-half-scale-system-at-no-2/.
7. Systolic Arrays (for VLSI)
8. A New Golden Age for Computer Architecture10.1145/3282307 ↗
9. Can Programming Be Liberated from the von Neumann Style? Functional Programming and Its Algebra of Programs
10. Kurra, S., Singh, N.K., and Panda, P.R. (2007). The Impact of Loop Unrolling on Controller Delay in High Level Synthesis. Proceedings of the Design, Automation & Test in Europe Conference & Exhibition, IEEE Computer Society.10.1109/DATE.2007.364623 ↗
11. Cooper, K.D., Harvey, T.J., and Waterman, T. (2008). An Adaptive Strategy for Inline Substitution. Proceedings of the International Conference on Compiler Construction, Springer.10.1007/978-3-540-78791-4_5 ↗
12. Compiler Optimization Sequence Selection Method Guided by Learning Model
13. An Autotuning Framework for Scalable Execution of Tiled Code via Iterative Polyhedral Compilation
14. A Graph-Based Iterative Compiler Pass Selection and Phase Ordering Approach10.1145/2980930.2907959 ↗
15. Parameter Selection Method for Function Level Compiler Optimization Guided by Supervised Learning Model
16. Fursin, G., Miranda, C., and Temam, O. (2008, January 17–19). MILEPOST GCC: Machine Learning Based Research Compiler. Proceedings of the GCC Developers’ Summit, Ottawa, ON, Canada.
17. Park, E., Cavazos, J., and Alvarez, M.A. (2012). Using Graph-Based Program Characterization for Predictive Modeling. Proceedings of the Tenth International Symposium on Code Generation and Optimization, Association for Computing Machinery.10.1145/2259016.2259042 ↗
18. Li, Y.P. (2022). Load-Balanced OpenMP Static Scheduling Method Under Multi-Threading. [Master’s Thesis, Zhengzhou University].
19. Trapezoid Self-Scheduling: A Practical Scheduling Scheme for Parallel Compilers10.1109/71.205655 ↗
20. Research on Loop Automatic Parallelization Technology
21. Speedup and Efficiency of Computational Parallelization: A Unifying Approach and Asymptotic Analysis10.1016/j.jpdc.2023.104835 ↗
22. Zhao, D.S. (2021). Research on the Thread-Level Speculation Execution Model for LLVM Compiler. [Ph.D. Thesis, Northwest A&F University].10.1145/3468691.3468707 ↗
23. Xu, M. (2012). Research on Key Technologies of Reconfigurable Manycore Stream Processor Architecture. [Master’s Thesis, University of Science and Technology of China].
24. A Loop Selection Approach Based on Performance Prediction for Speculative Multithreading
25. Nie, K. (2021). Research on Multi-threaded Compilation Optimization Techniques for Master-Slave Hybrid Architecture of CPU. [Ph.D. Thesis, Information Engineering University of the Strategic Support Force].
26. Research on Parallel Scheduling Strategy Optimization Technology Based on Sunway Compiler