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

Fingerprint

Synchronization
Hardware

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Hardware and Architecture

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.

Speculative synchronization : Applying thread-level speculation to explicitly parallel applications. / Martínez, José F.; Torrellas, Josep.

2002. 18-29 Paper presented at Tenth International Conference on Architectural Support for Programming Languages and Operating Systems, San Jose, CA, United States.

Research output: Contribution to conferencePaper

Martínez, JF & Torrellas, J 2002, 'Speculative synchronization: Applying thread-level speculation to explicitly parallel applications' Paper presented at Tenth International Conference on Architectural Support for Programming Languages and Operating Systems, San Jose, CA, United States, 10/5/02 - 10/9/02, pp. 18-29.
Martínez JF, Torrellas J. Speculative synchronization: Applying thread-level speculation to explicitly parallel applications. 2002. Paper presented at Tenth International Conference on Architectural Support for Programming Languages and Operating Systems, San Jose, CA, United States.
Martínez, José F. ; Torrellas, Josep. / Speculative synchronization : Applying thread-level speculation to explicitly parallel applications. Paper presented at Tenth International Conference on Architectural Support for Programming Languages and Operating Systems, San Jose, CA, United States.12 p.
@conference{28085eb3a9c146ac9b337ed3b4a016dd,
title = "Speculative synchronization: Applying thread-level speculation to explicitly parallel applications",
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.",
author = "Mart{\'i}nez, {Jos{\'e} F.} and Josep Torrellas",
year = "2002",
month = "12",
day = "1",
language = "English (US)",
pages = "18--29",
note = "Tenth International Conference on Architectural Support for Programming Languages and Operating Systems ; Conference date: 05-10-2002 Through 09-10-2002",

}

TY - CONF

T1 - Speculative synchronization

T2 - Applying thread-level speculation to explicitly parallel applications

AU - Martínez, José F.

AU - Torrellas, Josep

PY - 2002/12/1

Y1 - 2002/12/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0036949529&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0036949529&partnerID=8YFLogxK

M3 - Paper

AN - SCOPUS:0036949529

SP - 18

EP - 29

ER -