research-article

Dancing with uncertainty

Authors:

Sasa Misailovic,

Stelios Sidiroglou,

Martin C. RinardAuthors Info & Claims

RACES '12: Proceedings of the 2012 ACM workshop on Relaxing synchronization for multicore and manycore scalability

Pages 51 - 60

https://doi.org/10.1145/2414729.2414738

Published: 21 October 2012 Publication History

Abstract

We present Dubstep, a novel system that uses the find-transform-navigate paradigm to automatically explore new parallelization opportunities in already parallelized (fully-synchronized) 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.

References

[1]

J. Ansel, C. Chan, Y. Wong, M. Olszewski, Q. Zhao, A. Edelman, and S. Amarasinghe. Petabricks: A language and compiler for algorithmic choice. PLDI, 2009.

Digital Library

[2]

W. Baek and T. Chilimbi. Green: A framework for supporting energy-conscious programming using controlled approximation. PLDI, 2010.

Digital Library

[3]

M. Berry, D. Chen, P. Koss, D. Kuck, S. Lo, Y. Pang, L. Pointer, R. Roloff, A. Sameh, E. Clementi, et al. The perfect club benchmarks: Effective performance evaluation of supercomputers. International Journal of High Performance Computing Applications, 3(3):5--40, 1989.

Digital Library

[4]

M. Carbin, D. Kim, S. Misailovic, and M. Rinard. Proving acceptability properties of relaxed nondeterministic approximate programs. PLDI, 2012.

Digital Library

[5]

M. Carbin and M. Rinard. Automatically Identifying Critical Input Regions and Code in Applications. ISSTA, 2010.

Digital Library

[6]

S. Chaudhuri, S. Gulwani, R. Lublinerman, and S. Navidpour. Proving Programs Robust. FSE, 2011.

Digital Library

[7]

C. Ding, X. Shen, K. Kelsey, C. Tice, R. Huang, and C. Zhang. Software behavior oriented parallelization. PLDI, 2007.

Digital Library

[8]

W. Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301), 1963.

[9]

H. Hoffmann, S. Sidiroglou, M. Carbin, S. Misailovic, A. Agarwal, and M. Rinard. Dynamic knobs for responsive power-aware computing. ASPLOS, 2011.

Digital Library

[10]

C. Kirsch, H. Payer, H. Röck, and A. Sokolova. Performance, scalability, and semantics of concurrent FIFO queues. PODC, 2011.

[11]

J. Meng, S. Chakradhar, and A. Raghunathan. Best-Effort Parallel Execution Framework for Recognition and Mining Applications. IPDPS, 2009.

Digital Library

[12]

J. Meng, A. Raghunathan, S. Chakradhar, and S. Byna. Exploiting the Forgiving Nature of Applications for Scalable Parallel Execution. IPDPS, 2010.

[13]

S. Misailovic, D. Kim, and M. Rinard. Automatic parallelization with statistical accuracy bounds. Technical Report MIT-CSAIL-TR-2010-007, MIT, 2010.

[14]

S. Misailovic, D. Kim, and M. Rinard. Parallelizing sequential programs with statistical accuracy tests. Technical Report MIT-CSAIL-TR-2010-038, MIT, 2010.

[15]

S. Misailovic, D. Kim, and M. Rinard. Parallelizing sequential programs with statistical accuracy tests. ACM Transactions on Embedded Computing, Special Issue on Probabilistic Embedded Computing (to appear), 2013.

[16]

S. Misailovic, D. Roy, and M. Rinard. Probabilistically Accurate Program Transformations. SAS, 2011.

Digital Library

[17]

S. Misailovic, S. Sidiroglou, H. Hoffmann, and M. Rinard. Quality of service profiling. ICSE, 2010.

Digital Library

[18]

L. Renganarayana, V. Srinivasan, R. Nair, D. Prener, and C. Blundell. Relaxing synchronization for performance and insight. Technical Report RC25256, IBM, 2011.

[19]

M. Rinard. Probabilistic accuracy bounds for fault-tolerant computations that discard tasks. ICS, 2006.

Digital Library

[20]

M. Rinard. Using early phase termination to eliminate load imbalances at barrier synchronization points. OOPSLA, 2007.

