HL-TLS:Compiling Implementation of Thread Level Speculation Supporting Hot Spot

doi:10.3969/j.issn.1000-3428.2015.11.014

Abstract

Abstract: Thread Level Speculation(TLS) compiling can effectively improve the parallel efficiency.But the overheads,caused by the management of the speculative data and the failure of speculative thread’s rollback,decreases the improvement of the parallel performance.Aiming at the too big overhead of data management and thread rollback,the Hot Loops-TLS(HL-TLS) framework is proposed.HL-TLS marks the loops which can be efficiently paralleled as HL,using a more eager parallel way on HL to improve performance,while using conservative sequence way on non-HL to reduce the overheads.Experimental result shows that HL-TLS improves 20% performance.

Key words: parallel computing, multi-thread, speculative execution, Thread Level Speculation(TLS) parallel, Hot Loops(HL), dynamic transformation execution mechanism

摘要： 猜测并行化编译,即线程级猜测(TLS)编译,可将原来顺序运行的程序并行化。但由于猜测数据的不确定性引起的数据管理开销过大,以及猜测线程失败引起的线程回滚开销,使得并行后的执行性能较低。针对上述问题,提出一种HL-TLS并行化编译优化框架。HL-TLS能有效地标记并行化的循环体为热点循环体,采用对最高层次热点循环体进行更激进的并行化的方式提高性能,而对非热点循环体采用保守的顺序执行以减少开销。实验结果表明,使用HL-TLS编译优化框架,实验程序的执行效率可以提高20%。

关键词: 并行计算, 多线程, 猜测执行, 线程级猜测并行, 热点循环, 动态转换执行机制

CLC Number:

TP311

JIN Yue,LI Chunqiang,SHANG Yunhai,LU Yongjiang. HL-TLS:Compiling Implementation of Thread Level Speculation Supporting Hot Spot[J]. Computer Engineering, doi: 10.3969/j.issn.1000-3428.2015.11.014.

金跃,李春强,尚云海,卢永江. HL-TLS:支持热点的线程级猜测编译实现[J]. 计算机工程, doi: 10.3969/j.issn.1000-3428.2015.11.014.

/ / Recommend / Download Citations

URL: http://www.ecice06.com/EN/10.3969/j.issn.1000-3428.2015.11.014

http://www.ecice06.com/EN/Y2015/V41/I11/77

References

参考文献［1］Steffan J G,Colohan C G,Zhai A,et al.A Scalable Approach for Thread Level Speculation［C］//Pro-ceedings of the 27th Annual International Symposium on Computer Architecture.New York,USA:ACM Press,2000:1-12. ［2］赖鑫,刘聪,王志英.支持线程级猜测的存储体系结构设计［J］.计算机工程,2012,38(24):228-234. ［3］Krishnan V,Torrellas J.A Chip-multiprocessor Architec-ture with Speculative Multithreading［J］.IEEE Tran-sactions on Computers,1999,48(9):866-880. ［4］Cintra M,Llanos D R.Toward Efficient and Robust Software Speculative Parallelization on Multipro-cessors［C］//Proceedings of the 9th ACM SIGPLAN Symposium on Principles and Practice of Parallel Pro-gramming.New York,USA:ACM Press,2003:13-24. ［5］Liu W,Tuck J,Ceze L,et al.POSH:A TLS Compiler that Exploits Program Structure［C］//Proceedings of the 11th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming.New York,USA:ACM Press,2006:158-167. ［6］Yiapanis P,Rosas-Ham D,Brown G,et al.Optimizing Software Runtime Systems for Speculative Paralleliza-tion［J］.ACM Transactions on Architecture and Code Optimization,2013,9(4):39-51. ［7］Oancea C E,Mycroft A.Software Thread-level Specula-tion:An Optimistic Library Implementation［C］//Pro-ceedings of the 1st International Workshop on Multicore Software Engineering.New York,USA:ACM Press,2008:23-32. ［8］Oancea C E,Mycroft A.A Lightweight In-place Im-plementation for Software Thread-level Speculation［C］//Proceedings of the 21st Annual Symposium on Parallelism in Algorithms and Architectures.New York,USA:ACM Press,2009:223-232. ［9］Oancea C E,Mycroft A.Set-congruence Dynamic Anal-ysis for Thread-level Speculation［M］.Berlin,Germany:Springer-Verlag,2008:156-171. ［10］Rauchwerger L,Padua D.The LRPD Test:Speculative Run-time Parallelization of Loops with Privatization and Reduction Parallelization［C］//Proceedings of ACM SIGPLAN’95.New York,USA:ACM Press,1995:218-232. ［11］Dang F,Yu H,Rauchwerger L.The R-LRPD Test:Speculative Parallelization of Partially Parallel Loops,TX77843-3112［R］.College Station,USA:Texas A & M University,2001. ［12］Du Zhaohui,Lim Chu Cheow,Li Xiaofeng,et al.A Cost-driven Compilation Framework for Speculative Parallelization of Sequential Programs［C］//Proceedings of ACM SIGPLAN’04.New York,USA:ACM Press,2004:71-81. ［13］Dubey P K,O’Brien K,O’Brien K M,et al.Single-program Speculative Multithreading(SPSM) Architec-ture［C］//Proceedings of PACT’95.Manchester,UK:［s.n.］,1995:109-121. ［14］Xiang Lingxiang,Scott M L.Compiler Aided Manual Speculation for High Performance Concurrent Data Structures［C］//Proceedings of the 18th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming.New York,USA:ACM Press,2013:47-56. ［15］Aldea S,Estebanez A,Llanos D R,et al.A New GCC Plugin-based Compiler Pass to Add Support for Thread-level Speculation into OpenMP［C］//Proceedings of EPP’14.Porto,Portugal:Springer International Publish-ing,2014:234-245. ［16］郭辉,王琼,沈立,等.多核平台上的线程级猜测执行综述［J］.计算机科学,2014,41 (1):16-21. 编辑索书志

