Framework Preconstruction and Aggregate Storage Subsumption Optimizations for Sisal 1.2

David C. Cann Computing Research Group, L-306 Lawrence Livermore National Laboratory. P.O. Box 808, Livermore, CA 94550 cann@sisal.llnl.gov

Abstract

In this paper, we briefly discuss and evaluate two optimizations for reducing memory management overhead in sisal 1.2 programs. The first, called framework preconstruction, eliminates superfluous allocatedeallocate sequences in cyclic computations. The second, called aggregate storage subsumption, reduces the management overhead for some record definitions. We have implemented both optimizations in the Optimizing sisal Compiler.

1 Introduction

In this document, we briefly describe, illustrate, and evaluate two optimizations for minimizing memory management overhead in sisal 1.2 programs. The first, called framework preconstruction, helps eliminate superfluous allocate-deallocate sequences in cyclic computations. The second, called aggregate storage subsumption, reduces the management overhead for some record definitions. We have implemented both optimizations in the Optimizing sisal Compiler (osc) [5].

sisal 1.2 is a functional language for parallel numerical computation [13]. The sisal language project began in 1983 as a cooperative venture between Digital Equipment Corporation, the University of Manchester (England), Lawrence Livermore National Laboratory, and Colorado State University [11]. The primary goal evolved to become the achievement of sequential and parallel execution performance superior to imperative languages [4,6,17]. sisal programs cannot contain side effects or aliases; hence, they are concise, easy to understand, and amenable to automatic parallelization. Regardless of the target architecture, sisal programs are determinate.

To begin, we introduce and illustrate both optimizations. Next we present the performance of seven sisal programs with and without the optimizations, and then we draw some conclusions. The performance data were collect on a Cray Y-MP/864 at the National Energy Research Supercomputer Center. We assume the reader is familiar with sisal 1.2, osc, and osc’s copyelimination optimizations and aggregate management techniques [3,15].

This document was an outgrowth of the Sisal Scientific Computing Initiative, started at Lawrence Livermore National Laboratory to educate scientists in the art of functional computing, and to transfer the technology to industry [2,16].

2 Framework Preconstruction

sisal 1.2 only supports hierarchical array definitions. A true matrix data type does not exist; that is, a sisal matrix defines an array of arrays [12].

Although simple and elegant, in the absence of aggressive optimization, this style of array representation can severly degrade performance, especially for iterative computations. For example, without optimization

for initial
I := 1;
A := Ain;
while ( I <= N ) repeat
I := old I + 1;
A := for L in 1,K cross M in 1,K
     returns array of old A[L,M]+1
     end for;
returns value of A
end for

allocates and deallocates N-1 instances of matrix A before yielding its final result. The unoptimized translation follows.

oldA = Ain;
for ( I = 1; I <= N; I++ ) {
A = Malloc( K integer pointers );
for ( L = 1; L <= K; L++ ) {
  R = Malloc( K integers );
  for ( M = 1; M <= K; M++ )
    R[M] = oldA[L][M]+1;
  A[L] = R;
  }
for ( L = 1; L <= K; L++ )
  Free( oldA[L] );
Free( oldA );
oldA = A;
}

Each iteration makes K+1 calls to the memory allocator to build the array of arrays, and then the same number of calls to the memory deallocator to recycle the storage from the previous iteration.

Framework preconstruction eliminates repetitive and superfluous allocation-deallocation sequences like the sequence shown above. That is, it would recognize that A comprises K row vectors of size K and that K itself is loop invariant. Then it would generate code to allocate and assemble A outside the loop:

/* PREBUILD THE FRAMEWORK FOR MATRIX A */
oldA = Ain;
A = Malloc( K integer pointers );
for ( L = 1; L <= N; L++ ) {
R = Malloc( K integers );
A[L] = R;
}
/* NOW DO THE ITERATIVE COMPUTATION */
for ( I = 1; I <= N; I++ ) {
for ( L = 1; L <= N; L++ )
for ( M = 1; M <= N; M++ )
A[L][M] = oldA[L][M]+1;
oldA = A;
}

A summary of the framework preconstruction algorithm follows.

* FOR each sequential or parallel loop M in the program DO
* FOR each subexpression X yielding an array of arbitrary
nesting or rank DO
* MAKE sure X matches one of the preconstruction classes shown later
in this section. This requires verification of the following
conditions:
  1. The size and shape of X is invariant to M.
  2. The definition and use of X does not involve
     component sharing of any kind.
  3. X is read-only within M and never modified.
  4. Constituents of X are not returned from M.
