Space profiling for parallel functional programs

ABSTRACT

This paper presents a semantic space profiler for parallel functional programs. Building on previous work in sequential profiling, our tools help programmers to relate runtime resource use back to program source code. Unlike many profiling tools, our profiler is based on a cost semantics. This provides a means to reason about performance without requiring a detailed understanding of the compiler or runtime system. It also provides a specification for language implementers. This is critical in that it enables us to separate cleanly the performance of the application from that of the language implementation.

Some aspects of the implementation can have significant effects on performance. Our cost semantics enables programmers to understand the impact of different scheduling policies while hiding many of the details of their implementations. We show applications where the choice of scheduling policy has asymptotic effects on space use. We explain these use patterns through a demonstration of our tools. We also validate our methodology by observing similar performance in our implementation of a parallel extension of Standard ML.

REFERENCES

• 1: Shail Aditya, Arvind, Jan-Willem Maessen, and Lennart Augustsson. Semantics of pH: A parallel dialect of Haskell. Technical Report Computation Structures Group Memo 377, MIT, June 1995.
• 2: Andrew W. Appel, Bruce Duba, and David B. MacQueen. Profiling in the presence of optimization and garbage collection. Technical Report CS-TR-197-88, Princeton University, November 1988.
• 3: Arvind , Rishiyur S. Nikhil , Keshav K. Pingali, I-structures: data structures for parallel computing, ACM Transactions on Programming Languages and Systems (TOPLAS), v.11 n.4, p.598-632, Oct. 1989 [doi>10.1145/69558.69562]
• 4: Guy Blelloch , John Greiner, Parallelism in sequential functional languages, Proceedings of the seventh international conference on Functional programming languages and computer architecture, p.226-237, June 26-28, 1995, La Jolla, California, United States [doi>10.1145/224164.224210]
• 5: Guy E. Blelloch , John Greiner, A provable time and space efficient implementation of NESL, Proceedings of the first ACM SIGPLAN international conference on Functional programming, p.213-225, May 24-26, 1996, Philadelphia, Pennsylvania, United States
• 6: Guy E. Blelloch , Gary W. Sabot, Compiling collection-oriented languages onto massively parallel computers, Journal of Parallel and Distributed Computing, v.8 n.2, p.119-134, February 1990 [doi>10.1016/0743-7315(90)90087-6]
• 7: Guy E. Blelloch , Jonathan C. Hardwick , Jay Sipelstein , Marco Zagha , Siddhartha Chatterjee, Implementation of a portable nested data-parallel language, Journal of Parallel and Distributed Computing, v.21 n.1, p.4-14, April 1994 [doi>10.1006/jpdc.1994.1038]
• 8: Guy E. Blelloch , Phillip B. Gibbons , Yossi Matias, Provably efficient scheduling for languages with fine-grained parallelism, Journal of the ACM (JACM), v.46 n.2, p.281-321, March 1999 [doi>10.1145/301970.301974]
• 9: Robert D. Blumofe , Charles E. Leiserson, Space-Efficient Scheduling of Multithreaded Computations, SIAM Journal on Computing, v.27 n.1, p.202-229, Feb. 1998 [doi>10.1137/S0097539793259471]
• 10: Robert D. Blumofe , Charles E. Leiserson, Scheduling multithreaded computations by work stealing, Journal of the ACM (JACM), v.46 n.5, p.720-748, Sept. 1999 [doi>10.1145/324133.324234]
• 11: Manuel M. T. Chakravarty , Gabriele Keller, More types for nested data parallel programming, Proceedings of the fifth ACM SIGPLAN international conference on Functional programming, p.94-105, September 2000
• 12: Nathan Charles , Colin Runciman, An Interactive Approach to Profiling Parallel Functional Programs, Selected Papers from the 10th International Workshop on 10th International Workshop, p.20-37, September 09-11, 1998
• 13: Perry Cheng , Guy E. Blelloch, A parallel, real-time garbage collector, ACM SIGPLAN Notices, v.36 n.5, p.125-136, May 2001
• 14: Silvain Conchon , Fabrice Le Fessant, Jocaml: Mobile Agents for Objective-Caml, Proceedings of the First International Symposium on Agent Systems and Applications Third International Symposium on Mobile Agents, p.22, October 03-06, 1999
• 15: Robert Ennals. Adaptive Evaluation of Non-Strict Programs. PhD thesis, University of Cambridge, 2004.
• 16: Matthew Fluet , Nic Ford , Mike Rainey , John Reppy , Adam Shaw , Yingqi Xiao, Status report: the manticore project, Proceedings of the 2007 workshop on Workshop on ML, October 05-05, 2007, Freiburg, Germany [doi>10.1145/1292535.1292539]
• 17: Matthew Fluet , Mike Rainey , John Reppy, A scheduling framework for general-purpose parallel languages, Proceeding of the 13th ACM SIGPLAN international conference on Functional programming, September 20-28, 2008, Victoria, BC, Canada
• 18: Jörgen Gustavsson and David Sands. A foundation for space-safe transformations of call-by-need programs. In Proc. of Workshop on Higher Order Operational Techniques in Semantics, number volume 26 of Electronic Notes in Theoretical Computer Science, September 1999.
• 19: Kevin Hammond and Simon L. Peyton Jones. Profiling scheduling strategies on the GRIP multiprocessor. In Int. Workshop on the Parallel Implementation of Funct. Languages, pages 73-98, RWTH Aachen, Germany, September 1992.
• 20: Kevin Hammond, Hans-Wolfgang Loidl, and Andrew S. Partridge. Visualising Granularity in Parallel Programs: A Graphical Winnowing System for Haskell. In A. P. Wim Böhm and John T. Feo, editors, High Performance Functional Computing, pages 208--221, 1995.
• 21: Robin Milner , Mads Tofte , David Macqueen, The Definition of Standard ML, MIT Press, Cambridge, MA, 1997
• 22: John H. Reppy, Concurrent programming in ML, Cambridge University Press, New York, NY, 1999
• 23: Niklas Röjemo , Colin Runciman, Lag, drag, void and use—heap profiling and space-efficient compilation revisited, ACM SIGPLAN Notices, v.31 n.6, p.34-41, June 15, 1996
• 24: Mads Rosendahl, Automatic complexity analysis, Proceedings of the fourth international conference on Functional programming languages and computer architecture, p.144-156, September 11-13, 1989, Imperial College, London, United Kingdom [doi>10.1145/99370.99381]
• 25: Colin Runciman and David Wakeling. Heap profiling of lazy functional programs. J. Funct. Program., 3 (2): 217--245, 1993.
• 26: Colin Runciman and David Wakeling. Profiling Parallel Functional Computations (Without Parallel Machines). In Functional Programming, Glasgow '93, pages 236--251. Springer-Verlag, 1993.
• 27: David Sands. Calculi for Time Analysis of Functional Programs. PhD thesis, Department of Computing, Imperial College, University of London, September 1990.
• 28: Patrick M. Sansom , Simon L. Peyton Jones, Profiling Lazy Functional Programs, Proceedings of the 1992 Glasgow Workshop on Functional Programming, p.227-239, July 06-08, 1992
• 29: Patrick M. Sansom , Simon L. Peyton Jones, Time and space profiling for non-strict, higher-order functional languages, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.355-366, January 23-25, 1995, San Francisco, California, United States [doi>10.1145/199448.199531]
• 30: Zhong Shao , Andrew W. Appel, Space-efficient closure representations, Proceedings of the 1994 ACM conference on LISP and functional programming, p.150-161, June 27-29, 1994, Orlando, Florida, United States
• 31: Daniel Spoonhower, Guy E. Blelloch, Robert Harper, and Phillip B. Gibbons. Space profiling for parallel functional programs. Technical Report CMU-CS-08-110, Carnegie Mellon University, April 2008.
• 32: Stephen Weeks, Whole-program compilation in MLton, Proceedings of the 2006 workshop on ML, p.1-1, September 16-16, 2006, Portland, Oregon, USA [doi>10.1145/1159876.1159877]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Concurrent, distributed, and parallel languages

General Terms:
Languages, Measurement, Performance

Keywords:
cost semantics, parallelism, profiling, scheduling, standard ml