Copying operands versus copying results: A solution to the problem of large operands in FFP'S

ABSTRACT

In functional programming languages with reduction semantics, operators “use up” their operands to produce their results. This makes it difficult to execute efficiently certain computations, such as one in which several operators are applied—in succession or in parallel—to a large operand. The problem is that providing each operator with a separate copy of the large operand is a costly operation in most computer models. This paper proposes a solution to this problem in the context of a cellular computer that directly executes FFPs. The operators involved are applied in succession to the large operand, and only their results (with the exception of that of the last operator applied) need be moved. Providing each operator with a fresh copy of the large operand incurs no overhead in time. The proposed solution often allows one to avoid unproductive copying, and to suppress parallelism when it does not pay. The functional forms conditional, WHILE loop and construction are among the examples discussed. For example, when executing the conditional usually both the predicate and one of the “arms” of the conditional are applied to the operand. Since the result of the predicate computation is small, the overhead in the execution time of the conditional is negligible. A recursive matrix multiplication program described by Backus uses conditional and construction extensively. The proposed implementation technique reduces the execution time of this program on the cellular computer in question from O(n3) to O(n2).

REFERENCES

• 1: W. B. Ackerman, A STRUCTURE MEMORY FOR DATA FLOW COMPUTERS, Massachusetts Institute of Technology, Cambridge, MA, 1977
• 2: ARVIND, 'Decomposing a program for multiple processor systems.' Proceedings of the 1980 International Conference on Parallel Processing, (August 1980), 7-14.
• 3: John Backus, Can programming be liberated from the von Neumann style?: a functional style and its algebra of programs, Communications of the ACM, v.21 n.8, p.613-641, Aug. 1978 [doi>10.1145/359576.359579]
• 4: MAGO, G. A. 'A network of microprocessors to execute reduction languages.' Two parts. International Journal of Computer and Information Sciences 8, 5 (1979) 349-385, 8, 6 (1979) 435-471.
• 5: MAGO, G. A., STANAT, D. F. and KOSTER, A. 'Program execution in a cellular computer: some matrix algorithms' (in preparation).
• 6: MAGO, G. A. 'A cellular computer architecture for functional programming', Digest of Papers, IEEE Computer Society COMPCON, (Spring 1980), 179-187
• 7: Donald F. Stanat , E. Hollins Williams, Jr., Optimal associative searching on a cellular computer, Proceedings of the 1981 conference on Functional programming languages and computer architecture, p.99-106, October 18-22, 1981, Portsmouth, New Hampshire, United States [doi>10.1145/800223.806768]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Applicative (functional) languages

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.3 Other Architecture Styles
          Subjects: Cellular architecture (e.g., mobile)

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

General Terms:
Design, Languages