Automatic parallelization of APL-style programs

ABSTRACT

APL-style programs use high level primitives on arrays instead of DO-loops whenever possible. For such programs, the average size of a basic blocks is much large than those in their FORTRAN counterparts. Hence, it is sufficiently profitable and relative easy to concentrate on basic blocks when parallelizing APL-style programs. But such an approach must depend on an APL compiler. The APL/370 compiler we have been developing aims at implementing automatic parallelization of APL programs at basic block level. The compiler exploits functional parallelism on data independent sub-expressions and data parallelism of array primitives on array elements. The compiler front end does a local data dependency analysis and emits synchronization flags at function nodes. The back end does partitioning of (assembly code) array loop. A set of low-level synchronization primitives on MVS has also been developed. This will enable us to run compiled applications in parallel mode on IBM 3090 multi-processors to access the effectiveness of various scheduling methods on a shared memory model.

REFERENCES

• 1: T. Agerwala and Arvind, ed., Data Flow Systems, IEEE Computer, Feb., 1982.
• 2: Eugene Albert , Kathleen Knobe , Joan D. Lukas , Guy L. Steele, Jr., Compiling Fortran 8x array features for the connection machine computer system, Proceedings of the ACM/SIGPLAN conference on Parallel programming: experience with applications, languages and systems, p.42-56, July 19-21, 1988, New Haven, Connecticut, United States
• 3: Frances Allen , Michael Burke , Philippe Charles , Ron Cytron , Jeanne Ferreant, An overview for the PTRAN analysis system for multiprocessing, Journal of Parallel and Distributed Computing, v.5 n.5, p.617-640, October 1988 [doi>10.1016/0743-7315(88)90015-9]
• 4: M. Burke et al., Automatic Generation of Nested, Fork-Join Parallelism, Jour. of Supercomputing vol.3,71-88. 1989.
• 5: P Carnevali , P Sguazzero , V Zecca, Microtasking on IBM multiprocessors, IBM Journal of Research and Development, v.30 n.6, p.574-582, Nov. 1986
• 6: 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
• 7: W.-M. Ching and A. Xu, A Vector Code Back End of the APL370 Compiler on IBM 3090 and some Performance Comparisons, Proc. of APL'88 Conf., 69-76, 1988.
• 8: W.-M. Ching , R. Nelson , N. Shi, An empirical study of the performance of the APL370 compiler, Conference proceedings on APL as a tool of thought, p.87-93, July 1989, New York City, New York, United States
• 9: R. Cytron and J. Ferrante, What's in a name? On the value of renaming for parallelism detection and storage allocation, Proc. of 1987 Intern'1 Conf. on on Parallel Processing, 19-27, 1987.
• 10: R. Cytron , M. Hind , W. Hsieh, Automatic generation of DAG parallelism, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.54-68, June 19-23, 1989, Portland, Oregon, United States
• 11: Joseph A. Fisher , John R. Ellis , John C. Ruttenberg , Alexandru Nicolau, Parallel processing: a smart compiler and a dumb machine, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.37-47, June 17-22, 1984, Montreal, Canada
• 12: David L. Kuck, Structure of Computers and Computations, John Wiley & Sons, Inc., New York, NY, 1978
• 13: C. Polychronopoulos et al., Parafrase-2: An Evironmen1 for Parallelizing, Partitioning, Synchronizing Programs on Multiprocessors, Proc. of 1989 Intern'1 Conf. on Parallel Processing, 11-39-48, 1989.

INDEX TERMS

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

          Nouns: APL

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

          Nouns: FORTRAN
      D.3.4 Processors
          Subjects: Compilers

  E. Data
  E.1 DATA STRUCTURES
      Subjects: Arrays

General Terms:
Algorithms, Languages