[1]	WANG Qihan, PANG Jianmin, YUE Feng, ZHU Di, SHEN Li, XIAO Qian. Implementation and Optimization of Parallel KNN Algorithm for Sunway Architecture [J]. Computer Engineering, 2023, 49(5): 286-294.
[2]	XIA Libin, LIU Xiaoyu, JIANG Xiaowei, SUN Gongxing. Memory Optimization Method for Parallel Computing Framework Based on Distributed Dataset [J]. Computer Engineering, 2023, 49(4): 43-51.
[3]	LI Jinguo, JIAO Xubin. Research on Intrusion Detection Model in Fog Computing Environment [J]. Computer Engineering, 2022, 48(5): 43-52.
[4]	HUANG Rui, JIN Guanghao, LI Lei, JIANG Wenchao, SONG Qingzeng. Design and Implementation of Accelerator for Lightweight Neural Network [J]. Computer Engineering, 2021, 47(9): 185-190,196.
[5]	YI Peihuai, LI Weidong, LIN Tao, ZOU Jiaheng, DENG Ziyan, LIU Yan. Application of GPU in Fast Muon Simulation [J]. Computer Engineering, 2021, 47(8): 100-108.
[6]	SHE Xin, HE Zhenying. Spark-based clique Community Search Algorithm Under Complex Attribute Condition [J]. Computer Engineering, 2021, 47(12): 54-61,70.
[7]	GUO Yuluo, BIAN Haodong, DONG Runting, TANG Jiahao, WANG Xiaoying, HUANG Jianqiang. Parallel Fourier Space Image Similarity Calculation Based on SIMD [J]. Computer Engineering, 2021, 47(11): 247-253.
[8]	XIAO Chenglong, NIE Ziyang, WANG Ning, ZHANG Zhongpeng, WANG Shanshan. Research on Maximum Clique Identification Based on Parallel Constraint Programming [J]. Computer Engineering, 2020, 46(4): 53-59,69.
[9]	XU Guowei, CHEN Jian, CHENG Yi. Research on Radar Clutter Simulation Based on GPU Parallel Computing [J]. Computer Engineering, 2020, 46(11): 306-314.
[10]	LI Jie, ZHU Hongliang, CHEN Yuling, XIN Yang. Improved Parallel Apriori Algorithm Based on Hash Storage and Transaction Weighting [J]. Computer Engineering, 2020, 46(11): 109-116.
[11]	SONG Kuangshi, LI Chong, ZHANG Shibo. Design and Implementation of a Lightweight Distributed Machine Learning System [J]. Computer Engineering, 2020, 46(1): 201-207.
[12]	SHEN Yan,DAI Yuxing. Parallel Cholesky Decomposition and Its Application Based on GPU [J]. Computer Engineering, 2019, 45(2): 284-289.
[13]	LI Wenxin, ZHOU Xiaobo, XU Renhai, QI Heng, LI Keqiu. An Approximate Smallest-Effective-Bottleneck-First Coflow Scheduling Mechanism [J]. Computer Engineering, 2019, 45(10): 19-25,32.
[14]	ZHU Jiazhou,SHAO Peinan,CHEN Jing. Research on Distributed Parallel Computing Processing Platform Architecture for Image Data [J]. Computer Engineering, 2017, 43(5): 60-66,74.
[15]	WANG Shuang,FENG Zhiyong. Construction and Analysis of Drug Network Model Based on Semantic Data [J]. Computer Engineering, 2016, 42(6): 31-36.

Please choose a citation manager

Content to export