Dancing with uncertainty

Sasa Misailovic, Stelios Sidiroglou, Martin C. Rinard

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

Abstract

We present Dubstep, a novel system that uses the find transform-navigate approach to automatically explore new parallelization opportunities in already parallelized (fullysynchronized) programs by opportunistically relaxing synchronization primitives. This set of transformations generates a space of alternative, possibly non-deterministic, parallel programs with varying performance and accuracy characteristics. The freedom to generate parallel programs whose output may differ (within statistical accuracy bounds) from the output of the original program enables a significantly larger optimization space. Dubstep then searches this space to find a parallel program that will, with high likelihood, produce outputs that are acceptably close to the outputs that the original, fully synchronized parallel program would have produced. Initial results from our benchmarked application show that Dubstep can generate acceptably accurate and efficient versions of a parallel program that occupy different positions in performance/accuracy trade off space.

Original languageEnglish (US)
Title of host publicationSPLASH 2012
Subtitle of host publicationRACES 2012 - Proceedings of the 2012 ACM Workshop on Relaxing Synchronization for Multicore and Manycore Scalability
Pages51-60
Number of pages10
DOIs
StatePublished - Dec 1 2012
Externally publishedYes
Event2012 ACM Workshop on Relaxing Synchronization for Multicore and Manycore Scalability, RACES 2012 - Tucson, AZ, United States
Duration: Oct 21 2012Oct 21 2012

Publication series

NameSPLASH 2012: RACES 2012 - Proceedings of the 2012 ACM Workshop on Relaxing Synchronization for Multicore and Manycore Scalability

Other

Other2012 ACM Workshop on Relaxing Synchronization for Multicore and Manycore Scalability, RACES 2012
CountryUnited States
CityTucson, AZ
Period10/21/1210/21/12

Fingerprint

Synchronization
Mathematical transformations
Uncertainty

Keywords

  • Accuracy
  • Parallelization
  • Statistical test
  • Tradeoff

ASJC Scopus subject areas

  • Hardware and Architecture

Cite this

Misailovic, S., Sidiroglou, S., & Rinard, M. C. (2012). Dancing with uncertainty. In SPLASH 2012: RACES 2012 - Proceedings of the 2012 ACM Workshop on Relaxing Synchronization for Multicore and Manycore Scalability (pp. 51-60). (SPLASH 2012: RACES 2012 - Proceedings of the 2012 ACM Workshop on Relaxing Synchronization for Multicore and Manycore Scalability). https://doi.org/10.1145/2414729.2414738

Dancing with uncertainty. / Misailovic, Sasa; Sidiroglou, Stelios; Rinard, Martin C.

SPLASH 2012: RACES 2012 - Proceedings of the 2012 ACM Workshop on Relaxing Synchronization for Multicore and Manycore Scalability. 2012. p. 51-60 (SPLASH 2012: RACES 2012 - Proceedings of the 2012 ACM Workshop on Relaxing Synchronization for Multicore and Manycore Scalability).

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

