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

Article

JFlow: practical refactorings for flow-based parallelism

Authors:

Ralph E. JohnsonAuthors Info & Claims

ASE '13: Proceedings of the 28th IEEE/ACM International Conference on Automated Software Engineering

Pages 202 - 212

https://doi.org/10.1109/ASE.2013.6693080

Published: 11 November 2013 Publication History

Publisher Site Get Access

Abstract

Emerging applications in the domains of recognition, mining and synthesis (RMS); image and video processing; data warehousing; and automatic financial trading admit a particular style of parallelism termed flow-based parallelism. To help developers exploit flow-based parallelism, popular parallel libraries such as Groovy's GPars, Intel's TBB Flow Graph and Microsoft's TPL Dataflow have begun introducing many new and useful constructs. However, to reap the benefits of such constructs, developers must first use them. This involves refactoring their existing sequential code to incorporate these constructs - a manual process that overwhelms even experts. To alleviate this burden, we introduce a set of novel analyses and transformations targeting flow-based parallelism. We implemented these ideas in JFlow, an interactive refactoring tool integrated into the Eclipse IDE. We used JFlow to parallelize seven applications: four from a previously known benchmark and three from a suite of large open source projects. JFlow, with minimal interaction from the developer, can successfully parallelize applications from the aforementioned domains with good performance (offering up to 3.45x speedup on a 4-core machine) and is fast enough to be used interactively as part of a developer's workflow.

References

[1]

J. P. Morrison, Flow-Based Programming: A New Approach to Application Development, 2nd ed. CreateSpace, 2010.

Digital Library

[2]

T. G. Mattson, B. A. Sanders, and B. L. Massingill, Patterns for Parallel Programming. Addison-Wesley Professional, 2004.

Digital Library

[3]

E.-G. Kim and M. Snir, "Resources on Parallel Patterns," http://www.cs.uiuc.edu/homes/snir/PPP/, 2011.

[4]

"GPars (Groovy Parallel Systems)," http://gpars.codehaus.org/.

[5]

Intel Corporation, "Intel Threading Building Blocks," http://www.threadingbuildingblocks.org/.

[6]

"TPL Dataflow," http://msdn.microsoft.com/en-us/devlabs/gg585582.

[7]

E. Reed, N. Chen, and R. Johnson, "Expressing Pipeline Parallelism Using TBB Constructs: A Case Study on What Works and What Doesn't," in TMC, 2011.

Digital Library

[8]

M. Kim, H. Kim, and C.-K. Luk, "Prospector: A Dynamic Data-Dependence Profiler To Help Parallel Programming," in HotPar, 2010.

[9]

A. J. Dorta, C. Rodriguez, F. d. Sande, and A. Gonzalez-Escribano, "The OpenMP Source Code Repository," in Proceedings of the 13th Euromicro Conference on Parallel, Distributed and Network-Based Processing, 2005, pp. 244-250.

Digital Library

[10]

M. Wolfe, High Performance Compilers for Parallel Computing. Addison-Wesley, 1996.

Digital Library

[11]

M. Sridharan, S. Chandra, J. Dolby, S. J. Fink, and E. Yahav, Alias Analysis for Object-Oriented Programs. Springer Berlin Heidelberg, 2013, vol. 7850, pp. 196-232.

Digital Library

[12]

M. Naik, A. Aiken, and J. Whaley, "Effective Static Race Detection for Java," in PLDI '06.

Digital Library

[13]

R. Vallée-Rai, P. Co, E. Gagnon, L. Hendren, P. Lam, and V. Sundaresan, "Soot - a Java bytecode optimization framework," in Proceedings of the 1999 conference of the Centre for Advanced Studies on Collaborative research, ser. CASCON '99. IBM Press, 1999, pp. 13.

Digital Library

[14]

A. Milanova, A. Rountev, and B. G. Ryder, "Parameterized object sensitivity for points-to analysis for java," ACM Trans. Softw. Eng. Methodol., vol. 14, pp. 1-41, January 2005.

Digital Library

[15]

M. Sharir and A. Pnueli, Two approaches to interprocedural data flow analysis. Englewood Cliffs, NJ: Prentice-Hall, 1981, ch. 7, pp. 189-234.

[16]

T. B. Sheridan, "Function allocation: algorithm, alchemy or apostasy?" Int. J. Hum.-Comput. Stud., vol. 52, pp. 203-216, February 2000.

Digital Library

[17]

M. Lux and S. A. Chatzichristofis, "Lire: Lucene Image retrieval - An Extensible Java CBIR library," in MM '08.

Digital Library

[18]

H. Vandierendonck, S. Rul, and K. De Bosschere, "The Paralax Infrastructure: Automatic Parallelization with a Helping Hand," in PACT '10.

Digital Library

[19]

V. Sarkar, "Automatic partitioning of a program dependence graph into parallel tasks," IBM J. Res. Dev., vol. 35, no. 5-6, pp. 779-804, Sep. 1991.

Digital Library

[20]

J. Ferrante, K. J. Ottenstein, and J. D. Warren, "The program dependence graph and its use in optimization," ACM Trans. Program. Lang. Syst., vol. 9, pp. 319-349, July 1987.

