Copy or Discard execution model for speculative parallelization on multicores

Chen Tian, Min Feng, Vijay Nagarajan, Rajiv Gupta

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

The advent of multicores presents a promising opportunity for speeding up sequential programs via profile-based speculative parallelization of these programs. In this paper we present a novel solution for efficiently supporting software speculation on multicore processors. We propose the Copy or Discard (CorD) execution model in which the state of speculative parallel threads is maintained separately from the nonspeculative computation state. If speculation is successful, the results of the speculative computation are committed by copying them into the non-speculative state. If misspeculation is detected, no costly state recovery mechanisms are needed as the speculative state can be simply discarded. Optimizations are proposed to reduce the cost of data copying between nonspeculative and speculative state. A lightweight mechanism that maintains version numbers for non-speculative data values enables misspeculation detection. We also present an algorithm for profile-based speculative parallelization that is effective in extracting parallelism from sequential programs. Our experiments show that the combination of CorD and our speculative parallelization algorithm achieves speedups ranging from 3.7 to 7.8 on a Dell PowerEdge 1900 server with two Intel Xeon quad-core processors.
Original languageEnglish
Title of host publicationProceedings of the 41st IEEE/ACM International Symposium on Microarchitecture (MICRO-41)
Pages330-341
Number of pages12
ISBN (Electronic)978-1-4244-2837-3
DOIs
Publication statusPublished - 1 Nov 2008

Keywords

  • copy/discard execution model
  • misspeculation detection
  • multicore processor
  • optimising compiler
  • parallel thread
  • profile-based speculative parallelization algorithm
  • sequential program
  • software speculation
  • multi-threading
  • multiprocessing systems
  • optimising compilers
  • parallel algorithms

Fingerprint Dive into the research topics of 'Copy or Discard execution model for speculative parallelization on multicores'. Together they form a unique fingerprint.

Cite this