Hostname: page-component-586b7cd67f-rdxmf Total loading time: 0 Render date: 2024-11-25T00:46:32.488Z Has data issue: false hasContentIssue false
  • English
  • Français

A practical functional program for the CRAY X-MP*

Part of: JFP Research Articles

Published online by Cambridge University Press:  07 November 2008

James M. Boyle  and
Terence J. Harmer
James M. Boyle
Affiliation:
Mathematics and Computer Science Division, Argonne National Laboratory, Argonne, IL 60439, USA
Terence J. Harmer
Affiliation:
The Queen's University of Belfast, Department of Computer Science, Belfast BT7 INN, Northern Ireland
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

One can have all the advantages of functional programming – correctness, clarity, simplicity, and flexibility – without any sacrifice in performance, even for a scientifically significant computation on a supercomputer. Therefore, why use Fortran? We demonstrate parity – equality of speed and storage use – between a program generated automatically from a functional specification and a program written by hand in the procedural style. To our knowledge, this demonstration of parity is the first for a program that solves a scientifically significant problem – quasi-linear hyperbolic partial differential equations – on a scientifically interesting supercomputer – the CRAY X-MP. We use pure Lisp, including higher-order functions, to express the functional specification for the PDE solver. We designed this specification for maximal clarity and flexibility, rather than for efficiency. Nevertheless, we obtain a highly efficient program to solve the PDEs: automated program transformations put back the missing efficiency as they produce an executable Fortran program from the specification. The generated Fortran program vectorizes on the CRAY X-MP and runs about 4% faster than a handwritten Fortran program for the same problem. We describe the problem and the specification, and some of the problem-domain-specific and hardware-specific transformations that we use to obtain the high-efficiency program.

Type
Articles
Information
Journal of Functional Programming , Volume 2 , Issue 1 , January 1992 , pp. 81 - 126
Copyright
Copyright © Cambridge University Press 1992

References