Digital Library

[21]

W. Thies, V. Chandrasekhar, and S. Amarasinghe, "A Practical Approach to Exploiting Coarse-Grained Pipeline Parallelism in C Programs," in MICRO '07.

Digital Library

[22]

J. C. Jenista, Y. h. Eom, and B. C. Demsky, "OoOJava: Software Out-of-order Execution," in PPoPP '11.

Digital Library

[23]

K. Knobe, "Ease of use with concurrent collections (CnC)," in HotPar '09, Berkeley, CA, USA, 2009.

Digital Library

[24]

M. A. Suleman, M. K. Qureshi, Khubaib, and Y. N. Patt, "Feedback-Directed Pipeline Parallelism," in PACT '10, 2010.

Digital Library

[25]

"T.J. Watson Libraries for Analysis (WALA)," http://wala.sf.net.

[26]

M. Naik, "Effective Static Race Detection for Java," Ph.D. dissertation, Stanford University, 2008.

Digital Library

[27]

B. G. Ryder, W. A. Landi, P. A. Stocks, S. Zhang, and R. Altucher, "A Schema for Interprocedural Modification Side-Effect Analysis With Pointer Aliasing," ACM Trans. Program. Lang. Syst., vol. 23, no. 2, pp. 105-186, Mar. 2001.

Digital Library

[28]

S. Negara, R. K. Karmani, and G. Agha, "Inferring Ownership Transfer for Efficient Message Passing," in PPoPP '11.

Digital Library

[29]

D. G. Clarke, J. M. Potter, and J. Noble, "Ownership types for flexible alias protection," in OOPSLA '98.

Digital Library

[30]

C. Bienia, "Benchmarking modern multiprocessors," Ph.D. dissertation, Princeton University, January 2011.

Digital Library

[31]

E. Bodden, A. Sewe, J. Sinschek, H. Oueslati, and M. Mezini, "Taming Reflection: Aiding Static Analysis in the Presence of Reflection and Custom Class Loaders," in ICSE '11.

Digital Library

[32]

W. M. Johnston, J. R. P. Hanna, and R. J. Millar, "Advances in Dataflow Programming Languages," ACM Comput. Surv., vol. 36, pp. 1-34, March 2004.

Digital Library

[33]

A. Davis and R. Keller, "Data Flow Program Graphs," Computer, vol. 15, no. 2, pp. 26 - 41, feb 1982.

Digital Library

[34]

W. W. Wadge and E. A. Ashcroft, LUCID, The Dataflow Programming Language. San Diego, CA, USA: Academic Press Professional, Inc., 1985.

Digital Library

[35]

Arvind, K. P. Gostelow, and W. Plouffe, "An Asynchronous Programming Language and Computing Machine," University of California Irvine, Tech. Rep., 1978.

[36]

National Instruments, "What is NI Labview?" http://www.ni.com/labview/whatis/.

[37]

S. Matwin and T. Pietrzykowski, "PROGRAPH: A preliminary report," Computer Languages, vol. 10, no. 2, pp. 91 - 126, 1985.

Digital Library

[38]

W. Ackerman, "Data Flow Languages," Computer, vol. 15, no. 2, pp. 15-25, feb 1982.

Digital Library

[39]

J. P. Morrison, "Java Flow-Based Programming," http://sourceforge.net/projects/flow-based-pgmg.

[40]

I. Buck, T. Foley, D. Horn, J. Sugerman, K. Fatahalian, M. Houston, and P. Hanrahan, "Brook for GPUs: Stream Computing on Graphics Hardware," in SIGGRAPH '04.

Digital Library

[41]

W. Thies, M. Karczmarek, and S. P. Amarasinghe, "StreamIt: A Language for Streaming Applications," in CC '02.

Digital Library

[42]

U. J. Kapasi, S. Rixner, W. J. Dally, B. Khailany, J. H. Ahn, P. Mattson, and J. D. Owens, "Programmable stream processors," Computer, vol. 36, pp. 54-62, August 2003.

Digital Library

[43]

R. L. Bocchino, Jr., V. S. Adve, D. Dig, S. V. Adve, S. Heumann, R. Komuravelli, J. Overbey, P. Simmons, H. Sung, and M. Vakilian, "A Type and Effect System for Deterministic Parallel Java," in OOPSLA '09.

Digital Library

[44]

K. R. M. Leino, A. Poetzsch-Heffter, and Y. Zhou, "Using Data Groups to Specify and Check Side Effects," in PLDI '02.

Digital Library

[45]

J. M. Lucassen and D. K. Gifford, "Polymorphic Effect Systems," in POPL '88, New York, NY, USA.

Digital Library

[46]

N. Kellenberger, "Static Universe Type Inference," Master's thesis, ETH Zurich, 2005.

[47]

M. Niklaus, "Static universe type inference using a SAT-solver," Master's thesis, ETH Zurich, 2006.

[48]

