TACLeBench中内核程序循环级推测并行性分析

doi:10.11772/j.issn.1001-9081.2020111792

计算机应用 ›› 2021, Vol. 41 ›› Issue (9): 2652-2657.DOI: 10.11772/j.issn.1001-9081.2020111792

所属专题：先进计算

TACLeBench中内核程序循环级推测并行性分析

孟慧玲¹, 王耀彬¹, 李凌¹, 杨洋², 王欣夷¹, 刘志勤¹

1. 西南科技大学计算机科学与技术学院, 绵阳四川 621010;
2. 四川省计算机研究院, 成都 610041

收稿日期:2020-11-17 修回日期:2021-02-07 出版日期:2021-09-10 发布日期:2021-05-08
通讯作者: 王耀彬
作者简介:孟慧玲(1997-),女,四川眉山人,硕士研究生,主要研究方向:计算机系统结构;王耀彬(1982-),男,四川乐山人,教授,博士,CCF会员,主要研究方向:计算机系统结构;李凌(1982-),男,四川泸州人,讲师,博士,主要研究方向:网络安全、高性能计算、数值模拟与仿真;杨洋(1982-),男,四川泸州人,工程师,硕士,主要研究方向:虚拟现实、软件工程;王欣夷(1996-),女,四川中江人,硕士研究生,主要研究方向:计算机系统结构;刘志勤(1962-),女,四川绵阳人,教授,硕士,主要研究方向:高性能计算。
基金资助:
国家自然科学基金面上项目（61672438）。

Loop-level speculative parallelism analysis of kernel program in TACLeBench

MENG Huiling¹, WANG Yaobin¹, LI Ling¹, YANG Yang², WANG Xinyi¹, LIU Zhiqin¹

1. School of Computer Science and Technology, Southwest University of Science and Technology, Mianyang Sichuan 621010, China;
2. Sichuan Institute of Computer Sciences, Chengdu Sichuan 610041, China

Received:2020-11-17 Revised:2021-02-07 Online:2021-09-10 Published:2021-05-08
Supported by:
This work is partially supported by the Surface Program of National Natural Science Foundation of China (61672438).

摘要/Abstract

摘要： 线程级推测（TLS）技术可挖掘程序并行执行潜能，提高多核资源利用率，但目前TACLeBench的内核基准仍未在TLS并行化中得到有效分析。针对该问题设计了循环级推测执行的剖析方案和剖析工具。选取7个代表性的TACLeBench内核基准程序，首先对程序进行初始化分析，选取程序热点片段插入循环标识；其次对这些片段进行交叉编译，记录程序推测线程与内存地址相关数据，剖析其循环级最大潜在并行性；最后综合探讨程序运行时的特征（线程粒度、可并行化覆盖率、依赖特征）以及源码对加速比的影响。实验结果表明：1）该类程序适合采用TLS加速，与串行执行结果相比，循环结构的推测执行下的大部分程序的加速比在2以上，其中最高加速比达到20.79；2）利用TLS加速TACLeBench内核程序时，多数应用可有效利用4核到16核的计算资源。

关键词: 线程级推测, 多核, 并行, TACLeBench, 内核基准

Abstract: Thread-Level Speculation (TLS) technology can tap the parallel execution potential of programs and improve the utilization of multi-core resources. However, the current TACLeBench kernel benchmarks are not effectively analyzed in TLS parallelization. In response to this problem, the loop-level speculative execution analysis scheme and analysis tool were designed. With 7 representative TACLeBench kernel benchmarks selected, firstly, the initialization analysis was performed to the programs, the program hot fragments were selected to insert the loop identifier. Then, the cross-compilation was performed to these fragments, the program speculative thread and the memory address related data were recorded, and the maximun potential of the loop-level parallelism was analyzed. Finally, the program runtime characteristics (thread granularity, parallelizable coverage, dependency characteristics) and the impacts of the source code on the speedup ratio were comprehensively discussed. Experimental results show that:1) this type of programs is suitable for TLS acceleration, compared with serial execution results, under the loop structure speculative execution, the speedup ratios for most programs are above 2, and the highest speedup ratio in them can reach 20.79; 2) by using TLS to accelerate the TACLeBench kernel programs, most applications can effectively make use of 4-core to 16-core computing resources.

Key words: Thread-Level Speculation (TLS), multi-core, parallel, TACLeBench, kernel benchmark

