Master/Slave Speculative Parallelization

Craig Zilles, Gurinder Sohi

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

Abstract

Master/Slave Speculative Parallelization (MSSP) is an execution paradigm for improving the execution rate of sequential programs by parallelizing them speculatively for execution on a multiprocessor. In MSSP one processor - the master - executes an approximate version of the program to compute selected values that the full program's execution is expected to compute. The master's results are checked by slave processors that execute the original program. This validation is parallelized by cutting the program's execution into tasks. Each slave uses its predicted inputs (as computed by the master) to validate the input predictions of the next task, inductively validating the entire execution. The performance of MSSP is largely determined by the execution rate of the approximate program. Since approximate code has no correctness requirements (in essence it is a software value predictor), it can be optimized more effectively than traditionally generated code. It is free to sacrifice correctness in the uncommon case to maximize performance in the common case. A simulation-based evaluation of an initial MSSP implementation achieves speedups of up to 1.7 (harmonic mean 1.25) on the SPEC2000 integer benchmarks. Performance is currently limited by the effectiveness with which our current automated infrastructure approximates programs, which can likely be improved significantly.

Original languageEnglish (US)
Title of host publicationProceedings - 35th Annual IEEE/ACM International Symposium on Microarchitecture, MICRO 2002
PublisherIEEE Computer Society
Pages85-96
Number of pages12
ISBN (Electronic)0769518591
DOIs
StatePublished - Jan 1 2002
Event35th Annual IEEE/ACM International Symposium on Microarchitecture, MICRO 2002 - Istanbul, Turkey
Duration: Nov 18 2002Nov 22 2002

Publication series

NameProceedings of the Annual International Symposium on Microarchitecture, MICRO
Volume2002-January
ISSN (Print)1072-4451

Other

Other35th Annual IEEE/ACM International Symposium on Microarchitecture, MICRO 2002
CountryTurkey
CityIstanbul
Period11/18/0211/22/02

Keywords

  • Decision support systems
  • Master-slave
  • Quadratic programming
  • Roentgenium
  • Tellurium

ASJC Scopus subject areas

  • Hardware and Architecture

Cite this