At its core, HPF includes FORTRAN 90. If a FORTRAN 90 program were run through an HPF compiler, it must produce the same results as if it were run through a FORTRAN 90 compiler. Assuming an HPF program only uses FORTRAN 90 constructs and HPF directives, a FORTRAN 90 compiler could ignore the directives, and it should produce the same results as an HPF compiler.

As the user adds directives to the program, the semantics of the program are not changed. If the user completely misunderstands the application and inserts extremely ill-conceived directives, the program produces correct results very slowly. An HPF compiler doesn't try to "improve on" the user's directives. It assumes the programmer is omniscient.2

Once the user has determined how the data will be distributed across the processors, the HPF compiler attempts to use the minimum communication necessary and overlaps communication with computation whenever possible. HPF generally uses an "owner computes" rule for the placement of the computations. A particular element in an array is computed on the processor that stores that array element.

All the necessary data to perform the computation is gathered from remote processors, if necessary, to perform the computation. If the programmer is clever in decomposition and alignment, much of the data needed will be from the local memory rather then a remote memory. The HPF compiler is also responsible for allocating any temporary data structures needed to support communications at runtime.

In general, the HPF compiler is not magic - it simply does a very good job with the communication details when the programmer can design a good data decomposition. At the same time, it retains portability with the single CPU and shared uniform memory systems using FORTRAN 90.

Perhaps the most important contributions of HPF are its data layout directives. Using these directives, the programmer can control how data is laid out based on the programmer's knowledge of the data interactions. An example directive is as follows:

            REAL*4 ROD(10)
      !HPF$ DISTRIBUTE ROD(BLOCK)
    

The !HPF$ prefix would be a comment to a non-HPF compiler and can safely be ignored by a straight FORTRAN 90 compiler. The DISTRIBUTE directive indicates that the ROD array is to be distributed across multiple processors. If this directive is not used, the ROD array is allocated on one processor and communicated to the other processors as necessary. There are several distributions that can be done in each dimension:

             REAL*4 BOB(100,100,100),RICH(100,100,100)
      !HPF$ DISTRIBUTE BOB(BLOCK,CYCLIC,*)
      !HPF$ DISTRIBUTE RICH(CYCLIC(10))
    

These distributions operate as follows:

Figure 1

Distributing array elements to processors

Figure 1 shows how the elements of a simple array would be mapped onto three processors with different directives.

It must allocate four elements to Processors 1 and 2 because there is no Processor 4 available for the leftover element if it allocated three elements to Processors 1 and 2. In Figure 1, the elements are allocated on successive processors, wrapping around to Processor 1 after the last processor. In Figure 1, using a chunk size with CYCLIC is a compromise between pure BLOCK and pure CYCLIC.

To explore the use of the *, we can look at a simple two-dimensional array mapped onto four processors. In Figure 2, we show the array layout and each cell indicates which processor will hold the data for that cell in the two-dimensional array. In Figure 2, the directive decomposes in both dimensions simultaneously. This approach results in roughly square patches in the array. However, this may not be the best approach. In the following example, we use the * to indicate that we want all the elements of a particular column to be allocated on the same processor. So, the column values equally distribute the columns across the processors. Then, all the rows in each column follow where the column has been placed. This allows unit stride for the on-processor portions of the computation and is beneficial in some applications. The * syntax is also called on-processor distribution.

Figure 2

Two-dimensional distributions

When dealing with more than one data structure to perform a computation, you can either separately distribute them or use the ALIGN directive to ensure that corresponding elements of the two data structures are to be allocated together. In the following example, we have a plate array and a scaling factor that must be applied to each column of the plate during the computation:

            DIMENSION PLATE(200,200),SCALE(200)
      !HPF$ DISTRIBUTE PLATE(*,BLOCK)
      !HPF$ ALIGN SCALE(I) WITH PLATE(J,I)
    

Or:

            DIMENSION PLATE(200,200),SCALE(200)
      !HPF$ DISTRIBUTE PLATE(*,BLOCK)
      !HPF$ ALIGN SCALE(:) WITH PLATE(*,:)
    

In both examples, the PLATE and the SCALE variables are allocated to the same processors as the corresponding columns of PLATE. The * and : syntax communicate the same information. When * is used, that dimension is collapsed, and it doesn't participate in the distribution. When the : is used, it means that dimension follows the corresponding dimension in the variable that has already been distributed.

You could also specify the layout of the SCALE variable and have the PLATE variable "follow" the layout of the SCALE variable:

            DIMENSION PLATE(200,200),SCALE(200)
      !HPF$ DISTRIBUTE SCALE(BLOCK)
      !HPF$ ALIGN PLATE(J,I) WITH SCALE(I)
    

You can put simple arithmetic expressions into the ALIGN directive subject to some limitations. Other directives include:

The use of directives can range from very simple to very complex. In some situations, you distribute the one large shared structure, align a few related structures and you are done. In other situations, programmers attempt to optimize communications based on the topology of the interconnection network (hypercube, multi-stage interconnection network, mesh, or toroid) using very detailed directives. They also might carefully redistribute the data at the various phases of the computation.

