Thread-level Speculative Scheduling Method Based On KNN Model For Irregular Algorithms

Irregular algorithms have been widely used in complex network analysis,machine learning,image processing,biological information,molecular dynamics and climate simulation.How to effectively improve the execution efficiency of irregular algorithms through thread-level speculation technology has become a current research hotspot.However,the existing thread-level speculative scheduling strategy does not take into account the characteristics of irregular algorithms,and the "one size fits all" strategy is used for thread scheduling during speculative parallelism,resulting in poor execution results.In order to obtain better speculative execution performance,this paper has carried out research from two aspects: the sample set of irregular algorithms and the introduction of machine learning to the field of thread-level speculative scheduling.The main work of the paper is summarized as follows:(1)A method for constructing a sample set oriented to Thread Level Speculative(TLS)is proposed.Aiming at the problem that the existing irregular algorithm does not correspond to its optimal thread-level speculative scheduling strategy.First,through the study of thread level speculative technology,based on the extension of the Open MP programming model that supports TLS technology,the irregular algorithm is converted into a speculative parallel version,and then the feature information of the irregular algorithm is analyzed by the feature extraction technology.Extract,and then express the characteristics of the irregular algorithm,and establish the feature set of the irregular algorithm;Then,different TLS scheduling strategies were used to execute the irregular algorithm repeatedly,and the optimal TLS scheduling policy was selected as the label for the irregular algorithm;Finally,the irregular algorithm feature set and its corresponding label are combined to construct an irregular algorithm sample set based on TLS,which provides a data set for subsequent model training.(2)A thread-level speculative scheduling method based on KNN is proposed.In view of the situation that the thread-level speculative scheduling method does not consider the feature information of the irregular algorithm,this paper introduces machine learning into the threadlevel speculative scheduling field.First,the irregular algorithm sample set is used as the training sample,then the sample is preprocessed,and finally based on The KNN method constructs a predictive model for an irregular algorithm and determines the K value through experiments.When a new irregular algorithm needs to be executed,the prediction model is used to predict the optimal TLS scheduling strategy suitable for its own characteristics for the new irregular algorithm.(3)Performance research and analysis of scheduling method based on KNN.For the KNN scheduling method,design multiple sets of experiments to test and analyze the results,evaluate the accuracy of the KNN prediction model,verify the effectiveness of the proposed sample construction method;Quantitative data is used to verify the correctness and performance benefits of the proposed KNN-based thread-level speculative scheduling method during speculation execution.The experimental results show that the thread-level speculative scheduling method based on KNN for the irregular algorithm proposed in this paper improves the speculative execution efficiency of the irregular algorithm under different threads.The accuracy rate of the KNN model reached 78.95%.The worst performance of the speculated growth rate is that the speculative execution efficiency of the irregular algorithm is increased to 17.3% under 8threads,and the growth rate can reach the highest 55.9% under 4 threads.Experiments results show that the method proposed in this article can overcome the "one size fits all" phenomenon of the existing TLS scheduling strategy.Through the KNN prediction model,the optimal TLS scheduling strategy can be predicted for it based on the characteristics of the irregular algorithm itself,which effectively improves the irregular algorithm when speculating in parallel execution speed of execution,shorten execution time.