research-article

Efficiently speeding up sequential computation through the n-way programming model

Authors:

Romain E. Cledat,

Santosh PandeAuthors Info & Claims

OOPSLA '11: Proceedings of the 2011 ACM international conference on Object oriented programming systems languages and applications

Pages 537 - 554

https://doi.org/10.1145/2048066.2048109

Published: 22 October 2011 Publication History

Abstract

With core counts on the rise, the sequential components of applications are becoming the major bottleneck in performance scaling as predicted by Amdahl's law. We are therefore faced with the simultaneous problems of occupying an increasing number of cores and speeding up sequential sections. In this work, we reconcile these two seemingly incompatible problems with a novel programming model called N-way. The core idea behind N-way is to benefit from the algorithmic diversity available to express certain key computational steps. By simultaneously launching in parallel multiple ways to solve a given computation, a runtime can just-in-time pick the best (for example the fastest) way and therefore achieve speedup.

Previous work has demonstrated the benefits of such an approach but has not addressed its inherent waste. In this work, we focus on providing a mathematically sound learning-based statistical model that can be used by a runtime to determine the optimal balance between resources used and benefits obtainable through N-way. We further describe a dynamic culling mechanism to further reduce resource waste.

We present abstractions and a runtime support to cleanly encapsulate the computational-options and monitor their progress. We demonstrate a low-overhead runtime that achieves significant speedup over a range of widely used kernels. Our results demonstrate super-linear speedups in certain cases.

References

[1]

J. Ansel, Y. L. Wong, C. Chan, M. Olszewski, A. Edelman, and S. Amarasinghe. Language and compiler support for auto-tuning variable-accuracy algorithms. In CGO '11. IEEE Computer Society, 2011.

Digital Library

[2]

K. Asanovic et al. The landscape of parallel computing research: A view from berkeley. Technical Report UCB/EECS-2006--183, EECS Department, University of California, Berkeley, Dec 2006.

[3]

E. D. Berger, T. Yang, T. Liu, and G. Novark. Grace: safe multithreaded programming for C/C+. In OOPSLA '09, pages 81--96, New York, NY, USA, 2009. ACM.

Digital Library

[4]

J. Cachopo and A. Rito-Silva. Versioned boxes as the basis for memory transactions. Sci. Comput. Program., 63(2):172--185, 2006.

Digital Library

[5]

CLANG: A C family frontend for LLVM. http://clang.llvm.org/, 2010.

[6]

R. Cledat, T. Kumar, J. Sreeram, and S. Pande. Opportunistic computing: A new paradigm for scalable realism on many cores. In HotPar 2009: 1st USENIX Workshop on Hot Topics in Parallelism. USENIX, 2009.

Digital Library

[7]

R. Cledat and S. Pande. Energy efficiency via the n-way model. In PESPMA 2010, in conjunction with ISCA. ACM, 2010.

[8]

B. Cox, D. Evans, A. Filipi, J. Rowanhill, W. Hu, J. Davidson, J. Knight, A. Nguyen-tuong, and J. Hiser. N-variant systems: A secretless framework for security through diversity. In In Proceedings of the 15th USENIX Security Symposium, pages 105--120, 2006.

Digital Library

[9]

Dimacs benchmarks. http://tinyurl.com/myj2m7, 2009.

[10]

Y. Hamadi, S. Jabbour, and L. Sais. Manysat: Solver description. Technical Report MSR-TR-2008--83, Microsoft Research, May 2008.

[11]

T. Harris and K. Fraser. Language support for lightweight transactions. In OOPSLA '03: Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, pages 388--402, New York, NY, USA, 2003. ACM Press.

Digital Library

[12]

M. D. Hill and M. R. Marty. Amdahl's law in the multicore era. IEEE COMPUTER, 2008.

Digital Library

[13]

Intel haswell. http://tinyurl.com/28dxp67, 2010.

[14]

Intel shows 48-core 'datacentre on a chip'. http://tinyurl.com/2fyhejo, 2010.

[15]

S. K. Iyer, J. Jain, M. R. Prasad, D. Sahoo, and T. Sidle. Error detection using BMC in a parallel environment. In CHARME, pages 354--358, 2005.

Digital Library

[16]

C. F. Joerg. The Cilk System for Parallel Multithreaded Computing. PhD thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, Massachusetts, Jan. 1996. Available as MIT Laboratory for Computer Science Technical Report MIT/LCS/TR-701.

Digital Library

[17]

K. Knobe. Ease of use with concurrent collections (CnC). In HotPar 2009: 1st USENIX Workshop on Hot Topics in Parallelism. USENIX, 2009.

Digital Library

[18]

J. J. Kuffner Jr. and S. M. Lavalle. RRT-connect: An efficient approach to single-query path planning. In Proc. IEEE Int. Conf. Robot. Autom. (ICRA), pages 995--1001, 2000.

[19]

M. Kulkarni, K. Pingali, B. Walter, G. Ramanarayanan, K. Bala, and L. P. Chew. Optimistic parallelism requires abstractions. In PLDI '07, pages 211--222, 2007.

Digital Library

[20]

M. Luby and W. Ertel. Optimal parallelization of las vegas algorithms. In STACS '94, pages 463--474. Springer, 1994.

Digital Library

[21]

S. Misailovic, S. Sidiroglou, H. Hoffmann, and M. Rinard. Quality of service profiling. In Proceedings of the 32nd ACM/IEEE International Conference on Software Engineering - Volume 1, ICSE '10, pages 25--34, New York, NY, USA, 2010. ACM.

Digital Library

[22]

M. Mitzenmacher and E. Upfal. Probability and Computing. Cambridge University Press, 2005.

Digital Library

[23]

R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995.

Digital Library

[24]

D. Patterson. The trouble with multicore. http://spectrum.ieee.org/computing/software/the-trouble-with-multicore/%, July 2010.

Digital Library

[25]

G. Reinelt. TSPLIB - a traveling salesman problem library. In ORSA Journal on Computing, volume 3, pages 376--384, 1991.

[26]

M. Rinard. Probabilistic accuracy bounds for fault-tolerant computations that discard tasks. In Proceedings of the 20th annual international conference on Supercomputing, ICS '06, pages 324--334, New York, NY, USA, 2006. ACM.

Digital Library

[27]

B. Salamat, T. Jackson, A. Gal, and M. Franz. Orchestra: intrusion detection using parallel execution and monitoring of program variants in user-space. In EuroSys '09: Proceedings of the 4th ACM European conference on Computer systems, pages 33--46, New York, NY, USA, 2009. ACM.

Digital Library

[28]

B. Selman, H. Kautz, and B. Cohen. Local search strategies for satisfiability testing. In DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 521--532, 1995.

[29]

TomLab. CPLEX parameters interface. http://tomopt.com/docs/cplexug/tomlab_cplex014.php, March 2010.

[30]

O. Trachsel and T. Gross. A platform for competitive execution. In PESPMA 2008, in conjunction with ISCA. ACM, 2008.

[31]

O. Trachsel and T. R. Gross. Variant-based competitive parallel execution of sequential programs. In CF '10: Proceedings of the 7th ACM international conference on Computing frontiers, pages 197--206, New York, NY, USA, 2010. ACM.

Digital Library

[32]

M. Tygert. A fast algorithm for computing minimal-norm solutions to underdetermined systems of linear equations. May 2009.

[33]

V. Vazirani. Approximation Algorithms. Springer, 2001.

Digital Library

[34]

M. Wall. GAlib. http://lancet.mit.edu/ga/, 2009.

[35]

C. M. Wintersteiger, Y. Hamadi, and L. Moura. A concurrent portfolio approach to smt solving. In CAV '09, pages 715--720, Berlin, Heidelberg, 2009. Springer-Verlag.

Digital Library

Cited By

Qiu JSun XSabet AZhao ZSherwood TBerger EKozyrakis C(2021)Scalable FSM parallelization via path fusion and higher-order speculationProceedings of the 26th ACM International Conference on Architectural Support for Programming Languages and Operating Systems10.1145/3445814.3446705(887-901)Online publication date: 19-Apr-2021
https://dl.acm.org/doi/10.1145/3445814.3446705
Prabhu PBeard SApostolakis SZaks AAugust DEvripidou SStenström PO'Boyle M(2018)MemoDynProceedings of the 27th International Conference on Parallel Architectures and Compilation Techniques10.1145/3243176.3243193(1-12)Online publication date: 1-Nov-2018
https://dl.acm.org/doi/10.1145/3243176.3243193
Hauswirth MAzadmanesh MChurch LGabriel RHirschfeld RMasuhara H(2017)The entangled strands of time in software developmentProceedings of the 3rd ACM SIGPLAN International Workshop on Programming Experience10.1145/3167107(11-16)Online publication date: 22-Oct-2017
https://dl.acm.org/doi/10.1145/3167107
Show More Cited By