* IF all the above conditions hold and X matches one of the six
preconstruction classes, then do the transformation. Classes
three and four might require the preconstruction of an old
and new instance for X, which are pointer swapped at the
bottom of the body. Code is added to deallocate the old version
upon M's completion.

* END FOR
* END FOR

2.1 Preconstruction Classes

The six preconstruction classes mentioned in the above algorithm, and currently considered in osc, are shown below. In each class, M represents the outermost loop and X represents the preconstruction candidate:

class1 := for i in 1,n
X := for j in 1,n returns array of j + i end for;
% ONE OR MORE READ OPERATIONS FOR NEW X
y := X[1];
returns value of sum y
end for;
class2 := for initial
i := 1; y := 0;
while ( i <= n ) repeat
i := old i + 1;
X := for j in 1,n returns array of j + old i end for;
% ONE OR MORE READ OPERATIONS FOR NEW X
y := X[1];
returns value of sum y
end for;
class3 := for initial
i := 1; y := 0;
X := array_fill(1,n,1);
while ( i <= n ) repeat
i := old i + 1;
% OLD X IS READ IN THE DEFINITION OF NEW X
X := for j in 1,n returns array of j + old X[j] end for;
% ONE OR MORE READ OPERATIONS FOR NEW X
y := X[1];
returns value of sum y
end for;
class4 := for initial
i := 1; y := 0;
X := array_fill(1,n,1);
while ( i <= n ) repeat
i := old i + 1;
% OLD X IS READ IN THE DEFINITION OF NEW X
X := for j in 1,n returns array of j + old X[j] end for;
% ONE OR MORE READ OPERATIONS FOR NEW X
y := X[1];

% THE LAST VALUE OF X IS RETURNED FROM THE LOOP
returns value of X
end for;
class5 := for initial
  i := 1; y := 0;
  X := array_fill(1,n,1);
while ( i <= n ) repeat
  i := old i + 1;
  X := for j in 1,n returns array of j + old i end for;
  % ONE OR MORE READ OPERATIONS FOR NEW X
  y := X[1];
% THE LAST VALUE OF X IS RETURNED FROM THE LOOP
returns value of X
end for;
class6 := for i in 1,n
  X := for j in 1,n returns array of j + i end for;
% THE LAST VALUE OF X IS RETURNED FROM THE LOOP
returns value of X
end for;

3 Aggregate Storage Subsumption

As currently implemented in osc, unoptimized aggregate representations require special run time support that includes reference count, mutual exclusion, and storage allocation and deallocation operations. For small aggregates, the costs can be enormous. For example, without optimization

for J in 1,N
V := record[R:1.0;I:0.0];
returns array of V
end for

translates into

A := Malloc( N structure pointers );
for ( J = 1; J <= N; J++ ) {
V = Malloc( the structure );
V.RefCount = 1;
V.Mutex = UNLOCKED;
V.R = 1.0;
V.I = 0.0;
A[I] = V;
}

Table 1: Compilation options for fortran.

CRAY Y-MP/864  UNICOS 6.1  cf77:cft77 5.0.2.0
Desired Execution Mode  Options
Vector  -Zp -Wd”-ev68 -dci” -Wf”-pd”

which results in N+1 memory allocations and N reference count and mutual exclusion lock initializations.

Aggregate storage subsumption treats small aggregates (those having 1 to 3 scalar components) as scalar data instead of dynamic, reference counted objects. Hence, the optimized translation of the previous example is

  A := Malloc( N structures );
  for ( J = 1; J <= N; J++ ) {
    A[J].R = 1.0;
    V[J].I = 0.0;
    }

which requires only one storage allocation. All the initialization code is removed. The tradeoff is that the transformed records must now be passed-by-value. As such, osc only selects small records for subsumption. The selection processes, however, is independent of program behavior.

4 Performance Results

In this section, we present the performance for seven sisal programs with and without the memory management optimizations. We used fortran as the experimental control and collected the data on a Cray Y-MP/864. Table 1 shows the fortran compile options used in the study.

Table 2 describes the program suite. The smallest code is KIN16, a production code developed at the University of Colorado Medical Center (UCMC) [7]. KIN16 simulates the electrophoresis of looped protein and DNA complexes. We ran a complete production run requiring 42,000 time steps and 2 columns of 14,285 levels.

The next largest code in the suite is RICARD, also a production code developed at UCMC [8]. RICARD simulates experimentally observed elution patterns of proteins and ligands in a column of gel. For the comparison we ran a production run requiring 40,000 time steps to complete a simulation involving 5 proteins and a column of 1,215 levels.

