Interactive program improvement via EAVE: an expert adviser for vectorization

ABSTRACT

An example of a state-of-the-art high-end mainframe is the IBM 3090 VF; its associated compiler, the IBM VS Fortran (version 2) compiler, incorporates some of the latest techniques in automatic vectorization and code optimization. Advances in compiler technology not withstanding, a potential limitation is the “knowledge gap” which exists between the typical end user and the compiler/machine sub-system. In particular, the user often does not know how to write source code which will result in generation of efficient, high performance object code. In this paper, we address the issue of providing interactive aids for program development and transformation as a means to bridge this knowledge gap. We show how heuristic program changes, guided by the knowledge of a particular compiler-machine pair, help approach achievable peak performance through enhanced vectorization/parallelization. We present our techniques and results in terms of an implemented expert system, called EAVE, which has been designed to help users tune their programs for enhanced performance on the IBM 3090 VF.

REFERENCES

• 1: D.J. Kuck, R. !t. Kuhn, B. Leasure and M. Wolfe, "Fhe structure of an advanced retargetable vectorizer," Proc. of COMPSAC "80, 1980; revised form in: Supercomputers: Design and Applications, K. Hwang, ed., IEEE Computer Society Press, pp. 163-178, August 1984; also, follow-on Parafrase II project at CSRD, Univ. of Illinois, C. Polychronopoulos et at.
• 2: J. R. Allen and K. Kennedy, "PFC: A program to convert Fortran to parallel form," Proc. of the IBM Conf. on Parallel Computers and Scientific Computations, 1982; also available in: Supercomputers: Design and Applications, K. l lwang, ed., IEEE Computer Society Press, pp. 186-203, August 1984.
• 3: F. Allen , M. Burke , P. Charles , R. Cytron , J. Ferrante, An overview of the PTRAN analysis system for multiprocessing, Proceedings of the 1st International Conference on Supercomputing, p.194-211, March 1988, Athens, Greece
• 4: IBM, VS FORTRAN Version 2 Programming Guide, February 1986; IBM order number SC26-4222.
• 5: IBM, Engineering and Scientific Subroutine Library Guide and Reference, February 1986; IBM order number SC23-0184.
• 6: IBM System/370 Vector Operations, January 1986; IBM order number SA22-7125.
• 7: IBM, IBM Systems Journal, Vol 25, No.l, 1986, pp. 4-81.
• 8: Cray Researh, Inc., "Cray-1 computer system reference manual," publication 2240004, Cray Research, Inc., Bloomington,. Minnesota 1976.
• 9: A.A. Dubrulle, R. G. Scarborough and H. G. K olsky, "flow to write good vectorizable Fortran," IBM Palo Alto Scientific Center, G320-3478, Sept 1985.
• 10: II. H. Wang, "Introduction to vectorizing techniques," IBM Palo Alto Scientific Center, G320-3489, March 1986.
• 11: Randolf G Scarborough , Harwood G Kolsky, A vectorizing Fortran compiler, IBM Journal of Research and Development, v.30 n.2, p.163-171, March 1986
• 12: B. Liu and N. Strother, "Peak vector performance from VS Fortran," IBM Technical Report # RC 12849, T. J. Watson Research Center, Yorktown lleights, NY, June 1987.
• 13: R. Ellersiek, "Vector coding techniques for VS Fortran version 2," Proceedings of SItARE 68, March 1987.
• 14: T. Brandes and M. Sommer, "A knowledge-based parallelization tool in a programming environment," Pro~. 16th Int'l. Conf. on Parallel Processing, pp. 446-448, 1987.
• 15: Scientific Workstation Environment' Faust; brief description in CSRD Research Review, University of Illinois at Urbana-Champaign, page 43, October 1987.
• 16: U. Banerjee, "Data dependence in ordinary programs," Dept. of Computer Science, University of Illinois at Urbana-Champaign, UIUCDCS-R-76-837, 1976.
• 17: U. Banerjee, S-C.Chen, D. J.Kuck and R. A. Towle, "Time and parallel processor bounds for Fortran-like loops," IEEE Trans. on Computers, Vol C-28, No. 9, September 1979, pp. 660-670.
• 18: John Randal Allen, Dependence analysis for subscripted variables and its application to program transformations, 1983
• 19: J. J. Dongarra, F. G. Gustavson and A. Karp, "Implementing linear algebra algorithms for dense matrices on a vector pipeline machine," SIAM Review, 26(1):91-112, January 1984.
• 20: G. F. Pfister, et al., "The Research Parallel Processor Prototype (RP3): introduction and architecture," Proc. Int'l. Conf. on Parallel Processing, pp. 764-771, August 1985.
• 21: F. Darema et at., ZA Single-Program-Multiple-Data computational model for EPEX Fortran," IBM Research Report RC 11552, Yorktown lieights, NY, October 1986.
• 22: Alan H. Karp, Programming for parallelism, Computer, v.20 n.5, p.43-57, May 1987 [doi>10.1109/MC.1987.1663563]
• 23: Ken Kennedy, Automatic Decomposition of Fortran Programs for Execution on Multiprocessors-Abstract, Proceedings of the Third SIAM Conference on Parallel Processing for Scientific Computing, p.300, December 01-04, 1987
• 24: R. G. Cytron, 'q)oacross: beyond vectorizalfion for multiprocessors," Proc. of the 1986 Int'l. Conf. on Parallel Processing, 1986.
• 25: R. G. Cytron, "Limited processor scheduling of doacross loops," Proc. of the 1987 Int'l. Conf. on Parallel Processing, 1987.
• 26: P. Bose, "A brief status report on EAVE: an expert adviser for vectorization," IBM Research Report RC 13353, 12/10/87.
• 27: P. Bose, "Gedanken experiments with Fortran do loops on the 3090 VF," IBM Research Report (under clearance for publication).
• 28: Expert System Environment/VM, Reference Manual, 1st. edition, September 1987, IBM order number SC38-7004-0.
• 29: R. Allen, D. Baumgartner, K. Kennedy and A. Porterfield, "PTOOL: A semi-automatic parallel programming assistant," Proc. lnt'l. Conf. on Parallel Processing, pp. 164-1713, August 1986.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.5 Programming Languages and Software
          Subjects: Expert system tools and techniques

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Array and vector processors
  C.5 COMPUTER SYSTEM IMPLEMENTATION
      C.5.1 Large and Medium ("Mainframe") Computers
          Subjects: Super (very large) computers

  D. Software
  D.2 SOFTWARE ENGINEERING
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

General Terms:
Algorithms, Theory