Please wait a minute...
FITEE
Front. Inform. Technol. Electron. Eng.  2015, Vol. 16 Issue (3): 205-216    DOI: 10.1631/FITEE.1400172
    
基于人工免疫算法的推测多线程线程划分参数的优化
Yu-xiang Li, Yin-liang Zhao, Bin Liu, Shuo Ji
Department of Computer Science and Technology, Xi'an Jiaotong University, Xi'an 710049, China
Optimization of thread partitioning parameters in speculative multithreading based on artificial immune algorithm
Yu-xiang Li, Yin-liang Zhao, Bin Liu, Shuo Ji
Department of Computer Science and Technology, Xi'an Jiaotong University, Xi'an 710049, China
 全文: PDF 
摘要： 目的：用人工免疫算法优化线程划分过程的主要影响因素，使不同应用获得最优划分方案。
创新点：将智能算法应用到推测多线程技术，实现该技术在线程划分过程中的优化。
方法：首先，根据启发式规则提取影响线程划分的五个参数，分别是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.
Key words: Speculative multithreading    Thread partitioning    Artificial immune algorithm
收稿日期: 2014-05-13 出版日期: 2015-03-04
CLC:  TP311  
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　
Yu-xiang Li
Yin-liang Zhao
Bin Liu
Shuo Ji

引用本文:

Yu-xiang Li, Yin-liang Zhao, Bin Liu, Shuo Ji. Optimization of thread partitioning parameters in speculative multithreading based on artificial immune algorithm. Front. Inform. Technol. Electron. Eng., 2015, 16(3): 205-216.

链接本文:

http://www.zjujournals.com/xueshu/fitee/CN/10.1631/FITEE.1400172    或    http://www.zjujournals.com/xueshu/fitee/CN/Y2015/V16/I3/205

[1] Deng Chen, Yan-duo Zhang, Wei Wei, Shi-xun Wang, Ru-bing Huang, Xiao-lin Li, Bin-bin Qu, Sheng Jiang. 基于改进规则检查静态分析技术的高效脆弱性检测方法[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(3): 332-345.
[2] Long-xiang Wang, Xiao-she Dong, Xing-jun Zhang, Yin-feng Wang, Tao Ju, Guo-fu Feng. TextGen：用于新型存储系统基准测试的真实文本数据集生成方法[J]. Front. Inform. Technol. Electron. Eng., 2016, 17(10): 982-993.
[3] Shahab Pourtalebi, Imre Horváth. 用于定义系统表现特征的基因型与表型仓库数据库的信息图式构造方法[J]. Front. Inform. Technol. Electron. Eng., 2016, 17(9): 862-884.
[4] Saif Ur Rehman Khan, Sai Peck Lee, Mohammad Dabbagh, Muhammad Tahir, Muzafar Khan, Muhammad Arif. RePizer：一种软件需求排序架构[J]. Front. Inform. Technol. Electron. Eng., 2016, 17(8): 750-765.
[5] Hui-zong Li, Xue-gang Hu, Yao-jin Lin, Wei He, Jian-han Pan. 基于共同共现群体相似度的社会化标签聚类方法[J]. Front. Inform. Technol. Electron. Eng., 2016, 17(2): 122-134.
[6] Mohammad Alshayeb, Nasser Khashan, Sajjad Mahmood. 一种集成的统一建模语言框架[J]. Frontiers of Information Technology & Electronic Engineering, 2016, 17(2): 143-159.
[7] . Dr. Hadoop: an infinite scalable metadata management for Hadoop—How the baby elephant becomes immortal[J]. Front. Inform. Technol. Electron. Eng., 2016, 17(1): 15-31.
[8] Ignacio Marin, Francisco Ortin, German Pedrosa, Javier Rodriguez. 使用模型变换为多种终端生成原生用户界面[J]. Front. Inform. Technol. Electron. Eng., 2015, 16(12): 995-1017.
[9] Hong Yin, Shu-qiang Yang, Xiao-qian Zhu, Shao-dong Ma, Lu-min Zhang. 基于趋势特征的时间序列符号化方法[J]. Front. Inform. Technol. Electron. Eng., 2015, 16(9): 744-758.
[10] Ping Xie, Jian-zhong Huang, Er-wei Dai, Qiang Cao, Chang-sheng Xie. 一种负载平衡的RAID-6存储方案[J]. Front. Inform. Technol. Electron. Eng., 2015, 16(5): 335-345.
[11] Xiao-xia Zhang, Qiang-hua Xiao, Bin Li, Sai Hu, Hui-jun Xiong, Bi-hai Zhao. OMMR:一种关键模块重叠部分评价指标[J]. Front. Inform. Technol. Electron. Eng., 2015, 16(4): 293-300.
[12] László Lengyel, Hassan Charaf. 测试驱动的模式转换检验/认证[J]. Front. Inform. Technol. Electron. Eng., 2015, 16(2): 85-97.
[13] Alireza Parvizi-Mosaed, Shahrouz Moaven, Jafar Habibi, Ghazaleh Beigi, Mahdieh Naser-Shariat. 基于扩展型服务导向建模与应用（SOMA）的一种自适应服务导向方法[J]. Front. Inform. Technol. Electron. Eng., 2015, 16(1): 43-69.
[14] Zi-ying Dai, Xiao-guang Mao, Li-qian Chen, Yan Lei. Automatic recovery from resource exhaustion exceptions by collecting leaked resources[J]. Front. Inform. Technol. Electron. Eng., 2014, 15(8): 622-635.
[15] Juan J. Cuadrado-Gallego, Alain Abran, Pablo Rodriguez-Soria, Miguel A. Lara. An experimental study on the conversion between IFPUG and UCP functional size measurement units[J]. Front. Inform. Technol. Electron. Eng., 2014, 15(3): 161-173.