On performance and space usage improvements for parallelized compiled APL code

ABSTRACT

Loop combination has been a traditional optimization technique employed in APL compilers, but may introduce dependencies into the combined loop. We propose an analysis method by which the compiler can keep track of the change of the parallelism when combining high-level primitives. The analysis is necessary when the compiler needs to decide a trade-off between more parallelism and a further combination. We also show how the space usage, as well as the performance, improves by using system calls with the aid of garbage collection to implement a dynamic memory allocation. A modification of the memory management scheme can also increase available parallelism. Our experimental results indicate that the performance and the space usage improve appreciably with the above enhancements.

REFERENCES

• 1: Timothy Budd, An APL compiler, Springer-Verlag New York, Inc., New York, NY, 1988
• 2: Clark Wiedmann, A performance comparison between an APL interpreter and compiler, Proceedings of the international conference on APL, p.211-217, April 10-13, 1983, Washington, D.C., United States
• 3: Wai-Mee Ching, An APL/370 compiler and some performance comparisons with APL interpreter and FORTRAN, Proceedings of the international conference on APL, p.143-147, July 07-11, 1986, Mancheester, United Kingdom
• 4: Graham C. Driscoll, Jr. , Donald L. Orth, APL—compilation-where does the time come from?, Proceedings of the international conference on APL: APL in transition, p.457-459, May 10-14, 1987, Dallas, Texas, United States
• 5: Timothy A. Budd, An APL compiler for the UNIX timesharing system, Proceedings of the international conference on APL, p.205-209, April 10-13, 1983, Washington, D.C., United States
• 6: Robert Bernecky , Charles Brenner , Stephen B. Jaffe , George P. Moeckel, ACORN: APL to C on real numbers, Conference proceedings on APL 90: for the future, p.40-49, August 13-17, 1990, Copenhagen, Denmark
• 7: Alain Guillon, An APL compiler: The SOFREMI-AGL compiler, a tool to produce low-cost efficient software, Proceedings of the international conference on APL: APL in transition, p.151-156, May 10-14, 1987, Dallas, Texas, United States
• 8: Wai-Mee Ching, Automatic parallelization of APL-style programs, Conference proceedings on APL 90: for the future, p.76-80, August 13-17, 1990, Copenhagen, Denmark
• 9: Dz-Ching Ju , Wai-Mee Ching, Exploitation of APL data parallelism on a shared-memory MIMD machine, Proceedings of the third ACM SIGPLAN symposium on Principles and practice of parallel programming, p.61-72, April 21-24, 1991, Williamsburg, Virginia, United States
• 10: Leo J. Guibas , Douglas K. Wyatt, Compilation and delayed evaluation in APL, Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.1-8, January 23-25, 1978, Tucson, Arizona [doi>10.1145/512760.512761]
• 11: Jim Weigang, An introduction to STSC's APL compiler, Proceedings of the international conference on APL: APL and the future, p.231-238, May 12-16, 1985, Seattle, Washington, United States
• 12: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 13: W-M Ching, Program analysis and code generation in an APL/370 compiler, IBM Journal of Research and Development, v.30 n.6, p.594-602, Nov. 1986
• 14: F. E. Allen , J. Cocke, A program data flow analysis procedure, Communications of the ACM, v.19 n.3, p.137, March 1976 [doi>10.1145/360018.360025]
• 15: R. Tarjan, "Testing Flow-Graph Reducibility," Jour. of Computer & System Science, vol. 9, pp. 355-365, (1974).
• 16: Andrew R. Pleszkun , Matthew J. Thazhuthaveetil, The architecture of Lisp machines, Computer, v.20 n.3, p.35-44, March 1987 [doi>10.1109/MC.1987.1663507]
• 17: Guy L. Steele, Jr., Multiprocessing compactifying garbage collection, Communications of the ACM, v.18 n.9, p.495-508, Sept. 1975 [doi>10.1145/361002.361005]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

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

          Nouns: APL
      D.3.3 Language Constructs and Features
          Subjects: Concurrent programming structures
      D.3.4 Processors
          Subjects: Compilers

General Terms:
Languages, Performance