Augustsson, L. and Johnsson, T. 1989. The Chalmers Lazy-ML compiler. Computer J., 32 (2): 127–41.CrossRefGoogle Scholar
Barth, P., Nikhil, R. S. and Arvind, 1991. M-Structures: Extending a parallel, non-strict, functional language with state. MIT Computation Structures Group Memo 327, MIT/Laboratory for Computer Science, Cambridge, MA, USA. (To appear in Proc. Functional Programming and Computer Architecture, Cambridge, MA, USA. (To appear in Proc. Functional Programming and Computer Architecture, Cambridge, MA (08 28–30 1991).)Google Scholar
Bird, R. and Wadler, P. 1988. Introduction to Functional Programming. Prentice-Hall, New York.Google Scholar
Bloss, A., Hudak, P. and Young, J. 1988. Code optimizations for lazy evaluation. Lisp and Symbolic Computation, 1: 147–64.CrossRefGoogle Scholar
Bloss, A., Hudak, P. and Young, J. 1989. An optimizing compiler for a modern functional language. Computer J., 32(2): 152–61.CrossRefGoogle Scholar
Boyle, J. M. 1970. A Transformational Component for Programming Language Grammar. ANL-7690, Argonne National Laboratory, Argonne, IL, USA (07).CrossRefGoogle Scholar
Boyle, J. M. 1980. Program adaptation and program transformation. In Ebert, R.Lueger, J., and Goecke, L. (editors), Practice in Software Adaptation and Maintenance, pp. 3–20, North-Holland, Amsterdam.Google Scholar
Boyle, J. M. and Muralidharan, M. N. 1984. Program reusability through program transformation. IEEE Trans. Software Eng., 10(5): 574–88 (09).CrossRefGoogle Scholar
Boyle, J. M. 1989. Abstract programming and program transformations – an approach to reusing programs. In Biggerstaff, T. J. and Perlis, A. J. (editors), Software Reusability, Volume I, pp. 361–413, Addison-Wesley, New York.Google Scholar
Boyle, J. M. and Harmer, T. J. 1991. Functional specifications for mathematical computations. In Moeller, B. (editor), Proc. IFIP TC2/WG2.1 Working Conf. on Construction Programs from Specifications, Pacific Grove, California (05 13–16), Elsevier, Amsterdam.Google Scholar
Burton, F. W. and Kollias, J. Y. G. 1989. Functional programming with quadtrees. IEEE Software, 6: 90–97 (01).CrossRefGoogle Scholar
Church, A. 1941. The Calculi of Lambda Conversion. Princeton University Press.Google Scholar
Culler, D. E., Sah, A., Schauser, K. E., von Eicken, T. and Wawrzynek, J. 1991. Fine-grain parallelism with minimal hardware support: A compiler-controlled threaded abstract machine. In 4th Int. Conf. on Architectural Support for Programming Languages and Operating Systems.Google Scholar
Dritz, K. W. and Boyle, J. M. 1987. Beyond ‘Speedup’: Performance Analysis of Parallel Programs. Argonne National Laboratory Technical Report ANL-87-7, Argonne, IL, USA (02).Google Scholar
Federal Coordinating Council for Science, Engineering and Technology. 1987. A research and development strategy for high performance computing. Executive Office of the President, Office of Science and Technology Policy, Washington, DC (Nov. 20).Google Scholar
Feo, J. T., Cann, D. and Oldehoeft, R. R. 1990. A report on the SISAL language project. J. Parallel and Distributed Computing (12).CrossRefGoogle Scholar
Field, A. J. and Harrison, P. G. 1988. Functional Programming, Addison-Wesley, New York.Google Scholar
Friedman, D. P. and Felleisen, M. 1986. The Little LISPer, Science Research Associates, Inc., Chicago, IL, USA.Google Scholar
Garbey, M. and Levine, D. 1990. Massively parallel computation of conservation laws. Parallel Computing, 16: 293–304.CrossRefGoogle Scholar
Harrison, L. and Padua, X. 1989. Parcel: Project for the automatic restructuring and concurrent evaluation of Lisp. In Proc. 1988 Int. Conf. on Supercomputing, pp. 527–38, ACM Press, New York.Google Scholar
Kelly, P. 1989. Functional Programming for Loosely-Coupled Multiprocessors, Pitman Publishing/MIT Press, London/Cambridge, MA, USA.Google Scholar
Kelsey, E. and Hudak, P. 1989. Realistic compilation by program transformation. In Proc. 16th ACM Symposium on Principles of Programming Languages (01).Google Scholar
Kranz, D. 1988. ORBIT: An Optimizing Compiler for Scheme. Yale University Technical Report YALEU/DCS7/RR-632, Yale University, New Haven, CT, USA.Google Scholar
Kranz, D., Kelsey, R., Rees, J., Hudak, P., Philbin, J., and Adams, N. 1986. ORBIT: An optimizing compiler for Scheme. SIGPLAN Notices, 21 (7) (07).Google Scholar
Nikhil, R. S. 1991. The parallel programming language Id and its compilation for parallel machines. In Proc. Workshop on Massive Parallelism, Amalfi, Italy. Academic Press, New York.Google Scholar
Nordstrom, M. 1978. LISP F3, Users Guide. Report, Datalogilaboratoriet, Uppsala University, Uppsala, Sweden (06).Google Scholar
Paige, R. and Koenig, S. 1982. Finite differencing of computable expression. ACM Trans. Programming Lang. and Syst., 4 (3): 402–54 (07).CrossRefGoogle Scholar
Peyton-Jones, S. L. 1987. The Implementation of Functional Programming Languages, Prentice-Hall, New York.Google Scholar
Wolfram, S. 1986. Theory and Applications of Cellular Automata, World Scientific, Singapore.Google Scholar
Submit a response

Discussions

No Discussions have been published for this article.