Partial evaluation applied to numerical computation

ABSTRACT

There have been many demonstrations that the expressive power of Lisp can greatly simplify the process of writing numerical programs, but at the cost of reduced performance.[10][16] I show that by coupling Lisp's abstract, expressive style of programming with a compiler that uses partial evaluation, data abstractions can be eliminated at compile time, producing extremely high-performance code. For an important class of numerical programs, partial evaluation achieves order-of-magnitude speed-ups over conventional Lisp compilation technology. This approach has proven to be especially effective when used in conjunction with schedulers for VLIW and highly pipelined architectures, because the elimination of data structures and procedural abstractions exposes the low-level parallelism inherent in a computation.

REFERENCES

• 1: Harold Abelson, The Bifurcation Interpreter: A Step Towards the Automatic Analysis of Dynamical Systems, Massachusetts Institute of Technology, Cambridge, MA, 1989
• 2: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 3: Andrew Berlin, A Compilation Strategy for Numerical Programs Based on Partial Evaluation, Massachusetts Institute of Technology, Cambridge, MA, 1989
• 4: Anders Bondorf amd Olivier D~uvy, 'Automatic Autoprojection of Recuzsive Equations with Global Variables and Abstract Data Types~, DIKU research report 90/04, University of Copenhagen, Denmark, January 1990.
• 5: BjzIner, D., Ershov, A. P., and Jones, N. D., (eds.), Partial Evaluation and Mixed Computation, North Holland, 1988.
• 6: William H. Burge, 'An Optimizing Techniques for High Level Programming Languages", IBM Thomas J. Watson Research Center Report RC5834 (~25271), Yorktown Heights, New York, February 1976.
• 7: Ollvler Danvy, 'Semantics-Directed Compilation of Non-Linear Patterns', Technical Report 303, Indian~ University, Bloomongton, IN., January 1990.
• 8: Andrew Berlin , Daniel Weise, Compiling Scientific Code Using Partial Evaluation, Massachusetts Institute of Technology, Cambridge, MA, 1989
• 9: John R. Ellis, Bulldog: a compiler for VLSI architectures, MIT Press, Cambridge, MA, 1986
• 10: Gerald Jay Sussman , Matthew Halfant, Tutorial: abstraction in numerical methods, Proceedings of the 1988 ACM conference on LISP and functional programming, p.1-7, July 25-27, 1988, Snowbird, Utah, United States [doi>10.1145/62678.62679]
• 11: Neil D. 3ones, Carsten K. Gomard, Anders Bondorf, Olivier Danvy, Torben JE. Mogensen: 'A Serf-Applicable Partial Evaluator for the Lambda-Calculus', proceedings of the IEEE Computer Society 1990 International Conference on Compurer Languages, New Orleans, Louisiana, USA (March 12-15, 1990)
• 12: Henryk Jam Komorowskl, ~A Specifics. tion of an Abstract Prolog Machine &nd its application to Partial Evaluation'. Linkoping Studies in Science and Technology Dissertations, No. 69., 1981, Linkopink University
• 13: L. Robert Morris, "Automatic generation of time efficient digital signal processing 8oftwaref IEEE Tranzactionz on Acoustics, Speech, and Signal Processing, Vol. ASSP-25, No. 1, pps. 74-79, February 1977.
• 14: Laurence Nagel, SPICE~: A Computer Program to Simulate Semiconductor Cir. cults, Electronics Research Laboratory Report No. ERE.MS, O, University of California, Berkeley, May 1975.
• 15: David A. Padua , Michael J. Wolfe, Advanced compiler optimizations for supercomputers, Communications of the ACM, v.29 n.12, p.1184-1201, Dec. 1986 [doi>10.1145/7902.7904]
• 16: Gerald Roylance, Expressing mathematical subroutines constructively, Proceedings of the 1988 ACM conference on LISP and functional programming, p.8-13, July 25-27, 1988, Snowbird, Utah, United States [doi>10.1145/62678.62680]
• 17: R. Schooler, PARTIAL EVALUATION AS A MEANS OF LANGUAGE EXTENSIBILITY, Massachusetts Institute of Technology, Cambridge, MA, 1984
• 18: Philip Wadler, Listlessness is better than laziness: Lazy evaluation and garbage collection at compile-time, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.45-52, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802020]
• 19: Weise, Daniel, "Graphs as an Intermediate Representation for Partial Evaluation~, Computer Systems Laboratory, Stanford University, Submitted for publication, March 1990.
• 20: Feng Zhao, An {\it bf O(N)} Algorithm for Three-Dimensional N-body Simulations, Massachusetts Institute of Technology, Cambridge, MA, 1987

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: LISP

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Pipeline processors**

  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers; Optimization

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Algorithms, Design, Languages, Performance