Research On Multi-core/Many-core Platform Oriented Speculative Parallelizing Technology

With the development of computer architecture technologies and the production industrial of chips, Traditional parallel programming models are challenged by growing number of many-core and heterogenous core processors. The diversity of application also increases the difficulty of parallel programming. Normal programmers eagerly need a programming model with high efficiency, usability and universality. To exploit threadlevel parallelism efficiently and simply becomes the hot spot of parallel computing.Aiming at the high global overhead of conventional software speculative parallel model, the dissertation proposed a novel software speculative parallel model: HEUSPEC.The paper also proposed four optimizing technologies to reduce the overhead in the speculative execution, and improve the performance. They are: the Heuristic Value Prediction,the Inter-thread Fetching, the Dynamic Task Granularity Resizing and the Out-of-Order Committing. Specifically, the main contributions of the dissertation are as follows:The dissertation proposed a the software speculative parallel model HEUSPEC. The high execution overhead is the fatal defect of conventional software speculative parallel models. To reduce the overhead, the dissertation proposed and implemented the HEUSPEC, a software based speculative parallel model. The paper also proposed an analytical model of the overhead for software based speculative parallel models, according to the work flow of HEUSPEC. The experiment data shows that the HEUSPEC has better performance, lower time/space overheads and good scalability.The dissertation proposed the Heuristic Value Prediction(HVP) technology to improve the speculation accuracy of regular conflict variables. The Value Prediction mechanisms adopted in the existing software speculative parallel models hardly meet the demand of simplicity and effectiveness. To overcome this defect, the dissertation proposed Heuristic Value Prediction technology. It uses multiple predictors to predict the values of conflict variables based on their recorded history values. A credit system is applied to select the most reliable prediction result among multiple results. The HVP makes compromise between the Multiple Random Value Prediction and Pre-computing Value Prediction.The predictors are more intelligent than random predictors, and cost less hardware threads. The experiment shows that the HVP can reduce the mis-speculation rate, and improve the performance.The dissertation proposed the Inter-thread Fetching(IF) technology to improve the speculation accuracy of all conflict variables. Irregular conflict variables gains lower speculation accuracy under history based prediction scheme. To solve the problem, the dissertation proposed Inter-thread Fetching technology. The IF allows speculative threads exchange the un-submitted data without breaking the thread isolation of the software based speculative parallel model. For all types of conflict variables, the IF has the similar optimization effect. It expands the ”safe speculation time zone” and increases the probability of getting a right value of an Speculative Read(SRD) operation. The experiment shows that the IF can reduce the mis-speculation rate and improve the overall performance remarkably with low space overhead.The dissertation proposed the Dynamic Task Granularity Resizing(DTGR) technology to optimize global overhead. The conventional models with static task granularity hardly adapt the guest program with a constantly changing miss speculation rate. The global overhead is always very high for this type of program. To solve the problem, the dissertation proposed the Dynamic Task Granularity Resizing technology. It is based on the idea of dynamic optimization. It profiling the miss speculation rate, the average control overhead and rollback overhead in a period of execution, and calculate the new task granularity which leads to the optimized global overhead based on the analytical model of the global overhead. The experiment shows that DTGR can improve the performance remarkably while parallelize the programs with uncertain dependencies.The dissertation proposed the Out-of-order Committing(OOC) technology to reduce the control overhead. High control overhead limits the performance of software based speculative parallel models. To solve this problem, the dissertation proposed the Out-oforder Committing technology. It can reduce the unnecessary waiting time of the speculative threads while parallelizing a loop without dependency, accelerate the speculative task assignment, and reduce the global overhead, without damage the correctness of the speculative parallel execution. The experiment shows that the mechanism can improve the execution performance of the software based speculative parallel model when executing a program without cross-iter dependencies.