中图分类号:

TP302.7

孟慧玲, 王耀彬, 李凌, 杨洋, 王欣夷, 刘志勤. TACLeBench中内核程序循环级推测并行性分析[J]. 计算机应用, 2021, 41(9): 2652-2657.

MENG Huiling, WANG Yaobin, LI Ling, YANG Yang, WANG Xinyi, LIU Zhiqin. Loop-level speculative parallelism analysis of kernel program in TACLeBench[J]. Journal of Computer Applications, 2021, 41(9): 2652-2657.

参考文献

[1] 张朋. 多核平台下串行程序的并行化改造[D]. 成都:电子科技大学,2015:1-3.(ZHANG P. Parallel transformation of serialprogram under multi-core platform[D]. Chengdu:University of Electronic Science and Technology of China,2015:1-3.)
[2] 张潇, 支天. 面向多核处理器的机器学习推理框架[J]. 计算机研究与发展,2019,56(9):1977-1987. (ZHANG X,ZHI T. Machine learning inference framework on multi-core processor[J]. Journal of Computer Research and Development,2019,56(9):1977-1987.)
[3] HIRATA H, NUNOME A. Decoupling computation and result write-back for thread-level parallelization[J]. International Journal of Software Innovation,2020,8(3):19-34.
[4] 马巧梅. 基于程序特征的线程划分方法的研究[J]. 计算机科学与探索,2018,12(6):872-885.(MA Q M. Research of thread partitioning approach based on program characteristics[J]. Journal Frontiers of Computer Science and Technology,2018,12(6):872-885.)
[5] 刘聪. 面向多核体系结构的并行优化关键技术研究[D]. 长沙:国防科技大学,2014:1-7. (LIU C. Research on the key techniques of parallelization and optimization for multi-core architecture[D]. Changsha:National University of Defense Technology,2014:1-7.)
[6] VIJAYKUMAR T N,SOHI G S. Task selection for a multiscalar processor[C]//Proceedings of the 31st Annual ACM/IEEE International Symposium on Microarchitecture. Piscataway:IEEE, 1998:81-92.
[7] HAMMOND L,HUBBERT B A,SIU M,et al. The Stanford Hydra CMP[J]. IEEE Micro,2000,20(2):71-84.
[8] HAMMOND L,CARLSTROM B D,WONG V,et al. Transactional coherence and consistency:simplifying parallel hardware and software[J]. IEEE Micro,2004,24(6):92-103.
[9] STEFFAN J G,COLOHAN C,ZHAI A,et al. The STAMPede approach to thread-level speculation[J]. ACM Transactions on Computer Systems,2005,23(3):253-300.
[10] 刘斌, 赵银亮, 韩博, 等. 基于性能预测的推测多线程循环选择方法[J]. 电子与信息学报,2014,36(11):2768-2774.(LIU B, ZHAO Y L,HAN B,et al. A loop selection approach based on performance prediction for speculative multithreading[J]. Journal of Electronics and Information Technology,2014,36(11):2768-2774.)
[11] 李美蓉, 赵银亮. 一种基于推测代价评估的推测多线程并行粒度调节方法[J]. 计算机应用与软件,2019,36(4):29-36,90. (LI M R,ZHAO Y L. A parallel granularity tuning approach for speculative multithreading based on speculative cost evaluation[J]. Computer Applications and Software,2019,36(4):29-36,90.)
[12] SALAMANCA J,AMARAL J N,ARAUJO G. Using hardwaretransactional-memory support to implement thread-level speculation[J]. IEEE Transactions on Parallel and Distributed Systems,2018,29(2):466-480.
[13] FALK H,ALTMEYER S,HELLINCKX P,et al. TACLeBench:a benchmark collection to support worst-case execution time research[C]//Proceedings of the 16th International Workshop on Worst-Case Execution Time Analysis. Wadern:Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik,2016:No. 2.
[14] CARVALHO H,NELISSEN G,ZAYKOV P. mcQEMU:timeaccurate simulation of multi-core platforms using QEMU[C]//Proceedings of the 23rd Euromicro Conference on Digital System Design. Piscataway:IEEE,2020:81-88.
[15] POORHOSSEINI M,NEBEL W,GRÜTTNER K. A compiler comparison in the RISC-V ecosystem[C]//Proceedings of the 2020 International Conference on Omni-layer Intelligent Systems. Piscataway:IEEE,2020:1-6.
[16] SEGARRA J,CORTADELLA J,TEJERO R G,et al. Automatic safe data reuse detection for the WCET analysis of systems with data caches[J]. IEEE Access,2020,8:192379-192392.
[17] 李颖颖, 庞建民, 李雁冰, 等. 一种面向众核处理器的嵌套循环多维并行识别方法[J]. 计算机应用研究,2018,35(11):3311-3314.(LI Y Y,PANG J M,LI Y B,et al. Multi-dimensional parallelism recognition method of nested loop for many-core processors[J]. Application Research of Computers,2018,35(11):3311-3314.)
[18] 王耀彬, 安虹, 郭锐, 等. 用线程级推测技术在多核体系结构上并行化科学计算应用[J]. 小型微型计算机统,2010,31(2):264-270.(WANG Y B,AN H,GUO R,et al. Exposing threadlevel speculation parallelism in scientific applications on multicore architecture[J]. Journal of Chinese Computer Systems,2010,31(2):264-270.)
[19] SCHOEBERL M, NIELSEN C. A stack cache for real-time systems[C]//Proceedings of the IEEE 19th International Symposium on Real-Time Distributed Computing. Piscataway:IEEE,2016:150-157.

