Keywords - performance estimation, execution-driven simulation, program slicing, cache memory simulation, memory hierarchy, automatic program parallelisation

Abstract

This paper describes a performance estimating system developed at the University of Southampton for estimating the execution time of SPMD Fortran programs on distributed memory parallel systems. The system called PERFORM, (Performance EstimatoR For RISC Microprocessors), is an implementation of a new performance estimating technique based on the concept of execution-driven simulation. Whereas straightforward execution-driven simulation is slow, memory intensive and machine specific, our development of this technique has avoided these traditional problems associated with simulation methods. Specifically, our development of this method uses a feedback loop to reduce the amount of code executed during the simulation, while code sections that do not alter the control flow of the program are removed from the simulation code. Variables used in removed code sections are also removed from the simulation code, significantly reducing the memory requirements. This method is also architecturally independent, in that the properties and performance characteristics of the target platform can be specified in a machine description file. Our results show that PERFORM is a substantial improvement over existing performance estimating methods and that this tool could be used by programmers for code analysis, or for incorporation into an automatic/semi-automatic parallel compilation system. PERFORM is available with either a text-based interface or X-Windows/Motif GUI.

1 The Need For Performance Prediction

2 Methods and Problems of Performance Prediction

1. Determine the execution time of each operation on the target machine. This can be done a-priori and need only be done once for each target machine, operating system and compiler tuple.
2. Determine the number and type of operations in the program.
3. Compute the expected execution time of the program on the required target machine by summing the  benchmarked execution times of each operation in the program.

CALL timer(starttime)
DO i=1,iterations 
a(f(i)) = b(f(i)) + c(f(i)) + d(f(i))
ENDDO
CALL timer(endtime)

Figure 1: Benchmark to determine the effect of data locality

Given the importance of data locality in current microprocessor architectures, performance estimating methods are being developed which attempt to quantify the amount of time spent moving data within the memory hierarchy. Fahringer [4] developed a method of statically estimating the number of times a cache line would have to be replaced in a single-level, direct-mapped, cache for a given loop. Although this gave some indication of performance, the approximations were gross, and were unsuitable for converting to execution time. A more reliable method for computing the number of cache capacity and conflict misses was developed by Teman et al [12]. This method is, however, restricted to single-level, direct-mapped caches and has not been implemented in an automatic tool. 

3 The Simulation Solution and PERFORM

PERFORM, is a performance estimating system we have developed based on the principle of execution-driven simulation, but avoiding the traditional simulation problems of generality, speed and memory use. The manner in which this has been done is outlined below:

• Improved generality through source code analysis and augmentation. Our execution-driven simulation method is not machine specific as all code analysis and augmentation is done at the source code level. Platform specific features are accounted for during simulation. The gains in generality do have some impact on the accuracy of the system as the code analyser and augmenter have to approximate the operations that would be executed on the target machine.

• Fast execution-driven simulation. The time to obtain a performance estimate using our method is substantially lower than that of conventional execution-driven simulation techniques. This is due to two modifications that have been made based on the premise that accurate performance estimates are the only requirement of the system. First, only operations that modify the system state and therefore affect the execution time of later operations are simulated. Operations such as ``load'' and ``store'',  which take a variable amount of time to complete depending on the state of the memory hierarchy are  simulated, while arithmetic operations which have constant execution times are not. The second and  most significant way in which we reduce the execution time of our method is by using a feedback loop from the simulator engine to the source code. This feedback loop can curtail the execution of loops in the source code if sufficient information has been obtained on previous loop iterations to accurately predict the simulated execution time at the end of the loop.

• Minimal memory Requirements. One of the main problems with execution-driven simulation methods is that the executed program requires more memory than the original input program. Our method  reduces the amount of memory required by the simulation substantially using a technique known as  ``program slicing'' [14]. The original input program is first transformed into a ``sliced'' program in which all variables and data that do not influence control flow are removed. References to these variables in the program are also removed. By combining the techniques of program slicing, feedback loops, limited simulation and source level analysis into execution-driven simulation, we have developed a method of performance estimation that avoids the problems commonly associated with simulation, yet retains much of the accuracy of full simulation. The stages associated with producing the executable simulation are shown in figure 3.