Digital Library

[21]

M. Rinard. A lossy, synchronization-free, race-full, but still acceptably accurate parallel space-subdivision tree construction algorithm. Technical Report MIT-CSAIL-TR-2012-005, MIT, 2012.

[22]

S. Rul, H. Vandierendonck, and K. De Bosschere. A dynamic analysis tool for finding coarse-grain parallelism. HiPEAC Industrial Workshop, 2008.

[23]

A. Sampson, W. Dietl, E. Fortuna, D. Gnanapragasam, L. Ceze, and D. Grossman. Enerj: Approximate data types for safe and general low-power computation. PLDI, 2011.

Digital Library

[24]

S. Sidiroglou, S. Misailovic, H. Hoffmann, and M. Rinard. Managing Performance vs. Accuracy Trade-offs With Loop Perforation. FSE '11.

[25]

J. Sorber, A. Kostadinov, M. Garber, M. Brennan, M. D. Corner, and E. D. Berger. Eon: a language and runtime system for perpetual systems. SenSys, 2007.

Digital Library

[26]

G. Tournavitis, Z. Wang, B. Franke, and M. O'Boyle. Towards a holistic approach to auto-parallelization: integrating profile-driven parallelism detection and machine-learning based mapping. PLDI, 2009.

Digital Library

[27]

A. Udupa, K. Rajan, and W. Thies. Alter: Leveraging breakable dependences for parallelization. PLDI, 2011.

Digital Library

[28]

D. Ungar, D. Kimelman, and S. Adams. Inconsistency robustness for scalability in interactive concurrent-update in-memory MOLAP cubes. Technical report, IBM TJ Watson, 2011.

[29]

A. Wald. Sequential analysis. John Wiley and Sons, 1947.

[30]

Z. Zhu, S. Misailovic, J. Kelner, and M. Rinard. Randomized accuracy-aware program transformations for efficient approximate computations. POPL, 2012.

Digital Library

Cited By

Misailovic S(2022)Accuracy-Aware CompilersApproximate Computing Techniques10.1007/978-3-030-94705-7_7(177-214)Online publication date: 3-Jan-2022
https://doi.org/10.1007/978-3-030-94705-7_7
Jiang HZhang HTang XGovindaraj VSampson JKandemir MZhang DFreund SYahav E(2021)Fluid: a framework for approximate concurrency via controlled dependency relaxationProceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation10.1145/3453483.3454042(252-267)Online publication date: 19-Jun-2021
https://dl.acm.org/doi/10.1145/3453483.3454042
Sharif HSrivastava PHuzaifa MKotsifakou MJoshi KSarita YZhao NAdve VMisailovic SAdve S(2019)ApproxHPVM: a portable compiler IR for accuracy-aware optimizationsProceedings of the ACM on Programming Languages10.1145/33606123:OOPSLA(1-30)Online publication date: 10-Oct-2019
https://dl.acm.org/doi/10.1145/3360612
Show More Cited By

Index Terms

Dancing with uncertainty
1. Software and its engineering
  1. Software notations and tools
    1. Compilers

Recommendations

Parallelizing Sequential Programs with Statistical Accuracy Tests
Special Section on Probabilistic Embedded Computing

