Speculative synchronization: Applying thread-level speculation to explicitly parallel applications

José F. Martínez, Josep Torrellas

Research output: Contribution to conferencePaper

Abstract

Barriers, locks, and flags are synchronizing operations widely used by programmers and parallelizing compilers to produce race-free parallel programs. Often times, these operations are placed suboptimally, either because of conservative assumptions about the program, or merely for code simplicity. We propose Speculative Synchronization, which applies the philosophy behind Thread-Level Speculation (TLS) to explicitly parallel applications. Speculative threads execute past active barriers, busy locks, and unset flags instead of waiting. The proposed hardware checks for conflicting accesses and, if a violation is detected, the offending speculative thread is rolled back to the synchronization point and restarted on the fly. TLS's principle of always keeping a safe thread is key to our proposal: in any speculative barrier, lock, or flag, the existence of one or more safe threads at all times guarantees forward progress, even in the presence of access conflicts or speculative buffer overflow. Our proposal requires simple hardware and no programming effort. Furthermore, it can coexist with conventional synchronization at run time. We use simulations to evaluate 5 compiler- and hand-parallelized applications. Our results show a reduction in the time lost to synchronization of 34% on average, and a reduction in overall program execution time of 7.4% on average.

Original languageEnglish (US)
Pages18-29
Number of pages12
StatePublished - Dec 1 2002
EventTenth International Conference on Architectural Support for Programming Languages and Operating Systems - San Jose, CA, United States
Duration: Oct 5 2002Oct 9 2002

Other

OtherTenth International Conference on Architectural Support for Programming Languages and Operating Systems
CountryUnited States
CitySan Jose, CA
Period10/5/0210/9/02

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Hardware and Architecture

Fingerprint Dive into the research topics of 'Speculative synchronization: Applying thread-level speculation to explicitly parallel applications'. Together they form a unique fingerprint.

  • Cite this

    Martínez, J. F., & Torrellas, J. (2002). Speculative synchronization: Applying thread-level speculation to explicitly parallel applications. 18-29. Paper presented at Tenth International Conference on Architectural Support for Programming Languages and Operating Systems, San Jose, CA, United States.