The next largest code is BMK11A, a benchmark developed at Los Alamos National Laboratory to evaluate Cray computer systems. BMK11A exercises excerpts of a particle transport code. For the comparison we exercised each excerpt 200 times using vectors of 2560 elements.

The fourth code in the suite is the Livermore Loops (LOOPS), which is a set of 24 scientific kernels taken from production codes at llnl [14]. For many years, scientists have used the kernels

Table 2: The program suite.

Source

Program  Lines Time Steps Problem Size  Subject Area
KIN16  225  42000  2x14285  Gel Electrophoresis
RICARD  297  40000  5x1315  Gel Chromatography
BMK11A  1003  200  2560  Particle Transport
LOOPS  1116  4000  100-1000  Scientific Kernels
SIMPLE  1527  62  100x100  Hydrodynamics
UNSPLIT  1937  40  160x80  Hydrodynamics
WEATHER 2712  20  420km  Weather Modeling

to benchmark high-performance computers. For the comparison we timed 4000 repetitions of each kernel.

The next code is SIMPLE^{1}, a Lagrangian hydrodynamics benchmark developed at llnl [10]. This program simulates the behavior of fluid in a sphere, and uses a non-vector, but concurrent equation of state package. Here we ran a 100 × 100 problem requiring 62 time steps to complete.

UNSPLIT, the second largest code in the suite, is an unsplit integrator taken from an adaptive mesh refinement code at llnl [1]. For the comparison we propagated a shock down a tube comprising 160 × 80 zones, timing the first 40 steps of execution.

The largest and last program in the suite is WEATHER [9]. This code, developed at Royal Melbourne Institute of Technology, is a one-level barotropic weather prediction code. The Department of Meteorology at the University of Melbourne provided the original fortran, written and tuned for a VAX uniprocessor; as such, the code is explicitly scalar^{2}. Differing from the other programs, which occupy single source files, WEATHER occupies 33 files and manipulates complex data. For this code, we timed 20 cycles of execution using a 420 km grid.

For all the codes, the performance data reflects real arithmetic (64 bits).

Table 3 presents the compilation feedback for framework preconstruction, and Table 4 presents the resulting run time improvements. The data show that on average, preconstruction results in a 15% increase in performance. Further, the optimized programs compete well with fortran. The largest gain was for UNSPLIT, which improved by 34%.

Table 5 presents the resulting performance with and without aggregate subsumption. Here the optimization only applied to RICARD, SIMPLE, and WEATHER, and only WEATHER showed a gain in performance: improving by 37%. WEATHER relies on records to represent complex numbers. This is is not true for the other programs. Overall, subsumption eliminated over a quarter-million run time record storage allocations and deallocations, and lock manipulations.

1Different versions of SIMPLE exist. We used version 2a for this report.

2Personal communication with Martin Dix, CSIRO Division of Atmospheric Research, Australia.

Table 3: Program suite compilation feedback for framework preconstruction.

Framework Preconstruction

Candidates  Preconstruction Classes  Rank
Program  Total Selected 1 2 3 4 5 6  1 2 3
KIN16  11  1  0 0 0 1 0  0  0 1 0
RICARD  10  6  0 5 1 0 0  0  5 1 0
BMK11A  97  50  0 45 0 5 0  0  50 0 0
LOOPS  46  20  2 0 0 0 1 17 10 7 3
SIMPLE  80  33  4 19 10 0 0  0  9 24 0
UNSPLIT  149  107  43 60 0 4 0  0  47 60 0
WEATHER 126  22  2 20 0 0 0  0  10 12 0

Table 4: Performance data for the program suite with and without framework preconstruction.

Framework Preconstruction

CRAY Y-MP/864 Vector Seconds
Program  Sisal WITHOUT Sisal WITH Fortran
KIN16  81.0  74.9  79.5
RICARD  45.1  39.4  38.4
BMK11A  4.5  4.4  4.1
LOOPS  20.1  16.0  12.3
SIMPLE  12.0  9.4  9.0
UNSPLIT  15.4  10.2  7.3
WEATHER  6.3  6.1  6.2

Table 5: Performance data for the program suite with and without aggregate storage subsumption.

Aggregate Storage Subsumption

CRAY Y-MP/864 Vector Seconds
Program  Sisal WITHOUT Sisal WITH Fortran
KIN16  75.4  74.9  79.5
SIMPLE  9.4  9.4  9.0
WEATHER  9.7  6.1  6.2

5 Conclusions