We present QuickStep, a novel system for parallelizing sequential programs. Unlike standard parallelizing compilers (which are designed to preserve the semantics of the original sequential computation), QuickStep is instead designed to generate (...
Dual-level parallelism for ab initio molecular dynamics: Reaching teraflop performance with the CPMD code

We show teraflop performance of the fully featured ab initio molecular dynamics code CPMD on an IBM pSeries 690 cluster. A mixed distributed-memory, coarse-grained parallel approach using the MPI library and shared-memory, fine-grained parallelism using ...
Parallel Quicksort Using Fetch-And-Add

A parallelization of the Quicksort algorithm that is suitable for execution on a shared memory multiprocessor with an efficient implementation of the fetch-and-add operation is presented. The partitioning phase of Quicksort, which has been considered a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

RACES '12: Proceedings of the 2012 ACM workshop on Relaxing synchronization for multicore and manycore scalability

October 2012

74 pages

ISBN:9781450316323

DOI:10.1145/2414729

Program Chairs:
Andrew P. Black
Portland State University, United States
,
Theo D'Hondt
Vrije Universiteit Brussel, Belgium
,
Doug Kimelman
IBM Thomas J. Watson Research Center, United States
,
Martin Rinard
MIT CSAIL, United States
,
David Ungar
IBM Thomas J. Watson Research Center, United States

Copyright © 2012 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 21 October 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SPLASH '12

Sponsor:

SIGPLAN

SPLASH '12: Conference on Systems, Programming, and Applications: Software for Humanity

October 21, 2012

Arizona, Tucson, USA

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
175
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Misailovic S(2022)Accuracy-Aware CompilersApproximate Computing Techniques10.1007/978-3-030-94705-7_7(177-214)Online publication date: 3-Jan-2022
https://doi.org/10.1007/978-3-030-94705-7_7
Jiang HZhang HTang XGovindaraj VSampson JKandemir MZhang DFreund SYahav E(2021)Fluid: a framework for approximate concurrency via controlled dependency relaxationProceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation10.1145/3453483.3454042(252-267)Online publication date: 19-Jun-2021
https://dl.acm.org/doi/10.1145/3453483.3454042
Sharif HSrivastava PHuzaifa MKotsifakou MJoshi KSarita YZhao NAdve VMisailovic SAdve S(2019)ApproxHPVM: a portable compiler IR for accuracy-aware optimizationsProceedings of the ACM on Programming Languages10.1145/33606123:OOPSLA(1-30)Online publication date: 10-Oct-2019
https://dl.acm.org/doi/10.1145/3360612
Stitt GCampbell DChen JShrivastava A(2019)PANDORA: a parallelizing approximation-discovery framework (WIP paper)Proceedings of the 20th ACM SIGPLAN/SIGBED International Conference on Languages, Compilers, and Tools for Embedded Systems10.1145/3316482.3326345(198-202)Online publication date: 23-Jun-2019
https://dl.acm.org/doi/10.1145/3316482.3326345
Fernando VFranques AAbadal SMisailovic STorrellas JBahar IHerlihy MWitchel ELebeck A(2019)ReplicaProceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems10.1145/3297858.3304033(849-863)Online publication date: 4-Apr-2019
https://dl.acm.org/doi/10.1145/3297858.3304033
Jordan MBrandalero MMalfatti GOliveira GLorenzon Ada Silva BCarro LRutzig MBeck A(2019)Data clustering for efficient approximate computingDesign Automation for Embedded Systems10.1007/s10617-019-09228-zOnline publication date: 9-Nov-2019
https://doi.org/10.1007/s10617-019-09228-z
Khatamifard SAkturk IKarpuzcu U(2018)On Approximate Speculative Lock ElisionIEEE Transactions on Multi-Scale Computing Systems10.1109/TMSCS.2017.27734884:2(141-151)Online publication date: 1-Apr-2018
https://doi.org/10.1109/TMSCS.2017.2773488
Aponte-Moreno AMoncada ARestrepo-Calle FPedraza C(2018)A review of approximate computing techniques towards fault mitigation in HW/SW systems2018 IEEE 19th Latin-American Test Symposium (LATS)10.1109/LATW.2018.8347241(1-6)Online publication date: Mar-2018
https://doi.org/10.1109/LATW.2018.8347241
Ascia GCatania VMonteleone SPalesi MPatti DJose J(2018)Approximate Wireless Networks-on-Chip2018 Conference on Design of Circuits and Integrated Systems (DCIS)10.1109/DCIS.2018.8681491(1-6)Online publication date: Nov-2018
https://doi.org/10.1109/DCIS.2018.8681491
Pinto GCanino ACastor FXu GLiu YRosu GDi Penta MNguyen T(2017)Understanding and overcoming parallelism bottlenecks in ForkJoin applicationsProceedings of the 32nd IEEE/ACM International Conference on Automated Software Engineering10.5555/3155562.3155657(765-775)Online publication date: 30-Oct-2017
https://dl.acm.org/doi/10.5555/3155562.3155657
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents