Efficient translation of High Performance Fortran for distributed memory architectures

Case for support

Purpose

The recently published High Performance Fortran (HPF) language standard is expected to have a major impact on the future of parallel computing, especially on distributedmemory MIMD machines. It is based on a simple and familiar programming language, offers wide portability, a simple migration method for existing Fortran codes, and the promise of high performance. There is every chance, therefore, that it will rapidly become the preferred language for scientific and engineering applications of parallel computers.

Until now, the lack of a programming language with these desirable features has been a major factor behind the slow take-up of distributed memory architectures. Despite their high performance and cost effectiveness—demonstrated across a range of important applications—the development cost of application software targetting specialised architectures too often outweighs any inherent price-performance advantage of the hardware.

Looking ahead some years, there is no obvious reason why HPF compilers should not produce code competitive with hand-crafted message-passing code. It has been argued that an HPF compiler can actually do better because, for example, it can target low-level machine instructions, and statically allocate message buffers (rather than going through message-passing portability layers). However, early HPF compilation systems are unlikely to generate such efficient code. HPF-like systems are in their infancy, and there has been relatively little study of optimisation issues. Research is urgently needed into efficient implementation of the complex HPF semantics.

The aim of this project is therefore to investigate HPF compiler optimisation, particularly in the following areas:

• To develop methods to determine optimal placement of sub-expression calculation, to supersede the widely-used, very crude, “owner-computes” heuristic.

• To investigate the relative merits of various mooted schemes for organising data communications in HPF-like languages.

• To implement the fruits of this research within a Subset HPF compilation system currently under development by our group, and evaluate the performance gains from these optimisations.

• To compare our Subset HPF system with the Distributed Memory Paralleliser and HPF compiler in the ‘Forge 90’ system, widely considered to represent the state-of-the-art in Fortran parallelisation for distributed-memory systems.

Our Subset HPF compilation system will generate Fortran 90 output with calls to a communication library. We plan to make this freely available to the research community.

NAG Ltd, who market a successful Fortran 90 compiler, will act as “heavy uncle” for this project. They will allow us to use relevant parts of their Fortran 90 compiler and run-time library source code, and provide other assistance. Subject to the negotiation of suitable terms, they will distribute our system together with their Fortran 90 compiler as a complete Subset HPF compilation system.

Background

High Performance Fortran

In the last year the High Performance Fortran Forum (HPFF), a coalition of many leading industrial and academic groups in the field of parallel processing, has established the High Performance Fortran (HPF) informal standard. This is a set of extensions to Fortran 90 supporting data-parallel computations on multi-processor architectures [HPFF93, Mer93]. In particular, HPF includes directives for specifying (at various levels of abstraction) how program data should be distributed over virtual or actual processor memories. The standard is supported by most parallel computer manufacturers, and several vendors have already announced HPF products. An official subset of HPF has been defined to facilitate early implementations. It is expected that the first true “Subset HPF” compilers, implemented as translators to Fortran plus message-passing, will appear at the end of 1993 or start of 1994.

HPF was developed to simplify the programming of multi-processor architectures, especially distributed-memory MIMD systems. It is based on recent research into the transformation of ordinary sequential languages, suitably annotated with data distribution declarations, into distributed memory message-passing programs (e.g. [Koe90, Fox91, Wu91, Hat90, And90, Chap92, Mer92]).

Research implementations of these systems have been developed and demonstrate the feasibility of such transformations. However, current transformation schemes are somewhat limited. As yet there has been little work on optimisation issues for such systems—work to date has concentrated on initial implementation.

Southampton Involvement with HPF

Since 1989 Dr. John Merlin has been involved in research and development on a system called ADAPT (“Array Distribution Automatic Parallelisation Tool”) for automatically transforming Fortran 90, supplemented by data distribution declarations, into code for distributed memory message-passing architectures [Mer91]. The system generates a standard Fortran program to run on the individual nodes of the target machine, which calls a run-time library to perform data communications.

The input language for the ADAPT system, “Distributed Fortran 90”, may be regarded (with Fortran D and Vienna Fortran) as a precursor of HPF.

Southampton has had a significant input into, and influence on, the development of HPF, through an active involvement in the HPFF. Our contributions to the language include the PURE procedure mechanism, which allows suitably constrained procedures to be invoked concurrently, providing useful scope for MIMD parallelism in an otherwise predominantly SIMD programming model.

This year we have undertaken to modify the ADAPT system into a Subset HPF compiler (or rather a translator from Subset HPF to Fortran 90 plus calls to a communications library). This is a joint project involving Dr. Merlin, who is modifying the ADAPT translator, and Dr. Bryan Carpenter, who is developing the associated run-time system.

Limited attention is being paid to optimisation issues in the first version of the system.

Research experience

Prof. Tony Hey is the Professor of Computation at the University of Southampton and chairman of the Parallel Applications Centre (PAC) at Southampton. He has been a leading researcher in parallel computing for many years, being the initiator, with Dr. David May of INMOS, of the Esprit Supernode project which delivered the T800 transputer. He has since been involved in a wide range of projects in concurrent computation. Recently he was a co-author of a proposal which formed the basis for the Message Passing Interface (MPI) in the U.S.A., which aims to provide a standard for message-passing.