Index Terms

Efficiently speeding up sequential computation through the n-way programming model
1. Computing methodologies
  1. Parallel computing methodologies
    1. Parallel programming languages
2. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language features
      2. Language types
        Parallel programming languages

Recommendations

Efficiently speeding up sequential computation through the n-way programming model
OOPSLA '11

With core counts on the rise, the sequential components of applications are becoming the major bottleneck in performance scaling as predicted by Amdahl's law. We are therefore faced with the simultaneous problems of occupying an increasing number of ...
Study of parallel programming models on computer clusters with Intel MIC coprocessors

Coprocessors based on the Intel Many Integrated Core MIC Architecture have been adopted in many high-performance computer clusters. Typical parallel programming models, such as MPI and OpenMP, are supported on MIC processors to achieve the parallelism. ...
A MultiGPU Performance-Portable Solution for Array Programming Based on Kokkos
ARRAY 2023: Proceedings of the 9th ACM SIGPLAN International Workshop on Libraries, Languages and Compilers for Array Programming

Today, multiGPU nodes are widely used in high-performance computing and data centers. However, current programming models do not provide simple, transparent, and portable support for automatically targeting multiple GPUs within a node on application ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

OOPSLA '11: Proceedings of the 2011 ACM international conference on Object oriented programming systems languages and applications

October 2011

1104 pages

ISBN:9781450309400

DOI:10.1145/2048066

General Chair:
Cristina Videira Lopes
University of California, Irvine, USA
,
Program Chair:
Kathleen Fisher
Tufts University, USA

ACM SIGPLAN Notices Volume 46, Issue 10
OOPSLA '11
October 2011
1063 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/2076021
Issue’s Table of Contents

Copyright © 2011 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: 22 October 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SPLASH '11

Sponsor:

SIGPLAN

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

October 22 - 27, 2011

Oregon, Portland, USA

Acceptance Rates

Overall Acceptance Rate 268 of 1,244 submissions, 22%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
362
Total Downloads

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

Reflects downloads up to 23 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Qiu JSun XSabet AZhao ZSherwood TBerger EKozyrakis C(2021)Scalable FSM parallelization via path fusion and higher-order speculationProceedings of the 26th ACM International Conference on Architectural Support for Programming Languages and Operating Systems10.1145/3445814.3446705(887-901)Online publication date: 19-Apr-2021
https://dl.acm.org/doi/10.1145/3445814.3446705
Prabhu PBeard SApostolakis SZaks AAugust DEvripidou SStenström PO'Boyle M(2018)MemoDynProceedings of the 27th International Conference on Parallel Architectures and Compilation Techniques10.1145/3243176.3243193(1-12)Online publication date: 1-Nov-2018
https://dl.acm.org/doi/10.1145/3243176.3243193
Hauswirth MAzadmanesh MChurch LGabriel RHirschfeld RMasuhara H(2017)The entangled strands of time in software developmentProceedings of the 3rd ACM SIGPLAN International Workshop on Programming Experience10.1145/3167107(11-16)Online publication date: 22-Oct-2017
https://dl.acm.org/doi/10.1145/3167107
Ravichandran KPande S(2013)MultiverseACM SIGPLAN Notices10.1145/2544173.250952548:10(533-552)Online publication date: 29-Oct-2013
https://dl.acm.org/doi/10.1145/2544173.2509525
Ravichandran KPande SHosking AEugster PLopes C(2013)MultiverseProceedings of the 2013 ACM SIGPLAN international conference on Object oriented programming systems languages & applications10.1145/2509136.2509525(533-552)Online publication date: 29-Oct-2013
https://dl.acm.org/doi/10.1145/2509136.2509525
Qiu JSun XSabet AZhao ZSherwood TBerger EKozyrakis C(2021)Scalable FSM parallelization via path fusion and higher-order speculationProceedings of the 26th ACM International Conference on Architectural Support for Programming Languages and Operating Systems10.1145/3445814.3446705(887-901)Online publication date: 19-Apr-2021
https://dl.acm.org/doi/10.1145/3445814.3446705

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