Thread partition plays an important role in speculative multithreading （SpMT） for automatic parallelization of ir- regular programs. Using unified values of partition parameters to partition different applications l...Thread partition plays an important role in speculative multithreading （SpMT） for automatic parallelization of ir- regular programs. Using unified values of partition parameters to partition different applications leads to the fact that every ap- plication cannot own its optimal partition scheme. In this paper, five parameters affecting thread partition are extracted from heuristic rules. They are the dependence threshold （DT）, lower limit of thread size （TSL）, upper limit of thread size （TSU）, lower limit of spawning distance （SDL）, and upper limit of spawning distance （SDU）. Their ranges are determined in accordance with heuristic rules, and their step-sizes are set empirically. Under the condition of setting speedup as an objective function, all com- binations of five threshold values form the solution space, and our aim is to search for the best combination to obtain the best thread granularity, thread dependence, and spawning distance, so that every application has its best partition scheme. The issue can be attributed to a single objective optimization problem. We use the artificial immune algorithm （AIA） to search for the optimal solution. On Prophet, which is a generic SpMT processor to evaluate the performance of multithreaded programs, Olden bench- marks are used to implement the process. Experiments show that we can obtain the optimal parameter values for every benchmark, and Olden benchmarks partitioned with the optimized parameter values deliver a performance improvement of 3.00% on a 4-core platform compared with a machine learning based approach, and 8.92% compared with a heuristics-based approach.展开更多
基金supported by the National Natural Science Foundation of China(No.61173040)the Doctoral Fund of Ministry of Education of China(No.2013021110012)
文摘Thread partition plays an important role in speculative multithreading （SpMT） for automatic parallelization of ir- regular programs. Using unified values of partition parameters to partition different applications leads to the fact that every ap- plication cannot own its optimal partition scheme. In this paper, five parameters affecting thread partition are extracted from heuristic rules. They are the dependence threshold （DT）, lower limit of thread size （TSL）, upper limit of thread size （TSU）, lower limit of spawning distance （SDL）, and upper limit of spawning distance （SDU）. Their ranges are determined in accordance with heuristic rules, and their step-sizes are set empirically. Under the condition of setting speedup as an objective function, all com- binations of five threshold values form the solution space, and our aim is to search for the best combination to obtain the best thread granularity, thread dependence, and spawning distance, so that every application has its best partition scheme. The issue can be attributed to a single objective optimization problem. We use the artificial immune algorithm （AIA） to search for the optimal solution. On Prophet, which is a generic SpMT processor to evaluate the performance of multithreaded programs, Olden bench- marks are used to implement the process. Experiments show that we can obtain the optimal parameter values for every benchmark, and Olden benchmarks partitioned with the optimized parameter values deliver a performance improvement of 3.00% on a 4-core platform compared with a machine learning based approach, and 8.92% compared with a heuristics-based approach.