Dr. Bryan Carpenter and Dr. John Merlin have both been members of the Concurrent Computation Group for several years, initially involved in programming large-scale scientific applications in occam for transputer arrays. Dr. Merlin is the architect of ADAPT. He has been a participant in an Esprit-funded European working group on high level languages for distributed memory architectures. More recently he was actively involved with HPFF, made various contributions to HPF language, and authored sections of the language definition document. He is currently employed by the Esprit CAMAS project. Dr. Carpenter has been involved in the Supernode, Genesis and PUMA projects. In the latter he developed an Array Communications Library for implementing dataparallel applications on transputer arrays. The collective operations it implemented have influenced the design of ADLIB, the run-time library of ADAPT.

Numerical Algorithms Group

NAG Ltd, who are well known for their numerical libraries and more recently for developing the first full Fortran 90 compiler (which translates Fortran 90 to C), have taken an interest in this work and are giving us technical support. If our compiler is suitable, they plan to distribute it together with their Fortran 90 compiler as a Subset HPF compilation system. They will act in the rôle of “heavy uncle” for this research proposal, as we shall describe later.

Programme

HPF is a very high level language, in the sense that a simple-looking operation may translate to rather complicated target code. Efficient compilation is highly non-trivial. For example, even given the clues from program-variable distribution directives, there are often many candidate choices for the localisation of individual computations (“calculation placement”). A bad choice may lead to excessive communication or poor load balancing.

This project aims to advance the state-of-the-art in HPF translation schemes. Two principle areas demanding investigation are:

1. Effective strategies for the placement of calculation, and

2. Efficient schemes for managing communication, and minimising associated data copying.

These two aspects are logically somewhat independent. The first defines what communications will be needed. The second, given a required pattern of communication, concentrates on achieving that pattern efficiently.

Calculation Placement

Placement of calculation cannot be prescribed by directives in the HPF standard (proposals to allow this were rejected). In simple cases this placement will be obvious—for example where all of the operands of an individual computation are program variables held on the same processor (as determined by the placement directives). Things are rarely this simple, and in general a compiler will need an effective strategy for making the placement.

To allocate computation to processors, many current HPF-like prototype systems use a simple heuristic called the “owner-computes” rule, whereby the expression in an assignment statement is evaluated by the processor that “owns” the assignment variable, after the operands have been sent there. In many cases, where an expression is not the right hand side of a simple assignment statement, the strategy provides no guidance. Where it is applicable it may be far from optimal in terms of communication, temporary storage requirements, and processor utilisation.

Some research into this problem has concentrated on techniques for finding truly optimal placements for subexpressions, under some simplifying assumptions about language features and communication costs. An alternative approach is to develop heuristics which yield “intuitive” placements. Although these may not be optimal, they are unlikely to be very bad.

We will investigate these strategies. There are two issues to be taken into account. Firstly the resulting code must be reasonably close to optimal; secondly, the placement strategy should not be so expensive as to make compilation time prohibitive—optimisation problems such as this are prone to exponential time complexity. We have performed some preliminary experiments on placement heuristics encoded in Prolog for prototyping— probably a production compiler would have to be faster.

Communication Management

We will investigate (in particular) two important aspects.

Loop splitting

In many cases, especially with problems involving some “locality of reference” (e.g. local updates in grid problems), array assignments and DO-loops can profitably be split into parts operating on local data and parts involving communication. This may facilitate overlapping of communication and computation, and make calculations on internal data simpler.

For example, suppose that arrays A and B are identically aligned; consider the following array assignment:

  A (1:N-1) = B (0:N-2) + B (2:N)

This is typically parallelised by placing a segment of the assignment index range (or DOloop index range) on each processor. Communication is required at the edges of these segments. Two basic strategies are to use collective shifts to make two copies of the B array, or just to copy the data on the edges from the adjacent processors. In the latter case the edge data can be copied into an “overlap area” made by declaring the locally held array segment to be sufficiently large to accommodate the off-processor data, or the communicated data can be copied to separately allocated temporary storage.

Which of these assorted schemes is optimal depends on a number of circumstances, including system parameters such as calculation and communication costs, the availability of temporary storage, and how much information about the assignment is statically available. We propose to develop criteria to select the best candidate by context.

In-lining of layered communication library

In certain places in HPF code (for example, in subprograms, when data has “transcriptive” mapping) almost no information is statically available concerning the whereabouts of particular array elements. In this case data is accessed by very high-level run-time libraries, with a large performance penalty.

At the opposite extreme, on sufficiently simple code an optimising compiler may be able to go straight to low level communication instructions (below the level of standard message passing interfaces).

An attractive way to define the HPF translation scheme is to start from a layered runtime system, with general data access and collective communication near the top level. Some representation of this run-time system—which may differ between platforms—is available to the compiler (ideally in a data-base apart from the translator itself). Code is initially translated to employ top-level calls. In successive optimization passes, calls to the run-time library are “in-lined” to give calls to the next layer of the library, whenever appropriate static information is available about the actual arguments. The resulting code is simplified where the static context permits.

