Computer Science ›› 2014, Vol. 41 ›› Issue (1): 16-21.

Previous Articles     Next Articles

Survey of Thread Level Speculation on Multi-core Platform

GUO Hui,WANG Qiong,SHEN Li and WANG Zhi-ying   

  • Online:2018-11-14 Published:2018-11-14

Abstract: The development of multi-core architecture enables researchers to explore coarse-grained parallelism by a speculative mode.Thread level speculation (TLS) is the most representative one among current speculative parallelization techniques.The most abstractive advantage of TLS is the simple programming model in which programmers only need to mark the codes that can be executed speculatively while the runtime system or hardware is responsible for the correctness.This paper analyzed the existing TLS techniques and summarized the challenges TLS confronts and the developmented trend in the future.The main contributions are:1) we presented a novel taxonomy of TLS techniques based on the life circle of speculative variables and compared their advantages and disadvantages,2) we summarized the design space of multi-core platform supporting TLS on the basis of the life circle of speculative variables and proposed several ways to explore it,3) the paper pointed out the challenges TLS confronts and the development trend in the future.

Key words: Multi-core,Architecture,TLS,Speculative variable

[1] Lee J,Wu Hai-cheng,Ravichandran M,et al.Thread tailor:dynamically weaving threads together for efficient,adaptive parallel applications[C]∥ISCA.2010
[2] Speculative Multithreading.http:// en.wikipedia.org/wiki/Speculative_multithreading
[3] Prabhu M,Olukotun K.Using thread-level speculation to simplify manual parallelization[C]∥Proc.of the 2003Principles and Practices of Parallel Programming.2003
[4] Prabhu M,Olukotun K.Exposing speculative thread parallelism in SPEC 2000[C]∥Proc.of the 2005Principles and Practices of Parallel Programming.2005
[5] Olukotun K,Hammond L,Laudon J. 片上多处理器体系结构,改善吞吐率和延迟的技术[M].王东升,王海霞,李鹏,译.北京:机械工业出版社,2009
[6] Ding Chen,Shen Xi-peng,Kelsey K,et al.Software behavior oriented parallelization[C]∥Proc.of ACM SIGNPLAN Conf.on Programming Language Design and Implementation.2007
[7] Kelsey K,Bai T,Ding C,et al.Fast track:A software system for speculative program optimization[C]∥Proceedings of the International Symposium on Code Generation and Optimization (CGO).2009:157-168
[8] Tian Chen,Feng Min,Nagarajan V,et al.Copy or discard execution model for speculative parallelization on multicores[C]∥the 41st IEEE/ACM Intl.Symp.on Microarchitecture.2008
[9] Steffan J G,Colohan C,Zhai A,et al.The STAMPede approach to thread-level speculation[J].ACM Trans.on Computer Systems,2005,23(3)
[10] Hammond L,Hubbert B,Siu M,et al.The Stanford Hydra CMP[J].IEEE MICRO Magazine,2000,20(2):71-84
[11] Feng M,Gupta R,Hu Y.SpiceC:scalable parallelism via implicit copying and explicit commit[C]∥Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming.2011:69-80
[12] Steffan J,Colohan C,Zhai A,et al.A Scalable Approach toThread-Level Speculation[C]∥Proc.27th Annual Intl.Symp.on Computer Architecture.June 2000:1-12
[13] Oplinger J,Heine D,Liao S-W,et al.Software and hardware for exploiting speculative parallelism with a multiprocessor[M].Computer Systems Laboratary,Stanford University,1997
[14] Gopal S,Vijaykumar T N,Smith J E,et al.Speculative Versioning Cache[C]∥Proc.4th Intl.Symp.on High-Performance.Computer Architecture,February 1998:195-205
[15] Raman A,Kim Han-jun,Mason T R,et al.Speculative parallelization using software multi-threaded transactions[C]∥Proc.of the 15th Architecture Support for Programming Languages and Operating Systems.2010
[16] Vachharajani N,Rangan R,Raman E,et al.Speculative decoupled software pipelining[C]∥PACT.2007:49-59
[17] Cintra M,Martinez J F,Torrellas J.Architectural support for scalable speculative parallelization in shared memory systems[C]∥Proc.of the 27th Int.Symp.on Computer Architecture.2000
[18] Tsai J Y,Huang J,Amlo C,et al.The Superthreaded Processor Architecture[J].IEEE Trans.on Computers,1999,48(9):881-902
[19] Bruening D,Devabhaktuni S,Amarasinghe S.Softspec:Soft-ware-based speculative parallelism[C]∥Proceedings of the 3rd ACM Workshop on Feedback Directed and Dynamic Optimization (FDDO3).2000
[20] Rundberg P,Stenstrm P.An all software thread-level data dependence speculation system for multiprocessors[J].Journal of Instruction-Level Parallelism,2001,3(1)
[21] Oancea C E,Mycroft A,Harris T.A lightweight in-place implementation for software thread-level speculation[C]∥Proc.of the 21st Annual Symp.on Parallelism in Algorithms and Architectures.2009
[22] Rauchwerger L,Padua D.The LRPD test:Speculative run-time paralle-lization of loops with privatization and reduction parallelization[C]∥Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation.La Jolla,CA,June 1995
[23] Pyla H K,Ribbens C,Varadarajan S.Exploiting Coarse-GrainSpeculative Parallelism[C]∥Proceedings of the ACM international conference on Object oriented programming systems languages and applications.2011:555-574
[24] Olukotun K,Hammod L,Willey M.Improving the performance of speculatively parallel applications on the Hydra CMP[C]∥Proc.of the 1999ACM Intl.Conf.on Supercomputing.1999
[25] Steffan J G,Goldstein S C.Hardware support for thread-levelspeculation[D].Carnegie Mellon University,2003
[26] Kazi H,Lilja D J.Coarse-grained thread pipelining:A speculative parallel execution model for shared-memory multiprocessors[J].IEEE Trans.on Parallel and Distributed Systems,2001,12(9)
[27] Pickett C J F,Verbrugge C.Software thread level speculation for the java language and virtual machine environment[C]∥Proc.of the 18th Intl.Workshop on Languages and Compilers for Parallel Computing.2005
[28] Ke Chuan-le,Liu Lei,Zhang Chao,et al.Safe parallel programming using dynamic dependence hints[C]∥OOPSLA.2011:243-258
[29] Garzaran M J,Prvulovic M,Llaberia J M,et al.Tradeoffs inbuffering speculative memory state for thread-level speculation in multiprocessor[J].TACO,2005,2(3)
[30] OpenMP.http://www.openmp.org/
[31] Kim H,Johnson N P,Lee J W,et al.Automatic speculative DOALL for clusters[C]∥Proceedings of the Tenth International Symposium on Code Generation and Optimization.ACM,2012:94-103
[32] Aldea S,Llanos D R,González-Escribano A.Support for thread-level speculation into OpenMP,OpenMP in a Heterogeneous World[M].Berlin Heidelberg:Springer,2012:275-278
[33] Hertzberg B,Olukotun K.Runtime automatic speculative parallelization[C]∥Proceedings of the 20119th Annual IEEE/ACM International Symposium on Code Generation and Optimization.IEEE Computer Society,2011:64-73
[34] 赖鑫,刘聪,王志英.支持线程级猜测的存储体系结构设计的存储体系结构设计[J].Computer Engineering,2012,38(24)

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!