OpenMP Static Scheduling Method For Load Balancing Under Multithreading

In recent years,with the development of scientific research and engineering technology,the increasing demand for computing power in various fields has prompted the rapid development of multi-core computing systems,and the number of cores in mainstream computing platforms at home and abroad has been climbing.According to the two-eight rule in scientific computing,20% of the code in a program often occupies80% of the execution time,and these blocks of code with larger time share are usually the loop structures in the program.Therefore,using multi-core parallel computing resources to improve the performance of core loops in programs is an important research direction.OpenMP is a shared-store multithreaded parallel programming model based on compilation instructions,which is supported by mainstream compilers such as GCC,ICC,and LLVM due to its simplicity and efficiency,and is currently the main means of thread-level parallel programming.open MP provides three different scheduling strategies for loop parallelization,but for some specific loop patterns,such as linearly increasing or decreasing load However,for some specific loop patterns,such as linearly increasing or decreasing load loops,random load loops,etc.,the existing scheduling policies can hardly meet the requirements of better load balancing and smaller scheduling overhead at the same time.In order to solve the above problems,this paper proposes a more targeted scheduling strategy for different cyclic patterns,and the main work and research results are as follows.1.For the problem of load imbalance in linear load cyclic scheduling,a nonlinear static scheduling strategy(Nonlinear?Static)is proposed.Combined with OpenMP scheduling,the key parameters existing in the cyclic scheduling process are extracted,and a scheduling model that maximizes the use of linear cyclic features is designed,and the scheduling model is coded and implemented in the OMPi compiler.Finally,the scheduling strategy continues the advantage of static scheduling without scheduling overhead and achieves a balanced load distribution based on it.In this paper,the proposed scheduling strategy is tested using test cases with different loop patterns.The results show that the Nonlinear?Static scheduling strategy achieves a 5%-10% speedup compared to the existing scheduling strategy of OpenMP for a wide range of thread counts when dealing with linear loop structures.2.To address the problem of high scheduling overhead when dynamic scheduling strategy is used for random load loops,an iterative compilation-based scheduling strategy(Dual?static)is proposed.Unlike other scheduling policies,this scheduling strategy requires a pre-run before the loop scheduling in order to obtain the load information of the loop iterations.The load information of the loop iteration obtained by the pre-run is used to achieve load balancing by redistributing the tasks applicable to the random loop.At the same time,the extra time overhead caused by the pre-run is mitigated by code isolation and parallel execution of the pre-run code.In this paper,we use a test case containing a random load loop for testing,and the results show that the Dual?static scheduling strategy achieves an average speedup of about 8% compared to other scheduling policies for a wide range of thread counts when dealing with random loop structures.