We propose to explore the feasibility and utility of this modular “onion-skin” approach to optimising communication.

Implementation and evaluation

These optimisations will be implemented and evaluated within a Subset HPF compiler that is currently under development (see “Background”).

Finally, we will compare our Subset HPF system with the Distributed Memory Paralleliser and HPF compiler in the ‘Forge 90’ system, which is widely regarded as representing the state-of-the-art in the parallelisation of Fortran for distributed-memory computers.

Resources

We have requested funding for two named individuals, Dr. John Merlin and Dr. Bryan Carpenter, whose research backgrounds are detailed elsewhere in this proposal. Their experience and abilities are ideal for the proposed research.

The funds requested for travel allow for visits to our industrial collaborators NAG Ltd, for visits to other UK establishments who are active in HPF research and development, and for attendance at suitable HPF meetings and workshops in the UK. We have also requested travel funds for each researcher to attend two selected overseas conferences or workshops per year. In particular we wish to be represented at the specialist ‘Compilers for Parallel Computers’ workshops in Europe, which attract most of the leading researchers in this field and which we have attended since their inception, as well as selected conferences (e.g. Supercomputing) and HPF workshops. Finally, we have requested funds for one visit to Hans Zima’s group at the ACPC in Vienna, and one U.S. trip to visit the groups at Rice and Syracuse Universities (and possibly other “centres of excellence”). These are widely regarded as among the leading research groups in the field of Fortran parallelisation, and we have established close contacts with them which will be beneficial to maintain.

Two workstations have been requested for the personal use of the researchers.

Funds have also been requested for a 1-user licence for the ‘Forge 90’ Distributed Memory Paralleliser and run-time library for the Meiko CS-2. This will enable us to compare our Subset HPF system with what is widely regarded as the current state-of-the-art technology for parallelising Fortran for distributed-memory.

Applications, collaboration and exploitation

The aim of this proposed project is to advance the state-of-the-art in the optimisation of High Performance Fortran for distributed memory parallel architectures, workstation networks, etc, and will thereby promote the use of HPF and of such architectures.

We plan to make the Subset HPF translator and communications library that we produce freely available to the research community. The communications library will also be usable separately from the Subset HPF system, and will be well-documented to facilitate this. The system will be designed to retain portability as far as possible, since the translator will target a standard high-level language (Fortran 90), and the associated communications library will use a public domain message-passing system (e.g. PVM) allowing execution on workstation networks as well as parallel supercomputers.

NAG Ltd will act as “heavy uncle” for this project. They will allow us to use relevant parts of their Fortran 90 compiler and run-time library source code, will make any necessary modifications to their Fortran 90 compiler to handle the output of the Subset HPF system, and will also provide technical input and assistance with porting, testing and evaluation. Subject to the negotiation of suitable commercial terms, they plan to distribute the Subset HPF system together with their Fortran 90 compiler as a complete Subset HPF compilation system generating C code.

References

[And90] F. André, J.-L. Pazat and H. Thomas. PANDORE: a system to manage data distribution, Proc. Int. Conf. on Supercomputing, 380-88, June 1990.

[Chap92] B. Chapman, P. Mehrotra and H. Zima. Programming in Vienna Fortran. Scientific Programming \underline{1}(1), August 1992.

[Fox91] G. Fox et al. Fortran D Language Specification. Technical report COMP TR90-141, Dept. of Comp. Sci., Rice Univ., Houston, TX, April 1991.

[HPFF93] High Performance Fortran Forum. High Performance Fortran Language Specification. Sci. Prog., \underline{2} (1), Aug. 1993.

[Mer93] J.H. Merlin and A.J.G. Hey. An introduction to High Performance Fortran. To appear in Sci. Prog., \underline{2} (2), end of 1993.

[Hat90] P.J. Hatcher et al. A production quality C^{∗} compiler for a hypercube multicomputer. Report from Parallel Computing Lab., Dept. of Comp. Sci., Univ. of New Hampshire, Durham, NH 03824, U.S.A.

[Koe90] C. Koelbel, P. Mehrotra and J. Van Rosendale. Supporting shared data structures on distributed memory architectures, Proc. 2nd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pp 177-86, March 1990.

[Mer91] J.H. Merlin. ADAPTing Fortran 90 array programs for distributed memory architectures. Proc. 1st Int. Conf. of the ACPC , Salzburg, Sept. 1991.

[Mer92] J.H. Merlin. Techniques for the Automatic Parallelisation of ‘Distributed Fortran 90’. Technical report SNARC 92-02, Dept. of Electronics and Comp. Science, Univ. of Southampton, November 1991.

[Wu91] M.-Y. Wu and G. Fox. Fortran 90 D compiler for distributed memory MIMD parallel computers. Report SCCS-88b, Syracuse Center for Comp. Sci, Syracuse Univ., Syracuse, New York, July 1991.

[ZBG88] H. Zima, H.-J. Bast and M. Gerndt. SUPERB, a tool for semi-automatic MIMD / SIMD parallelisation, Parallel Computing, \underline{6}, 1-18, 1988.