More Web Proxy on the site http://driver.im/

tutorial

Pattern Candidate Discovery and Parallelization Techniques

Authors:

Tamás KozsikAuthors Info & Claims

IFL '17: Proceedings of the 29th Symposium on the Implementation and Application of Functional Programming Languages

Article No.: 1, Pages 1 - 26

https://doi.org/10.1145/3205368.3205369

Published: 30 August 2017 Publication History

Abstract

Parallel computations in a program can be expressed conveniently, at a high level of abstraction, using parallel patterns such as task farm, pipeline or divide-and-conquer. In order to transform a sequential program into a pattern-based parallel one, the software developer may want to apply refactoring transformations on it. This tutorial explains a methodology to perform tool supported parallelization of programs by presenting how to use a specific static source code analysis and transformation system for Erlang. A key element of the approach is pattern candidate discovery, a static analysis technique to identify code fragments that can be refactored into a parallel pattern.

References

[1]

Marco Aldinucci, Massimo Coppola, and Marco Danelutto. 1998. Rewriting Skeleton Programs: How to Evaluate the Data-Parallel Stream-Parallel Tradeoff. In Proc of CMPP: Intl. Workshop on Constructive Methods for Parallel Programming, S. Gorlatch (Ed.). Fakultät für mathematik und informatik, Uni. Passau, Germany, Germany, 44--58. http://www.di.unipi.it/~aldinuc/paper_files/1998_transf_cmpp.pdf

[2]

Joe Armstrong. 2013. Programming Erlang. The Pragmatic Bookshelf, 548 pages, ISBN 978.1-93778-533-6, NC, USA.

[3]

Stavros Aronis, Nikolaos Papaspyrou, Katerina Roukounaki, Konstantinos Sagonas, Yiannis Tsiouris, and Ioannis E. Venetis. 2012. A Scalability Benchmark Suite for Erlang/OTP. In Proc. of 11th ACM SIGPLAN workshop on Erlang. ACM, New York, NY, USA, 33--42.

Digital Library

[4]