TACLeBench中内核程序循环级推测并行性分析

Loop-level speculative parallelism analysis of kernel program in TACLeBench

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	王周恺, 张炯, 马维纲, 王怀军. 面向高速列车监测数据的并行解压缩算法[J]. 计算机应用, 2021, 41(9): 2586-2593.
[2]	安鑫, 杨海娇, 李建华, 任福继. 热安全约束下异构多核系统动态映射方法[J]. 计算机应用, 2021, 41(9): 2631-2638.
[3]	蒋林, 施佳琪, 李远成. 可重构结构下合成视点失真变化算法并行设计与实现[J]. 计算机应用, 2021, 41(6): 1734-1740.
[4]	张辰, 田甜, 杨秀婷, 巩敦卫. 基于占优关系的并行程序通信覆盖约减方法[J]. 计算机应用, 2021, 41(6): 1741-1747.
[5]	陈争涛, 黄灿, 杨波, 赵立, 廖勇. 基于迁移学习的并行卷积神经网络牦牛脸识别算法[J]. 计算机应用, 2021, 41(5): 1332-1336.
[6]	解文博, 韦永壮, 刘争红. 基于CUDA的SKINNY加密算法并行实现与分析[J]. 计算机应用, 2021, 41(4): 1136-1141.
[7]	王晓峰, 蒋彭龙, 周辉, 赵雄波. 面向卷积神经网络的高并行度FPGA加速器设计[J]. 计算机应用, 2021, 41(3): 812-819.
[8]	杨先凤, 贵红军, 傅春常. 统一计算设备架构下的F-X域预测滤波并行算法[J]. 计算机应用, 2021, 41(2): 486-491.
[9]	丛旌, 韦永壮, 刘争红. SM4密码算法的阶梯式相关能量分析[J]. 计算机应用, 2020, 40(7): 1977-1982.
[10]	李杏峰, 黄玉清, 任珍文. 联合低秩稀疏的多核子空间聚类算法[J]. 计算机应用, 2020, 40(6): 1648-1653.
[11]	安鑫, 夏近伟, 杨海娇, 欧阳一鸣, 任福继. 基于离散控制器合成的异构多核系统资源管理方法[J]. 计算机应用, 2020, 40(6): 1698-1706.
[12]	张伍, 陈红梅. 基于多核模糊粗糙集与蝗虫优化算法的高光谱波段选择[J]. 计算机应用, 2020, 40(5): 1425-1430.
[13]	顾军华, 王锋, 戚永军, 孙哲然, 田泽培, 张亚娟. 基于多尺度卷积特征融合的肺结节图像检索方法[J]. 计算机应用, 2020, 40(2): 561-565.
[14]	曾志阳, 陈燕, 王珂. 圆片下料并行遗传算法的设计与实现[J]. 计算机应用, 2020, 40(2): 392-397.
[15]	李翠, 陈庆奎. 基于DPDK并行通信的动态监控模型[J]. 计算机应用, 2020, 40(2): 335-341.