Optimization of thread partitioning parameters in speculative multithreading based on artificial immune algorithm

Abstract

Thread partition plays an important role in speculative multithreading (SpMT) for automatic parallelization of irregular programs. Using unified values of partition parameters to partition different applications leads to the fact that every application 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 combinations 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 benchmarks 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.

Keywords

Speculative multithreading / Thread partitioning / Artificial immune algorithm

References

[1] Akkary, H., Driscoll, M.A., 1998. A dynamic multithreading processor. Proc. 31st Annual ACM/IEEE Int. Symp. On Microarchitecture, p.226-236.

[2] Bhowmik, A., Franklin, M., 2002. A general compiler framework for speculative multithreading. Proc. 14th Annual ACM Symp. on Parallel Algorithms and Architectures, p.99-108. [

[3] Chen, Z., Zhao, Y., Pan, X., , 2009. An overview of Prophet. Proc. 9th Int. Conf. on Algorithms and Architectures for Parallel Processing, p.396-407. [

[4] Dasgupta, D., 1999. Artificial Immune Systems and Their Applications. Springer Berlin Heidelberg. [

[5] de Castro, L.N., Timmis, J., 2002. Artificial Immune Systems: a New Computational Intelligence Approach. Springer.

[6] Dong, Z., Zhao, Y., Wei, Y., , 2009. Prophet: a speculative multi-threading execution model with architectural support based on CMP. Proc. 8th Int. Conf. on Embedded Computing, and Int. Conf. on Scalable Computing and Communications, p.103-108. [

[7] Heinrich, J., 1994. MIPS R4000 Microprocessor User’s Manual (2nd Ed.). MIPS Technologies, Inc., Mountain View, CA.

[8] Krishnan, V., Torrellas, J., 1999. A chip-multiprocessor architecture with speculative multithreading. IEEE Trans. Comput., 48(9): 866-880. [

[9] Liu, B., Zhao, Y., Li, Y., , 2014. A thread partitioning approach for speculative multithreading. J. Supercomput., 67(3): 778-805. [

[10] Madriles, C., Lopez, P., Codina, J.M., , 2009. Anaphase: a fine-grain thread decomposition scheme for speculative multithreading. Proc. 18th Int. Conf. on Parallel Architectures and Compilation Techniques, p.15-25. [

[11] Marcuello, P., González, A., 1999. Clustered speculative multithreaded processors. Proc. 13th Int. Conf. on Supercomputing, p.365-372. [

[12] Olukotun, K., Hammond, L., Willey, M., 1999. Improving the performance of speculatively parallel applications on the Hydra CMP. Proc. 13th Int. Conf. on Supercomputing, p.21-30. [

[13] Quiñones, C.G., Madriles, C., Sánchez, J., , 2005. Mitosis compiler: an infrastructure for speculative threading based on pre-computation slices. Proc. ACM SIGPLAN Conf. on Programming Language Design and Implementation, p.269-279. [

[14] Sohi, G.S., Breach, S.E., Vijaykumar, T.N., 1995. Multiscalar processors. Proc. 22nd Annual Int. Symp. on Computer Architecture, p.414-425. [

[15] Timmis, J., 2000. Artificial Immune Systems: a Novel Data Analysis Technique Inspired by the Immune Network Theory. Available from https://kar.kent.ac.uk/21989/.

[16] Tsai, J., Yew, P., 1996. The superthreaded architecture: thread pipelining with run-time data dependence checking and control speculation. Proc. Conf. on Parallel Architectures and Compilation Techniques, p.35-46. [

[17] Tsai, J., Huang, J., Amlo, C., , 1999. The superthreaded processor architecture. IEEE Trans. Comput., 48(9): 881-902. [

[18] Wang, L., Pan, J., Jiao, L., 2000. The immune algorithm. Acta Electron. Sin., 28(7): 74-78 (in Chinese).

[19] Wilson, R.P., French, R., Wilson, C.S., , 1994. The SUIF Compiler System: a Parallelizing and Optimizing Research Compiler. Technical Report No. CSL-TR-94-620, Computer Systems Laboratory, Stanford University, CA.