Stavros Aronis and Konstantinos Sagonas. 2013. On Using Erlang for Parallelization. In Trends in Functional Programming, Hans-Wolfgang Loidl and Ricardo Peña (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 295--310.

Digital Library

[5]

Olivier Boudeville, Francesco Cesarini, Natalia Chechina, Kenneth Lundin, Nikolaos Papaspyrou, Konstantinos Sagonas, Simon Thompson, Phil Trinder, and Ulf Wiger. 2013. Trends in Functional Programming: 13th International Symposium, TFP 2012, St. Andrews, UK, June 12-14, 2012, Revised Selected Papers. Springer Berlin Heidelberg, Berlin, Heidelberg, Chapter RELEASE: A High-Level Paradigm for Reliable Large-Scale Server Software, 263--278.

Digital Library

[6]

István Bozó, Viktoria Fördős, Dániel Horpácsi, Zoltán Horváth, Tamás Kozsik, Judit Kőszegi, and Melinda Tóth. 2015. Refactorings to Enable Parallelization. In Trends in Functional Programming, Jurriaan Hage and Jay McCarthy (Eds.). Springer International Publishing, Berlin, Heidelberg, 104--121.

[7]

István Bozó, Viktoria Fördős, Zoltán Horváth, Melinda Tóth, Dániel Horpácsi, Tamás Kozsik, Judit Kőszegi, Adam Barwell, Christopher Brown, and Kevin Hammond. 2014. Discovering Parallel Pattern Candidates in Erlang. In Proceedings of the Thirteenth ACM SIGPLAN Workshop on Erlang (Erlang '14). ACM, New York, NY, USA, 13--23.

Digital Library

[8]

I. Bozó, D. Horpácsi, Z. Horváth, R. Kitlei, J. Kőszegi, M. Tejfel, and M Tóth. 2011. RefactorErl - Source Code Analysis and Refactoring in Erlang. In Proceedings of the 12th Symposium on Programming Languages and Software Tools. Proceedings of the Estonian Academy of Sciences, Tallin, Estonia, 138--148.

[9]

Christopher Brown, Marco Danelutto, Kevin Hammond, Peter Kilpatrick, and Archibald Elliott. 2014. Cost-Directed Refactoring for Parallel Erlang Programs. International Journal of Parallel Programming 42, 4 (01 Aug 2014), 564--582.

Digital Library

[10]

C. Brown, V. Janjic, K. Hammond, H. Schöner, K. Idrees, and C. Glass. 2014. Agricultural Reform: More Efficient Farming Using Advanced Parallel Refactoring Tools. In 2014 22nd Euromicro International Conference on Parallel, Distributed, and Network-Based Processing. IEEE, NJ, USA, 36--43.

Digital Library

[11]

Christopher Brown, Hans-Wolfgang Loidl, and Kevin Hammond. 2012. ParaForming: Forming Parallel Haskell Programs Using Novel Refactoring Techniques. In Trends in Functional Programming, Ricardo Peña and Rex Page (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 82--97.

Digital Library

[12]

R. M. Burstall and John Darlington. 1977. A Transformation System for Developing Recursive Programs. J. ACM 24, 1 (1977), 44--67.

Digital Library

[13]

Murray Cole. 1991. Algorithmic Skeletons: Structured Management of Parallel Computation. MIT Press, Cambridge, MA, USA.

Digital Library

[14]

Murray Cole. 2004. Bringing Skeletons out of the Closet: A Pragmatic Manifesto for Skeletal Parallel Programming. Parallel Comput. 30, 3 (March 2004), 389--406.

Digital Library

[15]

J. Darlington, Y. Guo, Y. Jing, and H. W. To. 1995. Parallel Skeletons for Structured Composition. In Proc. of the 15th Symposium on Principles and Practice of Parallel Programming. ACM New York, NY, USA, 19--28.

Digital Library

[16]

Danny Dig. 2011. A Refactoring Approach to Parallelism. IEEE Softw. 28 (2011), 17--22. Issue 1.

Digital Library

[17]

Danny Dig, John Marrero, and Michael D. Ernst. 2009. Refactoring Sequential Java Code for Concurrency via Concurrent Libraries. In Proceedings of the 31st International Conference on Software Engineering (ICSE '09). IEEE Computer Society, Washington, DC, USA, 397--407.

Digital Library

[18]

Danny Dig, John Marrero, and Michael D. Ernst. 2011. How Do Programs Become More Concurrent: A Story of Program Transformations. In Proceedings of the 4th International Workshop on Multicore Software Engineering (IWMSE '11). ACM, New York, NY, USA, 43--50.

Digital Library

[19]

Faculty of Informatics ELTE. 2017. RefactorErl Home Page. (2017). http://plc.inf.elte.hu/erlang/.

[20]

Faculty of Informatics ELTE. 2017. Wiki page of the ParaPhrase Refactoring Tool for Erlang. (2017). http://pnyf.inf.elte.hu/trac/refactorerl/wiki/parte.

[21]

B. Freisleben and T. Kielmann. 1995. Automated transformation of sequential divide-and-conquer algorithms into parallel programs. Computing and Informatics 14 (1995), 579--596. Issue 6.

[22]

Clemens Hammacher, Kevin Streit, Sebastian Hack, and Andreas Zeller. 2009. Profiling Java Programs for Parallelism. In Proc. IWMSE '09. IEEE Computer Society Washington, DC, USA, 49--55.

Digital Library

[23]

Kevin Hammond, Marco Aldinucci, Christopher Brown, Francesco Cesarini, Marco Danelutto, Horacio González-Vélez, Peter Kilpatrick, Rainer Keller, Michael Rossbory, and Gilad Shainer. 2013. The ParaPhrase Project: Parallel Patterns for Adaptive Heterogeneous Multicore Systems. In Formal Methods for Components and Objects. Lecture Notes in Computer Sscience, Vol. 7542. Springer, Berlin, Heidelberg, 218--236.

[24]

Fred Hebert. 2013. Learn You Some Erlang for Great Good! No Starch Press, San Francisco, CA 94103 USA.

Digital Library

[25]

Dániel Horpácsi, Judit Kőszegi, and Simon Thompson. 2016. Towards Trustworthy Refactoring in Erlang, In Fourth International Workshop on Verification and Program Transformation, Geoff Hamilton, Alexei Lisitsa, and Andrei P. Nemytykh (Eds.). Electronic Proceedings in Theoretical Computer Science 216, 83--103. http://kar.kent.ac.uk/56750/

[26]

Tamás Kozsik, Melinda Tóth, István Bozó, and Zoltán Horváth. 2017. Static analysis for divide-and-conquer pattern discovery. Computing and Informatics 35 (2017), 764--791. Issue 4.

[27]

Tamás Kozsik, Melinda Tóth, and István Bozó. 2018. Free the Conqueror! Refactoring divide-and-conquer functions. Future Generation Computer Systems 79, Part 2 (2018), 687 -- 699.

Digital Library

[28]

Lapedo. 2014. Available at http://lapedo.weebly.com/. (2014).

[29]

Huiqing Li and Simon Thompson. 2008. Tool support for refactoring functional programs. In WRT '08: Proceedings of the 2nd Workshop on Refactoring Tools. ACM, New York, NY, USA, 1--4.

Digital Library

[30]

M. Logan, E. Merritt, and R. Carlsson. 2010. Erlang and OTP in Action. Manning Publications Co., ISBN 9781933988788., New York, USA.

Digital Library

[31]

Rita Loogen. 2012. Eden -- Parallel Functional Programming with Haskell. In Central European Functional Programming School, Viktória Zsók, Zoltán Horváth, and Rinus Plasmeijer (Eds.). Lecture Notes in Computer Science, Vol. 7241. Springer, Berlin Heidelberg, 142--206.

Digital Library

[32]

Jonathan Mak, Karl-Filip Faxén, Sverker Janson, and Alan Mycroft. 2010. Estimating and Exploiting Potential Parallelism by Source-level Dependence Profiling. In Proceedings of the 16th International Euro-Par Conference on Parallel Processing: Part I (EuroPar'10). Springer-Verlag, Berlin, Heidelberg, 26--37. http://dl.acm.org/citation.cfm?id=1887695.1887700

Digital Library

[33]

Shane A. Markstrum and Robert M. Fuhrer. 2009. Extracting Concurrency via Refactoring in X10, in Proceedings of the 3rd ACM Workshop on Refactoring Tools. (2009). http://refactoring.info/WRT09/#program

[34]

Shane A. Markstrum, Robert M. Fuhrer, and Todd D. Millstein. 2009. Towards Concurrency Refactoring for x10. In Proceedings of the 14th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP '09). ACM, New York, NY, USA, 303--304.

Digital Library

[35]

Simon Marlow. 2012. Parallel and Concurrent Programming in Haskell. Central European Functional Programming School 7241 (2012), 339--401. http://community.haskell.org/~simonmar/papers/par-tutorial-cefp-2012.pdf

Digital Library

[36]

Greg Michaelson, Andrew Ireland, and Peter King. 1997. Towards a Skeleton Based Parallelising Compiler for SML. In Proceedings of 9th International Workshop on Implementation of Functional Languages. IFL'97, St. Andrews, Scotland, UK, 539--546.

[37]

K. Molitorisz. 2013. Pattern-Based Refactoring Process of Sequential Source Code. In Software Maintenance and Reengineering (CSMR), 2013 17th European Conference on. IEEE, Genova, Italy, 357--360.

Digital Library

[38]

Korbinian Molitorisz, Jochen Schimmel, and Frank Otto. 2012. Automatic Parallelization Using Autofutures. In Proceedings of the 2012 International Conference on Multicore Software Engineering, Performance, and Tools (MSEPT'12). Springer-Verlag, Berlin, Heidelberg, 78--81.

Digital Library

[39]

Steven S. Muchnick. 1997. Advanced Compiler Design and Implementation. Morgan Kaufmann Publishers, Inc., Burlington, Massachusetts.

Digital Library

[40]

Flemming Nielson, Hanne R. Nielson, and Chris Hankin. 1999, corrected 2005. Principles of Program Analysis. Springer, Berlin, Heidelberg.

Digital Library

[41]

William F. Opdyke. 1992. Refactoring Object-Oriented Frameworks. Ph.D. Dissertation. Department of Computer Science, University of Illinois at Urbana-Champaign, Champaign, IL, USA.

Digital Library

[42]

M. Pitidis and K. Sagonas. 2011. Purity in Erlang. Proc. 22nd Int'l Conf. on Implementation and Application of Functional Languages, Lecture Notes in Computer Science,Springer Berlin, Heidelberg 6647 (2011), 137--152.

Digital Library

[43]

Skel Tutorial. 2014. Available at http://chrisb.host.cs.st-andrews.ac.uk/skel-test-master/tutorial/bin/tutorial.html. (2014).

[44]

The ParaPhrase project. 2014. http://www.paraphrase-ict.eu. (2014).

[45]

Melinda Tóth and István Bozó. 2012. Static Analysis of Complex Software Systems Implemented in Erlang. Central European Functional Programming School 7241 (2012), 440--498.

Digital Library

[46]

AHG University. 2014. Multi Agent System. (2014). https://github.com/ParaPhraseAGH/erlang-mas/tree/0.1.

[47]

Uppsala University. 2017. The DIALYZER: a DIscrepancy AnaLYZer for ERlang programs. (2017). http://www.it.uu.se/research/group/hipe/dialyzer.

[48]

Jan Wloka, Manu Sridharan, and Frank Tip. 2009. Refactoring for Reentrancy. In ESEC/FSE '09. ACM, Amsterdam, 173--182.

Digital Library

[49]

WP2. 2013. Final Pattern Definition Report. Technical Report. University of Pisa. http://paraphrase-ict.eu/Deliverables/deliverable-2.5/deliverable-2.5-report/view

[50]

WP2. 2013. Initial Implementation of Application-Specific Patterns. Technical Report. University of Pisa. http://paraphrase-ict.eu/Deliverables/deliverable-2.6/deliverable-2.6-report/view

[51]

V. Zsók, Z. Hernyák, and Z. Horváth. 2006. Designing Distributed Computational Skeletons in D-Clean and D-Box. Central European Functional Programming School, Lecture Notes in Computer Science, Springer 4146 (2006), 223--256.

Cited By

Erdei ZTóth MBozó I(2024)Identifying Concurrent Behaviours in Erlang Legacy SystemsActa Cybernetica10.14232/actacyb.29952926:3(405-429)Online publication date: 20-Mar-2024
https://doi.org/10.14232/actacyb.299529
Erdei ZBozó ITóth M(2024)Transforming Erlang Server Applications2024 IEEE 3rd Conference on Information Technology and Data Science (CITDS)10.1109/CITDS62610.2024.10791346(1-6)Online publication date: 26-Aug-2024
https://doi.org/10.1109/CITDS62610.2024.10791346

Index Terms

Pattern Candidate Discovery and Parallelization Techniques
1. Software and its engineering
  1. Software creation and management
    1. Software development techniques
  2. Software notations and tools
    1. Software maintenance tools

Recommendations

Discovering parallel pattern candidates in Erlang
Erlang '14: Proceedings of the Thirteenth ACM SIGPLAN workshop on Erlang

The ParaPhrase Refactoring Tool for Erlang PaRTE provides automatic, comprehensive and reliable pattern candidate discovery to locate parallelisable components in Erlang programs. It uses semi-automatic and semantics-preserving program transformations ...
A language-independent parallel refactoring framework
WRT '12: Proceedings of the Fifth Workshop on Refactoring Tools

Recent trends towards increasingly parallel computers mean that there needs to be a seismic shift in programming practice. The time is rapidly approaching when most programming will be for parallel systems. However, most programming techniques in use ...
A pattern-supported parallelization approach
PMAM '13: Proceedings of the 2013 International Workshop on Programming Models and Applications for Multicores and Manycores

In the embedded systems domain a trend towards multi-and many-core processors is evident. For the exploitation of these additional processing elements parallel software is inevitable. The pattern-supported parallelization approach, which is introduced ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

IFL '17: Proceedings of the 29th Symposium on the Implementation and Application of Functional Programming Languages

August 2017

126 pages

ISBN:9781450363433

DOI:10.1145/3205368

Editor:
Nicolas Wu
University of Bristol

Copyright © 2017 Owner/Author.

Permission to make digital or hard copies of part or all 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 third-party components of this work must be honored. For all other uses, contact the Owner/Author.

In-Cooperation

ACM: Association for Computing Machinery
The University of Bristol: The University of Bristol
ERLANG: Erlang Solutions Ltd.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 30 August 2017

Check for updates

Author Tags

Qualifiers

Tutorial
Research
Refereed limited

Conference

IFL 2017

IFL 2017: 29th Symposium on the Implementation and Application of Functional Programming Languages

August 30 - September 1, 2017

Bristol, United Kingdom

Acceptance Rates

IFL '17 Paper Acceptance Rate 9 of 16 submissions, 56%;

Overall Acceptance Rate 19 of 36 submissions, 53%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
52
Total Downloads

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

Reflects downloads up to 31 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Erdei ZTóth MBozó I(2024)Identifying Concurrent Behaviours in Erlang Legacy SystemsActa Cybernetica10.14232/actacyb.29952926:3(405-429)Online publication date: 20-Mar-2024
https://doi.org/10.14232/actacyb.299529
Erdei ZBozó ITóth M(2024)Transforming Erlang Server Applications2024 IEEE 3rd Conference on Information Technology and Data Science (CITDS)10.1109/CITDS62610.2024.10791346(1-6)Online publication date: 26-Aug-2024
https://doi.org/10.1109/CITDS62610.2024.10791346

View Options

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