Obtaining a performance estimate using this method can be seen as a two stage process of analysis and augmentation, followed by execution. The analysis phase consists of program slicing, while the annotation phase consists of annotating the sliced code with simulator calls, and inserting the feedback loop mechanism.

4 Program Slicing within PERFORM

The form of slicing shown in figure 5 is termed an executable program slice. Our work uses this concept applied to the area of program simulation. As we are simulating the movement of data within the memory hierarchy the program slice we generate must maintain sufficient information from the input program to resolve all data addresses and maintain the order in which data is accessed. Computation that does not affect the order in which data is accessed can be removed. The executable program slice must therefore have the following properties:

• Control flow must be identical to the input code, and hence all operations that determine control flow must be included in the sliced program.
• All operations used to compute array indices must be included in the sliced program.

SUBROUTINE TEST (N1,AI1,N2,AR1,AR2) 
  W = 0.0 
  DO I = 1,N1 
    W = W + AI1 
  ENDDO 
  V = 0.0 
  DO I = 1,N2 
    V = V + I*AI1 + N2 
  ENDDO 
  AR1 = W 
  AR2 = V*2 
END

Figure 4: Original program

SUBROUTINE TEST (AI1,N2,AR2) 
  V = 0.0 
  DO I = 1,N2 
    V = V + I*AI1 + N2 
  ENDDO 
  AR2 = V*2 
END

Figure 5: Program in figure 4, sliced on variable AR2

N = 100 
index = 0 
do i = 1, N 
  do j = i-1, i+1, 3 
    index = index + 1 
    B(i) = B(i) + A(index)*X(j) 
  enddo 
enddo

Figure 6: Fortran program to calculate B of AX=B for tridiagonal matrix A

N = 100 
index = 0 
do i = 1, N 
  do j = i-1, i+1, 3 
    index = index + 1 
  enddo 
enddo

Figure 7: Code in figure 6 sliced on variables i; N; j; index

One of the problems with general program slicing is that it may in some situations, be equivalent to reproducing the entire program. Single-level program slicing is sufficient to accommodate many applications and provides three distinct benefits. First, the time required to generate the slice is less than that required if full program slicing is performed. Second, by excluding many operations from the simulation control flow, execution time of the simulation program is improved. Third, and most important, single-level program slicing will, in most instances, result in a significant decrease in the amount of memory required when compared with the original Fortran code. This occurs as only the control variables and array index variables are defined in the sliced program. Hence, for the program in figure 6, data space is only reserved for the variables i, j, N and index. Data space is not required for the arrays B, A, and X. In many applications this results in the data requirements of the simulation code being only a few bytes.

5 Simulator Calls in PERFORM

For example, consider the assignment statement y = sqrt(b² -4ac) This is translated onto the operation sequence given in figure 8. All symbolic names are bound to specific memory locations at a later phase.
 

y=sqrt(b**2 - 4ac)

LDREAL(b);
LDREAL(b);
REALOP('*');
LITINTLD(4);
LDREAL(a);
REALOP('*');
LDREAL(c);
REALOP('*');
REALOP('-');
intrinsic_function("sqrt", realtype);
STREAL(y);

In all cases the sliced program is augmented with the simulator calls at the point where the Fortran statement occurs. If  the Fortran statement has been removed from the sliced program, the simulator calls are inserted at the point where the statement was removed. Additionally, simulator calls are inserted into the sliced program to represent the computational overhead associated with control structures such as do
loops and if  constructs.

6 Modifying the Execution Path Using Feedback Control