Hopefully your application will yield good performance without too much effort.

While the HPF designers were in the midst of defining a new language, they set about improving on what they saw as limitations in FORTRAN 90. Interestingly, these modifications are what is being considered as part of the new FORTRAN 95 standard.

The FORALL statement allows the user to express simple iterative operations that apply to the entire array without resorting to a do-loop (remember, do-loops force order). For example:

      FORALL (I=1:100, J=1:100) A(I,J) = I + J
    

This can be expressed in native FORTRAN 90 but it is rather ugly, counterintuitive, and prone to error.

Another control structure is the ability to declare a function as "PURE." A PURE function has no side effects other than through its parameters. The programmer is guaranteeing that a PURE function can execute simultaneously on many processors with no ill effects. This allows HPF to assume that it will only operate on local data and does not need any data communication during the duration of the function execution. The programmer can also declare which parameters of the function are input parameters, output parameters, and input-output parameters.

The companies who marketed SIMD computers needed to come up with significant tools to allow efficient collective operations across all the processors. A perfect example of this is the SUM operation. To SUM the value of an array spread across N processors, the simplistic approach takes N steps. However, it is possible to accomplish it in log(N) steps using a technique called parallel-prefix-sum. By the time HPF was in development, a number of these operations had been identified and implemented. HPF took the opportunity to define standardized syntax for these operations.

A sample of these operations includes:

While there are a large number of these intrinsic functions, most applications use only a few of the operations.

In order to allow the vendors with diverse architectures to provide their particular advantage, HPF included the capability to link "extrinsic" functions. These functions didn't need to be written in FORTRAN 90/HPF and performed a number of vendor-supported capabilities. This capability allowed users to perform such tasks as the creation of hybrid applications with some HPF and some message passing.

High performance computing programmers always like the ability to do things their own way in order to eke out that last drop of performance.

To port our heat flow application to HPF, there is really only a single line of code that needs to be added. In the example below, we've changed to a larger two-dimensional array:

              INTEGER PLATESIZ,MAXTIME 
              PARAMETER(PLATESIZ=2000,MAXTIME=200)
      !HPF$   DISTRIBUTE PLATE(*,BLOCK)
              REAL*4 PLATE(PLATESIZ,PLATESIZ) 
              INTEGER TICK
              PLATE = 0.0
    
      * Add Boundaries
              PLATE(1,:) = 100.0
              PLATE(PLATESIZ,:) = -40.0
              PLATE(:,PLATESIZ) = 35.23
              PLATE(:,1) = 4.5
    
              DO TICK = 1,MAXTIME
                PLATE(2:PLATESIZ-1,2:PLATESIZ-1) = (
          +       PLATE(1:PLATESIZ-2,2:PLATESIZ-1) +
          +       PLATE(3:PLATESIZ-0,2:PLATESIZ-1) +
          +       PLATE(2:PLATESIZ-1,1:PLATESIZ-2) +
          +       PLATE(2:PLATESIZ-1,3:PLATESIZ-0) ) / 4.0
                PRINT 1000,TICK, PLATE(2,2)
      1000      FORMAT('TICK = ',I5, F13.8) 
              ENDDO
      *
              END
    

You will notice that the HPF directive distributes the array columns using the BLOCK approach, keeping all the elements within a column on a single processor. At first glance, it might appear that (BLOCK,BLOCK) is the better distribution. However, there are two advantages to a (*,BLOCK) distribution. First, striding down a column is a unit-stride operation and so you might just as well process an entire column. The more significant aspect of the distribution is that a (BLOCK,BLOCK) distribution forces each processor to communicate with up to eight other processors to get its neighboring values. Using the (*,BLOCK) distribution, each processor will have to exchange data with at most two processors each time step.

When we look at PVM, we will look at this same program implemented in a SPMD-style message-passing fashion. In that example, you will see some of the details that HPF must handle to properly execute this code. After reviewing that code, you will probably choose to implement all of your future heat flow applications in HPF!

In some ways, HPF has been good for FORTRAN 90. Companies such as IBM with its SP-1 needed to provide some high-level language for those users who didn't want to write message-passing codes. Because of this, IBM has invested a great deal of effort in implementing and optimizing HPF. Interestingly, much of this effort will directly benefit the ability to develop more sophisticated FORTRAN 90 compilers. The extensive data flow analysis required to minimize communications and manage the dynamic data structures will carry over into FORTRAN 90 compilers even without using the HPF directives.

Time will tell if the HPF data distribution directives will no longer be needed and compilers will be capable of performing sufficient analysis of straight FORTRAN 90 code to optimize data placement and movement.

In its current form, HPF is an excellent vehicle for expressing the highly data-parallel, grid-based applications. Its weaknesses are irregular communications and dynamic load balancing. A new effort to develop the next version of HPF is under- way to address some of these issues. Unfortunately, it is more difficult to solve these runtime problems while maintaining good performance across a wide range of architectures.