In this report, we have described, illustrated, and evaluated two memory management optimizations for sisal 1.2 programs: framework preconstruction and aggregate storage subsumption. We demonstrated the importance of both optimizations by presenting the performance of seven of our largest sisal programs. The data show that functional programs, with some simple but critical optimizations, can compete with fortran on conventional vector supercomputers.

Acknowledgements

This work was supported by the Applied Mathematical Sciences subprogram of the Office of Energy Research, U.S. Department of Energy, by Lawrence Livermore National Laboratory under contract No. W-7405-Eng-48.

References

[1] J. B. Bell, P. Colella, J. A. Trangenstein, and M. Welcome. Adaptive mesh refinement on moving quadrilateral grids. In AIAA 9th Computational Fluid Dynamics Conference, June 1989.

[2] Mathew Burns. Sisal challenges Fortran. Supercomputing Review, 5(2):72–73, February 1992.

[3] D. C. Cann. Compilation Techniques for High Performance Applicative Computation. PhD thesis, Colorado State University, Computer Science Department, Fort Collins, CO, 1989.

[4] D. C. Cann. Retire Fortran? A Debate Rekindled. In Supercomputing 91, November 1991.

[5] D. C. Cann. The optimizing SISAL compiler: Version 12.0. Technical Report UCRL-MA-110080, Lawrence Livermore National Laboratory, April 1992.

[6] D. C. Cann, R. Wolski, and J. T. Feo. SISAL: Toward resolving the parallel programming crisis. In IPPS 1992 Parallel Systems Fair, March 1992.

[7] J. R. Cann. Analysis of the gel electrophoresis of looped protein-DNA complexes by computer simulation. Molecular Biology, (216), September 1990.

[8] J. R. Cann, E. York, J. Stewart, J. Vera, and R. Maccioni. Small zone gel chromatography of interacting systems: Theoretical and experimental evaluation of elution profiles for kinetically controlled macromolecule-ligand reactions. Analytical Biochemistry, (175), December 1988.

[9] P. Chang and G. Egan. An implementation of a barotropic numerical weather prediction model in the functional language SISAL. In Proceedings of the SIGPLAN 1990 Symposium on Principles and Practice of Parallel Programming, March 1990.

[10] W. P. Crowley, C. P. Henderson, and T. E. Rudy. The simple code. Technical Report UCID 17715, Lawrence Livermore National Laboratory, Livermore, CA, Februrary 1978.

[11] J. Feo, D. Cann, and R. Oldehoeft. A report on the Sisal language project. Journal of Parallel and Distributed Computing, 10:349–365, December 1990.

[12] J. T. Feo. Arrays in sisal. In The First International Workshop on Arrays, Functional Languages, and Parallel Systems, Montreal, Canada, September 1990.

[13] J. R. McGraw, S. K. Skedzielewski, S. J. Allan, R. R. Oldehoeft, J. Glauert, C. Kirkham, W. Noyce, and R. Thomas. Sisal: Streams and iteration in a single assignment language: Reference manual version 1.2. Manual M-146, Rev. 1, Lawrence Livermore National Laboratory, Livermore, CA, March 1985.

[14] F. H. McMahon. The Livermore Fortran kernels: A computer test of the numerical performance range. Technical Report UCRL-53745, Lawrence Livermore National Laboratory, Livermore, CA, December 1986.

[15] J. E. Ranelletti. Graph Transformation Algorithms for Array Memory Optimization in Applicative Languages. PhD thesis, University of California at Davis, Computer Science Department, Davis, California, 1987.

[16] Lisa Stapleton. Livermore labs offers cray time—free. Supercomputing Review, 4(5):14–15, May 1991.

[17] R. Wolski, J. Feo, and D. C. Cann. A prototype functional language implemenation for hierarchical-memory architectures. In 25th Hawaii International Conference on System Sciences, January 1992.

Disclaimer

This document was prepared as an account of work sponsored by an agency of the United States Government. Neither the United States Government nor the University of California nor any of their employees, makes any warranty, express or implied, or assumes any legal liability or responsibility for the accuracy, completeness, or usefulness of any information, apparatus, product, or process disclosed, or represents that its use would not infringe privately owned rights. Reference herein to any specific commercial products, process, or service by trade name, trademark, manufacturer, or otherwise, does not necessarily constitute or imply its endorsement, recommendation, or favoring by the United States Government or the University of California. The views and opinions of authors expressed herein do not necessarily state or reflect those of the United States Government or the University of California, and shall not be used for advertising or product endorsement purposes.