STINT(i); 
LDINT(n); 
LDINT(i); 
INTOP('-'); 
STINT(TEMP 0); 
BRCOND ('!='); 
StartTracking (int(((n)-(1)+(1))/1)); 
for (TEMP 0=0; TEMP 0!int(((n)-(1)+(1))/1); TEMP 0++) { 
   i=1+(TEMP 0)*(1); 
   LDINT(i); 
   LITINTLD(1); 
   INTOP('+'); 
   STINT(i); 

7 Calculating the Execution Time in PERFORM

Once all data has been entered by the user, including the required target machine, the generated code is compiled and linked with the simulation library. Peformance and architecture details of the target machine are specified in a separate architecture specification file. Full details of this file can be found in [3].
 
On executing the execution-driven simulation, the simulator creates an internal representation of the register sets and cache memories of the target hardware as specified in the architecture description file. All load and store operations modify the state of this memory hierarchy model, and the time to complete each operation is recorded. Unlike load and store operations, which have varying execution times, the time
required to complete arithmetic operations and most function calls is largely constant. Accordingly, these are defined in terms of clock cycles in the architecture specification file. In situations where the execution time of arithmetic operations and functions is argument dependent, maximum and minimum times can be used to define the performance in the architecture specification file. As the simulator knows nothing about the actual argument values of these operations, the maximum and minimum times are used to predict an execution time bound. Message passing operations are treated in a similar way to function calls. That is, they do not modify the state of the simulator, and the execution time for an operation is determined from previously benchmarked operations. In particular, message passing time is estimated using the benchmarked values of n 1/2 and rinf for the target machine. This has been shown to be a sufficiently accurate model for the
current generation of high-performance processor interconnects [3].

8 Applicability of the PERFORM System

• To predict the execution time of different programs on the same architecture. Automatic parallelising  compilers require an accurate, fast and reliable solution to this problem. Figure 10 shows the extent to which our method solves this problem. This figure shows the percent by which the execution  time predicted by PERFORM for the Livermore kernels differs from the benchmarked results. For comparison, we also show the percent by which the performance estimates obtained using the statement counting method differ from the benchmarked results. The estimate errors obtained using PERFORM are within a much smaller error range, and are on average lower, than those obtained using statement benchmarking. All predicted execution times were obtained within a second.

• For analysing code to identify performance anomalies. PERFORM has been used to perform detailed  analysis on benchmark programs to determine the reason for performance anomalies on different machines and at different problem sizes.

• To predict program scalability. PERFORM has also been used to predict changes in program performance with changes in problem size. Figure 11 is a good example of this. The predicted performance changes closely match the benchmarked results throughout the problem sizes. This type of analysis is useful for identifying optimum problem sizes for a given machine, or for identifying suitable data partitioning sizes.

9 Summary and Conclusion

• Accuracy. We have shown the fast simulation method to be on average three times more accurate than  the statement counting method on the same architecture.

• Execution time. The fast simulation method required no more than 2 seconds to estimate the run time of any code tested, even though all run times were between 10 and 200 seconds on the target hardware. Moreover, the fast simulation method does not require an initial profile run of the program like many other approaches.

• Generality. The fast simulation method is applicable to the vast majority of scientific Fortran programs. Most scientific Fortran programs have execution paths that are defined by the problem size, rather than intermediate computed results. The fast simulation method is directly applicable to this problem class, but is also applicable to programs whose execution path is problem dependent, provided that additional static information concerning the execution path is supplied by the user.

• Portability. The fast simulation method is highly portable in that it is neither tied to a specific performance estimating machine, nor is the intended target hardware fixed or required to be present to obtain a performance estimate. All target hardware characteristics and performance information are specified in a machine description file which can easily and quickly be adapted for different machines.

• Minimal Memory Requirement. By constructing a program slice from the input program initially, many data arrays that existed in the input program are removed from the resulting execution-driven simulation code.

• Automatic Operation. Obtaining a performance estimate using PERFORM is a automatic process  provided that all loop and branch information can be deduced from the input program. As a result, this method could be used by automatic or semi-automatic parallel compilation systems.

References