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

Li Yu-xiang; Zhao Yin-liang; Liu Bin; Ji Shuo

doi:10.1631/FITEE.1400172

Your Location：

Home >

Browse articles >

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

Computer & Automation | Updated：2022-06-06

- Optimization of thread partitioning parameters in speculative multithreading based on artificial immune algorithm*
- 基于人工免疫算法的推测多线程线程划分参数的优化
- Frontiers of Information Technology & Electronic Engineering Vol. 16, Issue 3, Pages: 205-216(2015)
- Affiliations：
  
  Department of Computer Science and Technology, Xi’an Jiaotong University, Xi’an 710049, China
- Author bio：
  
  ‡Corresponding Author
- Funds：
- DOI：10.1631/FITEE.1400172
  CLC：
- Received：13 May 2014，
  
  Revised：2015-01-28，
  
  Accepted：10 September 2014，
  
  Published：2015-03
- Accepted：
Scan QR Code
Li Yu-xiang, Zhao Yin-liang, Liu Bin, et al. Optimization of thread partitioning parameters in speculative multithreading based on artificial immune algorithm*[J]. Frontiers of Information Technology & Electronic Engineering, 2015, 16(3): 205-216.
DOI：

Li Yu-xiang, Zhao Yin-liang, Liu Bin, et al. Optimization of thread partitioning parameters in speculative multithreading based on artificial immune algorithm*[J]. Frontiers of Information Technology & Electronic Engineering, 2015, 16(3): 205-216. DOI： 10.1631/FITEE.1400172.

摘要

目的

用人工免疫算法优化线程划分过程的主要影响因素，使不同应用获得最优划分方案。

创新点

将智能算法应用到推测多线程技术，实现该技术在线程划分过程中的优化。

方法

首先，根据启发式规则提取影响线程划分的五个参数，分别是DT，TSL，TSU，SDL，SDU。五个参数根据启发式规则确定取值范围，步长变化是随机的。将加速比设定为目标，五个参数变化形成解空间，优化目标是在解空间中寻找最优解（图6），即找出各个应用最优的划分策略。利用人工免疫算法搜索解空间，找到最优解（表4）。

结论

针对Olden测试集中每个测试函数获得最优划分参数值（图10-20），测试集中的函数在四核平台上的测试性能较之机器学习方法线程划分算法提高3.00%，较之启发式规则线程划分方法性提高8.92%。

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

references

H Akkary , MA Driscoll . A dynamic multithreading processor . 1998 . Proc. 31st Annual ACM/IEEE Int. Symp. on Microarchitecture . 226 - 236 .

A Bhowmik , M Franklin . A general compiler framework for speculative multithreading . 2002 . Proc. 14th Annual ACM Symp. on Parallel Algorithms and Architectures . 99 - 108 . DOI: 10.1145/564870.564885 http://doi.org/10.1145/564870.564885 .

Z Chen , Y Zhao , X Pan , 等 . An overview of Prophet . 2009 . Proc. 9th Int. Conf. on Algorithms and Architectures for Parallel Processing . 396 - 407 . DOI: 10.1007/978-3-642-03095-6_38 http://doi.org/10.1007/978-3-642-03095-6_38 .

D Dasgupta . Artificial Immune Systems and Their Applications , 1999 . Springer Berlin Heidelberg , DOI: 10.1007/978-3-642-59901-9 http://doi.org/10.1007/978-3-642-59901-9 .

LN de Castro , J Timmis . Artificial Immune Systems: a New Computational Intelligence Approach , 2002 . Springer .

Z Dong , Y Zhao , Y Wei , 等 . Prophet: a speculative multi-threading execution model with architectural support based on CMP . 2009 . Proc. 8th Int. Conf. on Embedded Computing, and Int. Conf. on Scalable Computing and Communications . 103 - 108 . DOI: 10.1109/EmbeddedCom-ScalCom.2009.128 http://doi.org/10.1109/EmbeddedCom-ScalCom.2009.128 .

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

V Krishnan , J Torrellas . A chip-multiprocessor architecture with speculative multithreading . IEEE Trans Comput , 1999 , 48 ( 9 ): 866 - 880 . DOI: 10.1109/12.795218 http://doi.org/10.1109/12.795218 .

B Liu , Y Zhao , Y Li , 等 . A thread partitioning approach for speculative multithreading . J Supercomput , 2014 , 67 ( 3 ): 778 - 805 . DOI: 10.1007/s11227-013-1000-1 http://doi.org/10.1007/s11227-013-1000-1 .

C Madriles , P Lopez , JM Codina , 等 . Anaphase: a fine-grain thread decomposition scheme for speculative multithreading . 2009 . Proc. 18th Int. Conf. on Parallel Architectures and Compilation Techniques . 15 - 25 . DOI: 10.1109/PACT.2009.27 http://doi.org/10.1109/PACT.2009.27 .

P Marcuello , A González . Clustered speculative multithreaded processors . 1999 . Proc. 13th Int. Conf. on Supercomputing . 365 - 372 . DOI: 10.1145/305138.305214 http://doi.org/10.1145/305138.305214 .

K Olukotun , L Hammond , M Willey . Improving the performance of speculatively parallel applications on the Hydra CMP . 1999 . Proc. 13th Int. Conf. on Supercomputing . 21 - 30 . DOI: 10.1145/305138.305155 http://doi.org/10.1145/305138.305155 .

CG Quiñones , C Madriles , J Sánchez , 等 . Mitosis compiler: an infrastructure for speculative threading based on pre-computation slices . 2005 . Proc. ACM SIGPLAN Conf. on Programming Language Design and Implementation . 269 - 279 . DOI: 10.1145/1064978.1065043 http://doi.org/10.1145/1064978.1065043 .

GS Sohi , SE Breach , TN Vijaykumar . Multiscalar processors . 1995 . Proc. 22nd Annual Int. Symp. on Computer Architecture . 414 - 425 . DOI: 10.1145/223982.224451 http://doi.org/10.1145/223982.224451 .

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

J Tsai , P Yew . The superthreaded architecture: thread pipelining with run-time data dependence checking and control speculation . 1996 . Proc. Conf. on Parallel Architectures and Compilation Techniques . 35 - 46 . DOI: 10.1109/PACT.1996.552553 http://doi.org/10.1109/PACT.1996.552553 .

J Tsai , J Huang , C Amlo , 等 . The superthreaded processor architecture . IEEE Trans Comput , 1999 , 48 ( 9 ): 881 - 902 . DOI: 10.1109/12.795219 http://doi.org/10.1109/12.795219 .

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

RP Wilson , R French , CS Wilson , 等 . The SUIF Compiler System: a Parallelizing and Optimizing Research Compiler . 1994 . Technical Report No. CSL-TR-94-620, Computer Systems Laboratory, Stanford University, CA .

Views

Downloads

CSCD

Alert me when the article has been cited

Submit

Tools

Publicity Resources

No data

Related Author

No data

Related Institution

No data

Chat

Address：Zhejiang University Press, 148 Tianmushan Road, Hangzhou, China Postal code：310028
Tel：+86-571-88273162 Email：fitee@zju.edu.cn
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