Misailovic, S, Sidiroglou, S & Rinard, MC 2012, Dancing with uncertainty. in SPLASH 2012: RACES 2012 - Proceedings of the 2012 ACM Workshop on Relaxing Synchronization for Multicore and Manycore Scalability. SPLASH 2012: RACES 2012 - Proceedings of the 2012 ACM Workshop on Relaxing Synchronization for Multicore and Manycore Scalability, pp. 51-60, 2012 ACM Workshop on Relaxing Synchronization for Multicore and Manycore Scalability, RACES 2012, Tucson, AZ, United States, 10/21/12. https://doi.org/10.1145/2414729.2414738
Misailovic S, Sidiroglou S, Rinard MC. Dancing with uncertainty. In SPLASH 2012: RACES 2012 - Proceedings of the 2012 ACM Workshop on Relaxing Synchronization for Multicore and Manycore Scalability. 2012. p. 51-60. (SPLASH 2012: RACES 2012 - Proceedings of the 2012 ACM Workshop on Relaxing Synchronization for Multicore and Manycore Scalability). https://doi.org/10.1145/2414729.2414738
Misailovic, Sasa ; Sidiroglou, Stelios ; Rinard, Martin C. / Dancing with uncertainty. SPLASH 2012: RACES 2012 - Proceedings of the 2012 ACM Workshop on Relaxing Synchronization for Multicore and Manycore Scalability. 2012. pp. 51-60 (SPLASH 2012: RACES 2012 - Proceedings of the 2012 ACM Workshop on Relaxing Synchronization for Multicore and Manycore Scalability).
@inproceedings{ed62ba40dc304fda81704bed474b5bf2,
title = "Dancing with uncertainty",
abstract = "We present Dubstep, a novel system that uses the find transform-navigate approach to automatically explore new parallelization opportunities in already parallelized (fullysynchronized) programs by opportunistically relaxing synchronization primitives. This set of transformations generates a space of alternative, possibly non-deterministic, parallel programs with varying performance and accuracy characteristics. The freedom to generate parallel programs whose output may differ (within statistical accuracy bounds) from the output of the original program enables a significantly larger optimization space. Dubstep then searches this space to find a parallel program that will, with high likelihood, produce outputs that are acceptably close to the outputs that the original, fully synchronized parallel program would have produced. Initial results from our benchmarked application show that Dubstep can generate acceptably accurate and efficient versions of a parallel program that occupy different positions in performance/accuracy trade off space.",
keywords = "Accuracy, Parallelization, Statistical test, Tradeoff",
author = "Sasa Misailovic and Stelios Sidiroglou and Rinard, {Martin C.}",
year = "2012",
month = "12",
day = "1",
doi = "10.1145/2414729.2414738",
language = "English (US)",
isbn = "9781450316323",
series = "SPLASH 2012: RACES 2012 - Proceedings of the 2012 ACM Workshop on Relaxing Synchronization for Multicore and Manycore Scalability",
pages = "51--60",
booktitle = "SPLASH 2012",

}

TY - GEN

T1 - Dancing with uncertainty

AU - Misailovic, Sasa

AU - Sidiroglou, Stelios

AU - Rinard, Martin C.

PY - 2012/12/1

Y1 - 2012/12/1

N2 - We present Dubstep, a novel system that uses the find transform-navigate approach to automatically explore new parallelization opportunities in already parallelized (fullysynchronized) programs by opportunistically relaxing synchronization primitives. This set of transformations generates a space of alternative, possibly non-deterministic, parallel programs with varying performance and accuracy characteristics. The freedom to generate parallel programs whose output may differ (within statistical accuracy bounds) from the output of the original program enables a significantly larger optimization space. Dubstep then searches this space to find a parallel program that will, with high likelihood, produce outputs that are acceptably close to the outputs that the original, fully synchronized parallel program would have produced. Initial results from our benchmarked application show that Dubstep can generate acceptably accurate and efficient versions of a parallel program that occupy different positions in performance/accuracy trade off space.

AB - We present Dubstep, a novel system that uses the find transform-navigate approach to automatically explore new parallelization opportunities in already parallelized (fullysynchronized) programs by opportunistically relaxing synchronization primitives. This set of transformations generates a space of alternative, possibly non-deterministic, parallel programs with varying performance and accuracy characteristics. The freedom to generate parallel programs whose output may differ (within statistical accuracy bounds) from the output of the original program enables a significantly larger optimization space. Dubstep then searches this space to find a parallel program that will, with high likelihood, produce outputs that are acceptably close to the outputs that the original, fully synchronized parallel program would have produced. Initial results from our benchmarked application show that Dubstep can generate acceptably accurate and efficient versions of a parallel program that occupy different positions in performance/accuracy trade off space.

KW - Accuracy

KW - Parallelization

KW - Statistical test

KW - Tradeoff

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

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

U2 - 10.1145/2414729.2414738

DO - 10.1145/2414729.2414738

M3 - Conference contribution

AN - SCOPUS:84872101189

SN - 9781450316323

T3 - SPLASH 2012: RACES 2012 - Proceedings of the 2012 ACM Workshop on Relaxing Synchronization for Multicore and Manycore Scalability

SP - 51

EP - 60

BT - SPLASH 2012

ER -