iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://unpaywall.org/10.1007/S10766-013-0266-5
Cost-Directed Refactoring for Parallel Erlang Programs | International Journal of Parallel Programming Skip to main content
Springer Nature Link
Log in

Cost-Directed Refactoring for Parallel Erlang Programs

  • Published:
International Journal of Parallel Programming Aims and scope Submit manuscript

Abstract

This paper presents a new programming methodology for introducing and tuning parallelism in Erlang programs, using source-level code refactoring from sequential source programs to parallel programs written using our skeleton library, Skel. High-level cost models allow us to predict with reasonable accuracy the parallel performance of the refactored program, enabling programmers to make informed decisions about which refactorings to apply. Using our approach, we demonstrate easily obtainable, significant and scalable speedups of up to 21 on a 24-core machine over the sequential code.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5

Similar content being viewed by others

Notes

  1. Our skeleton implementations can be found at https://github.com/ParaPhrase/skel.

References

  1. Cesarini, F., Thompson, S.: ERLANG Programming, 1st edn. O’Reilly Media, Inc., Sebastopol, CA (2009)

    MATH  Google Scholar 

  2. Cole, M.: Bringing skeletons out of the closet: a pragmatic manifesto for skeletal parallel programming. Parallel Comput. 30(3), 389–406 (2004)

    Article  Google Scholar 

  3. Li, H., Thompson, S.: A Comparative Study of Refactoring Haskell and Erlang Programs. SCAM 2006, pp. 197–206. IEEE (2006)

  4. Aronis, S., Sagonas, K.: On using Erlang for parallelization: experience from parallelizing dialyzer. In: Loidl, H.-W. (ed.) Trends in Functional Programming 2012 (TFP 2012). Springer, St Andrews (2012)

  5. Aronis, S., Papaspyrou, N., Roukounaki, K., Sagonas, K., Tsiouris, Y., Venetis, I.: A scalability benchmark suite for Erlang/OTP. In: Proceedings of 11th ACM SIGPLAN Workshop on Erlang Copenhagen, Denmark. pp. 33–42. ACM. NY, USA (2012)

  6. Opdyke, W.: Refactoring object-oriented frameworks. PhD Thesis, Department of Computer Science, University of Illinois at Urbana-Champaign, Champaign, IL, USA (1992)

  7. Burstall, R.M., Darlington, J.: A transformation system for developing recursive programs. J. ACM 24(1), 44–67 (1977)

    Article  MATH  MathSciNet  Google Scholar 

  8. Li, H., Thompson, S.: Let’s Make Refactoring Tools User Extensible! The Fifth ACM Workshop on Refactoring Tools. Rapperswill, Switzerland (2012)

  9. Li, H., Thompson, S.: A domain-specific language for scripting refactorings in Erlang. In: Proceedings 15th International Conference on Fund. Approaches to Software Engineering, pp. 501–515. (2012)

  10. Caromel, D., Leyton, M.: Fine tuning algorithmic skeletons. In: Kermarrec, A.-M., Bougé, L., Priol, T. (eds.) Euro-Par, vol. 4641. Lecture Notes in Computer Science. Springer, Rennes (2007)

  11. Pelagatti, S.: Structured Development of Parallel Programs. Taylor and Francis, London (1999)

    Google Scholar 

  12. Aldinucci, M.: Automatic program transformation: the meta tool for skeleton-based languages. In: Gorlatch, S., Lengauer, C. (eds.) Constructive Methods for Parallel Programming, Advances in Computation: Theory and Practice, chap. 5, pp. 59–78. Nova Science, NY (2002)

  13. Aldinucci, M., Coppola, M., Danelutto, M.: Rewriting Skeleton Programs: How to Evaluate the Data-Parallel Stream-Parallel Tradeoff, pp. 44–58. CMPP, Germany (1998)

  14. Partsch, H., Steinbruggen, R.: Program transformation systems. ACM Comput. Surv. 15(3), 199–236 (1983)

    Article  MathSciNet  Google Scholar 

  15. Mens, T., Tourwé, T.: A survey of software refactoring. IEEE Trans. Softw. Eng. 30(2), 126–139 (2004)

    Article  Google Scholar 

  16. Burstall, R.M., Darlington, J.: A transformation system for developing recursive programs. J. ACM 24(1), 44–67 (1977)

    Article  MATH  MathSciNet  Google Scholar 

  17. Hammond, K., Aldinucci, M., Brown, C., Cesarini, F., Danelutto, M., Gonzalez-Velez, H., Kilpatrick, P., Keller, R., Natschlager, T., Shainer, G.: The ParaPhrase Project: Parallel Patterns for Adaptive Heterogeneous Multicore Systems. FMCO, Turin (2012)

  18. Hammond, K., Berthold, J., Loogen, R.: Automatic skeletons in template Haskell. Parallel Process. Lett. 13(3), 413–424 (2003)

    Article  MathSciNet  Google Scholar 

  19. Sheard, T., Jones, S.P.: Template meta-programming for Haskell. SIGPLAN Not. 37, 60–75 (2002)

    Article  Google Scholar 

  20. Loogen, R., Ortega-Mallén, Y., Peña-Marí, R.: Parallel functional programming in Eden. J. Funct. Program. 15(3), 431–475 (2005)

    Article  MATH  Google Scholar 

  21. Wloka, J., Sridharan, M., Tip, F.: Refactoring for Reentrancy. ESEC/FSE ’09, pp.. 173–182. ACM, Amsterdam (2009)

  22. Dig, D.: A refactoring approach to parallelism. IEEE Softw. 28, 17–22 (2011)

    Article  Google Scholar 

  23. Brown, C., Li, H., Thompson, S.: An expression processor: a case study in refactoring Haskell programs. In: Eleventh Symposium on Trends in Functional Programming (2010)

  24. Brown, C., Loidl, H., Hammond, K.: Paraforming: forming Haskell programs using novel refactoring rechniques. In: 12th Symposium on Trends in Functional Programming, Spain (2011)

  25. Brown, C., Hammond, K., Danelutto, M., Kilpatrick, P.: A language-independent parallel refactoring framework. In: Proceedings of the Fifth Workshop on Refactoring Tools (WRT ’12), pp. 54–58. ACM, New York, USA (2012)

  26. Matsuzaki, K., Iwasaki, H., Emoto, K., Hu, Z.: A Library of Constructive Skeletons for Sequential Style of Parallel Programming. InfoScale ’06. Article 13, Hong Kong. ACM, NY, USA (2006)

  27. Bacci, B., Danelutto, M., Orlando, S., Pelagatti, S., Vanneschi, M.: \(\text{ P }^3\)L: a structured high level program language and its structured support. Concurr. Pract. Exp. 7(3), 225–255 (1995)

    Article  Google Scholar 

  28. Botorog, G.H., Kuchen, H.: Skil: An imperative language with algorithmic skeletons for efficient distributed programming. In: Proceedings of the 5th International Symposium on High Performance Distributed Computing (HPDC ’96), pp. 243–252. IEEE Computer Society Press, Syracuse, NY, USA (1996)

  29. Cole, M.: Algorithmic skeletons: structured management of parallel computations. In: Research Monographs in Par. and Distrib. Computing. Pitman (1989)

  30. Darlington, J., Guo, Y., Jing, Y., To, H.W.: Skeletons for Structured Parallel Composition. In: Proceedings of the 15th Symposium on Princ. and Prac. of Parallel Programming (1995)

  31. Aldinucci, M., Danelutto, M.: Stream Parallel Skeleton Optimization. In: Proceedings of the International Conference on Parallel and Distributed Computing and Systems (PDCS), pp. 955–962. IASTED, ACTA Press, Cambridge, MA, USA (1999)

  32. Aldinucci, M., Gorlatch, S., Lengauer, C., Pelagatti, S.: Towards parallel programming by transformation: the FAN skeleton framework. Parallel Algorithm Appl. 16(2–3), 87–121 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  33. Gorlatch, S., Wedler, C., Lengauer, C.: Optimization rules for programming with collective operations. In: Proceedings of the 13th International Symposium on Par. Proceedings and the 10th Symposium on Par. and Dist. Proc., pp. 492–499, Washington, DC, USA (1999)

  34. Skillicorn, D.B., Cai, W.: A cost calculus for parallel functional programming. J. Parallel Distrib. Comput. 28(1), 65–83 (1995)

    Article  MATH  Google Scholar 

  35. Li, H., Thompson, S.: Formalisation of Haskell refactorings. Trends Funct. Program. (2005)

Download references

Acknowledgments

This work has been supported by EU Framework 7 Grants IST-288570 “ParaPhrase” (http://www.paraphrase-ict.eu), and IST-248828 “ADVANCE” (http://www.project-advance.eu).

Author information

Authors and Affiliations

  1. School of Computer Science, University of St Andrews, Saint Andrews, Scotland, UK

    Christopher Brown, Kevin Hammond & Archibald Elliott

  2. Department of Computer Science, University of Pisa, Pisa, Italy

    Marco Danelutto

  3. School of Electronics, Electrical Engineering and Computer Science, Queen’s University, Belfast, UK

    Peter Kilpatrick

Authors
  1. Christopher Brown
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Marco Danelutto
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Kevin Hammond
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Peter Kilpatrick
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Archibald Elliott
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Christopher Brown.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Brown, C., Danelutto, M., Hammond, K. et al. Cost-Directed Refactoring for Parallel Erlang Programs. Int J Parallel Prog 42, 564–582 (2014). https://doi.org/10.1007/s10766-013-0266-5

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10766-013-0266-5

Keywords

Search

Navigation