Compiling APL for parallel execution on an FFP machine

Abstract

This paper investigates the features of an APL compiler designed for a cellular computer (the FFP machine). This machine directly executes Formal Functional Programming (FFP) code. The APL compiler generates parallel FFP code. Techniques for parallel implementation of many APL array processing operators and functions are described. The implicit parallelism between different operations in a given APL program is also exploited. The FFP machine can accommodate the almost unbounded parallelism of FFP programs. Execution time analysis shows potential for highly efficient execution of APL programs on this machine.

References

1. 1 Abrams, P.L. 1970; "An APL Machine", Ph.D. Thesis, Stanford University
2. 2 Aho, A.V. and Ullman, J.D. 1977. "Principles of Compiler Design". Addison Wesley
3. 3 Analogic Corp. 1983. "The APL Machine--The High Productivity APL Computer", product announcement
4. 4 Backus, J. 1973. "Programming Language Semantics and Closed Applicative Languages". IBM Research Report RJ 1010
5. 5 Backus, J. 1978. "Can Programming be Liberated from the von Neumann Style? A Functional Style and its Algebra of Programs". CACM, 21, 8.
6. 6 Brenner, N. 1982. "APL on a Multiprocessor Architecture". APL82, pp 57-60
7. 7 Budd, T.A. 1982. "An APL Compiler for a Vector Processor". Technical Report 86-2, University of Arizona
8. 8 Budd, T.A. 1983. "An APL Compiler for the UNIX Timesharing System". Proceedings APL83, pp 205-209
9. 9 Foster, G.H. 1980. "An Alternative Design for an APL Engine". Proc. APL80, pp 75-80
10. 10 Harrison, M.J. and Harrison, W.H. 1974. "The Implementation of APL on an Associative Processor" Lectures Notes in Computer Science: Parallel Processing, Springer-Verlag, pp 75-96
11. 11 Iverson, K.E 1979. 'The Role of Operators in APL". APL79, pp 128-133
12. 12 Jenkins, M.A. 1982. "The Q'Nial Reference Manual'. V. 1.0, Department of Computing and Information Science, Queen's University, Kingston, Canada
13. 13 Kerr, F.T. 1979. "Simulation of a Reduction Machine". M.S. Thesis, University of North Carolina at Chapel Hill.
14. 14 Koster, A. 1977. "Execution Time and Storage Requirements of Reduction Language Programs on a Reduction Machine". Ph.D. Thesis, University of North Carolina at Chapel Hill.
15. 15 Mago, G. 1979. "A Network of Microprocessors to Execute Reduction Languages". International Journal of Computer and Information Sciences, 8, 5, and 8, 6.
16. 16 Mago, G. 1980. "A Cellular Computer Architecture for Functional Programming". Proceedings, IEEE Spring Compcon.
17. 17 Mago, G., Stanat, D., and Koster, A. 1981. "Program Execution in a Cellular Computer: Some Matrix Algorithms". In preparation.
18. 17a Mago, G. and Middleton, C. 1984. "The FFP Machine: a Progress Report". Proc. International workshop on High-level Language Architecture, Los Angeles.
19. 18 Miller, T.C. 1979. 'Tentative Compilation: A Design for an APL Compiler". APL79, pp 88-95
20. 19 Muchnick, S. and Jones, N.D. 1981. "Program Flow Analysis: Theory and Application". Prentice Hall
21. 20 Perlis, A.J. 1975. 'Steps toward an APL Compiler". Dept of Computer Science, Yale University, Science Research Report #24
22. 21 Pozefsky, M. 1977. "Programming in Reduction Languages". Ph.D. Thesis, University of North Carolina at Chapel Hill.
23. 22 Schmidt, F.L., and Jenkins, M.A. 1982. "Arrays Diagrams and the Nial Approach". Proc. APL82, pp 315-319
24. 23 Stanat, D., and Williams, E. 1981. "Optimal Associative Searching on a Cellular Computer". Proceedings of the Conference on Functional Programming Languages, Portsmouth.
25. 24 Sybalsky, J.D. 1980. 'An APL Compiler for the Production Environment". Proceedings APL80, pp 71-74
26. 25 Thurber, K.J., and Myrna, J.W. 1970. "Systems Design of a Cellular APL Computer. IEEE Transactions on Computer, C-19, 4, pp 290-303
27. 26 Touretzky, D.S. 1983. "A Comparison of Reduction in APL with Polarity in LISP". Proceedings APL83, pp 259-263
28. 27 Wagner, Robert. 1983. "The Boolean Vector Machine {BVMI". Proceedings of the 10th Annual Conference on Computer Architecture, Stockholm, pp 59-66
29. 28 Wakshull, M.N. 1982. "The Use of APL in a Concurrent Data Flow Environment". APL82, pp 367-372
30. 29 Weiss, 2. and Sal1 H. 1981. "Compile Time Syntax Analysis of APL Programs". APL 81 Conference Proceedings, pp 313-321
31. 30 Wiedman, C. 1979. "Steps Toward an APL Compiler". APL79, pp 321-328
32. 31 Wulf, W. and Shaw, M. 1973. "Global Variables Considered Harmful". SIGPLAN Notices, 8, 2, pp 28-34

Index Terms

• Software and its engineering

  • Software notations and tools

    • Compilers

    • General programming languages

      • Language types

        • Functional languages

• Theory of computation

  • Models of computation

    • Concurrency

      • Parallel computing models