M. Vakilian, D. Dig, R. Bocchino, J. Overbey, V. Adve, and R. Johnson, "Inferring Method Effect Summaries for Nested Heap Regions," in ASE '09, Washington, DC, USA.

Digital Library

[49]

S. Rul, H. Vandierendonck, and K. De Bosschere, "A Profile-Based Tool for Finding Pipeline Parallelism in Sequential Programs," Parallel Comput., vol. 36, pp. 531-551, September 2010.

Digital Library

[50]

G. Tournavitis and B. Franke, "Semi-Automatic Extraction and Exploitation of Hierarchical Pipeline Parallelism using Profiling Information," in PACT '10, New York, NY, USA.

Digital Library

[51]

M. Kim, H. Kim, and C.-K. Luk, "SD3: A Scalable Approach to Dynamic Data-Dependence Profiling," in Proceedings of the 2010 43rd Annual IEEE/ACM International Symposium on Microarchitecture, ser. MICRO '43. Washington, DC, USA: IEEE Computer Society, 2010, pp. 535-546.

Digital Library

[52]

S.-W. Liao, A. Diwan, R. P. Bosch, Jr., A. Ghuloum, and M. S. Lam, "SUIF Explorer: An Interactive and Interprocedural Parallelizer," in Proceedings of the seventh ACM SIGPLAN symposium on Principles and practice of parallel programming, ser. PPoPP '99. New York, NY, USA: ACM, 1999, pp. 37-48.

Digital Library

[53]

K. Kennedy, K. S. McKinley, and C. W. Tseng, "Interactive Parallel Programming using the ParaScope Editor," IEEE Trans. Parallel Distrib. Syst., vol. 2, pp. 329-341, July 1991.

Digital Library

[54]

D. Dig, J. Marrero, and M. D. Ernst, "Concurrencer: A Tool for Retrofitting Concurrency into Sequential Java Applications via Concurrent Libraries," in ICSE '09 (Companion).

[55]

D. Dig, M. Tarce, C. Radoi, M. Minea, and R. Johnson, "Relooper: Refactoring for Loop Parallelism in Java," in OOPSLA '09 (Companion), New York, NY, USA.

Digital Library

[56]

F. Kjolstad, D. Dig, G. Acevedo, and M. Snir, "Transformation for Class Immutability," in ICSE '11, New York, NY, USA.

Digital Library

Cited By

Wang EDang ZCohen MGrunske LWhalen M(2015)A message-passing architecture without public ids using send-to-behaviorProceedings of the 30th IEEE/ACM International Conference on Automated Software Engineering10.1109/ASE.2015.79(902-905)Online publication date: 9-Nov-2015
https://dl.acm.org/doi/10.1109/ASE.2015.79

Recommendations

JFlow: practical mostly-static information flow control
POPL '99: Proceedings of the 26th ACM SIGPLAN-SIGACT symposium on Principles of programming languages

A promising technique for protecting privacy and integrity of sensitive data is to statically check information flow within programs that manipulate the data. While previous work has proposed programming language extensions to allow this static checking,...
OpenMP for Networks of SMPs

In this paper, we present the first system that implements OpenMP on a network of shared-memory multiprocessors. This system enables the programmer to rely on a single, standard, shared-memory API for parallelization within a multiprocessor and between ...
SPMD OpenMP versus MPI on a IBM SMP for 3 Kernels of the NAS Benchmarks
ISHPC '02: Proceedings of the 4th International Symposium on High Performance Computing

Shared Memory Multiprocessors are becoming more popular since they are used to deploy large parallel computers. The current trend is to enlarge the number of processors inside such multiprocessor nodes. However a lot of existing applications are using ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ASE '13: Proceedings of the 28th IEEE/ACM International Conference on Automated Software Engineering

November 2013

765 pages

ISBN:9781479902156

General Chair:
Ewen Denney
SGT, NASA, Ames Research Center, Moffett Field
,
Program Chairs:
Tevfik Bultan
University of California, Santa Barbara
,
Andreas Zeller
Saarland University, Saarbrücken, Germany

Sponsors

NASA: National Aeronatics and Space Administration
SIGAI: ACM Special Interest Group on Artificial Intelligence
IEEE: IEEE Computer Society Technical Committee on Design Automation
SIGSOFT: ACM Special Interest Group on Software Engineering
Microsoft: Microsoft

Publisher

IEEE Press

Publication History

Published: 11 November 2013

Check for updates

Qualifiers

Article

Conference

ASE '13

Sponsor:

NASA
SIGAI
IEEE
SIGSOFT
Microsoft

ASE '13: Automated Software Engineering

November 11 - 15, 2013

CA, Silicon Valley, USA

Acceptance Rates

Overall Acceptance Rate 82 of 337 submissions, 24%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
33
Total Downloads

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

Reflects downloads up to 17 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Wang EDang ZCohen MGrunske LWhalen M(2015)A message-passing architecture without public ids using send-to-behaviorProceedings of the 30th IEEE/ACM International Conference on Automated Software Engineering10.1109/ASE.2015.79(902-905)Online publication date: 9-Nov-2015
https://dl.acm.org/doi/10.1109/ASE.2015.79

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