Speculative Parallelization of Sequential Loops on Multicores

Chen Tian, Min Feng, Vijay Nagarajan, Rajiv Gupta

Research output: Contribution to journalArticlepeer-review

Abstract

The advent of multicores presents a promising opportunity for speeding up the execution of sequential programs through their parallelization. In this paper we present a novel solution for efficiently supporting software-based speculative parallelization of sequential loops on multicore processors. The execution model we employ is based upon state separation, an approach for separately maintaining the speculative state of parallel threads and non-speculative state of the computation. If speculation is successful, the results produced by parallel threads in speculative state are committed by copying them into the computation’s non-speculative state. If misspeculation is detected, no costly state recovery mechanisms are needed as the speculative state can be simply discarded. Techniques are proposed to reduce the cost of data copying between non-speculative and speculative state and efficiently carrying out misspeculation detection. We apply the above approach to speculative parallelization of loops in several sequential programs which results in significant speedups on a Dell PowerEdge 1900 server with two Intel Xeon quad-core processors.
Original languageEnglish
Pages (from-to)508-535
Number of pages28
JournalInternational journal of parallel programming
Volume37
Issue number5
DOIs
Publication statusPublished - 2009

Keywords

  • Multicores
  • Speculative parallelization
  • Profile-guided parallelization
  • State separation

Fingerprint

Dive into the research topics of 'Speculative Parallelization of Sequential Loops on Multicores'. Together they form a unique fingerprint.

Cite this